Erdős Problems

Tags Prizes

OPEN

Let $A=\{a_1<a_2<\cdots\}\subset \mathbb{N}$ be an infinite sum-free set - that is, there are no solutions to \[a=b_1+\cdots+b_r\] with $b_1<\cdots<b_r<a\in A$. How small can $a_{n+1}-a_n$ be? Is it possible that $a_{n+1}-a_n<n$?

#876: [Er98]

additive combinatorics

Erdős [Er98] writes that Graham 'recently proved' that there is such a sequence for which $a_{n+1}-a_n<n^{1+o(1)}$, and that Melfi proved a somewhat weaker result.

Erdős [Er62c] proved that a sum-free set has density zero. Deshouillers, Erdős, and Melfi [DEM99] constructed a sum-free set that grows like $a_n\sim n^{3+o(1)}$.

Luczak and Schoen [LuSc00] have proved that, for all large $N$, \[\lvert A\cap [1,N]\rvert\ll (N\log N)^{1/2},\] and that there exists a sum-free set $B$ such that \[\lvert B\cap [1,N]\rvert \gg \frac{N^{1/2}}{(\log N)^{1/2+o(1)}}\] for all large $N$.