Abstract
This paper introduces new techniques for the efficient computation of discrete Fourier transforms (DFTs) of Sn-k-invariant functions on the symmetric group Sn. We uncover diamond- and leaf-rake-like structures in Young's seminormal and orthogonal representations. Combining this with both a multiresolution scheme and an anticipation technique for saving scalar multiplications leads to linear time partial FFTs. Following the inductive version of Young's branching rule we obtain a global FFT that computes a DFT of Sn-k-invariant functions on Sn in at most ck...[Sn : Sn-k] scalar multiplications and additions, where ck denotes a positive constant depending only on k. This run-time, which is linear in [Sn : Sn-k], is order optimal and improves Maslen's algorithm. For example, it takes less than one second on a standard notebook to run our FFT algorithm for an Sn-2-invariant real-valued function on Sn, n=5000.