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

For $A \subset \mathbb{N}$ and positive integer $h > 0$, define $r_{A,h}(n)$ to be the number of ways to write $n$ as the sum of $h$ (not necessarily distinct) elements of $A$. We say $A$ is an additive basis of order $h$ if $r_{A,h}(n) > 0$ for all $n$ sufficiently large. Well-known additive bases of finite order include the Waring bases ($\mathbb{N}^k$ for some $k > 0$) and the primes (Goldbach-Shrinel'man Theorem, the $h = 4$ case known as Vinogradov's Theorem). In both cases, the COUNTING function for $A$, which is the function $f(n) = |A \cap [1,n]|$, is quite regular. In particular, for the Waring bases we have $f(n) \sim n^{1/k}$ and for the primes we have $f(n) = \pi(n) \sim \frac{n}{\log(n)}$ (Prime Number Theorem). My question is are there any well-known cases where $f(n)$ is very irregular? In other words there exists some function $g(n)$ and constants $0 < c_1 < c_2 < 1$ such that $\displaystyle \liminf_{n \rightarrow \infty} f(n)/g(n) < c_1, \limsup_{n \rightarrow \infty} f(n)/g(n) > c_2$. I am interested in naturally occurring examples, and less interested in a specific construction of a basis with this property (that shouldn't be too difficult, though I have not tried yet). In particular, whether this property is worthy of serious study.

share|cite|improve this question
Are you sure that you want to allow repeats? Then if you have 1 in the set or $a,b$ with $\gcd(a,b)=1$ then you already have an additive basis so you can do whatever you wish after that. – Aaron Meyerowitz Feb 14 '11 at 0:36
How about numbers whose first decimal digit is a 1? (a basis of order 6) Then the counting function varies between $n/9$ and $5n/9$ – Anthony Quas Feb 14 '11 at 0:52
@Aaron Meyerowitz: note that the number of elements one is allowed to sum is fixed (it is specified by h). Though analog question could be asked for distinct summands too, both make sense (and are studied); in fact there is a recent question of the OP sort-of comparing the two notions, see… – user9072 Feb 14 '11 at 0:59

I guess the very natural example of numbers whose base 3 expansions have only 0's and 1's (a basis of order 2) has the property you mention (taking $g(n)$ to be $n^{2/3}$).

share|cite|improve this answer

Well, there aren't terribly many well-known sequences for which f(n) is irregular. You could always go with something like the set of integers with an odd number of digits in its binary representation.

share|cite|improve this answer
Then, $f(n)\sim n/2$. – Kevin O'Bryant Feb 14 '11 at 13:47
No. $f(4^n) = 1+(1+4+4^2+...+4^{n-1})\sim 4^n/3$. $f(2*4^n) = 1+4+4^2+...+4^n \sim 2*4^n*(2/3)$. – dankane Jun 12 '11 at 3:27

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.