6
$\begingroup$

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$.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.