6
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ 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. $\endgroup$ Feb 14, 2011 at 0:36
  • 2
    $\begingroup$ 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$ $\endgroup$ Feb 14, 2011 at 0:52
  • 1
    $\begingroup$ @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/… $\endgroup$
    – user9072
    Feb 14, 2011 at 0:59

2 Answers 2

7
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Then, $f(n)\sim n/2$. $\endgroup$ Feb 14, 2011 at 13:47
  • 1
    $\begingroup$ 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)$. $\endgroup$
    – dankane
    Jun 12, 2011 at 3:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.