Inspired by this recent question, I wondered if a similar result is true for quadratic non-residues, namely, if it is true that for every $k \in \mathbb{N}$ there exists a prime $p$ such that exists $k$ consecutive quadratic non-residues mod $p$? or even a stronger result like for every $k \in \mathbb{N}$ there exists $N$ such that for every prime $p > N$ we have $k$ consecutive quadratic non-residues mod $p$?

Obviously, the idea used in the link could not be adapted to this case because it relies on the fact that the product of two quadratic residues is a quadratic residue, which is not true for quadratic non-residues. I searched the web and did not find anything relevant on this question. Does anybody have any ideas?

Thank you!

PS: If anyone could give me a reference to a book that approaches this kind of problems (consecutive quadratic or non-quadratic residues), I would be grateful.

  • 4
    $\begingroup$ For the first problem, you can choose $p=4k+3$ and multiply a sequence of consecutive quadratic residues by $-1$. I didn't read the second problem before voting to close, and I apologize for that and would undo it if I could. The second problem is more interesting. However, the abstract of the Buell and Hudson paper "On runs of consecutive quadratic residues and quadratic nonresidues" mentioned on the math.stackexchange.com question you linked claims to show that for all sufficiently large primes, there are arbitrarily long runs of quadratic nonresidues (and the same for residues). $\endgroup$ – Douglas Zare Mar 24 '14 at 17:36
  • 1
    $\begingroup$ @GH: it may not be trivial, but is very standard: if for a prime $p$ every run of $k$ residues contained a square, then the sum $$\sum_x \prod_{j=1}^k \left(1-\left(\frac{x+j}{p}\right)\right)$$ would be very close to $0$, while from Wwyl's bound it is actually close to $p$. Have I got anything wrong? $\endgroup$ – Seva Mar 24 '14 at 17:39
  • 1
    $\begingroup$ @GH: I didn't add any real ideas, but I think Seva's argument should be an answer. $\endgroup$ – Douglas Zare Mar 24 '14 at 17:46
  • 1
    $\begingroup$ @André: I made a mistake in my comment. Here it is corrected: Weil's bound (not Weyl's) shows that for any polynomial $Q\in\mathbb{F}_p[x]$ with distinct roots we have that $\left|\sum_{x\in\mathbb{F}_p}\left(\frac{Q(x)}{p}\right)\right|$ is bounded by a constant times $\sqrt{p}$. Factoring out the product in Seva's sum yields several such character sums and also a sum of $1$'s, hence the sum is $p+O(\sqrt{p})$. On the other hand, the product in the sum vanishes whenever $x+j$ is a quadratic residue for some $j$. $\endgroup$ – GH from MO Mar 24 '14 at 18:15
  • 2
    $\begingroup$ @André: Although that particular proof used $p=4k+1$, the idea that you can control whether the first few primes are quadratic residues by choosing $p$ to be in a particular arithmetic progression works even if we choose $p=4k+3$. Choose $p$ so that it is congruent to $-1$ mod $8$ and mod $q$ for the first few odd primes. By quadratic reciprocity this makes the first few primes squares mod $p$, while $-1$ is not a square. By Dirichlet's theorem on primes in arithmetic progressions there are primes satisfying these congruences. $\endgroup$ – Douglas Zare Mar 24 '14 at 18:23

The answer to both your questions is positive and indeed, every given pattern of quadratic residues and non-residues of fixed length appears among consecutive elements of ${\mathbb F}_p$, for all $p$ large enough; moreover, it appears about the expected number of times. This is non-trivial, but fairly standard.

Fix $\epsilon=(\epsilon_1,\ldots,\epsilon_k)\in\{-1,1\}^k$ ("the pattern") and for a prime $p$, let $N_\epsilon(p)$ denote the number of those $x\in{\mathbb F}_p$ with $$ \left(\frac{x+1}p\right)=\epsilon_1,\ldots, \left(\frac{x+k}p\right)=\epsilon_k, $$ where $\left(\frac xp\right)$ is the Legendre symbol. Clearly, we have \begin{align*} N_\epsilon(p) &= 2^{-k}\sum_{x=0}^{p-k-1} \prod_{j=1}^k \left(1+\epsilon_j\left(\frac{x+j}{p}\right) \right) \\ &= 2^{-k}\sum_{x=0}^{p-1} \prod_{j=1}^k \left(1+\epsilon_j\left(\frac{x+j}{p}\right) \right) - \theta \frac k2,\quad 0\le \theta\le 1, \end{align*} as the contribution of each $x\in[p-k,p-1]$ to the whole sum is at most $2^{k-1}$.

Expanding the product, one can write $N_\epsilon(p)$ as a sum of the main term $2^{-k}\sum_x1=2^{-k}p$ and $2^k-1$ remainder terms, each of the form $2^{-k}\sum_x \left(\frac{Q(x)}p\right)$ with a non-square polynomial $Q(x)$ of degree at most $k$. Now, Weil's bound implies that each of these remainder terms does not exceed $(k-1)\sqrt p$ in absolute value; as a result, $$ N_\epsilon(p)=2^{-k}p+\theta k(\sqrt p+1/2),\ |\theta|<1, $$ which is certainly positive for $p$ sufficiently large (like $p>\exp(ck)$ with a suitable constant $c$).

This argument readily extends to count, say, the number of those elements $x$ of a finite field such that for a given system of square-free, pairwise co-prime polynomials $P_1,\ldots,P_k\in{\mathbb Z}[X]$, the values $P_1(x),\ldots,P_k(x)$ follow a prescribed quadratic residue / non-residue pattern. Indeed, in a similar way one can handle the joint distribution of $P_1(x),\ldots P_k(x)$ in the cosets of any subgroup of the multiplicative group of a finite field, not just the subgroup of quadratic residues.

  • $\begingroup$ you have a typo in the definition of $\sigma_p$. $\endgroup$ – Asaf Mar 24 '14 at 18:28
  • $\begingroup$ I had a lot of typos, hopefully most of them are fixed now... Thanks! $\endgroup$ – Seva Mar 24 '14 at 18:31
  • $\begingroup$ @Seva: I think the exceptional $x$'s contribute at most $k/2$, not $1/2$ (as they add up and there are $k$ of them). $\endgroup$ – GH from MO Mar 24 '14 at 18:48
  • 8
    $\begingroup$ This result goes back to Davenport, and was a motivating problem for studying character sums over finite fields; see Acta Mathematica December 1939, Volume 71, Issue 1, pp 99-121, section 9. Davenport proves, and uses, a zero-free strip for the relevant L-functions instead of using the (then unproved) Riemann Hypothesis. $\endgroup$ – Denis Chaperon de Lauzières Mar 24 '14 at 19:45

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.