Erdős problem 436 — wave9j

Date: 2026-07-28 UTC

Result

I obtained the explicit completely multiplicative coloring

A from-scratch exhaustive sieve verifies that the first \(n\geq 1\) for which

is

Mills' preassigned-character theorem therefore gives infinitely many primes \(p\) for which

Consequently

The same argument gives this lower bound for every odd \(k\) divisible by \(5\). This is not a proof of finiteness or infinitude. [b+d]

Claim labels used below:

• [a]: elementary-rigorous, including directly checked source metadata;
• [b]: rigorous modulo an explicitly named theorem;
• [c]: plausible/structural but unverified;
• [d]: computational-only (with reproducible exhaustive code).

Step 0: live-page check (performed before mathematics)

I fetched the rendered live page through the Bright Data browser path: problem 436, LaTeX view, and discussion thread. The page was last edited 25 October 2025. It displayed OPEN, 0 claimed proofs, Currently working on this problem: None, Interested in collaborating: None, and no solved or falsified marker. Dogmachine had marked only “This problem looks difficult.” Thus the mandatory stop rule did not fire. `[a: directly observed on the rendered live page]`

Verbatim live statement

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?

This is copied from the live LaTeX view, not reconstructed from the stale tracker metadata. [a: direct transcription]

Results and annotations listed on the live page

The page lists the following ground truth.

• \(\Lambda(2,2)=9\), \(\Lambda(3,2)=77\), and

\(\Lambda(4,2)=1224\). [a: live-page source report]

• Lehmer and Lehmer proved \(\Lambda(k,3)=\infty\) for even \(k\) and

\(\Lambda(k,4)=\infty\) for \(k\leq 1048909\). `[a: live-page source report]`

• \(\Lambda(5,2)=7888\), \(\Lambda(6,2)=202124\), and

\(\Lambda(7,2)=1649375\). [a: live-page source report]

• Lehmer, Lehmer, Mills, and Selfridge proved

\(\Lambda(3,3)=23532\). [a: live-page source report]

• Graham proved \(\Lambda(k,\ell)=\infty\) for all \(k\geq2\) and

\(\ell\geq4\). [a: live-page source report]

• Hildebrand proved \(\Lambda(k,2)<\infty\) for every \(k\). `[a:

live-page source report]`

• The page identifies the remaining questions as finiteness of

\(\Lambda(k,3)\) for odd \(k\geq5\), and growth of the finite pair and (where finite) triple quantities as functions of \(k\). `[a: live-page source report]`

I also read all three comments. Adenwalla's 24 October 2025 comment points to the 1962 “Machine Proof” paper for the cubic value \(23532\), with a note that the site was updated. Thomas Bloom's 25 October reply discusses the paper's historical remarks about machine proofs. Adenwalla's second comment links a page collecting residue papers. None is a claimed new proof or a current-worker marker. [a: directly observed]

Primary-source literature audit

The following named items were opened and checked rather than inferred from titles.

1. D. H. Lehmer and Emma Lehmer,

“On Runs of Residues”, Proc. AMS 13 (1962), 102–106. It defines the same limsup problem, proves the even-\(k\) obstruction in the cases stated there, and on pp. 103–104 states the Kummer preassignment lemma for odd prime \(k\). [a: primary source checked]

1. W. H. Mills,

“Characters with Preassigned Values”, Canadian J. Math. 15 (1963), 169–171, DOI 10.4153/CJM-1963-019-3. Theorem 3 says that when \(k\) is odd, arbitrary prescribed \(k\)th roots of unity at finitely many distinct rational primes occur as the values of a \(k\)th-power character for infinitely many rational primes \(p\). This is the named theorem used below. `[a: primary source checked]`

1. D. H. Lehmer, E. Lehmer, W. H. Mills, and J. L. Selfridge,

“Machine Proof of a Theorem on Cubic Residues”, Math. Comp. 16 (1962), 407–415. Theorem 1(b,c) explicitly gives \((23532,23533,23534)\) as the sharp first cubic-residue triplet for infinitely many primes. [a: primary source checked]

1. R. L. Graham,

“On Quadruples of Consecutive \(k\)th Power Residues”, Proc. AMS 15 (1964), 196–197. It proves \(\Lambda(k,4)=\infty\) using preassigned character values. `[a: primary source checked]`

1. A. Hildebrand,

“On Consecutive \(k\)th Power Residues. II”, Michigan Math. J. 38 (1991), 241–253, DOI 10.1307/mmj/1029004331. Its bibliographic record and the later paper below verify the all-\(k\) pair theorem attributed to it. `[a: primary bibliographic source plus explicit later restatement]`

1. Carsten Dietzel,

“On a theorem of Hildebrand”, Moscow J. Comb. Number Theory 8 (2019), 189–191, DOI 10.2140/moscow.2019.8.189. Theorem 5 strengthens the pair result: for every finite-index multiplicative subgroup \(H\leq\mathbb Q^+\), \(H^*\cap(H^*-1)\) is an IP-set. Remark 8 then says explicitly that for odd \(|\mathbb Q^+/H|=k\), whether \(H^*\cap(H^*-1)\cap(H^*-2)\) must be nonempty was still open, with only \(k=3\) known. [a: primary source checked]

1. Dietzel's earlier

arXiv:1309.7506 exists and gives a combinatorial proof for the pair question; it does not assert the odd-\(k\) triple result. [a: primary source checked]

Exact-phrase searches for \(\Lambda(5,3)\), the three-shift subgroup intersection, and citations of Dietzel's 2019 formulation found no later primary paper resolving the triple problem or giving a numerical \(\Lambda(5,3)\) bound. This is an honest search miss, not a claim that unindexed literature cannot exist. `[c: literature coverage is necessarily incomplete]`

Exact reduction to a finite prime-labeling problem

Fix \(B\), and assign a label \(x_q\in\mathbb Z/5\mathbb Z\) to every prime \(q\leq B+2\). Define, for \(n\leq B+2\),

The finite constraint system \(C_B\) is

This formulation uses only prime factorization and is exact. [a]

Transfer lemma

If \(C_B\) has a solution, then there are infinitely many primes \(p\) for which \(r(5,3,p)>B\). [b: Mills' Theorem 3]

Proof: choose a primitive fifth root \(\zeta\) and prescribe \(\chi(q)=\zeta^{x_q}\) at every prime \(q\leq B+2\). Mills' theorem supplies infinitely many \(p\), and an onto fifth-power character \(\chi:\mathbb F_p^\times\to\mu_5\), with those values. Discard the finitely many \(p\leq B+2\). Complete multiplicativity gives \(\chi(n)=\zeta^{L_x(n)}\) throughout the tested interval. Since \(\mathbb F_p^\times\) is cyclic and \(p\equiv1\pmod5\), the kernel of an onto fifth-power character is exactly \((\mathbb F_p^\times)^5\): both it and the subgroup of fifth powers have index \(5\), and the latter lies in the former. Thus a tested integer is a fifth-power residue exactly when \(L_x(n)=0\), and \(C_B\) excludes all earlier triples. [a+b]

Conversely, if some \(C_B\) is unsatisfiable, then \(\Lambda(5,3)\leq B\). For \(p\equiv1\pmod5\), restrict a fifth-power character to the rational primes and apply unsatisfiability. For \(p\not\equiv1\pmod5\), exponentiation by \(5\) is an automorphism of \(\mathbb F_p^\times\), so \(r(5,3,p)=1\) apart from irrelevant tiny primes. [a]

Finally, if every \(C_B\) is satisfiable, compactness of \(\prod_q\mathbb Z/5\mathbb Z\) (equivalently, König's lemma applied to the finite assignment tree) gives one global labeling with no zero triple anywhere. The transfer lemma then implies \(\Lambda(5,3)=\infty\). Hence the open \(k=5\) question is exactly whether \(C_B\) is unsatisfiable for some finite \(B\). [a+b]

In subgroup language, the global labels define

and the missing assertion is precisely

for every cyclic quotient of order \(5\), the open case identified by Dietzel. [a: equivalence; a: source-verified open formulation]

Explicit coloring and verified lower bound

Take

Thus

This is a closed-form, globally defined completely multiplicative coloring. [a]

The exhaustive checker proves that its first zero triple starts at \(R=37\,329\,226\). [d] The endpoint arithmetic is

After ignoring \(2,5,7\), each line has exactly five prime factors with multiplicity, so all three colors are \(0\pmod5\). [a]

Prescribe \(\chi(2)=\chi(5)=\chi(7)=1\) and \(\chi(q)=\zeta_5\) for every other prime \(q\leq R+2\). Mills gives infinitely many primes \(p>R+2\) realizing these values. The exhaustive “no earlier triple” check and the displayed endpoint give

for all those \(p\), not merely \(r(5,3,p)\geq R\). Therefore \(\Lambda(5,3)\geq R\). [b+d]

More generally, if \(5\mid k\) and \(k\) is odd, then \(\zeta_5\in\mu_k\). Mills' odd-\(k\) theorem permits the same prescriptions for an onto \(k\)th-power character, so the identical proof gives

[b+d]

The short deterministic discovery path, also checked by the standalone script, was:

These rows are computational observations; no monotone continuation theorem is asserted. [d]

Independent verification

Standalone checker: erdos436_wave9j_verify.py. It uses only the Python standard library, constructs a smallest-prime-factor table from scratch, recomputes all four rows, scans every possible starting index, and independently factors the endpoint.

Command run:

/usr/bin/time -f 'max_rss_kb=%M elapsed=%e cpu=%P' \
  python runs/erdos436_wave9j_verify.py

Observed output:

PASS: all colors and first-zero-triple indices recomputed from scratch
  ignored=[]: first=15470, endpoint_colors=(0, 0, 0)
  ignored=[2]: first=1073149, endpoint_colors=(0, 0, 0)
  ignored=[2, 5]: first=3249531, endpoint_colors=(0, 0, 0)
  ignored=[2, 5, 7]: first=37329226, endpoint_colors=(0, 0, 0)
  endpoint_factorizations={37329226: [(2, 1), (11, 3), (37, 1), (379, 1)], 37329227: [(13, 4), (1307, 1)], 37329228: [(2, 2), (3, 3), (421, 1), (821, 1)]}
  primes_through_37329228=2280537, log10(5^prime_count)=1594026.956778
  spf_sieve_seconds=10.649
  total_seconds=28.260
CERTIFIED: c_{2,5,7} has no zero triple starting below 37329226, and has one starting exactly there.
max_rss_kb=193252 elapsed=28.29 cpu=99%

The SHA-256 digest of the checked script is 70a287d436cbe886e1a276dfcf8c3b75833a173c741da0fcbf0ec3f415c5fba0.

[a: execution record]

Complete verifier source

#!/usr/bin/env python3
"""From-scratch verification for the Erdős #436 wave9j lower bound.

For a finite set S of ignored primes, define

    c_S(n) = sum_{q prime, q not in S} v_q(n) (mod 5).

The script builds a smallest-prime-factor table from scratch and checks the
claimed first index at which c_S(n), c_S(n+1), c_S(n+2) are all zero.  The
last (and only theorem-relevant) row is S={2,5,7}.

No third-party packages or stored certificate/data files are used.

Expected resources on the exe.dev VM:
  about 45-60 seconds, one core, and about 190 MB peak working memory.
"""

from array import array
from math import isqrt, log10
from time import perf_counter


FINAL_FIRST = 37_329_226
PRIME_VARIABLES = 2_280_537
FINAL_FACTORS = {
    37_329_226: [(2, 1), (11, 3), (37, 1), (379, 1)],
    37_329_227: [(13, 4), (1307, 1)],
    37_329_228: [(2, 2), (3, 3), (421, 1), (821, 1)],
}

# The first three rows record the short deterministic discovery path.  The
# final row is the certificate used for the mathematical lower bound.
CASES = [
    (frozenset(), 15_470),
    (frozenset({2}), 1_073_149),
    (frozenset({2, 5}), 3_249_531),
    (frozenset({2, 5, 7}), FINAL_FIRST),
]


def smallest_prime_factors(limit: int) -> array:
    """Return spf[n], the smallest prime factor of n, for 0 <= n <= limit."""
    spf = array("I", range(limit + 1))
    if limit >= 1:
        spf[1] = 1
    for p in range(2, isqrt(limit) + 1):
        if spf[p] != p:
            continue
        for multiple in range(p * p, limit + 1, p):
            if spf[multiple] == multiple:
                spf[multiple] = p
    return spf


def factor_with_spf(n: int, spf: array) -> list[tuple[int, int]]:
    """Factor n using the independently constructed spf table."""
    factors: list[tuple[int, int]] = []
    while n > 1:
        p = int(spf[n])
        exponent = 0
        while n % p == 0:
            n //= p
            exponent += 1
        factors.append((p, exponent))
    return factors


def first_zero_triple(
    ignored: frozenset[int], expected: int, spf: array
) -> tuple[int, tuple[int, int, int]]:
    """Compute c_S from its definition and return its first zero triple."""
    # Only values through expected+2 are needed: finding a triple earlier
    # fails the assertion, while checking expected confirms the endpoint.
    colors = bytearray(expected + 3)
    for n in range(2, expected + 3):
        p = int(spf[n])
        colors[n] = (colors[n // p] + (0 if p in ignored else 1)) % 5

    first = None
    for n in range(1, expected + 1):
        if colors[n] == colors[n + 1] == colors[n + 2] == 0:
            first = n
            break
    assert first == expected, (
        f"ignored={sorted(ignored)}: expected first triple {expected}, "
        f"obtained {first}"
    )
    triple = (colors[first], colors[first + 1], colors[first + 2])
    return first, triple


def main() -> None:
    started = perf_counter()
    limit = FINAL_FIRST + 2
    spf = smallest_prime_factors(limit)
    sieve_seconds = perf_counter() - started
    prime_variables = sum(1 for n in range(2, limit + 1) if spf[n] == n)
    assert prime_variables == PRIME_VARIABLES
    log10_assignments = prime_variables * log10(5)
    assert 1_594_026.95 < log10_assignments < 1_594_026.97

    # Independent arithmetic check of the endpoint factorizations.
    obtained_factors = {
        n: factor_with_spf(n, spf) for n in range(FINAL_FIRST, FINAL_FIRST + 3)
    }
    assert obtained_factors == FINAL_FACTORS, (
        f"factorization mismatch: {obtained_factors!r}"
    )
    for n, factors in obtained_factors.items():
        reconstructed = 1
        for p, exponent in factors:
            reconstructed *= p**exponent
        assert reconstructed == n
        outside_count = sum(
            exponent for p, exponent in factors if p not in {2, 5, 7}
        )
        assert outside_count == 5

    results = []
    for ignored, expected in CASES:
        first, triple = first_zero_triple(ignored, expected, spf)
        results.append((sorted(ignored), first, triple))

    elapsed = perf_counter() - started
    print("PASS: all colors and first-zero-triple indices recomputed from scratch")
    for ignored, first, triple in results:
        print(f"  ignored={ignored}: first={first}, endpoint_colors={triple}")
    print(f"  endpoint_factorizations={obtained_factors}")
    print(
        f"  primes_through_{limit}={prime_variables}, "
        f"log10(5^prime_count)={log10_assignments:.6f}"
    )
    print(f"  spf_sieve_seconds={sieve_seconds:.3f}")
    print(f"  total_seconds={elapsed:.3f}")
    print(
        "CERTIFIED: c_{2,5,7} has no zero triple starting below "
        f"{FINAL_FIRST}, and has one starting exactly there."
    )


if __name__ == "__main__":
    main()

What remains and the exact wall

Dietzel's IP-set theorem supplies infinitely many \(a\) with \(a,a+1\in H\), but it gives no mechanism forcing one of those \(a\) also to satisfy \(a+2\in H\). The exact missing lemma is:

Every completely multiplicative \(f:\mathbb N\to\mu_5\) has some \(n\) with \(f(n)=f(n+1)=f(n+2)=1\).

By the compactness argument above, proving this qualitative statement would automatically give a finite uniform bound and settle \(\Lambda(5,3)<\infty\). Constructing one \(f\) avoiding such triples globally would instead prove \(\Lambda(5,3)=\infty\). The present coloring does neither, because it fails at the explicitly checked endpoint. [a+b]

At \(B=37\,329\,226\), there are \(2\,280\,537\) prime-label variables \(x_q\) with \(q\leq B+2\). Direct enumeration has

assignments. Even at an unrealistically optimistic \(10^9\) complete assignments per second per core, this is about \(2.5\times10^{1\,594\,014}\) core-hours. A structured SAT/CSP attack can exploit factorization and is the only plausible exact computation, but an upper bound would require a machine-checkable UNSAT certificate at some presently unknown \(B\); there is no defensible finite core-hour estimate without such a candidate. `[a: variable and enumeration counts; c: solver-cost diagnosis]`

Thus the verified deliverable is a large explicit lower bound and an exact finite-CSP reduction, not closure of the open problem.

PARTIAL: The Mills-realizable coloring \(c(n)=\sum_{q\notin\{2,5,7\}}v_q(n)\bmod5\) has first zero triple \(37,329,226\), proving \(\Lambda(5,3)\ge37,329,226\) (and the same for odd \(5\mid k\)); finiteness remains open.