Number of maximal antichains in the set $\{1,2,3,4,5,6,...,120\}$ where the order is by divisibility relation.

Question

Find the number of maximal antichains in the set $\{1,2,3,4,5,6,7,...,120\}$ where the order is divisibility relation. For example, $\{6,7,15\}$ is an antichain but not a maximal antichain, and $\{1\}$ is a maximal antichain, and $\{p : p \text{ is a prime less than } 120 \}$ is a maximal antichain.

Here is my work so far: whatever we end up doing with primes, we must add one to our final result because $\{1\}$ is a special antichain. Since there are precisely $30$ primes less than $120$, I was at first thinking about the number of ways of putting $30$ primes into $k$ indistinct boxes, so that for example if $2, 5, 7$ were in the same box, then we would have their product $70$ in the resulting set. We can form maximal antichains this way; however, this is not the only way to form maximal antichains, since $18,20$ could be part of some maximal antichains. I was then thinking about how to distribute the primes $2,3,5,7$ properly because $2^6 < 120 < 2^7, 3^4 < 120 < 3^5, 5^2 < 120 < 5^3, 7^2 < 120 < 7^3,$ and all the rest primes $p$ satisfy $p < 120 < p^2$. There are $17$ primes from $2$ to $59$, including the two ends; there are $26$ primes from $11$ to $113$, including both ends.

This question comes from a chapter dealing with Sperner's theorem. I am not sure if we could relate this question explicitly to the theorem though.

How can I proceed?

Answer 1

The number of maximal antichains in the $\{1,\dots,n\}$ partial order with divisibility as the relation is OEIS A326077. There is no formula listed, but the value at $n=120$ (and therefore the answer to your question is $$73879438410$$ I independently verified this result by translating the equivalent maximal independent set problem on the comparability graph of the poset to SAT, then running a #SAT solver on it (my code can be found here).

Answer 2

It seems to me that it can be seen as an application of the theorem of Dilworth. Applying the Erathostene sieve, we partition the lattice into as many chains as there are prime numbers below 120 (so 30 from what the author of the post says), and it is obviously a smallest chain decomposition. The longest antichain is therefore of size 30, and it is attained by taking the antichain of the prime numbers below 120, as it is indicated. The number of such antichains is the product of the size of the chains of the partition, if I am correct.

Another interesting exercise would be to consider only the divisors of a given number (and not all the numbers below it). For 120, the Hasse diagram of its divisors is an hypercube made of three cubes and we can see the longest antichain is of size 4:

https://en.m.wikipedia.org/wiki/File:Birkhoff120.svg

More generally, it seems to me that finding the size of the longest antichain of the divisors of $p_1^{a_1} \ldots p_n^{a_n}$ can be seen as an application of the Sperner theorem by considering the prime numbers without their order of divisibility (so that now we have a power set, whose longest antichain is of size $\binom{n}{[n/2]})$ and I would say it is of size $\binom{n}{[n/2]}+|\{q:a_q>1\}|$, because any $p_q^{b}$ with some $b>1$ can count as a new element to add to the antichain. For 120, this makes indeed $\binom{3}{[3/2]}+1=4$. But I am not sure of this formula, which sounds weird to me.

If a specialist comes around, I would be grateful if he could confirm or infirm my claims.