Let a_1 < a_2 < … be any infinite sequence of integers. Straus and I conjectured that there always exists a sequence b_1 < b_2 < … of density 0, so that every sufficiently large integer is of the form a_i + b_j.

Erdős Problem #31 — Density-zero complementary sequences for arbitrary sequences

The question asks whether every infinite $A\subseteq\mathbb N$ admits a density-zero $B$ for which $A+B$ contains all sufficiently large integers. Erdős conjectured this, and G. G. Lorentz proved it in 1954.

Known result

Lorentz, 1954: every infinite $A\subseteq\mathbb N$ has an additive complement of asymptotic density zero.

2024 disjoint-complement refinement

A newer paper studies the stronger condition $B\cap A=\varnothing$ . It proves existence when $A=\{a_i\}$ satisfies $\liminf_{n\to\infty}a_{n+1}/a_n>1$ , and gives counterexamples to disjoint complements when the ratio limit inferior is $1$ ; these do not challenge Lorentz’s theorem.

Current status (as of March 2026): The stated problem is resolved by Lorentz’s 1954 theorem; only stronger variants, such as requiring $B\cap A=\varnothing$ , remain under investigation.

Erdős Problem #31 — Density-zero complementary sequences for arbitrary sequences

Primary source

Progress summary

Solutions 0