Skip to Main content Skip to Navigation
New interface
Conference papers

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.
Complete list of metadata

https://hal.inria.fr/hal-03616406
Contributor : Hadrien Notarantonio Connect in order to contact the contributor
Submitted on : Friday, May 20, 2022 - 4:33:56 PM
Last modification on : Friday, September 16, 2022 - 3:56:31 PM

File

BoChNoSa22-hal-v2.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-03616406, version 2

Citation

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⟩

Share

Metrics

Record views

165

Files downloads

126