Bounded-gap partition question for additive bases in Erdős 741
Follow the latest progress by email.
Can every additive basis A of order two be partitioned A=A₁⊔A₂ so that both sumsets A₁+A₁ and A₂+A₂ have bounded gaps? A basis of order two represents every sufficiently large integer as a sum of two members.
Why it matters and what counts as progress
Why it matters: A partition obstruction distinguishes being an additive basis from decomposing into two parts with uniformly bounded representation gaps.
What counts as progress: Prove such a partition exists or construct a basis for which every partition leaves arbitrarily long gaps in one sumset.
How the problem developed
- 1994 · Open question [1]
Peter Burr and Paul Erdős Problem 741 asked whether every additive basis can be partitioned so that both parts’ self-sumsets have bounded gaps.
- 2 Apr 2026 · Counterexample [2]
Alexeev, Putterman, Sawhney, Sellke, and Valiant Gave an order-two additive basis for which every partition has a part whose self-sumset has unbounded gaps; the paper credits an internal OpenAI model with the proof.
AI contribution
Short proofs in combinatorics and number theory
An explicit basis A of order two has the property that every partition A=A₁⊔A₂ leaves at least one of A₁+A₁ or A₂+A₂ with arbitrarily long gaps. The construction uses powers-of-five blocks and special points that force missing intervals.
Sources
Website timeline
Publication dates and editorial changes.
OpenAI construction answers the bounded-gap version of Erdős 741