Holonomic function

In mathematics, and more specifically in analysis, a holonomic function is a smooth function in several variables that is a solution of a system of linear homogeneous differential equations with polynomial coefficients and satisfies a suitable dimension condition in terms of D-modules theory. More precisely, a holonomic function is an element of a holonomic module of smooth functions. Holonomic functions can also be described as differentiably finite functions, also known as D-finite functions. When a power series in the variables is the Taylor expansion of a holonomic function, the sequence of its coefficients, in one or several indices, is also called holonomic. Holonomic sequences are also called P-recursive sequences: they are defined recursively by multivariate recurrences satisfied by the whole sequence and by suitable specializations of it. The situation simplifies in the univariate case: any univariate sequence that satisfies a linear homogeneous recurrence relation with polynomial coefficients, or equivalently a linear homogeneous difference equation with polynomial coefficients, is holonomic.^[1]

Holonomic functions and sequences in one variable

Definitions

Let $\mathbb {K}$ be a field of characteristic 0 (for example, $\mathbb{K} = \mathbb{Q}$ or $\mathbb{K} = \mathbb{C}$).

A function $f = f(x)$ is called D-finite (or holonomic) if there exist polynomials $a_r(x), a_{r-1}(x), \ldots, a_0(x) \in \mathbb{K}[x]$ such that

$a_r(x) f^{(r)}(x) + a_{r-1}(x) f^{(r-1)}(x) + \ldots + a_1(x) f'(x) + a_0(x) f(x) = 0$

holds for all x. This can also be written as $A f = 0$ where

$A = \sum_{k=0}^r a_k D_x^k$

and $D_{x}$ is the differential operator that maps $f(x)$ to $f'(x)$. $A$ is called an annihilating operator of f (the annihilating operators of $f$ form an ideal in the ring $\mathbb{K}[x][D_x]$, called the annihilator of $f$). The quantity r is called the order of the annihilating operator. By extension, the holonomic function f is said to be of order r when an annihilating operator of such order exists.

A sequence $c = c_0, c_1, \ldots$ is called P-recursive (or holonomic) if there exist polynomials $a_r(n), a_{r-1}(n), \ldots, a_0(n) \in \mathbb{K}[n]$ such that

$a_r(n) c_{n+r} + a_{r-1}(n) c_{n+r-1} + \ldots + a_0(n) c_n = 0$

holds for all n. This can also be written as $A c = 0$ where

$A = \sum_{k=0}^r a_k S_n$

and $S_{n}$ the shift operator that maps $c_0, c_1, \ldots$ to $c_1, c_2, \ldots$. $A$ is called an annihilating operator of c (the annihilating operators of $c$ form an ideal in the ring $\mathbb{K}[n][S_n]$, called the annihilator of $c$). The quantity r is called the order of the annihilating operator. By extension, the holonomic sequence c is said to be of order r when an annihilating operator of such order exists.

Holonomic functions are precisely the generating functions of holonomic sequences: if $f(x)$ is holonomic, then the coefficients $c_{n}$ in the power series expansion

$f(x) = \sum_{n=0}^{\infty} c_n x^n$

form a holonomic sequence. Conversely, for a given holonomic sequence $c_{n}$, the function defined by the above sum is holonomic (this is true in the sense of formal power series, even if the sum has a zero radius of convergence).

Closure properties

Holonomic functions (or sequences) satisfy several closure properties. In particular, holonomic functions (or sequences) form a ring. They are not closed under division, however, and therefore do not form a field.

If $f(x) = \sum_{n=0}^{\infty} f_n x^n$ and $g(x) = \sum_{n=0}^{\infty} g_n x^n$ are holonomic functions, then the following functions are also holonomic:

• $h(x) = \alpha f(x) + \beta g(x)$, where $\alpha$ and $\beta$ are constants
• $h(x) = f(x) g(x)$ (the Cauchy product of the sequences)
• $h(x) = \sum_{n=0}^{\infty} f_n g_n x^n$ (the Hadamard product of the sequences)
• $h(x) = \int_0^x f(t) dt$
• $h(x) = \sum_{n=0}^{\infty} (\sum_{k=0}^n f_k) x^n$
• $h(x) = f(a(x))$, where $a(x)$ is any algebraic function. However, $a(f(x))$ is generally not holonomic.

A crucial property of holonomic functions is that the closure properties are effective: given annihilating operators for $f$ and $g$, an annihilating operator for $h$ as defined using any of the above operations can be computed explicitly.

Examples of holonomic functions and sequences

Examples of holonomic functions include:

• all algebraic functions
• some transcendental functions such as $\sin(x)$, $\cos(x)$, $e^{x}$, and $\log(x)$^[2]
• the generalized hypergeometric function ${}_pF_q(a_1,\ldots,a_p, b_1,\ldots,b_q, x)$, considered as a function of $x$ with all the parameters $a_{i}$, $b_{i}$ held fixed
• the error function $\operatorname{erf}(x)$
• the Bessel functions $J_n(x)$, $Y_n(x)$, $I_n(x)$, $K_n(x)$
• the Airy functions $\operatorname{Ai}(x)$, $\operatorname{Bi}(x)$
• all classical orthogonal polynomials, including the Legendre polynomials $P_n(x)$ and the Chebyshev polynomials $T_n(x)$ and $U_n(x)$.

The class of holonomic functions is a strict superset of the class of hypergeometric functions. Examples of special functions that are holonomic but not hypergeometric include the Heun functions.

Examples of holonomic sequences include:

• the sequence of Fibonacci numbers $F_{n}$, and more generally, all constant-recursive sequences
• the sequence of factorials $n!$
• the sequence of binomial coefficients ${n \choose k}$ (as functions of either n or k)
• the sequence of harmonic numbers $H_n = \sum_{k=1}^n \frac{1}{k}$, and more generally $H_{n,m} = \sum_{k=1}^n \frac{1}{k^m}$ for any integer m
• the sequence of Catalan numbers
• the sequence of Motzkin numbers.
• the sequence of derangements.

Hypergeometric functions, Bessel functions, and classical orthogonal polynomials, in addition to being holonomic functions of their variable, are also holonomic sequences with respect to their parameters. For example, the Bessel functions $J_n$ and $Y_{n}$ satisfy the second-order linear recurrence ${\displaystyle x(f_{n+1}+f_{n-1})=2nf_{n}}$.

Examples of nonholonomic functions and sequences

Examples of nonholonomic functions include:

• the function $\frac{x}{e^x-1}$
• the function tan(x) + sec(x)^[3]
• the quotient of two holonomic functions is generally not holonomic.

Examples of nonholonomic sequences include:

• the Bernoulli numbers^[4]
• the numbers of alternating permutations^[5]
• the numbers of integer partitions^[3]
• the numbers $\log(n)$^[3]
• the numbers $n^{\alpha}$ where $\alpha \not\in \mathbb{Z}$^[3]
• the prime numbers^[3]
• the enumerations of irreducible and connected permutations.^[6]

Algorithms and software

Holonomic functions are a powerful tool in computer algebra. A holonomic function or sequence can be represented by a finite amount of data, namely an annihilating operator and a finite set of initial values, and the closure properties allow carrying out operations such as equality testing, summation and integration in an algorithmic fashion. In recent years, these techniques have allowed giving automated proofs of a large number of special function and combinatorial identities.

Moreover, there exist fast algorithms for evaluating holonomic functions to arbitrary precision at any point in the complex plane, and for numerically computing any entry in a holonomic sequence.

Software for working with holonomic functions includes:

• The HolonomicFunctions package for Mathematica, developed by Christoph Koutschan, which supports computing closure properties and proving identities for univariate and multivariate holonomic functions
• The algolib library for Maple, which includes the following packages:
  • gfun, developed by Bruno Salvy, Paul Zimmermann and Eithne Murray, for univariate closure properties and proving
  • mgfun, developed by Frédéric Chyzak, for multivariate closure properties and proving
  • numgfun, developed by Marc Mezzarobba, for numerical evaluation

Notes

1. See Zeilberger 1990 and Kauers & Paule 2011.
2. See Mallinger 1996, p. 3.
3. See Flajolet, Gerhold & Salvy 2005.
4. This follows from the fact that the function $\frac{x}{e^x-1}$ has infinitely many (complex) singularities, whereas functions that satisfy a linear differential equation with polynomial coefficients necessarily have only finitely many singular points.
5. This follows from the fact that the function tan(x) + sec(x) is a nonholonomic function. See Flajolet, Gerhold & Salvy 2005.
6. See Klazar 2003.

References

• Flajolet, Philippe; Gerhold, Stefan; Salvy, Bruno (2005), "On the non-holonomic character of logarithms, powers, and the n-th prime function", Electronic Journal of Combinatorics, 11 (2).

• Flajolet, Philippe; Sedgewick, Robert (2009). Analytic Combinatorics. Cambridge University Press. ISBN 0521898064.

• Kauers, Manuel; Paule, Peter (2011). The Concrete Tetrahedron: Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Text and Monographs in Symbolic Computation. Springer. ISBN 978-3-7091-0444-6.

• Klazar, Martin (2003). "Irreducible and connected permutations" (PDF) (122). (ITI Series preprint)

• Mallinger, Christian (1996). Algorithmic Manipulations and Transformations of Univariate Holonomic Functions and Sequences (PDF) (Thesis). Retrieved 4 June 2013.

• Stanley, Richard P. (1999). Enumerative Combinatorics. 2. Cambridge University Press. ISBN 0-521-56069-1.

• Zeilberger, Doron (1990). "A holonomic systems approach to special functions identities". Journal of Computational and Applied Mathematics. 32 (3): 321–368. doi:10.1016/0377-0427(90)90042-X. ISSN 0377-0427. MR 1090884.