Computing Fourier transforms and convolutions of -invariant signals on in time linear in

Let S n denote the symmetric group on { 1 , … , n } and S n − 1 the stabilizer subgroup of n . We derive algorithms for computing Fourier transforms of left and right S n − 1 -invariant signals a : S n → C that require a total of 2 n − 2 additions and n − 2 scalar multiplications. Furthermore we show that the convolution of such signals can also be computed in time linear in n .