# The Mgfun Package

Dowload Mgfun 4.1 (Maple archive). This is release 4.1, June 2013, recompiled for Maple 2016.

⋆⋆⋆

Apart from the download link above, much of what follows is outdated and should be recycled.

## Mgfun and its relatives

The Mgfun Project is a collection of packages for the computer algebra system Maple, and is intended for the symbolic manipulation of a large class of special functions and combinatorial sequences (in one or several variables and indices) that appear in many branches of mathematics, mathematical physics, and engineering sciences. Members of the class satisfy a crucial finiteness property which makes the class amenable to computer algebra methods and enjoy numerous algorithmic closure properties, including algorithmic closures under integration and summation.

$\sum_{k=0}^n\left(\sum_{j=0}^k\binom{n}{j}\right)^3 =n2^{3n-1}+2^{3n}-3n2^{n-2}\binom{2n}{n}$ $\int_0^{+\infty}xe^{-px^2}J_n(bx)I_n(cx)\,dx=\frac{1}{2p} \exp\left(\frac{c^2-b^2}{4p}\right)J_n\left(\frac{bc}{2p}\right)$ $\sum_{-\infty}^{+\infty}\frac{(a;q)_nx^n}{(b;q)_n}= \frac{(ax;q)_\infty\left(\frac{q}{ax};q\right)_\infty (q;q)_\infty\left(\frac{b}{a};q\right)_\infty} {(x;q)_\infty\left(\frac{b}{ax};q\right)_\infty (b;q)_\infty\left(\frac{q}{a};q\right)_\infty}$ $\int_{-1}^{+1}\frac{e^{-px}T_n(x)}{\sqrt{1-x^2}}\,dx =(-1)^n\pi I_n(p)$

Much more than the search for closed forms, the aim is to be able to continue to compute with the implicit representation of holonomic objects even when no explicit form is available. Applications include the simplification of expressions in special functions and sequences, the evaluation of parametrized definite integrals and sums, series and asymptotic expansions, the automatic proof of identities, and will open to the fast numerical evaluation of special functions in the future. To achieve these goals, several algorithmic tools are used by Mgfun, and have been implemented as separate dedicated packages. The implementation has made it possible to give the first automatic proof of identities so far unreachable by computer algebra. The Mgfun family consists of:

• the package Ore_algebra, to deal with algebras of linear operators and skew polynomials;
• the package Groebner, that implements Gröbner basis methods in commutative polynomial algebras and skew polynomial algebras;
• the package Holonomy, for calculations with holonomic and d-finite functions at the level of systems of operators;
• the package Mgfun, a user-oriented interface to the previous packages, much in the spirit of gfun.

An earlier version of the first two packages have been distributed as part of the core library of Maple V release 5.

Implicit Representations of Special Functions and Sequences. The essence of the Mgfun packages is to base on implicit representations of special functions and combinatorial sequences in terms of systems of linear functional equations, rather than explicit closed forms. In order to accomodate linear operators of a general type, like linear differential and linear finite difference operators, a class of algebras of multivariate skew polynomials is introduced, namely Ore algebras. Although they are non-commutative, these algebras share many algorithmic properties with the usual commutative polynomial algebras, like the existence of a degree, a gcd theory, a euclidean algorithm. Moreover, they are used more and more in recent computer algebra algorithms as a tool to unify differential calculations with functions and calculations of recurrences with sequences. Their algorithmic aspects have been implemented in the package Ore_algebra.

Gröbner Bases in Algebras of Linear Operators. Many special functions and combinatorial sequences can be defined as the common solutions of systems of linear functional equations. In this spirit, Mgfun views special functions and combinatorial sequences as the zeroes of special left ideals in Ore algebras. Algorithms to manipulate special functions and sequences then appeal to polynomial elimination in those algebras of linear operators, for which methods of non-commutative Gröbner bases have been developed. Indeed, the simple commutation rules that describe the non-commutativity of Ore algebras make it possible to develop a theory of Gröbner bases together with an extension of Buchberger's algorithm whose termination is always guaranteed. Other natural extensions of Gröbner-based calculations (FGLM algorithm, Gröbner bases for modules, computation of syzygies, Gröbner walk, ...) exist in the skew setting and can be put to good use in applications. The package Groebner implements many of them. It provides Gröbner bases for many algebras and many term orderings.

Holonomy and Holonomic Functions. The approach followed by packages in the Mgfun family originates from work by D. Zeilberger at the beginning of the 1990's. Zeilberger's interesting observation is the relevance of the theory of holonomic D-modules to the problem of summation and integration of special functions and combinatorial sequences. This theory had originally been developed by J. Bernstein in the 1970's in order to answer a question of analytical nature, namely the existence of a meromorphic extension of a certain function known to be analytic in a half of the complex plane. In both types of applications, the role of holonomy is to ensure the existence of a linear operator with a special elimination property. Bernstein's holonomic modules specifically refer to modules over algebras of linear differential operators. Their definition relates to a dimension theory for ideals. Zeilberger suggested a definition in the case of linear recurrence operators. The case of algebras of linear q-difference operators was then developed in the 1990's.

Holonomic Summation and Integration. After Zeilberger's original work, algorithmic closures under summation and integration following the holonomic approach have been intensively studied in the 1990's, leading to a great deal of algorithms. The problem still stimulates vivid ongoing research. The package Holonomy implements several of these integration and summation algorithms, ranging from a brute-force elimination algorithm by Gröbner basis calculation to subtle algorithms based on a restricted kind of elimination. Specifically, the package provides the user with a toolbox for calculations with holonomic functions in their ideal-theoretic representation, and can be used to study sutble properties of holonomic functions. This is complemented at a higher level by the package Mgfun, a user-oriented interface to the previous packages, much in the spirit of the package gfun dedicated to the univariate case.

$\sum_{k=0}^n\binom{n}{k}^2\binom{n+k}{k}^2= \sum_{k=0}^n\binom{n}{k}\binom{n+k}{k}\sum_{j=0}^k\binom{k}{j}^3$ $\frac{\pi}{2}J_0(z)=\int_0^1\frac{\cos(zu)}{\sqrt{1-u^2}}\,du= \int_1^{+\infty}\frac{\sin(zu)}{\sqrt{u^2-1}}\,du$ $\sum_{n=0}^\infty H_n(x)H_n(y)\frac{u^n}{n!} =\frac{\exp\left(\frac{4u(xy-u(x^2+y^2))}{1-4u^2}\right)}{\sqrt{1-u^2}}$ $\int_0^{+\infty}xJ_1(ax)I_1(ax)Y_0(x)K_0(x)\,dx =-\frac{\ln(1-a^4)}{2\pi a^2}$ $\sum_{j=0}^n\sum_{i=0}^{n-j}\frac{q^{(i+j)^2+j^2}} {(q;q)_{n-i-j}(q;q)_i(q;q)_j}= \sum_{k=-n}^n\frac{(-1)^kq^{7/2k^2+1/2k}}{(q;q)_{n+k}(q;q)_{n-k}}$

## Example sessions

Each of the packages has its introductory Maple session.

 Ore_algebra (html) Groebner (html) Mgfun (html) Ore_algebra (mws) Groebner (mws) Mgfun (mws) Ore_algebra (ps) Groebner (ps) Mgfun (ps)

Besides, a few Maple sessions accompany Frédéric Chyzak's publications that are related to Mgfun. An older demo based on an earlier version of the software is also available.

## Publications related to Mgfun

The following are publications that describe the theoretical aspects implemented in the packages.

• Fonctions holonomes en calcul formel, Frédéric Chyzak (1998). Thèse universitaire no. TU 0531, INRIA. Defended on May 27, 1998. 227 pages.
• Gröbner Bases, Symbolic Summation and Symbolic Integration, Frédéric Chyzak (1998). In: Buchberger, B. and Winkler, F., Eds., Gröbner Bases and Applications (Proc. of the Conference 33 Years of Gröbner Bases''), Cambridge University Press (London Mathematical Society Lecture Notes Series, vol. 251). ISBN 0-521-63298-6. p. 32-60. Preliminary version available as: Research Report no. 3297, INRIA.
• An Extension of Zeilberger's Fast Algorithm to General Holonomic Functions, Frédéric Chyzak (1997). In: Formal Power Series and Algebraic Combinatorics, 9th Conference, Universität Wien, p. 172-183, Conference Proceedings. Preliminary version available as: Research Report no. 3195, INRIA.
• Non-commutative Elimination in Ore Algebras Proves Multivariate Identities, Frédéric Chyzak and Bruno Salvy (1998). Journal of Symbolic Computation, vol. 26, no. 2, p. 187-227. Preliminary version:
• Holonomic Systems and Automatic Proofs of Identities, Frédéric Chyzak (1994). Research Report no. 2371, INRIA. 61 pages.
$\int_0^\infty\int_0^\infty J_1(x)J_1(y)J_2(c\sqrt{xy})\,\frac{dxdy}{e^{x+y}} =\frac{c^2+8}{4\pi c^2}\left(\frac{c^4+8c^2+64}{(c^2+8)^2} \boldsymbol{K}\left(\frac{4c}{c^2+8}\right) -\boldsymbol{E}\left(\frac{4c}{c^2+8}\right)\right)$ $\sum_{k=1}^n\binom{k}{m}H_k =\binom{n+1}{m+1}\left(H_{n+1}-\frac{1}{m+1}\right)$ $\sum_{r=0}^\infty\sum_{s=0}^\infty(-1)^{n+r+s} \binom{n}{r}\binom{n}{s}\binom{n+r}{r}\binom{n+s}{s} \binom{2n-(r+s)}{n}=\sum_{k=0}^\infty\binom{n}{k}^4$

## Related links

• The package gfun, which performs the same calculations as Mgfun in the univariate case.
• The package desing, which uses Mgfun for its Gröbner basis calculations.
• Nobuki Takayama's package Kan, which performs some of Mgfun's, but also many very different ones!
• The web page for Glenn Tesler's course Topics in Combinatorics: Special Functions, Sums, Recurrences, and Algorithms at UCSD, in which he used Mgfun!
$J_0(z)^2+2\sum_{k=1}^\infty{J_k(z)^2}=1$ $\sum_{n=0}^{+\infty}P_n(x)y^n=\frac{1}{\sqrt{1-2xy+y^2}}$ $\oint_0\frac{(1+2xy+4y^2)\exp\left(\frac{4x^2y^2}{1+4y^2}\right)} {y^{n+1}(1+4y^2)^\frac{3}{2}}\,dy=\frac{n!H_n(x)}{\lfloor n/2\rfloor!}$ $\sum_{n=0}^\infty\frac{r_n(a,b;q)z^n}{(q;q)_n} =\frac{1}{(az;q)_\infty(bz;q)_\infty}$ $\sum_{n=0}^\infty\frac{r_n(a,b;q)r_n(c,d;q)z^n}{(q;q)_n} =\frac{(acz;q)_\infty(adz;q)_\infty(bcz;q)_\infty(bdz;q)_\infty} {(abcdz^2;q)_\infty}$ $\sum_{k=0}^n\frac{q^{k^2}}{(q;q)_k(q;q)_{n-k}}= \sum_{k=-n}^n\frac{(-1)^kq^{(5k^2-k)/2}}{(q;q)_{n-k}(q;q)_{n+k}}$