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

https://hal.inria.fr/hal-01229681
Contributor : Alain Monteil <>
Submitted on : Tuesday, November 17, 2015 - 10:19:51 AM
Last modification on : Saturday, February 15, 2020 - 2:06:27 AM
Long-term archiving on: : Thursday, February 18, 2016 - 11:37:16 AM

File

dmAS0190.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : hal-01229681, version 1

Collections

Citation

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. ⟨hal-01229681⟩

Share

Metrics

Record views

138

Files downloads

792