# A classification of (reasonable) asymptotics

Notations: "eventually" means "for $x$ sufficiently large"; "positive" means "strictly positive".

Let $\exp_1 = \exp$ and $\exp_{n+1} = \exp_n \circ \exp$.

Let $E$ be the set of smooth function $f: \mathbb{R}_{>0} \to \mathbb{R}$ such that $f$ and $f'$ are eventually positive, every order $n$ derivative $f^{(n)}$ is eventually monotonic, and $\exists r$ with $\lim_{x\to\infty} \frac{f(x)}{\exp_{r}(x)} = 0$ ($r$ depends on $f$).

Let the following operations on $E$ (which are eventually well-defined):

• $f \to \lambda f^{\alpha}$ for $\lambda, \alpha >0$
• $(f,g) \to f \cdot g$
• $(f,g) \to f \circ g$
• $(f,g) \to g/f$ if $\lim_{x\to\infty} \frac{f(x)}{g(x)} = 0$

Let the equivalence relation on $E$ defined by $f \sim g \Leftrightarrow \lim_{x\to\infty} \frac{f(x)}{g(x)} = 1$, i.e. $f$ and $g$ have the same asymptotic.

Question: What is a minimal subset of $E$ generating, for the $4$ operations above, a complete set of representatives for $\sim$ on $E$? Is the subset $\{\exp,\ln\}$ working? (we don't need $x$ because $x = e^{ln(x)}$)

Bonus question: is it true that $\forall f,g \in E$, $\lim_{x\to\infty} \frac{f(x)}{g(x)}$ exists and is in $[0, \infty]$?

• Composition is not well-defined: if $f(x)=\exp(x)$, $g_1(x)=x$, $g_2(x)=x+\sqrt{x}$, then $g_1\sim g_2$ but $f\circ g_1\nsim f\circ g_2$. – YCor Oct 24 '15 at 18:22
• @YCor: you're right, I must improve that. – Sebastien Palcoux Oct 24 '15 at 18:53
• @YCor: that's it! – Sebastien Palcoux Oct 24 '15 at 19:03
• Work by Hardy and others at the turn of the century show that for any denumerable set of functions, there exists one which dominates asymptotically all functions in the set ; it should then be reasonably easy to smooth it.... – Feldmann Denis Oct 24 '15 at 20:04
• Here's a buzzphrase that you can google with: Hardy field. E.g., en.wikipedia.org/wiki/Hardy_field – Todd Trimble Oct 24 '15 at 23:22

Some relevant background (all this can be found in a survey by Aschenbrenner and van den Dries on aymptotic differential algebra): the closure of $\exp, \log$ and real constants under field operations and composition is called the class of logarithmic-exponential functions, or LE-functions for short. It is a fundamental example of a Hardy field, which by definition is a subalgebra of the algebra of germs at infinity of $C^\infty$ functions that (1) forms a field, and (2) is closed under the derivative operation $f \mapsto f'$.

(Notes: (1) an LE-function is uniquely determined by its germ at infinity by analytic continuation. (2) In order for such a subalgebra $H$ of germs $[f]$ of functions $f$ to form a field, we need that each $f$ has eventually constant sign in $\{-,0, +\}$, and the same for all its derivatives by closure under differentiation. Hardy fields are thus ordered differential fields containing the field $\mathbb{R}$.)

We say that a (germ) $f$ is infinite if $|f|$ is not bounded above by any constant $r \in \mathbb{R}$.

Lemma: If $f$ defines an infinite germ in a Hardy field and $f'$ is (eventually) positive, then its compositional inverse $f^{-1}$ also belongs to a Hardy field (a larger one where $f^{-1}$ 1 is also infinite of course).

This is Theorem 1.7 in the linked reference by Aschenbrenner and van den Dries.

The question of the OP on whether every $f \in E$ is asymptotic to an LE-function is settled negatively by exhibiting a suitable LE-function $f$ whose compositional inverse is not asymptotic to an LE-function (suitable meaning that the growth rate of the inverse is not too extreme, as required in the OP). Hardy himself conjectured that $f(x) = (\log x)(\log \log x)$ should work. This was finally shown here:

• L. van den Dries, A. Macintyre, D. Marker, Logarithmic-exponential power series, J. London Math. Soc. 56 (1997), 417–434.

Another example of an $f$ that works is $f(x) = (\log \log x)(\log \log \log x)$, as shown by Shackell in 1993; see reference  in the survey. I've just now learned that Shackell has written a whole book in this area, titled Symbolic Asymptotics.

I've only done a little amateur dabbling in this area, and so I am absolutely in no position to give a full answer to the OP's question, but $E$ is quite enormous, and for what it's worth I doubt that any easily described set of functions generates (under algebraic operations and composition) the full set of asymptotic equivalency classes for $E$. See the cited survey for some useful information on various huge Hardy fields. One area of current interest is the nature of the intersection of all maximal Hardy fields (there's a Zorn's lemma argument that every Hardy field is contained in a maximal Hardy field); google the name Michael Boshernitzan for more on this.

As for the bonus question: for functions $f, g$ belonging to a Hardy field $H$, it's pretty much a triviality. Put $h = f/g$, and let $r = \limsup h(x) \in [0, \infty]$. That is, put $r = \inf_x \sup_{y \geq x} h(y)$. Then show $h(x)$ converges to $r$ by considering cases ($h$ eventually increasing, $h$ eventually decreasing, $h$ eventually constant). The trouble with the class $E$ of the OP is that it's not (I don't think) a Hardy field and hence isn't under very good algebraic control. For an example to consider, I'd think that something like $f(x) = \exp(\exp (x) + \sin (x))$ has all the derivative requirements of the OP [the $n^{th}$ derivative has a term $f(x)(e^x + \cos(x))^n$ which eventually dominates the other terms], and so does $g(x) = \exp(\exp (x))$, but the quotient $f/g$ has oscillatory behavior.

Edit: As pointed out by Gérard H.E. Duchamp in a comment below, Bourbaki also gave a nice treatment of Hardy fields (Functions of a Real Variable, published by Springer). In particular, the issue of compositional inverses is given in an appendix (paragraph 6).

• The lemma states that the composition inverse belong to a Hardy field but not necessarily the same, right? A counter-example (for my question on $\{\ln, \exp \}$) is the composition inverse of $f(x) = (\log x)(\log \log x)$ which is not a LE-function but still in $E$ (by this lemma), right? According to what you wrote, you don't expect that $E$ (or any reasonable improvement) can have a finite generating set, right? – Sebastien Palcoux Oct 25 '15 at 16:42
• @SébastienPalcoux Yes to both questions, absolutely. Actually it can be shown that that specific example of $f$ and its inverse do belong to a common Hardy field; one example would be the field of germs at infinity of functions which are definable (in first-order logic with equality) from the logical signature consisting of the field operations and constants on $\mathbb{R}$, an unary operation $\exp$, and the binary relation $<$. For this see the parts of the survey on o-minimal structures; the inverse of a definable $f$ is the relation defined by reflecting the graph of $f$ through $y=x$. – Todd Trimble Oct 25 '15 at 16:57
• @ToddTrimble Nice answer, thanks. You may improve the lemma [If $f$ is defines an infinite germ]-->[If $f$ defines an infinite germ] and [also belongs to a Hardy field (where it is also infinite of course)]-->[also belongs to a Hardy field (a larger one where $f^{-1}$ it is also infinite of course)]. For Hardy Fields, you can also add the reference of Bourbaki "Functions of a Real Variable, Springer" (the historical note is of interest). – Duchamp Gérard H. E. Oct 25 '15 at 17:19
• @DuchampGérardH.E. Thanks for the improvements; I'll edit in a bit. And yes, Bourbaki did work on this as well! It's a pretty subject. – Todd Trimble Oct 25 '15 at 17:21
• @ToddTrimble As regards Bourbaki, the question of compositional inverses is discussed in detail in the Appendix (HARDY FIELDS. (H) FUNCTIONS, paragraph 6). Yes, this is a fascinating subject. – Duchamp Gérard H. E. Oct 25 '15 at 17:28