Let A⊆ N be an asymptotic additive basis of order 2: every sufficiently large natural number is a sum of two elements of A. Suppose that for every t∈ N, for all sufficiently large n, there is a finite set P⊆ N× N with |P|≥ t such that every (a,b)∈ P satisfies a,b∈ A, a+b=n, and a≤ b. Can A always be partitioned into disjoint sets B,C such that both B and C are asymptotic additive bases of order 2?

Erdős Problem #871 — Partitioning Additive Bases with Unbounded Representations

About 38 years old · traced to 1988

Let $A\subseteq\mathbb N$ be an asymptotic additive basis of order $2$ : every sufficiently large natural number is a sum of two elements of $A$ . Suppose that for every $t\in\mathbb N$ , for all sufficiently large $n$ , there is a finite set $P\subseteq\mathbb N\times\mathbb N$ with $|P|\ge t$ such that every $(a,b)\in P$ satisfies $a,b\in A$ , $a+b=n$ , and $a\le b$ . Can $A$ always be partitioned into disjoint sets $B,C$ such that both $B$ and $C$ are asymptotic additive bases of order $2$ ?

References

Primary source

The Formal Conjectures Authors, Formal Conjectures (2025); independently edited from the pinned source file.

Additional references

Pinned Formal Conjectures source, Apache-2.0.

additive-basis number-theory

InErdős Problems

Posted 2 months ago · edited 3 weeks ago

Progress summary

Refreshed 1 month ago

Open

A reported computer-assisted construction says the conjecture is false, but no independent proof or published paper has confirmed it.

The problem asks whether an additive basis of order $2$ whose representation count tends to infinity must split into two disjoint additive bases of order $2$ . Erdős and Nathanson proposed this after proving stronger positive results.

Known results

Erdős and Nathanson, 1988: a partition exists when $1_A\ast1_A(n)>c\log n$ eventually, with $c>(\log\frac{4}{3})^{-1}$ .
Erdős and Nathanson, 1989: for every fixed $t$ , they constructed bases with $1_A\ast1_A(n)\ge t$ eventually that cannot be partitioned into two disjoint bases.

January 2026 counterexample claim

Daniel Larsen reportedly obtained a small modification of the 1989 construction, assisted by Gemini 3 Pro and Claude Opus 4.5, yielding a counterexample with representation counts tending to infinity. The claim is recorded as disproving the problem, but the available formalization still contains by sorry and no corroborating paper was found.

Current status (as of January 2026): A counterexample is claimed, but the conjecture remains formally and independently unverified.

Claude Opus 4.5Anthropicsolved2026-01-01evidence
Gemini 3.0 ProGoogle DeepMindsolved2026-01-01evidence

Sources

No solutions have been posted yet.