Erdős Problem #440
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: solved (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
Let \(A=\{a_1<a_2<\cdots\}\) be any infinite, increasing sequence of positive integers. Examine adjacent members, not arbitrary pairs. Write \(A(x)\) for the number of indices \(i\) such that
The least common multiple is the smallest positive integer divisible by both numbers. Erdős Problem 440 asks two related questions: must \(A(x)\) always be at most a constant times \(\sqrt{x}\), uniformly over the sequence; and what is the largest possible value of
The first asks for an upper bound valid at every large scale. The second asks for the greatest persistent normalized count: the limit inferior discounts occasional large peaks. A third quantity, the limit superior, permits peaks and has a different optimal constant. Keeping these three assertions separate is essential to reading the literature correctly.
The original problem is printed in P. Erdős and R. L. Graham, Old and New Problems and Results in Combinatorial Number Theory (1980), p. 87. Its notation uses \(\mathrm{lcm}(a_i,a_{i+1})\) and asks both the square-root upper bound and the size of the limit inferior. The maintained Erdős Problems entry reports that both questions have been settled; it records a sharp limit-superior constant as an additional result.
A small example
Take the simplest possible sequence, \(A=\mathbb N\). Consecutive integers are coprime, so
Consequently \(A(x)\) is the largest nonnegative integer \(i\) satisfying \(i(i+1)\leq x\). At \(x=1000\), exactly 31 adjacent pairs qualify because \(31\cdot32=992\) while \(32\cdot33=1056\). As \(x\) increases, \(A(x)=\sqrt{x}+O(1)\), and therefore the limit inferior and limit superior of \(A(x)/\sqrt{x}\) both equal \(1\). This construction proves that any universal upper bound for the limit inferior cannot be smaller than \(1\).
What is known
Erdős and Graham posed the question in their 1980 monograph, printed page 87. The associated Erdős–Szemerédi paper [ErSz80] proves that every infinite increasing sequence has \(A(x)=O(\sqrt{x})\). It also identifies the sharp value of the limit-inferior extremum: for every such \(A\), the limit inferior of \(A(x)/\sqrt{x}\) is at most \(1\), and the elementary choice \(A=\mathbb N\) shows that \(1\) is attainable. These are the answers to the original two questions, not conjectural patterns.
An elementary proof of the square-root bound.
There is a short elementary proof of the order of growth in the first question. It does not prove the sharp constant, the limit-inferior extremum, or the optimal limit-superior coefficient. The argument below was recovered from a retained GCL source-audit draft and independently checked for its quantifiers and inequalities.
Fix a real number \(x\geq1\). For any index counted by \(A(x)\), put \(d_i=\gcd(a_i,a_{i+1})\). Because the sequence is strictly increasing and \(d_i\) divides both terms, \(a_{i+1}-a_i\) is a positive multiple of \(d_i\). The defining least-common-multiple condition gives
At most \(\sqrt{x}\) qualifying starting values are smaller than \(\sqrt{x}\), because they are distinct positive integers. For every integer \(j\geq0\), consider qualifying starts in the interval
Each qualifying start in this interval is followed by a gap of at least \(4^j\) in the original sequence. Hence successive qualifying starting values in this interval are also separated by at least \(4^j\). The interval has length \(2^j\sqrt{x}\), so it contains at most \(\sqrt{x}/2^j+1\) qualifying starts.
Every qualifying start has \(a_i\leq x\), so the only possible intervals satisfy \(0\leq j\leq\lfloor\log_2\sqrt{x}\rfloor\). Summing the geometric bound yields
This proves a uniform square-root upper bound without relying on the sharp published theorem. It does not identify the optimal multiplicative coefficient; the separate results about limit inferior and limit superior still require their correctly attributed source theorems.
There is a stronger pointwise upper estimate involving a different constant. Erdős and Szemerédi proved that \(A(x)\leq(c+o(1))\sqrt{x}\), where
The series is convergent, because its terms are of order \(j^{-3/2}\). Its optimality relates to upper peaks as \(x\) varies, not to an attainable limit inferior greater than one. The maintained Erdős Problems #440 entry credits van Doorn with independently finding that coefficient and Terence Tao with a simple proof of the qualitative square-root upper bound, before identifying the earlier Erdős–Szemerédi result. Longer blocks of consecutive selected numbers are also considered in that primary paper.
It would be a substantive error to say that \(c\approx1.86\) is the largest possible value of the displayed liminf; the correct value is \(1\). The distinction is why the problem statement asks about two separate properties.
GCL's current state
The original audit issue #1710 maps to catalogue entry #440 at pinned teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml Git blob 4e60263a80af6207aca494d2e1388e44fa372889. The frozen status reports solved, consistent with the published result. The protected source packet records no 440.lean file in the admitted FormalConjectures revision 85f863718beeec7b58a3a1926ee92e3472bc2020. This absence does not affect the published theorem but prevents a claim of pinned GCL Lean replay.
The authenticated source-audit comment on original issue #1710 is https://github.com/grandchallenge/MATH-PROGRAMME/issues/1710#issuecomment-6158510176. It is a source-custody receipt, not mathematical certification. Protected Compendium publication and editorial acceptance through the V2 admissions ledger are separate operations.
What remains
A bounded computational fixture should generate sequences \(A=\mathbb N\), even integers, squares and multiples of a fixed integer, and enumerate all adjacent pairs whose least common multiple is at most a declared \(x\). Two independent implementations should calculate least common multiples using both gcd reduction and prime exponent maxima. For \(A=\mathbb N\), verify \(A(1000)=31\) and the exact quadratic threshold. For every sequence, since \(\mathrm{lcm}(a_i,a_{i+1})\geq a_{i+1}\), the enumeration may stop once the next selected term exceeds \(x\).
A source-concordance task should extract Erdős and Szemerédi's individual square-root bound, the exact liminf extremum, the series for the optimal pointwise coefficient and the hypotheses for each. Acceptance requires exact agreement of the two finite methods and a theorem table preserving which constant applies to which quantifier. Falsification includes missed adjacent indices, counting all pairs instead of adjacent pairs, mixing up liminf and limsup, or claiming that the finite example proves the general bound. Stop at this mathematical-source and arithmetic test, without reopening the solved theorem as an unselected research campaign.
Sources and claim boundaries
Original question: Erdős–Graham (1980), printed p.87. Resolving theorem: Erdős–Szemerédi (1980), referenced in Problem #440, with historical comments by Tao and van Doorn. GCL provenance: original issue #1710, pinned teorth catalogue, and the original authenticated source audit when posted.
The quadratic finite example is exact arithmetic. The universal statements are attributed to the original published researchers. Neither an original new theorem, certified Lean build, protected production publication, nor V2 editorial acceptance is claimed.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1710 — 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.