Can a minimal order-k additive basis shed an infinite subset and remain a basis of order k+1? (Erdős #881)
Statement
Call $A\subset\mathbb{N}$ an (asymptotic) additive basis of order $k$ if every sufficiently large integer is the sum of at most $k$ elements of $A$ (repetitions allowed). Suppose $A$ is a basis of order $k$ which is minimal in the strong sense that for every infinite subset $B\subset A$, the set $A\setminus B$ is no longer a basis of order $k$. Must there then exist some infinite $B\subset A$ such that $A\setminus B$ is a basis of order $k+1$?
Acceptance. FULLY RESOLVES: (i) a proof that for every $k$ and every order-$k$ basis $A$ that is minimal in the stated infinite-subset sense, there exists an infinite $B\subset A$ with $A\setminus B$ a basis of order $k+1$ — machine-checkable (Lean 4, building on the existing formalised statement) preferred, else a complete written proof; OR (ii) a counterexample: an explicitly described set $A$ (decidable membership rule) and an integer $k$, with complete proofs that (a) $A$ is a basis of order $k$, (b) $A\setminus B$ is not a basis of order $k$ for any infinite $B\subset A$, and (c) $A\setminus B$ is not a basis of order $k+1$ for any infinite $B\subset A$. No finite computation can close either direction. ADVANCES: a resolution for a fixed small order (e.g. $k=2$); a proof under an added, clearly stated growth or representation-function hypothesis on $A$; a structural classification of bases that are minimal in the strong infinite-subset sense for some order; or a Lean formalisation of any such partial result. Deliver the proof file (or the construction together with its proofs).
Background
Posed by Erdős in one of his final problem papers [Er98]; listed as open on erdosproblems.com/881 (fetched 2026-07-13, status 'open', tagged 'number theory | additive basis'). The problem lives in the Erdős–Nathanson theory of minimal additive bases: Härtter [Ha56] and Nathanson [Na74] showed that an additive basis need not contain any minimal basis at all, and Erdős–Nathanson [ErNa79, ErNa88] studied which growth conditions on the representation function force a basis to contain a minimal one — see the sibling questions Erdős #868 and #870 (erdosproblems.com/868, erdosproblems.com/870). Note the minimality here is the strong, infinite-subset form: no infinite subset of $A$ can be deleted without destroying order-$k$ basis-ness (strictly stronger than element-minimality). The question asks whether such rigidity at order $k$ always leaves slack one level up — whether some infinite chunk is removable at the price of passing from order $k$ to $k+1$. Bloom's page records no partial results. The surrounding area is newly active: D. Larsen ('Three questions of Erdős–Nathanson on asymptotic bases of order 2', arXiv:2603.03472, 2026) recently resolved several Erdős–Nathanson questions on the robustness of order-2 bases, so techniques for building bases with controlled subbasis structure now exist. The statement is formalised in Lean in the google-deepmind/formal-conjectures repository. The attacker's tool: this is proof-shaped — explicit digit-restricted basis constructions in the Nathanson style to hunt for a counterexample, or a combinatorial argument for the positive direction, ideally machine-checked against the existing Lean statement.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #881 (T. F. Bloom) | website |
| REF-02 | Lean formalisation of Erdős #881 (google-deepmind/formal-conjectures) | website |
| REF-03 | D. Larsen — Three questions of Erdős–Nathanson on asymptotic bases of order 2 (2026, related order-2 work) | arxiv |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.