Fast Fourier Transforms for Metabelian Groups

Let G be a finite group . Then $L_s (G)$, the minimal number of arithmetic operations to evaluate a Fourier transform corresponding to G, is smaller than $2 \cdot |G|^2 $. The fast Fourier transform algorithms improve this trivial upper bound by showing that for a cyclic group $G,L_s (G) \leqq c \cdot |G| \cdot \log |G|$. This last result is extended to metabelian groups, and it is shown that these groups also have fast inverse Fourier transforms. In particular there are fast algorithms for the (inverse) Fourier transforms for dihedral and generalized quaternion groups, as well as for all groups of square-free order.