Erdős Problem #443
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (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
For a positive integer \(m\), form the set of values \(S_m=\{k(m-k):1\leq k\leq m/2\}\), with \(k\) an integer. Erdős Problem 443 asks how large an intersection \(S_m\cap S_n\) can be for two parameters \(m,n\). Can the intersection have arbitrarily many members? And can its size be bounded by a subpolynomial function of the parameters?
The case \(m=n\) must be treated separately: then the two sets are equal and contain approximately \(m/2\) distinct values, so a bound of the form \((mn)^{o(1)}\) is impossible along \(m=n\to\infty\). The meaningful upper-bound question concerns distinct parameters, usually normalized as \(m>n\). This is a material quantifier boundary, not a cosmetic change. Within each set, the expression \(k(m-k)\) increases for \(1\leq k\leq m/2\), so values are distinct.
The quadratic expression is also a difference of squares:
Consequently an equality \(k(m-k)=\ell(n-\ell)\) can be rewritten as the difference-of-squares equation \((m-2k)^2-(n-2\ell)^2=m^2-n^2\). This connects the intersection problem to divisor factorizations of a fixed integer.
A small example
For \(m=5\), the integer indices \(k=1,2\) give \(S_5=\{4,6\}\). For \(n=7\), the indices \(\ell=1,2,3\) give \(S_7=\{6,10,12\}\). Therefore \(S_5\cap S_7=\{6\}\) and the intersection has exactly one member. The shared value is represented by \(2(5-2)=1(7-1)=6\).
By contrast \(S_5\cap S_5=S_5\) has two members. Increasing \(m=n\) makes that self-intersection grow linearly, illustrating why a theorem stated for different parameters cannot be casually applied to the diagonal. A bounded exact fixture can enumerate the sets by integer multiplication, deduplicate them, and compare their intersection with the factorization identity above.
The equation of two quadratic expressions is not merely a numerical coincidence. Write \(u=m-2k\) and \(v=n-2\ell\). Then \((u-v)(u+v)=m^2-n^2\), where the parity and range of \(u,v\) are constrained by the original indices. Each common value produces a permitted factor pair of \(m^2-n^2\). This reduction is the natural bridge to divisor-function estimates.
What is known
Erdős and Graham posed the questions in Old and New Problems and Results in Combinatorial Number Theory (1980), printed page 88. The maintained Erdős Problems #443 page records independent resolutions by Hegyvári (2025) and Cambie (an unpublished argument). They show that for distinct \(m>n\) the intersection has size at most \(m^{O(1/\log\log m)}\), a subpolynomial bound.
They also establish that for every fixed positive integer \(s\) there exist infinitely many parameter pairs \((m,n)\) with precisely \(s\) common values. Thus intersections can be arbitrarily large, even though their maximal size grows slower than every fixed positive power of the parameters in the distinct-parameter regime.
These results answer different halves of the historical question. The existence of arbitrarily large finite intersections does not contradict a subpolynomial uniform upper bound. Nor is the upper theorem an assertion about identical parameters, where the intersection is trivially large. The maintained source's qualification \(m>n\) is indispensable.
GCL's current state
The original source issue #1713 maps to teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml Git blob 4e60263a80af6207aca494d2e1388e44fa372889. The frozen catalogue records the problem as proved, consistent with the later mathematical results as reported. The source packet records no admitted #443 statement file within FormalConjectures revision 85f863718beeec7b58a3a1926ee92e3472bc2020. The absence of a pinned file cannot be converted into a claim of GCL formal certification.
The original authenticated source-return citation is https://github.com/grandchallenge/MATH-PROGRAMME/issues/1713#issuecomment-6158604647. This report keeps the published Hegyvári result distinct from the Cambie unpublished argument and records the critical \(m>n\) condition. Editorial acceptance is governed by the separate V2 admissions ledger.
What remains
A bounded computational fixture should enumerate \(S_m\) for \(1\leq m\leq100\), compare every pair of distinct parameters, and record their exact common values and cardinalities. A second implementation should factor \(m^2-n^2\) and enumerate compatible \(u,v\) satisfying the difference-of-squares equation, checking parity and original index restrictions. The calculations must reproduce \(S_5\cap S_7=\{6\}\) and exclude the diagonal from any claimed subpolynomial uniform upper bound.
The source audit should inspect Hegyvári's 2025 proof and the public mathematical description of Cambie's independent argument, identifying the \(O(1/\log\log m)\) exponent and the quantified construction with exactly \(s\) solutions. Success requires complete agreement of the two finite methods and faithful distinction between a published and unpublished proof. Falsification includes a missing factor-pair parity restriction, counting multiple index representations as distinct intersection values, or asserting a subpolynomial bound for \(m=n\). Stop after the stated finite and source checks.
Sources and claim boundaries
Historical source: Erdős–Graham (1980), printed p.88. Current proof attribution and exact quantitative claims: Erdős Problem #443, citing Hegyvári (2025) and Cambie. Original provenance: GCL issue #1713, teorth catalogue, and authenticated RESULT/1 comment when posted.
The small intersection and difference-of-squares identity are independently exact arithmetic. The general bounds and arbitrary-size construction are attributed to external researchers. This article claims no novel theorem, Lean replay, protected merge or V2 editorial admission.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1713 — 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.