# Isolated quadratic residues in integers mod p

For prime p sufficiently large, there is always an integer q such that q is a residue mod p, but neither q−1 nor q+1 are; the number of such residues scales like p/8 (and similarly for any sequence of residues/non-residues in three consecutive integers).

What are the best lower bounds on primes p, for which such "isolated" residues are guaranteed to exist? Do they exist, for instance, for all p ≡ 3 (mod 4) aside from p = 3?

(If this is a typical homework problem, please point me to a textbook for which it is an exercise.)

-

I'll write $\chi(x)$ for the Legendre symbol modulo $p$. Consider $$f(x)=(\chi(x)+1)(\chi(x-1)-1)(\chi(x+1)-1).$$ Then $f(x)=8$ if $x$ is an isolated quadratic residue and $0$ otherwise (unless $x$ is $0$, $\pm1$ which are exceptional cases that have to be factored in to the bookkeeping eventually). Thus $S=\sum_{x=1}^p f(x)$ is eight times the number of isolated primes plus a fudge factor. But expanding out $S$ gives sums such as $\sum\chi(x)$ and $\sum\chi(x(x-1))$ which are easy to deal with, and also $T=\sum\chi(x^3-x)$. This final sum is related to the number of points on the elliptic curve $y^2=x^3-x$ and so is bounded by $2\sqrt p$ by Hasse's bound. But if $p\equiv3$ (mod $4$), $T=0$ as the $x$ and $-x$ terms cancel. In this case one gets an exact formula for the number of isolated quadratic residues.

One can extend this ideal to bigger patterns of residues and nonresidues. As the polynomials become larger they are related to hyperelliptic curves, but from the Riemann hypothesis for curve one can still get bounds.

-
Thank you for sketching out the appropriate technique! This is very clean and quite helpful. – Niel de Beaudrap May 21 '10 at 13:17
"One can extend this ideal to bigger patterns"--an artistic typo? :) – Wadim Zudilin May 24 '10 at 13:54

This comes down to finding the points mod p on a certain elliptic curve with complex multiplication by the Gaussian integers. The good news is that the error term in Hasse's theorem is entirely manageable, and the cases of small p can be dealt with pretty much by hand for p congruent to 1 mod 4. For some reason you are asking about p congruent to 3 mod 4. Which is basically easier.

The reduction to the counting problem goes like this: set up a character sum using the Legendre symbol, over residues mod p, of a summand with three factors, which will be zero unless the three conditions are all fulfilled (so [Legendre symbol of q minus 1] is one typical factor). Multiply out, and all the terms except the one counting those points on an elliptic curve (i.e. Sigma [Legendre symbol of cubic in q]) can be evaluated. The Sigma of quadratic terms are 1 or -1 by a standard sum (counts points on projective line).

Hope that helps. This problem looks eminently doable.

[Added: Since Robin has answered in a complementary way while I was typing, an amplification. If you do need p congruent to 1 mod 4 and calculations for small p, the key thing is the size of a and b when you write p as a sum of two squares.]

-
Robin types faster? :-( – Charles Matthews May 21 '10 at 12:48
Sorry Charles for being too quick :-) To amplify your amplification, my $T$ will be one of Charles's $\pm 2a$ and $\pm 2b$. – Robin Chapman May 21 '10 at 13:04
Thanks for the response! Not having a background in such problems, I wasn't able to see even that my special case is the simpler one. – Niel de Beaudrap May 21 '10 at 13:20

In addition to the character sum approach explained by Charles and Robin, which gives you a precise formula for the number of NRN patterns $\mod p$ for any $p$, in the case $p\equiv 3(\mod 4)$ there is an elementary proof that avoids elliptic curves or Gauss sums. (Notation: N is quadratic non-residue, R is quadratic residue.)

I claim that it is sufficient to find an arithmetic progression $\mod p$ of the form $-a^2,1,-b^2$ with non-zero $a,b.$ Indeed, $-a^2$ and $-b^2$ are N and 1 is R. Choose the sign so that $n=\pm(1+a^2)$ is R: this is possible since $-1$ is a quadratic non-residue $(\mod p),$ by the assumption on $p$. Dividing by $n$, we'll get three consecutive non-zero numbers $\mod p$ in pattern NRN. Thus it remains to show that $a^2+b^2=-2 (\mod p)$ has a solution with $a,b\ne 0,$ which is a special case of the well known fact that for $p\geq 7,$ any non-zero element of $\mathbb{Z}/p\mathbb{Z}$ is the sum of two non-zero squares. Conversely, all NRN patterns are obtained in this way and with a tiny bit of extra work, one can count that there are $(p+1)/8$ or $(p-3)/8$ of them, depending on whether $p\equiv 7(\mod 8)$ or $p\equiv 3(\mod 8).$

-