This question is related to the [question](https://mathoverflow.net/questions/262063/large-gaps-in-singer-planar-difference-sets) 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](http://www.ams.org/journals/tran/1938-043-03/S0002-9947-1938-1501951-4/S0002-9947-1938-1501951-4.pdf) (1938) constructed a $(1+q+q^2)$-cyclic difference set $D$ of order $|D|=q+1$. A (still unproved) [Prime Power Conjecture](http://www.combinatorics.org/ojs/index.php/eljc/article/view/v1i1r6) 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](http://onlinelibrary.wiley.com/doi/10.1112/jlms/s1-31.2.160/full) in 1956 and discussed by [Golay](http://onlinelibrary.wiley.com/doi/10.1112/jlms/s2-4.4.729/full) 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](https://mathoverflow.net/questions/262063/large-gaps-in-singer-planar-difference-sets), @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$.



Large gaps in Singer's difference sets
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](https://arxiv.org/pdf/math/0407117.pdf) from 2004 that you may find useful; see section 4.1 there. 


