the convolution theorem
Convolution is the operation of sliding one signal across another, multiplying where they overlap, and adding up — it is how a blur smears an image, how an echo trails a sound, and how a filter shapes a waveform. Done directly it is laborious: for two lists of length N, every output point is a sum over up to N products, giving O(N^2) work overall. The convolution theorem is the beautiful shortcut that says convolution, which is hard, becomes ordinary multiplication, which is easy, once you cross into the frequency domain.
The statement is crisp: the Fourier transform of a convolution equals the pointwise product of the Fourier transforms. In symbols, if x and h are signals and * denotes convolution, then DFT(x * h) = DFT(x) . DFT(h), where the dot is plain element-by-element multiplication. So the recipe to convolve two signals is three steps: transform x and transform h (two FFTs), multiply the two spectra together term by term (cheap, O(N) work), then inverse-transform the product back (one more FFT). The tangled sliding-and-summing in the time domain collapses to a single multiply in the frequency domain. Intuitively this makes sense because convolution acts on each frequency independently — a filter just scales each frequency component by some amount — and the transform is precisely what exposes those independent components.
This theorem is one of the most consequential facts in computational mathematics, because it converts an O(N^2) operation into O(N log N) (the cost is dominated by the three FFTs). It underlies fast digital filtering, image processing, fast polynomial and big-integer multiplication, and the matched filters in radar and communications. One careful point: the DFT performs CIRCULAR (periodic) convolution, which wraps the ends around. To get ordinary linear convolution you must zero-pad both signals to at least the combined length minus one before transforming, otherwise the wrap-around contaminates the result.
To convolve two length-1000 signals directly costs about 1000^2 = 10^6 multiply-adds. Via the theorem: zero-pad both to length 2048, take two FFTs, multiply the spectra (2048 cheap products), and one inverse FFT — roughly 3 * 2048 * log2(2048) plus 2048, about 70,000 operations. Fifteen times fewer here, and the gap explodes as the signals grow.
Convolve = transform, multiply, transform back — O(N^2) becomes O(N log N).
The DFT gives CIRCULAR convolution, not linear: without zero-padding, the tail of the result wraps around and corrupts the start. Always pad to at least len(x) + len(h) - 1 to recover true linear convolution.