The unitary discrete Fourier transform on $\mathbb{Z}\mathrm{/}N\mathbb{Z}$

Let $N\ge 1$ and let ${\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}$ be the complex vector space of all functions $\mathbb{Z}\mathrm{/}N\mathbb{Z}\to \mathbb{C}$ (The vector space $F^X$ of all functions $X\to F$ with pointwise operations, and $F^n$ as the case $X=n=\{0,1,\dots ,n-1\}$, Vector space over a field). For $f\in {\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}$ define the unitary discrete Fourier transform ${\mathcal{F}}_{N}f:\mathbb{Z}\to \mathbb{C}$ by

$({\mathcal{F}}_{N}f)(k):=N^{-1\mathrm{/}2}{\sum }_{x=0}^{N-1}f([x{]}_N)e^{-2\pi ikx\mathrm{/}N},k\in \mathbb{Z},$

where $[x{]}_N$ is the class of the integer $x$ in $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ (The congruence class $[a{]}_n$ and the quotient set $\mathbb{Z}\mathrm{/}n$, Congruence modulo every integer is an equivalence relation on $\mathbb{Z}$), $e^z=\exp z$ is the complex exponential (The complex exponential by its power series), and $N^{-1\mathrm{/}2}$ is the rational power of the positive real $N$ (Rational powers $a^r$ of a positive base, Laws of rational exponents), read in $\mathbb{C}$ through the embedded copy of $\mathbb{R}$ ($\mathbb{C}=\mathbb{R}[x]\mathrm{/}(x^2+1)$ is a field, every element is uniquely $a+bi$, and every nonzero element has inverse $(a-bi)\mathrm{/}(a^2+b^2)$).

The summands depend only on classes, and the transform is periodic in $k$. Each summand $f([x{]}_N)e^{-2\pi ikx\mathrm{/}N}$ is a complex number determined by the class $[x{]}_N$ and the integer $k$, and the classes $[0{]}_N,\dots ,[N-1{]}_N$ are pairwise distinct and exhaust $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ (For $n\ge 1$, every class in $\mathbb{Z}\mathrm{/}n$ has one representative $r$ with $0\le r<n$, so $\mid \mathbb{Z}\mathrm{/}n\mid =n$; while $\mathbb{Z}\mathrm{/}0$ is in bijection with $\mathbb{Z}$); so the display is the finite sum, over the finite group, of the family $x\mapsto f(x)N^{-1\mathrm{/}2}{e}^{-2\pi ikx\mathrm{/}N}$, and reindexing by any other representative list leaves it unchanged (Finite commutative-monoid sums are invariant under bijective reindexing, split over disjoint unions, and satisfy the finite Fubini rule, part 1). Reindexing by the transition $x\mapsto x+N$ uses $e^{-2\pi ik(x+N)\mathrm{/}N}=e^{-2\pi ikx\mathrm{/}N}{e}^{-2\pi ik}$ and $e^{-2\pi ik}=1$ for every integer $k$, because $-2\pi k\in 2\pi \mathbb{Z}$ ($\exp (z+w)=\exp z\exp w$, and the complex exponential extends the real exponential, $\ker (\exp )=2\pi i\mathbb{Z}$, and $\exp z=\exp w$ exactly when $z-w\in 2\pi i\mathbb{Z}$). For periodicity in $k$, the same two facts give $e^{-2\pi i(k+N)x\mathrm{/}N}=e^{-2\pi ikx\mathrm{/}N}{e}^{-2\pi ix}=e^{-2\pi ikx\mathrm{/}N}$ for every integer $x$, so $({\mathcal{F}}_{N}f)(k+N)=({\mathcal{F}}_{N}f)(k)$ for every $k\in \mathbb{Z}$ ($\exp (z+w)=\exp z\exp w$, and the complex exponential extends the real exponential, $\ker (\exp )=2\pi i\mathbb{Z}$, and $\exp z=\exp w$ exactly when $z-w\in 2\pi i\mathbb{Z}$). Consequently ${\mathcal{F}}_{N}f$ factors through the quotient $\mathbb{Z}\to \mathbb{Z}\mathrm{/}N\mathbb{Z}$ and is a well-defined function on $\mathbb{Z}\mathrm{/}N\mathbb{Z}$, and ${\mathcal{F}}_N$ is a map ${\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}\to {\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}$.

Form in terms of characters. Define ${\chi }_k([m]):=\exp (2\pi ikm\mathrm{/}N)$ for $k,m\in \mathbb{Z}$. The assignment is well defined on classes because replacing $m$ by $m+N$ multiplies the exponential by $e^{2\pi ik}=1$ ($\ker (\exp )=2\pi i\mathbb{Z}$, and $\exp z=\exp w$ exactly when $z-w\in 2\pi i\mathbb{Z}$); it is multiplicative, ${\chi }_k(x+y)={\chi }_k(x){\chi }_k(y)$, by the addition law ($\exp (z+w)=\exp z\exp w$, and the complex exponential extends the real exponential); and it takes values of modulus $1$, since $\mathrm{\mid }\exp (i\theta )\mathrm{\mid }=1$ ($\exp (x+iy)=e^x(\cos y+i\sin y)$, $\mathrm{\mid }\exp (x+iy)\mathrm{\mid }=e^x$, and $e^{i\pi }+1=0$). Thus the ${\chi }_k$ are characters of the finite group $\mathbb{Z}\mathrm{/}N\mathbb{Z}$ (homomorphisms into the unit circle; no continuity is required on a discrete group), and the definition reads

$({\mathcal{F}}_{N}f)(k)=N^{-1\mathrm{/}2}{\sum }_{x\in \mathbb{Z}\mathrm{/}N}f(x){\chi }_{-k}(x),$

with the positive-sign transform obtained by replacing $k$ with $-k$. This fixes the negative-sign, $N^{-1\mathrm{/}2}$-normalised convention of the whole page: the forward transform carries the minus sign in the exponent and the factor $N^{-1\mathrm{/}2}$, and the inverse transform of the inversion theorem carries the plus sign with the same factor. A different, unnormalised convention is introduced later on this page for the algorithmic part; the two are related by a single explicit rescaling recorded there.

Linearity, recorded for later use. For $a,b\in \mathbb{C}$ and $f,g\in {\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}$ one has ${\mathcal{F}}_N(af+bg)=a{\mathcal{F}}_{N}f+b{\mathcal{F}}_{N}g$: the identity holds at each $k$ by distributivity in $\mathbb{C}$ ($\mathbb{C}=\mathbb{R}[x]\mathrm{/}(x^2+1)$ is a field, every element is uniquely $a+bi$, and every nonzero element has inverse $(a-bi)\mathrm{/}(a^2+b^2)$) and the elementary laws of finite sums over a fixed finite index set, which follow from the recursion clauses of A finite sum in a commutative monoid indexed by an arbitrary finite set by induction on an enumeration. Nothing else about ${\mathcal{F}}_N$ — unitarity, invertibility, the convolution law — is asserted here; those are proved in the items that follow.

• Why the normalisation is split as $N^{-1\mathrm{/}2}$. The factor $N^{-1\mathrm{/}2}$ is exactly what makes the transform an isometry for the counting inner product, and is the finite analogue of the $1\mathrm{/}\sqrt{2\pi }$ convention in the $L^2$ Fourier transform. Taylor writes the finite transform (11.1) with the factor $1\mathrm{/}n$ in the forward direction and weights $L^2({\mathrm{\Gamma }}_n)$ by $(1\mathrm{/}n)$-counting measure; the two descriptions differ by relabelling the sides, not by mathematics, and the translation used here sends ${\omega }^j$ to $[j{]}_N$ and $f^{\mathrm{\#}}$ to $N^{-1\mathrm{/}2}{\mathcal{F}}_{N}f$.

• No convergence hypothesis is needed or used. The index set is finite, so the definition involves no limit, no summability condition and no auxiliary topology; it applies to every function in ${\mathbb{C}}^{\mathbb{Z}\mathrm{/}N}$, including the zero function, and it is total at $N=1$, where the single summand is $f([0{]}_1)e^0=f([0{]}_1)$ with coefficient $1^{-1\mathrm{/}2}=1$.