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.


Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.