Английская Википедия:Dedekind number

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Шаблон:Short description <imagemap> File:Monotone Boolean functions 0,1,2,3.svg|400px|thumb|right|Файл:Loupe light.svg The free distributive lattices of monotonic Boolean functions on 0, 1, 2, and 3 arguments, with 2, 3, 6, and 20 elements respectively (move mouse over right diagram to see description)

circle 659 623 30 contradiction circle 658 552 35 A and B and C circle 587 480 35 A and B circle 659 481 35 A and C circle 729 481 35 B and C circle 588 410 35 (A and B) or (A and C) circle 658 410 35 (A and B) or (B and C) circle 729 410 35 (A and C) or (B and C) circle 548 339 30 A circle 604 339 30 B circle 758 339 30 C circle 661 339 35 (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 (A or B) and (A or C) circle 659 267 35 (A or B) and (B or C) circle 729 268 35 (A or C) and (B or C) circle 588 197 35 A or B circle 658 197 35 A or C circle 729 197 35 B or C circle 658 126 35 A or B or C circle 659 56 30 tautology

desc bottom-left </imagemap>

In mathematics, the Dedekind numbers are a rapidly growing sequence of integers named after Richard Dedekind, who defined them in 1897. The Dedekind number M(n) is the number of monotone boolean functions of n variables. Equivalently, it is the number of antichains of subsets of an n-element set, the number of elements in a free distributive lattice with n generators, and one more than the number of abstract simplicial complexes on a set with n elements.

Accurate asymptotic estimates of M(n) and an exact expression as a summation are known. However Dedekind's problem of computing the values of M(n) remains difficult: no closed-form expression for M(n) is known, and exact values of M(n) have been found only for n ≤ 9 Шаблон:OEIS.

Definitions

A Boolean function is a function that takes as input n Boolean variables (that is, values that can be either false or true, or equivalently binary values that can be either 0 or 1), and produces as output another Boolean variable. It is monotonic if, for every combination of inputs, switching one of the inputs from false to true can only cause the output to switch from false to true and not from true to false. The Dedekind number M(n) is the number of different monotonic Boolean functions on n variables.Шаблон:Sfnp

An antichain of sets (also known as a Sperner family) is a family of sets, none of which is contained in any other set. If V is a set of n Boolean variables, an antichain A of subsets of V defines a monotone Boolean function f, where the value of f is true for a given set of inputs if some subset of the true inputs to f belongs to A and false otherwise. Conversely every monotone Boolean function defines in this way an antichain, of the minimal subsets of Boolean variables that can force the function value to be true. Therefore, the Dedekind number M(n) equals the number of different antichains of subsets of an n-element set.

A third, equivalent way of describing the same class of objects uses lattice theory. From any two monotone Boolean functions f and g we can find two other monotone Boolean functions f ∧ g and f ∨ g, their logical conjunction and logical disjunction respectively. The family of all monotone Boolean functions on n inputs, together with these two operations, forms a distributive lattice, the lattice given by Birkhoff's representation theorem from the partially ordered set of subsets of the n variables with set inclusion as the partial order. This construction produces the free distributive lattice with n generators. Thus, the Dedekind numbers count the elements in free distributive lattices.

The Dedekind numbers also count one more than the number of abstract simplicial complexes on a set with n elements, families of sets with the property that any non-empty subset of a set in the family also belongs to the family. Any antichain (except {Ø}) determines a simplicial complex, the family of subsets of antichain members, and conversely the maximal simplices in a complex form an antichain.

Example

For n = 2, there are six monotonic Boolean functions and six antichains of subsets of the two-element set {x,y}:

• The function f(x,y) = false that ignores its input values and always returns false corresponds to the empty antichain Ø.
• The logical conjunction f(x,y) = x ∧ y corresponds to the antichain { {x,y} } containing the single set {x,y}.
• The function f(x,y) = x that ignores its second argument and returns the first argument corresponds to the antichain { {x} } containing the single set {x}
• The function f(x,y) = y that ignores its first argument and returns the second argument corresponds to the antichain { {y} } containing the single set {y}
• The logical disjunction f(x,y) = x ∨ y corresponds to the antichain { {x}, {y} } containing the two sets {x} and {y}.
• The function f(x,y) = true that ignores its input values and always returns true corresponds to the antichain {Ø} containing only the empty set.

Values

The exact values of the Dedekind numbers are known for 0 ≤ n ≤ 9:

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, 286386577668298411128469151667598498812366 Шаблон:OEIS.

The first five of these numbers (i.e., M(0) to M(4)) are given by Шаблон:Harvtxt. M(5) was calculated by Шаблон:Harvtxt. M(6) was calculated by Шаблон:Harvtxt, M(7) was calculated by Шаблон:Harvtxt and Шаблон:Harvtxt, M(8) by Шаблон:Harvtxt and M(9) was simultaneously discovered in 2023 by Christian Jäkel and Lennart Van Hirtum et al.

If n is even, then M(n) must also be even. The calculation of the fifth Dedekind number M(5) = 7581 disproved a conjecture by Garrett Birkhoff that M(n) is always divisible by (2n − 1)(2n − 2).

Summation formula

Шаблон:Harvtxt rewrote the logical definition of antichains into the following arithmetic formula for the Dedekind numbers:

<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>

where <math>b_i^k</math> is the <math>i</math>th bit of the number <math>k</math>, which can be written using the floor function as

<math>b_i^k=\left\lfloor\frac{k}{2^i}\right\rfloor - 2\left\lfloor\frac{k}{2^{i+1}}\right\rfloor.</math>

However, this formula is not helpful for computing the values of M(n) for large n due to the large number of terms in the summation.

Asymptotics

The logarithm of the Dedekind numbers can be estimated accurately via the bounds

<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>

Here the left inequality counts the antichains in which each set has exactly <math>\lfloor n/2\rfloor</math> elements, and the right inequality was proven by Шаблон:Harvtxt.

Шаблон:Harvtxt provided the even more accurate estimates

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

for even n, and

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

for odd n, where

<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>

and

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

The main idea behind these estimates is that, in most antichains, all the sets have sizes that are very close to n/2. For n = 2, 4, 6, 8 Korshunov's formula provides an estimate that is inaccurate by a factor of 9.8%, 10.2%, 4.1%, and −3.3%, respectively.

References

• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation. As cited by Шаблон:Harvtxt.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.
• Шаблон:Citation.