I am an overzealous undergraduate who is attempting to read through parts of Laszlo Lovasz's book "Graph Limits and Networks". However, it is intended for graduate readers and as such I reaching out for help to see how to solve this excercise:
Let $p_i$ be the $i$-th smallest prime of the form $p=4k+1$, and let $Q_i$ be the set of quadratic residues (mod $p$). Prove that as $i$ increases, that for almost all $r_1 \in Q_i$, $|\{r_2 \in Q_i : r_1-r_2 \in Q_i\}|$ is asymptotically half the size of $Q_i$.
(here, "almost all" and "asymptotically" mean that for any epsilon, there exists $i$ where the error is below epsilon)
I have been quite stumped on this, and would like a helpful push in the right direction. I am currently familiar with the Euler Criterion, Gauss's lemma, and quadratic reciprocity, but none of them seemed to help.
Fix $p$, and let $Q$ be the set of quadratic residues modulo $p$. Write $S_r = \{s\in Q\ :\ r-s\in Q\}$. Since $p\equiv 1\mod{4}$, we know that $-1$ is a quadratic residue, so that $S_r = \{s\in Q\ :\ s-r\in Q\}$. Now, if $q, r\not\equiv 0\mod{p}$ with $q, r\in Q$, then also $r^{-1}\in Q$. If $s\in S_r$, then $$s-r\in Q\equiv r^{-1}(s-r)\in Q\equiv qr^{-1}s-q\in Q.$$ Thus $|S_r| = |S_q|$. It suffices to compute the size of $S_1$.
Now, $s-1\in Q$, $s\ne 1$, means that (writing $s=y^2$ since $s\in Q$) $y^2-1 = x^2$ for some $x\in\left(\mathbb{Z}/p\right)^*$, or $1 = y^2-x^2 = (y+x)(y-x)$. So each factorization of $1$ in $\mathbb{Z}/p$ leads to an element of $Q$, namely $y^2$, and distinct (up to order and sign) factorizations lead to different elements of $Q$. There are (up to order) $\frac{p+1}{2}$ factorizations of $1$ ($1^2$, $(-1)^2$, and half of the set $\{a\cdot a^{-1}\ :\ 2\le a\le p-2\}$). Of these, there are $\frac{p-1}{4}$ pairs (of the form $(y,x)$ and $(-y,-x)$) differing only by sign, and one pair $(x,-x)$ (where $x^2\equiv -1\mod{p}$). Thus in total there are $\frac{p-1}{4}+1 = \frac{p+3}{4}$ distinct factorizations of $1$, so that $|S_1| = \frac{p+3}{4}$ and the result follows.