Differential Equations for Algebraic Functions

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.

Cited by in corpus (24)

• Creative Telescoping for Holonomic Functions
• High order Fuchsian equations for the square lattice Ising model: ${\tilde{\chi }}^{(5)}$
• Explicit formula for the generating series of diagonal 3D rook paths
• Controlled non uniform random generation of decomposable structures
• Power Series Solutions of Singular (q)-Differential Equations
• Fast Computation of Common Left Multiples of Linear Ordinary Differential Operators
• Automatic Classification of Restricted Lattice Walks
• Bounded-degree factors of lacunary multivariate polynomials
• On the algebraicity of Puiseux series
• Record statistics of integrated random walks and the random acceleration process
• Survival probability of random walks and Lévy flights with stochastic resetting
• Boolean Cumulants and Subordination in Free Probability
• Algebraic Diagonals and Walks
• Fast Computation of the Nth Term of an Algebraic Series over a Finite Prime Field
• Linear differential operators for generic algebraic curves
• Trading Order for Degree in Creative Telescoping
• Bounds for Substituting Algebraic Functions into D-finite Functions
• Complexity of Creative Telescoping for Bivariate Rational Functions
• Residues and Telescopers for Rational Functions
• Power Series Approximations to Fekete Polynomials
• P-finite Recurrences From Generating Functions with Roots of Polynomials
• Degree bounds for linear differential equations and recurrences
• Cogrowth Series for Free Products of Finite Groups
• Joint differential resolvents for pseudopolynomials