Dear GAP Forum,

Igor Markov asked about computing Fourier transforms on groups. For those who
haven't met this concept, given a function f from a group G to a field k of
characteristic coprime to G, then the Fourier transform of f is a function F
from
the k-linear representations of G to k, defined by

F(p) = Sum(g in G : f(g)p(g))

where p: G -> GL_n(k) is a representation.

Normally, one thinks of p running over the irreducible representations of G,
in which case, the Fourier transform can be regarded as a change of basis in
the group algebra from the basis of group elements to the basis of matrix
entries in irreducible representations.

The case of G = C* (the multiplicative group of the complex numbers) is
essentially
the standard Fourier transform, while G = C_{2^n} (cyclic order 2^n) is the
discrete Fourier transform.

Anyway, this offers a natural naive implementation in GAP:

FourierTransform := function(f, G)
return rho -> Sum(G, g->Image(rho,g)*f(g));
end;

this returns a function which accepts a homomorphism from G to a matrix group
and returns the value of the Fourier transform there. off the top of my head,
I'm less sure about how to do the inverse Fourier transform effectively.

There is a lot of work by Michael Clausen and Ulrich Baum on computing
non-abelian Fourier transforms efficiently. I include a few BiBTeX entries
culled from a very cursory search of MathSciNet. The basis of their approach
is the observation that, if H < G and T is a transversal of the cosets of H,
then:

F(p) = Sum(g in G: f(g)p(g)) = Sum( t in T: p(t) * Sum( h in H: f(th)p(h) ) )

On the face of it, this offers no gain, but if p decomposes over H, then one
can
choose a basis of p such that p(h) is block diagonal for all h, and then there
are fewer matrix entries to consider in the inner sum.

This is applied along a chain of subgroups, and further work is done to choose
a transversal and basis in such a way that all the matrices p(t) are highly
sparse, giving further improvements.

Steve Linton

@book {MR96i:68001,
   AUTHOR = {Clausen, Michael and Baum, Ulrich},
    TITLE = {Fast {F}ourier transforms},
PUBLISHER = {Bibliographisches Institut},
  ADDRESS = {Mannheim},
     YEAR = {1993},
    PAGES = {ii+181},
     ISBN = {3-411-16361-5},
  MRCLASS = {68-02 (11Y16 20F16 65T20 68Q25)},
 MRNUMBER = {96i:68001},
   MRREVR = {V{\'\i}t{\u{e}}zslav Vesel{\'y}},
}
@article {MR94f:65129,
   AUTHOR = {Baum, Ulrich and Clausen, Michael and Tietz, Benno},
    TITLE = {Improved upper complexity bounds for the discrete {F}ourier
             transform},
  JOURNAL = {Appl. Algebra Engrg. Comm. Comput.},
 FJOURNAL = {Applicable Algebra in Engineering, Communication and Computing},
   VOLUME = {2},
     YEAR = {1991},
   NUMBER = {1},
    PAGES = {35--43},
     ISSN = {0938-1279},
    CODEN = {AAECEW},
  MRCLASS = {65T10 (20D60 65Y20)},
 MRNUMBER = {94f:65129},
}
@article {MR94a:20028,
   AUTHOR = {Clausen, Michael and Baum, Ulrich},
    TITLE = {Fast {F}ourier transforms for symmetric groups: theory and
             implementation},
  JOURNAL = {Math. Comp.},
 FJOURNAL = {Mathematics of Computation},
   VOLUME = {61},
     YEAR = {1993},
   NUMBER = {204},
    PAGES = {833--847},
     ISSN = {0025-5718},
    CODEN = {MCMPAF},
  MRCLASS = {20C40 (20C30 68Q40)},
 MRNUMBER = {94a:20028},
   MRREVR = {Stephen A. Linton},
}
@article {MR93d:20031,
   AUTHOR = {Baum, Ulrich},
    TITLE = {Existence and efficient construction of fast {F}ourier
             transforms on supersolvable groups},
  JOURNAL = {Comput. Complexity},
 FJOURNAL = {Computational Complexity},
   VOLUME = {1},
     YEAR = {1991},
   NUMBER = {3},
    PAGES = {235--256},
     ISSN = {1016-3328},
  MRCLASS = {20C40 (20C15 68Q40)},
 MRNUMBER = {93d:20031},
}
@article {MR91m:68100,
   AUTHOR = {Baum, Ulrich and Clausen, Michael},
    TITLE = {Some lower and upper complexity bounds for generalized
             {F}ourier transforms and their inverses},
  JOURNAL = {SIAM J. Comput.},
 FJOURNAL = {SIAM Journal on Computing},
   VOLUME = {20},
     YEAR = {1991},
   NUMBER = {3},
    PAGES = {451--459},
     ISSN = {0097-5397},
    CODEN = {SMJCAT},
  MRCLASS = {68Q40 (20C15)},
 MRNUMBER = {91m:68100},
}
@incollection {MR1235793,
   AUTHOR = {Clausen, Michael and Baum, Ulrich},
    TITLE = {Fast {F}ourier transforms for symmetric groups},
BOOKTITLE = {Groups and computation (New Brunswick, NJ, 1991)},
    PAGES = {27--39},
PUBLISHER = {Amer. Math. Soc.},
  ADDRESS = {Providence, RI},
     YEAR = {1993},
  MRCLASS = {20C40 (68Q40 68R05)},
 MRNUMBER = {1 235 793},
}