MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question

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<b_2<...\}$ of order 2 with $b_n = \beta n^2 +O(n)$. That is, the set grows extremely smoothly, but perhaps not the representation function.

share|cite|improve this answer
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 '11 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<f(n)<C\log n$ for a suitable $A$ and all sufficiently large $n$. This is an open problem of Erdős if I remember. – GH from MO Jan 13 '11 at 18:52
Indeed it is not clear from the way that proofs were constructed how one can show that $c, C$ can be made arbitrarily close. Indeed, the proof relies on them being far apart in order to apply the Borel-Cantelli Lemma. – Stanley Yao Xiao Feb 6 '11 at 22:59
As long as various analogs such as sets of integers are concerned: it is known ( that every infinite abelian group which does not have ``enormously many'' involutions, possesses a perfect basis; that is, a basis such that every group element has exactly one representation as a sum of two elements of the basis. (Well, with just one exception: the direct sum of a group of exponent $3$ and the group of order $2$ does not have a perfect basis, but has a basis such that every group element has either one, or two representations.) – Seva Feb 7 '11 at 21:13

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.