7
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ You might also find the first few sections in chapter 4 of Enumerative Combinatorics, Volume I, by Richard Stanley helpful. $\endgroup$
    – Patricia Hersh
    Commented Aug 1, 2012 at 1:46
  • $\begingroup$ Thanks for the reference. It's in fact interesting (in particular proposition 4.4.1). $\endgroup$
    – tj_
    Commented Aug 9, 2012 at 19:18

1 Answer 1

Reset to default
8
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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$. $\endgroup$
    – tj_
    Commented Aug 8, 2012 at 19:05
  • $\begingroup$ 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. $\endgroup$
    – tj_
    Commented Aug 8, 2012 at 19:05
  • 2
    $\begingroup$ @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) $$ $\endgroup$
    – Robert Israel
    Commented Aug 8, 2012 at 20:47
  • $\begingroup$ Now everything is clear. Thank you so much! $\endgroup$
    – tj_
    Commented Aug 9, 2012 at 18:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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