Algorithms for discrete differential equations of order 1 - INRIA - Institut National de Recherche en Informatique et en Automatique
Conference Papers Year : 2022

Algorithms for discrete differential equations of order 1

Abstract

Discrete differential equations of order 1 are equations relating polynomially $F(t,u)$, a power series 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\'elou, reminiscent of Popescu's theorem in commutative algebra, states that $F$ is \emph{algebraic}. We address algorithmic and complexity questions related to this result. In \emph{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 \emph{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.
Fichier principal
Vignette du fichier
BoChNoSa22-hal-v2.pdf (846.66 Ko) Télécharger le fichier
Origin Files produced by the author(s)

Dates and versions

hal-03616406 , version 1 (22-03-2022)
hal-03616406 , version 2 (20-05-2022)

Licence

Identifiers

  • HAL Id : hal-03616406 , version 2

Cite

Alin Bostan, Frédéric Chyzak, Hadrien Notarantonio, Mohab Safey El Din. Algorithms for discrete differential equations of order 1. ISSAC 2022 - 47th International Symposium on Symbolic and Algebraic Computation, Jul 2022, Lille, France. pp.101-110. ⟨hal-03616406v2⟩
332 View
301 Download

Share

More