Computing Fourier transforms and convolutions of Sn−1Sn−1-invariant signals on SnSn in time linear in nn

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