MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
ummm. why do you want to know? – 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.

share|cite|improve this answer

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

share|cite|improve this answer
Your numerical suggestion is correct, see my response below. – GH from MO Jul 18 '14 at 20:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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