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
    Aug 1, 2012 at 1:46
  • $\begingroup$ Thanks for the reference. It's in fact interesting (in particular proposition 4.4.1). $\endgroup$
    – tj_
    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_
    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_
    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
    Aug 8, 2012 at 20:47
  • $\begingroup$ Now everything is clear. Thank you so much! $\endgroup$
    – tj_
    Aug 9, 2012 at 18:41

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .