Asymptotics/growth for coefficients of algebraic power series

Assume that the formal power series $a(z)=\sum\limits_{n\geq 1} a_n z^n$ satisfies an algebraic equation with polynomial coefficients (that is, there exists a nonzero polynomial $F(z,y)$ such that $F(z,a(z))=0$), and a finite number of terms of $a(z)$ determine uniquely the whole series as a solution to that equation.

Assume also that the sequence $\{a_n\}$ is increasing (and if necessary, one can even assume that all $a_i$ are integers), and grows polynomially, that is for some $C,d$ we have $a_n<Cn^d$ for all $n>>1$.

Is it true that there exists "a limit value of the exponent $d$"? More precisely, is it true that the infimum of exponents $d_1$ such that $a_n< C_1 n^{d_1}$ for some $C_1$ (depending on $d_1$) and all $n>>1$ coincides with the supremum of exponents $d_2$ such that $a_n > C_2 n^{d_2}$ for some $C_2$ (depending on $d_2$) and all $n>>1$?

-

1 Answer

This should follow from Theorem VII.8 in Flajolet and Sedgewick's Analytic Combinatorics (freely available at the link). As I understand the argument, you can obtain a straightforward general form for asymptotics of coefficients of algebraic generating functions by expanding in Puiseux series around the dominant poles.

This implies the dominant term is a finite sum of terms of the form $n^d \zeta^n$ where $|\zeta| = 1$ for some $d \in \mathbb{Q}$, and the increasing growth condition should rule out the terms with $\zeta \neq 1$ messing up the asymptotics.

-
Thanks for the link, it seems to be almost exactly what is needed! –  Vladimir Dotsenko Aug 12 '11 at 8:16
dominant poles or dominant singularities? –  Andrew MacFie Oct 19 '13 at 2:52