What is/are the lower bounds for finding a something akin to complex residue? Given a function $\sum_{i=-N}^N{c_i x^i}$:

$f(x) \equiv \sum_{i=-N}^N{c_i x^i}$ where $c_i$ is an integer; $0 \le c_i \le a$ for some $a$. 

The constant $c_0$ is desired, and we start with only $f(x)$ and $N$.  $N$ is $\Theta(2^{b})$ for some $b$.


  Can you clarify?


First, we start with a closed form of a function.  The function itself is similar to a generating function, so that the function description is usually more concise than a list of all of its coefficients, yet it describes all of the coefficients.  Some examples are

$\frac{1-x^{100}}{1-x} = 1 + x + x^2 + ... + x^{99}$

$\frac{ 1 - (n+1)x^n + nx^{n+1} }{ (x-1)^2 } = 1 + 2x + 3x^2 + ... + (n+1)x^n$

The problem seems to be that this coefficient is in the middle of a list of positive and negative coefficients.  In the two examples above, the coefficient c_0 can be easily extracted.  However, this is not so when there are negative coefficients.  For example, take the functions above and divide by x^m to get a function that contains some negative coefficients.


  What is known about the general form of $f(x)$?


The function $f(x)$ is a rational function:

$f(x) = P(x)/Q(x)$

where $P(x)$ and $Q(x)$ are polynomials.

Here's a little insight into how $f(x)$ is calculated.
I use a standard rational function:

$g(x) = (x^s(x^t-1)) / ((x-1)(x^u+1))$

I then multiply $g(x)$ by $g(y)$, and $g(y)$ is of the same form of $g(x)$, but in another variable.  I then possibly subtract this from a function of one coefficients:

$h(xy) = (1-(x y)^v) / (1-x y)$

I then use another variable function similar to $g(x)$, say $g(z)$, and multiply again.  Possibly subtract again.  Repeat this until the function I want is constructed.  Then reassign variables like so (to either positive or negative exponents):

$y \mapsto \displaystyle x^{\pm 2^N}$

$z \mapsto \displaystyle (x^{\pm 2^N})*(x^{\pm 2^N})$

and so on.  This is how the function is created, without going into detail.


  How fast can this computation be performed?


So far, I've seen that Bruno Salvy's webpage hosts a "gfun" package that solves this in O(N).

I'm attempting to write a more efficient algorithm than this, so I'm hoping that it's possible to do better.  I imagine that a bounds related to the length of the function description may be possible...
So far, I've seen that Bruno Salvy's webpage hosts a "gfun" package that solves this in O(N). I'm attempting to write a more efficient algorithm than this, so I'm hoping that it's possible to do better. I imagine that a bounds related to the length of the function description may be possible...


There are different measures of polynomial sparseness in the literature and you haven't been very clear on which one you might mean. However, your optimism is likely not well founded. 

Take (x-2) / x^32. It's almost maximally sparse by any reasonable measure, but the coefficients in its Laurent series grow exponentially fast. If multiplication is unit cost you can still use the binary exponentiation method to keep up with the exponential growth in sublinear time in the total degree of the series, but the example suggests that things aren't rosy. This is an area littered with hardness results for division and related problems, at least in realistic models of computation where multiplication isn't constant time.

Jacques Carette is an expert in this area, so let's hope he posts a definitive answer.