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

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

• scottaaronson.com/blog/?p=263 Nov 11, 2020 at 2:06
• This is too vague to be a real answer, but the theory of combinatorial species tells us that a lot of natural combinatorial constructions correspond to specific operations on (exponential) generating functions. So only certain kinds of generating functions typically arise, and then the methods of analytic combinatorics (as in the book by Flajolet and Sedgwick) tell us that the growth rates of the coefficients are going to be of a certain form. Nov 11, 2020 at 3:20
• Another vague comment is that Razborov's theory of flag algebras in some sense gives a "model-theoretic explanation" of nice formulas arising in asymptotic extremal combinatorics. Nov 11, 2020 at 3:32
• Should this be closed as a duplciate? Nov 11, 2020 at 4:56
• I'm not sure the following meet the criteria, so I'll leave a comment rather than an answer. oeis.org/A179386 tabulates records of minima of difference of a cube minus the next smaller square; by definition it's a monotonically increasing unbounded sequence of positive integers, oeis doesn't suggest any asymptotic formula. Similar remarks apply to oeis.org/A006884 – In the $3x+1$ problem, these values for the starting value set new records for highest point of trajectory before reaching $1$. Other "record value" sequences may qualify. Nov 11, 2020 at 9:20

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

• Thanks for the example! Sorry to be fussy, but I’d count this as a mild variation of the oscillatory examples I want to rule out. In other words I am basically happy to replace considering the growth rate with considering the average growth rate, for a pretty broad notion of “average.” Nov 11, 2020 at 18:38
• Ideally I’d like to be able to rigorously pose a question about “abstract growth rates” but I’m not sure how to state it precisely to get rid of all oscillations etc. so as to consider only “pure growth.” Nov 11, 2020 at 18:39

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.

• If I'm understanding the notation correctly, it seems that $\exp_k$ is a function. So, in the definition $\log^*(n) \mathrel{:=} \max \{k \in \mathbb N \mathrel: \exp_k \ge n\}$, what does the inequality $\exp_k \ge n$ mean? Jul 16, 2021 at 20:06
• @LSpice This was a typo: the intended term was $\exp_k(0)\leq n$. Thanks! Jul 16, 2021 at 21:43

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.

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.

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

$$$$-\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)$$$$

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

• Strange real numbers are nice but they're still elementary in the exp-log sense; I should have been more specific that arbitrary real constants are allowed also. Nov 12, 2020 at 2:22

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

• This is very nice but it’s elementary in the exp-log sense since $n^{1/3}$ can be written $\exp \left( \frac 13 \log n \right)$. Nov 11, 2020 at 18:31
• Sorry, I actually I hadn't noticed that you had asked for non-elementary asymptotics in this sense.
– YCor
Nov 11, 2020 at 19:21