## Arbitrarily thin additive bases of the natural numbers

A subset $A$ of $\mathbb{N}$ is called a basis of order $k$ if the set $kA$ = {$a_1 + \cdots + a_k | a_1, \cdots, a_k \in A$} $= \mathbb{N} \setminus C$, where $C$ is a finite set of positive integers. Let $r_{k,A}(N)$ be the number of representations of $N$ as a sum of $k$ (not necessarily distinct) elements of $A$. Erdos proved the following theorem in 1956:

There exists a basis $B \subset \mathbb{N}$ such that $r_{2,B}(N) = \Theta (\log(n))$ for every sufficiently large $n$.

In 1990, together with Tetali, he proved the following generalization.

For any fixed $k \in \mathbb{N}$, there exists a basis $B \subset \mathbb{N}$ such that $r_{k,B}(N) = \Theta (\log(n))$.

Now my question is, can there be any 'thinner' bases? That is, can we improve on the $\log(n)$ in the above theorems? Erdos and Turan conjectured that $\limsup_{n \rightarrow \infty} r_{2,B}(n) = \infty$ and later Erdos conjectured that $\limsup_{n \rightarrow \infty} r_{2,B}(n)/\log(n) > 0$ for any basis $B$ of order 2, suggesting that the answer is that one cannot really improve on the $\log(n)$. Are there are progress in this direction, either positive or negative?

-

As far as I know, one can achieve $r_{2,B}(n) \sim c \log(n)$, which is stronger than big-theta. I'm certain that nobody has beaten the logarithmic barrier in this problem, though.
Regarding the Erdos-Turan conjecture, essentially nothing is known except for a few factoids that rule out certain approaches. For example, there are some results showing that that $\limsup$ must be at least 6, and I wouldn't be surprised if a reasonable computation could push that up to 10 or 12 (the name Grekos comes to mind, but I'm not certain of his involvement). There has also been progress of the sort of proving and disproving various analogs (sets of integers, for example, instead of sets of naturals, or replace addition with some other binary function), Nathanson, Hegarty and others have worked on this sort of analog.
Edit: The result I was thinking of was one of Cassels', which isn't what I recalled. Cassels proved that there is a basis $\{b_1 -  Yes Nathanson showed in quite a spectacular fashion that the Erdos-Turan Conjecture does not hold for the set of all integers, in fact given any arithmetic function$f(n)$one can find a basis$B$for the integers such that$r_{2,B}(n)=f(n)$for all$n$. Also, Borwein and Choi showed that the limsup cannot be bounded by 6. Can you give a reference for the$r_{2,B}(n) \sim c \log(n)$? – Stanley Yao Xiao Jan 12 2011 at 21:34 I believe it is not even known that positive constants$c$and$C$exist arbitrarily close to each other such that$c\log n