Asymptotic growth of antichains in divisibility posets

Question

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?

Answer 1

Here is an expression for $c$ based on Mikhail Tikhomirov's nice answer to the question (divisibility independence). Let us also use his notation from that answer. With $1\leq x \leq n$, $x\equiv 1 \bmod 2$, define $d(x)$ in the same way except that the antichain does not need to be an $S_m(n)$. We think of $d(x)$ as being in $E(x)=\{\alpha,0,1,\dots,\lfloor\log(n/x)/\log 2 \rfloor\}$ where $\alpha$ is a symbol such that if $d(x)\not=\alpha$ then $d(x)$ has the same meaning in that answer, and if $d(x)=\alpha$, it means that no number of the form $x2^e$ is in the antichain. (Also, since the antichain need not be maximal, we clearly may have $d(x)<\left\lfloor\frac{\log\lfloor n/x \rfloor}{\log 3}\right\rfloor$ if $d(x)\not=\alpha$ in this case.) Let $P(x,y)$ be the statement $x|y \Rightarrow (d(x)\not=\alpha \Rightarrow (d(y)=\alpha \mbox{ or }d(y)<d(x)))$. Then $$ 2^{cn}=\sum_{\substack{(d(1),d(3),\dots,d(2\lfloor(n+1)/2\rfloor-1))\in \prod_{x\in \{1,3,\dots,2\lfloor(n+1)/2\rfloor-1\}}E(x)\\P(x,y) \forall (x,y)\in\{1,3,\dots,2\lfloor(n+1)/2\rfloor-1\}^2}}1 $$ Well, the main thing is to study that condition on the sum.