A large gap in a dilate of a set

Additive Combinatorics,

I recently uploaded “a large gap in a dilate of a set,” to the arXiv. We prove the following.

{\ } Theorem 1: Let {A \subset \mathbb{F}_p} with at least two elements. Suppose {N \leq 2p/|A| -2}. Then there is a {x \in \mathbb{F}_p} and {d \in \mathbb{F}_p^{\times}} such that

\displaystyle (d\cdot A + x ) \cap \{1 , \ldots , N\} = \emptyset.  \ \ \ \spadesuit

{\ }

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 {d} if we only insist {N \geq p/|A| - 1}. Thus we have effectively doubled the bound coming from the pigeon hole principle. Note without dilation, Theorem 1 is false, as one can take {|A|} equally spaced elements.

One can ask what happens for Theorem 1 if one does not allow translation by {x}. It turns out that one cannot hope to go beyond {N \geq 2p/|A|}, as it was shown in this paper of Chen, Shparlinski and Winterhof, using the example

\displaystyle A = \{1 , \ldots , p/N\} \cup -\{1 , \ldots , p/N\} .

It is an interesting question to decide to what extent Theorem 1 is true with translation by {x}. We remark this is in a similar spirit to the lonely runner conjecture.

It would be nice if Theorem 1 were true for {N \geq C p/|A|} for all {C}, even in the special case when {|A| \sim \sqrt{p}}. 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 {a+b = c+d} with {a,b,c,d \in A} implies {\{a,b\} = \{c,d\}}. Let {r_2(N)} be the largest Sidon set contained in {\{1 , \ldots , N\}}. Erdös asked if

\displaystyle r_2(N) = N^{1/2} + O(1).

There are constructions of Sidon sets of size {N^{1/2}} (for some {N}) coming from { \mathbb{Z} /N \mathbb{Z}} for well-chosen {N}. The hope would be to dilate the set in {\mathbb{Z}/N \mathbb{Z}} so there is a large gap of size {g}, thus finding a Sidon set of inside of {\{1 , \ldots , N-g\}} in place of {\{1 , \ldots , N\}}. It is actually not known if we can take {N } 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 {A \subset \mathbb{Z}/ (p(p-1)) \mathbb{Z}} does not admit large gaps. Indeed the set has size {\sim p} but any dilate of {A} does not contain a gap significantly longer than {2p}. This also shows Theorem 1 is false for general cyclic groups. The point is that in his construction the natural projection to {\mathbb{Z}/(p-1)\mathbb{Z}} maps {A} 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.

Leave a Reply