1

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]$?

Sebastien Palcoux
  • 25,922
  • 1
    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
  • 1
    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
  • @FeldmannDenis: the set $S$ of functions generated by $\ln$ and $\exp$ for the $4$ operations above is not a countable set, because the first operation (with $\alpha, \lambda >0$) can generate continuously many functions. Nevertheless, perhaps the result of Hardy works for $S$ also. – Sebastien Palcoux Oct 24 '15 at 20:21
  • Sure，but they are all dominated by one of the functions exp, exp o exp, exp o exp o exp, etc. – Feldmann Denis Oct 24 '15 at 20:33
  • @FeldmannDenis: you're right. A good way to avoid this phenomenon is to restrict to functions which can be dominated by a $\exp \circ \cdots \circ \exp$. I will improve that. Do you know if there is a name for such functions? – Sebastien Palcoux Oct 24 '15 at 20:41
  • @FeldmannDenis: that's it! – Sebastien Palcoux Oct 24 '15 at 20:55
  • 2
    Here's a buzzphrase that you can google with: Hardy field. E.g., https://en.wikipedia.org/wiki/Hardy_field – Todd Trimble Oct 24 '15 at 23:22
  • @ToddTrimble: the notion of Hardy fields seems match with what I'm looking for. In your interesting answer http://mathoverflow.net/a/45368/34538 what you call log-exp class should correspond nearly to what I call the representative for $\sim$ on $E$ generated by the set ${ exp, ln }$ for the $4$ operations above. In your answer, you believe the existence of "intermediate", i.e. if I'm not mistaken, of asymptotic which can't be represented by an element generated by ${ exp, ln }$. Did you find such an intermediate? – Sebastien Palcoux Oct 25 '15 at 09:44
  • @ToddTrimble: moreover it is not clear to me that one answer of the post http://mathoverflow.net/q/45284/34538 can answer my post (after smoothing) because I've this monotonicity assumption on every order $n$ derivative of $f$. – Sebastien Palcoux Oct 25 '15 at 10:29
  • I'll have to review some of the literature I'm aware of before getting back to you on intermediates. Regarding monotonicity: wouldn't a more natural condition be eventual monotonicity, i.e. for every $f \in E$ and $n \in \mathbb{N}$ there exists $x$ such that $f^{(n+1)}$ never changes sign ${-, 0,+}$ past $x$? That would be more parallel with your condition: $f(x) > 0$ for all sufficiently large $x$. – Todd Trimble Oct 25 '15 at 12:11
  • @ToddTrimble: yes, "eventually monotonic" is more natural because then there is no more abuse of notation in the $4$ operations. I've improved that. – Sebastien Palcoux Oct 25 '15 at 13:19
  • Similar to the exp o exp o exp o... problem, if f is one of your function something like f *( ln o ln o ln ...) (with suitable domain conditions, of course, and taking enough (depending of x) iterates) will eventually dominate f, but be dominated by all functions of S (this is mostly Hardy construction, you have to smooth it, but I dont think this would be so hard) – Feldmann Denis Oct 25 '15 at 15:01
  • Sorry, I meant f * ln * (ln o ln)* (ln o ln o ln)...,, of course – Feldmann Denis Oct 25 '15 at 15:09
  • @FeldmannDenis: I don't understand the details of your comment, how it can <<eventually dominate $f$, but be dominated by all functions of $S$>> because $f$ is an element of $S$ ($S$ is now noted $E$). – Sebastien Palcoux Oct 25 '15 at 15:36
  • @FeldmannDenis: What I guess is that there exists an element $h \in E$ which is eventually dominated by $\ln, \ln \circ \ln$, $\ln \circ \ln \circ \ln, \dots$, but even if we restrict the definition of $E$ to functions $f$ which eventually dominates a $\ln \circ \cdots \circ \ln$, then a function like $ln \cdot h$ will be still in $E$ but not in the set generated by ${ \ln, \exp}$. Perhaps it is what Todd Trimble call "intermediates". It is not clear to me if it is the end of the story, or if there is a way to improve for avoiding that. I need to think. – Sebastien Palcoux Oct 25 '15 at 15:37

1 Answers1

2

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 [68] 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).

Todd Trimble
  • 52,336
  • 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
  • @ToddTrimble: is it true that such a non-LE-asymptotic is the smallest (or the biggest) asymptotic dominating (resp. dominated) by a sequence of LE-asymptotic? If so, these counter-examples could be seen as "irrational asymptotics" (in analogy with irrational numbers). – Sebastien Palcoux Oct 25 '15 at 18:02
  • I doubt it. It sounds suspiciously close to trying to complete a non-archimedean field, which can't be done. I'd have to think on it to be sure. – Todd Trimble Oct 25 '15 at 18:12