Combinatorialist here; I mainly think of fourier transforms as an efficient way to shuffle cards.

https://statweb.stanford.edu/~cgates/PERSI/papers/aldous86.p...

Neat, I've spent years with the Fourier transform and never have seen this!

Yep. Grade school multiplication of two large numbers is the same thing (except for the carries) as convolution of two signals in the time domain. The numbers are the signals. You already know that piecewise multiplication in the frequency domain is equivalent to (and faster than) convolution of those signals in the time domain. So that's what FFT multiplication is about.

It's only useful for VERY large numbers (thousands of digits), which is why most people never encounter it.

Note that a “signal” in this context is just a trigonometric polynomial over a periodic interval.

If you think of your periodic interval as representing angle measure, and the points in the interval as points on the unit circle in the complex plane, then your trigonometric polynomial can alternately be thought of as a Laurent polynomial in the complex plane. https://en.wikipedia.org/wiki/Laurent_polynomial

What the FFT does is convert between the values of your function at n roots of unity in the complex plane -> the coefficients of the Laurent polynomial interpolating those values.