Restricted order of an additive basis: existence, boundedness in the order, and equality (Erdős #338)
Statement
Let $A\subseteq\mathbb{N}$ be an additive basis of order $h$, i.e. every sufficiently large integer is a sum of at most $h$ elements of $A$ with repetitions allowed. The restricted order of $A$ is the least integer $t$ (if it exists) such that every sufficiently large integer is the sum of at most $t$ pairwise distinct elements of $A$. Three questions: (1) What are necessary and sufficient conditions on $A$ for the restricted order to exist? (2) When it exists, can it be bounded in terms of the order of $A$? (3) What are necessary and sufficient conditions for the restricted order to equal the order?
Acceptance. FULLY RESOLVES: complete answers, with proofs, to all three questions: (1) a necessary-and-sufficient criterion for the existence of the restricted order; (2) either an explicit function $B(k)$ such that every order-$k$ basis possessing a restricted order has restricted order $\leq B(k)$, or a proof that for some $k$ no finite bound exists; (3) a necessary-and-sufficient criterion for the restricted order to equal the order. Machine-checkable proofs (Lean 4) preferred, else complete written proofs. ADVANCES (each independently valuable): (a) a full answer to any single one of the three questions; (b) for any fixed $k\geq 3$, either a finite bound on the restricted order of order-$k$ bases or a family of order-$k$ bases with unbounded restricted order; (c) a construction, with proof, of order-$k$ bases whose restricted order strictly exceeds the $2^{k-2}+k-1$ lower bound stated in the background, already interesting for small $k$; (d) an answer to the subsidiary question: whether $A\setminus F$ being a basis for every finite $F$ forces a restricted order. Constructions may be computer-discovered but each basis property is an asymptotic statement and must be certified by a complete proof — a finite check alone is insufficient. Deliver the proofs and the explicit constructions.
Background
Raised by Erdős and Graham [ErGr80], [ErGr80b]; listed as open on erdosproblems.com/338 (fetched 2026-07-13, status 'open'). Existence can fail: Bateman observed that for $h\geq 3$ the set $A=\{1\}\cup\{x>0 : h\mid x\}$ is a basis of order $h$ with no restricted order (sums of distinct elements only hit residues $0$ and $1$ modulo $h$). For order $2$ the answer to question (2) is complete: Kelly [Ke57] proved every basis of order $2$ has restricted order at most $4$ and conjectured the bound $3$ (which he proved assuming positive lower density), but Hennecart [He05] disproved the general conjecture by constructing an order-$2$ basis with restricted order exactly $4$. For higher orders only a lower bound is known: Hegyvári, Hennecart and Plagne [HHP07] showed that for every $k\geq 2$ there is a basis of order $k$ with restricted order at least $2^{k-2}+k-1$, so any bound in (2) must grow at least exponentially, and for $k\geq 3$ it is not even known whether a finite bound exists. For question (3), classical examples: the squares form a basis of order $4$ with restricted order $5$ [Pa33], while the triangular numbers have order $3$ and restricted order $3$ [Sc54]. Bloom's page also records the subsidiary question: if $A\setminus F$ is a basis for every finite set $F$, must $A$ have a restricted order — and what if all these are bases of the same order? No Lean formalisation exists yet. The attacker's tools: explicit constructions in the Hennecart/Hegyvári–Hennecart–Plagne style — structured unions of residue classes and intervals whose covering properties are certified by finite case analysis plus induction, with candidate patterns found by computer search — and combinatorial covering arguments for upper bounds.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #338 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.