A thing that consistently surprises me is that many "natural" sequences $f(n)$, even apparently very complicated ones, have growth rates which can be described by elementary functions $g(n)$ (say, to be precise, functions expressible using a bounded number of arithmetic operations, $\exp$, and $\log$), in the sense that $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 1$. I'll write $f \sim g$ for this equivalence relation. Here are some examples roughly in increasing order of how surprising I think it is that the growth rate is elementary (very subjective, of course).
- The Fibonacci sequence $F_n$ satisfies $F_n \sim \frac{\phi^n}{\sqrt{5}}$.
- The factorial $n!$ satisfies $n! \sim \sqrt{2\pi n} \left( \frac{n}{e} \right)^n$.
- The prime counting function $\pi(n)$ satisfies $\pi(n) \sim \frac{n}{\log n}$.
- The partition function $p(n)$ satisfies $p(n) \sim \frac{1}{4n \sqrt{3}} \exp \left( \pi \sqrt{ \frac{2n}{3} } \right)$.
- The Landau function $g(n)$ satisfies $\log g(n) \sim \sqrt{n \log n}$. I don't know whether or not it's expected that $g(n) \sim \exp(\sqrt{n \log n})$.
- For $p$ a prime, the number $G(p^n)$ of groups of order $p^n$ satisfies $\log_p G(p^n) \sim \frac{2}{27} n^3$.
I know some metatheorems guaranteeing elementary asymptotics for some classes of sequences. The simplest one involves sequences with meromorphic generating functions; this gives the Fibonacci example above as well as more complicated examples like the ordered Bell numbers. I have the impression that there are analogous theorems for Dirichlet series involving tauberian theorems that produce the PNT example and other similar number-theoretic examples. There's a metatheorem involving saddle point bounds which gives the factorial example and at least heuristically gives the partition function example. And I don't know any metatheorems relevant to the Landau function or $p$-group examples. So, questions:
Q1: What are some "natural" sequences $f(n)$ which (possibly conjecturally) don't have elementary asymptotics, in the sense that there are no elementary functions $g(n)$ such that $f(n) \sim g(n)$?
Right off the bat I want to rule out two classes of counterexamples that don't get at what I'm interested in: $f(n)$ may oscillate too wildly to have an elementary growth rate (for example $f(n)$ could be the number of abelian groups of order $n$), or it may grow too fast to have an elementary growth rate (for example $f(n)$ could be the busy beaver function). Unfortunately I'm not sure how to rigorously pose a condition that rules these and other similar-flavored counterexamples out. At the very least I want $f(n)$ to be a monotonically increasing unbounded sequence of positive integers, and I also want it to be bounded from above by an elementary function.
The kinds of sequences I'm interested in as potential counterexamples are sequences like the Landau function above, as well as combinatorial sequences like the Bell numbers $B_n$. The Bell numbers themselves might be a potential counterexample. Wikipedia gives some elementary bounds but expresses the growth rate in terms of the Lambert W function; it seems that the Lambert W function has elementary growth but I'm not sure if that implies that $B_n$ itself does.
Q2: What are some more metatheorems guaranteeing elementary growth rates? Are there good organizing principles here?
Q3: What are some "natural" sequences known to have elementary growth rates but by specific arguments that don't fall under cases covered by any metatheorems?
Apologies for the somewhat open-ended questions, I'd ask a tighter question if I knew how to state it.
Edit: Wow, apparently I asked almost exactly this question almost exactly $10$ years ago, and I even gave three of the same examples…
Best Answer
An interesting example is the enumeration of 2,3-trees here. The number $a_n$ of such trees with $n$ vertices satisfies $$ a_n\sim \frac{\phi^n}{n}u(\log n), $$ where $\phi=(1+\sqrt{5})/2$ and $u(x)$ is a positive nonconstant continuous function satisfying $u(x)=u(x+\log(4-\phi))$. The average value of $u(x)$ is $(\phi\log(4-\phi))^{-1}$.