Erdős Problem #444
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: number theory, divisors.
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
Let \(A\) be any infinite set of positive integers, and let \(d_A(n)\) count how many selected elements divide the integer \(n\):
Write \(H_A(x)=\sum_{a\in A\cap[1,x)}1/a\) for the harmonic weight of the selected elements and \(M_A(x)=\max_{1\leq n<x}d_A(n)\). Erdős Problem 444 asks whether, for every fixed positive integer \(k\), the ratio \(M_A(x)/H_A(x)^k\) has unbounded limsup as \(x\) tends to infinity.
In ordinary terms, no matter how an infinite set of possible divisors is chosen, some integers have extraordinarily many of those divisors relative to any fixed polynomial in their total reciprocal weight. The assertion involves a maximum over all integers below \(x\), not an average over those integers. Moreover the quantifier is “for every \(k\)”; proving the assertion for just one exponent is insufficient.
A small example
If \(A=\{2,3,6\}\) and \(n=6\), each of \(2,3,6\) divides \(6\), so \(d_A(6)=3\). Its reciprocal weight is \(1/2+1/3+1/6=1\). This gives the finite ratio \(3\) for any exponent \(k\), but finite \(A\) does not satisfy the theorem's hypothesis and no asymptotic conclusion follows from it.
A more instructive infinite example takes \(A=\mathbb N\), so \(d_A(n)\) is the ordinary divisor-counting function \(\tau(n)\) and \(H_A(x)\) is approximately \(\log x\). Let \(N_r\) be the product of the first \(r\) distinct primes. Unique factorization gives \(\tau(N_r)=2^r\): each prime is either included or excluded in a divisor. Taking \(x=N_r+1\) guarantees \(M_A(x)\geq2^r\).
By Bertrand's postulate one may crudely bound prime number \(r\) by \(2^r\), giving \(\log N_r=O(r^2)\). Hence \(H_A(N_r+1)=O(r^2)\) and \(M_A(N_r+1)/H_A(N_r+1)^k\geq2^r/O(r^{2k})\), which diverges for every fixed \(k\). This is an elementary proof of the theorem for this particular set, not for an arbitrary infinite set \(A\).
What is known
Erdős and Graham included the question in Old and New Problems and Results in Combinatorial Number Theory (1980), printed page 88. The general affirmative result was proved by Erdős and Sárközy [ErSa80], as documented in the maintained Erdős Problems #444 entry.
The theorem says that every infinite \(A\), including an extremely sparse one, satisfies the unbounded-limsup conclusion for every fixed \(k\). The primorial example above shows why the result may be plausible for a dense set of divisors, but the full strength is its independence from any density assumption on \(A\).
One should not silently replace the maximum with an average. The expected value of \(d_A(n)\) over a finite interval has a natural relation to \(H_A(x)\), but the theorem detects rare integers with much larger divisor multiplicities. Similarly, the theorem does not claim that the ratio tends to infinity along every sufficiently large \(x\); an unbounded limsup is a weaker and more precise assertion.
GCL's current state
The original audit issue #1714 pins teorth/erdosproblems at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml Git blob 4e60263a80af6207aca494d2e1388e44fa372889. Its historical status is proved. The source packet records no #444 statement file in the admitted FormalConjectures revision 85f863718beeec7b58a3a1926ee92e3472bc2020; the absence of a pinned theorem precludes any claim of a GCL Lean replay.
The authenticated first original-issue return is https://github.com/grandchallenge/MATH-PROGRAMME/issues/1714#issuecomment-6158616099. It binds the printed question, the published Erdős–Sárközy attribution and the independently checked divisor examples to their exact issue. Source readiness is not mathematical certification or protected V2 editorial admission.
What remains
A bounded numerical fixture can choose several explicitly infinite sets, such as all natural numbers, even numbers, perfect squares and an increasing sequence of prime powers, then compute exact truncated reciprocal sums and maxima of \(d_A(n)\) for small \(x\). Two implementations should agree: one tests divisibility directly and the other factors \(n\) and generates its divisors before testing membership in \(A\). These checks make the definitions executable without pretending to test an infinite limsup.
The documentary obligation is to read Erdős–Sárközy's 1980 primary theorem and verify the order of quantifiers: all infinite \(A\), each fixed exponent \(k\), and unbounded limsup as \(x\to\infty\). A finite set, a growing exponent \(k=k(x)\), or an ordinary limit in place of limsup would be materially different. Success requires exact arithmetic and the correct theorem statement. Falsification includes counting divisors from outside \(A\), omitting the denominator's square-free harmonic weights, or promoting the primorial special case into a proof for arbitrary \(A\).
Sources and claim boundaries
Historical problem: Erdős–Graham (1980), printed p.88. Primary resolution: Erdős and Sárközy [ErSa80], described in Erdős Problem #444. Frozen GCL source: issue #1714, teorth catalogue, and authenticated source return when posted.
The finite example and special-case primorial calculation are independently verified. The universal theorem remains attributed to its original researchers. This article asserts no novel mathematical result, successful formal build, protected publication or editorial admission.
In particular, the phrase “for every fixed \(k\)” is mathematically substantive: even if the denominator grows slowly, its \(k\) th power can grow rapidly, and the theorem nevertheless finds a larger maximum along some subsequence of scales. Nothing in that assertion implies a uniform bound across all \(k\) simultaneously, or a construction of the maximizing integer at every scale.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1714 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.