Fabian Arevalo

Research note · Computational number theory

The first upper bound for Λ(8,2)

An exhaustive case tree over the eighth-power characters of the primes below 300 closes the open side of Erdős problem 436 at k = 8: 1,200,744 ≤ Λ(8,2) ≤ 1,508,324.
September 2, 2026 · produced in a Claude Code research session (AI-assisted, disclosed) · code, data & logs in the companion repository.

Start here: no maths required

Pick a prime number p and go through the numbers 1, 2, 3, … asking of each one: is it a perfect eighth power, once you are allowed to wrap around at p? Some are and some are not, and which is which depends on p in a way that looks random. Now look for the first time that two numbers in a row both pass the test. How far do you have to go?

For most primes, not far at all. But some primes are awkward, and the question is how awkward a prime can be. Write Λ for the worst case: the furthest you are ever forced to go, for infinitely many primes. The Lehmers, working with John Brillhart in 1964 on one of the last machines you had to book time on, computed this worst case when you ask about squares, cubes, fourth powers, and so on up to seventh powers. For eighth powers their method broke down, for a specific and slightly annoying reason: when p leaves remainder 1 on division by 8, the number 2 is automatically a square, and that single forced fact wrecked the bookkeeping their general theorem relied on. They left a lower bound, 1,200,744, and nothing above it. That is where it stayed for sixty-two years.

This note supplies the missing upper bound: 1,508,324. So the worst case for eighth powers is somewhere between 1,200,744 and 1,508,324, and it is no longer merely known to be finite.

The method is the Lehmers’, run on hardware they would have found absurd. You cannot check every prime, because there are infinitely many. What you can do is notice that the answer only depends on a finite amount of information about p: for each small prime q, which of eight possible “types” q has. That gives finitely many cases. Enumerate them all, and for each one produce a specific pair of consecutive numbers that works. If every case gets a pair, and no pair is bigger than 1,508,324, you are done, for every prime at once. The figure below is that enumeration finishing.

The proof, as a measurement: every marker is one completed run recorded in a committed log, not a fitted curve. Horizontal axis is L, the largest pair the search is allowed to use. Hollow crosses on the baseline are runs that failed, leaving 108 cases with no witness; filled squares are runs that settled everything, plotted at U, the largest pair they actually needed, which is the bound that run proves. Two things are visible. The failures stop and the successes start at exactly L = 1,508,324, so that is the smallest bound this prime set can certify. And above the threshold the curve rises: given a longer leash the search settles on larger pairs and proves a worse bound, which is why the certified number is the minimum of U rather than the value at any convenient L. The 16 runs plotted are every k = 8 run over the primes below 300 that has a committed log; the wider sweep rows quoted in section 5 come from the session note without a separate log and are marked there.

What this note adds

  1. The first upper bound at k = 8: Λ(8,2) ≤ 1,508,324. Brillhart and the Lehmers had only the lower bound 1,200,744 and an explicit note that their theorem did not cover this case. The bound here is unconditional and comes with a checkable certificate: 3,499,913 cases, each with a named pair of consecutive numbers that settles it.
  2. An independent checker, and it was run. The program that builds the enumeration and the program that verifies it were written separately; the verifier re-reads the whole certificate and confirms that the cases really do cover every possibility and that every witness really works. Two minutes, and it passes.
  3. The old values reproduced. The same programs re-derive the Lehmers’ answers for squares through seventh powers exactly: 9, 77, 1224, 7888, 202124, 1649375. Each is also sharp, in the sense that stopping one short leaves cases unsettled, so the machinery is not merely getting lucky.
  4. An honest gap. The exact value is still unknown, and it is between 1,200,744 and 1,508,324. Several attempts to push the lower bound up all failed, and they are written down in section 6 rather than left out.

Everything below is the technical version. The one figure to look at is the one above: it is the whole argument.

AbstractSummary of results

Let Λ(k,2) be the limit superior over primes p of the least r such that r and r + 1 are both k-th power residues modulo p. Brillhart, Lehmer and Lehmer [BLL] determined Λ(k,2) for k ≤ 7 by a machine case analysis and gave only Λ(8,2) ≥ 1,200,744. We complete the case analysis for k = 8, obtaining 1,200,744 ≤ Λ(8,2) ≤ 1,508,324. The upper bound is unconditional and CERTIFIED: an exhaustive decision tree over the eighth-power characters of the primes below 300, with the parity constraint on 2 and one child per orbit of the unit group, has 3,499,913 leaves, each settled by a pair of consecutive 293-smooth eighth-power residues (n, n+1) with n ≤ 1,508,324; an independent checker verifies exhaustiveness and every leaf. A first certificate using only the primes up to 113 gives 1,794,897. The lower bound is BLL’s, re-verified here by an exact sieve. The exact value remains open.

Section 1The setting, and why k = 8 was left out

For a prime p ≡ 1 (mod k) fix a character χ of order k on (Z/p)* and write R(q) ∈ Z/k for the index with χ(q) = ζR(q). An integer n = Π qeq prime to p is a k-th power residue iff Σ eqR(q) ≡ 0 (mod k). Hence, for primes p larger than every prime factor of n(n+1), whether (n, n+1) is a pair of consecutive residues depends only on the case vector (R(q))q on the primes dividing n(n+1). Changing the generator of the character group replaces R by uR for a unit u ∈ (Z/k)*, which does not change residue status; that is the symmetry the tree quotients by.

This is what makes the problem finite. There are infinitely many primes, but only finitely many case vectors on a fixed finite set of small primes, and the case vector is all that matters.

The k = 8 obstruction

For k = 8 and p ≡ 1 (mod 8), the number 2 is a quadratic residue, so χ(2)4 = 1 and R(2) is even. This is precisely the constraint that made BLL’s general theorem inapplicable. Their §8 says so in as many words: since 2 is a quadratic residue of p = 8m+1, they cannot choose R(2) = 1.

The fix is not deep, it is bookkeeping: carry the constraint R(2) ∈ {0, 2, 4, 6} through the enumeration explicitly instead of relying on a theorem that assumes it away. What was missing in 1964 was not the idea but the machine time to run the resulting tree, which has three and a half million leaves rather than the roughly one million BLL managed at k = 7.

For primes p ≢ 1 (mod 8) the eighth-power residues are the d-th power residues with d = gcd(8, p−1) ∈ {2, 4}, so r(8,2,p) = r(d,2,p) ≤ max(Λ(2,2), Λ(4,2)) + o(1) = 1224 for large p. The limit superior is therefore governed entirely by p ≡ 1 (mod 8), and 1224 is far below the bound in question, so those primes never bind.

Section 2The case tree

Fix a finite set S of primes and a bound L. A trial pair is (n, n+1) with n ≤ L and both members S-smooth; all consecutive such pairs are computed by smoothpairs.py. A node of the tree is a partial assignment A of values in Z/8 to some primes of S, with A(2) even. A trial pair is settled at A if all primes of n(n+1) are assigned and both residue sums vanish; dead if some member can never become a residue under any extension, the achievable sums forming the subgroup generated by gcd(eq·sq, 8) over the unassigned primes with s2 = 2 and sq = 1 otherwise; and open otherwise.

At a node, the least open admitted pair is branched on: its smallest unassigned prime q receives one child per orbit of the allowed values under the current stabiliser H ≤ (Z/8)*, the units fixing all earlier decisions; the child’s stabiliser is the stabiliser of its value in H. A settled pair closes the leaf with value n. If no admitted pair is open, the next prime of S is admitted, which is BLL’s “dimension window”. If all primes are admitted and nothing is settled, the leaf is unsettled, and the run has failed at that L.

Lemma 2.1 · exhaustiveness · PROVED

Let R be any assignment of Z/8 to the primes of S with R(2) even. Then there is a leaf ℓ and a unit u such that uR extends the assignment of ℓ.

Proof. Walk down from the root. At a node with branching prime q and stabiliser H, the current, already transformed assignment R′ agrees with the node on all decided primes; R′(q) lies in the orbit under H of some child value v, say R′(q) = u·v with u ∈ H; replace R′ by u−1R′, which fixes all decided values because u ∈ H, and sends R′(q) to v. Continue into the child v. □

Proposition 2.2 · PROVED

If every leaf is settled, then for every prime p ≡ 1 (mod 8) larger than every prime of S, r(8,2,p) ≤ U := maxℓ nℓ. Consequently Λ(8,2) ≤ U.

Proof. Apply Lemma 2.1 to the character indices of p; the leaf’s pair (nℓ, nℓ+1) consists of S-smooth numbers, all of whose primes are assigned at the leaf, and both residue sums vanish for uR, hence for R. As p exceeds every prime of S, p does not divide nℓ(nℓ+1). Together with section 1 for p ≢ 1 (mod 8) this gives the limit superior. □

Two features of this argument are worth stating explicitly, because they are what make the certificate cheap to trust. Nothing in the upper bound requires the trial-pair list to be complete, the tree to be minimal, or any case vector to be realisable by an actual prime. A missing trial pair or a redundant branch can only make the bound worse, never wrong. All the verifier has to establish is that the children cover every allowed value at each branch, and that each leaf’s named pair really works. That is a local, mechanical check.

Section 3The certificate and the checker

tree2 writes one line per leaf, q₁=v₁ q₂=v₂ … | n, giving the decisions in order, with n = −1 if unsettled, in depth-first order. check_tree2.py, 69 lines of exact integer arithmetic, re-reads the pairs file and verifies three things:

  1. at every internal node the children’s values, expanded by the node’s stabiliser, cover all allowed values of the branching prime, with the stabiliser recomputed by the checker from the decisions rather than trusted from the generator;
  2. every leaf’s n is at most L, occurs in the pairs list, and both members are residues under the leaf’s own assignment with all their primes assigned, exponents reduced mod 8;
  3. no leaf is unsettled.

Given these and a correct pairs file, Proposition 2.2 applies. The session’s audit added audit_pairs.py, which verifies every line of the pairs files independently, checking that the product of the listed factors really is n, that the next product really is n + 1, and that every base is prime; it re-ran the checker and regenerated all the controls of section 4.

Pair
What a leaf actually contains, factorised live in your browser by trial division rather than quoted from the note. Each bar is one prime factor, positioned by the prime and labelled with its exponent; the dashed line is the smoothness bound 300, and every factor has to fall left of it or the pair is unusable. The upper pair is the one that closes the certificate: 1,508,324 and 1,508,325 are consecutive, both 113-smooth, and together they settle the last 108 cases. The lower pair is the Lehmers’ 1964 lower-bound witness, shown for comparison; it is 109-smooth, and the gap between the two numbers is exactly the gap between the bounds this note leaves open.

The certificates themselves are not in the repository. At 20.97 MB and 19.5 MB gzipped they are above the repository’s commit threshold, so what is committed is the SHA-256 of each, the exact command that produces it, and the run and check logs. Regeneration takes about a minute, and re-checking about two:

artifactsizeSHA-256status
cert_k8_P300_L1508324.gz20,970,402 B9c6ddb3d0f3d62097bcac873cb5109f149849ad1d9f4a2d72ea56ba54623eb8bregenerate, ~1 min
cert_k8_P113_L1800000.gz19,527,067 B820efd1c4da9802bfbca0966ede43a354783b9eb06c4babb29c0be32aa4d1ce5regenerate, ~1 min

This is a real difference from a certificate you can download and check without running anything, and it is the reason the hashes and the exact invocations are recorded rather than just the verdict. The committed logs data/cert_P300.log and data/check_k8.log record the runs that produced and checked them.

Section 4Controls: reproducing k = 2 through 7

The programs are only worth trusting at k = 8 if they give the right answer where the answer is known. They do, for every k the Lehmers settled, and they are sharp: stopping one below the true value always leaves cases unsettled.

kΛ(k,2) [BLL, LLM]tree at L = Λat L = Λ − 1
294 leaves, none unsettled1 unsettled
37718 leaves, none unsettled1,536 unsettled
41,224232 leaves, none unsettled1,235,808 unsettled
57,8885,882 leaves, none unsettled (LLM: 4,568 cases)63 unsettled
6202,12419,075 leaves, none unsettlednot separately logged
71,649,3751,379,438 leaves, none unsettled, 2 s (BLL: ≈1.18 M cases plus hand cases)587 unsettled
8≤ 1,508,324 this note3,499,913 leaves, none unsettled108 unsettled

The gap counts at L = Λ − 1 depend on the pair list and the window policy, so only their positivity is meaningful; the leaf counts at L = Λ are exact for the stated prime set. Beyond the values themselves, BLL’s Table II vectors sieved exactly give least pairs 7888, 202124 and 1649375, matching; the k = 7 window profile, with leaves peaking at window 10 to 11, matches BLL’s Table III; a complete backjumping search at k = 5 from R(2) = 1 finds 7888 and proves 7889 unreachable; and the consecutive-smooth-pair counts reproduce OEIS A002071, 869 pairs for the first 13 primes.

Hover or tap a value to read it exactly.
Where k = 8 sits: the first entry that is still an interval rather than a point. Λ(k,2) against k on a log scale. The filled squares for k = 2 to 7 are the Lehmers’ values, each reproduced by the programs behind this note. At k = 8 the vertical bar is the bracket, from BLL’s 1964 lower bound 1,200,744 to the upper bound 1,508,324 established here; before this note the bar had no top. The growth is fast and irregular: the steps are ×8.6, ×15.9, ×6.4, ×25.6 and ×8.2, averaging about elevenfold but ranging from sixfold to twenty-sixfold, so no extrapolation would have told anyone where the k = 8 value sits. Against that spread the bracket left here is narrow, a factor of 1.256, but it is narrow because the search closed early rather than because the value was predictable.

Section 5Results at k = 8

Two prime sets were run. With S = {p ≤ 113}, that is 30 primes, with R(2) ∈ {0,2,4,6} and pairs from data/pairs_P113_L10000000.txt:

LleavesunsettledUcommitted log
1,300,0003,517,028734—note only
1,500,0003,468,728539—note only
1,700,0003,331,150254—note only
1,800,0003,270,93601,794,897audit.log
2,000,0003,225,97501,992,535note only
10,000,0002,528,32709,927,575k8_cert.log

The rows marked “note only” are reported in the session note but have no separate committed run log; they are intermediate probes of the sweep, and nothing in the theorem depends on them. The two logged rows are the ones that matter: the run that first settles everything, and the far-out check at 107.

With S = {p < 300}, that is 62 primes, from data/pairs_P300_L10000000.txt with 78,834 pairs to 107, all audited, the tree settles earlier because the extra primes admit more trial pairs:

LleavesunsettledUcommitted log
1,200,7444,651,99418,432 (362 leaves settle exactly at BLL’s pair)—note only
1,300,0004,189,19611,128—note only
1,502,0003,520,857108—bisect
1,505,0003,520,752108—bisect
1,508,0003,520,206108—bisect
1,508,3233,520,206108—cert_P300
1,508,3243,499,91301,508,324 (244 leaves)cert_P300
1,510,0003,499,91301,508,324bisect
1,512,5003,486,79501,510,784bisect
1,600,0003,440,70001,594,175tight
1,700,0003,343,40001,697,311tight

Rows marked with a chip are read from data/sweepP300_bisect.log, data/sweepP300_tight.log or data/cert_P300.log; the two “note only” rows are reported in the session note without a committed log. The session note lists the third row as L = 1,500,000; the committed bisection log records that run at L = 1,502,000, and the logged value is what is shown here. Four further settled runs between 1,525,000 and 1,575,000 are in the log and plotted in the figure above; they are omitted from the table only to keep it short.

Theorem · CERTIFIED · unconditional

Λ(8,2) ≤ 1,508,324. The certificate at L = 1,508,324 has 3,499,913 leaves and no unsettled leaf, and passes check_tree2.py in 2 m 0 s. The settling pair of its 244 extreme leaves is 1,508,324 = 2²·47·71·113 and 1,508,325 = 3·5²·7·13²·17. The 108 case vectors unsettled at L = 1,508,323 are all settled by this one pair.

The number 1,508,324 is what the primes below 300 give. It is an upper bound on Λ(8,2), not an estimate of it, and there is no reason to think it is tight: a larger prime set may well settle the last 108 vectors earlier, which would lower the certified bound without changing the true value at all. The 113-smooth run reaching only 1,794,897 is the direct evidence that the number moves with the prime set.

Section 6The lower bound, and the attempts to raise it that failed

BLL’s Table V vector, committed as data/tableII_k8.txt, has least pair exactly 1,200,744 by an exact sieve over all smaller n: 1,200,744 = 2³·3⁴·17·109 and 1,200,745 = 5·7²·13²·29. So Λ(8,2) ≥ 1,200,744, provided the vector is realised by infinitely many primes. That is Mills’ theorem of 1963, whose condition for k = 8 is exactly that R(2) be even, invoked here in the same way BLL invoke it. This session did not re-read Mills; the lower bound is conditional on that citation in a way the upper bound is not conditional on anything.

Every attempt to beat the vector failed. All are NUMERICAL and negative, and they are listed because a reader deciding whether the gap is worth attacking should know what has already been tried:

So the honest statement of the outcome is: the upper end of the bracket moved from infinity to 1,508,324, and the lower end did not move at all.

Section 7What is and is not shown

Section 8Open questions

  1. The exact value. The 108 case vectors unsettled at L = 1,508,323 are the natural cubes for the next attack. A complete extension search over the primes below 1.5 M on each either produces a witness above 1.5 M, raising the lower bound, conditional on Mills, or certifies that nothing does.
  2. A larger prime set. The bound is a function of S, and S < 300 was chosen for run time rather than for any structural reason. Running S < 1000 would very likely lower 1,508,324, and the amount it lowers by is itself informative about how far the bound is from the truth.
  3. k = 9 and 10. The same machinery applies. BLL record Λ(9,2) > 107 and Λ(10,2) ≥ 22,458,303, both without upper bounds; the trees are larger but not obviously out of reach, and the k = 10 case carries a parity constraint on 2 of the same kind as k = 8.