DMTCS Proceedings, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)

Font Size:  Small  Medium  Large

Coefficients of algebraic functions: formulae and asymptotics

Cyril Banderier, Michael Drmota

Abstract


This paper studies the coefficients of algebraic functions. First, we recall the too-little-known fact that these coefficients fn have a closed form. Then, we study their asymptotics, known to be of the type fn ∼C An nα. When the function is a power series associated to a context-free grammar, we solve a folklore conjecture: the appearing critical exponents α 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 α=-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 &N;-algebraic). We end by discussing some extensions of this work (limit laws, systems involving non-polynomial entire functions, algorithmic aspects). &bigskip;
Résumé. Cet article a pour héros les coefficients des fonctions algébriques. Après avoir rappelé le fait trop peu connu que ces coefficients fn admettent toujours une forme close, nous étudions leur asymptotique fn ∼C An nα. Lorsque la fonction algébrique est la série génératrice d'une grammaire non-contextuelle, nous résolvons une vieille conjecture du folklore : les exposants critiques α ne peuvent pas être 1/3 ou -5/2 et sont en fait restreints á un sous-ensemble des nombres dyadiques. Nous étendons ce que Philippe Flajolet appelait le théorème de Drmota-Lalley-Woods (qui affirme que α=-3/2 dès lors qu'un "graphe de dépendance" associé au système algébrique est fortement connexe) : nous caractérisons complètement les exposants critiques dans le cas non fortement connexe. Un corolaire immédiat est que certaines marches et cartes planaires ne peuvent pas être engendrées par une grammaire non-contextuelle non ambigüe (i. e., leur série génératrice n'est pas &N;-algébrique). Nous terminons par la discussion de diverses extensions de nos résultats (lois limites, systèmes d'équations de degré infini, aspects algorithmiques).

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional