デデキント数

<imagemap> File:Monotone Boolean functions 0,1,2,3.svg|400px|thumb|right| 引数0, 1, 2, 3個の単調ブール関数の自由分配束は、それぞれ 2, 3, 6, 20個の元から成る（一番右の束の各元にマウスオーバーすると、その関数を記述する式が読める）。

circle 659 623 30 circle 658 552 35 circle 587 480 35 circle 659 481 35 circle 729 481 35 circle 588 410 35 circle 658 410 35 circle 729 410 35 circle 548 339 30 circle 604 339 30 circle 758 339 30 circle 661 339 35 circle 588 268 35 circle 659 267 35 circle 729 268 35 circle 588 197 35 circle 658 197 35 circle 729 197 35 circle 658 126 35 circle 659 56 30

desc bottom-left </imagemap>

数学において、デデキント数（デデキントすう、テンプレート:Lang-en-short）は急激に増大する整数列の一つで、1897年にこれを定義したリヒャルト・デーデキントにちなむ。デデキント数 M(n) は n 変数単調ブール関数の個数に等しい。等価的に、n 元集合のテンプレート:仮リンクの個数、n 個の生成元から生成されるテンプレート:仮リンクの元の個数でもあり、また n 元集合のテンプレート:仮リンクの個数を表す。

M(n) を表す漸近的に正確な式 および総和による表現式が知られている。しかし、M(n) を閉じた式で表すデデキントの問題は未だに難問であり、また M(n) の正確な値は n ≤ 9 の場合にしか知られていない。

定義

ブール関数とは、n 個のブール型変数（真か偽かのいずれかの値をとる変数。あるいは等価だが0か1かのビット値をとる変数）を入力とし、別のブール型変数を出力する関数である。ブール関数が単調であるとは、任意の入力の組合せに対して、1個の入力を偽から真に変えるとき、出力が偽から真に変わることはあっても真から偽に変わることはないことを言う。デデキント数 M(n) は、n 個の変数を入力値とする全ての単調なブール関数の個数を表す。

集合の反鎖（antichain, アンチチェイン、反チェイン）とは部分集合の族であって、どの相異なる2元も一方が他方を包含していないものを指す（これはテンプレート:仮リンク（Sperner family）としても知られる）。今 V を n 個のブール型変数の組とするとき、V の反鎖 A は次のように単調ブール関数 f を定める：真であるような入力変数の集合が、A の元を部分集合として少なくとも1つ持っているとき、f の出力を真とする。そうでないとき偽とする。

逆に、任意の単調ブール関数は同じようにして1つの反鎖を定める：出力が真となるような入力変数の定め方（真である入力変数の指定）の中で、包含関係について極小であるものを全て集めてきて A とする。

このように、デデキント数 M(n) は n 元集合の反鎖の個数に等しい。

これらと同じクラスを記述する3番目の同値な方法は束論を用いるものである。任意の2個の単調ブール関数 f, g から、別の単調ブール関数 f ∧ g（論理積）および f ∨ g（論理和） を作ることができる。全ての n 変数単調ブール関数から成る集合にこれら2つの二項演算を入れたものは分配束をなし、これは n 個の変数の冪集合に包含関係を順序として入れた半順序集合からテンプレート:仮リンクによって得られる束である。このような構成によって n 個の生成子による自由分配束が得られ、デデキント数はその束の元の数を与える。

デデキント数は n 元集合の抽象単体複体（n 元集合の冪集合の部分集合であって、性質「x が元で、y が x に包含されるならば y も元である」を持つもの）の個数に1を加えた値でもある。任意の反鎖は、その各元とそれらの全ての部分集合を集めてくることで1つの抽象単体複体を定める。逆に任意の抽象単体複体から、極大な部分集合を全て取り出してくると1つの反鎖になる。

例

n = 2 の場合、2変数単調ブール関数は6個あり、2元集合 {x,y} の部分集合で反鎖となるものも6個ある。

• 入力によらずに常に偽を返す関数 f(x,y) = false に対応する反鎖は空集合である。
• 論理積 f(x,y) = x ∧ y は1個の元 {x,y} のみから成る反鎖 { {x,y} } に対応する。
• 2番目の引数を無視して1番目の引数を返す関数 f(x,y) = x は1個の元 {x} のみから成る反鎖 { {x} } に対応する。
• 1番目の引数を無視して2番目の引数を返す関数 f(x,y) = y は1個の元 {y} のみから成る反鎖 { {y} } に対応する。
• 論理和 f(x,y) = x ∨ y は元 {x} と元 {y} から成る反鎖 { {x}, {y} } に対応する。
• 入力によらずに常に真を返す関数 f(x,y) = true は空集合のみから成る反鎖 {Ø} に対応する。

値

0 ≤ n ≤ 9 に対する正確なデデキント数が知られている。

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, 286386577668298411128469151667598498812366 （テンプレート:OEIS）

これらのうち最初の6個は テンプレート:Harvtxt によって与えられた。M(6) は テンプレート:Harvtxt によって計算された。M(7) は テンプレート:Harvtxt と テンプレート:Harvtxt により、M(8) は テンプレート:Harvtxt により計算された。M(9) は2023年に Christian Jäkel と Lennart Van Hirtum の二人により同時に計算された。

n が偶数ならば M(n) も偶数でなければならない。5番目のデデキント数 M(5) = 7581 の計算により、テンプレート:仮リンクの予想「（n = 1 を除き）M(n) は必ず (2n − 1)(2n − 2) で割り切れる」は反証された。

和による公式

テンプレート:Harvtxt は反鎖の論理学的定義を、次の算術的公式に書き直した。

$M(n)=\sum _{k=1}^{2^{2^n}}\prod _{j=1}^{2^n-1}\prod _{i=0}^{j-1}(1-b_i^k{b}_j^k\prod _{m=0}^{{\log }_{2}i}(1-b_m^i+b_m^i{b}_m^j)),$

ここで $b_i^k$ は整数 $k$ の整数第 $i$ 位のビットで、床関数を使うと

$b_i^k=\lfloor \frac{k}{2^i}\rfloor -2\lfloor \frac{k}{2^{i+1}}\rfloor .$

と書ける。大きな n に対しては和の項数が膨大になるため、M(n) を計算するのに有用ではない。

漸近評価

デデキント数の対数をとったものは次の上界・下界で漸近的な評価ができる。

$(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })\le {\log }_{2}M(n)\le (\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })(1+O\left(\frac{\log n}{n}\right)).$

ここで左側の不等式はちょうど $\lfloor n/2\rfloor$ 個の元から成る反鎖の個数を数えることで得られ、右側の不等式は テンプレート:Harvtxt により証明された。

テンプレート:Harvtxt は、以下のより正確な評価式を導いた。

n が偶数のとき、

$M(n)=(1+o(1))2^{(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor })}\exp a(n)$

n が奇数のとき、

$M(n)=(1+o(1))2^{(\genfrac{}{}{0ex}{}{n}{\lfloor n/2\rfloor +1})}\exp (b(n)+c(n))$

ただし

$a(n)=(\genfrac{}{}{0ex}{}{n}{n/2-1})(2^{-n/2}+n^2{2}^{-n-5}-n{2}^{-n-4}),$

$b(n)=(\genfrac{}{}{0ex}{}{n}{(n-3)/2})(2^{-(n+3)/2}+n^2{2}^{-n-6}-n{2}^{-n-3}),$

$c(n)=(\genfrac{}{}{0ex}{}{n}{(n-1)/2})(2^{-(n+1)/2}+n^2{2}^{-n-4}).$

とする。この評価式の背景にあるアイディアは、ほとんどの反鎖において、各元（部分集合）の濃度が n/2 に非常に近いという事実である。n = 2, 4, 6, 8 に対してKorshunovの公式はそれぞれ誤差率 9.8%, 10.2%, 4.1%, -3.3% の評価値を与える。

参考文献

• テンプレート:Citation.
• テンプレート:Citation.
• テンプレート:Citation. As cited by テンプレート:Harvtxt.
• テンプレート:Citation （『数の最大公約数による分解について』）
• テンプレート:Citation.
• テンプレート:Citation
• テンプレート:Citation.
• テンプレート:Citation.
• テンプレート:Citation.
• テンプレート:Citation.
• テンプレート:Citation.
• テンプレート:Citation.
• テンプレート:Cite arXiv.
• テンプレート:Cite journal.