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<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.

  • $\begingroup$ 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)$? $\endgroup$ Jan 12 '11 at 21:34
  • $\begingroup$ 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. $\endgroup$
    – GH from MO
    Jan 13 '11 at 18:52
  • $\begingroup$ 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. $\endgroup$ Feb 6 '11 at 22:59
  • $\begingroup$ As long as various analogs such as sets of integers are concerned: it is known (arxiv.org/abs/0901.1649) 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.) $\endgroup$
    – Seva
    Feb 7 '11 at 21:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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