9
$\begingroup$

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.

$\endgroup$
14
  • 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$ Commented Mar 24, 2014 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
    Commented Mar 24, 2014 at 17:39
  • 1
    $\begingroup$ @GH: I didn't add any real ideas, but I think Seva's argument should be an answer. $\endgroup$ Commented Mar 24, 2014 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
    Commented Mar 24, 2014 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$ Commented Mar 24, 2014 at 18:23

1 Answer 1

23
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ you have a typo in the definition of $\sigma_p$. $\endgroup$
    – Asaf
    Commented Mar 24, 2014 at 18:28
  • $\begingroup$ I had a lot of typos, hopefully most of them are fixed now... Thanks! $\endgroup$
    – Seva
    Commented Mar 24, 2014 at 18:31
  • 10
    $\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$ Commented Mar 24, 2014 at 19:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .