Return to Answer

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_1,\ldots,\epsilon_k\in\{-1,1\}$ ("the pattern") and for a prime $p$, let $$ \sigma_p := 2^{-k} \sum_{x\in{\mathbb F}_p}\prod_{j=1}^k \left(\epsilon_j+\left(\frac{x+j}{p}\right)\right) $$ where $\left(\frac xp\right)$ is the Legendre symbol. If no run of $k$ consecutive elements of ${\mathbb F}_p$ follows our pattern (meaning that for every $x\in{\mathbb F}_p$ there is $j\in[1,k]$ with $\left(\frac{x+j}p\right)\ne\epsilon_j$), then all summands in $\sigma_p$ vanish, with the possible exception of the $k$ summands corresponding to $x\in\{-k,\ldots,-1\}$, and each of these $k$ exceptional summands is at most $2^{k-1}$ in absolute value; hence, $|\sigma_p|\le k/2$. On the other hand, expanding the product in $\sigma_p$ one can write it as a sum of the main term $2^{-k}\sum_x\epsilon_1\dotsb\epsilon_k=2^{-k}\epsilon p$ (with $\epsilon=\epsilon_1\dotsb\epsilon_k$) 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, $$ \sigma_p=2^{-k}\epsilon p+\theta k\sqrt p,\ |\theta|<1, $$ manifestly contradicting $|\sigma_p|\le k/2$ for $p>\exp(ck)$ with a sufficiently large $c$.

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.

The answer to both your questions is positive; this is non-trivial, but fairly standard. For a prime $p$, let $$ \sigma_p := 2^{-k} \sum_{x\in{\mathbb F}_p}\prod_{j=1}^k \left(1-\left(\frac{x+j}{p}\right)\right) $$ where $(x/p)$ is the Legendre symbol. If every run of $k$ consecutive elements of ${\mathbb F}_p$ contains a square, then all summands in $\sigma_p$ vanish, with the possible exception of the $k$ summands corresponding to $x\in\{-k,\ldots,-1\}$, and each of these $k$ exceptional summands is at most $2^{k-1}$; hence, $\sigma_p\le k/2$. On the other hand, expanding the product in $\sigma_p$ one can write it 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 (Q(x)/p)$ 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, $$ \sigma_p>2^{-k}p-k\sqrt p, $$ manifestly contradicting $\sigma_p\le k/2$ for $p>\exp(ck)$ with a sufficiently large $c$.

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_1,\ldots,\epsilon_k\in\{-1,1\}$ ("the pattern") and for a prime $p$, let $$ \sigma_p := 2^{-k} \sum_{x\in{\mathbb F}_p}\prod_{j=1}^k \left(\epsilon_j+\left(\frac{x+j}{p}\right)\right) $$ where $\left(\frac xp\right)$ is the Legendre symbol. If no run of $k$ consecutive elements of ${\mathbb F}_p$ follows our pattern (meaning that for every $x\in{\mathbb F}_p$ there is $j\in[1,k]$ with $\left(\frac{x+j}p\right)\ne\epsilon_j$), then all summands in $\sigma_p$ vanish, with the possible exception of the $k$ summands corresponding to $x\in\{-k,\ldots,-1\}$, and each of these $k$ exceptional summands is at most $2^{k-1}$ in absolute value; hence, $|\sigma_p|\le k/2$. On the other hand, expanding the product in $\sigma_p$ one can write it as a sum of the main term $2^{-k}\sum_x\epsilon_1\dotsb\epsilon_k=2^{-k}\epsilon p$ (with $\epsilon=\epsilon_1\dotsb\epsilon_k$) 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, $$ \sigma_p=2^{-k}\epsilon p+\theta k\sqrt p,\ |\theta|<1, $$ manifestly contradicting $|\sigma_p|\le k/2$ for $p>\exp(ck)$ with a sufficiently large $c$.

The answer to both your questions is positive; this is non-trivial, but fairly standard. For a prime $p$, let $$ \sigma_p := 2^{-k} \sum_{x\in{\mathbb F}_p}\prod_{j=1}^k \left(1-\left(\frac{x+j}{p}\right)\right) $$ where $(x/p)$ is the Legendre symbol. If every run of $k$ consecutive elements of ${\mathbb F}_p$ contains a square, then all summands in $\sigma_p$ vanish, with the possible exception of the $k$ summands corresponding to $x\in\{-k,\ldots,-1\}$, and each of these $k$ exceptional summands is at most $2^{k-1}$; hence, $\sigma_p\le 1/2$. On the other hand, expanding the product in $\sigma_p$ one can write it 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 (Q(x)/p)$ 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; hence $$ \sigma_p>2^{-k}p-k\sqrt p, $$ manifestly contradicting $\sigma_p\le 1/2$ for $p>\exp(ck)$ with a sufficiently large $c$.

The answer to both your questions is positive; this is non-trivial, but fairly standard. For a prime $p$, let $$ \sigma_p := 2^{-k} \sum_{x\in{\mathbb F}_p}\prod_{j=1}^k \left(1-\left(\frac{x+j}{p}\right)\right) $$ where $(x/p)$ is the Legendre symbol. If every run of $k$ consecutive elements of ${\mathbb F}_p$ contains a square, then all summands in $\sigma_p$ vanish, with the possible exception of the $k$ summands corresponding to $x\in\{-k,\ldots,-1\}$, and each of these $k$ exceptional summands is at most $2^{k-1}$; hence, $\sigma_p\le k/2$. On the other hand, expanding the product in $\sigma_p$ one can write it 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 (Q(x)/p)$ 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, $$ \sigma_p>2^{-k}p-k\sqrt p, $$ manifestly contradicting $\sigma_p\le k/2$ for $p>\exp(ck)$ with a sufficiently large $c$.