I have managed to implement and understand most of the Fast Fourier Transformation. However, I have one last question.
If one has two polynomials, say $A(x)$ and $B(x)$, and one computes DFT of $A$ and $B$ [discrete fourier trasformation], then why can one just multiply corresponding elements and then take the inverse DFT? Why does one not have to multiply all pairs of elements together?
For example, if $DFT(A)=\{0,0,1\}$ and $DFT(B)=\{1,0,0\}$, it is true that one can just do INVERSE({0,0,0}), multiplying corresponding elements, instead of doing inverse of $\{0,0,1\}$, or multiplying elements in pairs. Why is this so?
(For context: the question is based on this article).
This is an illustration of using DFT to find the product of two polynomials. It is based on the fact that Fourier transform (discrete or continuous) converts convolution into multiplication.
The product of two polynomials amounts to convolution of their coefficients: $$ \left(\sum_{j=0}^n a_j x^j\right)\left(\sum_{k=0}^n b_k x^k\right) = \sum_{m=0}^{2n} c_m x^m $$ where $c_m = \sum_{j+k=m}a_jb_k$.
The DFT of the vector $(c_m)$ is the product of the DFTs of $(a_j)$ and $(b_k)$ (up to some normalization constants). Note that we need the vectors to be of the same length for this to work; thus, the vectors $a,b$ need to be padded by adding zero coefficients in front of polynomials.
How convolution becomes multiplication: for every $s$ (frequency index) we have $$ \hat c(s) = \sum_r c_r e^{2\pi i rs/(2n+1)} = \sum_{j,k} a_j b_k e^{2\pi i (j+k)s/(2n+1)} = \left(\sum_j a_j e^{2\pi i js/(2n+1)}\right)\left(\sum_k b_k e^{2\pi i ks/(2n+1)}\right) $$ The factors on the right are simply $\hat a(s)$ and $\hat b(s)$.
Yes, you would multiply coordinatewise and get zero. However, the DFT will not be like this. Since the product of two nonzero polynomials is nonzero, their DFTs will not have disjoint supports; otherwise we'd have a contradiction to the above. The aforementioned padding places some restrictions on what the DFT of polynomial coefficients will be.