# A large gap in a dilate of a set

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.