デデキント数

数学において、デデキント数は、 1897 年に定義されたリチャード デデキントにちなんで名付けられた、急速に増加する整数列です。デデキント数M ( n ) は、n変数の単調ブール関数の数です。同様に、これはn元集合の部分集合の反連鎖の数、n個の生成元を持つ自由分配格子の元の数、およびn元集合上の抽象単体複体の数より 1 多い数です。

M ( n )の正確な漸近推定値と、その和としての正確な表現は知られている。[1]しかし、M ( n )の値を計算するというデデキントの問題は依然として困難である。M ( n )の^閉じた形式の表現は知られておらず、M ( n )の正確な値はn ≤ 9 （OEISの シーケンスA000372 ）の場合にのみ見つかっている。

ブール関数は、 n 個の ブール変数（つまり、偽または真のいずれかの値、または同等の0 または 1 のいずれかのバイナリ値）を入力として受け取り、別のブール変数を出力する関数です。入力のすべての組み合わせに対して、入力の 1 つを偽から真に切り替えると、出力が偽から真に切り替わるだけで、真から偽に切り替わらない場合に、ブール関数は単調です。デデキント数M ( n ) は、 n 個の変数に対する異なる単調ブール関数の数です。^[2]

集合の反鎖（スペルナー族とも呼ばれる）は、他のどの集合にも含まれない集合の族である。Vがn 個のブール変数の集合である場合、 Vの部分集合の反鎖A は単調ブール関数f を定義する。ここで、 fの値は、与えられた入力集合に対して、fへの真の入力の一部がAに属する場合は真となり、それ以外の場合は偽となる。逆に、すべての単調ブール関数は、このようにして、関数値を真にすることができるブール変数の最小の部分集合の反鎖を定義する。したがって、デデキント数M ( n ) は、 n要素の集合の部分集合の異なる反鎖の数に等しい。^[3]

同じクラスのオブジェクトを記述する 3 つ目の同等の方法は、格子理論を使用する方法です。任意の 2 つの単調ブール関数fとgから、別の 2 つの単調ブール関数f ∧ gとf ∨ g、つまりそれぞれそれらの論理積と論理和を見つけることができます。n 入力のすべての単調ブール関数の族は、これら 2 つの演算とともに、分配格子を形成します。これは、集合包含を半順序とするn変数の部分集合の半順序集合からバーコフの表現定理によって与えられる格子です。この構成により、 n個の生成元を持つ自由分配格子が生成されます。 ^[4]したがって、デデキント数は自由分配格子の要素を数えます。^[5]

デデキント数は、 n個の元を持つ集合上の抽象単体複体の数よりも 1 多く数えます。抽象単体複体は、集合族に属する集合の空でない部分集合もその集合族に属するという性質を持つ集合族です。任意の反鎖 ({Ø} を除く) は、反鎖メンバーの部分集合族である単体複体を決定し、逆に、複合体内の最大単体は反鎖を形成します。^[6]

n = 2の場合、6 つの単調ブール関数と、2 要素集合 { x , y } の部分集合の 6 つの反連鎖が存在します。

• 入力値を無視して常に false を返す関数f ( x , y ) = false は、空のアンチチェーンØ に対応します。
• 論理積 f ( x , y ) =  x  ∧  y は、単一の集合 { x , y } を含む反鎖 { { x , y } } に対応します。
• 2番目の引数を無視して最初の引数を返す関数f ( x , y ) =  xは、単一の集合 { x }を含む反鎖 { { x } } に対応します。
• 最初の引数を無視して2番目の引数を返す関数f ( x , y ) =  yは、単一の集合 { y } を含む反鎖 { { y } }に対応する。
• 論理和 f ( x , y ) =  x  ∨  y は、 2つの集合 { x } と{ y } を含む反鎖 { { x }, { y } } に対応します。
• 入力値を無視して常にtrueを返す関数f ( x , y )=trueは、空集合のみを含む反鎖{Ø}に対応する。^[7]

デデキント数の正確な値は0 ≤ n ≤ 9で知られています。

2、3、6、20、168、7581、7828354、2414682040998、56130437228687557907788、286386577668298411128469151667598498812366（OEISの配列A000372）。

これらの数値の最初の5つ（すなわち、M (0) からM (4)）は、Dedekint (1897) によって与えられました。^[8] M (5) は Church (1940) によって計算されました。M ( 6) は Ward (1946) によって計算され、M (7) は Church (1965) と Berman & Köhler (1976) によって計算され、M (8) は Wiedemann (1991) によって計算され、M (9) は 2023 年に Christian Jäkel ^{[9] [10]}と Lennart Van Hirtum らによって同時に発見されました。^[11]

nが偶数であれば、M ( n )も偶数でなければならない。^[12] 第5デデキント数M (5)=7581の計算により、 M ( n )は常に( 2n−  1)(2n − 2)で割り切れるというギャレット・バーコフの予想が反証された 。^[13]

Kisielewicz (1988) は、反鎖の論理的定義を、デデキント数の次の算術式に書き直しました。

${\displaystyle 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),}$

ここで は数 の 番目のビットであり、これは床関数を使用して次のように 表すことができます。${\displaystyle b_{i}^{k}}$${\displaystyle i}$${\displaystyle k}$

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

しかし、この式は合計に含まれる項の数が多いため、nが大きい場合のM ( n )の値を計算するのには役立ちません。 ^[14]

デデキント数の対数は境界値によって正確に推定 できる。

${\displaystyle {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).}$

ここで、左の不等式は各集合が正確に要素を持つ反鎖を数え、右の不等式はKleitman & Markowsky (1975) によって証明されました。 ${\displaystyle \lfloor n/2\rfloor }$

コルシュノフ（1981）はさらに正確な推定値を提供している^[15]

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

nが偶数の場合、

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

nが奇数の場合、

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

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

そして

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

これらの推定値の背後にある主な考え方は、ほとんどの反鎖において、すべてのセットのサイズがn /2に非常に近いということです。^[15] n = 2、4、6、8の場合、コルシュノフの式はそれぞれ9.8%、10.2%、4.1%、-3.3%の不正確な推定値を提供します。 ^[16]

• バーマン、ジョエル; ケーラー、ピーター (1976)、「有限分配格子の基数」、Mitt. Math. Sem. Giessen、121 : 103–124、MR  0485609。
• チャーチ、ランドルフ (1940)、「特定の自由分配構造の数値解析」、デューク数学ジャーナル、6 (3): 732–734、doi :10.1215/s0012-7094-40-00655-x、MR  0002842。
• チャーチ、ランドルフ（1965）、「7つの生成元を持つ自由分配格子のランクによる列挙」、アメリカ数学会誌、11：724Wiedemann (1991) より引用。
• デデキント、リチャード(1897)、「Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Tailer」、Gesammelte Werke、vol. 2、103–148ページ。
• カーン、ジェフ（2002）、「エントロピー、独立集合、反連鎖：デデキント問題への新しいアプローチ」、アメリカ数学会紀要、130（2）：371–378、doi：10.1090/S0002-9939-01-06058-0、MR  1862115。
• Kisielewicz、Andrzej (1988)、「等音音ブール関数の数に関するデデキントの問題の解決法」、Journal für die Reine und Angewandte Mathematik、1988 (386): 139–144、doi :10.1515/crll.1988.386.139、MR  0936995、S2CID  115293297
• クライトマン、Ｄ． Markowsky, G. (1975)、「デデキントの問題について: 同音ブール関数の数。II」、米国数学学会論文誌、213 : 373–390、doi :10.2307/1998052、JSTOR  1998052、MR  0382107。
• Korshunov, AD (1981)、「単調ブール関数の数」、Problemy Kibernet。、38 : 5–108、MR  0640855。
• トムバック、マティ (2001)、「デデキント数を数える論理的方法について」、計算理論の基礎、コンピュータサイエンスの講義ノート、第 2138 巻、pp. 424–427、doi :10.1007/3-540-44669-9_48、ISBN 978-3-540-42487-1。
• ウォード、モーガン(1946)、「自由分配格子の順序に関する注記」、アメリカ数学会報、52 :423、doi : 10.1090/S0002-9904-1946-08568-7。
• ヴィーデマン、ダグ（1991）、「8番目のデデキント数の計算」、Order、8（1）：5–6、doi：10.1007 / BF00385808、MR  1129608、S2CID  120878757。
• 山本 耕一 (1953)、「自由分配格子の順序に関するノート」、金沢大学理科報告、2 (1): 5–6、MR  0070608。
• Zaguia, Nejib (1993)、「Isotone マップ: 列挙と構造」、Sauer, NW、Woodrow, RE、Sands, B. (編)、集合と論理における有限および無限の組合せ論 (Proc. NATO Advanced Study Inst.、バンフ、アルバータ州、カナダ、1991 年 5 月 4 日)、Kluwer Academic Publishers、pp. 421–430、MR  1261220。