# Cliques in the Paley graph and a problem of Sarkozy

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

# Added December 19, 2013

For the sumset $2A$ (instead of the difference set $A-A$), the problem was recently solved by Shkredov, who has shown that there is no $A\subset{\mathbb F}_p$ such that $2A$ is precisely the set ${\mathcal Q}_0:={\mathcal Q}\setminus\{0\}$ of all quadratic residues. I cannot keep myself from sketching Shkredov's argument here.

Assuming that $2A={\mathcal Q}_0$ and writing fro brevity $n:=|A|$, we have $\binom{n}{2}+n\ge\frac{p-1}2$, whence $p\le n^2+n+1$. For every $x\in{\mathbb F}_p$, let $\sigma(x):=\sum_{a\in A}\left(\frac{x+a}p\right)$. If $x\in A$, then $\sigma(x)=n$. Hence, $$\sum_{x\in A}(\sigma(x))^2\ge n^3,$$ while the sum over all $x\in{\mathbb F}_p$ can be only marginally larger: $$\sum_{x\in{\mathbb F}_p} (\sigma(x))^2 = \sum_{a,b\in A} \sum_{x\in{\mathbb F}_p} \left(\frac{(x+a)(x+b)}p\right) = n(p-n) \le \sum_{x\in A} (\sigma(x))^2 + n.$$ With a very minor further effort, one obtains a contradiction.

Since the original problem for the difference set $A-A$ cannot be treated with this method and, apparently, is still too difficult, here is a presumably easier question.

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}$, and every non-zero element of $\mathcal Q$ has a unique representation as a difference of two elements of $A$?

Needless to say, the anticipated answer is negative.

-