Difference sets avoiding quadratic residues I have a homework question that is stumping me, and I am looking for an entry point. It goes like this:

Suppose $p$ is prime. Prove that the largest set $S\subseteq\{0,1,\dots, p-1\}$ such that $S-S$ contains no nonzero quadratic residues must have cardinality less than $\sqrt p$.

I use $S-S$ to mean the difference set modulo $p$; that is $\{a-b\in\mathbb{Z}_p: a,b\in S\}$.
The question also comes with the suggestion of looking for a combinatorial argument. Since we have an inquality, I naturally tried to find an injection. Nothing was immediately obvious in the problem that had size $\sqrt p$, so I considered $S^2$. The advantage of this is that there is a function that we know something about: $f: S^2\to\mathbb{Z}_p\setminus Q_p$ such that $(a,b)\mapsto a-b$. Here the $Q_p$ is meant to be the quadratic residues, not including $0$.
If I could show that $f$ was at-most-two-to-one except on the diagonal, this would be good enough. But I strongly suspect that this is false. Unfortunately, with some fiddling it becomes clear that any counterexample would have to be with quite large $p$ and I am not sure how one might be found.
What has me really stumped is how to use the primeness of $p$. My best guess is that for some reason we are particularly worried that $0$ may be a square number nontrivially, which can be avoided because $\mathbb{Z}_p$ is a field?
 A: We use quadratic Gauss sums: 
$$g(a, p)=\sum_{n=0}^{p-1}{e^{\frac{2 \pi ian^2}{p}}}=\sum_{n=0}^{p-1}{e\left(\frac{an^2}{p}\right)}$$
where for readability we use $$e(x)=e^{2 \pi ix}$$
We have the following property of quadratic Gauss sums:
$$\begin{cases} |g(a, p)|=\sqrt{p} & a \not =0 \\ g(0, p)=p \end{cases}$$
Suppose that $S$ is as given. Consider 
\begin{align}
A& =\sum_{a=0}^{p-1}{\left(\left|\sum_{s \in S}{e\left(\frac{as}{p}\right)}\right|^2(g(a, p)-1)\right)} \\
& =\sum_{a=0}^{p-1}{\left(\sum_{s, s' \in S}{e\left(\frac{a(s-s')}{p}\right)}\sum_{n=1}^{p-1}{e\left(\frac{an^2}{p}\right)}\right)} \\
& =\sum_{a=0}^{p-1}{\left(\left(|S|+\sum_{s, s' \in S, s \not =s'}{e\left(\frac{a(s-s')}{p}\right)}\right)\sum_{n=1}^{p-1}{e\left(\frac{an^2}{p}\right)}\right)} \\
& =|S|\sum_{n=1}^{p-1}{\sum_{a=0}^{p-1}{e\left(\frac{an^2}{p}\right)}}+\sum_{s, s' \in S, s \not =s'}{\sum_{n=1}^{p-1}{\sum_{a=0}^{p-1}{{e\left(\frac{a(s-s'+n^2)}{p}\right)}}}} \\
& =|S|\sum_{n=1}^{p-1}{0}+\sum_{s, s' \in S, s \not =s'}{\sum_{n=1}^{p-1}{\sum_{a=0}^{p-1}{{0}}}} \\
& =0
\end{align}
where to get from the third last line to the second last line, we have used that $s'-s \not \equiv n^2 \pmod{p}$ for $s \not =s'$ and $\sum_{a=0}^{p-1}{e\left(\frac{ak}{p}\right)}=0$ for $p \nmid k$.
\begin{align}
0& =\sum_{a=0}^{p-1}{\left(\left|\sum_{s \in S}{e\left(\frac{as}{p}\right)}\right|^2(g(a, p)-1)\right)} \\
&= |S|^2(p-1)+\sum_{a=1}^{p-1}{\left(\left|\sum_{s \in S}{e\left(\frac{as}{p}\right)}\right|^2(g(a, p)-1)\right)}
\end{align}
Thus 
\begin{align}
|S|^2(p-1)&= \left||S|^2(p-1)\right|\\
&=\left|-\sum_{a=1}^{p-1}{\left(\left|\sum_{s \in S}{e\left(\frac{as}{p}\right)}\right|^2(g(a, p)-1)\right)}\right| \\
& \leq \sum_{a=1}^{p-1}{\left|\left|\sum_{s \in S}{e\left(\frac{as}{p}\right)}\right|^2(g(a, p)-1)\right|} \\
& =\sum_{a=1}^{p-1}{\left(\left|\sum_{s \in S}{e\left(\frac{as}{p}\right)}\right|^2|g(a, p)-1|\right)} \\
& \leq (\sqrt{p}+1)\sum_{a=1}^{p-1}{\left(\left|\sum_{s \in S}{e\left(\frac{as}{p}\right)}\right|^2\right)}
\end{align}
Therefore 
\begin{align}
|S|^2(\sqrt{p}-1) & \leq \sum_{a=1}^{p-1}{\left(\left|\sum_{s \in S}{e\left(\frac{as}{p}\right)}\right|^2\right)} \\
& =\sum_{a=1}^{p-1}{\left(|S|+\sum_{s, s' \in S, s \not =s'}{e\left(\frac{a(s-s')}{p}\right)}\right)} \\
& =(p-1)|S|+\sum_{s, s' \in S, s \not =s'}{\sum_{a=1}^{p-1}{e\left(\frac{a(s-s')}{p}\right)}} \\
& =(p-1)|S|+\sum_{s, s' \in S, s \not =s'}{\left(\left(\sum_{a=0}^{p-1}{e\left(\frac{a(s-s')}{p}\right)}\right)-1\right)} \\
& =(p-1)|S|+\sum_{s, s' \in S, s \not =s'}{-1} \\
&=(p-1)|S|-|S|(|S|-1) \\
& =p|S|-|S|^2
\end{align}
It is now easy to see that we get $|S| \leq \sqrt{p}$. Clearly equality cannot hold.
