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

Let $B \subset \mathbb{N}$ be an additive basis of order $h$. Define $r_{B,h}(n)$ to be the number of ways $n$ can be written as a sum of $h$ elements of $B$. In particular, $B$ is a basis of order $h$ if $r_{B,h}(n) > 0$ for all $n$. Erdos showed in 1956 that there exists a $B$ and constants $c_1, c_2 > 0$ such that $c_1 \log(n) \leq r_{B,2}(n) \leq c_2 \log(n)$. This was generalized to arbitrary $h$ in 1990 by Erdos and Tetalli. Their proof employed the probabilistic method and were existential. My question is, can an explicit example of a set $B$ be constructed and what would it look like? More specifically, can a 'prime number theorem' type result be proved about an Erdos thin basis? For example, is it possible to show that if $B$ is an additive basis such that $c_1 \log(n) \leq r_{B,h}(n) \leq c_2 \log(n)$, then there exists an 'explicit' function $f_h(n)$ such that $|B \cap [1,n]| \gg f_h(n)$?

We can see that if $B$ is a thin basis of order 2 constructed by the probabilistic method of Erdos, then the expected value of $|B \cap [1,n]|$ is equal to $\displaystyle \sum_{j=1}^n p_j$ where $p_j = c \displaystyle \sqrt{\frac{\log(j)}{j}}$ for some suitably chosen constant $c > 0$. Then $E[|B \cap [1,n]|] \sim 2\sqrt{n \log(n)}$ by partial summation. This provides a satisfactory answer for the latter question, at least for $h = 2$. However, this doesn't shed much insight on how to construct such a $B$ explicitly. In particular the 'obvious' candidate of {$\{\lfloor 4n \log(n) \rfloor : n \in \mathbb{N}\}$} is not likely to work since this set is too 'regular', likely leading to much more representations than $C \log(n)$ many for some $C > 0$.

share|cite|improve this question
Second question: if $r_{B,h}(n)>X$ then $B\cap [1,n]$ contains at least $\approx X^{1/h}$ elements by pigeonhole principle. As for the first question, I think the answer is that there are no known explicit constructions. – Boris Bukh Jan 23 '11 at 15:04
How about defining $r_{B,h}(n)$? – Anthony Quas Jan 23 '11 at 17:17
@Anthony: $r_{B,h}(n)$ is the number of ways $n$ can be written as a sum of $h$ elements from $B$. BTW I second Boris' response. – GH from MO Jan 23 '11 at 17:27
@GH. That's what I thought, but it doesn't agree with the the inequalities in the original posting. But I thunk there are plenty of bases e.g. the squares – Anthony Quas Jan 23 '11 at 17:35
@Anthony: The post was about special bases whose existence was proved by Erdős and Erdős-Tetalli. It is a famous problem going back to Sidon (I believe) to give a basis which is only "barely a basis", the post is about these guys. Am I missing something? – GH from MO Jan 23 '11 at 18:02

Your Answer


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

Browse other questions tagged or ask your own question.