Problem 868

If $A$ is an additive basis of order $2$ , and $1_A\ast 1_A(n)\to \infty$ as $n\to \infty$ , then must $A$ contain a minimal additive basis of order $2$ ? (i.e. such that deleting any element creates infinitely many $n\not\in A+A$ )

What if $1_A\ast 1_A(n) >\epsilon \log n$ (for all large $n$ , for arbitrary fixed $\epsilon>0$ )?

Source: erdosproblems.com/868

Number theory
Additive bases

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

Disproved. The site labels the problem SOLVED (LEAN) and records a negative answer to both questions by Larsen and Larsen, who build a basis with representation counts above $\varepsilon\log n$ and no minimal subbasis, against the positive answer of [ErNa79] when every large $n$ has more than $c\log n$ representations $n=a+a'$ with $a\le a'$ in $A$ for some $c>1/\log(4/3)$ (the site writes this threshold for $1_A\ast 1_A(n)$ , which counts ordered pairs and is about twice that number); its label's Lean qualifier refers to a Lean 4 formalization of the note posted in lean-proofs on 2026-08-16, which this corpus has not audited. The accepted claim, a disproof of both questions, is Larsen and Larsen.

ErNa79: Erdős, Paul and Nathanson, Melvyn B., Systems of distinct representatives and minimal bases in additive number theory. (1979), 89-107.
ErNa89: Erdős, Paul and Nathanson, Melvyn B., Additive bases with many representations. Acta Arith. (1989), 399-406.
Ha56: Härtter, Erich, Ein Beitrag zur Theorie der Minimalbasen. J. Reine Angew. Math. (1956), 170-204.
Na74: Nathanson, Melvyn B., Minimal bases and maximal nonbases in additive number theory. J. Number Theory (1974), 324-333.
Er92c: Erdős, P., Some of my forgotten problems in number theory. Hardy-Ramanujan J. 15 (1992), 34-50; on p. 44 Erdős asks whether $f(n)\to\infty$ forces a minimal asymptotic basis of order $2$ and, if not, whether $f(n)>c\log n$ for any $c>0$ already does. Library home: Erdős 1992.
LaLa26: Larsen, Daniel and Larsen, Michael, Robust additive bases without minimal subbases. arXiv:2601.18507 (2026), 9 pp.; note posted to the problem's forum 2026-01-13.

Problem 868

Status

Proof claims

Discussion