デデキント数のソースを表示

<imagemap>
File:Monotone Boolean functions 0,1,2,3.svg|400px|thumb|right|[[File:Loupe light.svg|15px|link=http://upload.wikimedia.org/wikipedia/commons/thumb/5/57/Monotone_Boolean_functions_0%2C1%2C2%2C3.svg/1500px-Monotone_Boolean_functions_0%2C1%2C2%2C3.svg.png]] 引数0, 1, 2, 3個の単調ブール関数の自由分配束は、それぞれ 2, 3, 6, 20個の元から成る<small>（一番右の束の各元にマウスオーバーすると、その関数を記述する式が読める）。</small>

circle 659 623 30 [[File:Boolean function 0000 0000.svg|contradiction]]
circle 658 552 35 [[File:Boolean functions like 1000 0000.svg|A and B and C]]
circle 587 480 35 [[File:Boolean functions like 1000 1000.svg|A and B]]
circle 659 481 35 [[File:Boolean functions like 1010 0000.svg|A and C]]
circle 729 481 35 [[File:Boolean functions like 1100 0000.svg|B and C]]
circle 588 410 35 [[File:Boolean functions like 1010 1000.svg|(A and B) or (A and C)]]
circle 658 410 35 [[File:Boolean functions like 1100 1000.svg|(A and B) or (B and C)]]
circle 729 410 35 [[File:Boolean functions like 1110 0000.svg|(A and C) or (B and C)]]
circle 548 339 30 [[File:Boolean functions like 1010 1010.svg|A]]
circle 604 339 30 [[File:Boolean functions like 1100 1100.svg|B]]
circle 758 339 30 [[File:Boolean functions like 1111 0000.svg|C]]
circle 661 339 35 [[File:Boolean functions like 1110 1000.svg|(A or B) and (A or C) and (B or C) <====> (A and B) or (A and C) or (B and C)]]
circle 588 268 35 [[File:Boolean functions like 1110 1010.svg|(A or B) and (A or C)]]
circle 659 267 35 [[File:Boolean functions like 1110 1100.svg|(A or B) and (B or C)]]
circle 729 268 35 [[File:Boolean functions like 1111 1000.svg|(A or C) and (B or C)]]
circle 588 197 35 [[File:Boolean functions like 1110 1110.svg|A or B]]
circle 658 197 35 [[File:Boolean functions like 1111 1010.svg|A or C]]
circle 729 197 35 [[File:Boolean functions like 1111 1100.svg|B or C]]
circle 658 126 35 [[File:Boolean functions like 1111 1110.svg|A or B or C]]
circle 659 56 30 [[File:Boolean function 1111 1111.svg|tautology]]

desc bottom-left
</imagemap>

[[数学]]において、'''デデキント数'''（デデキントすう、{{Lang-en-short|Dedekind numbers}}）は急激に増大する[[整数列]]の一つで、1897年にこれを定義した[[リヒャルト・デーデキント]]にちなむ。デデキント数 ''M''(''n'') は ''n'' 変数[[単調写像|単調]][[ブール関数]]の個数に等しい。等価的に、''n'' 元集合の{{仮リンク|反鎖|en|antichain}}の個数、''n'' 個の生成元から生成される{{仮リンク|自由分配束|en|free distributive lattice}}の元の個数でもあり、また ''n'' 元集合の{{仮リンク|抽象単体複体|en|abstract simplicial complex}}の個数を表す。

''M''(''n'') を表す漸近的に正確な式<ref>{{harvtxt|Kleitman|Markowsky|1975}}; {{harvtxt|Korshunov|1981}}; {{harvtxt|Kahn|2002}}.</ref> および[[総和]]による表現式<ref name="#1">{{harvtxt|Kisielewicz|1988}}.</ref>が知られている。しかし、''M''(''n'') を閉じた式で表す'''デデキントの問題'''は未だに難問であり、また ''M''(''n'') の正確な値は ''n''&nbsp;≤&nbsp;9 の場合にしか知られていない<ref>{{harvtxt|Wiedemann|1991}}.</ref>。

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

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

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

このように、デデキント数 ''M''(''n'') は ''n'' 元集合の反鎖の個数に等しい<ref>{{harvtxt|Kahn|2002}}</ref>。

これらと同じクラスを記述する3番目の同値な方法は[[束 (束論)|束論]]を用いるものである。任意の2個の単調ブール関数 ''f'', ''g'' から、別の単調ブール関数 ''f'' ∧ ''g''（[[論理積]]）および ''f'' ∨ ''g''（[[論理和]]） を作ることができる。全ての ''n'' 変数単調ブール関数から成る集合にこれら2つの二項演算を入れたものは分配束をなし、これは ''n'' 個の変数の冪集合に包含関係を順序として入れた[[順序集合|半順序集合]]から{{仮リンク|バーコフの表現定理|en|Birkhoff's representation theorem}}によって得られる束である。このような構成によって ''n'' 個の生成子による自由分配束<ref>ここでの自由分配束の定義は（空の交わり、空の結びも含めて）任意有限個の元の交わりと結びを許すものである。ちょうど2個の元の交わりと結びのみを許す定義では、束の最大元と最小元は除かれねばならず、自由分配束の元の数はデデキント数から2を引いた値になる。</ref>が得られ、デデキント数はその束の元の数を与える<ref>{{harvtxt|Church|1940}}; {{harvtxt|Church|1965}}; {{harvtxt|Zaguia|1993}}.</ref>。

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

== 例 ==
''n'' = 2 の場合、2変数単調ブール関数は6個あり、2元集合 {''x'',''y''} の部分集合で反鎖となるものも6個ある。
*入力によらずに常に偽を返す関数 ''f''(''x'',''y'')&nbsp;=&nbsp;false に対応する反鎖は空集合である。
*論理積 ''f''(''x'',''y'')&nbsp;=&nbsp;''x''&nbsp;∧&nbsp;''y'' は1個の元 {''x'',''y''} のみから成る反鎖 { {''x'',''y''} } に対応する。
*2番目の引数を無視して1番目の引数を返す関数 ''f''(''x'',''y'')&nbsp;=&nbsp;''x'' は1個の元 {''x''} のみから成る反鎖 { {''x''} } に対応する。
*1番目の引数を無視して2番目の引数を返す関数 ''f''(''x'',''y'')&nbsp;=&nbsp;''y'' は1個の元 {''y''} のみから成る反鎖 { {''y''} } に対応する。
*論理和 ''f''(''x'',''y'')&nbsp;=&nbsp;''x''&nbsp;∨&nbsp;''y'' は元 {''x''} と元 {''y''} から成る反鎖 { {''x''}, {''y''} } に対応する。
*入力によらずに常に真を返す関数 ''f''(''x'',''y'')&nbsp;=&nbsp;true は空集合のみから成る反鎖 {Ø} に対応する。

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

:2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, 286386577668298411128469151667598498812366 （{{OEIS|id=A000372}}）

これらのうち最初の6個は {{harvtxt|Church|1940}} によって与えられた。''M''(6) は {{harvtxt|Ward|1946}} によって計算された。''M''(7) は {{harvtxt|Church|1965}} と {{harvtxt|Berman|Köhler|1976}} により、''M''(8) は {{harvtxt|Wiedemann|1991}} により計算された。''M''(9) は2023年に Christian Jäkel<ref>{{Cite arXiv |last=Jäkel |first=Christian |date=2023-04-03 |title=A computation of the ninth Dedekind Number |class=math.CO |eprint=2304.00895 }}</ref><ref>{{Cite journal |last=Jäkel |first=Christian |year=2023 |title=A computation of the ninth Dedekind Number |journal=Journal of Computational Algebra |doi=10.1016/j.jaca.2023.100006 }}</ref> と Lennart Van Hirtum<ref>{{Cite arXiv |last=Van Hirtum |first=Lennart |date=2023-04-06 |title=A computation of D(9) using FPGA Supercomputing |class=cs.DM |eprint=2304.03039 }}</ref> の二人により同時に計算された。

''n'' が偶数ならば ''M''(''n'') も偶数でなければならない<ref>{{harvtxt|Yamamoto|1953}}.</ref>。5番目のデデキント数 ''M''(5)&nbsp;=&nbsp;7581 の計算により、{{仮リンク|ガレット・バーコフ|en|Garrett Birkhoff}}の予想「（''n'' = 1 を除き）''M''(''n'') は必ず (2''n''&nbsp;−&nbsp;1)(2''n''&nbsp;−&nbsp;2) で割り切れる」は反証された<ref>{{harvtxt|Church|1940}}.</ref>。

== 和による公式 ==
{{harvtxt|Kisielewicz|1988}} は反鎖の論理学的定義を、次の算術的公式に書き直した。
:<math>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),</math>
ここで <math>b_i^k</math> は整数 <math>k</math> の整数第 <math>i</math> 位の[[ビット]]で、[[床関数と天井関数|床関数]]を使うと
:<math>b_i^k=\left\lfloor\frac{k}{2^i}\right\rfloor - 2\left\lfloor\frac{k}{2^{i+1}}\right\rfloor.</math>
と書ける。大きな ''n'' に対しては和の項数が膨大になるため、''M''(''n'') を計算するのに有用ではない。

== 漸近評価 ==
デデキント数の[[対数]]をとったものは次の上界・下界で漸近的な評価ができる。
:<math>{n\choose \lfloor n/2\rfloor}\le \log_2 M(n)\le {n\choose \lfloor n/2\rfloor}\left(1+O\left(\frac{\log n}{n}\right)\right).</math>
ここで左側の不等式はちょうど <math>\lfloor n/2\rfloor</math> 個の元から成る反鎖の個数を数えることで得られ、右側の不等式は {{harvtxt|Kleitman|Markowsky|1975}} により証明された。

{{harvtxt|Korshunov|1981}} は、以下のより正確な評価式を導いた<ref name="z93">{{harvtxt|Zaguia|1993}}.</ref>。

''n'' が偶数のとき、
:<math>M(n) = (1+o(1)) 2^{n\choose \lfloor n/2\rfloor}\exp a(n)</math>
''n'' が奇数のとき、
:<math>M(n) = (1+o(1)) 2^{n\choose \lfloor n/2\rfloor + 1}\exp (b(n)+c(n))</math>
ただし
:<math>a(n)={n\choose n/2-1}(2^{-n/2} + n^2 2^{-n-5} - n2^{-n-4}),</math>
:<math>b(n)={n\choose (n-3)/2}(2^{-(n+3)/2} + n^2 2^{-n-6} - n2^{-n-3}),</math>
:<math>c(n)={n\choose (n-1)/2}(2^{-(n+1)/2} + n^2 2^{-n-4}).</math>
とする。この評価式の背景にあるアイディアは、ほとんどの反鎖において、各元（部分集合）の濃度が ''n''/2 に非常に近いという事実である<ref name="z93" />。''n'' = 2, 4, 6, 8 に対してKorshunovの公式はそれぞれ誤差率 9.8%, 10.2%, 4.1%, -3.3% の評価値を与える<ref>{{citation|first=K. S.|last=Brown|title=Generating the monotone Boolean functions|url=https://www.mathpages.com/home/kmath094/kmath094.htm}}</ref>。

== 脚注 ==
{{reflist|2}}

== 参考文献 ==
*{{citation
 | last1 = Berman | first1 = Joel
 | last2 = Köhler | first2 = Peter
 | mr = 0485609
 | journal = Mitt. Math. Sem. Giessen
 | pages = 103–124
 | title = Cardinalities of finite distributive lattices
 | volume = 121
 | year = 1976}}.
*{{citation
 | last = Church | first = Randolph
 | mr = 0002842
 | journal = Duke Mathematical Journal
 | pages = 732–734
 | title = Numerical analysis of certain free distributive structures
 | volume = 6
 | year = 1940
 | doi=10.1215/s0012-7094-40-00655-x}}.
*{{citation
 | last = Church | first = Randolph
 | journal = Notices of the American Mathematical Society
 | page = 724
 | title = Enumeration by rank of the free distributive lattice with 7 generators
 | volume = 11
 | year = 1965}}. As cited by {{harvtxt|Wiedemann|1991}}.
*{{citation
 | last = Dedekind | first = Richard | author-link = Richard Dedekind
 | contribution = Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler
 | pages = 103–148
 | title = Gesammelte Werke
 | volume = 2
 | year = 1897}} （『数の最大公約数による分解について』）
*{{citation
 | last = Kahn | first = Jeff
 | doi = 10.1090/S0002-9939-01-06058-0
 | mr = 1862115
 | issue = 2
 | journal = Proceedings of the American Mathematical Society
 | pages = 371–378
 | title = Entropy, independent sets and antichains: a new approach to Dedekind's problem
 | volume = 130
 | year = 2002}}.
*{{citation
 | last = Kisielewicz | first = Andrzej
 | doi = 10.1515/crll.1988.386.139
 | mr = 936995
 | journal = Journal für die Reine und Angewandte Mathematik
 | pages = 139–144
 | title = A solution of Dedekind's problem on the number of isotone Boolean functions
 | volume = 386
 | year = 1988}}
*{{citation
 | last1 = Kleitman | first1 = D. | author1-link = Daniel Kleitman
 | last2 = Markowsky | first2 = G.
 | mr = 0382107
 | journal = Transactions of the American Mathematical Society
 | pages = 373–390
 | title = On Dedekind's problem: the number of isotone Boolean functions. II
 | volume = 213
 | year = 1975 | doi=10.2307/1998052}}.
*{{citation
 | last = Korshunov | first = A. D.
 | mr = 0640855
 | journal = Problemy Kibernet.
 | pages = 5–108
 | title = The number of monotone Boolean functions
 | volume = 38
 | year = 1981}}.
*{{citation
 | last = Ward | first = Morgan | authorlink = モーガン・ワード
 | journal = Bulletin of the American Mathematical Society
 | page = 423
 | title = Note on the order of free distributive lattices
 | volume = 52
 | doi = 10.1090/S0002-9904-1946-08568-7
 | year = 1946}}.
*{{citation
 | last = Wiedemann | first = Doug
 | doi = 10.1007/BF00385808
 | mr = 1129608
 | issue = 1
 | journal = [[Order (journal)|Order]]
 | pages = 5–6
 | title = A computation of the eighth Dedekind number
 | volume = 8
 | year = 1991}}.
*{{citation
 | last = Yamamoto | first = Koichi
 | mr = 0070608
 | issue = 1
 | journal = Science Reports of the Kanazawa University
 | pages = 5–6
 | title = Note on the order of free distributive lattices
 | volume = 2
 | year = 1953}}.
*{{citation
 | last = Zaguia | first = Nejib
 | contribution = Isotone maps: enumeration and structure
 | editor1-last = Sauer | editor1-first = N. W.
 | editor2-last = Woodrow | editor2-first = R. E.
 | editor3-last = Sands | editor3-first = B.
 | mr = 1261220
 | pages = 421–430
 | publisher = Kluwer Academic Publishers
 | title = Finite and Infinite Combinatorics in Sets and Logic (Proc. NATO Advanced Study Inst., Banff, Alberta, Canada, May 4, 1991)
 | year = 1993}}.
*{{cite arXiv
 | last = Jäkel | first = Christian
 | title = A computation of the ninth Dedekind Number
 | eprint=2304.00895
 | date = 2023-04-03
 | language = en}}.
*{{cite journal
 | last = Jäkel | first = Christian
 | title = A computation of the ninth Dedekind Number
 | journal = Journal of Computational Algebra
 | year = 2023
 | doi = 10.1016/j.jaca.2023.100006
 | language = en}}.
{{Classes of natural numbers}}

{{DEFAULTSORT:ててきんとすう}}
[[Category:整数の類]]
[[Category:束論]]
[[Category:組合せ論]]
[[Category:数理論理学]]
[[Category:数学に関する記事]]