Asymptotics for the coefficients of a rational function - MathOverflow most recent 30 from http://mathoverflow.net 2013-06-20T05:14:07Z http://mathoverflow.net/feeds/question/103553 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/103553/asymptotics-for-the-coefficients-of-a-rational-function Asymptotics for the coefficients of a rational function TJ 2012-07-30T21:30:07Z 2012-08-08T19:57:56Z <p>Let $(a_n)$ be a sequence of non-negative real numbers and assume that the resulting power series defines a rational function </p> <p>$$\sum_{n=0}^\infty a_n x^n = \dfrac{f(x)}{(1-x^{k_1})\cdots (1-x^{k_d})}$$ where $k_1,...,k_d>0$ are integers and $f(x)$ is a real polynomial s.t. $f(1) \neq 0$. It is not hard to show that $$\frac{f(1)}{k_1 \cdots k_d}\le \limsup \frac{a_n}{n^{d-1}} \cdot (d-1)! \le f(1)$$</p> <p>As a special case we obtain for example $\limsup = f(1)$ if $k_1=\cdots k_d = 1$ (this is in fact not only the limsup but even the limit of the sequence). </p> <p><strong>Questions:</strong> 1) Are there known formulas or better estimates for the $\limsup$ above in terms of $f$ and $k_1,...,k_d$ ? </p> <p>2) Are there particular techniques, that can be used to obtain good estimates (the one above is simply based on the binomial series for $(1-x)^{-d}$). </p> <p><strong>Background:</strong> Such rational functions occur as Poincaré series of graded Noetherian algebras where $a_n$ is the dimension of the subspace of homogeneous lements of degree $n$. I'm trying to relate this quantity to the rational function. </p> http://mathoverflow.net/questions/103553/asymptotics-for-the-coefficients-of-a-rational-function/103562#103562 Answer by Robert Israel for Asymptotics for the coefficients of a rational function Robert Israel 2012-07-30T23:39:19Z 2012-08-01T01:27:50Z <p>We have the partial fraction decomposition $$\dfrac{f(x)}{(1-x^{k_1}) \ldots (1 - x^{k_d})} = \text{polynomial}(x) + \sum_\omega \sum_{j=1}^{d(\omega)} b_{\omega,j} ( \omega-x)^{-j}$$ where $\omega$ are the roots of $(1 - x^{k_1})\ldots(1 - x^{k_d})$ and $d(\omega)$ is the multiplicity of the root $\omega$. Then $(\omega-x)^{-j} = \sum_{n=0}^\infty {{j+n-1} \choose {j-1}} \omega^{-j-n} x^n$. The asymptotics will be dominated by the $\omega$'s with highest multiplicity, namely the $\gcd(k_1, \ldots, k_d)$'th roots of unity, which have multiplicity $d$ (assuming $f(\omega) \ne 0$). In particular if $\gcd(k_1,\ldots,k_d) = 1$, we have $$a_n \sim \frac{f(1)}{k_1 \ldots k_d} {{d+n-1} \choose {d-1}} \sim \frac{f(1) n^{d-1}}{(d-1)!\; k_1 \ldots k_d}$$ But if $\gcd(k_1,\ldots,k_d) = g > 1$ we also have to consider the other $g$'th roots of unity: $$a_n \sim \sum_{\omega^g=1} \dfrac{f(\omega) n^{d-1}}{\omega^{n + k_1 + \ldots + k_d} (d-1)!\; k_1 \ldots k_d}$$ </p> <p>EDIT: For example, with $f(x) = x + c(x-1)$, $d=2$, $k_1 = 2$, $k_2 = 4$ I get $a_n \sim \dfrac {1 - (2c+1)(-1)^n}{8} n$ which, by the way, shows that your upper bound is wrong since $c$ can be arbitrary without affecting $f(1)$.</p>