Interpolating for particular coefficients

Say $F(X) \in \mathbb{Z}[X]$ is an even degree polynomial of degree $2n$.

One needs to evaluate $F(X)$ at $O(n)$ points to interpolate and get all the coefficients of $F(X)$.

However say I need only the coefficient of $X^{n}$ or $X^{2n}$ (the mid coefficient or the largest), do I still have to evaluate at $O(n)$ points?

Will having coefficient of $X^{t}$ same as coefficient of $X^{2n-t}$ help in reducing the number of points from $O(n)$ to detect $X^{n}$ coefficient (mid-coefficient in the symmetric case)?

Is this a well studied problem that has some good references - that is interpolating for only one or few coefficients?

There is one way to do this - evaluating at one large prime and reduction via modulo operations. However, this gives way too much information(that is I can get all the coefficients) and when I evaluate at a large prime, the word size become the order of $O(n\log(nM))$ where M is the largest coefficient size. So in a way we are still using $O(n^{1+\epsilon})$ operations.

I am guessing there should be a way to get only information about the single coefficient I am interested in while getting the operations down to $O(n^{1-\epsilon})$ at the 'cost of not-getting' information about other coefficients.

Say you have a polynomial of odd degree (even coeffcients). Evaluating at $1$ and $-1$ and adding the results or subtracting the results, localizes the information into groups of two coefficients. My question could be can we localize further? Supposing in addition I have $F(x) = A(x)B(x)$ where I know $A(x)$ and $B(x)$, is it possible to represent $A(x)$ and $B(x)$ in a different way so that I can somehow target the mid coefficient of $F(x)$ without getting other coefficients?

-
If you evaluate $F$ at $\pi$ then you can figure out all of its coefficients from the answer! – Kevin Buzzard May 23 '11 at 16:15
If you could get the top coefficient from evaluation at 2n - 1 points, you could actually then get all of them. So that can't work in general. On the other hand the symmetry of the coefficients is going to reduce the number of unknowns. – Charles Matthews May 23 '11 at 16:22
Drat, 2n + 1 coefficients so I meant 2n. Why the O-notation? You might hope to get down to n + 1, which is what general position could give you. – Charles Matthews May 23 '11 at 16:26
@Kevin: $F(\pi)$ determines $F$ uniquely, and since its degree is known, I guess that an approximation with bounded precision is enough. But is there an efficient (i.e., faster than interpolating $2n$ values at integer points) algorithm to actually extract the coefficients from $F(\pi)$? – Emil Jeřábek May 23 '11 at 16:34
I have two polynomials of degree $n-1$. I am interested in taking their product but discarding all but the mid coefficient. – Turbo May 23 '11 at 17:41

Barring tricks such as evaluating to a large/irrational number with large precision, I doubt you can do anything. Let's say you evaluate at $2n$ points only, $x_1,\dots,x_{2n}$ (which is one less than you'd need to know everything about the polynomial). Then you'll never know if you were working with the polynomial $p(x)$ or with $p(x)+K(x-x_1)(x-x_2)\cdots(x-x_{2n})$, for some $K$. And the leading coefficient of the latter depends on $K$.

(though not necessarily the central coefficient, if you chose the $x_i$ appropriately. Hmmm, maybe we need a more complicated argument for the central coefficient. But this argument definitely works for the leading term.)

-

I’ll turn my comment above into an answer, maybe it will make things more clear for the OP.

Theorem: Let $1\le m\le n$, $m\le k\le2n$, $a_1,\dots,a_k\in\mathbb Q$. Then there exist polynomials $A,B,\tilde A\in\mathbb Z[x]$ of degree $n$ such that $AB$ and $\tilde AB$ have distinct $k$th coefficient, but $A(a_i)B(a_i)=\tilde A(a_i)B(b_i)$ for every $i=1,\dots,m$.

Proof: Put $A=0$, $A'=cx^r\prod_{i=1}^m(x-a_i)$, $B=x^s$, where $k=m+r+s$, $r+m,s\le n$, and $c$ is chosen so that $A'$ has integer coefficients (i.e., $c$ is a multiple of the product of the denominators of the $a_i$s).

Thus, if you want to extract the $k$th coefficient by evaluation at rational points, you absolutely need at least $k+1$ points, and therefore time $\Omega(k)$.

In fact, any algorithm for extraction of the $k$th coefficient of $AB$ needs time $\Omega(k)$. The reason is that the coefficient equals $\sum_{i\le k}A_iB_{k-i}$, and therefore it depends on $2k+2$ of the input numbers in the sense that changing any of them can change the result. In fact, it will always change the result unless the matching coefficient in the product is $0$, thus even in the best possible case, we need to read at least one of $A_i$ or $B_{k-i}$ for every $i$ to fix the result, i.e., we need to use at least $k+1$ of the input numbers, and therefore we need time at least $k+1$. There is no way around it.

In view of this fact, it’s probably best to stick to direct evaluation of the formula $\sum_{i=0}^kA_iB_{k-i}$, which computes the result using $k+1$ multiplications and $k$ additions. Since you need at least $k$ or so operations using any other method, this is pretty much optimal, and as an additional bonus it is simple and easy to implement.

More sofisticated methods (like evaluation and interpolation) are only useful if you need to extract many coefficients of the polynomial, because they save some repeated computations. They are not going to help you if you need just one coefficient.

-
What you are saying is true if $A$ and $B$ remains represented as a degree-$n$ polynomial. What if there is another clever representation of the coefficients of of $A$ and $B$ that gives a faster approach to getting $AB$'s mid coefficient? – Turbo May 24 '11 at 19:31
I like your answer...... but do you think there could be no other clever representations of $A$ and $B$? – Turbo May 24 '11 at 19:43

Do you have an estimate on the size of the largest coefficient? For a few moderately-sized primes $p$, calculate $(p^{2n} F(1/p))\ {\rm mod}\ p$ which gives you the coefficient of $X^{2n}$ mod $p$, then use Chinese Remainder.

-
Hi: How many would you need? Say the coefficients are bounded by $2^{O(log_{2}({nM}))}$ where $n$ is as before and $M$ is some constant integer. – Turbo May 23 '11 at 18:46
But wouldn't that still have the same problem of enlarging the word sizes even if one uses reducing modulo $p$, that is modulo $p$ in the worst case might have $O(n^{1+\epsilon})$ atomic operations (atomic in the sense - of atmoic integer multiplication, division, add or subtract operations). – Turbo May 23 '11 at 18:49

If you have a bound on the coefficients, then you can certainly get the highest degree coefficient by evaluating at one (count'em) point, since you are just trying to evaluate the limit of $P(X)/X^N,$ where $N$ is the degree, and you know that the answer is an integer. If you don't have such a bound, I doubt you can do better than the obvious (where "the obvious" might be "evaluate the polynomial at the roots of unity and do the inverse Fourier transform", or "evaluate it at small integers and do Lagrange interpolation").

-
I think you may be right. But is there some kind of proof that shows one canot do better than $O(n)$. – Turbo May 23 '11 at 19:40
Precisely: if we know that $|a_k|\leq m$ for $0\leq k < N$, then $| a_N - F(X)X ^ {-N} | < 1/2$ for $X=2m+1$ so $a_N$ is the closest integer to $F(X)X ^ {-N}$. – Pietro Majer May 23 '11 at 20:28
But still $F(X)X^{−N}$ is $O(n^{1+\epsilon})$ bits isn't it? – Turbo May 23 '11 at 22:31
No, the number of bits depends on $m$ (in @Pietro's notation), not on $N.$ – Igor Rivin May 23 '11 at 23:40
When you calculate $F(X)$ you will have to raise $X$ to power $N$ at some point which will make the words $O(N)$ size. (size is number of bits) – Turbo May 24 '11 at 1:24

If there are equal coefficients for $x^{2n-t}$ and $x^t$ for all $0 \le t \lt n$ then we have $n+1$ unknown coefficients so $n+1$ points suffice. Of course that is still $O(n).$ Then the top c oeffcient is $y(0)$ but that is no fun. I'll focus on the middle coefficient.

• For the quadratic case $y=ax^2+bx+a$ we have $y(i)=bi.$

• For $y=ax^4+bx^3+cx^2+bx+a$ we have $y(I)=2a+c$ and $y(0)=a.$

• for $y=ax^6+bx^5+cx^4+dx^3+cx^2+bx+a$ it is enough to have $y$ at $i$ and at $\frac{\pm1+\sqrt{3}i}{2}$

This suggests a reduction from $n+1$ to $n$ points. This is not using the fact that the coefficients are integers.

For the case $2n=4$ there the values $u=\sqrt{-2+\sqrt{-5}},v=-\sqrt{-2-\sqrt{-5}}$ make $v^4+1=-(u^4+1)$, $v^3+v=-(u^3+u)$ but $v^2 \ne -u^2$ thus one can find $c$ along with a certain linear combination of $a,b$ but not $a$ or $b.$

A useful question might be "we have a polynomial of degree $2n$ with (symmetric) integer coefficients. How many function evaluations are needed to decide if the middle coefficient is $0$ or not?"

I don't know if you consider complex inputs reasonable. I imagine one might be able to use an appropriate finite field instead.

It sounds as if another question is something like: " Suppose that $a_1,a_2,\cdots,a_k$ are values such that $f(a_i)=0$ where $f$ has degree $2n$. What conditions on $n,k$ the coefficients and the $a_i$ are such that $f$ is forced to be the zero polynomial (or to have degree a certain coefficient be zero)" The conditions might be bounds on the size. This is related to the question of how few evaluations determine the coefficient(s) without regard to how much work it is to extract them.

-
For $2n=4$, from your technique, I am getting more than I want. That is I am getting coefficient $a$ in addition to $c$. The question is whether one can get information about $c$ at the cost of all other coefficients. May be there is a way to get $c$ without knowing $a$. In that case, may be lesser computations suffice. For$2n=4$, I dont think less than $2$ evaluations suffice but there could be another way that generalizes to general $n$ so that when that technique is applied to $2n=4$ case, it may not give anything about $a$ while giving information about $c$. – Turbo May 23 '11 at 18:37
OK, I expanded the answer a bit. – Aaron Meyerowitz May 23 '11 at 23:14
Complex inputs is fine. – Turbo May 24 '11 at 1:24