TOPICS
Search

Dedekind Number


The number d(n) of monotone Boolean functions of n variables (equivalent to one more than the number of antichains on the n-set {1,2,...,n}) is called the nth Dedkind number. For n=0, 1, ..., d(n) is given by 2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, 286386577668298411128469151667598498812366, ... (OEIS A000372).

The numbers and their discovers are summarized in the following table (Yusun 2011, Jäkel 2023). The last of these values was found by Jäkel (2023) using 5311 GPU-hours and 4257682565 matrix multiplications on Nvidia A100 GPUs.

nd(n)source
02Dedekind (1897)
13Dedekind (1897)
26Dedekind (1897)
320Dedekind (1897)
4168Dedekind (1897)
57581Church (1940)
67828354Ward (1946)
72414682040998Church (1965)
856130437228687557907788Wiedemann (1991)
9286386577668298411128469151667598498812366Jäkel (2023)

The determination of these numbers is known as Dedekind's problem.


See also

Antichain, Boolean Function, Dedekind's Problem

Explore with Wolfram|Alpha

References

Church, R. "Numerical Analysis of Certain Free Distributive Structures." Duke Math. J. 6, 732-733, 1940.Dedekind, R. "Über Zerlegungen von Zahlen durch ihre grössten gemeinsammen Teiler." In Gesammelte Werke, Bd. 1. (Ed. K. May). Heidelberg, Germany: Mohr Siebeck, pp. 103-148, 1897.Church, R. "Enumeration by Rank of the Elements of the Free Distributive Lattice with Seven Generators." Not. Amer. Math. Soc. 12, 724, 1965.Jäkel, C. "A Computation of the Ninth Dedekind Number." 3 Apr 2023. https://arxiv.org/abs/2304.00895.Sloane, N. J. A. Sequence A000372/M0817 in "The On-Line Encyclopedia of Integer Sequences."Ward, M. "Note on the Order of the Free Distributive Lattice." Bull. Amer. Math. Soc. 52, 423, 1946.Wiedemann, D. "A Computation of the Eighth Dedekind Number." Order 8, 5-6, 1991.Yusun, T. J. L. "Dedekind Numbers and Related Sequences." M. S. thesis. Burnaby, British Columbia, Canada: Simon Fraser University, 2011. https://summit.sfu.ca/item/12001.

Cite this as:

Weisstein, Eric W. "Dedekind Number." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/DedekindNumber.html

Subject classifications