It is somewhat miraculous to me that even very complicated sequences $a_n$ which arise in various areas of mathematics have the property that there exists an elementary function $f(n)$ such that $a_n = \Theta(f(n))$ or, even better, $a_n \sim f(n)$. Examples include
- Stirling's approximation $n! \sim \sqrt{2\pi n} \left( \frac{n}{e} \right)^n$ (and its various implications),
- The asymptotics of the partition function $p_n \sim \frac{1}{4n \sqrt{3}} \exp \left( \pi \sqrt{ \frac{2n}{3} } \right)$,
- The prime number theorem $\pi(n) \sim \frac{n}{\log n}$,
- The asymptotics of the off-diagonal Ramsey numbers $R(3, n) = \Theta \left( \frac{n^2}{\log n} \right)$.
What are examples of sequences $a_n$ which occur "in nature" and which provably don't have this property (either the weak or strong version)? Simpler examples preferred.
(I guess I should mention that I am not interested in sequences which don't have this property for computability reasons, e.g. the busy beaver function. I am more interested in, for example, natural examples of sequences with "half-exponential" asymptotic growth.)
Best Answer
Since this is community wiki, I won't feel that bad about not offering any crisp answers, but more of an abstract point of view which might suggest another avenue of pursuit.
To me the basic subject matter goes by the name "Hardy fields": fields of germs of real-valued functions at infinity. One of the basic examples is the field of germs of all functions that can be built up from polynomials, exponentials, and logarithms, and closed under the four arithmetic operations and composition.
A wonderful fact is the trichotomy law: that such "log-exp functions" are either eventually positive, eventually zero, or eventually negative. This is perhaps along the lines of the monotonicity assumptions Qiaochu mentioned above. It guarantees that the germs at infinity of such functions do indeed form a field $K$. Sitting inside the field is a valuation ring consisting of germs of bounded functions, $O$. There is a corresponding valuation on $K$ whose value group is $K^\ast/O^\ast$.
The elements of $K^\ast/O^\ast$ may be called "rates of growth". Indeed, two germs of functions $[f]$, $[g]$ are equivalent mod $O^\ast$ iff both $f/g$ and $g/f$ are bounded, which is to say they are asymptotic (up to a constant) -- remember that by trichotomy, these bounded functions do not oscillate but tend to a definite limit.
From this point of view, we are interested in naturally arising Hardy fields whose value groups strictly contain the value group of the log-exp class mentioned above (so that we get "intermediate rates of growth").
The reason I mention all this is that I think there is a pretty big literature on constructions of Hardy fields (which unfortunately I am not very familiar with). One area of research is via model theory and particularly o-minimal structures, where o-minimality guarantees the trichotomy law above. There are experts out there (for example, David Marker, if he's listening) who may be able to give us "natural" examples of o-minimal structures with such intermediate rates of growth at infinity. I'd be interested in this myself.
Edit: And now that I've written this, I have a memory that there are theorems in o-minimal structure theory which tend to rule out such intermediate rates of growth! That in itself would be interesting, and anyhow maybe someone like David Marker would know some interesting examples anyway, whether from o-minimal structure theory or not.