The Discrete Fourier Transform (DFT)

The Discrete Fourier Transform (DFT) is one of the most important operators in computational mathematics. The DFT operator acts on the n-dimenional Hilbert Space $L^2(Z/n)$ of complex valued functions on the group of integers modulo n: It becomes very useful in the last century due to the Cooley-Tukey Fast Fourier Transform (FFT) algorithm that computes the DFT in order of nlog(n) operations.

In the lecture I will elaborate on an idea-due to Auslander and Tolimieri-which establishes this algorithm as a logical consequence of the construction of an arithmetic model which realizes the irreducible representations of Heisenberg group.