← All problems

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

38 years old · traced to

Let A⊆NA\subseteq\mathbb N be an asymptotic additive basis of order 22: every sufficiently large natural number is a sum of two elements of AA. Suppose that for every t∈Nt\in\mathbb N, for all sufficiently large nn, there is a finite set P⊆N×NP\subseteq\mathbb N\times\mathbb N with ∣P∣≥t|P|\ge t such that every (a,b)∈P(a,b)\in P satisfies a,b∈Aa,b\in A, a+b=na+b=n, and a≤ba\le b. Can AA always be partitioned into disjoint sets B,CB,C such that both BB and CC are asymptotic additive bases of order 22?

References

Progress summary

Refreshed
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 22 whose representation count tends to infinity must split into two disjoint additive bases of order 22. Erdős and Nathanson proposed this after proving stronger positive results.

Known results

  • Erdős and Nathanson, 1988: a partition exists when 1A∗1A(n)>clog⁡n1_A\ast1_A(n)>c\log n eventually, with c>(log⁡43)−1c>(\log\frac{4}{3})^{-1}.
  • Erdős and Nathanson, 1989: for every fixed tt, they constructed bases with 1A∗1A(n)≥t1_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.

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

Sources

Solutions 0

No solutions have been posted yet.