Erdős problem #962 (wave 7x)

Access date: 2026-07-28 UTC.

Claim labels

• (a) elementary-rigorous: proved in this report from definitions.
• (b) rigorous-modulo-named-theorem: the elementary deduction is complete, but a specifically named published theorem is used.
• (c) plausible/structural-unverified: heuristic or a reduction with an unproved input.
• (d) computational-only: exhaustively checked in the stated finite range, with reproducible code, but not promoted to an asymptotic theorem.

Result

The main question remains open. The useful new observation is an apparently unrecorded connection with the Grimm function. It gives the following genuine improvement to the upper bound recorded on the live page.

Corollary (b). For all sufficiently large \(n\), \[ > k(n)<n^{0.46}=n^{1/2-1/25}. > \]

This follows from Theorem 1(i) of Laishram and Murty, Grimm's Conjecture and Smooth Numbers, Michigan Math. J. 61 (2012), 151--160, DOI 10.1307/mmj/1331222852. They prove \(g(m)<m^\alpha\) for some permissible \(0.45<\alpha<0.46\), where \(g(m)\) is the longest prefix \(m+1,\ldots,m+r\) admitting distinct representative prime divisors. Every block in problem #962 automatically has such distinct representatives. The full two-line reduction is proved below.

This settles the fixed-power saving which Erdős called a “ridiculously weak result” in 1976, but it does not approach \(\log k(n)\leq(\log n)^{1/2+o(1)}\). The new upper bound only says \(\log k(n)\leq 0.46\log n\).

The finite checker also independently certifies

Step 0: authoritative live page

The live page was fetched through the Bright Data browser path, including the linked discussion thread, rather than by datacenter curl.

Verbatim statement

Let \(k(n)\) be the maximal \(k\) such that there exists \(m\leq n\) such that each of the integers \[ > m+1,\ldots,m+k > \] are divisible by at least one prime \(>k\). Estimate \(k(n)\) - in particular, is it true that \[ > \log k(n) \leq (\log n)^{1/2+o(1)}? > \]

This is copied verbatim from the page's “View the LaTeX source” rendering.

Status, results, comments, and collision markers

The page displayed OPEN, last edited 03 April 2026. It displayed 0 claimed proofs and the following marker values:

Thus the mandatory stop condition did not trigger.

The page records the following mathematical results.

1. (b) Erdős [Er65] wrote that

\[ \log k(n)\geq(\log n)^{1/2-o(1)} \] and conjectured \(k(n)=o(n^\epsilon)\), but had no nontrivial upper bound.

1. (b) Erdős [Er76e] obtained

\[ \log k(n)\gg\sqrt{\log n\log\log n} \] and reported \[ k(n)\leq n^{1/2}\exp\!\bigl(-(\log n)^c\bigr) \] for some \(c>0\), while saying he could not prove \(k(n)\leq n^{1/2-c}\) for a fixed \(c>0\).

1. (b) Tao's comment, using the prime number theorem, proves

\(k(n)\leq(1+o(1))n^{1/2}\): if \(k>(1+\epsilon)\sqrt n\), a prime \(\sqrt n<p<(1+\epsilon)\sqrt n<k\) has a multiple in every interval of length \(k\), and that multiple has no prime factor exceeding \(k\).

1. (b) Tang's note proves

\[ \log k(n)\geq \left(\frac1{\sqrt2}-o(1)\right) \sqrt{\log n\log\log n}. \]

There were five comments, all read before beginning the mathematics:

• Terence Tao, 12 October 2025: the \( (1+o(1))\sqrt n\) upper-bound

argument just summarized.

• Terence Tao, 28 October 2025: “Some initial numerics,” linking

GitHub issue #145. That issue computes the least starting point for 400 values of \(k\).

• Quanyu Tang, 28 December 2025: announces and links the improved lower

bound above.

• Thomas Bloom, 03 April 2026: records the rediscovered 1976 Erdős bounds.
• Darin Dimitroff (deezel), 02 May 2026: proposes a fourth-moment

route which, if two level-of-distribution/bilinear estimates labelled L5 and L6 held, would give \(k(n)\ll n^{1/e+o(1)}\). (c) The commenter explicitly disclaims a theorem; L5 and L6 are unproved. The numerical normality, kurtosis, and variance observations in that comment are (d) and are not used here.

Primary-source audit and literature search

The following sources were opened and checked directly.

The source-audit mode of the checker downloads these exact PDFs and verifies their SHA-256 hashes, page counts, and extractable theorem phrases. The 1976 PDF is an image-only scan, so its page 273 was additionally inspected visually. The verified hashes are:

Er65   b2dc8978ca143027e8d5940211a71aaf69cde9f2d771499dad881d9fb27878ea
Er76e  5c7d95ca79a407de8b1f2f5ee01e7ad6acdf304cfc587752e213e3bdf57f04fb
LM12   01724c88d7ec1c40ee81745da7a19bc95f180424a4f2aacca37993cbb5d6e8ef
Tang   3db0419ffc8d8c1bb742bb4551e53c8a93207d5b6a60879ed60fd777a6b97327

Targeted searches for the exact problem text, “Erdős Problem 962” together with “Grimm,” the Grimm-function notation \(g(n)\), and all-interval smooth number results found no source that already states the reduction below and no primary source solving the main \(1/2+o(1)\) exponent question. This is a search report, not a claim of bibliographic completeness.

The most recent directly relevant paper found was Sarvagya Jain, Existence of Smooth Numbers in Short Intervals, Q. J. Math. 77 (2026), 397--422. (b) Its all-interval theorem requires an interval length at least

which is longer than \(\sqrt x\), and hence does not improve the present worst-case exponent. Its much shorter “almost all intervals” result cannot exclude the single exceptional interval needed to define \(k(n)\).

The Grimm reduction

For \(m>1\), Laishram and Murty say that \((m,r)\) has a prime representation when there are distinct primes

and define \(g(m)\) as the largest such \(r\).

Lemma

(a) If \(m+1,\ldots,m+k\) is admissible for problem #962, then

Proof. For each \(1\leq i\leq k\), choose a prime \(q_i>k\) dividing \(m+i\). If \(q_i=q_j=q\) for \(i<j\), then

But \(0<j-i\leq k-1<q\), a contradiction. Thus the \(q_i\) are distinct and give a prime representation of length \(k\). \(\square\)

Fixed power saving

(b) Laishram--Murty Theorem 1(i) says that there is a permissible \(\alpha\in(0.45,0.46)\) and an \(m_0\) such that

Let \(n\) be large and let an admissible pair \(m\leq n,k\) witness \(k(n)\). If \(m\geq m_0\), the lemma gives

If \(m<m_0\), the elementary observation \(k\leq m\) (proved in the finite-computation section) gives \(k<m_0\). Increasing the lower threshold for \(n\) absorbs this fixed bound as well. Taking the maximum over all \(m\leq n\) proves

for all sufficiently large \(n\).

The arithmetic \(0.46=1/2-1/25\) is checked exactly with rational arithmetic in the verifier. This is asymptotically stronger than Erdős's recorded \(n^{1/2}\exp(-(\log n)^c)=n^{1/2-o(1)}\) upper bound (its constant necessarily has \(0<c<1\), since the displayed right-hand side would tend to zero if \(c\geq1\)).

A density corollary

Laishram--Murty Theorem 1(ii) also gives, for fixed \(0<\epsilon<1/3\),

By the elementary lemma, (b)

This is a rarity statement and does not control the extremal exceptional starting point, so it does not by itself improve \(k(n)\).

Exact finite computation

Let \(P^+(t)\) be the largest prime factor of \(t\), with \(P^+(1)=1\), and define

Thus the least problem parameter is \(m=A(k)-1\), and (a)

Also \(A(k)\leq A(k+1)\): the first \(k\) terms of a qualifying \((k+1)\)-block qualify as a \(k\)-block. An admissible pair necessarily has \(m\geq k\), since \(m+1\) has a prime factor \(>k\); this also makes the maximum in (1) finite.

Two independent sieves agreed on every \(P^+(t)\) through \(1{,}583{,}000\):

1. overwrite every multiple of each prime, processing primes increasingly;
2. construct smallest prime factors with a linear sieve and use

\(P^+(t)=\max(\operatorname{spf}(t),P^+(t/\operatorname{spf}(t)))\).

For every \(1\leq k\leq122\), the checker then scans every earlier possible start before accepting \(A(k)\). Every accepted block is factored again by plain trial division, a third independent implementation. (d) The exact plateaux are:

In particular, \(A(121)=879499\leq10^6+1<A(122)=1582081\), and monotonicity gives the exact certificate \(k(10^6)=121\).

These values independently reproduce the initial portion of OEIS A327909; they are not claimed as a sequence extension. Their purpose here is an auditable small-case computation tied exactly to the problem's convention \(m=A(k)-1\).

Reproducible checker

Complete standalone code:

runs/erdos962_wave7x_reverify.py

Run the finite mathematical audit:

python3 runs/erdos962_wave7x_reverify.py

Run the finite audit plus fresh primary-source downloads:

python3 runs/erdos962_wave7x_reverify.py --check-sources

The core exhaustive computation is:

def first_starts(lpf, k_max):
    starts = [0] * (k_max + 1)
    for k in range(1, k_max + 1):
        run = 0
        for value in range(1, len(lpf)):
            if lpf[value] > k:
                run += 1
                if run == k:
                    starts[k] = value - k + 1
                    break
            else:
                run = 0
        if starts[k] == 0:
            raise RuntimeError("sieve limit too small")
    return starts

The complete script additionally:

• compares the two full LPF arrays byte for byte;
• trial-factors every integer in all 122 witness blocks;
• exhaustively checks the block-to-Grimm map for all

\(1\leq m\leq5000,\ 1\leq k\leq50\) (50,797 qualifying pairs);

• checks all reported landmarks and inverse values;
• checks \(1/2-0.46=1/25\) using fractions.Fraction;
• optionally verifies source hashes, page counts, and theorem phrases.

The final run completed in 10.2 seconds including downloads and printed ALL CHECKS PASSED. The two LPF tables through \(1{,}583{,}000\) had the common SHA-256

7ceac0dafba99cb8dbc94823ffc0ed2b2b3693231b4ded72d6c8b386b16746f1

Exact remaining wall

Define the following all-interval smoothness assertion for fixed \(\delta>0\):

(a) If \(\mathcal U_\delta(X)\) holds for every sufficiently large \(X\), then no admissible block can have length \(k\geq\exp((\log X)^{1/2+\delta})\), so

Proving this for every \(\delta>0\), with the needed uniformity, would give the requested upper bound.

This isolates the wall: existing worst-case theorems put smooth numbers in intervals whose length is a fixed power near \(x^{0.45}\), or at least \(x^{1/2+o(1)}\) in broader smoothness ranges. The target has both the interval length and the smoothness threshold equal to \(\exp((\log X)^{1/2+o(1)})\). Fixed-\(\epsilon\) “almost all interval” theorems do not have uniformity as \(\epsilon=\log y/\log X\to0\), and even a tiny exceptional set is insufficient for this extremal question. Dimitroff's proposed L5/L6 bilinear estimates are one possible intermediate route, but they are currently (c) and would only reach \(X^{1/e+o(1)}\), not the final subpolynomial scale.

PARTIAL: Via Laishram--Murty's published Grimm-function theorem, \(k(n)<n^{0.46}=n^{1/2-1/25}\) for all sufficiently large \(n\); the main \(\log k(n)\leq(\log n)^{1/2+o(1)}\) conjecture remains open, and the checker also certifies \(k(10^6)=121\).