Erdős–Tetali theorem

A natural question is whether similar results apply for functions other than log. That is, fixing an integer ${\displaystyle h\geq 2}$, for which functions f can we find a subset of the natural numbers ${\displaystyle {\mathcal {B}}\subseteq \mathbb {N} }$ satisfying ${\displaystyle r_{{\mathcal {B}},h}(n)=\Theta (f(n))}$? It follows from a result of C. Táfula (2018)[10] that if f is a locally integrable, positive real function satisfying

• ${\displaystyle {\frac {1}{x}}\int _{1}^{x}f(t)\,\mathrm {d} t=\Theta (f(x))}$, and
• ${\displaystyle \log(x)\ll f(x)\ll x^{\frac {1}{h-1}}\log(x)^{-\varepsilon }}$ for some ${\displaystyle \varepsilon >0}$,

then there exists an additive basis ${\displaystyle {\mathcal {B}}\subseteq \mathbb {N} }$ of order h which satisfies ${\displaystyle r_{{\mathcal {B}},h}(n)=\Theta (f(n))}$. While improvements to the upper bound for f can be reasonably expected (e.g. it is unclear whether the ${\displaystyle \log(x)^{-\varepsilon }}$ is necessary), any improvements to the lower bound would produce a counterexample to the strong version of Erdős–Turán (see below for details).

All the known proofs of Erdős–Tetali theorem are, by the nature of the infinite probability space used, non-constructive proofs. However, Kolountzakis (1995)[11] showed the existence of a recursive set ${\displaystyle {\mathcal {R}}\subseteq \mathbb {N} }$ satisfying ${\displaystyle r_{{\mathcal {R}},2}(n)=\Theta (\log(n))}$ such that ${\displaystyle {\mathcal {R}}\cap \{0,1,\ldots ,n\}}$ takes polynomial time in n to be computed. The question for ${\displaystyle h\geq 3}$ remains open.

Given an arbitrary additive basis ${\displaystyle {\mathcal {A}}\subseteq \mathbb {N} }$, one can ask whether there exists ${\displaystyle {\mathcal {B}}\subseteq {\mathcal {A}}}$ such that ${\displaystyle {\mathcal {B}}}$ is an economical basis. V. Vu (2000)[12] showed that this is the case for Waring bases ${\displaystyle \mathbb {N} ^{\wedge }k:=\{0^{k},1^{k},2^{k},\ldots \}}$, where for every fixed k there are economical subbases of ${\displaystyle \mathbb {N} ^{\wedge }k}$ of order ${\displaystyle s}$ for every ${\displaystyle s\geq s_{k}}$, for some large computable constant ${\displaystyle s_{k}}$.

The original Erdős–Turán conjecture on additive bases states, in its most general form, that if ${\displaystyle {\mathcal {B}}\subseteq \mathbb {N} }$ is an additive basis of order h then ${\displaystyle r_{{\mathcal {B}},h}(n)\neq O(1)}$. Nonetheless, in his 1956 paper on the case ${\displaystyle h=2}$ of Erdős–Tetali, P. Erdős asked whether it could be the case that actually ${\displaystyle r_{{\mathcal {B}},2}(n)\neq o(\log(n))}$ whenever ${\displaystyle {\mathcal {B}}\subseteq \mathbb {N} }$ is an additive basis of order 2. The question naturally extends to ${\displaystyle h\geq 3}$, making it a way stronger assertion than that of Erdős–Turán. In some sense, what is being conjectured is that there are no additive bases substantially more economical than those guaranteed to exist by the Erdős–Tetali theorem.