Dedekind number

Last updated
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) Monotone Boolean functions 0,1,2,3.svg
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)

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.

Contents

Accurate asymptotic estimates of M(n) and an exact expression as a summation are known. [1] 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 (sequence A000372 in the 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. [2]

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

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 fg and fg, 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. [4] Thus, the Dedekind numbers count the elements in free distributive lattices. [5]

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

Example

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

Values

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

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

The first five of these numbers (i.e., M(0) to M(4)) are given by Dedekind (1897). [8] M(5) was calculated by Church (1940). M(6) was calculated by Ward (1946), M(7) was calculated by Church (1965) and Berman & Köhler (1976), M(8) by Wiedemann (1991) and M(9) was simultaneously discovered in 2023 by Christian Jäkel [9] [10] and Lennart Van Hirtum et al. [11]

If n is even, then M(n) must also be even. [12] 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). [13]

Summation formula

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

where is the th bit of the number , 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. [14]

Asymptotics

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 [15]

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. [15] 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. [16]

Notes

  1. Kleitman & Markowsky (1975); Korshunov (1981); Kahn (2002); Kisielewicz (1988).
  2. Kisielewicz (1988).
  3. Kahn (2002).
  4. The definition of free distributive lattices used here allows as lattice operations any finite meet and join, including the empty meet and empty join. For the free distributive lattice in which only pairwise meets and joins are allowed, one should eliminate the top and bottom lattice elements and subtract two from the Dedekind numbers.
  5. Church (1940); Church (1965); Zaguia (1993).
  6. Kisielewicz (1988).
  7. That this antichain corresponds to the top lattice element of the lattice can be seen by considering the definition of meet in the article on antichains.
  8. Tombak, Mati (2001). "On Logical Method for Counting Dedekind Numbers". Fundamentals of Computation Theory. Lecture Notes in Computer Science. Vol. 2138. pp. 424–427. doi:10.1007/3-540-44669-9_48. ISBN   978-3-540-42487-1.
  9. Jäkel, Christian (2023-04-03). "A computation of the ninth Dedekind Number". arXiv: 2304.00895 [math.CO].
  10. Jäkel, Christian (2023). "A computation of the ninth Dedekind number". Journal of Computational Algebra. 6–7. arXiv: 2304.00895 . doi: 10.1016/j.jaca.2023.100006 .
  11. Van Hirtum, Lennart (2023-04-06). "A computation of D(9) using FPGA Supercomputing". arXiv: 2304.03039 [cs.DM].
  12. Yamamoto (1953).
  13. Church (1940).
  14. For example, for , the summation contains terms, which is far beyond what can be numerically summed.
  15. 1 2 Zaguia (1993).
  16. Brown, K. S., Generating the monotone Boolean functions

Related Research Articles

<span class="mw-page-title-main">Boolean algebra (structure)</span> Algebraic structure modeling logical operations

In abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. This type of algebraic structure captures essential properties of both set operations and logic operations. A Boolean algebra can be seen as a generalization of a power set algebra or a field of sets, or its elements can be viewed as generalized truth values. It is also a special case of a De Morgan algebra and a Kleene algebra.

<span class="mw-page-title-main">Complete lattice</span> Partially ordered set in which all subsets have both a supremum and infimum

In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum (join) and an infimum (meet). A conditionally complete lattice satisfies at least one of these properties for bounded subsets. For comparison, in a general lattice, only pairs of elements need to have a supremum and an infimum. Every non-empty finite lattice is complete, but infinite lattices may be incomplete.

<span class="mw-page-title-main">Monotonic function</span> Order-preserving mathematical function

In mathematics, a monotonic function is a function between ordered sets that preserves or reverses the given order. This concept first arose in calculus, and was later generalized to the more abstract setting of order theory.

<span class="mw-page-title-main">Floor and ceiling functions</span> Nearest integers from a number

In mathematics, the floor function is the function that takes as input a real number x, and gives as output the greatest integer less than or equal to x, denoted x or floor(x). Similarly, the ceiling function maps x to the smallest integer greater than or equal to x, denoted x or ceil(x).

In mathematics, especially in order theory, a Galois connection is a particular correspondence (typically) between two partially ordered sets (posets). Galois connections find applications in various mathematical theories. They generalize the fundamental theorem of Galois theory about the correspondence between subgroups and subfields, discovered by the French mathematician Évariste Galois.

In mathematics, a Heyting algebra (also known as pseudo-Boolean algebra) is a bounded lattice (with join and meet operations written ∨ and ∧ and with least element 0 and greatest element 1) equipped with a binary operation ab of implication such that (ca) ≤ b is equivalent to c ≤ (ab). From a logical standpoint, AB is by this definition the weakest proposition for which modus ponens, the inference rule AB, AB, is sound. Like Boolean algebras, Heyting algebras form a variety axiomatizable with finitely many equations. Heyting algebras were introduced by Arend Heyting (1930) to formalize intuitionistic logic.

In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other. The prototypical examples of such structures are collections of sets for which the lattice operations can be given by set union and intersection. Indeed, these lattices of sets describe the scenery completely: every distributive lattice is—up to isomorphism—given as such a lattice of sets.

In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable.

Order theory is a branch of mathematics that investigates the intuitive notion of order using binary relations. It provides a formal framework for describing statements such as "this is less than that" or "this precedes that". This article introduces the field and provides basic definitions. A list of order-theoretic terms can be found in the order theory glossary.

This is a glossary of some terms used in various branches of mathematics that are related to the fields of order, lattice, and domain theory. Note that there is a structured list of order topics available as well. Other helpful resources might be the following overview articles:

A lattice is an abstract structure studied in the mathematical subdisciplines of order theory and abstract algebra. It consists of a partially ordered set in which every pair of elements has a unique supremum and a unique infimum. An example is given by the power set of a set, partially ordered by inclusion, for which the supremum is the union and the infimum is the intersection. Another example is given by the natural numbers, partially ordered by divisibility, for which the supremum is the least common multiple and the infimum is the greatest common divisor.

Sperner's theorem, in discrete mathematics, describes the largest possible families of finite sets none of which contain any other sets in the family. It is one of the central results in extremal set theory. It is named after Emanuel Sperner, who published it in 1928.

In mathematics, in the areas of order theory and combinatorics, Dilworth's theorem states that, in any finite partially ordered set, the maximum size of an antichain of incomparable elements equals the minimum number of chains needed to cover all elements. This number is called the width of the partially order. The theorem is named for the mathematician Robert P. Dilworth, who published it in 1950.

<span class="mw-page-title-main">Boolean function</span> Function returning one of only two values

In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set. Alternative names are switching function, used especially in older computer science literature, and truth function, used in logic. Boolean functions are the subject of Boolean algebra and switching theory.

Boolean algebra is a mathematically rich branch of abstract algebra. Stanford Encyclopaedia of Philosophy defines Boolean algebra as 'the algebra of two-valued logic with only sentential connectives, or equivalently of algebras of sets under union and complementation.' Just as group theory deals with groups, and linear algebra with vector spaces, Boolean algebras are models of the equational theory of the two values 0 and 1. Common to Boolean algebras, groups, and vector spaces is the notion of an algebraic structure, a set closed under some operations satisfying certain equations.

In mathematics, a Riesz space, lattice-ordered vector space or vector lattice is a partially ordered vector space where the order structure is a lattice.

<span class="mw-page-title-main">Post's lattice</span>

In logic and universal algebra, Post's lattice denotes the lattice of all clones on a two-element set {0, 1}, ordered by inclusion. It is named for Emil Post, who published a complete description of the lattice in 1941. The relative simplicity of Post's lattice is in stark contrast to the lattice of clones on a three-element set, which has the cardinality of the continuum, and a complicated inner structure. A modern exposition of Post's result can be found in Lau (2006).

<span class="mw-page-title-main">Dedekind–MacNeille completion</span> Smallest complete lattice containing a partial order

In mathematics, specifically order theory, the Dedekind–MacNeille completion of a partially ordered set is the smallest complete lattice that contains it. It is named after Holbrook Mann MacNeille whose 1937 paper first defined and constructed it, and after Richard Dedekind because its construction generalizes the Dedekind cuts used by Dedekind to construct the real numbers from the rational numbers. It is also called the completion by cuts or normal completion.

In theoretical computer science, multiparty communication complexity is the study of communication complexity in the setting where there are more than 2 players.

In computer science, pseudopolynomial time number partitioning is a pseudopolynomial time algorithm for solving the partition problem.

References