# divisibility independence

The following is a standard combinatorics question:

Any set of $n+1$ numbers from $1, \dotsc, 2n$ contains a pair of numbers $a, b$ where $a \left| b \right.$

The argument is by pigeonhole principle: consider $A_i = \{2^k (2i-1), k\in \mathbb{N}\}.$ The sets $A_i$ cover $1, \dotsc, 2n,$ and there are $n$ of them.

The question is this: to find the maximal division-free set, the obvious way is to do the following (in Mathematica):

divGraph[n_] := With[{pairs = Subsets[Range[n], {2}]},
With[{divis = Select[pairs, Mod[#[[2]], #[[1]]] == 0 &]},
Graph[Apply[Rule, #] & /@ divis]]]

FindIndependentSet[divGraph[n]]

Now, when one runs this for smallish numbers one sees that the maximal set $S_m(2n)$ always has cardinality $n,$ but also, the minimum of $S_m(2n)$ is equal to

• 1 once
• 2 thrice
• 4 nine times
• 8 $27$ times
• 16 $81$ times
• 32 $243$ times

And so on. The question is: what is going on? Is this the true size of the minimal element of $S_m?$ As Vladimir Dotsenko points out, the obvious example has the minimum equal to $n+1.$

• Do you assume a canonical way of choosing $S_m(2n)$ among possible largest independent sets? Is it lexicographically minimal? Sep 12, 2017 at 17:29
• For the first question, maybe I misunderstand something, but would not the $n$ numbers $n+1$,...,$2n$ be an example showing that the bound is sharp? Sep 12, 2017 at 17:32
• @VladimirDotsenko Yes, I was overcomplicating matters. Sep 12, 2017 at 17:36
• @MikhailTikhomirov I don't know, which is why I am asking whether anything interesting is going on (if this were canonical, it would obviously be interesting). Sep 12, 2017 at 17:37
• @IgorRivin Hi! While your question already has a great answer, and the following old question may not have direct relevance, maybe it is of interest! (mathoverflow.net/questions/84207/…) Sep 12, 2017 at 19:46

First, I ran some bruteforce myself (I don't have access to Mathematica at the moment), and I'm fairly sure the mysterious numbers obtained in OP ($1, 2, 2, 2, 4\ldots$) are the minimal possible numbers that are present in any $S_m(2n)$. I'm going to explain the pattern in this assumption.

Long story short, the minimal possible number in $S_m(n)$ is $2^{\left\lfloor \frac{\log n}{\log 3} \right\rfloor}$.

As follows from the OP's explanation, for any odd number $x \leq n$ there is exactly one representative of form $x 2^k$ in any $S_m(n)$. Let us call the exponent $k = d(x)$ the degree of $x$ in a particular $S_m(n)$. Obviously, for non-equal $x \vert y$ we must $d(x) > d(y)$.

One can see that the "critical" values where the OP's minimal numbers change are exactly $\frac{3^k + 1}{2}$, that is, the minimum changes whenever a new power of 3 arrives in the set. One can indeed see that in any $S_m(n)$ we have $d(1) \geq \left\lfloor \frac{\log n}{\log 3} \right\rfloor = k_0$ by simply applying the inequality above for a divisor chain $1 \vert 3 \vert \ldots \vert 3^{k_0}$. The numbers $2^{k_0}$ follow the OP's pattern exactly.

But why any number that is not a binary power cannot be less than $2^{k_0}$ in an $S_m(n)$? Let $1 < x \leq n$ be an odd number. Then for any $S_m(n)$ the numbers $\{2^{d(x)}, 3\cdot 2^{d(3x)}, \ldots\}$ must be an $S_m(\left\lfloor \frac{n}{x} \right\rfloor)$. As we have shown above, that implies $d(x) \geq \left\lfloor \frac{\log \lfloor n/x \rfloor}{\log 3} \right \rfloor$. It suffices to show $2^{\left\lfloor \frac{\log n}{\log 3} \right\rfloor} < x \cdot 2^{\left\lfloor \frac{\log \lfloor n/x \rfloor}{\log 3} \right\rfloor}$. But $2^{\left\lfloor \frac{\log n}{\log 3} \right\rfloor - \left\lfloor \frac{\log \lfloor n/x \rfloor}{\log 3} \right\rfloor} \leq 2^{\frac{\log x}{\log 3} + 1} = 2 \cdot x^{\frac{\log 2}{\log 3}} < x$ for all $x > 5$ (for $x = 3, 5$ we may still have the claim by handling the rounding error more carefully).

To finish the proof, notice that the set $\{x \cdot 2^{\left\lfloor \frac{\log \lfloor n/x \rfloor}{\log 3} \right\rfloor}\}$ with $x$ ranging over odd numbers at most $n$ is an $S_m(n)$. Note that this set is minimal with respect to any measure, e.g. no proper divisor of any of its elements can be in an $S_m(n)$, hence it's also lexicographically minimal when sorted.

• That's a nice argument! Sep 12, 2017 at 19:36