By a classical result of Singer (1938), for a prime number $p$ the cyclic group $C_n$ of order $n=1+p+p^2$ contains a subset $D$ of cardinality $|D|=1+p$ such that $DD^{-1}=C_n$. Such set $D$ is called a difference set. The cardinality restrictions imply that each non-unit element $x\in C_n$ can be uniquely written as the difference $x=a-b$ for $a,b\in D$.

Identify $C_n$ with a subgroup of the unit circle $\mathbb T=\{z\in C_n:|z|=1\}$ on the complex plane. Let $D$ be a subset of $C_n\subset \mathbb T$. A 2-element set $\{a,b\}\subset D$ is called a gap in $D$ if there exists an arc $A\subset \mathbb T$ with end-points $a,b$ such that $A\cap D=\{a,b\}$. The real number $|a-b|$ is called the diameter of the gap $\{a,b\}$.

Problem 1. What is the largest possible diameter of a gap in a difference set in a cyclic group $C_n$?

More precisely:

Problem 2. Is there $\epsilon>0$ such that for every prime number $p$ the cyclic group $C_n\subset\mathbb T$ of order $n=1+p+p^2$ contains a difference set $D$ with a gap of diameter $>\varepsilon$?


No you cannot have very big gaps in a perfect difference sets -- the elements in a perfect difference set will be pretty uniform. Suppose $A$ is a perfect difference set $\mod n$ with $n=1+p+p^2$ as above. Put $$ {\hat A}(k) = \sum_{a \in A} e(ak/n). $$ Since $A$ is a perfect difference set, for any $k\neq 0$ one has $$ |{\hat A}(k)|^2 = |A| + \sum_{a \neq b \in A} e(k(a-b)/n) = |A|-1. $$ In other words, all the non-trivial Fourier coefficients of $A$ are small.

Now suppose $I$ is an arc $\mod n$, and let us count the number of elements of $A$ on $I$. By orthogonality we can write this as $$ \frac{1}{n} \sum_{k \mod n} {\hat A}(k) {\hat I}(-k), $$ and using our knowledge of the Fourier coefficients above, this is $$ \frac{|I||A|}{n} +O\Big( \frac{\sqrt{|A|}}{n} \sum_{k\neq 0} |{\hat I}(-k)|\Big). $$ It is a simple calculation to bound the $L^1$ norm of the Fourier coefficients of an interval -- it is $\ll n \log n$. So from the above analysis we get $$ \frac{|I||A|}{n} + O(\sqrt{|A|} \log n). $$

Since $|A| = p+1$ is about $\sqrt{n}$, this means that any arc with size a bit more than $n^{\frac 34}$ will contain many points of $A$. This settles Problem 2; I don't really have a guess as to the right size of the maximum gap.

  • 1
    $\begingroup$ Thank you very much for the answer. In fact, the above question was motivated by another question: mathoverflow.net/questions/261920/… $\endgroup$ – Taras Banakh Feb 13 '17 at 0:18
  • $\begingroup$ I think the argument I gave here basically shows that the answer to your Problem 2 in that question is negative. If I have some time, I'll post an answer there (or maybe this is enough for you). $\endgroup$ – Lucia Feb 13 '17 at 2:11

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.