Cliques in the Paley graph and a problem of Sarkozy

2012-09-19T09:44:41Z

The following question is motivated by pure curiosity; it is not a part of any research project and I do not have any applications. The question comes as an interpolation between two notoriously difficult open problems.

The first problem is to show that if $p\equiv 1\pmod 4$ is prime, and a set $A\subset{\mathbb F}_p$ has the property that the difference of any two elements of $A$ is a square, then $A$ is "small". (Basic details can be found here). Notice that, letting ${\mathcal Q}:=\{x^2\colon x\in{\mathbb F}_p\}$ , one can write the assumption as $A-A\subset{\mathcal Q}$.

The second problem, to my knowledge first posed by Andras Sarkozy several years ago, is to determine whether the set of all squares is as a sumset; that is, whether ${\mathcal Q}=A+B$ with $A,B\subset{\mathbb F}_p$ and $\min\{|A|,|B|\}\ge 2$ . The conjectural answer is, of course, negative, provided that $p$ is sufficiently large.

Both problems just mentioned seem to be quite tough; but, maybe, the following combination of the two is more tractable:

For a prime $p\equiv 1\pmod 4$, writing ${\mathcal Q}$ for the set of all squares in ${\mathbb F}_p$, does there exist a set $A\subset{\mathbb F}_p$ such that $A-A={\mathcal Q}$?

Compared to the first of the two aforementioned problems, we now assume that every quadratic residue is representable as a difference of two elements of $A$; compared to the second problem we assume that $B=-A$. Is there a way to utilize these extra assumptions?

A funny observation is that sets $A$ with the property in question do exist for $p=5$ and also for $p=13$; however, it would be very plausible to conjecture that these values of $p$ are exceptional. (In this direction, Peter Mueller has verified computationally that no other exceptions of this sort occur for $p<1000$.)

Cliques in the Paley graph and a problem of Sarkozy - MathOverflow

Cliques in the Paley graph and a problem of Sarkozy