20.11.2008

The c-linear complexity L_c(A) of a complex matrix A is the minimal number of additions, subtractions and multiplications by complex constants of absolute value ≤ c, c ≥ 2, needed to evaluate A at a generic input vector. Define L_S(A) := lim_c→∞L_c(A). We show that if A is a Fourier transform on the finite group G, then |L_S(A) - L_S(A^-1)| ≤ |G|. The c-linear complexity of a finite group G is defined by L_c(G) := min {L_c(A) | A a Fourier transform of G}. We prove that L₂(G) > 1/4|G| log|G| for any finite group G, and present two infinite classes of non-abelian groups G with L₂(G) ≤ 0.6|G| log|G| and L₂(G) ≤ 0.8|G| log|G|, respectively. Thus there are non-abelian groups with even faster Fourier transforms than elementary abelian 2-groups (for which L₂(G) ≤ |G| log|G|) !