14
$\begingroup$

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.$

$\endgroup$
6
  • $\begingroup$ Do you assume a canonical way of choosing $S_m(2n)$ among possible largest independent sets? Is it lexicographically minimal? $\endgroup$ Sep 12, 2017 at 17:29
  • $\begingroup$ 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? $\endgroup$ Sep 12, 2017 at 17:32
  • $\begingroup$ @VladimirDotsenko Yes, I was overcomplicating matters. $\endgroup$
    – Igor Rivin
    Sep 12, 2017 at 17:36
  • $\begingroup$ @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). $\endgroup$
    – Igor Rivin
    Sep 12, 2017 at 17:37
  • $\begingroup$ @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/…) $\endgroup$ Sep 12, 2017 at 19:46

1 Answer 1

13
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ That's a nice argument! $\endgroup$
    – Igor Rivin
    Sep 12, 2017 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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