Dedekind number

In mathematics, the Dedekind numbers are a rapidly growing sequence of integers named after Richard Dedekind, who defined them in 1897.

Equivalently, it is the number of antichains of subsets of an

-element set, the number of elements in a free distributive lattice with

generators, and one more than the number of abstract simplicial complexes on a set with

[2] However Dedekind's problem of computing the values of

remains difficult: no closed-form expression for

[3] 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.

is the number of different monotonic Boolean functions on

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.

equals the number of different antichains of subsets of an

[5] A third, equivalent way of describing the same class of objects uses lattice theory.

we can find two other monotone Boolean functions

The family of all monotone Boolean functions on

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

variables with set inclusion as the partial order.

This construction produces the free distributive lattice with

[6] Thus, the Dedekind numbers count the elements in free distributive lattices.

) determines a simplicial complex, the family of subsets of antichain members, and conversely the maximal simplices in a complex form an antichain.

, there are six monotonic Boolean functions and six antichains of subsets of the two-element set

[11] M(6) was calculated by Ward in 1946,[12] M(7) was calculated by Church in 1965,[13] M(8) by Wiedemann in 1991,[14] and M(9) was independently discovered in 2023 by Jäkel[15] and Van Hirtum et al.[16] If n is even, then M(n) must also be even.

[17] 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).

[18] Kisielewicz (1988) rewrote the logical definition of antichains into the following arithmetic formula for the Dedekind numbers: where

, which can be written using the floor function as 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.

[19] The logarithm of the Dedekind numbers can be estimated accurately via the bounds Here the left inequality counts the antichains in which each set has exactly

elements, and the right inequality was proven by Kleitman & Markowsky (1975).

Korshunov (1981) provided the even more accurate estimates[20] for even n, and for odd n, where and The main idea behind these estimates is that, in most antichains, all the sets have sizes that are very close to n/2.

[20] 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.