Dedekind number

The free distributive associations of the 0-, 1-, 2- and 3-digit, monotonic Boolean functions, with 2, 3, 6 or 20 elements (a mouse movement over the node in the diagram on the right shows a description)

In mathematics , the Dedekind numbers are a rapidly growing sequence of whole numbers . They are named after Richard Dedekind , who defined them in 1897. The Dedekind number counts the number of monotonous Boolean functions in variables. This is equal to the number of anti-chains in the set of subsets of a -elementary set, the number of elements of a freely generated distributive lattice or equal to the number of abstract simplicial complexes with elements. ${\displaystyle M(n)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$

For one knows exact asymptotic estimates and exact expressions in the form of summation formulas , but that Dedekind problem to determine the exact value is difficult. There is currently no closed formula and the exact value of is only known for. ${\displaystyle M(n)}$ ${\displaystyle M(n)}$ ${\displaystyle 0\leq n\leq 8}$

Definitions

An n -place Boolean function is a function whose arguments are Boolean variables and whose values ​​can only be true or false , or in other words, whose output is again a Boolean variable. Such a function is called monotonic if the value does not change when an input variable changes from false to true or also changes from false to true , but never vice versa. The Dedekind number is defined as the number of different -digit, monotone Boolean functions. ${\displaystyle n}$ ${\displaystyle M(n)}$ ${\displaystyle n}$

An anti-chain of sets, sometimes called the Sperner family, is a family of sets that have none in any other. Is a set of Boolean variables, defined as an anti chain of subsets of a -digit, monotone Boolean function , wherein the function value if and only true is when the amount of the input variables with a value of true is an element of the anti chain comprises, and false otherwise. Conversely defined every -digit, monotonous Boolean function is an anticchain , which consists of all minimal subsets of , for which assumes the value true , if at least the input variables of this subset are true . Therefore the Dedekind number is equal to the number of different anti-chains in the power set of a -elemental set. ${\displaystyle V}$ ${\displaystyle n}$ ${\displaystyle A}$ ${\displaystyle V}$ ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle A}$ ${\displaystyle V}$ ${\displaystyle f}$ ${\displaystyle M(n)}$ ${\displaystyle n}$

A third equivalent description of this number uses lattice theory . For every two -digit, monotone Boolean functions and one receives two more such functions, namely and , that is, their logical conjunction and adjunction . The set of -digit, monotonous Boolean functions forms a distributive lattice with these operations . It is the distributive lattice, which, according to Birkhoff's representation theorem, results from the partially ordered set that is created by the subsets of a -element set with the inclusion as the order. This construction creates the free distributive lattice with generators. The Dedekind number is therefore the number of elements of the free distributive lattice with generators. ${\displaystyle n}$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f\land g}$ ${\displaystyle f\lor g}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle M(n)}$ ${\displaystyle n}$

The Dedekind numbers are also (by one greater than) the numbers of the abstract simplicial complexes with elements, that is, the families of sets which with every set also contain all subsets. Each anti-chain defines an abstract simplicial complex, namely the set of subsets of the anti-chain elements, and conversely, the maximum simplices of an abstract simplicial complex form an anti-chain. ${\displaystyle M(n)}$ ${\displaystyle n}$

Examples

For there are six monotone Boolean functions and six antichains on the amount corresponding to each other as follows. ${\displaystyle n=2}$ ${\displaystyle \{x,y\}}$

• The function , that is, the function that always returns false regardless of the arguments , belongs to the empty anticchain . ${\displaystyle f(x,y)=falsch}$ ${\displaystyle \emptyset }$
• The logical conjunction belongs to the anti-chain , which consists only of the element . ${\displaystyle f(x,y)=x\land y}$ ${\displaystyle \{\{x,y\}\}}$ ${\displaystyle \{x,y\}}$
• The function , i.e. the projection onto the first argument, corresponds to the one-element anti-chain . ${\displaystyle f(x,y)=x}$ ${\displaystyle \{\{x\}\}}$
• The function , i.e. the projection onto the second argument, corresponds to the one-element anti-chain . ${\displaystyle f(x,y)=y}$ ${\displaystyle \{\{y\}\}}$
• The logical adjunction belongs to the anti-chain , which consists of the two elements and . ${\displaystyle f(x,y)=x\lor y}$ ${\displaystyle \{\{x\},\{y\}\}}$ ${\displaystyle \{x\}}$ ${\displaystyle \{y\}}$
• After all, the constant function corresponds to the anti-chain , the only element of which is the empty set. ${\displaystyle f(x,y)=wahr}$ ${\displaystyle \{\emptyset \}}$

values

The exact values ​​of the Dedekind numbers are only known for, these are: ${\displaystyle M(n)}$ ${\displaystyle 0\leq n\leq 8}$

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (sequence A000372 in OEIS ).

The first six of these numbers were obtained by Church. was calculated by Ward, by Church, Berman & Koehler, and goes back to Wiedemann. ${\displaystyle M(6)}$ ${\displaystyle M(7)}$ ${\displaystyle M(8)}$

Is straight , so must be straight. The calculation of disproved the assumption, which goes back to Garrett Birkhoff , according to which should always be divisible by . ${\displaystyle n}$ ${\displaystyle M(n)}$ ${\displaystyle M(5)}$ ${\displaystyle M(n)}$ ${\displaystyle (2n-1)(2n-2)}$

Summation formulas

Kisielewicz translated the logical definition of anti-chains into the following arithmetic formula for determining the Dedekind numbers:

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

It is the -th bit of the number , which by means of the rounding-off function as ${\displaystyle b_{i}^{k}}$ ${\displaystyle i}$ ${\displaystyle k}$ ${\displaystyle \left\lfloor .\right\rfloor }$

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

can be written. However, this formula is not helpful for determining because of the high number of summands for large ones. ${\displaystyle M(n)}$ ${\displaystyle n}$

Asymptotic growth

The logarithms of the Dedekind numbers can be given by the inequalities

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

be estimated. The left inequality is created by counting the anti-chains with exactly the elements and the right inequality was proven by Kleitman and Markowsky. ${\displaystyle \lfloor n/2\rfloor }$

Korshunov made even more precise estimates:

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

for straight and ${\displaystyle n}$

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

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

and

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

The main idea behind these estimates is that most anti-chains only consist of sets with thicknesses close to . ${\displaystyle \textstyle {\frac {n}{2}}}$

Individual evidence

1. ↑ Richard Dedekind: On the decomposition of numbers by their greatest common divisor . In: Collected Works . tape 2 , 1897, p. 732-734 .
2. ^ ^{A b} Daniel Kleitman, G. Markowsky: On Dedekind's problem: the number of isotone Boolean functions. II . In: Transactions of the American Mathematical Society . tape 213 , 1975, pp. 373-390 , doi : 10.2307 / 1998052 .
3. ↑ ^{a b} A. D. Korshunov: The number of monotone Boolean functions . In: Problemy Kibernet . tape 38 , 1981, pp. 5-108 .
4. ^ ^{A b} Jeff Kahn: Entropy, independent sets and antichains: a new approach to Dedekind's problem . In: Proceedings of the American Mathematical Society . tape 130 , 2002, pp. 371–378 , doi : 10.1090 / S0002-9939-01-06058-0 .
5. ^ ^{A b c} Andrzej Kisielewicz: A solution of Dedekind's problem on the number of isotone Boolean functions . In: Journal for Pure and Applied Mathematics . tape 386 , 1988, pp. 139-144 , doi : 10.1515 / crll.1988.386.139 .
6. ^ ^{A b} Doug Wiedemann: A computation of the eighth Dedekind number . In: Order . tape 8 , 1991, pp. 5-6 , doi : 10.1007 / BF003858087 .
7. ↑ ^{a b c} Randolph Church: Numerical analysis of certain free distributive structures . In: Duke Mathematical Journal . tape 36 , 1940, p. 732-734 , doi : 10.1215 / s0012-7094-40-00655-x .
8. ↑ ^{a b} Randolph Church: Enumeration by rank of the free distributive lattice with 7 generators . In: Notices of the American Mathematical Society . tape 11 , 1965, pp. 724 .
9. ↑ ^{a b c} Nejib Zaguia: Isotone maps: enumeration and structure . In: Finite and Infinite Combinatorics in Sets and Logic (Proc. NATO Advanced Study Inst., Banff, Alberta, Canada, May 4, 1991) . 1993, p. 421-430 .
10. ^ Morgan Ward: Note on the order of free distributive lattices . In: Transactions of the American Mathematical Society . tape 52 , 1946, pp. 423 , doi : 10.1090 / S0002-9904-1946-08568-7 .
11. ^ Joel Berman, Peter Koehler: Cardinalities of finite distributive lattices . In: Mitt. Math. Sem. Gießen . tape 121 , 1976, pp. 103-124 .
12. ^ Koichi Yamamoto: Note on the order of free distributive lattices . In: Science Reports of the Kanazawa University . tape 1 , 1953, p. 5-6 .