Alin Bostan
ABSTRACT
It is classical that univariate algebraic functions satisfy linear differential equations with polynomial coefficients. 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 deduce a fast algorithm for the expansion of algebraic series.
- N. H. Abel. (Euvres complètes. Tome II. Éd. J. Gabay, 1992. Reprint of the 2nd (1881) ed. Available at http://gallica.bnf.fr.Google Scholar
- G. Almkvist and D. Zeilberger. The method of differentiating under the integral sign. J. Symbolic Comput., 10(6):571--591, 1990. Google ScholarDigital Library
- M. Apagodu and D. Zeilberger. Multi-variable Zeilberger and Almkvist-Zeilberger algorithms and the sharpening of Wilf-Zeilberger theory. Adv. in Appl. Math., 37(2):139--152, 2006.Google ScholarDigital Library
- D. Bini and V. Y. Pan. Polynomial and matrix computations. Vol. 1. Birkhäuser, 1994. Google ScholarDigital Library
- W. Bosma, J. Cannon, and C. Playoust. The Magma algebra system I: The user language. J. Symbolic Comput., 24(3-4):235--265, 1997. Google ScholarDigital Library
- A. Bostan, P. Gaudry, and É. Schost. Linear recurrences with polynomial coefficients and computation of the Cartier-Manin operator on hyperelliptic curves. SIAM J. Comput., 36(6):1777--1806, 2007. Google ScholarDigital Library
- G. Chèze and G. Lecerf. Lifting and recombination techniques for absolute factorization. J. Complexity, doi:10.1016/j.jco.2007.01.008, in press, 2007. Google ScholarDigital Library
- D. V. Chudnovsky and G. V. Chudnovsky. On expansion of algebraic functions in power and Puiseux series. I. J. Complexity, 2(4):271--294, 1986. Google ScholarDigital Library
- D. V. Chudnovsky and G. V. Chudnovsky. On expansion of algebraic functions in power and Puiseux series. II. J. Complexity, 3(1):1--25, 1987. Google ScholarDigital Library
- D. V. Chudnovsky and G. V. Chudnovsky. Computer algebra in the service of mathematical physics and number theory. In Computers in mathematics (Stanford, CA, 1986), 109--232, 1990. Dekker.Google Scholar
- J. Cockle. On transcendental and algebraic solution. Philosophical Magazine, XXI:379--383, 1861.Google Scholar
- L. Comtet. Calcul pratique des coefficients de Taylor d'une fonction algébrique. Enseignement Math. (2), 10:267--270, 1964.Google Scholar
- O. Cormier, M. F. Singer, B. M. Trager, and F. Ulmer. Linear differential operators for polynomial equations. J. Symbolic Comput., 34(5):355--398, 2002. Google ScholarDigital Library
- J. Gray. Linear differential equations and group theory from Riemann to Poincaré. Birkhäuser, 1986.Google ScholarCross Ref
- R. Harley. On the theory of the transcendental solution of algebraic equations. Quart. J. of Pure and Applied Math, 5:337--361, 1862.Google Scholar
- J. M. Nahay. Linear differential resolvents. PhD thesis, Rutgers University, 2000.Google Scholar
- J. M. Nahay. Linear relations among algebraic solutions of differential equations. J. Differential Equations, 191(2):323--347, 2003.Google ScholarCross Ref
- J. M. Nahay. Differential resolvents of minimal order and weight. Int. J. Math. and Math. Sciences, 2004(53-56):2867--2893, 2004.Google ScholarCross Ref
- A. Storjohann. Notes on computing minimal approximant bases. Dagstuhl preprint, 2006.Google Scholar
- N. Takayama. An approach to the zero recognition problem by Buchberger algorithm. J. Symbolic Comput., 14(2-3):265--282, 1992. Google ScholarDigital Library
- J. Tannery. Propriétés des intégrales deséquations différentielles linéaires à coefficients variables. Annales scientifiques de l'ENS Sér. 2, 4:113--182, 1875.Google Scholar
- H. Tsai. Weyl closure of a linear differential operator. J. Symbolic Comput., 29(4-5):747--775, 2000. Google ScholarDigital Library
- J. von zur Gathen and J. Gerhard. Modern computer algebra. Cambridge University Press, 2nd ed., 2003. Google ScholarDigital Library
- C. K. Yap. Fundamental Problems in Algorithmic Algebra. Oxford University Press, New York, 2000. Google ScholarDigital Library
- D. Zeilberger. The method of creative telescoping. J. Symbolic Comput., 11(3):195--204, 1991. Google ScholarDigital Library
Index Terms
- Differential equations for algebraic functions
Recommendations
Generalized Hermite Reduction, Creative Telescoping and Definite Integration of D-Finite Functions
ISSAC '18: Proceedings of the 2018 ACM International Symposium on Symbolic and Algebraic ComputationHermite 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 ...
Creative telescoping for rational functions using the griffiths: dwork method
ISSAC '13: Proceedings of the 38th International Symposium on Symbolic and Algebraic ComputationCreative telescoping algorithms compute linear differential equations satisfied by multiple integrals with parameters. We describe a precise and elementary algorithmic version of the Griffiths-Dwork method for the creative telescoping of rational ...
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 ...
Comments