Asymptotics for the coefficients of a rational function

2012-07-30T21:30:07Z

Let $(a_n)$ be a sequence of non-negative real numbers and assume that the resulting power series defines a rational function

$$\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)$$

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).

Questions: 1) Are there known formulas or better estimates for the $\limsup$ above in terms of $f$ and $k_1,...,k_d$ ?

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}$).

Background: 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.

Answer by Robert Israel for Asymptotics for the coefficients of a rational function

2012-07-30T23:39:19Z

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

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)$.

Asymptotics for the coefficients of a rational function - MathOverflow

Asymptotics for the coefficients of a rational function

Answer by Robert Israel for Asymptotics for the coefficients of a rational function