The ninth Dedekind number

Privacy & Cookies: This site uses cookies. By continuing to use this website, you agree to their use.
To find out more, including how to control cookies, see here: Cookie Policy

In April 2023, a new mathematical milestone was reached when scientists discovered the ninth Dedekind number:

286386577668298411128469151667598498812366.
To be pedantic, this newly-discovered number is actually the tenth in a sequence of rapidly increasing integers, first defined by mathematician Richard Dedekind in the 1890s. Like all sane people, Dedekind believed in indexing from zero. So, the first number in this sequence is the zeroth Dedekind number, the second is the first, and so on. Not confusing at all.

This ninth Dedekind number was, in fact, simultaneously and independently discovered by two separate research groups, both unaware of the other’s work. Christian Jäkel, mathematician at TU Dresden, published his algorithm and computation of the 42-digit number on 3 April. Three days later, Lennart Van Hirtum with a team from KU Leuven and Paderborn University published a paper, employing a very different technique. They got the same result—a relief for both, no doubt.

Before tackling the mathematical definition of Dedekind numbers, let’s rewind 192 years. Julius Wilhelm Richard Dedekind was born on 6 October 1831 in Braunschweig, Germany. Deciding that Julius Wilhelm Richard was too much of a mouthful, he dropped his first two names before starting his mathematics studies at the University of Göttingen in 1850. He finished his PhD just two years later, as Gauss’s last doctoral student, before moving to Berlin where he hung out with Riemann for a couple of years. Two years of hypothesising with Bernard was enough for Richard. He moved back to Göttingen, where he taught courses on geometry and probability, and became good friends with Dirichlet. Later, after a brief stint in Zürich, he returned to his hometown in 1862, where he worked and taught for the rest of his life, until his death in 1916.

Dedekind gave the field of mathematics many breakthroughs. In 1888, he published Was sind und was sollen die Zahlen? (roughly translating to ‘What are numbers and what are they good for?’) which included his definition of an infinite set. The Dedekind cut is a standard definition of the real numbers. Dedekind groups are groups where every subgroup is normal.

And Dedekind numbers, which he first defined in 1897, are a sequence of integers describing the number of different monotonic boolean functions of $n$ variables! Until March 2023, we only knew the first nine (up to $n=8$) of them. They are:

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788.
Now, I know what you’re thinking. What the heck is a ‘MoNoToNiC BoOlEaN fUnCtIoN oF $n$ VaRiAbLeS?’

Boolean

A Boolean variable is a variable whose value is either $1$ or $0$, or equivalently, true or false. A Boolean function is a function whose inputs are Boolean variables, and its output is also a Boolean variable. These are sometimes called switching functions, truth functions or logical functions.

A simple example of a Boolean function is one which is constant, always returning the same value no matter what the input is. For a Boolean variable $x$, the function
\[f(x) = 1\]
is a constant Boolean function. Another simple example of a Boolean function is the negation function:
\[f(x) = \begin{cases} \;0 & \text{if } x=1\\ \;1 & \text{if } x=0 \end{cases} \]
which negates the value of the input. In true/false terms, it returns false if $x$ = true, and true if $x$ = false. Another way of defining this function is with a truth table:

\[x\]	\[f(x)\]
0	1
1	0

Truth tables are a standard way of defining Boolean functions. A truth table has one column for each input variable, plus one final column showing all possible results of the function. Each row is one possible configuration of input variable values, and the result of the function for those values.

In Boolean algebra, the negation function, or not operator, is represented by the notation: $\neg x$. You might recognise this symbol from mathematical logic. The notation for the and and or operators, $\land$ and $\lor$, may also be familiar. This leads nicely into defining simple Boolean functions for two variables.

Truth table for and:

\[x\]	\[y\]	\[x \land y\]
0	0	0
1	0	0
0	1	0
1	1	1

Truth table for or:

\[x\]	\[y\]	\[x \lor y\]
0	0	0
1	0	1
0	1	1
1	1	1

For not, both $x$ and $y$ must be true for the function to return true. For or, either $x$ or $y$ can be true for the function to return true. In terms of ones and zeros, we can write these functions with ordinary arithmetic operations: $x \land y = xy$, $x \lor y = x + y-xy$, $\neg x = 1-x$.

Monotonic

In maths, the term monotonic describes something that changes in a way such that it either never decreases or never increases. I like to think of it as meaning ‘always going in the same direction’. For example, the function $f(x) = \mathrm{e}^x$ is monotonic, but $f(x) = \sin(x)$ is not monotonic.

A Boolean function is monotonic if, for any combination of inputs, switching one of the inputs from 0 to 1 only results in the output switching from 0 to 1, and not from 1 to 0. More precisely, an $n$-variable Boolean function is monotonic if the following holds: for two different inputs $\boldsymbol{x}=\{x_1, x_2, \dots, x_n\}$,  $\boldsymbol{y}=\{y_1, y_2, \dots, y_n\}$ with $x_i, y_j \in \{0,1\}$, if $x_i \leq y_i$ for all $i$, then $f(\boldsymbol{x}) \leq f(\boldsymbol{y})$.

This means, and eagle-eyed Chalkdust readers may have already spotted, that the or and and functions shown above are both examples of monotonic Boolean functions. But negation, $\neg x$, is a non-monotonic Boolean function.

In fact, the monotonic Boolean functions are defined by expressions which combine inputs using only the and ($\land$) and or ($\lor$) operators. The not ($\neg$) operator is forbidden. If it appears in the simplest form of a Boolean function’s definition, then the function is not monotonic.

To get a little more notationally-spicy, when other operators in Boolean algebra appear in a function, namely implication ($x \rightarrow y$), bi-implication ($x \leftrightarrow y$) and exclusive or ($x \oplus y$), they are non-monotonic by construction.

This is because writing these operators with and and or requires the use of not. Implication, which means ‘if $x$ then $y$’, can be written as: $x \rightarrow y = \neg x \lor y$. Bi-implication, also called ‘equivalence’, is equivalent (haha) to: $x \leftrightarrow y = (x \lor \neg y) \land (\neg x \lor y)$. Exclusive or, which returns true if and only if $x$ and $y$ are different and so is sometimes called ‘non-equivalence’, can be written as: $x \oplus y = (x \land \neg y) \lor (\neg x \land y)$. So, if you come across a Boolean function with any of these operators, you’ll know it’s non-monotonic. Alright, that’s enough notation overload.

Let’s look at a more complex example of a monotonic Boolean function, this time for three variables. The function \[ ((x \land y) \lor (x \land z) \lor (y \land z))\] can be expressed simply as ‘at least two of $x$, $y$ and $z$ are true.’ We can see this function is monotonic by examining its truth table, but we can also see this by drawing a Hasse diagram. These are diagrams that crop up in order theory, but for our intensive purposes, there is simply a directed edge in the graph from one node to another when one of the inputs changes from 0 to 1. We colour the nodes in the graph to represent the output of the function. If the output of our Boolean function, $((x \land y) \lor (x \land z) \lor (y \land z))$, equals $0$, the node is orange, and if it equals $1$, the node is blue.

A Boolean function is monotonic when its Hasse diagram representation, sometimes referred to as an $n$-cube labelled with truth values, has no upward edge from true to false. In our case, all the blue nodes are above the orange, so this Boolean function is monotonic. It’s worth mentioning, because I’m apparently incapable of writing an article without encountering them, that this function is also commonly represented with… you guessed it, a Venn diagram (ta-da!).

Speaking of cubes… this delivers us nicely to an alternative way of defining Dedekind numbers. The fun thing about Dedekind numbers is that they actually have multiple definitions, which you may find easier to digest depending on your preferred flavour of mathematics.

There are three common ways to define Dedekind numbers: in terms of Boolean functions, in set-theoretic terms, and in geometric terms by colouring the corners of an $n$-dimensional cube. Other definitions include: the number of antichains of subsets of an $n$-element set, the number of elements in a free distributive lattice with $n$ generators, or one more than the number of abstract simplicial complexes on a set with $n$ elements.

I’m no pure mathematician, let alone a set theorist, so I’ll leave these scary-sounding wordy ones for the reader to go ahead and investigate. But cubes? Sure, I can picture one of those!

You can think of a monotone Boolean function as game with an $n$-dimensional cube. Balance the cube on one corner and then colour each of the remaining corners either blue or orange. The rule is this: you may never place an orange corner above a blue one. The number of different ways of doing this for $n$ dimensions is equivalent to the $n$th Dedekind number.

It makes sense that this cube-colouring definition is equivalent to the Boolean function one. An $n$-dimensional cube has $2^n$ vertices. For a Boolean function of $n$ variables, there are $2^n$ possible input states since each variable can either be 1 or 0—each state matches up with one of the vertices of the $n$-cube. For each possible input state, there are two possible outputs, again either 1 or 0—this corresponds to colouring each vertex of the $n$-cube in one of two colours. Thus, there are $2^{2^n}$ possible Boolean functions of $n$ variables—the same number of ways to colour the corners of an $n$-cube.

Dedekind

Let’s start with the trivial case, $n=0$. We’re dealing with a zero-dimensional cube, which is actually just a single point (a zero-dimensional anything is a single point). And since this single point can either be blue or orange, we see that the zeroth Dedekind number is 2. In terms of Boolean functions, the functions that have zero variables are the constant functions: $f=0$ and $f=1$, and both these are monotonic. This is another way of seeing that the first Dedekind number is $2$. Hurrah!

Onto the next. When $n=1$, we’ve got one variable to play with. What could we possibly do with it? Well, we could either set it to a constant, $f(x) =0$, $f(x) = 1$, or we could return it via the identity function: $f(x)=x$. This identity function satisfies all our requirements for being a monotonic Boolean function. The only other possible thing we could do with one variable is negate it, $f(x)=\neg x$, but recall that negation is forbidden when monotonicity is required. Thus, the number of monotonic Boolean functions with one variable is $3$. Woohoo!

A one-dimensional cube is just a line connecting two vertices. There are only three ways to colour these two vertices such that an orange node is never above a blue one. So again, we see that the first Dedekind number is 3.

Now onto $n=2$, where we’ve got two variables to play with. Now is a good time to bring up the fact that any function that is a composition of monotone Boolean functions is itself monotone. In fancier words, the ‘class of all monotone Boolean functions is closed’, and the set of functions $\{0, 1, \lor, \land\}$ is a complete basis for this class (proof left as an exercise for the Boolean-algebra-enthusiast reader).

For $n=2$, we still have our constant and identity functions. But now we can also use the other functions in our basis. The monotone Boolean functions of two variables are: $f(x,y) = 0$, $f(x,y) = x$, $f(x,y) = y$, $f(x,y) = x \lor y$, $f(x,y) = x \land y$, and $f(x,y) = 1$. So the third Dedekind number is $6$!

Let’s revisit the Hasse diagram representation with these functions, keeping in mind that we now have our cube-based definition of the Dedekind numbers.

In all of these diagrams, there is never an orange node on a level above a blue one, so we know these are all monotonic. If we look at the Hasse diagram for a function that includes negation, we see that there are false nodes above true ones, so these cannot be monotonic.

If we think about these as 2-dimensional cubes (AKA “squares'”) balancing on one corner, consider the question: how many different ways are there to colour the four corners with two colours? Well, it’s $2^4 = 16$. But only six of these possible ways correspond to monotonic Boolean functions.

Thinking about the problem in this way, it’s easy to see how the Dedekind numbers can become gigantic very quickly. How many different ways are there to colour the corners of an $n$-dimensional cube balancing on one vertex with two colours, such that there’s never an orange corner above a blue one? When $n=3$, the cube has eight corners, so there’s $2^8 = 256$ different ways to colour the vertices, but how many of these correspond to monotonic Boolean functions?

I’ve lost count

It turns out, for $n=3$ the answer is $20$. And for $n=4$, out of a possible 65,536 Boolean functions, only 168 are monotonic. In 1897, when Dedekind first defined the sequence, this was as far as he got. It took over forty years, and the invention of computers, for the next numbers in the sequence to be determined. The last Dedekind number to be found, $n=8$, was discovered in 1991. Finding the ninth Dedekind number was an open challenge for 32 years.

Until earlier this year! But how did they do it?

Christian Jäkel, at TU Dresden, developed a computer algorithm that used matrix multiplication and symmetries in a free distributive lattice (which appears in our list of equivalent definitions earlier). He developed a technique to ‘shift’ or ‘jump’ up to four spaces forward, and calculate the proceeding numbers in the sequence. With this algorithm, from a free distributive lattice with $168$ ($n=4$) elements, he could calculate the eighth Dedekind number in just three seconds. So, all he needed to do was run the same code on the $n=5$ lattice.

The $n=5$ lattice, however, has $7581$ elements. He rented eight graphics cards and ran the algorithm for 28 days, before the 42-digit number finally appeared on 3 April. Thank goodness he didn’t miss a minus sign.

Meanwhile, Lennart Van Hirtum, with the team at KU Leuven and Paderborn University, pursued an entirely different approach. Their approach started back in 2014, when Patrick De Causmaecker and Stefan De Wannemacker found a new formula for counting anti-chains. Seven years later, as a master’s student in Leuven, Lennart found a way to simplify the formula, priming it for numerical computation. With specifically-designed hardware and specialised parallel arithmetic units, they ran the calculation on the Paderborn supercomputer for three months, before the answer for the ninth Dedekind number was revealed to them.

Lennart’s code actually finished running on 8 March, almost a month before Christian’s preprint appeared on arXiv. They were, in fact, running the code for a second time to validate their answer when Christian’s paper came out. Since their number was the same, Lennart and the team hurried to share their own result a few days later. They published their paper on arXiv on 6 April.

To give you a sense of how big 28638657766829841 1128469151667598498812366 ($\approx 2.86 \times 10^{42}$) actually is, there are $7.5 \times 10^{18}$ grains of sand on Earth. There are an estimated $2 \times 10^{23}$ stars in the universe. These values are around $10^{20}$ times smaller than the ninth Dedekind number.