Symbolic-Numeric Tools for Analytic Combinatorics in Several Variables

International audienceAnalytic combinatorics studies the asymptotic behaviour of sequences throughthe analytic properties of their generating functions. This article provideseffective algorithms required for the study of analytic combinatorics inseveral variables, together with their complexity analyses. Given amultivariate rational function we show how to compute its smooth isolatedcritical points, with respect to a polynomial map encoding asymptoticbehaviour, in complexity singly exponential in the degree of its denominator.We introduce a numerical Kronecker representation for solutions of polynomialsystems with rational coefficients and show that it can be used to decideseveral properties (0 coordinate, equal coordinates, sign conditions for realsolutions, and vanishing of a polynomial) in good bit complexity. Among thecritical points, those that are minimal---a property governed by inequalitieson the moduli of the coordinates---typically determine the dominant asymptoticsof the diagonal coefficient sequence. When the Taylor expansion at the originhas all non-negative coefficients (known as the `combinatorial case') and underregularity conditions, we utilize this Kronecker representation to determineprobabilistically the minimal critical points in complexity singly exponentialin the degree of the denominator, with good control over the exponent in thebit complexity estimate. Generically in the combinatorial case, this allows oneto automatically and rigorously determine asymptotics for the diagonalcoefficient sequence. Examples obtained with a preliminary implementation showthe wide applicability of this approach