Erdős–Turán conjecture on additive bases

Open

erdos-turan-additive-basis

Statement

A \subseteq \mathbb{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) \asymp \log 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