<blockquote>
  <p>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...</p>
</blockquote>

<p>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. </p>

<p>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.</p>

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

CC BY-SA 2.5
2010-09-29T03:02:37.080Z
I was lucky enough to have Jacques Carette personally email me and suggest reading up on Bruno Salvy and implement using "gfun". However, I forgot to ask him if the results were known to be optimal - but it sounds like I can safely assume that they are indeed optimal. Thanks so much for the mention!  As for the polynomial sparseness, I'll try to come up with a better description in the question.
Matt Groff
CC BY-SA 2.5
2010-09-29T03:15:54.103Z
@Matt: Regarding sparseness, one measure which is natural for computer science but perhaps less so for mathematics is "straight-line complexity", which is the size of a straight-line program to generate the polynomial in terms of the addition and multiplication by constants and indeterminates.
Per Vognsen
CC BY-SA 2.5
2010-09-29T01:49:20.030Z
2010-09-29T02:06:32.010Z
2010-09-29T02:06:32.010Z
Per Vognsen
<p>The extended comments after the question indicate that $f$ is a "black box", $N$ is known, and the coefficients $c_i$ are all integers.  If in addition we have a bound on the sizes of the coefficients, say $|c_i| \le q$ for all $i$, then all $2N+1$ coefficients can be read off the value of </p>

<p>$$(2q+1)^N f(2q+1) = c_{-N} + c_{1-N}(2q+1) + \cdots + c_0(2q+1)^N + \cdots + c_N(2q+1)^{2N}$$ </p>

<p>by looking at its base-$2q+1$ expansion.  The middle term, $c_0$, can then be computed in $O(1)$ time.  This old trick might be impracticable if $q$ or $N$ are at all sizable but perhaps it will inspire some practical $o(N)$ solutions.</p>

CC BY-SA 2.5
2010-09-30T17:04:50.683Z
We do have a bound on the coefficients.  N is known to be quite large, but there may be a workaround...  As for q, I believe it is much smaller.  I'm giving this more thought...
Matt Groff
CC BY-SA 2.5
2010-10-01T16:17:53.643Z
@Matt: Based on your updated description, why don't you compute $x^N f(x)$ in base $2q+1$ throughout?  You can even carry them out modulo $(2q+1)^{N+1}$.
whuber
CC BY-SA 2.5
2010-10-01T19:02:09.773Z
That sounds interesting...  I'm considering it.
Matt Groff
CC BY-SA 2.5
2010-09-30T14:38:17.743Z
2010-09-30T14:38:17.743Z
whuber
<p><em>Warning: I haven't used complex analysis much so this answer may be wrong.</em></p>

<p>Suppose you can write  $Q(x) = x^c \bar Q(x)$ where $\bar Q(x)$ is a polynomial that's non-zero at 0 and $c$ is a non-negative integer. It follows that the "residue" you're looking for is the $c^{th}$ term in the power series for $P(x)$ divided by $\bar Q(0)$. If $Q$ is written in a form that allows easy factorization (e.g. as a product of small polynomials) you can determine $c$ and $\bar Q(0)$ easily without expanding them. Computing the $c^{th}$ term in the power series of $P$ can be done relatively quickly if $c$ is small.</p>

<p>Another possibly helpful tool is that the $i^{th}$ derivative of a polynomial evaluated at zero is precisely the $i^{th}$ coefficient times $i!$. It may be that $P$ or $Q$ are easier to differentiate (symbolically) than expand.</p>

CC BY-SA 2.5
2010-09-30T17:09:51.610Z
I believe that we can easily obtain the factorization of $Q$, even though the polynomials will possibly be large.  Computing the power series $P$ may be worthwhile.  As for the derivative, I've found the function difficult to differentiate.
Matt Groff
CC BY-SA 2.5
2010-09-30T18:44:22.220Z
If you're going to be using residues, first you have to divide P(z)/Q(z) by z, because the residue is the coefficient of the -1 power.  Unless P is a multiple of z, you don't even have to consider it: the residue of P/(zQ) at zero equals P(0) times the residue of 1/(zQ).  After taking out any common power of z from P and Q, you may as well assume Q(z) = z^k(1 + q_1 z + ...).  Thus you're looking for the k-1st coefficient of the last term.  But note (once again) that P/Q *cannot* be expressed as a finite Laurent series (i.e., N is infinite).
whuber
CC BY-SA 2.5
2010-09-29T21:23:42.923Z
2010-09-29T21:23:42.923Z
Warren Schudy
<p>I'm providing a second answer because a later edit of the question has changed it considerably and this thought will not fit into the space of just one or two comments.</p>

<p>Because $g$ is described as a rational function, both $s$ and $u$ must be positive integers.  Notice that</p>

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

<p>$$= x^s \left(1 + x + \cdots + x^{t-1} \right) \left(1 - x^u + x^{2u} + \cdots + (-1)^j x^{j u} \cdots  \right).$$</p>

<p>(If I misinterpreted the definition of $g$, which was ambiguously parenthesized, the analysis only gets simpler because we multiply, rather than divide, by $1 + x^u$.)</p>

<p>When multiplied out, this becomes a Taylor series expanded around $x = 0$ with lowest term $x^s$.  Similarly,</p>

<p>$$h(xy) = (1-(x y)^v)/(1-x y) = 1 + x y + (x y)^2 + \cdots + (x y)^{v-1}$$</p>

<p>is a Taylor series (actually, a polynomial) with lowest term 1.  Therefore any series of multiplications, subtractions, and substitutions of positive powers of $x$ for $y$ will produce a Taylor series: <em>there will be no negative powers of $x$</em> in the result.</p>

<p>All you have to do, then, is track the constant term by performing all calculations modulo $x$ as you go.  Not only does this greatly simplify the computation of $f$, it gives you the constant term $c_0$ immediately.</p>

CC BY-SA 2.5
2010-09-30T21:38:15.767Z
Did you consider the subtraction and variable reassignment?  You're correct that the functions initially start with all positive coefficients, but then I reassign variables.  My description may contain an error, because the actual process is more complicated, but I end up with coefficients for both positive and negative powers, I can assure you.
Matt Groff
CC BY-SA 2.5
2010-09-30T22:10:16.817Z
@Matt: Yes.  The variable reassignments only increase the powers of x; the subtraction (like addition) cannot create new powers.  The sign of the *coefficients* is immaterial; what matters are the signs of the *exponents*.  As far as I can see, you have no negative exponents.  You must be doing something in addition to the operations you describe if you are winding up with negative exponents.  But how do you know that?
whuber
CC BY-SA 2.5
2010-09-30T22:17:41.670Z
I'm Very sorry.  I copied my variable reassignments incorrectly.  The variables are possibly reassigned to negative exponents.  The method I use requires them, and I don't know a workaround.
Matt Groff
CC BY-SA 2.5
2010-09-30T18:55:46.057Z
2010-09-30T19:00:58.867Z
2010-09-30T19:00:58.867Z
whuber
<p>I am not allowed to comment yet, so sorry for posting this in an answer. If someone can move it, please do so.</p>

<p>I have some questions:</p>

<p>1) What does gfun do for $N=\infty$? Do you want to find residues of functions like that?</p>

<p>2) Do you need a precise expression? There are approaches that give you reasonable asymptotics, for example Cauchy's integral formula together with the saddle-point method. I don't know how efficiently the involved integrals can be calculated, though.</p>

CC BY-SA 2.5
2010-09-28T22:14:19.413Z
I'm really concerned with finite functions.  I don't need a precise expression, I'm just interested in the possibility of something faster than O(n)
Matt Groff
CC BY-SA 2.5
2010-09-28T21:46:48.593Z
2010-09-28T21:46:48.593Z
Raphael
<p>Given a function $\sum_{i=-N}^N{c_i x^i}$:</p>

<p>$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$. </p>

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

<blockquote>
  <p>Can you clarify?</p>
</blockquote>

<p>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</p>

<p>$\frac{1-x^{100}}{1-x} = 1 + x + x^2 + ... + x^{99}$</p>

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

<p>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.</p>

<blockquote>
  <p>What is known about the general form of $f(x)$?</p>
</blockquote>

<p>The function $f(x)$ is a rational function:</p>

<p>$f(x) = P(x)/Q(x)$</p>

<p>where $P(x)$ and $Q(x)$ are polynomials.</p>

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

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

<p>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:</p>

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

<p>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):</p>

<p>$y \mapsto \displaystyle x^{\pm 2^N}$</p>

<p>$z \mapsto \displaystyle (x^{\pm 2^N})*(x^{\pm 2^N})$</p>

<p>and so on.  This is how the function is created, without going into detail.</p>

<blockquote>
  <p>How fast can this computation be performed?</p>
</blockquote>

<p>So far, I've seen that <a href="http://algo.inria.fr/salvy/" rel="nofollow">Bruno Salvy's webpage</a> hosts a "gfun" package that solves this in O(N).</p>

<p>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...</p>

CC BY-SA 2.5
2010-09-28T19:57:52.830Z
Are all $c_i$ apart from $c_0$ known? The question is unclear.
Dave Clarke
CC BY-SA 2.5
2010-09-28T20:08:20.367Z
they are unknown - we have only a function like \frac{1-x^{10}}{1-x} - in which case f(x) \equiv 1 + x + x^2 + ... x^9
Matt Groff
CC BY-SA 2.5
2010-09-28T20:12:40.540Z
How is the problem read in? Do you not need to read in c_1 ... c_n, which already takes linear time?
Lev Reyzin
CC BY-SA 2.5
2010-09-28T20:20:23.703Z
We read in the function. We DO NOT have the representation of c_{-N}...c_N. We have a function that is probably smaller in total size. Again, \frac{1-x^{M}}{1-x} is a function that gives a total of M c_i's that are all 1. However, it is possibly smaller than O(M).  The size of the function can be assumed to be O(l), where l represents the length of the function description, and usually l<N.
Matt Groff
CC BY-SA 2.5
2010-09-28T20:24:34.370Z
Matt, it's a good idea to improve your question to reflect these comments. Also, there's no need to write the function both in ASCII and in latex.
Dave Clarke
CC BY-SA 2.5
2010-09-28T20:29:57.790Z
I intended to, and forgot that I don't have an editor badge yet.  For clarity, remember Taylor series and Maclauren series.  This is similar, we have a very concise function like sin x, which has associated a host of coefficients.  We would simply like to find the coefficient c_0.
Matt Groff
CC BY-SA 2.5
2010-09-28T20:34:31.587Z
You can always edit your own questions.
Dave Clarke
CC BY-SA 2.5
2010-09-28T20:55:28.657Z
Please forgive my ignorance.  @supercooldave: thanks!
Matt Groff
CC BY-SA 2.5
2010-09-28T21:17:24.203Z
The question is still difficult to understand. The \frac chunks can be placed in math mode ($). Also it's probably worth reading the question from top to bottom to produce a coherent flow of thoughts.
Dave Clarke
CC BY-SA 2.5
2010-09-28T21:20:23.040Z
So it seems like f() is presented as a 'value oracle' ? i.e given x, you merely output f(x) ? also, if there is a linear time algorithm, what exactly do you not like about it ?
Suresh Venkat
CC BY-SA 2.5
2010-09-28T21:41:06.097Z
Or is it the case that $f$ is represented as a rational function $f(x) = P(x)/Q(x)$, and here $P$ and $Q$ can be sparse polynomials (few non-zero coefficients)?
Jukka Suomela
CC BY-SA 2.5
2010-09-28T22:22:22.053Z
@Suresh Venkat: The function f(x) above represents a set of coefficients, so I suppose a function g(x) would output a specific coefficient.  Is that what you're getting at?
Matt Groff
CC BY-SA 2.5
2010-09-28T22:36:38.610Z
@Jukka: I believe that for my particular case $f(x)$ is a rational function, and also that $P$ and $Q$ are sparse polynomials.  However, from my understanding, $P$ will be of essentially exponential size from my point of view - thusly, even though it's sparsely "populated" it will still be enormous.  $P$ is essentially a product of many bivariate or similarly sized polynomials.
Matt Groff
CC BY-SA 2.5
2010-09-28T22:42:57.537Z
it seems that N should be n right?
Marcos Villagra
CC BY-SA 2.5
2010-09-28T22:44:23.813Z
Basically.  I didn't mean to confuse.
Matt Groff
CC BY-SA 2.5
2010-09-29T14:58:49.113Z
This question is still problematic for a couple of reasons.  (1) The Laurent series for a non-trivial rational function will never be in the form given at the beginning of the question.  (2) The "residue" of any complex analytic function at a point z is the -1 coefficient (not the 0 coefficient) of its Laurent expansion around z.  (3) P/Q can have a nonzero residue (in the conventional sense) at z=0 if and only if q_0 = 0 and q_1 != 0, in which case the residue is obtained by evaluating xP(x)/Q(x) at x=0, giving p_0/q_1 (where P(x) = p_0 + p_1 x + ... etc.).
whuber
CC BY-SA 2.5
2010-09-29T16:36:43.573Z
Perhaps I should rephrase the initial question. I'm not looking for a complex residue exactly, but as you correctly pointed out, I'm looking for the 0 coefficient.  I wonder if the conditions you describe still hold for a SEQUENCE of terms from -N to N, as this is the exact form that I'm interested in.
Matt Groff
CC BY-SA 2.5
2010-09-29T19:18:07.860Z
@Matt: But then how is this function f(x) provided to you?  Obviously not as the sequence of terms itself and obviously not as a ratio of arbitrary polynomials, for otherwise the solution would be trivial (since Q(x) would have to be a constant multiple of x^N).
whuber
CC BY-SA 2.5
2010-09-29T19:59:56.350Z
@whuber:The sequence is provided through the completion of a set of calculations, which are hard to explain. (I wish I had a simpler explanation) If you want, you can email me at mgroff100@yahoo.com and I'll provide a lengthier description...  I'll try to come up with a better description of f(x), but it's proving hard to do without getting complicated
Matt Groff
CC BY-SA 2.5
2010-09-29T21:29:16.047Z
@Matt: But despite the complications of the calculations, their output must be represented with some kind of data structure.  Clearly it's not the sequence $(c_{-N}, c_{-N+1}, \ldots, c_N)$, for otherwise you would just consult $c_0$ in $O(1)$ time!  So maybe the calculations don't require an explanation, but this data structure does.  Or are you saying we should treat $f$ as a "black box" and you would like to find (or at least estimate) $c_0$ with $o(N)$ evaluations of $f$?  If this is the case, do you know $N$ *a priori*?
whuber
CC BY-SA 2.5
2010-09-29T23:48:02.290Z
@whuber: $N$ is known - I'm sorry I forgot to mention this.  The overall function that represents the coefficients is known, but the coefficients themselves are not known.  I'd like to treat this as a black box, but certainly use any information that is known or can be determined easily.
Matt Groff
CC BY-SA 2.5
2010-09-30T01:01:59.387Z
@Matt: Do you know anything about the coefficients?  Bounds on their absolute values might accomplish a lot.  For example, if they are bounded integers, there is a way to find them in a single evaluation of $f$.
whuber
CC BY-SA 2.5
2010-09-30T01:35:29.673Z
The coefficients are integers.
Matt Groff
<lower-bounds><algebra>
What is/are the lower bounds for finding a something akin to complex residue?
Matt Groff
# What is/are the lower bounds for finding a something akin to complex residue?

(Asked by: username_0 on 2010-09-28)

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](http://algo.inria.fr/salvy/) 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...

**Tags:** lower-bounds, algebra

> **Comments:**
> **username_1**: Are all $c_i$ apart from $c_0$ known? The question is unclear.  
> **username_0**: they are unknown - we have only a function like \frac{1-x^{10}}{1-x} - in which case f(x) \equiv 1 + x + x^2 + ... x^9  
> **username_2**: How is the problem read in? Do you not need to read in c_1 ... c_n, which already takes linear time?  
> **username_0**: We read in the function. We DO NOT have the representation of c_{-N}...c_N. We have a function that is probably smaller in total size. Again, \frac{1-x^{M}}{1-x} is a function that gives a total of M c_i's that are all 1. However, it is possibly smaller than O(M).  The size of the function can be assumed to be O(l), where l represents the length of the function description, and usually l<N.  
> **username_1**: Matt, it's a good idea to improve your question to reflect these comments. Also, there's no need to write the function both in ASCII and in latex.  
> **username_0**: I intended to, and forgot that I don't have an editor badge yet.  For clarity, remember Taylor series and Maclauren series.  This is similar, we have a very concise function like sin x, which has associated a host of coefficients.  We would simply like to find the coefficient c_0.  
> **username_1**: You can always edit your own questions.  
> **username_0**: Please forgive my ignorance.  @supercooldave: thanks!  
> **username_1**: The question is still difficult to understand. The \frac chunks can be placed in math mode ($). Also it's probably worth reading the question from top to bottom to produce a coherent flow of thoughts.  
> **username_3**: So it seems like f() is presented as a 'value oracle' ? i.e given x, you merely output f(x) ? also, if there is a linear time algorithm, what exactly do you not like about it ?  
> **username_4**: Or is it the case that $f$ is represented as a rational function $f(x) = P(x)/Q(x)$, and here $P$ and $Q$ can be sparse polynomials (few non-zero coefficients)?  
> **username_0**: @username_3: The function f(x) above represents a set of coefficients, so I suppose a function g(x) would output a specific coefficient.  Is that what you're getting at?  
> **username_0**: @Jukka: I believe that for my particular case $f(x)$ is a rational function, and also that $P$ and $Q$ are sparse polynomials.  However, from my understanding, $P$ will be of essentially exponential size from my point of view - thusly, even though it's sparsely "populated" it will still be enormous.  $P$ is essentially a product of many bivariate or similarly sized polynomials.  
> **username_5**: it seems that N should be n right?  
> **username_0**: Basically.  I didn't mean to confuse.  
> **username_6**: This question is still problematic for a couple of reasons.  (1) The Laurent series for a non-trivial rational function will never be in the form given at the beginning of the question.  (2) The "residue" of any complex analytic function at a point z is the -1 coefficient (not the 0 coefficient) of its Laurent expansion around z.  (3) P/Q can have a nonzero residue (in the conventional sense) at z=0 if and only if q_0 = 0 and q_1 != 0, in which case the residue is obtained by evaluating xP(x)/Q(x) at x=0, giving p_0/q_1 (where P(x) = p_0 + p_1 x + ... etc.).  
> **username_0**: Perhaps I should rephrase the initial question. I'm not looking for a complex residue exactly, but as you correctly pointed out, I'm looking for the 0 coefficient.  I wonder if the conditions you describe still hold for a SEQUENCE of terms from -N to N, as this is the exact form that I'm interested in.  
> **username_6**: @Matt: But then how is this function f(x) provided to you?  Obviously not as the sequence of terms itself and obviously not as a ratio of arbitrary polynomials, for otherwise the solution would be trivial (since Q(x) would have to be a constant multiple of x^N).  
> **username_0**: @username_6:The sequence is provided through the completion of a set of calculations, which are hard to explain. (I wish I had a simpler explanation) If you want, you can email me at mgroff100@yahoo.com and I'll provide a lengthier description...  I'll try to come up with a better description of f(x), but it's proving hard to do without getting complicated  
> **username_6**: @Matt: But despite the complications of the calculations, their output must be represented with some kind of data structure.  Clearly it's not the sequence $(c_{-N}, c_{-N+1}, \ldots, c_N)$, for otherwise you would just consult $c_0$ in $O(1)$ time!  So maybe the calculations don't require an explanation, but this data structure does.  Or are you saying we should treat $f$ as a "black box" and you would like to find (or at least estimate) $c_0$ with $o(N)$ evaluations of $f$?  If this is the case, do you know $N$ *a priori*?  
> **username_0**: @username_6: $N$ is known - I'm sorry I forgot to mention this.  The overall function that represents the coefficients is known, but the coefficients themselves are not known.  I'd like to treat this as a black box, but certainly use any information that is known or can be determined easily.  
> **username_6**: @Matt: Do you know anything about the coefficients?  Bounds on their absolute values might accomplish a lot.  For example, if they are bounded integers, there is a way to find them in a single evaluation of $f$.  
> **username_0**: The coefficients are integers.  

---

## 5 answers

### Answer by username_7 on 2010-09-29. Score: 4

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

> **Comments:**
> **username_0**: I was lucky enough to have Jacques Carette personally email me and suggest reading up on Bruno Salvy and implement using "gfun". However, I forgot to ask him if the results were known to be optimal - but it sounds like I can safely assume that they are indeed optimal. Thanks so much for the mention!  As for the polynomial sparseness, I'll try to come up with a better description in the question.  
> **username_7**: @Matt: Regarding sparseness, one measure which is natural for computer science but perhaps less so for mathematics is "straight-line complexity", which is the size of a straight-line program to generate the polynomial in terms of the addition and multiplication by constants and indeterminates.  

---

### Answer by username_6 on 2010-09-30. Score: 2

The extended comments after the question indicate that $f$ is a "black box", $N$ is known, and the coefficients $c\_i$ are all integers. If in addition we have a bound on the sizes of the coefficients, say $|c\_i| \le q$ for all $i$, then all $2N+1$ coefficients can be read off the value of

$$(2q+1)^N f(2q+1) = c\_{-N} + c\_{1-N}(2q+1) + \cdots + c\_0(2q+1)^N + \cdots + c\_N(2q+1)^{2N}$$

by looking at its base-$2q+1$ expansion. The middle term, $c\_0$, can then be computed in $O(1)$ time. This old trick might be impracticable if $q$ or $N$ are at all sizable but perhaps it will inspire some practical $o(N)$ solutions.

> **Comments:**
> **username_0**: We do have a bound on the coefficients.  N is known to be quite large, but there may be a workaround...  As for q, I believe it is much smaller.  I'm giving this more thought...  
> **username_6**: @Matt: Based on your updated description, why don't you compute $x^N f(x)$ in base $2q+1$ throughout?  You can even carry them out modulo $(2q+1)^{N+1}$.  
> **username_0**: That sounds interesting...  I'm considering it.  

---

### Answer by username_8 on 2010-09-29. Score: 1

*Warning: I haven't used complex analysis much so this answer may be wrong.*

Suppose you can write $Q(x) = x^c \bar Q(x)$ where $\bar Q(x)$ is a polynomial that's non-zero at 0 and $c$ is a non-negative integer. It follows that the "residue" you're looking for is the $c^{th}$ term in the power series for $P(x)$ divided by $\bar Q(0)$. If $Q$ is written in a form that allows easy factorization (e.g. as a product of small polynomials) you can determine $c$ and $\bar Q(0)$ easily without expanding them. Computing the $c^{th}$ term in the power series of $P$ can be done relatively quickly if $c$ is small.

Another possibly helpful tool is that the $i^{th}$ derivative of a polynomial evaluated at zero is precisely the $i^{th}$ coefficient times $i!$. It may be that $P$ or $Q$ are easier to differentiate (symbolically) than expand.

> **Comments:**
> **username_0**: I believe that we can easily obtain the factorization of $Q$, even though the polynomials will possibly be large.  Computing the power series $P$ may be worthwhile.  As for the derivative, I've found the function difficult to differentiate.  
> **username_6**: If you're going to be using residues, first you have to divide P(z)/Q(z) by z, because the residue is the coefficient of the -1 power.  Unless P is a multiple of z, you don't even have to consider it: the residue of P/(zQ) at zero equals P(0) times the residue of 1/(zQ).  After taking out any common power of z from P and Q, you may as well assume Q(z) = z^k(1 + q_1 z + ...).  Thus you're looking for the k-1st coefficient of the last term.  But note (once again) that P/Q *cannot* be expressed as a finite Laurent series (i.e., N is infinite).  

---

### Answer by username_6 on 2010-09-30. Score: 0

I'm providing a second answer because a later edit of the question has changed it considerably and this thought will not fit into the space of just one or two comments.

Because $g$ is described as a rational function, both $s$ and $u$ must be positive integers. Notice that

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

$$= x^s \left(1 + x + \cdots + x^{t-1} \right) \left(1 - x^u + x^{2u} + \cdots + (-1)^j x^{j u} \cdots \right).$$

(If I misinterpreted the definition of $g$, which was ambiguously parenthesized, the analysis only gets simpler because we multiply, rather than divide, by $1 + x^u$.)

When multiplied out, this becomes a Taylor series expanded around $x = 0$ with lowest term $x^s$. Similarly,

$$h(xy) = (1-(x y)^v)/(1-x y) = 1 + x y + (x y)^2 + \cdots + (x y)^{v-1}$$

is a Taylor series (actually, a polynomial) with lowest term 1. Therefore any series of multiplications, subtractions, and substitutions of positive powers of $x$ for $y$ will produce a Taylor series: *there will be no negative powers of $x$* in the result.

All you have to do, then, is track the constant term by performing all calculations modulo $x$ as you go. Not only does this greatly simplify the computation of $f$, it gives you the constant term $c\_0$ immediately.

> **Comments:**
> **username_0**: Did you consider the subtraction and variable reassignment?  You're correct that the functions initially start with all positive coefficients, but then I reassign variables.  My description may contain an error, because the actual process is more complicated, but I end up with coefficients for both positive and negative powers, I can assure you.  
> **username_6**: @Matt: Yes.  The variable reassignments only increase the powers of x; the subtraction (like addition) cannot create new powers.  The sign of the *coefficients* is immaterial; what matters are the signs of the *exponents*.  As far as I can see, you have no negative exponents.  You must be doing something in addition to the operations you describe if you are winding up with negative exponents.  But how do you know that?  
> **username_0**: I'm Very sorry.  I copied my variable reassignments incorrectly.  The variables are possibly reassigned to negative exponents.  The method I use requires them, and I don't know a workaround.  

---

### Answer by username_9 on 2010-09-28. Score: 0

I am not allowed to comment yet, so sorry for posting this in an answer. If someone can move it, please do so.

I have some questions:

1) What does gfun do for $N=\infty$? Do you want to find residues of functions like that?

2) Do you need a precise expression? There are approaches that give you reasonable asymptotics, for example Cauchy's integral formula together with the saddle-point method. I don't know how efficiently the involved integrals can be calculated, though.

> **Comments:**
> **username_0**: I'm really concerned with finite functions.  I don't need a precise expression, I'm just interested in the possibility of something faster than O(n)  

---

