Take the 2-minute tour ×

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|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 mathoverflow.net/questions/54493/… –  quid Feb 14 '11 at 0:59

2 Answers 2

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


