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}.

“Let’s take a guess at the upper bound by seeing what the big-O term was for M(9).”

That’s a pretty neat idea! I’d never seen it before.

I know we don’t have an argument for just how valid it may or may not be, but it seems like a pretty sensible approach with just the information we have.

Beware, there are some large numbers out there!

n len est a(n)

0 1 1 2

1 1 1 3

2 1 1 6

3 2 2 20

4 3 3 168

5 4 5 7,581

6 7 7 7,828,354

7 13 12 2,414,682,040,998

8 23 23 56,130,437,228,687,557,907,788

9 42 42 286,386,577,668,298,411,128,469,151,667,598,498,812,366

10 77

I’m using the following equation as an estimate:

Len = actual length

Est = Estimated length

Est[M(10)] = 77

Est[M(n)] = 2 * len[M(n-1)] – len[M(n-4)]