Erdős Problem #442
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (not automatically the live result).
Subject areas: number theory.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
A set of integers can have a large harmonic weight even when its ordinary counting density is small. For \(A\subseteq\mathbb N\), define \(H_A(x)=\sum_{n\in A\cap[1,x)}1/n\). Erdős Problem 442 asked whether the condition \(H_A(x)/\log\log x\to\infty\) forces the reciprocal-least-common-multiple correlations within \(A\) to become arbitrarily large after normalization by \(H_A(x)^2\):
The two sums have slightly different endpoint conventions in the historical statement; these are normally negligible in suitable asymptotic regimes, but a formal statement must retain them exactly. The pair sum uses unordered distinct pairs. This is a question about the interaction of additive growth in harmonic weight with multiplicative overlap measured by gcd, since \(1/\mathrm{lcm}(a,b)=\gcd(a,b)/(ab)\).
A small example
Take the finite set \(A=\{2,3,6\}\) and an \(x>6\). Its harmonic weight is \(H_A=1/2+1/3+1/6=1\). All three pairwise least common multiples equal \(6\), so the reciprocal-LCM sum is \(3/6=1/2\), and the normalized expression is \(1/2\). This verifies the exact normalizations and the requirement to count each unordered pair once.
This finite example is not a counterexample to an asymptotic conjecture, because a finite set has bounded harmonic weight. More generally, multiplying the harmonic sum by an arbitrary scale without correspondingly changing the underlying set is not a valid operation: both the numerator and denominator must come from the same \(A\). A useful computational fixture sums exact rational numbers, avoiding rounding errors that can obscure close comparisons in finite examples. The identity \(\gcd(a,b)/(ab)\) gives a second independent way to calculate each LCM contribution.
What is known
The original question appears in Erdős and Graham's Old and New Problems and Results in Combinatorial Number Theory (1980), printed page 88. The answer is no, proved by Terence Tao in 2024, as described in the maintained Erdős Problems #442 entry.
Tao constructed an infinite set \(A\) whose harmonic weight grows at least as fast as
but whose normalized reciprocal-LCM pair correlation remains \(O(1)\). This is much stronger than merely exceeding \(\log\log x\): it explicitly falsifies the implication from large harmonic weight to divergent normalized correlations.
Tao also established a near-matching threshold: if the harmonic sum grows faster than \(\exp(O(\sqrt{\log\log x}\log\log\log x))\) in the precise sense specified by the theorem, the normalized correlation must diverge. Thus the counterexample is coupled to a sharp growth-regime analysis. The distinction between a bounded ratio for one carefully engineered set and forced divergence above a threshold is central to the result.
GCL's current state
The protected original source issue #1712 binds Erdős #442 to teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml Git blob 4e60263a80af6207aca494d2e1388e44fa372889. The frozen status is disproved, consistent with the mathematical counterexample. Its admitted FormalConjectures provider revision is 85f863718beeec7b58a3a1926ee92e3472bc2020; a present statement file, where applicable, is not itself a GCL-checked proof or verified theorem equivalence.
The authenticated original-issue RESULT/1 citation is https://github.com/grandchallenge/MATH-PROGRAMME/issues/1712#issuecomment-6158584246. This article does not attribute Tao's research to GCL or claim that an external Lean build has been reproduced. Accepted editorial coverage remains determined by the separate V2 SHA256 admissions ledger, not by this staging manuscript.
What remains
A bounded reproducible task should compute exact rational values of \(H_A(x)\) and the pair-correlation numerator for several finite sets, including \(A=\{2,3,6\}\) as a normalization regression. One implementation should use gcd reduction; another should compute lcm from prime-power maxima. They must agree on every unordered pair and explicitly exclude \(a=b\). A small finite calculation cannot settle the growth threshold, so the output must label its horizon.
The mathematical source task is to inspect Tao's 2024 proof and identify the precise interpretation of "grows faster than" the exponential threshold, including the little-o and big-O terms. It should state separately which construction keeps the correlation bounded and which theorem forces divergence at greater harmonic weight. Success requires complete source hypotheses and correct finite arithmetic; failure includes confusing divergent \(H_A\) with the stronger original hypothesis, changing endpoints without notice, or claiming a near-sharp exponent is an exact limiting constant. Stop after the bounded computation and source-concordance review.
Sources and claim boundaries
Original question: Erdős–Graham (1980), printed p.88. Resolving mathematical work: Tao (2024), linked through Erdős Problem #442. Frozen GCL issue #1712, teorth catalogue and the original issue source return when posted.
The finite \(1/2\) ratio is independent exact arithmetic. Tao's asymptotic counterexample and threshold are credited external research, not independently reproved here. No novel theorem, formal certification, protected merge or V2 admission is asserted.
A crucial claim-boundary detail is that the asymptotic theorem concerns one fixed infinite set and then the limit as \(x\) grows. Choosing a different set for each finite \(x\) would change the logical problem. Likewise, the normalization depends on the square of the harmonic weight of that same set; it is not a free parameter selected independently of the pair sum.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1712 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.