Gruntz algorithm

The Gruntz algorithm computes limits of exp-log functions at infinity^[1]. Limits at a finite point reduce to this case by substituting $x=a+1/t$ or $x=a-1/t$, and many special functions can be handled by rewriting them in exp-log form. Earlier limit procedures expanded the function in powers of $1/x$, which fails whenever an exponentially small term decides the answer. Gruntz's method, from his 1996 thesis at ETH Zürich^[1], instead expands in the most rapidly varying subexpression, using the comparability classes of Hardy's orders of infinity^[2]. The recursion terminates because each step moves to a strictly lower class. It is used by SymPy's limit and was developed for Maple; related methods based on multiseries and transseries give full asymptotic expansions^[3][4][5].

The bracket is the difference of two numbers that agree to about $x{\log }_{10}e$ decimal digits, multiplied by a number that large. Evaluating it in floating point loses all accuracy once $x$ is a few tens, and expanding in powers of $1/x$ gives zero at every order. The answer depends only on $e^{-x}$, which is smaller than every power of $1/x$.

     x                  direct           in terms of w
     1       -2.27434683020919       -2.27434683020919
     5       -1.21729711102195       -1.21729711102194
    10       -1.10514583111641       -1.10514583111427
    20       -1.05127117037794       -1.05127109529261
    30       -1.03457307555225       -1.03389511351353
    36      -0.957285705619525       -1.02816717743771
    40                       0       -1.02531512052443
   100                       0       -1.01005016708417
   700                       0       -1.00142959232282

Functions tending to 0 or $\infty$ are compared through their logarithms^[1][2]. $f$ is more rapidly varying than $g$, written $f\succ g$, when

and they are in the same comparability class, $f\asymp g$, when the limit is finite and nonzero. A function tending to a finite nonzero constant is in the lowest class, below all others. So $\log x\prec x\prec e^x\asymp e^{2x}\prec e^{x^2}\prec e^{e^x}$: every power of $x$ is in one class, $e^x$, $e^{-x}$ and $x{e}^x$ are in the class above it, and $e^{e^x}$ is above both. Exp-log functions form a Hardy field, in which any two functions are eventually comparable, so these limits always exist in $[-\infty ,\infty ]$^[2].

The MRV set $\mathrm{mrv}(f)$ is the set of subexpressions of $f$ in the highest comparability class present. It is computed recursively: for $f=gh$ or $g+h$, compare the classes of $\mathrm{mrv}(g)$ and $\mathrm{mrv}(h)$ and keep the higher, or their union if they are equal; for $e^g$ with $g\to \pm \infty$, compare $\{e^g\}$ with $\mathrm{mrv}(g)$. Each comparison is itself a limit of a smaller expression, computed by the same algorithm^[1].

For ${\lim }_{x\to \infty }f(x)$^[1]:

1. Compute $\Omega =\mathrm{mrv}(f)$. If $x\in \Omega$, substitute $x\mapsto e^x$, which moves every class up one level without changing the limit, and start again.

2. Choose $\omega$ in the class of $\Omega$ with $\omega \to 0$, of the form $e^h$. Every element $e^g$ of $\Omega$ can then be written $e^g=A{\omega }^c$ with $c=\lim g/h$ and $A=e^{g-ch}$ in a strictly lower class.

3. Substitute these into $f$ and expand as a power series in $\omega$, treating the lower-class expressions as constants:

4. If $e_0>0$ the limit is 0; if $e_0<0$ it is $\pm \infty$, with the sign of $c_0$; if $e_0=0$ it is $\lim c_0$, computed recursively. The coefficient $c_0$ lies in a lower class than $\omega$, so the recursion terminates.

For the example above, the MRV set is $\{e^x,e^{-x}\}$. Take $\omega =e^{-x}$, so $e^x={\omega }^{-1}$, and $e^{1/x}$, which tends to 1, is in a lower class. Expanding,

The leading exponent is 0, so the limit is that of $c_0=-e^{1/x}$, which is $-1$. The rewritten form is also what the demo evaluates in its second column, and it is accurate for every $x$.

For $\lim x^{1/x}=\lim e^{\log (x)/x}$, the MRV set is $\{x\}$, so the algorithm substitutes $x\mapsto e^x$ and obtains $e^{x{e}^{-x}}$. Now $\omega =e^{-x}$ and

with leading exponent 0 and $c_0=1$, so the limit is 1.

An expansion in powers of $1/x$ cannot find the first limit. 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. Older limit procedures based on such expansions, or on heuristics like repeated l'Hôpital's rule, either failed or returned wrong answers on such inputs^[1]. The series has to be taken in the most rapidly varying quantity, which is what the MRV set provides; more generally, asymptotic expansions of exp-log functions are multiseries in several scales, or transseries^[3][5].

The algorithm has to decide whether the leading coefficient $c_0$ is identically zero, and whether constants such as the $c$ in step 2 are zero. If a zero coefficient is mistaken for a nonzero one, the answer is wrong. For exp-log expressions over $\mathbb{Q}$ this reduces to deciding whether exp-log constants are zero, which is not known to be decidable; Richardson showed that related problems for richer classes of functions are undecidable^[6]. Gruntz's algorithm is therefore complete relative to a zero-equivalence oracle, the same limitation as the Risch algorithm. In practice systems use normal forms and numerical tests.

Hardy introduced the orders of infinity and the comparability of functions in 1910^[2]. Algorithms for asymptotic expansions of exp-log functions were developed in the late 1980s and 1990s by Shackell, Salvy, Richardson and van der Hoeven, using nested expansions and multiseries^[3][4][7]. Gruntz's 1996 thesis gave the MRV method, simpler to implement because it needs only ordinary power series in one variable at each step, and implemented it in Maple^[1]. SymPy's limit function is based on it. Van der Hoeven's theory of transseries gives the general framework in which such expansions live^[5].

• Risch algorithmThe Risch algorithm is a decision procedure for integration in finite terms: given an elementary function, it either finds an elementary antiderivative or proves that none exists. It rests on Liouville's theorem, which says that an elementary antiderivative, if one exists, is a function of the same field plus constant multiples of logarithms. The algorithm writes the integrand in a tower of logarithmic, exponential and algebraic extensions of the rational functions and works down it, using Hermite reduction, the Rothstein–Trager resultant and the Risch differential equation y′ + fy = g. Its transcendental case is completely algorithmic; its algebraic case is much harder; and both are decision procedures only relative to deciding whether a constant is zero.
• Canonical formIn computer algebra, a canonical form is a representation in which mathematically equal expressions are written identically, so that equality becomes a syntactic comparison and zero-testing a look at the representation. A normal form is the weaker requirement that expressions equal to zero are represented by 0. Expanded polynomials with sorted terms, reduced rational functions and remainders modulo a Gröbner basis are canonical; for expressions with exponentials, logarithms and absolute values, Richardson proved in 1968 that zero-equivalence is undecidable, so no canonical form can exist. Where no canonical form is practical, randomized evaluation, justified by the Schwartz–Zippel lemma, tests identities with high confidence.
• Hermite reductionHermite reduction is the step of symbolic integration that splits the integral of a rational function A/D into a rational function and an integral whose denominator is square-free, using only gcds and the extended Euclidean algorithm, with no factorization of D. The rational part of the antiderivative comes entirely from the repeated factors of D, and each reduction step lowers their multiplicity by one. What remains integrates to a sum of logarithms, whose coefficients are the roots of the Rothstein–Trager resultant. Together the two steps integrate any rational function over a field of characteristic zero exactly, introducing algebraic numbers only where the answer needs them.

1. [1]D. Gruntz, On Computing Limits in a Symbolic Manipulation System, PhD thesis, ETH Zürich (1996).
2. [2]G. H. Hardy, Orders of Infinity, Cambridge Tracts in Mathematics 12 (1910).
3. [3]D. Richardson, B. Salvy, J. Shackell, J. van der Hoeven, “Asymptotic expansions of exp-log functions”, ISSAC (1996).
4. [4]J. R. Shackell, Symbolic Asymptotics, Algorithms and Computation in Mathematics 12, Springer (2004).
5. [5]J. van der Hoeven, Transseries and Real Differential Algebra, Lecture Notes in Mathematics 1888, Springer (2006).
6. [6]D. Richardson, “Some undecidable problems involving elementary functions of a real variable”, Journal of Symbolic Logic 33 (1968).
7. [7]B. Salvy, J. Shackell, “Symbolic asymptotics: multiseries of inverse functions”, Journal of Symbolic Computation 27 (1999).

last updated 28 September 2026