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.

Let 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:

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

By convention, the tuple ${\displaystyle (v_{0},\ldots ,v_{n-1})}$ is said to be in the time domain and the index j is called time. The tuple ${\displaystyle (f_{0},\ldots ,f_{n-1})}$ is said to be in the frequency domain and the index 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 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:

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

where the sum matches (1). Since ${\displaystyle \alpha }$ is a primitive root of unity, ${\displaystyle \beta -1\neq 0}$. 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 ${\displaystyle \alpha ^{n/2}=-1}$.