Quadratic residues and difference sets

Vsevolod F. Lev, Jack Sonn

Published 2015-02-24Version 1

It has been conjectured by Sarkozy that with finitely many exceptions, the set of quadratic residues modulo a prime $p$ cannot be represented as a sumset $\{a+b\colon a\in A, b\in B\}$ with non-singleton sets $A,B\subset F_p$. The case $A=B$ of this conjecture has been recently established by Shkredov. The analogous problem for differences remains open: is it true that for all sufficiently large primes $p$, the set of quadratic residues modulo $p$ is not of the form $\{a'-a"\colon a',a"\in A,\,a'\ne a"\}$ with $A\subset F_p$? We attack here a presumably more tractable variant of this problem, which is to show that there is no $A\subset F_p$ such that every quadratic residue has a \emph{unique}representation as $a'-a"$ with $a',a"\in A$, and no non-residue is represented in this form. We give a number of necessary conditions for the existence of such $A$, involving for the most part the behavior of primes dividing $p-1$. These conditions enable us to rule out all primes $p$ in the range $13<p<10^{18}$ (the primes $p=5$ and $p=13$ being conjecturally the only exceptions).