I recently uploaded “a large gap in a dilate of a set,” to the arXiv. We prove the following.
Theorem 1: Let with at least two elements. Suppose . Then there is a and such that
As the note is only 3 pages, we do not remark on the proof (which uses the polynomial method) but elaborate on some related topics. Note by the pigeon-hole principle, Theorem 1 is true for every if we only insist . Thus we have effectively doubled the bound coming from the pigeon hole principle. Note without dilation, Theorem 1 is false, as one can take equally spaced elements.
One can ask what happens for Theorem 1 if one does not allow translation by . It turns out that one cannot hope to go beyond , as it was shown in this paper of Chen, Shparlinski and Winterhof, using the example
It is an interesting question to decide to what extent Theorem 1 is true with translation by . We remark this is in a similar spirit to the lonely runner conjecture.
It would be nice if Theorem 1 were true for for all , even in the special case when . Certainly this is true for a random set, without the need for dilation.
In particular, this would give us hope in answering an old question of Erdös, which we recall. A Sidon set in a abelian group is a set such that with implies . Let be the largest Sidon set contained in . Erdös asked if
There are constructions of Sidon sets of size (for some ) coming from for well-chosen . The hope would be to dilate the set in so there is a large gap of size , thus finding a Sidon set of inside of in place of . It is actually not known if we can take to be a prime in the modular construction, which may be found in this nice survey of O’ Bryant. This is certainly a question of interest.
On the other hand, one can hope to improve Theorem 1 for some of these constructions. It turns out one can easily check that Ruzsa’s construction which is the set does not admit large gaps. Indeed the set has size but any dilate of does not contain a gap significantly longer than . This also shows Theorem 1 is false for general cyclic groups. The point is that in his construction the natural projection to maps surjectively.
This seems to be a bit of a red herring in the application to Sidon sets. On the other hand, for the well-known construction of Bose-Chowla (contained in the aforementioned survey), the analog of Theorem 1 is true and there is no reason to suspect that it cannot be improved. In fact, in this case a proof also proceeds by the polynomial method.