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