The 10th Dedekind number

The nth 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⁴¹.

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_i^k be its ith bit:

Then the nth 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³⁰⁸ 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³⁰⁸.

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²⁵² which is approximately 7.237 * 10⁷⁵, 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⁸².

So to recap, we know for certain that M(10) is between 7.237 * 10⁷⁵ and 1.8 * 10³⁰⁸, and our guess based on the heuristic above is that M(10) = 3.253 * 10⁸².

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