Formulae and Asymptotics for Coefficients of Algebraic Functions. (January 2015)

• Record Type: Journal Article
• Authors: BANDERIER, CYRIL; DRMOTA, MICHAEL
• Editors: Broutin, Nicolas; Fill, James Allen; Nebel, Markus; Ward, Mark Daniel
• Is Part Of: Combinatorics, probability and computing. Volume 24:Number 1(2015:Jan.)
• Page Start: 1
• Page End: 53
• Publication Date: 2015-01
• Subjects: Primary 05A15, -- 05A16, -- Secondary 68Q45, -- 68R15; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548314000728
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : We study the coefficients of algebraic functions ∑ n ≥0 f n z n . First, we recall the too-little-known fact that these coefficients f n always admit a closed form. Then we study their asymptotics, known to be of the type f n ~ CA n n α . When the function is a power series associated to a context-free grammar, we solve a folklore conjecture: the critical exponents α cannot be 1/3 or −5/2; they in fact belong to a proper subset of the dyadic numbers. We initiate the study of the set of possible values for A . We extend what Philippe Flajolet called the Drmota–Lalley–Woods theorem (which states that α=−3/2 when the dependency graph associated to the algebraic system defining the function is strongly connected). We fully characterize the possible singular behaviours in the non-strongly connected case. As a corollary, the generating functions of certain lattice paths and planar maps are not determined by a context-free grammar ( i.e., their generating functions are not ℕ-algebraic). We give examples of Gaussian limit laws (beyond the case of the Drmota–Lalley–Woods theorem), and examples of non-Gaussian limit laws. We then extend our work to systems involving non-polynomial entire functions (non-strongly connected systems, fixed points of entire functions with positive coefficients). We give several closure properties for ℕ-algebraic functions. We end by discussing a few extensions of our results (infinite systems of equations, algorithmic aspects).