Erdős problem #462 — live audit, balanced-semiprime reduction, and an exhaustive finite bound
Date: 2026-07-26 (UTC)
Result at a glance
The problem is still open. I found no claimed proof and no current worker on the
live page. The useful new output of this run is a computer-assisted finite
theorem for the stronger, composite-only reading:
\[ \boxed{\quad \sum_{\substack{x\le n\le x+\sqrt{x}(\log x)^2\\ n\ {\rm composite}}} \frac{p(n)}n>0.961 \quad\text{for every real }10^6\le x\le10^9. \quad} \]Only balanced semiprimes \(n=pq\), \(p\le q\le2p\), are used in this
lower bound. Thus primes and all other composites are discarded. The
verification is exhaustive, not sampled, and uses integer lower
approximations to \(1/q\), so no floating-point comparison enters the
certificate.
The standalone verifier is
Claim labels used below:
- (a) elementary-rigorous: proved here from elementary identities.
- (b) rigorous-modulo-named-theorem: the only non-elementary input is
explicitly named.
- (c) plausible/structural-unverified: heuristic or proposed analytic
route, not a theorem.
- (d) computational-only: finite exhaustive statement certified by the
supplied program.
0. Mandatory live-page check
I fetched the protected page through the Bright Data browser path, then fetched
the LaTeX endpoint and the discussion thread through the same path.
Verbatim live statement
> Let \(p(n)\) denote the least prime factor of \(n\). There is a constant
> \(c>0\) such that
> \[
> \sum_{\substack{n
> Is it true that there exists a constant \(C>0\) such that
> \[ > \sum_{x\leq n\leq x+Cx^{1/2}(\log x)^2}\frac{p(n)}{n} \gg 1 > \]
> for all large \(x\)?
Source: live problem page and its
LaTeX view, accessed 2026-07-26.
The cited source on the page is [ErGr80,p.92].
Live status and markers
- Status: OPEN.
- Comments: 1.
- Claimed proofs: 0.
- “Currently working on this problem”: None.
- “Interested in collaborating”: None.
- All other displayed reaction/interest markers: None.
The one comment, by TerenceTao on 2025-09-28, flags an ambiguity: the displayed
short sum does not exclude prime \(n\). On the literal reading, prime terms
connect the question to a weakening of Legendre's conjecture; on the
composite-only reading, the issue is the distribution of roughly balanced
semiprimes in intervals of the stated length. The comment is explicitly
unverified by the site.
Check of the original source
I also downloaded the scan on Ronald Graham's UCSD publication page:
[Erdős–Graham, *Old and New Problems and Results in Combinatorial Number
Theory* (1980)](https://mathweb.ucsd.edu/~ronspubs/80_11_number_theory.pdf).
Printed page 92 is PDF page 88. It writes the global sum with
\(n\ne\text{prime}\), but then asks for the short sum “where \(n\) ranges over
all integers” in the interval. Thus the literal live statement accurately
tracks the typography of the original. Whether the omission of the
composite restriction in the second sum was intentional is not resolved by
the scan.
Everything proved below uses only composite \(n\), so it applies to both
readings and avoids this ambiguity.
1. Literature audit
I searched the exact problem number, exact formula, “least prime factor” short
intervals, balanced/proportional semiprimes, and RSA-integers. I checked the
following primary sources rather than relying on search snippets.
1. The original source. Erdős and Graham, 1980, printed p. 92, linked
above. It states the question but gives no local result.
2. A directly targeted 2026 preprint. Zeraoulia Rafik,
*Toward Erdős–Graham Problem 462 (composite-only): exact rough-number and
semiprime decompositions, averaged progress, and quantitative necessary
conditions*, dated 2026-02-03, is self-uploaded as
ResearchGate publication 400404179.
I found no arXiv identifier or journal record for the exact title. The
preprint explicitly says that the target-scale, uniform-in-\(x\),
composite-only problem remains open. It records the constant \(8\) in the
global asymptotic, exact rough-number/semiprime decompositions, an averaged
consequence, conditional uniformity criteria, and computations at selected
\(x\le2\cdot10^7\). I independently rederived the elementary identities and
did not use its conditional claims as theorems.
3. Global balanced-semiprime counts.
Decker–Moree, arXiv:0801.1451,
Counting RSA-integers, proves for fixed \(r>1\)
\[
\#\{pq\le X:p Moree–Saad Eddin, arXiv:1606.07727 and Saad Eddin–Suzuki, arXiv:1908.09503 refine global distribution questions. These are cumulative asymptotics, not target-scale uniform short-interval estimates. For example, the explicit \(O(X/\log^3X)\) error in the fixed-\(r\) 2008 theorem is vastly larger than the expected \(\asymp\sqrt X\) number of balanced products in the interval relevant here, so differencing that theorem cannot answer #462. 4. Almost-primes in almost all very short intervals. Matomäki–Teräväinen, arXiv:2207.05038, Almost primes in almost all short intervals II, proves that almost all intervals \((x,x+(\log x)^{2.1}]\) contain a product of exactly two primes. This does not provide \(\gg\sqrt x\) balanced products in every interval, which is what the weight \(p(n)/n\) needs here. One possibly very unbalanced semiprime contributes far too little. 5. Current prime short-interval frontier. The current v2 of Guth–Maynard, arXiv:2405.20552, New large value estimates for Dirichlet polynomials, gives the prime number theorem in every interval of length \(y^{17/30+\epsilon}\), and an almost-all result at \(y^{2/15+\epsilon}\). The all-\(y\) and almost-all distinction is also made explicit in now published in Essential Number Theory 5 (2026), 221–241. At #462's balanced factor scale \(y=\sqrt x\), the individual prime intervals have only polylogarithmic length. Thus these theorems are not close enough to settle the target scale. Exact-title/problem-number searches found no other primary paper claiming to solve this specific problem. This is a search miss, not a proof that none exists. Claim (b). With primes excluded, The named input is the prime number theorem. If \(n\) has at least three prime factors, counted with multiplicity, then \(p(n)\le n^{1/3}\). Their total contribution is therefore For a semiprime \(n=pq\), write \(p\le q\). Its summand is \(p/(pq)=1/q\), and, up to immaterial endpoint conventions,
2. Two analytical facts checked from scratch
2.1 The global constant is \(8\)
Prime-number-theorem partial summation gives \(4\sqrt X/\log^2X\) from
each sum. Hence \(A_2(X)\sim8\sqrt X/\log^2X\), and the terms with at
least three prime factors are negligible. This also independently checks
the constant quoted in the 2026 preprint.
2.2 A sharp averaged consequence, but not uniformity
Claim (b). Fix \(C>0\), put
\(H_X=C\sqrt X(\log X)^2\), and let
\[ S_{\rm c}(t;H)= \sum_{\substack{tIndeed, every \(n\in(X+H_X,2X]\) is counted for exactly \(H_X\) values of
\(t\), so
\[ \int_X^{2X}S_{\rm c}(t;H_X)\,dt \ge H_X\bigl(A(2X)-A(X+H_X)\bigr). \]Insert the global asymptotic and use \(H_X=o(X)\). In particular, every
large dyadic block contains at least one good starting point. Since
\(H_X\le C\sqrt t(\log t)^2\) for \(t\in[X,2X]\), this produces arbitrarily
large good \(t\) at the live-page scale.
This argument supplies no information about a sparse set of bad \(t\), which
is exactly the quantifier in the question.
3. Exact semiprime reduction
Let \(S_2(x;H)\) be the contribution from semiprimes alone. Unique
factorisation gives the exact identity
\[ S_2(x;H)= \sum_{\substack{q\ {\rm prime}\\q\ge\sqrt x}}\frac1q \#\left\{ p\ {\rm prime}:\frac{x}{q}\le p\le \min\!\left(q,\frac{x+H}{q}\right) \right\}. \tag{1} \]Here \(q\) is the larger prime factor. This is (a).
Restrict further to \(p\le q\le2p\), and call the resulting sum \(B(x;H)\).
Then
\[ B(x;H)= \sum_{\substack{q\ {\rm prime}\\ \sqrt x\le q\le\sqrt{2(x+H)}}}\frac1q \#\left\{ p\ {\rm prime}: \max\!\left(\frac q2,\frac xq\right) \le p\le \min\!\left(q,\frac{x+H}{q}\right) \right\}. \tag{2} \]Every term in (2) is a term of the composite-only sum, so
\[ S_{\rm all}(x;H)\ge S_{\rm c}(x;H)\ge S_2(x;H)\ge B(x;H). \tag{3} \]This isolates a clean sufficient lemma:
> Uniform balanced-pair lemma needed. Find fixed \(C,\kappa>0\) such
> that, for every sufficiently large \(x\),
> \[ > \#\{(p,q)\in\mathbb P^2:p\le q\le2p,\ > x\le pq\le x+C\sqrt x(\log x)^2\}\ge\kappa\sqrt x. \tag{4} > \]
For large \(x\), all \(q\) in (4) are at most \(2\sqrt x\). Thus (4) would
give \(B(x;H)\ge\kappa/2\), proving even the composite-only version.
For \(q\asymp\sqrt x\), each inner prime interval in (1) or (2) has length
\[ \frac{H}{q}\asymp(\log x)^2. \]A lane-by-lane prime number theorem would therefore demand uniform prime
control in polylogarithmic intervals, far beyond known all-\(y\) results.
Such lane-by-lane control is stronger than necessary: (4) only asks for an
aggregate Type-II lower bound across the hyperbolic strip. But no checked
source supplies that aggregate lower bound either.
For comparison, applying the Guth–Maynard all-\(y\) exponent
\(\theta>17/30\) at factor scale \(y=\sqrt x\) naturally produces product
intervals of size
\[ y^{1+\theta}=x^{(1+\theta)/2}>x^{47/60}, \]polynomially longer than \(x^{1/2}\log^2x\).
A prime-number-theorem heuristic, not a proof, predicts
\[ B(x;C\sqrt x\log^2x) \sim 4C\left(1-\frac1{\sqrt2}\right). \tag{5} \]This follows by replacing each prime measure by \(dt/\log t\) in (2).
The full semiprime heuristic similarly predicts \(4C\). Both statements are
(c) only.
4. Exhaustive finite theorem
4.1 A wholly integer inner window
For integer \(m\ge3\), set
\[ k_m=\lfloor\log_2(m-1)\rfloor \]and
\[ h_-(m)= \lfloor\sqrt{m-1}\rfloor \left\lfloor\left(\frac{693k_m}{1000}\right)^2\right\rfloor-1. \tag{6} \]The exact positive-term expansion
\[ \log2 =2\sum_{j\ge0}\frac{1}{(2j+1)3^{2j+1}} >\frac{842}{1215} >\frac{693}{1000} \]certifies the decimal inequality; the last cross-product differs by \(5\):
\(842000-693\cdot1215=5\).
Since \(m-1\ge2^{k_m}\), (6) gives
\[ h_-(m)+1 \le\sqrt{m-1}\left(\frac{693k_m}{1000}\right)^2 <\sqrt{m-1}\log^2(m-1). \tag{7} \]Now take any real \(x\) and \(m=\lceil x\rceil\).
- If \(x\notin\mathbb Z\), then \(x>m-1\), and monotonicity of
\(u+\sqrt u\log^2u\), together with (7), gives
\[
m+h_-(m) Therefore This proves that checking the integer window (6) for every integer \(m\) also checks every real \(x\). This part is (a). Generate every event that can occur in the windows. Its genuine contribution is \(1/q\). The checker instead adds All comparisons and running sums use the integer numerator \(\lfloor10^{12}/q\rfloor\). Let Both \(h_-(m)\) and \(m+h_-(m)\) are nondecreasing. If \(m\) is not an event product, moving from \(m\) to \(m+1\) removes no event and may only add events on the right. Hence a new minimum can occur only 1. at the first integer of a reported block, or 2. at \(m=n+1\) immediately after an event \(n=pq\) leaves. The program scans exactly these candidates with two monotone pointers. This is the reason 3.56 million candidates certify roughly one billion integer starts. Completeness of prime generation is also elementary: if \(p\le q\le2p\) and \(pq\le N\), then \(p\le\sqrt N\) and \(q^2\le2pq\le2N\). A sieve through \(\lfloor\sqrt{2N}\rfloor+2\) therefore contains every possible factor. The table blocks are blocks of the integer \(m=\lceil x\rceil\). “Minimum” is the exact minimum of the fixed-point lower sum (9), not a floating estimate. | integer \(m\) block | certified minimum | attaining \(m\) | \(h_-(m)\) | balanced terms | |---:|---:|---:|---:|---:| | \(10^6\)–\(9{,}999{,}999\) | 0.961228141898 | 1,021,338 | 174,729 | 1,189 | | \(10^7\)–\(99{,}999{,}999\) | 1.022100901595 | 16,113,170 | 1,019,555 | 4,913 | | \(10^8\)–\(10^9\) | 1.066514980610 | 516,150,462 | 8,541,967 | 28,703 | The global fixed-point minimum is By (8), (9), and (3), this proves the boxed finite theorem for every real \(x\in[10^6,10^9]\). The finite conclusion is (d), backed by the elementary proof of what the computation certifies. Run: Observed output on this VM: Measured cost was 10.87 seconds wall time and 160,864 KiB peak resident memory. The script contains four independent safeguards: 1. an exact rational certificate for \(0.693<\log2\); 2. a complete least-prime-factor factorisation check against prime-pair generation through \(10^5\); 3. a candidate-only scan compared with an every-integer prefix scan on \(1000\le m\le50000\); 4. a fresh factor-pair enumeration at each of the three reported minima, independent of the event array and two-pointer scan. The displayed the smaller exact integer The finite computation rules out small or moderately large counterexamples for \(C=1\), even for the stronger composite-only sum, but it cannot settle an eventual statement. No finite extension changes that quantifier. The precise missing analytic input is (4), or an alternative lower bound of comparable strength for the rough-number integral/full weighted sum. Existing tools checked here fall short for distinct reasons: \(\asymp\sqrt x\) target increment; factor intervals; weight only \(\asymp x^{-1/2}\), while the desired sum needs \(\gg\sqrt x\) such weighted events in aggregate. Thus the honest endpoint is a verified finite theorem, an exact balanced bilinear reduction, and a named uniform Type-II lower-bound barrier—not a solution of the asymptotic problem. PARTIAL: The stronger composite-only inequality with C=1 is certified (>0.961) for every real x in [10^6,10^9], and the remaining all-x asymptotic step is the stated uniform balanced-semiprime Type-II lower bound.
4.2 Exact lower weights and the event scan
4.3 Certified table
4.4 Reproduction and independent checks
python runs/erdos462_wave5x_reverify.py
exact log(2) certificate: 842/1215 > 693/1000
least-factor vs prime-pair identity cross-check: PASS
small candidate-scan vs every-x cross-check: PASS
parameters: real_x=[1000000,1000000000] terminal=1012743665 q_limit=45007 primes=4676 events=3602274 candidates=3561287 scale=1000000000000
block=[1000000,9999999] scaled_min=961228141898 lower=0.961228141898 at_m=1021338 h_minus=174729 right=1196067 terms=1189 direct_sum≈0.961228142459 direct_recount=PASS
block=[10000000,99999999] scaled_min=1022100901595 lower=1.022100901595 at_m=16113170 h_minus=1019555 right=17132725 terms=4913 direct_sum≈1.022100903973 direct_recount=PASS
block=[100000000,1000000000] scaled_min=1066514980610 lower=1.066514980610 at_m=516150462 h_minus=8541967 right=524692429 terms=28703 direct_sum≈1.066514994833 direct_recount=PASS
CERTIFIED: for every real x in [10^6,10^9], the balanced-semiprime contribution in the live-page window is > 0.961
direct_sum≈ values are diagnostics only. Certification usesscaled_min values.5. Exact wall