1
$\begingroup$

I need to compute the product of two polynomials $f(X)$ and $g(X)$ over a finite field. The degrees of these polynomials are $n^2$ for some integer $n$. However, we also know that the polynomials are sparse in the sense that most coefficients are zero and furthermore, only $O(n)$ of the coefficients are non-zero.

Can we compute the product $f(X)\cdot g(X)$ in runtime $O(n\cdot \log^2(n))$ via FFT? If not, could we at least do it in subquadratic runtime?

$\endgroup$

1 Answer 1

2
$\begingroup$

Let $n>0$.
Let $f(X)=X^{n^2} + X^{n(n-1)} + X^{n(n-2)}+\cdots + X^n + 1$.
Let $g(X) =X^{n^2} + X^{n-1} + X^{n-2} + \cdots + 1$.

$$\begin{aligned} f(X)g(X)&=f(X)X^{n^2} + f(X)(X^{n-1} + X^{n-2} + \cdots + 1)\\ &=X^{2n^2}+X^{2n^2-n} + \cdots + X^{n^2+n} + X^{n^2} + {}\\ &\quad\quad X^{n^2+n-1}+X^{n^2+n-2} +\cdots+ X^2 + X + 1\\ &=\sum_{2n\ge i\ge n+1}X^{ni} + \sum_{n^2+n-1\ge i\ge n^2+1}X^i \ \ + 2X^{n^2} + \sum_{n^2-1\ge i\ge0}X^i \end{aligned}$$

The number of non-zero coefficients of $f(X)$ is $n+1$.
The number of non-zero coefficients of $g(X)$ is $n+1$.
The number of non-zero coefficients of $f(X)g(X)$ is $(n+1)^2-1=n^2+2n$.

It is impossible to list all nonzero coefficients of $f(X)g(X)$ in subquadratic runtime of $n$ in the worst time. So, it is impossible to compute all nonzero coefficients of $f(X)g(X)$ in subquadratic runtime of $n$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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