GAP

Main Branches

Downloads  Installation  Overview  Data Libraries  Packages  Documentation  Contacts  FAQ  GAP 3 

Condensation Techniques

By Jürgen Müller

See also: J. Müller, Computational representation theory. Remarks on condensation (dvi, ps, pdf), Lecture Notes, IEM, Universität Duisburg-Essen, 2003.

Condensation techniques are being used as one of the workhorses of computational representation theory, for both the analysis of given matrix or permutation representations and the explicit construction of matrix representations.

Formally, these techniques are explicit computational applications of suitable Schur functors, see e. g. [Green]: Let A be a finite-dimensional algebra over a field F, and let e be an idempotent in A. Then the corresponding Schur functor maps an A-module V to the eAe-module Ve, where the subset Ve of V is the image of the projection induced by e.

In the group algebra case A=FG, where G is a finite group, this is applied as follows: Let H be a subgroup of G such that the characteristic of F does not divide the order of H. Then

e = |H|−1h ∈ H h

is an idempotent in FG. The subset Ve of an FG-module V is the set of H-fixed points in V, hence this technique is called fixed point condensation.

Algorithms for fixed point condensation have been developed, implemented and used by various people, see e. g. [Müller] for a more detailed overview. In particular, the following applications underline the role of GAP as a valuable research tool:

Finding so-called faithful idempotents has been pursued in [Lux], where in particular the character tables and tables of marks libraries of GAP have been used. Fixed point condensation of induced modules has been described and implemented as GAP-code in [Müller-Rosenboom].

So-called direct condensation of permutation modules is based on the general computational task of enumerating large G-sets. Programs using the technique of distributed computing have been described in [Lübeck-Neunhöffer], where the overall implementation is as C-code, but certain precomputation programs are written as GAP-code. An application of direct condensation techniques is given in [Müller-Neunhöffer-Röhr-Wilson], where again both C-programs and GAP-programs are used. Enumeration of huge G-sets, together with applications, has been described in [Müller], where the latter programs are written completely as GAP-code.

Typically, the GAP-parts of the above-mentioned implementations make use of the basic data structures and arithmetical features of GAP, such as permutations or vectors and matrices over small finite fields, and the possibility to handle them efficiently and manipulate them easily. These specially tailored programs are not part of the official GAP-distribution, and for more details the reader is referred to the various authors.

References

[Green] J. Green: Polynomial representations of GLn, Lecture Notes in Mathematics 830, Springer, 1980.

[Lübeck-Neunhöffer] F. Lübeck, M. Neunhöffer: Enumerating large orbits and direct condensation, Experiment. Math. 10, 2001, 197--205.

[Lux] K. Lux: Algorithmic methods in modular representation theory, Habilitationsschrift, RWTH Aachen, 1997.

[Müller] J. Müller: On endomorphism rings and character tables, Habilitationsschrift, RWTH Aachen, 2003.

[Müller-Neunhöffer-Röhr-Wilson] J. Müller, M. Neunhöffer, F. Röhr, R. Wilson: Completing the Brauer trees for the sporadic simple Lyons group, LMS J. Comput. Math. 5, 2002, 18--33.

[Müller-Rosenboom] J. Müller, J. Rosenboom: Condensation of induced representations and an application: the 2-modular decomposition numbers of Co2, in: Proc. of the Euroconference on computational methods for representations of groups and algebras, Essen, 1997, 309--321, Progr. Math. 173, Birkhäuser, 1999.