Discrete Differential Equations (DDEs) are functional equations that relate algebraically a power series F(t, u) in t with polynomial coefficients in a “catalytic” variable u and the specializations, say at u = 1, of F(t, u) and of some of its partial derivatives in u. If a DDE is of a fixed-point type then its solution F(t, u) is unique, and an elegant result by Bousquet-Mélou and Jehanne implies that F(t, u) is an algebraic power series. Last year, Bostan et al. initiated a systematic algorithmic study of DDEs of order 1. We generalize this study to DDEs of arbitrary order. First, we propose nontrivial extensions of algorithms based on polynomial elimination and on the guess-and-prove paradigm. Second, we design two brand-new algorithms that exploit the special structure of the underlying polynomial systems. Last, but not least, we report on implementations that are able to solve highly challenging DDEs with a combinatorial origin.

Discrete differential equations of order 1 relate polynomially a power series F(t,u) in t with polynomial coefficients in a ''catalytic'' variable~u and one of its specializations, say F(t,u). 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élou and Jehanne, reminiscent of Popescu's theorem in commutative algebra, states that F is algebraic. We address algorithmic and complexity questions related to this result. In 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 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.