# Large gaps in Singer's difference sets

This question is related to the question I asked earlier.

For a natural number $n$, a set $D$ of integer numbers is called a $n$-cyclic difference set if each integer number $x\notin n\mathbb Z$ can be uniquely represented as the difference $x\equiv a-b \mod n$
for a unique pair $(a,b)\in D\times D$. For example, $\{0,1,3,6\}$ is a $13$-cyclic difference set.

For every power $q=p^k$ of a prime number $p$, Singer (1938) constructed a $(1+q+q^2)$-cyclic difference set $D$ of order $|D|=q+1$. A (still unproved) Prime Power Conjecture says that a number $n$ admitting an $n$-cyclic difference set is of the form $n=1+q+q^2$ for some power $q$ of a prime number. The Singer's cyclic difference sets play an important role in Additive Combinatorics.

We are interested in evaluating the largest gap in an $n$-cyclic difference set. A pair $(a,b)$ of numbers is called a gap in a set $A\subset \mathbb Z$ if the intersection $[a,b]\cap A$ coinsides with the doubleton $\{a,b\}$. The number $|a-b|$ is called the length of the gap. For a subset $A\subset\mathbb Z$ let $gap(A)$ be the largest lenght of a gap in $A$. For example, $g(\{0,1,3,6\})=|6-3|=3$.

Problem 1. What is the largest possible gap in an $n$-cyclic difference set $D$?

A more precise question:

Problem 2. Is it true that for any positive constant $C$ there exists an $n$-cyclic difference set $D$ with $gap(D)>C\cdot \sqrt{n}$?

Remark 1. In fact, Problem 2 was implicitely asked by Leech in 1956 and discussed by Golay in 1972. So, maybe this problem has been already solved, in which case I would greatly appreciate a corresponding reference.

Remark 2. Answering my preceding question, @Lucia proved that for every $\varepsilon>0$ there exists a number $n_\varepsilon$ such that $gap(D)<\varepsilon \cdot n$ for any $n$-cyclic difference set $D$ with $n \ge n_\varepsilon$. So, gaps in cyclic difference sets cannot be very large.

I can prove that for any prime power $q=p^k$ each $(1+q+q^2)$-cyclic difference set $D$ has $gap(D)\ge q+\sqrt{q}-1$, but it is very far from $gap(D)>Cq$.

## 1 Answer

Firstly, in my previous answer I showed that the gaps are bounded by $O(n^{\frac 34} \log n)$ (and one can remove the $\log$ with a little more care). I expect that this is the best known bound on the gap.

Problem 2 is definitely an open problem. Suppose one can show that there is a gap of size $C\sqrt{n}$. By translating the perfect difference set, one can assume that the gap is at the end -- that is, make the residue classes $\mod n$ lie in $[0, n -C \sqrt{n}]$. But if we simply think of these now as integers, then it would follow that there is a Sidon set (or $B_2$-set) in $[1,N]$ (with $N=n-C\sqrt{n}$) having more than $\sqrt{N} + C/2$ elements. This an open problem going back to Erdos, who offered \\$ 500 for a solution -- there is a survey/annotated bibiliography of O'Bryant from 2004 that you may find useful; see section 4.1 there.