Between thousand to million times per day, your cellphone calculates the Fourier Transform (FT) of certain functions defined on 0,1,…,N-1, with N large (order of magnitude of thousands and more). The calculation is done using the Fast Fourier Transform (FFT) - discovered by Cooley–Tukey in 1965 and by Gauss in 1805. In the lecture I want to advertise a beautiful way—due to Auslander-Tolimieri—to obtain the FFT as a natural consequence of an answer to the following:
Question: How to think on the space of functions on the set 0,1,…,N-1?
Engineers tell us that there are two answers for this question:
(A) as functions on that set, where 0,1,…,N-1 regarded as times;
and,
(B) as functions on that set, where 0,1,…,N-1 regarded frequencies;
and then the FT is an operator translating between the two spaces. In the lecture, I will explain that there is another answer, i.e., a not so well-known third space (C), of arithmetic nature, that also gives an answer to the above question, and then the FFT appears simply as the composition of two operators: the one translating between spaces (A) and (C), and the one that translates (C) to (B).
Remark: The lecture is prepared to be understood to anyone who is familiar with basic linear algebra. In particular, advanced undergraduate students, from computer science, engineering, mathematics, physics, etc, are more than welcome to attend.