most recent 30 from http://mathoverflow.net 2013-05-21T19:58:01Z http://mathoverflow.net/feeds/question/51852 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/51852/arbitrarily-thin-additive-bases-of-the-natural-numbers Stanley Yao Xiao 2011-01-12T16:03:00Z 2011-02-07T14:30:56Z

<p>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:</p> <p>There exists a basis $B \subset \mathbb{N}$ such that $r_{2,B}(N) = \Theta (\log(n))$ for every sufficiently large $n$. </p> <p>In 1990, together with Tetali, he proved the following generalization.</p> <p>For any fixed $k \in \mathbb{N}$, there exists a basis $B \subset \mathbb{N}$ such that $r_{k,B}(N) = \Theta (\log(n))$. </p> <p>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? </p>

http://mathoverflow.net/questions/51852/arbitrarily-thin-additive-bases-of-the-natural-numbers/51873#51873 Kevin O'Bryant 2011-01-12T21:11:26Z 2011-02-07T14:30:56Z

<p>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.</p> <p>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.</p> <hr> <p>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