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. Wellknown additive bases of finite order include the Waring bases ($\mathbb{N}^k$ for some $k > 0$) and the primes (GoldbachShrinel'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 wellknown 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.
Take the 2minute tour
×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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}$). 


Well, there aren't terribly many wellknown 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. 

