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.
Origin | Files produced by the author(s) |
---|