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 numbers from , there will be two distinct numbers and such that divides .
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 can be written as , with and by considering the largest power of in the factorisation of . Now write each of the numbers you have chosen in this form. Since there are precisely odd integers in the set and hence precisely possibilities for the factor, by the pigeonhole principle we must have two integers with and , for some and . Thus, divides .
Looking at the proof carefully, what we have really done is partition the set into parts , with , such that in each every number divides all the other numbers which are bigger. Then since we have chosen elements from , there must be an index for which contains two of these 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 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 -element subset does not have any two distinct elements in it with one dividing the other. And since we have shown that any -element subset will violate this property, 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 is the unique -element subset of 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 , which is another such example. And then is another one. We can keep doing this for a certain number of steps, where is a constant (figure out what 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 . 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 such that there are at least -element subsets of 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 ? 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 ?
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 , 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.