# overlap quadratic residues

Let $p$ be a prime number of form $4k+1$ and $M$ is its quadratic residue set.

Let $M_i=\{i+x|\forall x\in M\}$ $\forall 0<i<p$.

Does there exist a positive constant $\varepsilon$ such that for every $p$ large enough, $|M\cap M_i|<\frac{(1-\varepsilon)(p-1)}{2}\ \ \forall 0<i<p$?

-
ummm. why do you want to know? –  Will Jagy Jul 18 '14 at 18:11

## 2 Answers

Here is an elementary approach. $\#(M\cap M_i)$ equals the number of solutions $y-x=i$ with $x,y\in M$. Every quadratic residue is the square of two nonzero residues, so $\#(M\cap M_i)$ equals $1/4$ times the number of solutions of $a^2-b^2=i$ with $a,b\in\mathbb{F}_p^\times$. For $p>2$ we can make the bijective change of variables $u:=a+b$ and $v:=a-b$, which shows that we are counting the number of solutions $uv=i$ with $u,v\in\mathbb{F}_p$ such that $u\neq\pm v$. Without the restriction $u\neq\pm v$, there are exactly $p-1$ solutions (indeed, let $u\in\mathbb{F}_p^\times$ be arbitrary and put $v:=i/u$). If $i$ is a quadratic residue, then there are precisely $4$ solutions with $u=\pm v$, otherwise there are no such solutions.

To summarize, $\#(M\cap M_i)$ equals $\frac{p-5}{4}$ or $\frac{p-1}{4}$ depending on whether $i$ is a quadratic residue or not.

For $p\equiv 3\pmod{3}$, there are precisely $2$ solutions of $uv=i$ with $u=\pm v$ (because precisely one of $i$ and $-i$ is a quadratic residue), hence in this case $\#(M\cap M_i)$ always equals $\frac{p-3}{4}$.

Added. In general, it is easy to count the number of solutions of $a_1x_1^2+\dots +a_kx_k^2=b$ in a finite field. For a treatment of $k=2$ (which is straightforward to extend to $k>2$) see my earlier response here.

-

Using the fact that $\frac12(1+(\frac np))$ equals $1$ if $n$ is a quadratic residue modulo $p$ and $0$ if $n$ is a quadratic nonresidue, we see that $$\#(M\cap M_i) = \sum_{n=1}^{p-1} \frac12\bigg(1+\bigg(\frac np\bigg)\bigg)\frac12\bigg(1+\bigg(\frac{n+i}p\bigg)\bigg) + O(1).$$ (If $i$ is a quadratic residue modulo $p$, then the $n=p-i$ term in this sum contributes $\frac12$ when it should contribute $0$; that's the reason for the $O(1)$. I'll not comment on similar anomalies hereafter, for brevity.) Therefore \begin{align*} \#(M\cap M_i) &= \frac{p-1}4 + \frac14\sum_{n=1}^{p-1} \bigg(\frac np\bigg) + \frac14\sum_{n=1}^{p-1} \bigg(\frac{n+i}p\bigg) + \frac14\sum_{n=1}^{p-1} \bigg(\frac np\bigg)\bigg(\frac {n+i}p\bigg) + O(1) \\ &= \frac{p-1}4 + 0+0+ \frac14\sum_{n=1}^{p-1} \bigg(\frac {n(n+i)}p\bigg) + O(1). \end{align*}

Making the change of variables $m\equiv n^{-1}$ (mod $p$), this last sum is \begin{align*} \sum_{n=1}^{p-1} \bigg(\frac {n(n+i)}p\bigg) &= \sum_{m=1}^{p-1} \bigg(\frac {m^{-1}(m^{-1}+i)}p\bigg) \\ &= \sum_{m=1}^{p-1} \bigg(\frac {m^{-1}(m^{-1}+i)}p\bigg) \bigg(\frac {m^2}p\bigg) \\ &= \sum_{m=1}^{p-1} \bigg(\frac {1+mi}p\bigg) = \sum_{k=1}^{p-1} \bigg(\frac kp\bigg) + O(1) = 0 + O(1). \end{align*} by another change of variables. (This assumes $p\nmid i$ of course.)

In sumamry, $\#(M\cap M_i)$ is extremely close to $\frac{p-1}4$: the difference is even bounded! Numerical experiments suggest, and a clarification of the above argument would surely show, that the answer is exactly $\frac{p-3}4$ when $p\equiv3$ (mod $4$) and either $\frac{p-1}4$ or $\frac{p-5}4$ when $p\equiv1$ (mod $4$).

-
Your numerical suggestion is correct, see my response below. –  GH from MO Jul 18 '14 at 20:05