Erdős–Turán conjecture on additive bases

The conjecture was made jointly by Paul Erdős and Pál Turán in 1941.[1] In the original paper, they write

"(2) If ${\displaystyle f(n)>0}$ for ${\displaystyle n>n_{0}}$, then ${\displaystyle \varlimsup _{n\rightarrow \infty }f(n)=\infty }$",

where ${\displaystyle \varlimsup _{n\rightarrow \infty }}$ denotes the limit superior. Here ${\displaystyle f(n)}$ is the number of ways one can write the natural number ${\displaystyle n}$ as the sum of two (not necessarily distinct) elements of ${\displaystyle B}$. If ${\displaystyle f(n)}$ is always positive for sufficiently large ${\displaystyle n}$, then ${\displaystyle B}$ is called an additive basis (of order 2).[2] This problem has attracted significant attention[2] but remains unsolved.

In 1964, Erdős published a multiplicative version of this conjecture.[3]

While the conjecture remains unsolved, there have been some advances on the problem. First, we express the problem in modern language. For a given subset ${\displaystyle B\subset \mathbb {N} }$, we define its representation function ${\displaystyle r_{B}(n)=\#\{(a_{1},a_{2})\in B^{2}\mid a_{1}+a_{2}=n\}}$. Then the conjecture states that if ${\displaystyle r_{B}(n)>0}$ for all ${\displaystyle n}$ sufficiently large, then ${\displaystyle \limsup _{n\rightarrow \infty }r_{B}(n)=\infty }$.

More generally, for any ${\displaystyle h\in \mathbb {N} }$ and subset ${\displaystyle B\subset \mathbb {N} }$, we can define the ${\displaystyle h}$ representation function as ${\displaystyle r_{B,h}(n)=\#\{(a_{1},\cdots ,a_{h})\in B^{h}\mid a_{1}+\cdots +a_{h}=n\}}$. We say that ${\displaystyle B}$ is an additive basis of order ${\displaystyle h}$ if ${\displaystyle r_{B,h}(n)>0}$ for all ${\displaystyle n}$ sufficiently large. One can see from an elementary argument that if ${\displaystyle B}$ is an additive basis of order ${\displaystyle h}$, then

${\displaystyle \displaystyle n\leq \sum _{m=1}^{n}r_{B,h}(m)\leq |B\cap [1,n]|^{h}}$

So we obtain the lower bound ${\displaystyle n^{1/h}\leq |B\cap [1,n]|}$.

The original conjecture spawned as Erdős and Turán sought a partial answer to Sidon's problem (see: Sidon sequence). Later, Erdős set out to answer the following question posed by Sidon: how close to the lower bound ${\displaystyle |B\cap [1,n]|\geq n^{1/h}}$ can an additive basis ${\displaystyle B}$ of order ${\displaystyle h}$ get? This question was answered in the case ${\displaystyle h=2}$ by Erdős in 1956.[4] Erdős proved that there exists an additive basis ${\displaystyle B}$ of order 2 and constants ${\displaystyle c_{1},c_{2}>0}$ such that ${\displaystyle c_{1}\log n\leq r_{B}(n)\leq c_{2}\log n}$ for all ${\displaystyle n}$ sufficiently large. In particular, this implies that there exists an additive basis ${\displaystyle B}$ such that ${\displaystyle r_{B}(n)=n^{1/2+o(1)}}$, which is essentially best possible. This motivated Erdős to make the following conjecture:

If ${\displaystyle B}$ is an additive basis of order ${\displaystyle h}$, then ${\displaystyle \limsup _{n\rightarrow \infty }r_{B}(n)/\log n>0.}$

In 1986, Eduard Wirsing proved that a large class of additive bases, including the prime numbers, contains a subset that is an additive basis but significantly thinner than the original.[5] In 1990, Erdős and Prasad V. Tetali extended Erdős's 1956 result to bases of arbitrary order.[6] In 2000, V. Vu proved that thin subbases exist in the Waring bases using the Hardy–Littlewood circle method and his polynomial concentration results.[7] In 2006, Borwein, Choi, and Chu proved that for all additive bases ${\displaystyle B}$, ${\displaystyle f(n)}$ eventually exceeds 7.[8][9]