MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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$. – Timothy Foo Dec 24 '11 at 6:09
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. – Mark Sapir Dec 24 '11 at 23:58
@Mark: No need to run computer experiments, Sloane's A051026 ( has the first few terms. – Guntram Dec 25 '11 at 0:59
@Guntram: Thanks! I did feel that it is too natural a question to appear now for the first time. – Mark Sapir Dec 25 '11 at 1:32
@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. – Gjergji Zaimi Dec 25 '11 at 2:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.