12
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Let $A_n$ be the roughly $n/6$ integers in $(n/3,n/2)$. Let $B_n$ be the integers in $(n/2 + 1,n]$ that are of the form $2m$, $m \in A_n$. Let $C_n$ be the integers in $(n/2+1,n]$. By considering $C_n \setminus B_n$ we get $2^{n/2-n/6}$. By considering $A_n$ and $B_n$ we get $3^{n/6}$. So a lower bound is $2^{(0.5+r/6)n}$ where $2^r=1.5$. $\endgroup$ – Timothy Foo Dec 24 '11 at 6:09
  • 1
    $\begingroup$ Perhaps you can run a computer experiment for small $n$, say, $n\le 20$. Also I guess one needs only to know the maximal antichains, and the semilattice (under intersection) they generate. I wonder, what this semilattice is for small $n$. It must be something quite "regular". The whole problem, in my opinion, should have a definite answer, that is the limit of $(\log p_n)/n$ should exist and be something nice. $\endgroup$ – Mark Sapir Dec 24 '11 at 23:58
  • 3
    $\begingroup$ @Mark: No need to run computer experiments, Sloane's A051026 (oeis.org/A051026) has the first few terms. $\endgroup$ – Guntram Dec 25 '11 at 0:59
  • $\begingroup$ @Guntram: Thanks! I did feel that it is too natural a question to appear now for the first time. $\endgroup$ – Mark Sapir Dec 25 '11 at 1:32
  • $\begingroup$ @Guntram: Thanks! Now I feel silly, because I couldn't find this sequence in OEIS as I wasn't counting the empty set. "Primitive sequnces" does give a lot of hits on google, including some articles of Erdos. It will take a while to go through those and check what the answer to this question is. $\endgroup$ – Gjergji Zaimi Dec 25 '11 at 2:42
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I've been thinking about how to give estimates on this sum for some time, but couldn't break the existing (kinda trivial) bounds yet. $\endgroup$ – Mikhail Tikhomirov Sep 14 '17 at 15:22
  • $\begingroup$ @MikhailTikhomirov It is an interesting question. Thanks for your insight. $\endgroup$ – Release the Christians. Sep 14 '17 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.