デデキント数

数学において、デデキント数（デデキントすう、英: Dedekind numbers）は急激に増大する整数列の一つで、1897年にこれを定義したリヒャルト・デーデキントにちなむ。デデキント数 M(n) は n 変数単調ブール関数の個数に等しい。等価的に、n 元集合の反鎖（英語版）の個数、n 個の生成元から生成される自由分配束（英語版）の元の個数でもあり、また n 元集合の抽象単体複体（英語版）の個数を表す。

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

定義

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

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

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

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

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

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

例

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 （オンライン整数列大辞典の数列 A000372）

これらのうち最初の6個は Church (1940) によって与えられた。M(6) は Ward (1946) によって計算された。M(7) は Church (1965) と Berman & Köhler (1976) により、M(8) は Wiedemann (1991) により計算された。M(9) は2023年に Christian Jäkel^[7]^[8] と Lennart Van Hirtum^[9] の二人により同時に計算された。

n が偶数ならば M(n) も偶数でなければならない^[10]。5番目のデデキント数 M(5) = 7581 の計算により、ガレット・バーコフ（英語版）の予想「（n = 1 を除き）M(n) は必ず (2n − 1)(2n − 2) で割り切れる」は反証された^[11]。

和による公式

Kisielewicz (1988) は反鎖の論理学的定義を、次の算術的公式に書き直した。

M(n)=\sum _{k=1}^{2^{2^{n}}}\prod _{j=1}^{2^{n}-1}\prod _{i=0}^{j-1}\left(1-b_{i}^{k}b_{j}^{k}\prod _{m=0}^{\log _{2}i}(1-b_{m}^{i}+b_{m}^{i}b_{m}^{j})\right),

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

b_{i}^{k}=\left\lfloor {\frac {k}{2^{i}}}\right\rfloor -2\left\lfloor {\frac {k}{2^{i+1}}}\right\rfloor .

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

漸近評価

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

{n \choose \lfloor n/2\rfloor }\leq \log _{2}M(n)\leq {n \choose \lfloor n/2\rfloor }\left(1+O\left({\frac {\log n}{n}}\right)\right).

ここで左側の不等式はちょうど $\lfloor n/2\rfloor$ 個の元から成る反鎖の個数を数えることで得られ、右側の不等式は Kleitman & Markowsky (1975) により証明された。

Korshunov (1981) は、以下のより正確な評価式を導いた^[12]。

n が偶数のとき、

M(n)=(1+o(1))2^{n \choose \lfloor n/2\rfloor }\exp a(n)

n が奇数のとき、

M(n)=(1+o(1))2^{n \choose \lfloor n/2\rfloor +1}\exp(b(n)+c(n))

ただし

a(n)={n \choose n/2-1}(2^{-n/2}+n^{2}2^{-n-5}-n2^{-n-4}),

b(n)={n \choose (n-3)/2}(2^{-(n+3)/2}+n^{2}2^{-n-6}-n2^{-n-3}),

c(n)={n \choose (n-1)/2}(2^{-(n+1)/2}+n^{2}2^{-n-4}).

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

脚注

^ Kleitman & Markowsky (1975); Korshunov (1981); Kahn (2002).
^ ^a ^b Kisielewicz (1988).
^ Wiedemann (1991).
^ Kahn (2002)
^ ここでの自由分配束の定義は（空の交わり、空の結びも含めて）任意有限個の元の交わりと結びを許すものである。ちょうど2個の元の交わりと結びのみを許す定義では、束の最大元と最小元は除かれねばならず、自由分配束の元の数はデデキント数から2を引いた値になる。
^ Church (1940); Church (1965); Zaguia (1993).
^ Jäkel, Christian (3 April 2023). "A computation of the ninth Dedekind Number". arXiv:2304.00895 [math.CO]。
^ Jäkel, Christian (2023). “A computation of the ninth Dedekind Number”. Journal of Computational Algebra. doi:10.1016/j.jaca.2023.100006.
^ Van Hirtum, Lennart (6 April 2023). "A computation of D(9) using FPGA Supercomputing". arXiv:2304.03039 [cs.DM]。
^ Yamamoto (1953).
^ Church (1940).
^ ^a ^b Zaguia (1993).
^ Brown, K. S., Generating the monotone Boolean functions

参考文献

Berman, Joel; Köhler, Peter (1976), “Cardinalities of finite distributive lattices”, Mitt. Math. Sem. Giessen 121: 103–124, MR0485609 .
Church, Randolph (1940), “Numerical analysis of certain free distributive structures”, Duke Mathematical Journal 6: 732–734, doi:10.1215/s0012-7094-40-00655-x, MR0002842 .
Church, Randolph (1965), “Enumeration by rank of the free distributive lattice with 7 generators”, Notices of the American Mathematical Society 11: 724 . As cited by Wiedemann (1991).
Dedekind, Richard (1897), “Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler”, Gesammelte Werke, 2, pp. 103–148 （『数の最大公約数による分解について』）
Kahn, Jeff (2002), “Entropy, independent sets and antichains: a new approach to Dedekind's problem”, Proceedings of the American Mathematical Society 130 (2): 371–378, doi:10.1090/S0002-9939-01-06058-0, MR1862115 .
Kisielewicz, Andrzej (1988), “A solution of Dedekind's problem on the number of isotone Boolean functions”, Journal für die Reine und Angewandte Mathematik 386: 139–144, doi:10.1515/crll.1988.386.139, MR936995
Kleitman, D.; Markowsky, G. (1975), “On Dedekind's problem: the number of isotone Boolean functions. II”, Transactions of the American Mathematical Society 213: 373–390, doi:10.2307/1998052, MR0382107 .
Korshunov, A. D. (1981), “The number of monotone Boolean functions”, Problemy Kibernet. 38: 5–108, MR0640855 .
Ward, Morgan (1946), “Note on the order of free distributive lattices”, Bulletin of the American Mathematical Society 52: 423, doi:10.1090/S0002-9904-1946-08568-7 .
Wiedemann, Doug (1991), “A computation of the eighth Dedekind number”, Order 8 (1): 5–6, doi:10.1007/BF00385808, MR1129608 .
Yamamoto, Koichi (1953), “Note on the order of free distributive lattices”, Science Reports of the Kanazawa University 2 (1): 5–6, MR0070608 .
Zaguia, Nejib (1993), “Isotone maps: enumeration and structure”, in Sauer, N. W.; Woodrow, R. E.; Sands, B., Finite and Infinite Combinatorics in Sets and Logic (Proc. NATO Advanced Study Inst., Banff, Alberta, Canada, May 4, 1991), Kluwer Academic Publishers, pp. 421–430, MR1261220 .
Jäkel, Christian (3 April 2023). "A computation of the ninth Dedekind Number" (英語). arXiv:2304.00895。.
Jäkel, Christian (2023). “A computation of the ninth Dedekind Number” (英語). Journal of Computational Algebra. doi:10.1016/j.jaca.2023.100006. .

[1] Kleitman & Markowsky (1975); Korshunov (1981); Kahn (2002).

[#1-2] Kisielewicz (1988).

[3] Wiedemann (1991).

[4] Kahn (2002)

[5] ここでの自由分配束の定義は（空の交わり、空の結びも含めて）任意有限個の元の交わりと結びを許すものである。ちょうど2個の元の交わりと結びのみを許す定義では、束の最大元と最小元は除かれねばならず、自由分配束の元の数はデデキント数から2を引いた値になる。

[6] Church (1940); Church (1965); Zaguia (1993).

[7] Jäkel, Christian (3 April 2023). "A computation of the ninth Dedekind Number". arXiv:2304.00895 [math.CO]。

[8] Jäkel, Christian (2023). “A computation of the ninth Dedekind Number”. Journal of Computational Algebra. doi:10.1016/j.jaca.2023.100006.

[9] Van Hirtum, Lennart (6 April 2023). "A computation of D(9) using FPGA Supercomputing". arXiv:2304.03039 [cs.DM]。

[10] Yamamoto (1953).

[11] Church (1940).

[z93-12] Zaguia (1993).

[13] Brown, K. S., Generating the monotone Boolean functions

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]