Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$?

share|improve this question

1 Answer 1

up vote 5 down vote accepted

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.

share|improve this answer
    
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.