Dedekind number

In mathematics, the Dedekind numbers D_n form a rapidly growing sequence of integers that count the number of monotone Boolean functions on n variables, or equivalently, the number of antichains (including the empty set) in the Boolean lattice of subsets of an n-element set.^[1]^[2] These functions are increasing mappings from the power set to {0,1}, preserving the subset order, and the antichain equivalence arises because each such function corresponds to the collection of minimal sets where it evaluates to 1.^[3] Named after the 19th-century German mathematician Richard Dedekind, who introduced the problem in 1897 while investigating decompositions of integers based on their greatest common divisors, the sequence has since emerged as a cornerstone of enumerative combinatorics and lattice theory.^[4]^[5] The initial terms of the sequence, starting from n=0, are D_0 = 2, D_1 = 3, D_2 = 6, D_3 = 20, D_4 = 168, D_5 = 7581, D_6 = 7828354, D_7 = 2414682040998, D_8 = 56130437228687557907788, and D_9 = 286386577668298411128469151667598498812366.^[2]^[6] Dedekind himself computed the first four values, but larger terms have required sophisticated computational algorithms due to the double-exponential growth rate.^[4] The computation of D_9 in 2023, achieved independently by two teams using parallel processing and symmetry reductions, marked a significant milestone after decades of effort.^[7]^[8] Beyond enumeration, Dedekind numbers connect to diverse areas including free distributive lattices, where D_n gives the size of the free distributive lattice on n generators, and computational complexity, as determining whether a given monotone function exists ties into hard problems in Boolean analysis.^[2] Their study highlights fundamental challenges in counting discrete structures, with ongoing research exploring asymptotic bounds, generating functions, and applications in computer science such as circuit complexity and database theory.^[9]

Definitions and interpretations

Antichains in power set lattices

In the context of order theory, the power set of an n-element set, denoted $2^{}, consists of all $2^n subsets of = \{1, 2, \dots, n\}, partially ordered by set inclusion \subseteq. This poset, known as the Boolean lattice B_n, is graded by the cardinality of subsets, with the empty set \emptyset as the minimal element and the full set as the maximal element.^[10] The structure of B_n encodes the combinatorial properties of subsets under inclusion, making it a fundamental object in enumerative combinatorics.^[2] An antichain in a poset is a subset of elements where no two are comparable, meaning for any distinct A, B in the antichain, neither A \subseteq B nor B \subseteq A. In the Boolean lattice B_n, an antichain is thus a family of subsets where no set properly contains another. The Dedekind number D(n) counts the total number of such antichains, including the empty family:

D(n) = \bigl| \bigl\{ A \subseteq 2^{} \bigm| A \text{ is an antichain in } (2^{}, \subseteq) \bigr\} \bigr|.

This enumeration captures all possible collections of incomparable subsets, from the empty antichain to maximal ones like the Sperner capacity (the middle level of subsets of size \lfloor n/2 \rfloor).^[2] For small n, the antichains can be explicitly listed to illustrate the count. For n=0, B_0 has one element (the empty set), yielding two antichains: the empty family and \{\emptyset\}, so D(0) = 2. For n=1, the subsets are \emptyset and \{1\} with \emptyset \subset \{1\}; the antichains are the empty family, \{\emptyset\}, and \{\{1\}\}, giving D(1) = 3. These examples highlight how comparability under inclusion restricts collections, excluding pairs like \{\emptyset, \{1\}\}.^[2] The Dedekind numbers also enumerate down-sets (order ideals) in B_n, collections closed under taking subsets: if B \in I and A \subseteq B, then A \in I. There is a natural bijection between antichains and down-sets, where each antichain A corresponds to the down-set it generates (all subsets of elements in A), whose maximal elements recover A. Dually, up-sets (filters, closed under supersets) are enumerated by D(n) as well, via complements: the complement of a down-set is an up-set.^[6] This combinatorial interpretation arose from Richard Dedekind's 1897 investigation into the structure of distributive lattices, where he posed the problem of counting elements in certain posets equivalent to enumerating antichains in the Boolean lattice.^[6]

Monotone Boolean functions

A monotone Boolean function on n variables is a function f: \{0,1\}^n \to \{0,1\} that is non-decreasing with respect to the componentwise partial order on \{0,1\}^n, meaning that if \mathbf{x} \leq \mathbf{y} componentwise (i.e., x_i \leq y_i for all i=1,\dots,n), then f(\mathbf{x}) \leq f(\mathbf{y}).^[1] The nth Dedekind number D(n), also denoted M(n), counts the total number of such monotone Boolean functions.^[2] Each monotone Boolean function f corresponds uniquely to an up-set (or filter) in the Boolean lattice $2^{}, where the up-set is defined as U_f = \{\mathbf{x} \in \{0,1\}^n \mid f(\mathbf{x})=1\}. This set U_f is closed under taking supersets: if \mathbf{x} \in U_f and \mathbf{x} \leq \mathbf{y}, then \mathbf{y} \in U_f. Conversely, the characteristic function of any up-set in the Boolean lattice is monotone, establishing a bijection between monotone Boolean functions and up-sets.^[2] Thus, D(n) also equals the number of up-sets in the power set lattice of an n-element set.^[2] For n=2, there are D(2)=6 monotone Boolean functions on variables x_1, x_2 \in \{0,1\}, which can be explicitly listed as follows:

The constant function f(\mathbf{x}) = 0.
The projection f(\mathbf{x}) = x_1.
The projection f(\mathbf{x}) = x_2.
The conjunction f(\mathbf{x}) = x_1 \land x_2.
The disjunction f(\mathbf{x}) = x_1 \lor x_2.
The constant function f(\mathbf{x}) = 1.

These correspond to the up-sets: the empty set, the upset generated by (1,0), the upset generated by (0,1), the upset generated by (1,1), the upset generated by \{(1,0),(0,1)\}, and the full lattice, respectively.^[1]^[2] By duality in the Boolean lattice, the number of down-sets equals the number of up-sets, so D(n) also counts the down-sets. Specifically, for a monotone f, the complement function $1-f defines a down-set \{ \mathbf{x} \mid f(\mathbf{x})=0 \}, which is closed under taking subsets.^[2] The maximal elements of the down-set (or minimal elements of the up-set) form an antichain in the Boolean lattice, providing a bijection that links this functional perspective to the order-theoretic view of antichains.^[1]

Elements in free distributive lattices

A distributive lattice is a lattice (L, \wedge, \vee) satisfying the distributive laws

a \wedge (b \vee c) = (a \wedge b) \vee (a \wedge c)

and its dual

a \vee (b \wedge c) = (a \vee b) \wedge (a \vee c)

for all a, b, c \in L.^[11] The free distributive lattice \mathrm{FD}(n) on n generators is the initial object in the category of distributive lattices equipped with n distinguished generators x_1, \dots, x_n. It is constructed as the quotient of the free lattice (the term algebra generated by the x_i under \wedge and \vee) by the congruence ideal generated by the distributive laws, along with the associative, commutative, and idempotent laws of the operations, as well as the absorption laws a \wedge (a \vee b) = a and a \vee (a \wedge b) = a.^[8] Dedekind's theorem states that the cardinality of \mathrm{FD}(n) equals the nth Dedekind number D(n).^[2] This result was established by Dedekind in 1897 through a bijection between the elements of \mathrm{FD}(n) and the monotone Boolean functions on n variables.^[6] The elements of \mathrm{FD}(n) are the equivalence classes of terms formed from the generators x_1, \dots, x_n using \wedge and \vee, taken modulo the aforementioned lattice laws.^[1] Each such element corresponds to a monotone Boolean function, as the lattice operations align with pointwise meet and join on the functions induced by the generators.^[8] Equivalently, by Birkhoff's representation theorem, \mathrm{FD}(n) is isomorphic to the lattice of order ideals (down-sets) in its poset of join-irreducible elements, which is the Boolean lattice on n elements; each order ideal then corresponds to an antichain consisting of its maximal elements. For n=1, \mathrm{FD}(1) has three elements: the bottom element $0, the generator x

, and the top element &#36;1

.^[2]

History

Dedekind's introduction

Richard Dedekind (1831–1916), a leading figure in the development of modern abstract algebra, first encountered the structures now associated with Dedekind numbers during his work on algebraic number theory in the 1890s. While revising Peter Gustav Lejeune Dirichlet's Vorlesungen über Zahlentheorie for a new edition, Dedekind examined the lattices formed by ideals and modules in rings of algebraic integers, focusing on their generation under operations like intersection and the formation of least upper bounds. This investigation prompted him to consider the free distributive lattice generated by a finite set of elements, posing the question of determining the cardinality of such lattices for varying numbers of generators.^[6] In unpublished notes dated 1897, Dedekind explicitly computed the sizes of these free distributive lattices for small numbers of generators n, yielding 2 elements for n=0, 3 for n=1, 6 for n=2, 20 for n=3, and 168 for n=4. These values, later termed Dedekind numbers D(n), arose from his enumeration of the distinct elements producible through the lattice operations, reflecting the lattice's structure as the smallest distributive lattice containing the generators and closed under meets and joins. Dedekind noted the rapid growth of these cardinalities even for modest n, highlighting the combinatorial complexity involved. The notes were eventually reprinted in the second volume of his collected works.^[2]^[1] This work formed part of Dedekind's broader introduction of Dualgruppen—his term for partially ordered sets closed under binary suprema and infima, equivalent to modern lattices—in the published paper "Über die von drei Moduln erzeugte Dualgruppe" from the same year. There, he analyzed the Dualgruppe generated by three modules, emphasizing modular properties, but the distributive case in his notes extended the inquiry to fully distributive structures without modular anomalies. Dedekind's motivation stemmed from seeking a rigorous algebraic framework for divisor theory, connecting lattice enumerations to ideal decompositions in number fields.^[12]^[13]

Developments in the 20th century

In the early 20th century, Dedekind's work on free distributive lattices was rediscovered and systematized within the emerging field of lattice theory. Garrett Birkhoff's influential 1940 monograph Lattice Theory highlighted the enumeration of elements in these lattices, building on Dedekind's original calculations and establishing them as a central object of study in abstract algebra. Around the same time, Randolph Church computed the fifth Dedekind number, D(5) = 7581, extending the sequence beyond Dedekind's values up to D(4) = 168.^[2] This period also saw contributions from Philip Hall, whose 1930s research on the structure of distributive lattices, including subgroup counts in finite groups, provided foundational tools for analyzing lattice embeddings and irreducibles relevant to Dedekind's problem.^[14] The 1940s marked further progress in explicit computations, with Morgan Ward determining D(6) = 7,828,354 in 1946 using recursive methods on lattice ideals.^[1] Robert P. Dilworth's 1941 work on lattice decompositions and homomorphisms indirectly supported these efforts by clarifying the representation of distributive lattices as unions of chains, aiding the enumeration process. By the mid-century, the numbers began attracting attention in combinatorics, though initial focus remained on algebraic interpretations. The 1960s shifted emphasis toward combinatorial interpretations, particularly as counts of antichains in the power set lattice and monotone Boolean functions. Daniel Kleitman's 1969 paper (received 1968) provided the first rigorous enumeration algorithm for these objects, computing bounds and partial values that underscored their rapid growth and connection to Dedekind's lattice elements.^[15] Randolph Church revisited the sequence in 1965, calculating D(7) = 2,414,682,040,998 via exhaustive case analysis.^[2] This era solidified the dual views of Dedekind numbers, bridging order theory and Boolean function theory. By the 1970s, the computational challenges became evident, with the problem of counting monotone Boolean functions recognized as #P-hard, implying that exact values for larger n would require exponential resources.^[16] The late 20th century saw a milestone in 1991 when Douglas Wiedemann used a Cray-2 supercomputer for over 200 hours to compute D(8) = 56,130,437,228,687,557,907,788, demonstrating the escalating difficulty and need for advanced hardware.^[1] These advancements, while limited to small n, highlighted the numbers' role in testing algorithmic limits in combinatorics and lattice theory. In 2023, two independent teams achieved a breakthrough by computing the ninth Dedekind number D(9), a 42-digit value, using advanced parallel computing and optimized algorithms, marking the first update to the sequence in over three decades.^[6]

Computation and known values

Table of small values

The Dedekind numbers M(n) for small n up to 9 are known exactly, with computations becoming increasingly challenging due to their rapid growth. The following table lists these values, along with the researchers and years of their first computations.

n	M(n)	Computed by (year)
0	2	Dedekind (1897)
1	3	Dedekind (1897)
2	6	Dedekind (1897)
3	20	Dedekind (1897)
4	168	Dedekind (1897) https://mathworld.wolfram.com/DedekindNumber.html
5	7581	Church (1940) https://mathworld.wolfram.com/DedekindNumber.html
6	7828354	Ward (1946) https://mathworld.wolfram.com/DedekindNumber.html
7	2414682040998	Church (1965) https://mathworld.wolfram.com/DedekindNumber.html
8	56130437228687557907788	Wiedemann (1991) https://link.springer.com/article/10.1007/BF01107601
9	286386577668298411128469151667598498812366	Jäkel and independently Van Hirtum et al. (2023) https://arxiv.org/abs/2304.00895 https://arxiv.org/abs/2304.03039

For the larger values, the binary logarithms provide a sense of scale: \log_2 M(8) \approx 75.58 and \log_2 M(9) \approx 137.69.^[17]

Algorithms and challenges

Computing Dedekind numbers involves enumerating the down-sets (or equivalently, antichains or monotone Boolean functions) in the Boolean lattice of rank n, a task that requires checking vast numbers of candidates due to the exponential growth in the size of the power set $2^{}. The naive approach enumerates all possible subsets and verifies whether they form a valid down-set, but this runs in exponential time, specifically O(3^n) in the worst case without optimizations, as each element's inclusion depends on its predecessors.^[1] More efficient methods build on dynamic programming or recursive enumeration, constructing down-sets level by level according to the partial order. For instance, one can use a state-based recursion where the state represents the "filter" or "cut" at the current layer of the lattice, ensuring monotonicity by only extending valid partial down-sets; this prunes invalid branches early but still faces super-exponential time complexity for larger n. The transfer-matrix method, adapted from statistical mechanics, models the problem by representing states of minimal elements (or ideals) as vectors and transitions between layers as matrix multiplications, allowing computation for small n up to around 8 by iteratively multiplying matrices whose dimensions grow with the number of possible states at each level.^[8] Key historical algorithms include Church's 1940 computation of the fifth Dedekind number via enumeration and Ward's 1946 computation of the sixth via systematic counting of antichains with computational aids of the era. Later computations in the 1960s used inclusion-exclusion principles combined with dynamic programming over subsets, with Church reaching the seventh value in 1965. The computational complexity of counting down-sets in general posets, which includes the Boolean lattice case for Dedekind numbers, is #P-complete, as proven by Provan and Ball, implying that no polynomial-time algorithm exists unless P = NP, and explaining the inherent hardness even with optimized methods. In modern techniques as of 2025, computations leverage symmetries of the Boolean lattice and advanced matrix methods; for example, Jäkel's 2023 algorithm computes the ninth Dedekind number using matrix multiplication over equivalence classes of intervals in the free distributive lattice, incorporating automorphism groups to reduce redundancy and taking 28 days on eight graphical processing units (GPUs). Independently, Van Hirtum et al. used a custom enumeration with symmetry reduction and parallel processing to verify the same value. Experimental approaches like SAT solvers have been explored for bounding or approximating, but exact computation remains reliant on tailored enumeration due to the lack of closed-form expressions.^[8]^[7]^[18]^[19] The primary challenges stem from the super-exponential growth in both time and space requirements: the number of candidate states explodes as n increases, with storage for intermediate matrices or partial enumerations demanding terabytes for n=9, and projections suggesting n=10 would require infeasible resources exceeding current supercomputing capabilities. Thus, while values up to n=9 are now known, further progress hinges on breakthroughs in algorithmic symmetry exploitation or hardware acceleration.^[6]

Exact formulas

Recurrence relations

Dedekind numbers lack a simple linear recurrence of fixed order, consistent with their rapid super-exponential growth, but they admit recursive definitions derived from the layered structure of the Boolean lattice. These relations typically express D(n+1) as a sum over quantities associated with the downsets of the preceding lattice B_n, enabling step-by-step enumeration by dissecting the poset according to the role of the newest element n. A key recursive relation classifies downsets in B_{n+1} based on their status relative to the "top layer" consisting of sets containing the element n+1. For each downset a \in \mathcal{D}_n (the collection of all downsets in B_n), the extensions to B_{n+1} are determined by the possible ways to incorporate subsets from this top layer while preserving downward closure and the status inherited from a. This yields the recurrence

D(n+1) = \sum_{a \in \mathcal{D}_n} \top(a),

where \top(a) counts the valid top-layer extensions compatible with a. This formula can be reformulated in terms of the lattice of downsets itself, exploiting its distributive structure. Specifically,

D(n+1) = \# \Int(\mathcal{D}_n),

with \Int(\mathcal{D}_n) denoting the set of all intervals [x, y] (pairs of downsets x \leq y) in \mathcal{D}_n. To facilitate computation, intervals are partitioned into equivalence classes under a suitable relation \equiv that preserves extension counts, giving

D(n+1) = \sum_{[I] \in \Int(\mathcal{D}_n)/\equiv} \#[I].

Such equivalences reduce redundancy in enumeration by grouping structurally similar intervals. These recursive relations, while inherently exponential in complexity due to the summation over \mathcal{D}_n, underpin practical algorithms for verifying small Dedekind numbers and tie into broader poset dissections, such as those using the lattice's zeta function to track compatible extensions without yielding shorter recurrences. Generating functions incorporating the Boolean lattice's automorphism or symmetry properties offer piecewise recursive insights for low n, as originally explored by Dedekind in manual computations up to n=4, but they do not simplify to closed forms.

Inclusion-exclusion summation

The Dedekind number D(n) can be expressed using the inclusion-exclusion principle applied to the total number of families of subsets of an n-element set, excluding those containing comparable elements. Equivalently, since D(n) counts the antichains in the Boolean lattice B_n of rank n^[1], this summation systematically subtracts and adds back overcounts of families violating the antichain property via specific comparable pairs. Let \mathcal{P} denote the set of all ordered comparable pairs (A, B) where A \subsetneq B \subseteq , with || = n. The cardinality of \mathcal{P} is $3^n - 2^n. For each such pair, define the bad property P_{A,B} as the families of subsets that include both A and B. The total number of families is $2^{2^n}. The inclusion-exclusion principle then yields the number of families avoiding all bad properties (i.e., antichains) as

D(n) = \sum_{S \subseteq \mathcal{P}} (-1)^{|S|} \cdot 2^{2^n - \left| \bigcup_{(A,B) \in S} \{A, B\} \right|}

where the union in the exponent counts the distinct subsets forced to be included to satisfy the properties in S. This formula is exact but combinatorially explosive, with $2^{3^n - 2^n} terms, rendering it unsuitable for direct computation beyond trivial n. This summation highlights the combinatorial essence of Dedekind numbers as sieving out non-antichain structures, contrasting with recursive approaches that build upon smaller instances.

Asymptotic analysis

Growth bounds

The Dedekind number D(n) admits a trivial upper bound of D(n) \leq 2^{2^n}, obtained by noting that the total number of subsets of the power set of an n-element set is $2^{2^n}, and the antichains form a subset of these.^[10] A basic lower bound arises from Sperner's theorem, which states that the largest antichain in the Boolean lattice has size \binom{n}{\lfloor n/2 \rfloor}. Any subset of this middle level is itself an antichain, yielding D(n) \geq 2^{\binom{n}{\lfloor n/2 \rfloor}}.^[10] In 1966, Hansel established an improved upper bound of D(n) \leq 3^{\binom{n}{\lfloor n/2 \rfloor}} via a partition of the Boolean lattice into chains, allowing the counting of order-preserving functions along these chains.^[20] Kleitman (1969) further sharpened the upper bound, demonstrating that D(n) \leq 2^{\binom{n}{\lfloor n/2 \rfloor} (1 + o(1))}, which shows the lower bound is asymptotically tight in the leading exponential term.^[21]

Logarithmic estimates

The asymptotic behavior of the Dedekind number D(n) is captured by the relation \log_2 D(n) \sim \binom{n}{\lfloor n/2 \rfloor} as n \to \infty. This equivalence implies that D(n) = 2^{\binom{n}{\lfloor n/2 \rfloor} + o\left( \binom{n}{\lfloor n/2 \rfloor} \right)}, highlighting that the logarithm of D(n) is dominated by the central binomial coefficient. Equivalently, \log_2 D(n) / \binom{n}{\lfloor n/2 \rfloor} \to 1 as n \to \infty.^[21] An early upper bound was established by Kleitman, who showed that \log_2 D(n) \le \binom{n}{\lfloor n/2 \rfloor} + O(n 2^{n/2}). This result demonstrated that the Dedekind number grows no faster than exponentially in the central binomial coefficient, up to a subdominant error term. The proof relies on partitioning the Boolean lattice and bounding the contributions from levels away from the middle.^[15] The asymptotic equivalence was proven by Kleitman (1969). Korshunov (1977) provided a more explicit asymptotic expansion. His analysis separates the cases of even and odd n and uses probabilistic methods, including local central limit theorems for the distribution of antichain sizes, to show that nearly all down-sets (or equivalently, monotone Boolean functions) are concentrated around a "Dedekind cut" near the middle level of the Boolean lattice. This concentration implies that the vast majority of such structures arise from selecting nearly arbitrary subsets of the middle layer while fixing the inclusion of lower layers and exclusion of upper layers. Kahn (2001) gave a simpler proof using entropy methods.^[21]^[22] Subsequent improvements have refined the error terms using advanced techniques such as entropy methods and container arguments. For instance, these have yielded tighter bounds, such as \log_2 D(n) = \binom{n}{\lfloor n/2 \rfloor} + O\left( \binom{n}{\lfloor n/2 \rfloor} \frac{\log n}{n} \right), providing more granular insight into the subleading contributions without altering the dominant term. These approaches emphasize the structural uniformity of typical antichains near the middle binomial level.^[23]