gpt pro 5.2 attempt on Math-816

If $p$ is a prime and $k,m\geq 2$ then let $r(k,m,p)$ be the minimal $r$ such that $r,r+1,\ldots,r+m-1$ are all $k$th power residues modulo $p$. Let\[\Lambda(k,m)=\limsup_{p\to \infty} r(k,m,p).\]Is it true that $\Lambda(k,2)$ is finite for all $k$? Is $\Lambda(k,3)$ finite for all odd $k$? How large are they? Asked by Lehmer and Lehmer [LeLe62], who note that for example $\Lambda(2,2)=9$ - indeed, $9$ is always a quadratic residue, and if $10$ isn't then either $2$ or $5$ is, and hence at least one of $1,2$ or $4,5$ or $9,10$ is a consecutive pair of quadratic residues (and similarly there are infinitely many $p$ for which there are no consecutive quadratic residues below $9,10$). A similar argument of Dunton [Du65] proves $\Lambda(3,2)=77$, and Bierstedt and Mills [BiMi63] proved $\Lambda(4,2)=1224$. Lehmer and Lehmer proved that $\Lambda(k,3)=\infty$ for all even $k$ and $\Lambda(k,4)=\infty$ for all $k\leq 1048909$. Lehmer, Lehmer, and Mills [LLM63] proved $\Lambda(5,2)=7888$ and $\Lambda(6,2)=202124$. Brillhart, Lehmer, and Lehmer [BLL64] proved $\Lambda(7,2)=1649375$. Lehmer, Lehmer, Mills, and Selfridge [LLMS62] proved that $\Lambda(3,3)=23532$. Graham [Gr64g] proved that $\Lambda(k,l)=\infty$ for all $k\geq 2$ and $l\geq 4$. Hildebrand [Hi91] resolved the first question, proving that $\Lambda(k,2)$ is finite for all $k$: in other words, for any $k\geq 2$, if $p$ is sufficiently large then there exists a pair of consecutive $k$th power residues modulo $p$ in $[1,O_k(1)]$. The remaining questions are to examine whether $\Lambda(k,3)$ is finite for all odd $k\geq 5$, and the growth rate of $\Lambda(k,2)$ and $\Lambda(k,3)$ as functions of $k$. References [BLL64] Brillhart, John and Lehmer, D. H. and Lehmer, Emma, Bounds for pairs of consecutive seventh and higher power residues . Math. Comp. $1964$, 397--407. [BiMi63] Bierstedt, R. G. and Mills, W. H., On the bound for a pair of consecutive quartic residues of a prime . Proc. Amer. Math. Soc. $1963$, 628--632. [Du65] Dunton, M., Bounds for pairs of cubic residues . Proc. Amer. Math. Soc. $1965$, 330--332. [Gr64g] Graham, R. L., On quadruples of consecutive {$k$}th power residues . Proc. Amer. Math. Soc. $1964$, 196--197. [Hi91] Hildebrand, Adolf, On consecutive {$k$}th power residues. II . Michigan Math. J. $1991$, 241-253. [LLM63] Lehmer, D. H. and Lehmer, Emma and Mills, W. H., Pairs of consecutive power residues . Canadian J. Math. $1963$, 172--177. [LLMS62] Lehmer, D. H. and Lehmer, E. and Mills, W. H. and Selfridge, J. L., Machine proof of a theorem on cubic residues . Math. Comp. $1962$, 407--415. [LeLe62] Lehmer, D. H. and Lehmer, Emma, On runs of residues . Proc. Amer. Math. Soc. $1962$, 102-106.

FORMAL RESTATEMENT

Fix integers $k\ge 2$ and $m\ge 2$. For an odd prime $p$, write $\mathbb F_p^*=(\mathbb Z/p\mathbb Z)^*$. Define the set of nonzero $k$th power residues modulo $p$ by \[ \mathcal R_k(p):=\{x^k\bmod p : x\in\mathbb F_p^*\}\subseteq\{1,2,\dots,p-1\}. \] Define $r(k,m,p)$ to be the least integer $r\in\{1,2,\dots,p-m\}$ such that \[ \{r,r+1,\dots,r+m-1\}\subseteq \mathcal R_k(p). \] If no such $r$ exists, set $r(k,m,p)=\infty$. Then \[ \Lambda(k,m):=\limsup_{p\to\infty} r(k,m,p)\in[1,\infty]. \] Questions: 1) Is $\Lambda(k,2)<\infty$ for all $k\ge 2$? 2) Is $\Lambda(k,3)<\infty$ for all odd $k$? 3) What are the sizes/growth of $\Lambda(k,2),\Lambda(k,3)$ as functions of $k$?

Stress points: definition excludes $0$; otherwise $r(k,2,p)$ would trivially be $0$ because $0$ and $1$ are always $k$th powers.

QUICK LITERATURE/CONTEXT CHECK

I do not use results beyond those already named in the problem statement. The statement reports many exact values for small $k$ and $m=2$, and that Hildebrand proved $\Lambda(k,2)<\infty$ for all $k$.

ATTACK PLAN

Proof track (for special cases): 1) Prove the classical elementary bound $r(2,2,p)\le 9$ for all sufficiently large primes $p$ using residue multiplication. 2) Prove basic structural facts about $k$th powers in $\mathbb F_p^*$ (size of $\mathcal R_k(p)$).

Disproof track: Try to construct (for fixed $k,m$) infinitely many primes $p$ with no short run of $m$ consecutive $k$th power residues below some threshold.

I carry out $1$ and $2$ fully, and do computations for small primes to sanity-check definitions.

WORK

FAST REALITY CHECK (computation of $r(k,m,p)$ for small primes). Using the nonzero-residue definition above, I computed $r(k,m,p)$ for primes $p\le 2000$ or $5000$.

k=2 m=2 primes<= 2000: worst_r=9 at p=43; missing_runs=3
k=3 m=2 primes<= 5000: worst_r=36 at p=2161; missing_runs=3
k=4 m=2 primes<= 5000: worst_r=81 at p=1013; missing_runs=6
k=2 m=3 primes<= 5000: worst_r=49 at p=1303; missing_runs=6
k=3 m=3 primes<= 5000: worst_r=245 at p=2143; missing_runs=13

Here "missing_runs" counts primes with $r(k,m,p)=\infty$ in the searched range (these are small primes where $\mathcal R_k(p)$ is too sparse to contain an $m$-run).

Lemma 436.1 (elementary bound for consecutive quadratic residues). For every prime $p\ge 7$, there exists a pair of consecutive nonzero quadratic residues modulo $p$ among one of the three pairs $(1,2)$, $(4,5)$, or $(9,10)$. In particular, \[ r(2,2,p)\le 9\quad\text{for all primes }p\ge 7. \]

Proof. Let $Q\subseteq\mathbb F_p^*$ denote the set of nonzero quadratic residues modulo $p$. Then $Q$ is a subgroup of $\mathbb F_p^*$ of index $2$ (because the map $x\mapsto x^2$ is a group homomorphism with kernel $\{\pm 1\}$). In particular: - $1\in Q$ because $1\equiv 1^2$. - $4\in Q$ because $4\equiv 2^2$. - $9\in Q$ because $9\equiv 3^2$.

If $10\in Q$, then $(9,10)$ is a consecutive pair of quadratic residues and we are done. Assume instead that $10\notin Q$. Suppose for contradiction that both $2\notin Q$ and $5\notin Q$. Since $Q$ has index $2$, the complement $\mathbb F_p^*\setminus Q$ is a coset of $Q$, hence the product of two nonresidues lies in $Q$. Therefore $2\cdot 5=10$ would belong to $Q$, contradicting $10\notin Q$. Thus at least one of $2$ or $5$ is in $Q$.

- If $2\in Q$, then $(1,2)$ is a consecutive pair of residues. - If $5\in Q$, then $(4,5)$ is a consecutive pair of residues.

In all cases, one of the pairs $(1,2),(4,5),(9,10)$ consists of consecutive quadratic residues, which implies $r(2,2,p)\le 9$. $\Box$

Lemma 436.2 (count of nonzero $k$th power residues). Let $p$ be an odd prime and $k\ge 1$ an integer. Then \[ |\mathcal R_k(p)| = \frac{p-1}{\gcd(k,p-1)}. \]

Proof. The multiplicative group $\mathbb F_p^*$ is cyclic of order $p-1$. Consider the group homomorphism $\varphi:\mathbb F_p^*\to\mathbb F_p^*$ given by $\varphi(x)=x^k$. Then $\mathrm{im}(\varphi)=\mathcal R_k(p)$ by definition. By the first isomorphism theorem, \[|\mathrm{im}(\varphi)| = \frac{|\mathbb F_p^*|}{|\ker(\varphi)|} = \frac{p-1}{|\{x\in\mathbb F_p^*: x^k=1\}|}. \] Since $\mathbb F_p^*$ is cyclic of order $p-1$, the equation $x^k=1$ has exactly $\gcd(k,p-1)$ solutions (it is the unique subgroup of order $\gcd(k,p-1)$). Therefore $|\ker(\varphi)|=\gcd(k,p-1)$, giving the claimed formula. $\Box$

VERIFICATION

- The definition of $k$th power residue excludes $0$; otherwise Lemma 436.1 would be vacuous. This matches the example in the statement where $\Lambda(2,2)=9$. - Lemma 436.1: The only group fact used is that nonresidues form a coset of residues, hence product of two nonresidues is a residue; this is correct for an index-2 subgroup. - Lemma 436.2: Standard cyclic-group calculation; no hidden assumptions. - Small primes: For $p=3$ and $p=5$, there is no pair of consecutive nonzero quadratic residues, consistent with the computation reporting "missing runs".

FINAL

UNRESOLVED

(i) Strongest proved partial result: (a) For all primes $p\ge 7$, $r(2,2,p)\le 9$ (Lemma 436.1), giving an elementary upper bound consistent with $\Lambda(2,2)=9$ stated in the problem text. (b) For general $k$, the number of nonzero $k$th power residues modulo $p$ equals $(p-1)/\gcd(k,p-1)$ (Lemma 436.2).

(ii) First gap (crisp): Prove or disprove that $\Lambda(k,3)<\infty$ for all odd $k\ge 5$ (equivalently: is there a uniform bound $B(k)$ such that for all sufficiently large primes $p$ there is a run of three consecutive nonzero $k$th powers among $\{1,2,\dots,B(k)\}$?).

(iii) Top 3 next moves: 1. Computation: for fixed odd $k\ge 5$, compute $r(k,3,p)$ for primes up to much larger bounds to look for growth or apparent boundedness; identify candidate worst primes. 2. Analytic step: attempt to bound the number of solutions to $x^k\equiv n\pmod p$ in short intervals uniformly in $n$ using character sums (this is the natural bridge to the known results cited in the problem statement). 3. Structural step: relate $k$th power residues to multiplicative subgroups and study additive patterns (runs of consecutive integers) inside multiplicative subgroups.

(iv) What a minimal counterexample would likely look like: for some fixed odd $k\ge 5$, an infinite sequence of primes $p_j\to\infty$ such that for each $p_j$ every triple of consecutive integers $\{r,r+1,r+2\}$ with $1\le r\le B$ contains at least one non-$k$th-power residue, for all candidate bounds $B$; in other words, $r(k,3,p_j)\to\infty$.