Inmathematics, thediscrete Fourier transform over a ring generalizes thediscrete Fourier transform (DFT), of a function whose values are commonlycomplex numbers, over an arbitraryring.

LetR be anyring, let${\displaystyle n\ge 1}$ be an integer, and let${\displaystyle \alpha \in R}$ be aprincipalnth root of unity, defined by:^[1]

1

The discrete Fourier transform maps ann-tuple${\displaystyle (v_0,\dots ,v_{n-1})}$ of elements ofR to anothern-tuple${\displaystyle (f_0,\dots ,f_{n-1})}$ of elements ofR according to the following formula:

${\displaystyle f_k=\sum _{j=0}^{n-1}{v}_j{\alpha }^{jk}.}$

2

By convention, the tuple${\displaystyle (v_0,\dots ,v_{n-1})}$ is said to be in thetime domain and the indexj is calledtime. The tuple${\displaystyle (f_0,\dots ,f_{n-1})}$ is said to be in thefrequency domain and the indexk is calledfrequency. The tuple${\displaystyle (f_0,\dots ,f_{n-1})}$ is also called thespectrum of${\displaystyle (v_0,\dots ,v_{n-1})}$. This terminology derives from the applications of Fourier transforms insignal processing.

IfR is anintegral domain (which includesfields), it is sufficient to choose${\displaystyle \alpha }$ as aprimitiventh root of unity, which replaces the condition (1) by:^[1]

${\displaystyle {\alpha }^k\ne 1}$ for

Another simple condition applies in the case wheren 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}.}$

3

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

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

The matrix for this transformation is called theDFT matrix.

Similarly, the matrix notation for the inverse Fourier transform is

Sometimes it is convenient to identify ann-tuple${\displaystyle (v_0,\dots ,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).}$

4

The Fourier transform can therefore be seen to relate thecoefficients and thevalues 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 thenth 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}).}$

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 thevalues of${\displaystyle p_v(x)}$ are thecoefficients of${\displaystyle p_f(x)}$, then thevalues of${\displaystyle p_f(x)}$ are thecoefficients of${\displaystyle p_v(x)}$, up to a scalar factor and reordering.^[2]

If${\displaystyle F=\mathbb{C}}$ is the field of complex numbers, then the${\displaystyle n}$th roots of unity can be visualized as points on theunit circle of thecomplex plane. In this case, one usually takes

${\displaystyle \alpha =e^{\frac{-2\pi i}{n}},}$

which yields the usual formula for thecomplex discrete Fourier transform:

${\displaystyle f_k=\sum _{j=0}^{n-1}{v}_j{e}^{\frac{-2\pi i}{n}jk}.}$

Over the complex numbers, it is often customary to normalize the formulas for the DFT and inverse DFT by using the scalar factor${\displaystyle \frac{1}{\sqrt{n}}}$ in both formulas, rather than${\displaystyle 1}$ in the formula for the DFT and${\displaystyle \frac{1}{n}}$ in the formula for the inverse DFT. With this normalization, the DFT matrix is then unitary. Note that${\displaystyle \sqrt{n}}$ does not make sense in an arbitrary field.

If${\displaystyle F=\mathrm{G}\mathrm{F}(q)}$ is afinite field, whereq is aprime power, then the existence of a primitiventh root automatically implies thatndivides${\displaystyle q-1}$, because themultiplicative order of each element must divide the size of themultiplicative group ofF, which is${\displaystyle q-1}$. This in particular ensures that${\displaystyle n=\underset{n\mathrm{t}\mathrm{i}\mathrm{m}\mathrm{e}\mathrm{s}}{\underbrace{1+1+\cdots +1}}}$ is invertible, so that the notation${\displaystyle \frac{1}{n}}$ in (3) makes sense.

An application of the discrete Fourier transform over${\displaystyle \mathrm{G}\mathrm{F}(q)}$ is the reduction ofReed–Solomon codes toBCH codes incoding theory. Such transform can be carried out efficiently with proper fast algorithms, for example,cyclotomic fast Fourier transform.

Suppose${\displaystyle F=\mathrm{G}\mathrm{F}(p)}$. If${\displaystyle p\nmid n}$, it may be the case that${\displaystyle n\nmid p-1}$. This means we cannot find an${\displaystyle n^{th}}$ root of unity in${\displaystyle F}$. We may view the Fourier transform as an isomorphism${\displaystyle \mathrm{F}[C_n]=\mathrm{F}[x]/(x^n-1)\cong \underset{i}{⨁}\mathrm{F}[x]/(P_i(x))}$ for some polynomials${\displaystyle P_i(x)}$, in accordance withMaschke's theorem. The map is given by theChinese remainder theorem, and the inverse is given by applyingBézout's identity for polynomials.^[3]

${\displaystyle x^n-1=\prod _{d|n}{\mathrm{\Phi }}_d(x)}$, a product of cyclotomic polynomials. Factoring${\displaystyle {\mathrm{\Phi }}_d(x)}$ in${\displaystyle F[x]}$ is equivalent to factoring the prime ideal${\displaystyle (p)}$ in${\displaystyle \mathrm{Z}[\zeta ]=\mathrm{Z}[x]/({\mathrm{\Phi }}_d(x))}$. We obtain${\displaystyle g}$ polynomials${\displaystyle P_1\dots P_g}$ of degree${\displaystyle f}$ where${\displaystyle fg=\phi (d)}$ and${\displaystyle f}$ is the order of${\displaystyle p\text{ mod }d}$.

As above, we may extend the base field to${\displaystyle \mathrm{G}\mathrm{F}(q)}$ in order to find a primitive root, i.e. asplitting field for${\displaystyle x^n-1}$. Now${\displaystyle x^n-1=\prod _k(x-{\alpha }^k)}$, so an element${\displaystyle \sum _{j=0}^{n-1}{v}_j{x}^j\in F[x]/(x^n-1)}$ maps to${\displaystyle \sum _{j=0}^{n-1}{v}_j{x}^j\mathrm{mod}(x-{\alpha }^k)\equiv \sum _{j=0}^{n-1}{v}_j({\alpha }^k{)}^j}$ for each${\displaystyle k}$.

When${\displaystyle p|n}$, we may still define an${\displaystyle F_p}$-linear isomorphism as above. Note that${\displaystyle (x^n-1)=(x^m-1{)}^{p^s}}$ where${\displaystyle n=m{p}^s}$ and${\displaystyle p\nmid m}$. We apply the above factorization to${\displaystyle x^m-1}$, and now obtain the decomposition${\displaystyle F[x]/(x^n-1)\cong \underset{i}{⨁}F[x]/(P_i(x{)}^{p^s})}$. The modules occurring are now indecomposable rather than irreducible.

Suppose${\displaystyle p\nmid n}$ so we have an${\displaystyle n^{th}}$ root of unity${\displaystyle \alpha }$. Let${\displaystyle A}$ be the above DFT matrix, aVandermonde matrix with entries${\displaystyle A_{ij}={\alpha }^{ij}}$ for. Recall that${\displaystyle \sum _{j=0}^{n-1}{\alpha }^{(k-l)j}=n{\delta }_{k,l}}$ since if${\displaystyle k=l}$, then every entry is 1. If${\displaystyle k\ne l}$, then we have ageometric series with common ratio${\displaystyle {\alpha }^{k-l}}$, so we obtain${\displaystyle \frac{1-{\alpha }^{n(k-l)}}{1-{\alpha }^{k-l}}}$. Since${\displaystyle {\alpha }^n=1}$ the numerator is zero, but${\displaystyle k-l\ne 0}$ so the denominator is nonzero.

First computing the square,${\displaystyle (A^2{)}_{ik}=\sum _{j=0}^{n-1}{\alpha }^{j(i+k)}=n{\delta }_{i,-k}}$. Computing${\displaystyle A^4=(A^2{)}^2}$ similarly and simplifying the deltas, we obtain${\displaystyle (A^4{)}_{ik}=n^2{\delta }_{i,k}}$. Thus,${\displaystyle A^4=n^2{I}_n}$ and the order is${\displaystyle 4\cdot \text{ord}(n^2)}$.

In order to align with the complex case and ensure the matrix is order 4 exactly, we can normalize the above DFT matrix${\displaystyle A}$ with${\displaystyle \frac{1}{\sqrt{n}}}$. Note that though${\displaystyle \sqrt{n}}$ may not exist in the splitting field${\displaystyle F_q}$ of${\displaystyle x^n-1}$, we may form a quadratic extension${\displaystyle F_{q^2}\cong F_q[x]/(x^2-n)}$ in which the square root exists. We may then set${\displaystyle U=\frac{1}{\sqrt{n}}A}$, and${\displaystyle U^4=I_n}$.

Suppose${\displaystyle p\nmid n}$. One can ask whether the DFT matrix isunitary over a finite field. If the matrix entries are over${\displaystyle F_q}$, then one must ensure${\displaystyle q}$ is a perfect square or extend to${\displaystyle F_{q^2}}$ in order to define the order two automorphism${\displaystyle x\mapsto x^q}$. Consider the above DFT matrix${\displaystyle A_{ij}={\alpha }^{ij}}$. Note that${\displaystyle A}$ is symmetric. Conjugating and transposing, we obtain${\displaystyle A_{ij}^{\ast }={\alpha }^{qji}}$.

${\displaystyle (A{A}^{\ast }{)}_{ik}=\sum _{j=0}^{n-1}{\alpha }^{j(i+qk)}=n{\delta }_{i,-qk}}$

by a similar geometric series argument as above. We may remove the${\displaystyle n}$ by normalizing so that${\displaystyle U=\frac{1}{\sqrt{n}}A}$ and${\displaystyle (U{U}^{\ast }{)}_{ik}={\delta }_{i,-qk}}$. Thus${\displaystyle U}$ is unitary iff${\displaystyle q\equiv -1(\text{mod}n)}$. Recall that since we have an${\displaystyle n^{th}}$ root of unity,${\displaystyle n|q^2-1}$. This means that${\displaystyle q^2-1\equiv (q+1)(q-1)\equiv 0(\text{mod}n)}$. Note if${\displaystyle q}$ was not a perfect square to begin with, then${\displaystyle n|q-1}$ and so${\displaystyle q\equiv 1(\text{mod}n)}$.

For example, when${\displaystyle p=3,n=5}$ we need to extend to${\displaystyle q^2=3^4}$ to get a 5th root of unity.${\displaystyle q=9\equiv -1(\text{mod}5)}$.

For a nonexample, when${\displaystyle p=3,n=8}$ we extend to${\displaystyle F_{3^2}}$ to get an 8th root of unity.${\displaystyle q^2=9}$, so${\displaystyle q\equiv 3(\text{mod}8)}$, and in this case${\displaystyle q+1\not\equiv 0}$ and${\displaystyle q-1\not\equiv 0}$.${\displaystyle U{U}^{\ast }}$ is a square root of the identity, so${\displaystyle U}$ is not unitary.

When${\displaystyle p\nmid n}$, we have an${\displaystyle n^{th}}$ root of unity${\displaystyle \alpha }$ in the splitting field${\displaystyle F_q\cong F_p[x]/(x^n-1)}$. Note that thecharacteristic polynomial of the above DFT matrix may not split over${\displaystyle F_q}$. The DFT matrix is order 4. We may need to go to a further extension${\displaystyle F_{q^{\prime }}}$, the splitting extension of the characteristic polynomial of the DFT matrix, which at least contains fourth roots of unity. If${\displaystyle a}$ is a generator of the multiplicative group of${\displaystyle F_{q^{\prime }}}$, then the eigenvalues are${\displaystyle \{\pm 1,\pm a^{(q^{\prime }-1)/4}\}}$, in exact analogy with the complex case. They occur with some nonnegative multiplicity.

Thenumber-theoretic transform (NTT)^[4] is obtained by specializing the discrete Fourier transform to${\displaystyle F=\mathbb{Z}/p}$, theintegers modulo a primep. This is afinite field, and primitiventh roots of unity exist whenevern divides${\displaystyle p-1}$, so we have${\displaystyle p=\xi n+1}$ for a positive integerξ. Specifically, let${\displaystyle \omega }$ be a primitive${\displaystyle (p-1)}$th root of unity, then annth root of unity${\displaystyle \alpha }$ can be found by letting${\displaystyle \alpha ={\omega }^{\xi }}$.

e.g. for${\displaystyle p=5}$,${\displaystyle \alpha =2}$

when${\displaystyle N=4}$

The number theoretic transform may be meaningful in thering${\displaystyle \mathbb{Z}/m}$, even when the modulusm is not prime, provided a principal root of ordern exists. Special cases of the number theoretic transform such as theFermat Number Transform (m = 2^k+1), used by theSchönhage–Strassen algorithm, or Mersenne Number Transform^[5] (m = 2^k − 1) use a composite modulus.

In general, if$m=\prod _i{p}_i^{e_i}$, then one may find an$n^{th}$ root of unity modm by finding primitive$n^{th}$ roots of unity${\displaystyle g_i}$ mod$p_i^{e_i}$, yielding a tuple$g={\left(g_i\right)}_i\in \prod _i{\left(\mathbb{Z}/p_i^{e_i}\mathbb{Z}\right)}^{\ast }$. The preimage of${\displaystyle g}$ under theChinese remainder theorem isomorphism is an$n^{th}$ root of unity$\alpha$ such that${\alpha }^{n/2}=-1\mathrm{mod}m$. This ensures that the above summation conditions are satisfied. We must have that$n|\phi (p_i^{e_i})$ for each${\displaystyle i}$, where${\displaystyle \phi }$ is theEuler's totient function function.^[6]

Fast Fourier transform can be adapted to NTT and implemented with only integer operations.^[7] Some choices ofm such as theSolinas prime${\displaystyle 2^{64}-2^{32}+1}$ are even easier to calculate on computers as they require no division operation for reduction.^[8]

Thediscrete weighted transform (DWT) is a variation on the discrete Fourier transform over arbitrary rings involvingweighting the input before transforming it by multiplying elementwise by a weight vector, then weighting the result by another vector.^[9] TheIrrational base discrete weighted transform is a special case of this.

Most of the important attributes of thecomplex DFT, including the inverse transform, theconvolution theorem, and mostfast 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 thefield with one element, considering any field with a primitiventh root of unity as an algebra over the extension field${\displaystyle {\mathbf{F}}_{1^n}.}$^{[clarification needed]}

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 thenumber-theoretic transform gives an efficient way to compute exactconvolutions of integer sequences. While the complex DFT can perform the same task, it is susceptible toround-off error in finite-precisionfloating 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 howFFT computes theDFT), it is often desirable that the transform length is also highly composite, e.g., apower of two. However, there are specialized fast Fourier transform algorithms for finite fields, such as Wang and Zhu's algorithm,^[10] that are efficient regardless of the transform length factors.

• Discrete Fourier transform (complex)
• Fourier transform on finite groups
• Gauss sum
• Convolution
• Least-squares spectral analysis
• Multiplication algorithm

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

• Fourier analysis

• Articles with short description
• Short description is different from Wikidata
• Wikipedia articles needing clarification from November 2018