The *n*th Dedekind number *M*(*n*) is the number of monotone Boolean functions of *n* variables. The 9th Dedekind number was recently computed to be

*M*(9) = 286386577668298411128469151667598498812366.

The previous post defines monotone Boolean functions and explicitly enumerates the functions for one, two, or three variables. As that post demonstrates, *M*(1) = 3, *M*(2) = 6, and *M*(3) = 20. But as *n* increases, *M*(*n*) increases rapidly, with *M*(9) being on the order of 10^{41}.

Although computing the Dedekind numbers exactly is difficult—*M*(8) was computed in 1991 and *M*(9) now in 2023—there is an explicit formula for these numbers, and much is known about their asymptotic growth. This post speculates about what *M*(10) might be.

Write the number *k* in binary and let *b*_{ik} be its *i*th bit:

Then the *n*th Dedekind number is given by

and so

In principle, all you have to do to compute *M*(10) is evaluate the sum above. However, since this sum has more than 10^{308} terms, it would take a while.

What can we say about *M*(10) without computing it? The number of monotone Boolean functions of *n* variables is less than the total number of Boolean functions of *n* variables, which equals

That tells us *M*(10) < 1.8 × 10^{308}.

There are more useful bounds. It has been proven that

This gives us a definite lower bound but not a definite upper bound. We know *M*(10) ≥ 2^{252} which is approximately 7.237 × 10^{75}, but we don’t know what the big-O term is. All we know is that for sufficiently large *n*, this term is smaller than some multiple of log(*n*)/*n*. How large does *n* need to be and what is this constant? I don’t know. Maybe researchers in this area have some partial results.

Let’s take a **guess** at the upper bound by seeing what the big-O term was for *M*(9). Find *k* such that

We get

and we can use this to guess that

which would imply *M*(10) = 3.253 × 10^{82}.

So to recap, we know for certain that *M*(10) is between 7.237 × 10^{75} and 1.8 × 10^{308}, and our guess based on the heuristic above is that *M*(10) = 3.253 × 10^{82}.

The post The 10th Dedekind number first appeared on John D. Cook.