Discrete Fourier transform (general)

Let ${\displaystyle R}$ be any ring, let ${\displaystyle n\geq 1}$ be an integer, and let ${\displaystyle \alpha \in R}$ be a principal nth root of unity, defined by:[1]

${\displaystyle {\begin{aligned}&\alpha ^{n}=1\\&\sum _{j=0}^{n-1}\alpha ^{jk}=0{\text{ for }}1\leq k<n\qquad (1)\end{aligned}}}$

The discrete Fourier transform maps an n-tuple ${\displaystyle (v_{0},\ldots ,v_{n-1})}$ of elements of ${\displaystyle R}$ to another n-tuple ${\displaystyle (f_{0},\ldots ,f_{n-1})}$ of elements of ${\displaystyle R}$ according to the following formula:

${\displaystyle f_{k}=\sum _{j=0}^{n-1}v_{j}\alpha ^{jk}.\qquad (2)}$

By convention, the tuple ${\displaystyle (v_{0},\ldots ,v_{n-1})}$ is said to be in the time domain and the index ${\displaystyle j}$ is called time. The tuple ${\displaystyle (f_{0},\ldots ,f_{n-1})}$ is said to be in the frequency domain and the index ${\displaystyle k}$ is called frequency. The tuple ${\displaystyle (f_{0},\ldots ,f_{n-1})}$ is also called the spectrum of ${\displaystyle (v_{0},\ldots ,v_{n-1})}$. This terminology derives from the applications of Fourier transforms in signal processing.

If ${\displaystyle R}$ is an integral domain (which includes fields), it is sufficient to choose ${\displaystyle \alpha }$ as a primitive nth root of unity, which replaces the condition (1) by:[1]

${\displaystyle \alpha ^{k}\neq 1}$ for ${\displaystyle 1\leq k<n}$

Proof: take ${\displaystyle \beta =\alpha ^{k}}$ with ${\displaystyle 1\leq k<n}$. Since ${\displaystyle \alpha ^{n}=1}$, ${\displaystyle \beta ^{n}=(\alpha ^{n})^{k}=1}$, giving:

${\displaystyle \beta ^{n}-1=(\beta -1)\left(\sum _{j=0}^{n-1}\beta ^{j}\right)=0}$

where the sum matches (1). Since ${\displaystyle \alpha }$ is a primitive root of unity, ${\displaystyle \beta -1\neq 0}$. Since ${\displaystyle R}$ is an integral domain, the sum must be zero. ∎

Another simple condition applies in the case where n is a power of two: (1) may be replaced by ${\displaystyle \alpha ^{n/2}=-1}$.[1]

The inverse of the discrete Fourier transform is given as:

${\displaystyle v_{j}={\frac {1}{n}}\sum _{k=0}^{n-1}f_{k}\alpha ^{-jk}.\qquad (3)}$

where ${\displaystyle 1/n}$ is the multiplicative inverse of ${\displaystyle n}$ in ${\displaystyle R}$ (if this inverse does not exist, the DFT cannot be inverted).

Proof: Substituting (2) into the right-hand-side of (3), we get

${\displaystyle {\begin{aligned}&{\frac {1}{n}}\sum _{k=0}^{n-1}f_{k}\alpha ^{-jk}\\={}&{\frac {1}{n}}\sum _{k=0}^{n-1}\sum _{j'=0}^{n-1}v_{j'}\alpha ^{j'k}\alpha ^{-jk}\\={}&{\frac {1}{n}}\sum _{j'=0}^{n-1}v_{j'}\sum _{k=0}^{n-1}\alpha ^{(j'-j)k}.\end{aligned}}}$

This is exactly equal to ${\displaystyle v_{j}}$, because ${\displaystyle \sum _{k=0}^{n-1}\alpha ^{(j'-j)k}=0}$ when ${\displaystyle j'\neq j}$ (by (1) with ${\displaystyle k=j'-j}$), and ${\displaystyle \sum _{k=0}^{n-1}\alpha ^{(j'-j)k}=n}$ when ${\displaystyle j'=j}$. ∎

Since the discrete Fourier transform is a linear operator, it can be described by matrix multiplication. In matrix notation, the discrete Fourier transform is expressed as follows:

${\displaystyle {\begin{bmatrix}f_{0}\\f_{1}\\\vdots \\f_{n-1}\end{bmatrix}}={\begin{bmatrix}1&1&1&\cdots &1\\1&\alpha &\alpha ^{2}&\cdots &\alpha ^{n-1}\\1&\alpha ^{2}&\alpha ^{4}&\cdots &\alpha ^{2(n-1)}\\\vdots &\vdots &\vdots &&\vdots \\1&\alpha ^{n-1}&\alpha ^{2(n-1)}&\cdots &\alpha ^{(n-1)(n-1)}\\\end{bmatrix}}{\begin{bmatrix}v_{0}\\v_{1}\\\vdots \\v_{n-1}\end{bmatrix}}.}$

The matrix for this transformation is called the DFT matrix.

Similarly, the matrix notation for the inverse Fourier transform is

${\displaystyle {\begin{bmatrix}v_{0}\\v_{1}\\\vdots \\v_{n-1}\end{bmatrix}}={\frac {1}{n}}{\begin{bmatrix}1&1&1&\cdots &1\\1&\alpha ^{-1}&\alpha ^{-2}&\cdots &\alpha ^{-(n-1)}\\1&\alpha ^{-2}&\alpha ^{-4}&\cdots &\alpha ^{-2(n-1)}\\\vdots &\vdots &\vdots &&\vdots \\1&\alpha ^{-(n-1)}&\alpha ^{-2(n-1)}&\cdots &\alpha ^{-(n-1)(n-1)}\end{bmatrix}}{\begin{bmatrix}f_{0}\\f_{1}\\\vdots \\f_{n-1}\end{bmatrix}}.}$

Sometimes it is convenient to identify an ${\displaystyle n}$-tuple ${\displaystyle (v_{0},\ldots ,v_{n-1})}$ with a formal polynomial

${\displaystyle p_{v}(x)=v_{0}+v_{1}x+v_{2}x^{2}+\cdots +v_{n-1}x^{n-1}.\,}$

By writing out the summation in the definition of the discrete Fourier transform (2), we obtain:

${\displaystyle f_{k}=v_{0}+v_{1}\alpha ^{k}+v_{2}\alpha ^{2k}+\cdots +v_{n-1}\alpha ^{(n-1)k}.\,}$

This means that ${\displaystyle f_{k}}$ is just the value of the polynomial ${\displaystyle p_{v}(x)}$ for ${\displaystyle x=\alpha ^{k}}$, i.e.,

${\displaystyle f_{k}=p_{v}(\alpha ^{k}).\,}$

The Fourier transform can therefore be seen to relate the coefficients and the values of a polynomial: the coefficients are in the time-domain, and the values are in the frequency domain. Here, of course, it is important that the polynomial is evaluated at the ${\displaystyle n}$th roots of unity, which are exactly the powers of ${\displaystyle \alpha }$.

Similarly, the definition of the inverse Fourier transform (3) can be written:

${\displaystyle v_{j}={\frac {1}{n}}(f_{0}+f_{1}\alpha ^{-j}+f_{2}\alpha ^{-2j}+\cdots +f_{n-1}\alpha ^{-(n-1)j}).\qquad (5)}$

With

${\displaystyle p_{f}(x)=f_{0}+f_{1}x+f_{2}x^{2}+\cdots +f_{n-1}x^{n-1},}$

this means that

${\displaystyle v_{j}={\frac {1}{n}}p_{f}(\alpha ^{-j}).}$

We can summarize this as follows: if the values of ${\displaystyle p(x)}$ are the coefficients of ${\displaystyle q(x)}$, then the values of ${\displaystyle q(x)}$ are the coefficients of ${\displaystyle p(x)}$, up to a scalar factor and reordering.

Most of the important attributes of the complex DFT, including the inverse transform, the convolution theorem, and most fast Fourier transform (FFT) algorithms, depend only on the property that the kernel of the transform is a principal root of unity. These properties also hold, with identical proofs, over arbitrary rings. In the case of fields, this analogy can be formalized by the field with one element, considering any field with a primitive nth root of unity as an algebra over the extension field ${\displaystyle \mathbf {F} _{1^{n}}.}$

In particular, the applicability of ${\displaystyle O(n\log n)}$ fast Fourier transform algorithms to compute the NTT, combined with the convolution theorem, mean that the number-theoretic transform gives an efficient way to compute exact convolutions of integer sequences. While the complex DFT can perform the same task, it is susceptible to round-off error in finite-precision floating point arithmetic; the NTT has no round-off because it deals purely with fixed-size integers that can be exactly represented.

For the implementation of a "fast" algorithm (similar to how FFT computes the DFT), it is often desirable that the transform length is also highly composite, e.g., a power of two. However, there are specialized fast Fourier transform algorithms for finite fields, such as Wang and Zhu's algorithm,[4] that are efficient regardless of whether the transform length factors.

• Discrete Fourier transform (complex)
• Gauss sum
• Convolution
• Multiplication algorithm

• http://www.apfloat.org/ntt.html