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$?

  • 3
    $\begingroup$ ummm. why do you want to know? $\endgroup$ – Will Jagy Jul 18 '14 at 18:11

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

  • $\begingroup$ Your numerical suggestion is correct, see my response below. $\endgroup$ – GH from MO Jul 18 '14 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.