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

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 bik be its ith bit:

b_i^k=leftlfloorfrac{k}{2^i}rightrfloor - 2leftlfloorfrac{k}{2^{i+1}}rightrfloor

Then the nth Dedekind number is given by

M(n)=sum_{k=1}^{2^{2^n}} prod_{j=1}^{2^n-1} prod_{i=0}^{j-1} left(1-b_i^k b_j^kprod_{m=0}^{log_2 i} (1-b_m^i+b_m^i b_m^j)right)

and so

M(10)=sum_{k=1}^{2^{1024}} prod_{j=1}^{1023} prod_{i=0}^{j-1} left(1-b_i^k b_j^kprod_{m=0}^{log_2 i} (1-b_m^i+b_m^i b_m^j)right)

In principle, all you have to do to compute M(10) is evaluate the sum above. However, since this sum has more than 10308 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

2^{2^n}

That tells us M(10) < 1.8 × 10308.

There are more useful bounds. It has been proven that

{nchoose lfloor n/2rfloor}le log_2 M(n)le {nchoose lfloor n/2rfloor}left(1+Oleft(frac{log n}{n}right)right)

This gives us a definite lower bound but not a definite upper bound. We know M(10) ≥ 2252 which is approximately 7.237 × 1075, 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

log_2 M(9) = binom{9}{4}left(1 + k frac{log 9}{9}right)

We get

k = left(frac{log_2M(9)}{126} - 1 right)frac{9}{log 9} approx 0.3809

and we can use this to guess that

log_2 M(10) stackrel{?}{=} binom{10}{5}left(1 + 0.3809 frac{log 10}{10}right) approx 274.1

which would imply M(10) = 3.253 × 1082.

So to recap, we know for certain that M(10) is between 7.237 × 1075 and 1.8 × 10308, and our guess based on the heuristic above is that M(10) = 3.253 × 1082.

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

Previous Post
Next Post