Longest antichain of divisors

Question

I Need to find a way to calculate the length of the longest antichain of divisors of a number N (example 720 - 6, or 1450 - 4), with divisibility as operation. Is there a universally applicable way to approach this problem for a given N?

Answer 1

A natural number is said to be of degree m if it's the product of m primes. If N is of degree 2m, then the largest antichain of divisors of N is the set of all divisors of degree m. If N is of degree 2m + 1, there are two largest antichains of divisors of N: the set of all divisors of degree m, and the set of all divisors of degree m + 1. This generalizes Sperner's theorem, which is just the case where N is squarefree.

Example: N = 720 = 2*2*2*2*3*3*5 is of degree 7. The six divisors of degree 3 are 8, 12, 18, 20, 30, 45; the six divisors of degree 4 are 16, 24, 36, 40, 60, 90.

The reference for this result is: N. G. de Bruijn, Ca. van Ebbenhorst Tengbergen, and D. Kruyswijk, On the set of divisors of a number, Nieuw Arch. Wiskunde (2) 23 (1951), 191–193.

http://ohkawa.cc.it-hiroshima.ac.jp/AoPS.pdf/On%20the%20Set%20of%20Divisors%20of%20a%20Number%20-%20Debruijn.pdf

Answer 2

If $N=\prod_p p^{e_p}$ is the prime factorization of $N$, then the longest such antichain has length $1+\sum_p e_p$ (if we count $N$ and $1$ as part of the chain, otherwise subtract $2$) and can be realized by dividing by a prime in each step. Thus with $N=720=2^4\cdot 3^2\cdot 5^1$ we find $720\stackrel{\color{red}2}, 360\stackrel{\color{red}2}, 180\stackrel{\color{red}2}, 90\stackrel{\color{red}2}, 45\stackrel{\color{red}3}, 15\stackrel{\color{red}3}, 5\stackrel{\color{red}5}, 1$ and with $N=1450=2^15^229^1$ we find $1450\stackrel{\color{red}2},725\stackrel{\color{red}5},145\stackrel{\color{red}5},29\stackrel{\color{red}{29}}, 1$ (in red is the prime I divide by in each step; I start with the smallest, but the order does not matter).