The following question is inspired by a problem that Erdős used to ask epsilons. It asks to prove that if one chooses a subset of $\lbrace 1,\dots,n\rbrace$ with more than $\lfloor\frac{n+1}{2}\rfloor$ elements, then there are two numbers in this subset with an integer ratio.

My question is about subsets which don't satisfy that conclusion, i.e. no element divides the other. So to phrase it more succinctly, how many antichains are there in the divisibility poset $\mathcal P_n$? The partial order here is $x\le y$ if $x|y$. Let's denote this number by $p_n$.

Of course an exact enumeration is not possible in such cases, so one looks for asymptotics. I haven't been able to do much progress at that, either.

What I have so far is really just the obvious bounds one gets from the solution of the problem mentioned in the beginning of this post. For the lower bound, by looking at numbers $> \frac{n}{2}$ one obtains $p_n\geq 2^{\frac{n}{2}}$.

For the upper bound, by using the fact that we have chains $\lbrace k,2k,4k\dots\rbrace$ for every odd $k$, one obtains $p_n\le 2^{cn}$ where $$c=\sum_{n=1}^{\infty}\frac{\log_2 n}{2^n}\approx 0.73264948$$ Can somebody help me bridge the gap between these two bounds?

4more comments