# Product of sparse polynomials with FFT

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?

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