ABSTRACT
Differentially finite series are solutions of linear differential equations with polynomial coefficients. P-recursive sequences are solutions of linear recurrences with polynomial coefficients. Corresponding notions are obtained by replacing classical differentiation or difference operators by their q-analogues. All these objects share numerous properties that are described in the framework of "D-finiteness". Our aim in this area is to enable computer algebra systems to deal in an algorithmic way with a large number of special functions and sequences. Indeed, it can be estimated that approximately 60% of the functions described in Abramowitz & Stegun's handbook [1] fall into this category, as well as 25% of the sequences in Sloane's encyclopedia [20,21].
In a way, D-finite sequences or series are non-commutative analogues of algebraic numbers: the role of the minimal polynomial is played by a linear operator.Ore [14] described a non-commutative version of Euclidean division and extended Euclid algorithm for these linear operators (known as Ore polynomials). In the same way as in the commutative case, these algorithms make several closure properties effective (see[22]). It follows that identities between these functions or sequences can be proved or computed automatically. Part of the success of the <sc>gfun</sc> package [17] comes from an implementation of these operations. Another part comes from the possibility of <i>discovering</i> such identities empirically, with Padé-Hermite approximants on power series [2] taking the place of the LLL algorithm on floating-point numbers.
The discovery that a series is D-finite is also important from the complexity point of view: several operations can be performed on D-finite series at a lower cost than on arbitrary power series. This includes multiplication, but also evaluation at rational points by binary splitting [4]. A typical application is the numerical evaluation of π in computer algebra systems; we give another one in these proceedings [3].
Also, the local behaviour of solutions of linear differential equations in the neighbourhood of their singularities is well understood [9] and implementations of algorithms computing the corresponding expansions are available [24, 13]. This gives access to the asymptotics of numerous sequences or to analytic proofs that sequences or functions cannot satisfy such equations [10]Results of a more algebraic nature are obtained by differential Galois theory [18, 19], which naturally shares many subroutines with algorithms for D-finite series.
The truly spectacular applications of D-finiteness come from the multivariate case: instead of series or sequences, one works with multivariate series or sequences, or with sequences of series or polynomials,.... They obey systems of linear operators that may be of differential, difference, <i>q</i>-difference or mixed types, with the extra constraint that a finite number of initial conditions are sufficient to specify the solution. This is a non-commutative analogue of polynomial systems with a finite number of solutions. It turns out that, as in the polynomial case, Gröbner bases give algorithmic answers to many decision questions, by providing normal forms in a finite dimensional vector space. This has been observed first in the differential case [11, 23] and then extended to the more general multivariate Ore case [8].
A crucial insight of Zeilberger [27, 15] is that elimination in this non-commutative setting computes definite integrals or sums. This is known as <i>creative telescoping</i>. In the<i>hypergeometric</i> setting (when the quotient is a vector space of dimension1), a fast algorithm for this operation is known as Zeilberger's fast algorithm [26]. In the more general case, Gröbner bases are of help in this elimination. This is true in the differential case [16, 25] and to a large extent in the more general multivariate case [8]. Also, Zeilberger's fast algorithm has been generalized to the multivariate Ore case by Chyzak [5, 6]. Still, various efficiency issues remain and phenomena of non-minimality of the eliminated operators are not completely understood.
A further generalization of D-finite series is due to Gessel [12] who developed a theory of symmetric series. These series are such than when all but a finite number of their variables (in a certain basis) are specialized to0, the resulting series is D-finite in the previous sense. Closure properties under scalar product lead to proofs of D-finiteness (in the classical sense) for various combinatorial sequences. Again, algorithms based on Gröbner bases make these operations effective [7].
The talk will survey the nicest of these algorithms and their applications. I will also indicate where current work is in progress, or where more work is needed.
- M. Abramowitz and I. A. Stegun, editors. Handbook of mathematical functions with formulas, graphs, and mathematical tables. Dover Publications Inc., New York, 1992. Reprint of the 1972 edition.]] Google ScholarDigital Library
- B. Beckermann and G. Labahn. A uniform approach for the fast computation of matrix-type Padé approximants. SIAM Journal on Matrix Analysis and Applications, 15(3):804--823, July 1994.]] Google ScholarDigital Library
- A. Bostan, T. Cluzeau, and B. Salvy. Fast algorithms for polynomial solutions of linear differential equations. In M. Kauers, editor, Symbolic and Algebraic Computation, New York, 2005. ACM Press. Proceedings of ISSAC'05, July 2005, Beijing, China.]] Google ScholarDigital Library
- D. V. Chudnovsky and G. V. Chudnovsky. Approximations and complex multiplication according to Ramanujan. In Ramanujan revisited, pages 375--472. Academic Press, Boston, MA, 1988.]]Google Scholar
- F. Chyzak. Fonctions holonomes en calcul formel. Phd thesis, école polytechnique, 1998.]]Google Scholar
- F. Chyzak. An extension of Zeilberger's fast algorithm to general holonomic functions. Discrete Mathematics, 217(1-3):115--134, 2000.]] Google ScholarDigital Library
- F. Chyzak, M. Mishna, and B. Salvy. Effective scalar products of D-finite symmetric functions. Journal of Combinatorial Theory, Series A, 2005. 51 pages. To appear.]] Google ScholarDigital Library
- F. Chyzak and B. Salvy. Non-commutative elimination in Ore algebras proves multivariate holonomic identities. Journal of Symbolic Computation, 26(2):187--227, Aug. 1998.]] Google ScholarDigital Library
- E. Fabry. Sur les intégrales des équations différentielles linéaires à coefficients rationnels. Thèse de doctorat ès sciences mathématiques, Faculté des Sciences de Paris, July 1885.]]Google Scholar
- P. Flajolet, S. Gerhold, and B. Salvy. On the non-holonomic character of logarithms, powers, and the nth prime function. The Electronic Journal of Combinatorics, 11(2), Apr. 2005. A2, 16 pages.]]Google ScholarCross Ref
- A. Galligo. Some algorithmic questions on ideals of differential operators. In B. F. Caviness, editor, Proceedings EUROCAL'85, volume 204 of Lecture Notes in Computer Science, pages 413--421. Springer-Verlag, 1985.]]Google Scholar
- I. M. Gessel. Symmetric functions and P-recursiveness. Journal of Combinatorial Theory, Series A, 53:257--285, 1990.]] Google ScholarDigital Library
- M. van Hoeij. Formal solutions and factorization of differential operators with power series coefficients. Journal of Symbolic Computation, 24(1):1--30, 1997.]] Google ScholarDigital Library
- O. Ore. Theory of non-commutative polynomials. Annals of Mathematics, 34:480--508, 1933.]]Google ScholarCross Ref
- M. Petkovšek, H. S. Wilf, and D. Zeilberger. A=B. A. K. Peters, Wellesley, MA, 1996.]]Google Scholar
- M. Saito, B. Sturmfels, and N. Takayama. Gröbner deformations of hypergeometric differential equations. Springer-Verlag, Berlin, 2000.]]Google ScholarCross Ref
- B. Salvy and P. Zimmermann. Gfun: a Maple package for the manipulation of generating and holonomic functions in one variable. ACM Transactions on Mathematical Software, 20(2):163--177, 1994.]] Google ScholarDigital Library
- M. F. Singer. Liouvillian solutions of n-th order homogeneous linear differential equations. American Journal of Mathematics, 103(4):661--682, 1981.]]Google ScholarCross Ref
- M. F. Singer. Algebraic relations among solutions of linear differential equations. Transactions of the American Mathematical Society, 295(2):753--763, 1986.]]Google ScholarCross Ref
- N. J. A. Sloane. The On-Line Encyclopedia of Integer Sequences. 2005. Published electronically at http://www.research.att.com/~njas/sequences/.]]Google Scholar
- N. J. A. Sloane and S. Plouffe. The Encyclopedia of Integer Sequences. Academic Press, 1995.]]Google Scholar
- R. P. Stanley. Enumerative combinatorics, volume2. Cambridge University Press, 1999.]] Google ScholarDigital Library
- N. Takayama. Gröbner basis and the problem of contiguous relations. Japan Journal of Applied Mathematics, (1):147--160, 1989.]]Google ScholarCross Ref
- É. Tournier. Solutions formelles d'équations différentielles. Doctorat d'état, Université scientifique, technologique et médicale de Grenoble, 1987.]]Google Scholar
- H. Tsai. Algorithms for algebraic analysis. PhD thesis, University of California at Berkeley, Spring 2000.]] Google ScholarDigital Library
- H. S. Wilf and D. Zeilberger. Rational function certification of multisum/integral/"q" identities. Bulletin of the American Mathematical Society, 27(1):148--153, July 1992.]]Google ScholarCross Ref
- D. Zeilberger. A holonomic systems approach to special functions identities. Journal of Computational and Applied Mathematics, 32(3):321--368, 1990.]] Google ScholarDigital Library
Index Terms
- D-finiteness: algorithms and applications
Recommendations
GFUN: a Maple package for the manipulation of generating and holonomic functions in one variable
We describe the GFUN package which contains functions for manipulating sequences, linear recurrences, or differential equations and generating functions of various types. This article is intended both as an elementary introduction to the subject and as ...
Low complexity algorithms for linear recurrences
ISSAC '06: Proceedings of the 2006 international symposium on Symbolic and algebraic computationWe 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 ...
Fast algorithms for polynomial solutions of linear differential equations
ISSAC '05: Proceedings of the 2005 international symposium on Symbolic and algebraic computationWe investigate polynomial solutions of homogeneous linear differential equations with coefficients that are polynomials with integer coefficients. The problems we consider are the existence of nonzero polynomial solutions, the determination of the ...
Comments