Suppose that a rational generating function is given representing the function $f(x) = \sum_{i=0}^{2n}{c_i x^i}$ where $c_i \in \mathbb{N}$

The goal is to determine if the coefficient in the middle, $c_n$, is nonzero or not.

For example, we could be given $f(x) = \frac{1 - 10x^9 + 9x^{10}}{(x - 1)^2}$, which represents $1 + 2x + 3x^2 + \cdots + 9x^8$. We are interested, in this case, in the middle coefficient, which happens to be 5.

Original Formulation

The actual value can be determined by evaluating a contour integral. This is accomplished by first multiplying $f(x)$ by $x^{-n}$. Then, rewriting the variable $x$ as $x\cdot e^{i t}$ and finally evaluating the integral $\int_C{f(x)dt}$. The result of all of this is the coefficient in question.

The Goal

I seek to find alternative formulations to this problem. Let me give some examples.

Example 1 : "Tiling"

Start with the original formula $f(x)$. Make a copy, for example $f(y)$, by rewriting $x$ as $y$. Then we can subtract the second function from the first, eliminating the first coefficient. We repeat additions and subtractions (possibly infinitely many times) until all coefficients except for the middle one have been eliminated.

Example 2 : "Division"

We multiply $f(x)$ by a function $g(y)$, where $g(y) = \frac{1}{1-x^{2n+1}}$, essentially making the series repeat forever. We then divide this by $x^n\cdot g(y)$, and get the remainder. This remainder is the first half of the original series, and $c_n$ can be easily obtained from this.

What is desired / Motivations

I'd simply like to have alternative formulations for the solution. I'm using this for an algorithm, and I'd like to publish this with anyone who gives a formulation that provides a quick result.


I'm not sure I understand exactly what you want, but if you differentiate the function $n$ times and then evaluate the result at $x=0$ you get $n! c_n$.

  • $\begingroup$ That's what I want, except that differentiation is hard. It's probably faster to integrate once. Great idea, though! $\endgroup$ – Matt Groff Oct 20 '10 at 7:14
  • 4
    $\begingroup$ Symbolically, differentiation is way easier than integration. Numerically, it's the other way round. $\endgroup$ – Christopher Creutzig Oct 20 '10 at 9:43
  • 2
    $\begingroup$ Christopher is correct. I note that one of the established routines for numerically finding Taylor coefficients essentially uses the trapezoidal rule on a transformed contour integral. On the other hand, automatic differentiation is considered a symbolic technique, since it starts by analyzing the routine corresponding to the function to be differentiated. $\endgroup$ – J. M. is a poor mathematician Oct 21 '10 at 0:29
  • $\begingroup$ Thanks for your enlightening arguments. I had originally ruled out many methods in my mind, because $n \approx \Theta(2^{q 2^p})$. I hope to be more open minded now, and I've realized there's alot more I can consider. $\endgroup$ – Matt Groff Oct 21 '10 at 2:30

If the coefficients are naturals, there is no problem with rounding. So just divide the polynomials and look at the middle term.

Rather equivalently, you can evaluate it at a number of points and do Lagrange interpolation.

  • $\begingroup$ Be aware, though, that things like the Runge phenomenon still rear their ugly heads even in exact arithmetic. Polynomial interpolation requires great care in use. $\endgroup$ – J. M. is a poor mathematician Oct 21 '10 at 0:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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