Skip to Main content Skip to Navigation
Conference papers

Coefficients of algebraic functions: formulae and asymptotics

Abstract : 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).
Document type :
Conference papers
Complete list of metadata
Contributor : Alain Monteil Connect in order to contact the contributor
Submitted on : Tuesday, November 17, 2015 - 10:19:51 AM
Last modification on : Wednesday, October 27, 2021 - 2:52:37 PM
Long-term archiving on: : Thursday, February 18, 2016 - 11:37:16 AM


Publisher files allowed on an open archive



Cyril Banderier, Michael Drmota. Coefficients of algebraic functions: formulae and asymptotics. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. pp.1065-1076, ⟨10.46298/dmtcs.2366⟩. ⟨hal-01229681⟩



Record views


Files downloads