Skip to content

Erdős Problem #436

Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: number theory.

Read this status correctly

The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.

The question in plain language

For a prime \(p\) and positive integers \(k,m\geq2\), let \(r(k,m,p)\) be the smallest positive integer \(r\) such that the consecutive integers \(r,r+1,\ldots,r+m-1\) are all nonzero residues that are powers of degree \(k\) modulo \(p\). The Erdős–Graham question of Lehmer and Lehmer concerns the eventual limsup \(\Lambda(k,m)=\limsup_{p\to\infty}r(k,m,p)\). Does every fixed \(k\) admit a bounded first pair, that is, finite \(\Lambda(k,2)\)? Is the same true of three consecutive residues for all odd \(k\)? The two questions are separate. For an individual small prime, a suitable run may not exist at all; the limsup question concerns sufficiently large primes, with bounds depending on \(k\) rather than a bound uniform in \(k\).

A small example

For quadratic residues modulo \(11\), the nonzero squares are \(\{1,3,4,5,9\}\). They contain the consecutive pair \(3,4\) and also \(4,5\); thus \(r(2,2,11)=3\). By contrast, none of the two-element blocks \(1,2\) or \(2,3\) consists entirely of squares, so the least start is genuinely \(3\). This exact finite computation can be verified by squaring \(1\) through \(10\) modulo \(11\). It does not determine a limsup over all primes. A single prime with a small first run gives an upper bound at that prime only. One must take account of \(k\) th-power residue classes and, when \(\gcd(k,p-1)>1\), the size of the subgroup of nonzero powers of degree \(k\).

What is known

Lehmer and Lehmer originally raised these questions in 1962 and Erdős–Graham recorded them in Old and New Problems and Results in Combinatorial Number Theory (1980). They noted \(\Lambda(2,2)=9\). Later computations and proofs gave \(\Lambda(3,2)=77\) (Dunton), \(\Lambda(4,2)=1224\) (Bierstedt–Mills), \(\Lambda(5,2)=7888\) and \(\Lambda(6,2)=202124\) (Lehmer–Lehmer–Mills), and \(\Lambda(7,2)=1649375\) (Brillhart–Lehmer–Lehmer). These are specific fixed-exponent theorems, not a universal formula in \(k\). Hildebrand proved in 1991 that \(\Lambda(k,2)<\infty\) for every \(k\geq2\), resolving the first qualitative question. Graham proved \(\Lambda(k,m)=\infty\) when \(m\geq4\), and earlier work shows infinite limsup for triples when \(k\) is even. The important surviving question is finite \(\Lambda(k,3)\) for odd \(k\geq5\), together with quantitative growth in \(k\). The maintained Problem #436, last edited October 25, 2025, describes precisely this split between solved and open portions.

An elementary proof of the first-pair bound. For each prime \(p\geq7\), the numbers \(1\), \(4\), and \(9\) are nonzero quadratic residues. If \(2\) is a quadratic residue, the pair \(1,2\) works. Otherwise, if \(5\) is a quadratic residue, the pair \(4,5\) works. If both \(2\) and \(5\) are nonresidues, their product \(10\) is a residue because the product of two nonsquare classes is a square class; hence \(9,10\) works. Thus \(r(2,2,p)\leq9\) for all primes \(p\geq7\). The finitely many excluded small primes do not affect the limit superior.

The bound is attained at \(p=43\): \(9\equiv3^2\) and \(10\equiv15^2\pmod{43}\), and no earlier adjacent pair of nonzero squares occurs. That one-prime example does not establish the infinite-prime lower bound required for \(\Lambda(2,2)=9\), which is a result already attributed to Lehmer and Lehmer. Neither the argument nor the example settles the open odd-exponent triple-residue question.

A useful structural test is to let \(g\) be a primitive root modulo \(p\). The nonzero powers of degree \(k\) form a subgroup of the multiplicative group \(\mathbb F_p^\times\) with index \(\gcd(k,p-1)\). Thus one may test whether \(r\) lies in this subgroup by reducing discrete-log exponents modulo the index, or, without computing discrete logarithms, by checking \(r^{(p-1)/\gcd(k,p-1)}\equiv1\pmod p\). The latter criterion holds for any nonzero residue and is convenient for independent cross-validation. It also shows why a prime with \(\gcd(k,p-1)=1\) is exceptional: every nonzero residue is already a power of degree \(k\), so the first run is trivially available. The hard primes are those where \(k\) shares factors with \(p-1\).

Moreover, the assertion that \(\Lambda(k,3)\) is infinite for even \(k\) is qualitatively different from Graham's universal length-four obstruction. The surviving odd-exponent triple problem is not resolved by either result. An article that omitted these distinctions would misstate the current literature even if all its small numerical examples were correct.

GCL's current state

The original GCL issue #1706 maps this article to Erdős #436 and freezes the teorth catalogue at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml blob 4e60263a80af6207aca494d2e1388e44fa372889. The frozen label is OPEN and accurately describes the surviving odd-triple question. The original issue records no #436 statement file in the admitted FormalConjectures revision 85f863718beeec7b58a3a1926ee92e3472bc2020. The absence of a pinned formalization neither undermines Hildebrand's theorem nor certifies any new resolution. The authenticated source audit is linked at https://github.com/grandchallenge/MATH-PROGRAMME/issues/1706#issuecomment-6158367859; it is documentary evidence rather than accepted mathematical certification.

What remains

A bounded experiment should fix \(2\leq k\leq7\) and enumerate sufficiently many primes, computing the exact subgroup of residues that are powers of degree \(k\) and the least consecutive blocks of lengths two, three and four. Compare the first-run maxima observed with the historical exact values, stating that finitely many primes cannot prove a global limsup. Separately read Hildebrand's theorem with its quantifiers and its dependency on the fixed exponent, and prepare a critical source table of the odd \(k\) triple cases. Acceptance requires an independent residue enumerator, exact small-prime certificates, and correct attribution of each proved and open regime. The test fails if zero residues are counted as nonzero, if a finite maximum is called a limsup, or if Hildebrand's pair theorem is silently promoted to triples. Stop at this bounded source-and-computation interface.

Sources and claim boundaries

Original mathematical question: Lehmer–Lehmer (1962) and Erdős–Graham (1980). Maintained research statement and bibliography: Erdős Problem #436. Published context: Hildebrand (1991), Graham (1964), and earlier Lehmer, Dunton, Bierstedt–Mills results, as catalogued on the maintained page. Frozen custody: GCL #1706, teorth catalogue, and authenticated RESULT/1. The small residue calculation is independently exact; the general bounds are attributed external mathematics. No formal replay, novel theorem or editorial admission is asserted.

Catalogue and evidence provenance

  • Pinned catalogue source: teorth/erdosproblems at 536408716724.
  • GCL issue: #1706 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
  • GCL triage: STATEMENT_CAPTURE_REQUIRED.
  • Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
  • External mathematical status: consult current problem page and its dated bibliography.

Back to catalogue · Compendium introduction