Frédéric Chyzak's Publications

We develop and compare two algorithms for computing first-order right-hand factors in the ring of linear Mahler operators $\ell_r M^r + \dots + \ell_1 M + \ell_0$ where $\ell_0, \dots, \ell_r$ are polynomials in $x$ and $Mx = x^b M$ for some integer $b \geq 2$. In other words, we give algorithms for finding all formal infinite product solutions of linear functional equations $\ell_r(x) f(x^{b^r}) + \dots + \ell_1(x) f(x^b) + \ell_0(x) f(x) = 0$.
The first of our algorithms is adapted from Petkovšek's classical algorithm for the analogous problem in the case of linear recurrences. The second one proceeds by computing a basis of generalized power series solutions of the functional equation and by using Hermite–Padé approximants to detect those linear combinations of the solutions that correspond to first-order factors.
We present implementations of both algorithms and discuss their use in combination with criteria from the literature to prove the differential transcendence of power series solutions of Mahler equations.

By a classic result of Gessel, the exponential generating functions for k-regular graphs are D-finite. Using Gröbner bases in Weyl algebras, we compute the linear differential equations satisfied by the generating function for 5-, 6-, and 7- regular graphs. The method is sufficiently robust to consider variants such as graphs with multiple edges, loops, and graphs whose degrees are limited to fixed sets of values.

We provide short product formulas for the $f$-vectors of the canonical complexes of the Tamari lattices and of the cellular diagonals of the associahedra.

Discrete differential equations of order 1 relate polynomially a power series $F(t,u)$ in $t$ with polynomial coefficients in a “catalytic” variable $u$ and one of its specializations, say $F(t,1)$. Such equations are ubiquitous in combinatorics, notably in the enumeration of maps and walks. When the solution $F$ is unique, a celebrated result by Bousquet-Mélou and Jehanne, reminiscent of Popescu's theorem in commutative algebra, states that $F$ is algebraic. We address algorithmic and complexity questions related to this result. In generic situations, we first revisit and analyze known algorithms, based either on polynomial elimination or on the guess-and-prove paradigm. We then design two new algorithms: the first has a geometric flavor, the second blends elimination and guess-and-prove. In the general case (no genericity assumptions), we prove that the total arithmetic size of the algebraic equations for $F(t,1)$ is bounded polynomially in the size of the input discrete differential equation, and that one can compute such equations in polynomial time.

We present a symbolic-numeric Las Vegas algorithm for factoring Fuchsian ordinary differential operators with rational function coefficients. The new algorithm combines ideas of van Hoeij's “local-to-global” method and of the “analytic” approach proposed by van der Hoeven. It essentially reduces to the former in “easy” cases where the local-to-global method succeeds, and to an optimized variant of the latter in the “hardest” cases, while handling intermediate cases more efficiently than both.

We present in this extended abstract a new software designed to work with generating functions that count walks in the quarter plane. With this software we offer a cohesive package that brings together all the required procedures for manipulating these generating functions, as well as a unified interface to deal with them. We also display results that this package offers on a public webpage.

In this article, we study the enumeration by length of several walk models on the square lattice. We obtain bijections between walks in the upper half-plane returning to the $x$-axis and walks in the quarter plane. A recent work by Bostan, Chyzak, and Mahboubi has given a bijection for models using small north, west, and south-east steps. We adapt and generalize it to a bijection between half-plane walks using those three steps in two colours and a quarter-plane model over the symmetrized step set consisting of north, north-west, west, south, south-east, and east. We then generalize our bijections to certain models with large steps: for given $p\geq1$, a bijection is given between the half-plane and quarter-plane models obtained by keeping the small south-east step and replacing the two steps north and west of length 1 by the $p+1$ steps of length $p$ in directions between north and west. This model is close to, but distinct from, the model of generalized tandem walks studied by Bousquet-Mélou, Fusy, and Raschel.

Divide-and-conquer recurrences relate values of a given sequence at indices of the form $b^ℓ n + r$ for fixed $b\geq2$ and various pairs $(ℓ,r)$. Using systems of such recurrences makes it possible to express the behaviour of a quantity according to congruence classes modulo $b^ℓ$. The study of such systems is poorly developed so far. In particular, no consistency check is available and no theory of initial values has been developed yet. In an ongoing study in order to fill this gap, we have introduced a noncommutative multivariate polynomial setting to represent divide-and-conquer systems. This setting involves at the same time variables that behave like words in purely noncommutative algebras and variables governed by commutation rules like in skew polynomial extensions. In the present work, we initiate the study of left ideals of such polynomials and we develop their Gröbner-basis theory, including the usual division and Buchberger algorithms. Strikingly, the nature of commutations generally prevents the leading monomial of a polynomial product to be the product of the leading monomials. To overcome the difficulty, we consider a specific monomial ordering, together with a restriction to monic divisors in intermediate steps. We also develop a variant of the $F_4$ algorithm with distinguishing features.

We report a closed-form expression for the Kullback-Leibler divergence between Cauchy distributions which involves the calculation of a parametric definite integral with 6 parameters. The formula shows that the Kullback-Leibler divergence between Cauchy densities is always finite and symmetric.

In 1994, Becker conjectured that if F(z) is a k-regular power series, then there exists a k-regular rational function R(z) such that F(z)/R(z) satisfies a Mahler-type functional equation with polynomial coefficients where the initial coefficient satisfies a₀(z) = 1. In this paper, we prove Becker's conjecture in the best-possible form; we show that the rational function R(z) can be taken to be a polynomial z^γ Q(z) for some explicit non-negative integer γ and such that 1/Q(z) is k-regular.

Hermite reduction is a classical algorithmic tool in symbolic integration. It is used to decompose a given rational function as a sum of a function with simple poles and the derivative of another rational function. We extend Hermite reduction to arbitrary linear differential operators instead of the pure derivative, and develop efficient algorithms for this reduction. We then apply the generalized Hermite reduction to the computation of linear operators satisfied by single definite integrals of D-finite functions of several continuous or discrete parameters. The resulting algorithm is a generalization of reduction-based methods for creative telescoping.

Mahler equations relate evaluations of the same function $f$ at iterated $b$th powers of the variable. They arise in particular in the study of automatic sequences and in the complexity analysis of divide-and-conquer algorithms. Recently, the problem of solving Mahler equations in closed form has occurred in connection with number-theoretic questions. A difficulty in the manipulation of Mahler equations is the exponential blow-up of degrees when applying a Mahler operator to a polynomial. In this work, we present algorithms for solving linear Mahler equations for series, polynomials, and rational functions, and get polynomial-time complexity under a mild assumption. Incidentally, we develop an algorithm for computing the gcrd of a family of linear Mahler operators with nonzero constant terms.

Le calcul formel traite des objets mathématiques exacts d’un point de vue informatique. Cet ouvrage « Algorithmes efficaces en calcul formel » explore deux directions : la calculabilité et la complexité. La calculabilité étudie les classes d’objets mathématiques sur lesquelles des réponses peuvent être obtenues algorithmiquement. La complexité donne ensuite des outils pour comparer des algorithmes du point de vue de leur efficacité.
Cet ouvrage est une synthèse de notes de cours rédigées principalement pour le cours du même nom que nous avons donné pendant plus de dix ans au Master Parisien de Recherche en Informatique de l’Université Paris Diderot, des Écoles Normales Supérieures de Cachan et de Paris, et de l’École polytechnique. La partie concernant les systèmes polynomiaux provient aussi de notes de cours donnés au DEA Méthodes algébriques puis au Master Algèbre et Géométrie de l’Université Pierre-et-Marie-Curie, mais aussi au DEA Informatique Mathématique et Applications de l’École Normale Supérieure de Paris, l’École polytechnique, l’Université Pierre-et-Marie-Curie, l’Université Paris Diderot, et l’Université Paris-Sud. Plusieurs parties ont aussi fait l’objet de mini-cours plus spécialisés donnés à l’occasion des Journées Nationales de Calcul Formel en 2007, 2010, 2011, et 2013.

We study nearest-neighbors walks on the two-dimensional square lattice, that is, models of walks on $\mathbb{Z}^2$ defined by a fixed step set that is a subset of the non-zero vectors with coordinates 0, 1 or $-1$. We concern ourselves with the enumeration of such walks starting at the origin and constrained to remain in the quarter plane $\mathbb{N}^2$, counted by their length and by the position of their ending point. Bousquet-Mélou and Mishna [Contemp. Math., pp. 1–39, Amer. Math. Soc., 2010] identified 19 models of walks that possess a D-finite generating function; linear differential equations have then been guessed in these cases by Bostan and Kauers [FPSAC 2009, Discrete Math. Theor. Comput. Sci. Proc., pp. 201–215, 2009]. We give here the first proof that these equations are indeed satisfied by the corresponding generating functions. As a first corollary, we prove that all these 19 generating functions can be expressed in terms of Gauss' hypergeometric functions that are intimately related to elliptic integrals. As a second corollary, we show that all the 19 generating functions are transcendental, and that among their $19\times4$ combinatorially meaningful specializations only four are algebraic functions.

We present a criterion for the existence of telescopers for mixed hypergeometric terms, which is based on additive and multiplicative decompositions. The criterion enables us to determine the termination of Zeilberger's algorithms for mixed hypergeometric inputs, and to verify that certain indefinite sums do not satisfy any polynomial differential equation.

This paper describes the formal verification of an irrationality proof of $\zeta(3)$, the evaluation of the Riemann zeta function, using the Coq proof assistant. This result was first proved by Apéry in 1978, and the proof we have formalized follows the path of his original presentation. The crux of this proof is to establish that some sequences satisfy a common recurrence. We formally prove this result by an a posteriori verification of calculations performed by computer algebra algorithms in a Maple session. The rest of the proof combines arithmetical ingredients and some asymptotic analysis that we conduct by extending the Mathematical Components libraries. The formalization of this proof is complete up to a weak corollary of the Prime Number Theorem.

Uncoupling algorithms transform a linear differential system of first order into one or several scalar differential equations. We examine two approaches to uncoupling: the cyclic-vector method (CVM) and the Danilevski-Barkatou-Zürcher algorithm (DBZ). We give tight size bounds on the scalar equations produced by CVM, and design a fast variant of CVM whose complexity is quasi-optimal with respect to the output size. We exhibit a strong structural link between CVM and DBZ enabling to show that, in the generic case, DBZ has polynomial complexity and that it produces a single equation, strongly related to the output of CVM. We prove that algorithm CVM is faster than DBZ by almost two orders of magnitude, and provide experimental results that validate the theoretical complexity analyses.

We present a new reduction algorithm that simultaneously extends Hermite's reduction for rational functions and the Hermite-like reduction for hyperexponential functions. It yields a unique additive decomposition that allows to decide hyperexponential integrability. Based on this reduction algorithm, we design a new algorithm to compute minimal telescopers for bivariate hyperexponential functions. One of its main features is that it can avoid the costly computation of certificates. Its implementation outperforms Maple's function DEtools[Zeilberger]. We also derive an order bound on minimal telescopers that is tighter than the known ones.

We study tight bounds and fast algorithms for LCLMs of several linear differential operators with polynomial coefficients. We analyze the arithmetic complexity of existing algorithms for LCLMs, as well as the size of their outputs. We propose a new algorithm that recasts the LCLM computation in a linear algebra problem on a polynomial matrix. This algorithm yields sharp bounds on the coefficient degrees of the LCLM, improving by one order of magnitude the best bounds obtained using previous algorithms. The complexity of the new algorithm is almost optimal, in the sense that it nearly matches the arithmetic size of the output.

In computer algebra there are different ways of approaching the mathematical concept of functions, one of which is by defining them as solutions of differential equations. We compare different such approaches and discuss the occurring problems. The main focus is on the question of determining possible branch cuts. We explore the extent to which the treatment of branch cuts can be rendered (more) algorithmic, by adapting Kahan's rules to the differential equation setting.

We report on the design and implementation of a programming tool, DynaMoW, to control interactive and incremental mathematical calculations to be presented on the web. This tool is implemented as a language extension of OCaml using Camlp4. Fragments of mathematical code written for a computer-algebra system as well as fragments of mathematical web documents are embedded directly and naturally inside OCaml code. A DynaMoW-based application is made of independent web services, whose parameter types are checked by the OCaml extension. The approach is illustrated by two implementations of online mathematical encyclopedias on top of DynaMoW.

Let $a_n$ denote the number of ways in which a chess rook can move from a corner cell to the opposite corner cell of an $n \times n \times n$ three-dimensional chessboard, assuming that the piece moves closer to the goal cell at each step. We describe the computer-driven discovery and proof of the fact that the generating series $G(x)= \sum_{n \geq 0} a_n x^n$ admits the following explicit expression in terms of a Gaussian hypergeometric function: \[ G(x) = 1 + 6 \cdot \int_0^x \frac{ {}_2F_1\left(1/3,2/3;2; {\frac{27 w(2-3w)}{(1-4w)^3}} \right) }{(1-4w)(1-64w)} \, dw . \]

The long-term goal initiated in this work is to obtain fast algorithms and implementations for definite integration in Almkvist and Zeilberger's framework of (differential) creative telescoping. Our complexity-driven approach is to obtain tight degree bounds on the various expressions involved in the method. To make the problem more tractable, we restrict to bivariate rational functions. By considering this constrained class of inputs, we are able to blend the general method of creative telescoping with the well-known Hermite reduction. We then use our new method to compute diagonals of rational power series arising from combinatorics.

We describe the main features of the Dynamic Dictionary of Mathematical Functions (version 1.5). It is a website consisting of interactive tables of mathematical formulas on elementary and special functions. The formulas are automatically generated by computer algebra routines. The user can ask for more terms of the expansions, more digits of the numerical values, or proofs of some of the formulas.

We extend Zeilberger's approach to special function identities to cases that are not holonomic. The method of creative telescoping is thus applied to definite sums or integrals involving Stirling or Bernoulli numbers, incomplete Gamma function or polylogarithms, which are not covered by the holonomic framework. The basic idea is to take into account the dimension of appropriate ideals in Ore algebras. This unifies several earlier extensions and provides algorithms for summation and integration in classes that had not been accessible to computer algebra before.

Let ${\mathcal T}_n$ denote the set of unrooted labeled trees of size $n$ and let $\mathcal M$ be a particular (finite) tree. Assuming that every tree of ${\mathcal T}_n$ is equally likely, it is shown that the limiting distribution of the number of occurrences of $\mathcal M$ as an induced sub-tree is asymptotically normal with mean value $\sim\mu n$ and variance $\sim\sigma^2n$ with computable constants $\mu>0$ and $\sigma\ge 0$.

It is known that multiplication of linear differential operators over ground fields of characteristic zero can be reduced to a constant number of matrix products. We give a new algorithm by evaluation and interpolation which is faster than the previously-known one by a constant factor, and prove that in characteristic zero, multiplication of differential operators and of matrices are computationally equivalent problems. In positive characteristic, we show that differential operators can be multiplied in nearly optimal time. Theoretical results are validated by intensive experiments.

In the seventies, the study of transfer matrices of time-invariant linear systems of ordinary differential equations (ODEs) led to the development of the polynomial approach. In particular, the univariate polynomial matrices play a central role in this approach (e.g., Hermite, Smith and Popov forms, invariant factors, primeness, Bézout/Diophantine equations).

We propose algorithms for the computation of the first $N$ terms of a vector (or a full basis) of power series solutions of a linear system of differential equations at an ordinary point, using a number of arithmetic operations that is quasi-linear with respect to $N$. Similar results are also given in the non-linear case. This extends previous results obtained by Brent and Kung for scalar differential equations of order 1 and 2.

It is classical that univariate algebraic functions satisfy linear differential equations with polynomial coefficients. From there, linear recurrences follow for the coefficients of their power series expansions. We show that the linear differential equation of minimal order has coefficients whose degree is cubic in the degree of the function. We also show that there exists a linear differential equation of order linear in the degree whose coefficients are only of quadratic degree. Furthermore, we prove the existence of recurrences of order and degree close to optimal. We study the complexity of computing these differential equations and recurrences.

We consider two kinds of problems: the computation of polynomial and rational solutions of linear recurrences with coefficients that are polynomials with integer coefficients; indefinite and definite summation of sequences that are hypergeometric over the rational numbers. The algorithms for these tasks all involve as an intermediate quantity an integer $N$ (dispersion or root of an indicial polynomial) that is potentially exponential in the bit size of their input. Previous algorithms have a bit complexity that is at least quadratic in $N$. We revisit them and propose variants that exploit the structure of solutions and avoid expanding polynomials of degree $N$. We give two algorithms: a probabilistic one that detects the existence or absence of nonzero polynomial and rational solutions in $O(\sqrt{N}\log^{2}N)$ bit operations; a deterministic one that computes a compact representation of the solution in $O(N\log^{3}N)$ bit operations. Similar speed-ups are obtained in indefinite and definite hypergeometric summation. We describe the results of an implementation.

These seminar notes constitute the proceedings of a seminar devoted to the analysis of algorithms and related topics. The subjects covered include combinatorics, symbolic computation, and the asymptotic analysis of algorithms, data structures, and network protocols.

In this paper, we study linear control systems over Ore algebras. Within this mathematical framework, we can simultaneously deal with different classes of linear control systems such as time-varying ordinary differential systems (ODEs), differential time-delay systems, partial differential equations (PDEs), multidimensional discrete systems, multidimensional codes etc. We give effective algorithms which check whether or not a linear control system over some Ore algebra is controllable, parametrizable, flat or $\pi$-free.

Many combinatorial generating functions can be expressed as combinations of symmetric functions, or extracted as sub-series and specializations from such combinations. Gessel has outlined a large class of symmetric functions for which the resulting generating functions are D-finite. We extend Gessel's work by providing algorithms that compute differential equations these generating functions satisfy in the case they are given as a scalar product of symmetric functions in Gessel's class. Examples of applications to k-regular graphs and Young tableaux with repeated entries are given. Asymptotic estimates are a natural application of our method, which we illustrate on the same model of Young tableaux. We also derive a seemingly new formula for the Kronecker product of the sum of Schur functions with itself. (This article completes the extended abstract published in the proceedings of FPSAC'02 under the title “Effective D-Finite Symmetric Functions”.)

These seminar notes constitute the proceedings of a seminar devoted to the analysis of algorithms and related topics. The subjects covered include combinatorics, symbolic computation, asymptotic analysis, number theory, as well as the analysis of algorithms, data structures, and network protocols.

In this paper, we study linear control systems over Ore algebras. Within this mathematical framework, we can simultaneously deal with different classes of linear control systems such as time-varying ordinary differential systems (ODEs), differential time-delay systems, partial differential equations (PDEs), multidimensional discrete systems, multidimensional codes etc. We give effective algorithms which check whether or not a linear control system over some Ore algebra is controllable, parametrizable, flat or π-free.

This paper aims at introducing and comparing various methods for solving the following problem which arises naturally in computer algebra for differential equations: given a series $\hat f(x)=\sum_{m\geq 0}u_mx^m$ solution of an ordinary linear differential equation and given an integer $r\geq 2$ find a differential equation satisfied by the sub-series $\hat f^{(j)}(x)=\sum_{m\geq 0}u_{j+mr}x^{j+mr}$. These methods have been implemented in Maple. References are given to the corresponding programs. Possible realistic algorithms to effectively calculate the formal invariants of an ordinary linear differential system of order one and arbitrary rank are sketched in an Appendix.

Some combinatorial generating functions can be expressed in terms of coefficients of symmetric functions. In simple cases these can be determined directly however, the general case is ``too unwieldly to be useful''. Gessel describes conditions in which the resulting generating functions are D-finite. This work extends these results by giving a method for making the D-finite effective by determining the differential equation satisfied by the generating functions. Two examples of the method are given: the equations satisfied by $k$-regular graphs for $k=2,3,4$ and the equations satisfied by Young tableaux with each entry appearing $k$ times, for $k=2,3,4$.

These seminar notes constitute the proceedings of a seminar devoted to the analysis of algorithms and related topics. The subjects covered include combinatorics, symbolic computation, asymptotic analysis, computational biology, and average-case analysis of algorithms and data structures.

In this paper we discuss closed form representations of filter coefficients of wavelets on the real line, half real line and on compact intervals. We show that computer algebra can be applied to achieve this task. Moreover, we present a matrix analytical approach that unifies constructions of wavelets on the interval.

We give a randomized algorithm in deterministic time $O(N\log M)$ for estimating the score vector of matches between a text string of length $N$ and a pattern string of length $M$, i.e., the vector obtained when the pattern is slid along the text, and the number of matches is counted for each position. A direct application is approximate string matching. The randomized algorithm bases on convolution to find an estimator of the scores; the variance of the estimator is particularly small for scores that are close to $M$, i.e., for approximate occurrences of the pattern in the text. No assumption is made about the probabilistic characteristics of the input, or about the size of the alphabet. The solution extends to string matching with classes, class complements, ``never match'' and ``always match'' symbols, to the weighted case and to higher dimensions.

These seminar notes constitute the proceedings of a seminar devoted to the analysis of algorithms and related topics. The subjects covered include combinatorics, symbolic computation, asymptotic analysis, computational biology, and average-case analysis of algorithms and data structures.

We report on case studies where Zeilberger's fast algorithm and the other holonomy-based algorithms known so far for definite hypergeometric summation fail to find the minimal annihilating recurrence satisfied by the sum. To explain the phenomenon we propose a new elimination paradigm, together with a promising heuristic method which we hope to turn into an algorithm in the future. The approach applies to partial-finite functions as well and extends to the related algorithms.

We extend Zeilberger's fast algorithm for definite hypergeometric summation to non-hypergeometric holonomic sequences. The algorithm generalizes to the differential case and to $q$-calculus as well. Its theoretical justification is based on a description by linear operators and on the theory of holonomy.

We predict the number of hexagonal systems consisting of 24 and 25 hexagons to be $H_{24}=122237774262384$ and $H_{25}=606259305418149$, with 6 and 5 significant digits, respectively. Further estimates for $H_n$ up to ${n=31}$ are also given.

Une grande classe de fonctions spéciales et de suites combinatoires d'entiers qui sont représentées sous forme implicite par des systèmes d'équations fonctionnelles linéaires est sujette à un traitement par des méthodes de calcul formel. Les applications en sont la simplification d'expressions en termes de fonctions et suites spéciales, l'évaluation d'intégrales et de sommes paramétrées, les développements en série et asymptotiques, et la preuve automatique d'identités. La classe considérée jouit de nombreuses propriétés de clôture qui ont été étudiée depuis le début des années 1990 et qui ont récemment été transcrites en algorithmes. L'approche est la suivante. Pour prendre en compte un type d'opérateurs linéaires généraux, une classe d'algèbres de polynômes multivariés non commutatifs est introduite, à savoir les algèbres de Ore. Dans ce cadre, les fonctions spéciales et les suites combinatoires sont vues comme les zéros d'idéaux à gauche particuliers des algèbres de Ore. Des algorithmes pour la manipulation des fonctions et suites spéciales font alors appel à de l'élimination polynomiale dans ces algèbres d'opérateurs linéaires, pour lesquels des méthodes de bases de Gröbner non commutatives ont été developpées.

Many computations involving special functions, combinatorial sequences or their q-analogues can be performed using linear operators and simple arguments on the dimension of related vector spaces. In this article, we develop a theory of D-finite sequences and functions which provides a unified framework to express algorithms for computing sums and integrals and for the proof or discovery of multivariate identities. This approach is vindicated by an implementation.

The treatment of combinatorial expressions and special functions by linear operators is amenable to Gröbner basis methods. In this tutorial, we illustrate the applications of Gröbner bases to symbolic summation and integration.

This thesis shows how computer algebra makes it possible to manipulate a large class of sequences and functions that are solutions of linear operators, namely that of holonomic functions. This class contains numerous special functions, in one or several variables, as well as numerous combinatorial sequences. First, a theoretical framework is introduced in order to give algorithms for the closure properties of the holonomic class, to permit a zero test in this class, and to unify differential calculations with functions and calculations of recurrences with sequences. These methods are based on calculations by an extension of the theory of Gröbner bases in a framework of non-commutative polynomials, namely Ore polynomials. Two kinds of algorithms for symbolic definite and indefinite summation and integration are then developed, whose theoretical justification appeals to the theory of holonomic D-modules. The former resort to non-commutative polynomial elimination by Gröbner bases; the latter to algorithms to solve linear functional systems for their rational function solutions. 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. In particular, this type of calculation makes the automatic proof of summatory and integral identities possible. An implementation of these algorithms for the computer algebra system Maple has made it possible to give the first automatic proof of identities so far unreachable by computer algebra.

We extend Zeilberger's fast algorithm for definite hypergeometric summation to non-hypergeometric holonomic sequences. The algorithm generalizes to differential and q-cases as well. Its theoretical justification is based on a description by linear operators and on the theory of holonomy.

We present a computer algebra package in the Maple language for the symbolic manipulation of linear systems of differential and recurrence equations. This programme is especially designed to deal with so-called holonomic systems. This report also gives a theoretical justification to our implementation. The set of holonomic functions and sequences is a large class of objects. It forms an algebra and is closed under algebraic substitution and diagonal. An implementation of these properties makes it possible to perform computer assisted proofs of holonomic identities in a simple way, since a holonomic system has a normal form obtained by an extension of the Gröbner basis algorithm. For instance, combinatorial problems often lead to holonomic systems and to identities involving binomial coefficients. Many identities involving special functions are also captured by the theory of holonomy. Examples are given to show how some interesting identities are proved by our system.

This report presents three computer algebra packages in the Maple language for the symbolic manipulation of linear systems of differential and recurrence equations. They are especially designed to deal with so-called holonomic systems. We also give a theoretical justification to our implementation. The set of holonomic functions and sequences is a large class of objects. It forms an algebra and is closed under algebraic substitution and diagonal. An implementation of these properties makes it possible to perform computer assisted proofs of holonomic identities in a simple way, since any holonomic system has a normal form obtained by an extension of the Gröbner basis algorithm. For instance, combinatorial problems often lead to holonomic systems and to identities involving binomial coefficients. Many identities involving special functions are also captured by the theory of holonomy. Examples are given to show how some interesting identities are proved by our system.