Generalisation of Fourier transform to any ring
In mathematics, the discrete Fourier transform over a ring generalizes the discrete Fourier transform (DFT), of a function whose values are commonly complex numbers, over an arbitrary ring.
Definition.
Let R be any ring, let formula_1 be an integer, and let formula_2 be a principal "n"th root of unity, defined by:
 ;templatestyles src="Numbered block/styles.css" / ;
The discrete Fourier transform maps an "n"-tuple formula_3 of elements of R to another "n"-tuple formula_4 of elements of R according to the following formula:
 ;templatestyles src="Numbered block/styles.css" / ;
By convention, the tuple formula_3 is said to be in the "time domain" and the index j is called "time". The tuple formula_4 is said to be in the "frequency domain" and the index k is called "frequency". The tuple formula_4 is also called the "spectrum" of formula_3. This terminology derives from the applications of Fourier transforms in signal processing.
If R is an integral domain (which includes fields), it is sufficient to choose formula_9 as a primitive "n"th root of unity, which replaces the condition (1) by:
formula_10 for formula_11
 ;templatestyles src="Math_proof/styles.css" / ;Proof
Take formula_12 with formula_11. Since formula_14, formula_15, giving:
formula_16
where the sum matches (1). Since formula_9 is a primitive root of unity, formula_18. Since 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 formula_19.
Inverse.
The inverse of the discrete Fourier transform is given as:
 ;templatestyles src="Numbered block/styles.css" / ;
where formula_20 is the multiplicative inverse of n in R (if this inverse does not exist, the DFT cannot be inverted).
 ;templatestyles src="Math_proof/styles.css" / ;Proof
Substituting (2) into the right-hand-side of (3), we get
formula_21
This is exactly equal to formula_22, because 
formula_23 when formula_24 (by (1) with formula_25), and 
formula_26 when formula_27. ∎
Matrix formulation.
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:
formula_28
The matrix for this transformation is called the DFT matrix.
Similarly, the matrix notation for the inverse Fourier transform is 
formula_29
Polynomial formulation.
Sometimes it is convenient to identify an n-tuple formula_3 with a formal polynomial
formula_31
By writing out the summation in the definition of the discrete Fourier transform (2), we obtain:
formula_32
This means that formula_33 is just the value of the polynomial formula_34 for formula_35, i.e.,
 ;templatestyles src="Numbered block/styles.css" / ;
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 nth roots of unity, which are exactly the powers of formula_9.
Similarly, the definition of the inverse Fourier transform (3) can be written:
 ;templatestyles src="Numbered block/styles.css" / ;
With
formula_37
this means that
formula_38
We can summarize this as follows: if the "values" of formula_34 are the "coefficients" of formula_40, then the "values" of formula_40 are the "coefficients" of formula_34, up to a scalar factor and reordering.
Special cases.
Complex numbers.
If formula_43 is the field of complex numbers, then the formula_44th roots of unity can be visualized as points on the unit circle of the complex plane. In this case, one usually takes
formula_45
which yields the usual formula for the complex discrete Fourier transform:
formula_46
Over the complex numbers, it is often customary to normalize the formulas for the DFT and inverse DFT by using the scalar factor formula_47 in both formulas, rather than formula_48 in the formula for the DFT and formula_49 in the formula for the inverse DFT. With this normalization, the DFT matrix is then unitary. 
Note that formula_50 does not make sense in an arbitrary field.
Finite fields.
If formula_51 is a finite field, where q is a prime power, then the existence of a primitive nth root automatically implies that n divides formula_52, because the multiplicative order of each element must divide the size of the multiplicative group of F, which is formula_52. This in particular ensures that formula_54 is invertible, so that the notation formula_49 in (3) makes sense.
An application of the discrete Fourier transform over formula_56 is the reduction of Reed–Solomon codes to BCH codes in coding theory. Such transform can be carried out efficiently with proper fast algorithms, for example, cyclotomic fast Fourier transform.
Polynomial formulation without nth root.
Suppose formula_57. If formula_58, it may be the case that formula_59. This means we cannot find an formula_60 root of unity in formula_61. We may view the Fourier transform as an isomorphism formula_62 for some polynomials formula_63, in accordance with Maschke's theorem. The map is given by the Chinese remainder theorem, and the inverse is given by applying Bézout's identity for polynomials.
formula_64, a product of cyclotomic polynomials. Factoring formula_65 in formula_66 is equivalent to factoring the prime ideal formula_67 in formula_68. We obtain formula_69 polynomials formula_70 of degree formula_71 where formula_72 and formula_71 is the order of formula_74.
As above, we may extend the base field to formula_56 in order to find a primitive root, i.e. a splitting field for formula_76. Now formula_77, so an element formula_78 maps to formula_79 for each formula_80.
When p divides n.
When formula_81, we may still define an formula_82-linear isomorphism as above. Note that formula_83 where formula_84 and formula_85. We apply the above factorization to formula_86, and now obtain the decomposition formula_87. The modules occurring are now indecomposable rather than irreducible.
Order of the DFT matrix.
Suppose formula_88 so we have an formula_60 root of unity formula_9. Let formula_91 be the above DFT matrix, a Vandermonde matrix with entries formula_92 for formula_93. Recall that formula_94 since if formula_95, then every entry is 1. If formula_96, then we have a geometric series with common ratio formula_97, so we obtain formula_98. Since formula_14 the numerator is zero, but formula_100 so the denominator is nonzero.
First computing the square, formula_101. Computing formula_102 similarly and simplifying the deltas, we obtain formula_103. Thus, formula_104 and the order is formula_105.
Normalizing the DFT matrix.
In order to align with the complex case and ensure the matrix is order 4 exactly, we can normalize the above DFT matrix formula_91 with formula_47. Note that though formula_50 may not exist in the splitting field formula_109 of formula_76, we may form a quadratic extension formula_111 in which the square root exists. We may then set formula_112, and formula_113.
Unitarity.
Suppose formula_88. One can ask whether the DFT matrix is unitary over a finite field. If the matrix entries are over formula_109, then one must ensure formula_116 is a perfect square or extend to formula_117 in order to define the order two automorphism formula_118. Consider the above DFT matrix formula_92. Note that formula_91 is symmetric. Conjugating and transposing, we obtain formula_121.
formula_122
by a similar geometric series argument as above. We may remove the formula_44 by normalizing so that formula_124 and formula_125. Thus formula_126 is unitary iff formula_127. Recall that since we have an formula_60 root of unity, formula_129. This means that formula_130. Note if formula_116 was not a perfect square to begin with, then formula_132 and so formula_133.
For example, when formula_134 we need to extend to formula_135 to get a 5th root of unity. formula_136.
For a nonexample, when formula_137 we extend to formula_138 to get an 8th root of unity. formula_139, so formula_140, and in this case formula_141 and formula_142. formula_143 is a square root of the identity, so formula_126 is not unitary.
Eigenvalues of the DFT matrix.
When formula_88, we have an formula_60 root of unity formula_9 in the splitting field formula_148. Note that the characteristic polynomial of the above DFT matrix may not split over formula_109. 
The DFT matrix is order 4. We may need to go to a further extension formula_150, the splitting extension of the characteristic polynomial of the DFT matrix, which at least contains fourth roots of unity. If formula_151 is a generator of the multiplicative group of formula_150, then the eigenvalues are formula_153, in exact analogy with the complex case. They occur with some nonnegative multiplicity.
Number-theoretic transform.
The number-theoretic transform (NTT) is obtained by specializing the discrete Fourier transform to formula_154, the integers modulo a prime p. This is a finite field, and primitive nth roots of unity exist whenever n divides formula_155, so we have formula_156 for a positive integer ξ. Specifically, let formula_157 be a primitive formula_158th root of unity, then an nth root of unity formula_9 can be found by letting formula_160.
e.g. for formula_161, formula_162
formula_163
when formula_164
formula_165
The number theoretic transform may be meaningful in the ring formula_166, even when the modulus m is not prime, provided a principal root of order n exists. Special cases of the number theoretic transform such as the Fermat Number Transform ("m" = 2"k"+1), used by the Schönhage–Strassen algorithm, or Mersenne Number Transform ("m" = 2"k" − 1) use a composite modulus.
Discrete weighted transform.
The discrete weighted transform (DWT) is a variation on the discrete Fourier transform over arbitrary rings involving weighting the input before transforming it by multiplying elementwise by a weight vector, then weighting the result by another vector. The Irrational base discrete weighted transform is a special case of this.
Properties.
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 "n"th root of unity as an algebra over the extension field formula_167
In particular, the applicability of formula_168 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.
Fast algorithms.
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, that are efficient regardless of whether the transform length factors.