Isolated quadratic residues in integers mod p

Question

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

Answer 1

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.

Answer 2

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.]

Answer 3

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