Erdős Problem #339
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: proved (not automatically the live result).
Subject areas: number theory, additive basis.
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
Take a set \(A\) of positive integers that is an additive basis of order \(r\): every sufficiently large positive integer can be made by adding at most \(r\) members of \(A\), and no smaller bound has this property. Repetition is allowed in this ordinary sumset. Erdős and Graham asked whether the same order still has many representations when repetition is forbidden. In other words, define the restricted r-fold sumset by \(r\times A=\{a_1+\cdots+a_r:a_i\in A\text{ and the }a_i\text{ are pairwise distinct}\}\). Must this set have positive lower asymptotic density?
Here “positive lower density” means that the eventual lower proportion of represented integers is nonzero: \(\liminf_{x\to\infty}|(r\times A)\cap[1,x]|/x>0\). The maintained problem page records a companion question as well: if the ordinary r-fold sumset has positive upper density, must the restricted r-fold sumset have positive upper density? These are density assertions, not claims that every large integer has a distinct representation.
A small example
Let \(A\) be the odd positive integers and take \(r=2\). Every sufficiently large odd integer is already in \(A\), while every sufficiently large even integer is a sum of two odd integers, so \(A\) is a basis of order \(2\). For the restricted sumset, the exact calculation is transparent: if \(n\) is even and \(n\ge4\), then \(n=1+(n-1)\), and the two summands are distinct odd integers. No odd integer is a sum of two odd integers, and \(2\) has no representation by two distinct positive odd integers.
I checked this with exact integer enumeration of all pairs from \(\{1,3,5,\ldots,21\}\) whose sum is at most \(20\). The represented values are exactly \(4,6,8,10,12,14,16,18,20\). This finite check illustrates both the parity and the distinctness condition. It does not prove a positive density statement for an arbitrary basis, and it does not reproduce the general theorem’s argument.
What is known
The pinned catalogue entry at commit 536408716724a2402bdfa7c1d764bf83d64a8c89, whose data/problems.yaml blob is 4e60263a80af6207aca494d2e1388e44fa372889, labels Problem 339 “proved” with last update 2025-10-12. The maintained page gives the same statement and says that both density questions have affirmative answers through Hegyvári, Hennecart, and Plagne [HHP03]. Its live bibliography identifies the paper as A proof of two Erdős' conjectures on restricted addition and further results, Journal für die reine und angewandte Mathematik 560 (2003), 199–220, DOI 10.1515/crll.2003.055. The live history shows the explanatory status was added on 20 October 2025, while the page currently says it was last edited 14 October 2025; this is presentation history, not a new mathematical result.
The primary paper’s abstract states the two relevant conclusions: positive upper density of an ordinary sumset implies positive upper density of the corresponding restricted sumset, and an additive basis of order \(r\) has an r-fold restricted sumset of positive lower density. The maintained problem discussion identifies the direct implication as Theorem 4. I could not read the publisher’s complete 2003 text in this timebox, so the exact printed page on which Theorem 4 appears is not independently locked here; only the article’s journal page range and theorem number are reported. A later primary paper by the same authors, Answer to a Question by Burr and Erdős on Restricted Addition, and Related Results, was readable and confirms the notation separating repeated and pairwise-distinct sums. Its local PDF SHA-256 is 2012568bc0c255ec0c234cc5cbf8eb7081022987a52cef80eccb192a0f954a02. That later paper is contextual evidence, not a substitute for checking the 2003 proof.
GCL's current state
GCL’s issue #1609 assigns a source and reusable-lemma audit for Problem 339. At the audit readback it was open, carried gcl-job, gcl-pickup:direct-editorial, gcl-collab:cooperative, gcl-role:source-audit, and gcl-state:available, and had no comments. The local protected registry records OUTSIDE_STRICT_OPEN_TRIAGE; that operational class does not change the external theorem’s status and does not authorize mathematical certification.
The exact FC-GDM snapshot named by the packet is FC-GDM-85F86371, upstream FormalConjectures revision 85f863718beeec7b58a3a1926ee92e3472bc2020. Its admitted manifest SHA-256 is faa43f174717ef0126114b9bbd61bb9fdc827ce7eb9f64e56c1e63c7b15608db. There is no Problem 339 statement file in that snapshot, so GCL has no pinned Lean theorem source, with or without sorry, to compare against the paper. The V2 ledger, not the catalogue label alone, decides any accepted coverage; this article supplies documentary evidence only.
What remains
The bounded next step is a source-lock task: obtain a readable copy of HHP03 from the DOI or an author/archive copy, record its exact file hash, transcribe Theorem 4 and its hypotheses, and compare its definitions of basis, ordinary \(rA\), restricted \(r\times A\), upper density, and lower density line by line with the live statement. Acceptance should require the theorem to imply both clauses with the same quantifiers and no hidden assumption such as \(0\in A\); falsification is any mismatch in order convention, density notion, or distinctness requirement. Stop when the primary text remains unavailable after the bounded retrieval attempts, or when the semantic comparison is complete. No Lean replay or formalization should be claimed from this audit.
Sources and claim boundaries
The original statement is attributed by the live page to Erdős and Graham, Old and new problems and results in combinatorial number theory (1980), p. 52; the live reference record is ErGr80. The current maintained entry is Erdős Problem 339, with revision history and discussion thread. The frozen catalogue source is the pinned YAML blob. The resolving primary citation is HHP03 above; its full proof remains a bounded source-access limitation here. The original SOURCE RESULT/1 citation is authenticated original RESULT/1. Nothing in this article is a GCL mathematical certificate, Lean verification, publication decision, or independent re-proof.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1609 — 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.