Dedekind-Zahl

Die freien distributiven Verbände der 0-, 1-, 2- und 3-stelligen, monotonen booleschen Funktionen, mit 2, 3, 6 bzw. 20 Elementen (Eine Mausbewegung über den Knoten des rechten Diagramms zeigt eine Beschreibung)

Die Dedekind-Zahlen sind eine schnell wachsende mathematische Folge aus ganzen Zahlen. Sie sind nach Richard Dedekind benannt, der sie 1897 definierte.^[1] Die Dedekind-Zahl ${\displaystyle M(n)}$ zählt die Anzahl der monotonen booleschen Funktionen in ${\displaystyle n}$ Variablen. Diese ist gleich der Anzahl der Antiketten in der Menge der Teilmengen einer ${\displaystyle n}$-elementigen Menge, der Anzahl der Elemente eines von ${\displaystyle n}$ Elementen frei erzeugten distributiven Verbandes oder gleich der Anzahl der abstrakten Simplizialkomplexe mit ${\displaystyle n}$ Elementen.

Für ${\displaystyle M(n)}$ kennt man exakte asymptotische Abschätzungen^[2][3][4] und exakte Ausdrücke in Form von Summationsformeln^[5], aber das Dedekind-Problem, den genauen Wert zu ermitteln, bleibt schwierig. Es gibt bislang keine geschlossene Formel und der genaue Wert von ${\displaystyle M(n)}$ ist nur für ${\displaystyle 0\leq n\leq 9}$ bekannt. (Folge A000372 in OEIS)

Definitionen

Eine n-stellige boolesche Funktion ist eine Funktion, deren Argumente ${\displaystyle n}$ boolesche Variable sind und deren Werte nur wahr oder falsch sein können, oder anders ausgedrückt, deren Ausgabe wieder eine boolesche Variable ist. Eine solche Funktion heißt monoton, wenn sich der Wert bei Änderung einer Eingangsvariable von falsch zu wahr nicht ändert oder ebenfalls von falsch zu wahr wechselt, aber niemals umgekehrt. Die Dedekind-Zahl ${\displaystyle M(n)}$ ist definiert als die Anzahl der verschiedenen ${\displaystyle n}$-stelligen, monotonen booleschen Funktionen.

Eine Antikette von Mengen, manchmal auch Sperner-Familie genannt, ist eine Familie von Mengen, bei der keine in einer anderen enthalten ist. Ist ${\displaystyle V}$ eine Menge von ${\displaystyle n}$ booleschen Variablen, so definiert eine Antikette ${\displaystyle A}$ von Teilmengen von ${\displaystyle V}$ eine ${\displaystyle n}$-stellige, monotone booleschen Funktion ${\displaystyle f}$, wobei der Funktionswert genau dann wahr ist, wenn die Menge der Eingangsvariablen mit Wert wahr ein Element der Antikette ${\displaystyle A}$ umfasst, und falsch sonst. Umgekehrt definiert jede ${\displaystyle n}$-stellige, monotone boolesche Funktion ${\displaystyle f}$ eine Antikette ${\displaystyle A}$, die aus allen minimalen Teilmengen von ${\displaystyle V}$ besteht, für die ${\displaystyle f}$ den Wert wahr annimmt, wenn mindestens die Eingangsvariablen dieser Teilmenge wahr sind. Daher ist die Dedekind-Zahl ${\displaystyle M(n)}$ gleich der Anzahl der verschiedenen Antiketten in der Potenzmenge einer ${\displaystyle n}$-elementigen Menge.^[4]

Eine dritte äquivalente Beschreibung dieser Anzahl verwendet Verbandstheorie. Für je zwei ${\displaystyle n}$-stellige, monotone boolesche Funktionen ${\displaystyle f}$ und ${\displaystyle g}$ erhält man zwei weitere solche Funktionen, nämlich ${\displaystyle f\land g}$ und ${\displaystyle f\lor g}$, das heißt deren logische Konjunktion und Adjunktion. Die Menge der ${\displaystyle n}$-stelligen, monotonen booleschen Funktionen bildet mit diesen Operationen einen distributiven Verband. Es handelt sich um den distributiven Verband, der sich gemäß dem Darstellungssatz von Birkhoff aus der partiell geordneten Menge ergibt, die durch die Teilmengen einer ${\displaystyle n}$-elementigen Menge mit der Inklusion als Ordnung entsteht. Diese Konstruktion erzeugt den freien distributiven Verband mit ${\displaystyle n}$ Erzeugenden. Die Dedekind-Zahl ${\displaystyle M(n)}$ ist also die Anzahl der Elemente des freien distributiven Verbandes mit ${\displaystyle n}$ Erzeugenden.^[6][7][8]

Die Dedekind-Zahlen ${\displaystyle M(n)}$ sind auch (um eins größer als) die Anzahlen der abstrakten Simplizialkomplexe mit ${\displaystyle n}$ Elementen, das heißt der Familien von Mengen, die mit jeder Menge auch alle Teilmengen enthalten. Jede Antikette bestimmt einen abstrakten Simplizialkomplex, nämlich die Menge der Teilmengen der Antiketten-Elemente, und umgekehrt bilden die maximalen Simplizes eines abstrakten Simplizialkomplexes eine Antikette.^[5]

Beispiele

Für ${\displaystyle n=2}$ gibt es sechs monotone boolesche Funktionen und sechs Antiketten auf der Menge ${\displaystyle \{x,y\}}$, die einander wie folgt entsprechen:

• Die Funktion ${\displaystyle f(x,y)=falsch}$, das heißt die Funktion, die unabhängig von den Argumenten stets falsch zurückgibt, gehört zur leeren Antikette ${\displaystyle \emptyset }$.
• Die logische Konjunktion ${\displaystyle f(x,y)=x\land y}$ gehört zur Antikette ${\displaystyle \{\{x,y\}\}}$, die nur aus dem Element ${\displaystyle \{x,y\}}$ besteht.
• Die Funktion ${\displaystyle f(x,y)=x}$, das heißt die Projektion auf das erste Argument, entspricht der einelementigen Antikette ${\displaystyle \{\{x\}\}}$.
• Die Funktion ${\displaystyle f(x,y)=y}$, das heißt die Projektion auf das zweite Argument, entspricht der einelementigen Antikette ${\displaystyle \{\{y\}\}}$.
• Die logische Adjunktion ${\displaystyle f(x,y)=x\lor y}$ gehört zur Antikette ${\displaystyle \{\{x\},\{y\}\}}$, die aus den beiden Elementen ${\displaystyle \{x\}}$ und ${\displaystyle \{y\}}$ besteht.
• Schließlich korrespondiert die konstante Funktion ${\displaystyle f(x,y)=wahr}$ zur Antikette ${\displaystyle \{\emptyset \}}$, deren einziges Element die leere Menge ist.

Werte

Die exakten Werte der Dedekind-Zahlen ${\displaystyle M(n)}$ sind für ${\displaystyle 0\leq n\leq 9}$ bekannt (Folge A000372 in OEIS):

n	M(n)	erstmals berechnet
0	2	Dedekind (1897)[1]
1	3
2	6
3	20
4	168
5	7.581	Church (1940)[6]
6	7.828.354	Ward (1946)[9]
7	2.414.682.040.998	Church (1965),[7] verifiziert von Berman und Köhler (1976)[10]
8	56.130.437.228.687.557.907.788	Wiedemann (1991)[11]
9	286.386.577.668.298.411.128.469.151.667.598.498.812.366	gleichzeitig von Jäkel (2023)[12][13] und Van Hirtum et al. (2023)[14]

DorFuchs erstveröffentlichte am 31. Oktober 2023 auf YouTube Approximationen von Alex Fihman, der bereits die ersten Stellen von ${\displaystyle M(9)}$ korrekt vorhergesagt hatte. Fihman berechnete den Wert von ${\displaystyle M(10)}$ mit verschiedenen Berechnungsmethoden auf zwischen ca. 8,89197 · 10⁷⁸ und 8,93619 · 10⁷⁸.^[15]

Ist ${\displaystyle n}$ gerade, so muss auch ${\displaystyle M(n)}$ gerade sein.^[16] Die Berechnung von ${\displaystyle M(5)}$ widerlegte die auf Garrett Birkhoff zurückgehende Vermutung, nach der ${\displaystyle M(n)}$ stets durch ${\displaystyle (2n-1)(2n-2)}$ teilbar sein sollte.^[6]

Summationsformeln

Kisielewicz^[5] hat die logische Definition von Antiketten in folgende arithmetische Formel zur Bestimmung der Dedekind-Zahlen übersetzt:

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

Dabei ist ${\displaystyle b_{i}^{k}}$ das ${\displaystyle i}$-te Bit der Zahl ${\displaystyle k}$, was mittels der Abrundungsfunktion ${\displaystyle \left\lfloor .\right\rfloor }$ auch als

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

geschrieben werden kann. Allerdings ist diese Formel zur Bestimmung von ${\displaystyle M(n)}$ wegen der hohen Anzahl der Summanden schon für ${\displaystyle n=6}$ nicht hilfreich.

Asymptotisches Wachstum

Die Logarithmen der Dedekind-Zahlen können durch die Ungleichungen

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

abgeschätzt werden. Die linke Ungleichung entsteht durch Abzählen der Antiketten mit genau ${\displaystyle \lfloor n/2\rfloor }$ Elementen und die rechte Ungleichung wurde von Kleitman und Markowsky^[2] bewiesen.

Korshunov^[3] erzielte noch genauere Abschätzungen:^[8]

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

für gerade ${\displaystyle n}$ und

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

für ungerade ${\displaystyle n}$, wobei

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

und

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

Die wesentliche Idee hinter diesen Abschätzungen ist, dass die meisten Antiketten nur aus Mengen mit Mächtigkeiten nahe an ${\displaystyle \textstyle {\frac {n}{2}}}$ bestehen.^[8]

Einzelnachweise

1. Richard Dedekind: Über Zerlegungen von Zahlen durch ihre größten gemeinsamen Teiler. In: Gesammelte Werke. Band 2, 1897, S. 732–734. 
2. Daniel Kleitman, G. Markowsky: On Dedekind’s problem: the number of isotone Boolean functions. II. In: Transactions of the American Mathematical Society. Band 213, 1975, S. 373–390, doi:10.2307/1998052. 
3. A. D. Korshunov: The number of monotone Boolean functions. In: Problemy Kibernet. Band 38, 1981, S. 5–108. 
4. Jeff Kahn: Entropy, independent sets and antichains: a new approach to Dedekind’s problem. In: Proceedings of the American Mathematical Society. Band 130, 2002, S. 371–378, doi:10.1090/S0002-9939-01-06058-0. 
5. Andrzej Kisielewicz: A solution of Dedekind’s problem on the number of isotone Boolean functions. In: Journal für die Reine und Angewandte Mathematik. Band 386, 1988, S. 139–144, doi:10.1515/crll.1988.386.139. 
6. Randolph Church: Numerical analysis of certain free distributive structures. In: Duke Mathematical Journal. Band 36, 1940, S. 732–734, doi:10.1215/s0012-7094-40-00655-x. 
7. Randolph Church: Enumeration by rank of the free distributive lattice with 7 generators. In: Notices of the American Mathematical Society. Band 11, 1965, S. 724. 
8. Nejib Zaguia: Isotone maps: enumeration and structure. In: Finite and Infinite Combinatorics in Sets and Logic (Proc. NATO Advanced Study Inst., Banff, Alberta, Kanada, 4. Mai 1991). 1993, S. 421–430. 
9. Morgan Ward: Note on the order of free distributive lattices. In: Transactions of the American Mathematical Society. Band 52, 1946, S. 423, doi:10.1090/S0002-9904-1946-08568-7. 
10. Joel Berman, Peter Köhler: Cardinalities of finite distributive lattices. In: Mitt. Math. Sem. Gießen. Band 121, 1976, S. 103–124. 
11. Doug Wiedemann: A computation of the eighth Dedekind number. In: Order. Band 8, 1991, S. 5–6, doi:10.1007/BF003858087. 
12. Christian Jäkel: A computation of the ninth Dedekind Number. 3. April 2023, arxiv:2304.00895 (englisch). 
13. Christian Jäkel: A computation of the ninth Dedekind Number. In: Journal of Computational Algebra. 2023, doi:10.1016/j.jaca.2023.100006 (englisch). 
14. Lennart Van Hirtum, Patrick De Causmaecker, Jens Goemaere, Tobias Kenter, Heinrich Riebler, Michael Lass, Christian Plessl: A computation of D(9) using FPGA Supercomputing. 6. April 2023, arxiv:2304.03039 (englisch). 
15. DorFuchs: Die 9. Dedekind-Zahl wurde nach 32 Jahren Suche gefunden! (ab 0:11:58) auf YouTube, 31. Oktober 2023.
16. Koichi Yamamoto: Note on the order of free distributive lattices. In: Science Reports of the Kanazawa University. Band 1, 1953, S. 5–6.