Is it known that if polynomial multiplication of degree $n$ polynomials and coefficient size bounded by $M$ can be done in $O(n)$ arithmetic operations on $O(\log n+\log M)$ bit sized words then $FFT$ of length $n$ vectors with entries bound by $M$ can also be done in $O(n)$ arithmetic operations on $O(\log n+\log M)$ bit sized words?
Note that the converse is trivial since polynomial multiplication reduces to $FFT$.
Suppose you have vectors $u$ and $v$. Imagine a table $M$ of the products of each of their entries.
$$M = |u\rangle\langle v| = \begin{bmatrix} u_0 v_0 & u_1 v_0 & u_2 v_0 & \dots & u_{n-1} v_0 \\ u_0 v_1 & u_1 v_1 & u_2 v_1 & \dots & u_{n-1} v_1 \\ u_0 v_2 & u_1 v_2 & u_2 v_2 & \dots & u_{n-1} v_2 \\ \vdots &\vdots &\vdots & \ddots & \vdots \\ u_0 v_{n-1} & u_1 v_{n-1} & u_2 v_{n-1} & \dots & u_{n-1} v_{n-1} \\ \end{bmatrix}$$
The convolution $u \ast v$ of the two vectors is a vector of the values you get when summing along each anti-diagonal of this grid. For example:
$$(u \ast v)_2 = \sum \begin{bmatrix} & & & & & & u_{n-3} v_0 & 0 & 0\\ & & & & & u_{n-4} v_1 \\ & & & & \ddots \\ & & & u_2 v_{n-5} & \\ & & u_1 v_{n-4} & & \\ u_0 v_{n-3} & & & & \\ 0 &\\ 0& \text{ } \end{bmatrix}$$
We can also think of the FFT of a vector as summing entries in a grid defined by multiplying two vectors' entries. The second vector is the sequence of roots of unity.
$$M = | u \rangle \langle e^{\tau i k/n} |\begin{bmatrix} u_0 & u_1 & u_2 & \dots & u_{n-1} \\ u_0 e^{\tau/n} & u_1 e^{\tau/n} & u_2 e^{\tau/n} & \dots & u_{n-1} e^{\tau/n} \\ u_0 e^{2\tau/n} & u_1 e^{2\tau/n} & u_2 e^{2\tau/n} & \dots & u_{n-1} e^{2\tau/n} \\ \vdots &\vdots &\vdots & \ddots & \vdots \\ u_0 e^{-\tau/n} & u_1 e^{-\tau/n} & u_2 e^{-\tau/n} & \dots & u_{n-1} e^{-\tau/n} \end{bmatrix}$$
The Fourier transform doesn't track along the diagonals, though. Its row-hop is different from its column-hop. For the $k$'th entry of the output we go through each column $c$ and sum up the cell from that column and the $k \cdot c$'th row (wrapping around).
$$FFT(v)_2 = \sum \begin{bmatrix} u_0 \\ &&&&u_4e^{\tau/7} \\ & u_1 e^{2\tau/7} \\ &&&&&u_5e^{3\tau/7} \\ & & u_2 e^{4\tau/7} \\ &&&&&&u_6e^{5\tau/7} \\ &&& u_3 e^{6\tau/7} \\ \end{bmatrix}$$
So our question becomes: can we somehow re-arrange our vectors so that the each-stride sums $\sum u_i v_{k \cdot i}$ correspond to the each-diagonal sums $\sum u_i v_{k-i}$? Can we turn index-multiplication into index-adding?
We can, as long as we're operating in a context that allows for a logarithm. Suppose our vector size is $n$ and $g$ is a multiplicative generator for the integers modulo $n$. Then we can use the powers of $g$, i.e. the base-$g$ discrete logarithm, to define a permutation of the non-zero elements that does most of what we need. Our transformation goes roughly as follows:
In other words: define a permutation $P$ based on when indices are reached when iteratively multiplying by $g$. Permute the input vector and the vector of $e^{\tau k /n}$ powers by $P$. Convolve. Unpermute by $P$. The result is the Fourier transform.
... Except that I've ignored one important issue. Our permutation doesn't work for $k=0$, because $g^k \mod n$ is never 0. Also, $g^0 = g^{n-1} = 1$. Fixing this hole requires special-casing the edges of the grid. But hopefully I've communicated the core idea of performing an FFT by delegating the heavy-lifting to a convolution and a permutation.
Note that, if you care about bit complexity instead of the number of arithmetic operations, computing the permutation may also be an obstacle. If multiplying by $g \pmod{n}$ costs $\log n$ time, and you don't have the permutation ahead of time, then overall the algorithm will still cost $O(n \log n)$.
