Question

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.

Answer 1

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

Answer 2

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.