Erdős–Turán conjecture on additive bases

Open

erdos-turan-additive-basis

Statement

If $A \subseteq N$ is a basis of order 2 (every large integer is a sum of two elements of $A$ ), prove its representation count $r_{A} (n)$ is unbounded.

Current frontier

erdosproblems.com/28, OPEN since 1941. A random set gives a basis with $r_{A} (n) ≍ lo g n$ (Erdős 1956); Erdős–Fuchs (1956) rules out too-regular counting functions. Whether every order-2 basis has unbounded $r_{A} (n)$ is open.

When this counts as solved

BINARY

PROOF_COMPLETE for unboundedness over all order-2 bases, or COUNTEREXAMPLE: an explicit basis with $r_{A} (n) \leq C$ for all $n$ . Almost-all results or conditional statements are not terminal.

Classification

Binary

Mine this problem →