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


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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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