On a famous pigeonhole problem

After a short break from blogging, which involved moving from Ghent to Berlin, dealing with German bureaucracy, and learning how to make simple websites (the easiest bit), I am now back. I am working as a postdoc at the Free University of Berlin right now and a part of my job is to teach a course (mainly taking care of the exercise classes) called Extremal Combinatorics with Tibor Szabó . While preparing a review sheet of exercises for this course, we discussed about which pigeonhole problem to include. In the actual sheet we ended up giving a simple one, but we did think about including the following famous problem:

Prove that if you pick any $n + 1$ numbers from $1, 2, \dots, 2n$ , there will be two distinct numbers $a$ and $b$ such that $a$ divides $b$ .

This used to be one of the favourite problems of Paul Erdős for young (mathematically inclined) kids. Quoting Proofs from THE BOOK, “As Erdős told us, he put this question to young Lajos Pośa during dinner, and when the meal was over, Lajos had the answer. It has remained Erdős’ famous initiation questions to mathematics”. Perhaps you should try it over your next dinner, before reading further.

So here is the standard pigeonhole argument for this. Every positive integer $a$ can be written as $a = 2^k(2m - 1)$ , with $k \geq 0$ and $m \geq 1$ by considering the largest power of $2$ in the factorisation of $a$ . Now write each of the $n + 1$ numbers you have chosen in this form. Since there are precisely $n$ odd integers in the set $1, \dots, 2n$ and hence precisely $n$ possibilities for the $2m - 1$ factor, by the pigeonhole principle we must have two integers $a, b$ with $a = 2^{k_1}(2m - 1)$ and $b = 2^{k_2}(2m - 1)$ , for some $k_1 < k_2$ and $m \in \{1, \dots, n\}$ . Thus, $a$ divides $b$ .

Looking at the proof carefully, what we have really done is partition the set $[2n] = \{1, \dots, 2n\}$ into $n$ parts $S_1, \dots, S_n$ , with $S_i = \{2^k(2i - 1) : k \geq 0\} \cap [2n]$ , such that in each $S_i$ every number divides all the other numbers which are bigger. Then since we have chosen $n + 1$ elements from $[2n] = S_1 \sqcup \dots \sqcup S_n$ , there must be an index $i$ for which $S_i$ contains two of these $n + 1$ elements.

Now, as a mathematician, there are two natural questions that one can ask:

(Q1) What is the largest possible size of a subset of $[2n]$ which does not contain two elements with one dividing the other?

(Q2) Can we classify, or say something interesting about, all such largest possible subsets?

(Q1) is straightforward to answer, since we quickly see that the $n$ -element subset $\{n + 1, n + 2, \dots, 2n\}$ does not have any two distinct elements in it with one dividing the other. And since we have shown that any $(n+1)$ -element subset will violate this property, $n$ is the largest possible size.

(Q2) is what we will be really interested in.

This is such a natural question for a combinatorialist, but somehow I have been unable to find any reference for it (which Tibor found quite surprising as well). Now the first natural guess for an answer is that the example $\{n + 1, n + 2, \dots, 2n\}$ is the unique $n$ -element subset of $[2n]$ with this “non-divisibility” property. It is natural because this is what happens in typical extremal combinatorics problems. But if you think about it for a while, you’ll be able to come up with the set $\{n, n + 1, n + 2, \dots, 2n - 1\}$ , which is another such example. And then $\{n - 1, n, n + 1, \dots, 2n - 3, 2n - 1\}$ is another one. We can keep doing this for a certain $k = cn$ number of steps, where $c$ is a constant (figure out what $c$ is!). This shows that there are at least a linear number of extremal examples in this problem. Moreover, you can prove that any such extremal set must contain all the odd numbers from $\{n + 1, n + 2, \dots, 2n\}$ . But are there any more such sets?

After some more thought, I was able to show that there are in fact exponentially many such extremal sets! More precisely, there exists a constant $c > 1$ such that there are at least $c^n$ $n$ -element subsets of $[2n]$ in which there are no two elements with one dividing the other. I will leave the proof of this as an exercise, since it did not take me too long to come up with it and in fact, one of the students in the exercise classes that I teach was able to come up with the same proof as mine pretty quickly.

Now the questions that I want to ask are the following:

What is the best possible value of the base $c$ ? In other words, asymptotically how many such extremal subsets can we find? Is there a “substantially” better upper bound on the number of such sets than $\binom{3n/2}{n/2} \sim 2^{1.38 n}$ ?

If you have an answer, or some ideas, then please let me know in the comments.

Edit 06/11/2017: I computed the number of such extremal subsets for small values of $n$ , after which a quick search on The On-Line Encyclopedia of Integer Sequences revealed that people have computed and studied this number. In particular, Robert Israel mentions the same lower bound that I obtained.

Edit 22/05/2018: My question has been completely answered independently by Liu, Pach and Palincza in “The Number of Maximum Primitive Sets of Integers“, Edit 29/11/2018: and Nathan Mcnew in “Counting primitive subsets and other statistics of the divisor graph of {1, …, n}”

About Anurag Bishnoi

A mathematician working at TU Delft. I am broadly interested in combinatorics and finite geometry.

View all posts by Anurag Bishnoi →

5 Responses to On a famous pigeonhole problem

Fedor Petrov says:

November 2, 2017 at 4:40 pm

For each odd number $a\in \{1,3,\dots,2n-1\}$ there should exist unique non-negative integer $k(a)$ such that our set contains $2^{k(a)} \cdot a$ (in particular, this implies that $k(a)\leqslant \log_2 (2n/a)$ . The condition is that $k(a)>k(b)$ whenever $a$ divides $b$ . So, we have to count the number of integer points in a certain convex polytope.

- Anurag Bishnoi says:
  
  November 2, 2017 at 5:48 pm
  
  Do you know any nice general results for convex polytopes that can help us in this particular problem? My knowledge of polytope theory, and especially counting lattice points, is almost non-existent.
  
- Anurag Bishnoi says:
  
  November 3, 2017 at 6:30 pm
  
  This formulation does help in computing the exact number of such sets for small values of $n$ . Here are the first $30$ elements of the sequence that I have just computed using SageMath.
  $2, 2, 3, 5, 4, 6, 12, 10, 14, 26, 26, 34, 68, 48, 72, 120, 120, 168, 336, 264, 396,$
  $792, 624, 816, 1632, 1632, 2208, 3616, 3616, 5056$ .
  
Anurag Bishnoi says:

November 3, 2017 at 6:51 pm

Let me write down my construction for an exponential lower bound that I left as an exercise. If you still want to try it yourself then ignore this comment.

Let $S = \{n + 1, \dots, 2n\}$ . Then for any $T \subseteq \{\lfloor 2n/3 \rfloor + 1, \dots, n\}$ the set $S' = (S \setminus 2T) \cup T$ is division free and has cardinality $n$ , where $2T = \{2x : x \in T\}$ . This gives us (at least) $2^{n/3}$ such sets ( $2^{1 + \lfloor (n-1)/3 \rfloor}$ if we want to be more precise).

Can we construct more division free sets? Numerical data suggests we can but I don’t see any other explicit construction which gives a better bound than $2^{n/3}$ .

Aaditya Salgarkar says:

November 4, 2017 at 1:04 pm

As a preliminary attempt, the uppar bound can be improved to $2^ {nF}$ where $F~0.78$ as shown below.
https://www.dropbox.com/s/fuv6yg2rfzmvln0/divFreeSets.pdf?dl=0