Erdős Problem #338
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (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
Let \(A\) be an infinite set of positive integers. An ordinary sum may reuse an element: \(hA\) consists of sums of \(h\) members of \(A\), repetitions allowed. A restricted sum uses distinct members, written \(h\times A\). The ordinary order of \(A\) is the least \(h\) for which every sufficiently large integer lies in one of \(A,2A,\ldots,hA\). The restricted order is the least \(t\), if one exists, for which every sufficiently large integer lies in one of \(A,2\times A,\ldots,t\times A\).
Erdős Problem 338 asks four related questions. When does a basis have a finite restricted order? If its ordinary order is \(r\), is there a bound depending only on \(r\)? When are the two orders equal? It also asks whether a basis remains a basis after deleting any finite set, and whether that stronger deletion property forces a restricted order. “Sufficiently large” is essential: finitely many exceptional integers do not matter.
The original issue is MATH-PROGRAMME #1608, and the maintained entry is Erdős Problem 338. The current page calls the problem open. That is a status report about the general questions, not a claim that no special cases are known.
A small example
The maintained page gives Bateman’s useful obstruction. For \(h\geq3\), take
For \(h=3\), every sufficiently large integer has an ordinary representation using at most three terms: a multiple of \(3\) uses one term; a number congruent to \(1\) uses \(1+(n-1)\); and a number congruent to \(2\) uses \(1+1+(n-2)\). The last representation is allowed to repeat \(1\), so it is not restricted. Thus the ordinary order is \(3\).
The obstruction to restricted order is exact modular arithmetic. A distinct sum from \(A_3\) contains either zero or one copy of \(1\); all other summands are divisible by \(3\). Therefore every restricted sum is congruent to \(0\) or \(1\) modulo \(3\). Integers congruent to \(2\) modulo \(3\) are never represented, no matter how large they are.
I checked the finite prefix \(A_3\cap[1,60]\) independently with an unbounded dynamic program for ordinary sums and a descending 0/1 subset-sum computation for distinct sums. The exact output was:
A={1} union {3,6,...,60}
ordinary_max_for_5_to_60= 3
restricted_missing_residue_2= [5, 8, 11, 14]
14=1+1+12 (ordinary), 14 not in distinct subset sums= True
This verifies the finite calculation and illustrates the mechanism; it does not prove a statement about every possible basis, nor does a finite search establish an asymptotic order. The source packet also contains a material transcription issue: the scanned Erdős–Graham page appears to print the congruence class \(\{x>0:x\equiv1\pmod h\}\) where the maintained page and later summaries give \(\{1\}\cup\{x>0:h\mid x\}\). Those sets have different restricted-order behavior, so the formula must not be silently normalized.
What is known
The primary source inspected here is P. Erdős and R. L. Graham, “On bases with an exact order,” Acta Arithmetica 37 (1980), 201–207. Its p. 201 introduction defines ordinary and exact order; p. 206 defines restricted order and prints the four questions that became Problem 338. The same page records the Bateman example, Kelly’s order-two bound, and the examples of squares and triangular numbers. Because of the displayed-set discrepancy just noted, those p. 206 lines are evidence for the question and historical context, but not yet a clean source lock for the obstruction formula.
Several special results are recorded by the maintained page and have identifiable primary references. Kelly, “Restricted bases,” American Journal of Mathematics 79 (1957), 258–264, proves restricted order at most \(4\) for an order-two basis and at most \(3\) under positive lower density. Hennecart, “On the Restricted Order of Asymptotic Bases of Order Two,” The Ramanujan Journal 9 (2005), 123–130, gives the order-two upper bound and an example attaining restricted order \(4\). Hegyvári, Hennecart, and Plagne, “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, is the primary reference behind the later lower-bound literature. The maintained entry reports that for every \(k\geq2\) there is a basis of order \(k\) with restricted order at least \(2^{k-2}+k-1\).
These results leave the general necessary-and-sufficient conditions and the best order-only bound open. In particular, an explicit family with no restricted order is not a solution of the whole problem; it only shows that ordinary basishood does not force restricted basishood.
GCL's current state
The frozen catalogue packet is teorth/erdosproblems commit 536408716724a2402bdfa7c1d764bf83d64a8c89, entry number: "338" in data/problems.yaml, Git blob 4e60263a80af6207aca494d2e1388e44fa372889. It records informal status open, last update 2025-08-31, formal status unformalized, and statement-formalized no. The live page was last edited 14 September 2025 and likewise says OPEN, with no claimed solution or comments.
The admitted FormalConjectures provider is snapshot FC-GDM-85F86371, upstream commit 85f863718beeec7b58a3a1926ee92e3472bc2020. Querying that exact commit found no FormalConjectures/ErdosProblems/338.lean file. The provider is metadata-only in the GCL import record, so neither its absence nor any newer upstream file is a GCL formal result. The V2 ledger alone decides accepted coverage; this article records evidence for that process and does not confer acceptance.
What remains
The smallest immediate research task is source reconciliation. Compare the p. 206 scan with the original book or a reliable contemporaneous reprint, determine whether the congruence-class display is a typographical error, and record the exact set, convention for positive integers, and quantifier “sufficiently large.” Then independently verify the Bateman modular argument for the corrected set.
A second bounded task can formalize only the elementary interface: define ordinary and restricted sumsets, prove that \(A_3\) has ordinary order \(3\), and prove that its restricted sums omit every integer congruent to \(2\) modulo \(3\). That would be a useful test case, not a formal solution of the open classification questions. A larger formalization would need the primary proofs of Kelly, Hennecart, and Hegyvári–Hennecart–Plagne, plus a semantic review of their hypotheses.
Sources and claim boundaries
The source paper is the Erdős–Graham scan, inspected at p. 206; the downloaded bytes had SHA-256 f44cf64462480beee3239be050306d6f2bc0597c179cc1821b70ab3cddfd0f6e. The frozen catalogue and blob are linked above. The live status is erdosproblems.com/338. The primary references are Kelly’s DOI record, Hennecart’s DOI record, and the Hegyvári–Hennecart–Plagne paper.
The original SOURCE RESULT/1 citation is authenticated original RESULT/1; no GitHub comment has been posted by this worker. The finite computation is a verified illustration, not an external proof. Published theorem reports, catalogue metadata, and any future Lean statement remain distinct from GCL mathematical certification. This file makes no certification, publication, novelty, or award claim.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1608 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: STATEMENT_CAPTURE_REQUIRED.
- 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.