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

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.

share|improve this question
2  
You might also find the first few sections in chapter 4 of Enumerative Combinatorics, Volume I, by Richard Stanley helpful. –  Patricia Hersh Aug 1 '12 at 1:46
    
Thanks for the reference. It's in fact interesting (in particular proposition 4.4.1). –  tj_ Aug 9 '12 at 19:18
add comment

1 Answer

up vote 8 down vote accepted

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

share|improve this answer
    
Robert, thanks for your answer. However, I need little help in the last step: I understand $$a_n \sim \sum_{\omega^g=1} \dfrac{b_{\omega,d}\; n^{d-1}}{\omega^{n + d} (d-1)! }\;\;,\qquad f(\omega)=b_{\omega,d} \prod_{\nu \neq \omega}(\nu-\omega)^d$$ where $\omega^g=1$. So what I'm missing is the relation $k_1 \cdots k_d\; \omega^{k_1 + \cdots + k_d}=\omega^d\prod_{\nu \neq \omega}(\nu - \omega)^d$. –  tj_ Aug 8 '12 at 19:05
    
Nb. My upper bound is obtained under the additional assumption $a_n \ge 0$. In your example $$\dfrac{(1+c)x -c}{(1-x^2)(1-x^4)}$$ the coefficients have alternating sign (if $c>0$) since $1/(1-x^2)(1-x^4)$ is even with non-negative coefficients. But your limit-formula is superior to my estimates in any way. –  tj_ Aug 8 '12 at 19:05
2  
@TJ: If $\omega$ is a root of $g(z) = (1 - z^{k_1})\ldots(1-z^{k_d})$ with multiplicity $d$, i.e. a root of each $1 - z^{k_j}$, then $\lim_{z \to \omega} \frac{1 - z^{k_j}}{\omega - z} = k_j \omega^{k_j-1} = k_j \omega^{-1}$. The coefficient of $(\omega-z)^{-d}$ in the partial fraction decomposition of $f(z)/g(z)$ is $$ \lim_{z \to \omega} \frac{f(z) (\omega - z)^d}{g(z)} = \lim_{z \to \omega} f(z) \frac{\omega - z}{1 - z^{k_1}} \ldots \frac{\omega - z}{1 - z^{k_d}} = f(\omega) \prod_{j=1}^d (\omega/k_j) $$ –  Robert Israel Aug 8 '12 at 20:47
    
Now everything is clear. Thank you so much! –  tj_ Aug 9 '12 at 18:41
add comment

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.