Research note · Computational number theory
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.
Everything below is the technical version. The one figure to look at is the one above: it is the whole argument.
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.
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.
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.
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.
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. □
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.
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:
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.
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:
| artifact | size | SHA-256 | status |
|---|---|---|---|
| cert_k8_P300_L1508324.gz | 20,970,402 B | 9c6ddb3d0f3d62097bcac873cb5109f149849ad1d9f4a2d72ea56ba54623eb8b | regenerate, ~1 min |
| cert_k8_P113_L1800000.gz | 19,527,067 B | 820efd1c4da9802bfbca0966ede43a354783b9eb06c4babb29c0be32aa4d1ce5 | regenerate, ~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.
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 |
|---|---|---|---|
| 2 | 9 | 4 leaves, none unsettled | 1 unsettled |
| 3 | 77 | 18 leaves, none unsettled | 1,536 unsettled |
| 4 | 1,224 | 232 leaves, none unsettled | 1,235,808 unsettled |
| 5 | 7,888 | 5,882 leaves, none unsettled (LLM: 4,568 cases) | 63 unsettled |
| 6 | 202,124 | 19,075 leaves, none unsettled | not separately logged |
| 7 | 1,649,375 | 1,379,438 leaves, none unsettled, 2 s (BLL: ≈1.18 M cases plus hand cases) | 587 unsettled |
| 8 | ≤ 1,508,324 this note | 3,499,913 leaves, none unsettled | 108 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.
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:
| L | leaves | unsettled | U | committed log |
|---|---|---|---|---|
| 1,300,000 | 3,517,028 | 734 | — | note only |
| 1,500,000 | 3,468,728 | 539 | — | note only |
| 1,700,000 | 3,331,150 | 254 | — | note only |
| 1,800,000 | 3,270,936 | 0 | 1,794,897 | audit.log |
| 2,000,000 | 3,225,975 | 0 | 1,992,535 | note only |
| 10,000,000 | 2,528,327 | 0 | 9,927,575 | k8_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:
| L | leaves | unsettled | U | committed log |
|---|---|---|---|---|
| 1,200,744 | 4,651,994 | 18,432 (362 leaves settle exactly at BLL’s pair) | — | note only |
| 1,300,000 | 4,189,196 | 11,128 | — | note only |
| 1,502,000 | 3,520,857 | 108 | — | bisect |
| 1,505,000 | 3,520,752 | 108 | — | bisect |
| 1,508,000 | 3,520,206 | 108 | — | bisect |
| 1,508,323 | 3,520,206 | 108 | — | cert_P300 |
| 1,508,324 | 3,499,913 | 0 | 1,508,324 (244 leaves) | cert_P300 |
| 1,510,000 | 3,499,913 | 0 | 1,508,324 | bisect |
| 1,512,500 | 3,486,795 | 0 | 1,510,784 | bisect |
| 1,600,000 | 3,440,700 | 0 | 1,594,175 | tight |
| 1,700,000 | 3,343,400 | 0 | 1,697,311 | tight |
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.
Λ(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.
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.