Authors: Cyril Banderier ¹; Michael Drmota ²

• 1 Laboratoire d'Informatique de Paris-Nord
• 2 Institut für Diskrete Mathematik und Geometrie [Wien]

This paper studies the coefficients of algebraic functions. First, we recall the too-little-known fact that these coefficients $f_n$ have a closed form. Then, we study their asymptotics, known to be of the type $f_n \sim C A^n n^{\alpha}$. When the function is a power series associated to a context-free grammar, we solve a folklore conjecture: the appearing critical exponents $\alpha$ can not be $^1/_3$ or $^{-5}/_2$, they in fact belong to a subset of dyadic numbers. We extend what Philippe Flajolet called the Drmota-Lalley-Woods theorem (which is assuring $\alpha=^{-3}/_2$ as soon as a "dependency graph" associated to the algebraic system defining the function is strongly connected): We fully characterize the possible critical exponents in the non-strongly connected case. As a corollary, it shows that certain lattice paths and planar maps can not be generated by a context-free grammar (i.e., their generating function is not $\mathbb{N}-algebraic). We end by discussing some extensions of this work (limit laws, systems involving non-polynomial entire functions, algorithmic aspects).