Gruntz algorithm

An algorithm for limits of exp-log functions, built from x and constants by arithmetic, exp and log, as x tends to infinity. It finds the most rapidly varying subexpressions, rewrites the function as a series in one of them, and reads the limit off the leading term, recursing when that term is itself a function of x.

Functions tending to 0 or $\infty$ are compared through their logarithms. $f$ is more rapidly varying than $g$ , written $f ≻ g$ , when

x \to \infty lim \frac{lo g ∣ f ( x ) ∣}{lo g ∣ g ( x ) ∣} = \pm \infty

and they are in the same comparability class, $f ≍ g$ , when the limit is finite and nonzero. So $x ≺ e^{x} ≍ e^{2 x} ≺ e^{e^{x}}$ : every power of $x$ is in one class, $e^{x}$ and $e^{2 x}$ are in another above it, and $e^{e^{x}}$ is above both.

For $lim_{x \to \infty} f (x)$ :

The algorithm.

1. Compute the MRV set: the subexpressions of f in the highest comparability class.
2. Pick w in that class with w -> 0, and rewrite each element of the set as A * w^c,
   with A in a lower class.
3. Expand f as a series in w:  f = c0 * w^e0 + ...,  the ci functions of lower class.
4. e0 > 0: the limit is 0.   e0 < 0: it is +-infinity, with the sign of c0.
   e0 = 0: it is the limit of c0, computed by the same algorithm.

The recursion ends because each step moves to a strictly lower class. An example from Gruntz's thesis:^[1]

x \to \infty lim e^{x} (e^{1/ x - e^{- x}} - e^{1/ x})

The MRV set is ${e^{x}, e^{- x}}$ . Take $ω = e^{- x}$ , so $e^{x} = ω^{- 1}$ , and expand:

f = ω^{- 1} e^{1/ x} (e^{- ω} - 1) = ω^{- 1} e^{1/ x} (- ω + \frac{1}{2} ω^{2} - \dots) = - e^{1/ x} + \frac{1}{2} e^{1/ x} ω - \dots

The leading exponent is 0, so the limit is that of $c_{0} = - e^{1/ x}$ , which is $- 1$ .

f(x) evaluated at 80 significant digits.

x = 10    -1.1051458311
x = 20    -1.0512710953
x = 40    -1.0253151205
x = 80    -1.0125784515

An expansion in powers of $1/ x$ cannot do this. Since $e^{- x}$ is smaller than every power of $1/ x$ , the bracket expands to zero at every order in $1/ x$ , and the factor $e^{x}$ that makes the product finite is invisible. The series has to be taken in the most rapidly varying quantity, which is what the MRV set provides. The algorithm also has to decide whether the leading coefficient $c_{0}$ is identically zero, the same zero-equivalence problem that limits the Risch algorithm.