Interpolating for particular coefficients

Question

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?

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

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

Answer 5

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.