Theory
Character of ℤ/Nℤ:
χₖ(n) = e^(2πikn/N)
k = 0,1,...,N−1
DFT (Fourier on ℤ/Nℤ):
f̂(k) = ∑ₙ f(n) χₖ(n)*
f(n) = (1/N) ∑ₖ f̂(k) χₖ(n)
Pontryagin: Ĝ = Hom(G,U(1))
ℤ/Nℤ ≅ ẑ/Nẑ (self-dual!)
ℝ̂ ≅ ℝ, ℤ̂ ≅ T (circle)
Convolution theorem:
f*g ↔ f̂·ĝ (pointwise)
Pontryagin duality (1934): every locally compact abelian group G is naturally isomorphic to its double dual G̃̂. The Fourier transform is the bridge. For ℤ/Nℤ, the N characters form an orthonormal basis. The self-duality of ℤ/Nℤ is why DFT has the same structure forward and inverse.