Are there "natural" sequences with "exotic" growth rates? What metatheorems are there guaranteeing "elementary" growth rates?

Question

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...

Answer 1

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

Answer 2

This is most of all a comment on $\exp$-$\log$ growth rates, and a variation on the theme "$\exp (\log +1)$". Throughout, forf $m \in \mathbb{N}$, I write $\exp_m$ and $\log_m$ for the $m$-fold iteration of the exponential and (natural) logarithm.

---

There is a function $L:\mathbb{R}^{\geq 0} \rightarrow \mathbb{R}^{\geq 0}$ which is strictly increasing, analytic, and satisfies $L(0)=0$ and $L(\exp(r))=L(r)+1$ for all $r\geq 0$. By a theorem of Szekeres (Fractional iteration of exponentially growing functions), this function is unique if one imposes that $\lim_{r \to 0^+} (-r)^{k+1} L^{(k)}(r)=2 k!$ for all $k>0$. Using $L$ and its functional inverse $E$, one can define real iterates $\exp_s:=r\mapsto E(L(r)+s)$ of $\exp$ for all $s\geq 0$ (also for $s<0$ on $[s,+\infty)$). We have $\exp_{\frac{1}{2}} \circ \exp_{\frac{1}{2}} = \exp$ for instance.

I won't argue that $L$ is a very natural function. However its integer version $\log^*(n):=\max \{k \in \mathbb{N} \ : \ \exp_k(0)\leq n\}$ appears naturally in the computation of the complexity of algorithms, namely when a routine $A(n)$ inductively calls upon itself at $\log(n)$ to perform its task. In computer science usually one relies on base $2$ exponentials and logarithms but the two ways are similar. A real-life example is the best asymptotic bound known (Harvey and van der Hoeven - Faster integer multiplication using short lattice vectors) for algorithms to multiply two polynomials over $\mathbb{F}_p$, which is $u_n = n \log n (\frac{4}{\log 2})^{\log^*(n)}$ for $n>0$. One could replace $\log^*$ by $L$ in that formula.

So this gives two sequences $u=(u_n)_{n \in \mathbb{N}}$ and $v=(\exp_{\frac{1}{2}}(n))_{n \in \mathbb{N}}$ whose growth rates are not represented by $\exp$-$\log$ functions. For $u$ this a consequence of the fact that $\exp$-$\log$ functions form a field and each positive infinite one grows faster than some iterate of $\log$, contrary to $x\mapsto a^{L(x)}$. The claim for $v$ is a little harder to see, and it is helpful to study a cut in the growth orders of $\exp$-$\log$ functions.

---

Write $\mathcal{H}$ for the set of germs at $+\infty$ of functions definable on neighborhoods of $+\infty$ in the first order structure of real numbers with exponentiation. Then $\mathcal{H}$ is an ordered field under pointwise operations and comparisons on/of germs.

Moreover $\mathcal{H}$ embeds as an exponential field into the field $\mathbb{T}$ of $\log$-$\exp$ transseries (see van den Dries, Macintyre, and Marker - The elementary theory of restricted analytic fields with exponentiation). Elements in $\mathbb{T}$ are constructed by induction using $\exp$ and $\log$ as building blocks, which allows one to prove that those transseries which correspond to strictly increasing unbounded functions can be partitionned in various order of growth. Thus so can positive infinite elements of $\mathcal{H}$. The coarsest such partition is that any such $f$ satisfies $\log_n f \sim\log_n \mathfrak{d}(f)$ for all sufficiently large $n$, for a unique iterate of $\exp$ or $\log$.

This implies in particular that for $f \in \mathcal{H}$ with $\lim_{+\infty} f =+\infty$, we either have $\frac{1}{2}f\circ(\frac{1}{2} f)>\exp$ or $f$ is slower than a $\Psi_n:r \mapsto \exp_n(\log_n(r)+1)$, where $\Psi_n$ is defined for sufficiently large $r$. So $\Psi_0$ is a translation, whereas $\Psi_1$ is an homotethy, and $\Psi_2$ is a power function. For $n\geq 3$, I don't think that $\Psi_n$ has a standard name, but it grows faster than any polynomial while all its iterates are still slower than $\Psi_{n+1}$.

Thus one way to find non-elementary growth rates is to find things that are intermediate between all $\Psi_n$'s and $\exp$. Using this one shows that the growth rate of $v$ is not in $\mathcal{H}$.

---

As a simpler application, consider the sequence $w$ given by $w_n:=\Psi_{\log^*(n)}(n)$ for all $n\geq 0$. Then $w$ is increasing and we have $w_n\geq\Psi_k(n)$ for all $n\geq \exp_k(0)$. So the growth order of $w$ is greater than all $\Psi_n$'s. However $w_{\left\lfloor w_n \right\rfloor}\leq \exp(n)$ for large enough $n$, which implies that the growth order of $w$ cannot correspond to an element of $\mathcal{H}$.

One can probably show that $w_n$ is much smaller than $v_n$ for large enough $n$, but I don't have a proof right now.

Answer 3

It's possible that this example is ruled out by your proviso regarding oscillatory behavior, but the dance marathon problem gives rise to a function that you might naïvely think converges to a limit, but actually oscillates. To briefly recap, we have $n$ independent fair coins and we flip them; we remove all the heads, and recurse, until we have either no heads or exactly one head. What is the probability that we terminate with exactly one head?

At minimum, this example shows that naturally occurring processes that one might expect to exhibit tame behavior are not necessarily tame, and so any metatheorem that you might hope to prove has to take such phenomena into account.

Answer 4

nombre mentioned the work by van den Dries, Macintyre and Marker on transseries, but it seems no one has mentioned the paper Logarithmic-exponential power series by the same authors, in which they proved:

The compositional inverse to $x\mapsto(\log x)(\log\log x)$ is not asymptotic to a composition of semialgebraic functions, log and exp.

confirming a conjecture of Hardy. Denote the inverse by $f(x)$. They mentioned in the paper that $e^{f(x)}$ had been shown to have non-elementary growth rate by Shackell. Also $f(x)=e^{e^{W(x)}}$ if my algebra is right.

This is a real function instead of an integer sequence, but $\lfloor f(n)\rfloor$ should work since $\lim_{n\rightarrow\infty}\frac{f(n+1)}{f(n)}=1$, so if $\lfloor f(n)\rfloor$ were asymptotic to $g(n)$ for some elementary function $g$, then $f(x)$ would be asymptotic to $g(x)$ (using the fact that $g(x)$ must be eventually increasing, mentioned in an answer to your old question).

I realized that I completely ignored trignometric functions; fortunately you also excluded them in your question. It seems even just adding $\cos x$ makes the situation a lot more complicated. In A Simple Example for a Theorem of Vijayaraghavan, the authors showed that for any $\phi:[0,\infty)\rightarrow\mathbb{R}$, there exists a suitable irrational number $\alpha$ such that $\frac{1}{2-\cos x-\cos\alpha x}$ is greater than $\phi$ on a sequence that tends to infinity.

Answer 5

A broad class of examples like this comes from statistical physics, at least if strange real numbers as exponential growth rates qualify. For example the free energy of the Ising model is the the exponential growth rate of a certain sequence of positive numbers. The Ising model can be constructed with various parameters and the free energies are nonelementary functions of the parameters.

• In one dimension the free energy is given for real parameters $\beta,J$ and $h$ by

\begin{equation} -\frac{1}{\beta} \log\left(e^{\beta J} \cosh(\beta h) + \sqrt{e^{2\beta J} \sinh^2(\beta h) + e^{-2\beta J}} \right)\end{equation}

• In two dimensions the free energy is given in various cases by integrals of hyperbolic trigonometric functions that have no known simpler form.

• In three dimensions there are results related to theoretical incomputability of free energies.

For more advanced statistical physics models the free energies are even less likely to be elementary functions of the parameters. However, the one of the first things that is usually done in the mathematical approach to a statistical physics model is to prove that the free energy is well defined in a sense that the relevant sequence of positive numbers has an exact exponential growth rate for each fixed value of the parameters.

Answer 6

For every polycyclic group of exponential growth and finite symmetric generating subset $S$ containing $1$, the reciprocal $1/p_n$ of the probability of return, that is, the probability $p_n$ of hitting $1$ after $n$ steps of a random walk ($X_0=1$, $X_{n+1}=X_ns_n$ with, say, $s_n$ iid uniform on $S$) is $$\simeq \exp(n^{1/3}).$$

This applies in particular to every semidirect product $\mathbf{Z}^d\rtimes_A\mathbf{Z}$ as soon as the matrix $A\in\mathrm{GL}_d(\mathbf{Z})$ has at least one eigenvalue that is not a root of unity.

The same estimate also holds for several known amenable groups, such as Baumslag-Solitar groups $\mathrm{BS}(1,n\ge 2)$, lamplighter groups (finite $\neq 1$)$\,\wr\,\mathbf{Z}$. Actually, this is the asymptotic lower bound for the probability of return of among all groups with exponential growth (for context, a group is non-amenable iff $1/p_n$ grows exponentially).