DFT-based word normalization in finite supersolvable groups
In this paper we discuss the word normalization problem in pc presented finite supersolvable groups: given two group elements a and b in normal form the normal form of the product a . b is to be computed. As an alternative to classical collection strategies we present a new DFT-based strategy, which uses fragments of certain irreducible representations of the underlying group. This strategy allows an explicit running time analysis. For example, in the special case of a pc presented p-group G of order p(n) one needs at most 5 . p . n(2) additions in Z(e) := Z/eZ for the computation of the normal form, where e denotes the exponent of G. Interpreting pc presentations as polynomials in multivariate non-commutative polynomial rings we derive an algorithm for fast polynomial division.
word normalization supersolvable groups discrete fourier transform power-commutator presentation