5
$\begingroup$

How does GAP (or Magma, Maple, ...) compute the centralizer of an element in a group? What about the center of a group?

I'm interested in semidirect products, so probably there are simpler answers in this case.

I'm sorry if this question is not be appropriate for this website. Thanks anyway!

  • 0
    Rod: For your last question, I would hope that GAP does not compute the centre by intersecting all of the centralizers! In permutation groups (and I think the situation is similar in polycyclic groups), computing the centre is known to be polynomial, whereas computing the centralizer of an element is probably not - it is at least as hard as graph isomorphism.2011-06-14

1 Answers 1

8

Algorithms depend in an essential way on data-types. How are your groups represented?

Semi-direct products

A semi-direct product could be represented as a triple (H, K, φ) where H, K are well-known groups and φ is a well-studied homomorphism from H to Aut(K). In this case, an element (h, k) lies in the center if and only if:

  • h is centralized by H: (x, 1) ⋅ (h, k) = (xh, k) and (h, k) ⋅ (x, 1) = ( hx, φ(x)(k) ), so xh = hx for all x in H
  • k is centralized by φ(x) as above
  • φ(h) = Id: (h, k) ⋅ (1, x) = (h, kx) and (1, x) ⋅ (h, k) = ( h, φ(h)(x) k), so kx = φ(h)(x) k for all x, so φ(h)(x) = kxk−1, and φ(h) is conjugation by k−1.
  • If h = 1, then k is centralized by K, since (1, k) ⋅ (1, x) = (1, kx) and (1, x) ⋅ (1, k) = (1, xk)

In the other direction, if h in Z(H) ∩ ker(φ), and k in Z(K) ∩ CK(φ(H)), then (h, k) is in the center. Clearly any such h determines a central (h,1), and any such k determines a central (1,k), and so their product (h, k) is also central.

If K is abelian, then this is also necessary. If K is not abelian, then I believe one takes φ−1(Inn(K)), being careful to remember the k such that h = φ−1( conjugation by k−1)

To compute this then you have to be able to find the center of H, the center of K, the kernel (or preimage) and image of φ, and then two intersections (with at least one subgroup normal). Assuming H, K, φ are well understood, then you can do this, but in general those problems may be just as hard.

GAP

In GAP, groups are represented (roughly in order of efficiency) as polycyclic groups, permutation groups, matrix groups, and finitely presented groups.

Finite polycyclic groups are represented using SpecialPCGS (polycyclic generating systems) which is a data-type that fairly directly displays most relevant information about the group. These are described in Cannon–Eick–Leedham-Green (2004) and calculated in GAP'slib/pcgsspec.gi. The center is calculated from these as an iterated centralizer, using the idea that the center of the group is contained in the center of the Fitting, and centralizes some minimal modules. This is in GAP'slib/grppcatr.gi. Infinite polycyclic groups are represented using less specialized PCGS, but the methods are similar, and are in GAP'spkg/polycyclic/gap/pcpgrp/fitting.gi.

Permutation groups are represented using a base and strong generating system (also called stabilizer chains). These allow one to efficiently write down any permutation as a product of generators and define canonical coset representatives for subgroups in the stabilizer chain. It is very similar to "cleaning" a vector giving a semi-echelon basis of a vector space. An algorithm of Beals–Seress (1992) is used (see Seress (2003)) and is in GAP'slib/grpprmcs.gi.

Matrix groups are currently an area of active research. One should decompose the group using Aschbacher's structure theorem, and then the center can be computed. As far as I know this is not implemented in mainstream GAP and only partially implemented in magma. Basically, one expresses the group as a composition of well understood groups whose centers can be written down. In practice, GAP computes a permutation representation by finding a vector or projective point with a short orbit, and computing in the resulting permutation group.

Finitely presented groups typically have no algorithms in the traditional sense (of being terminating and correct). Special cases such as free products and direct products (and their combinations, graphs of groups), I believe have methods to express the center of the whole based on centers of the factors. In GAP, a successful center calculation almost surely comes from the group being finite and represented internally using permutations or being polycyclic and represented (explicitly I believe) as a polycyclic group.

  • Cannon, John J.; Eick, Bettina; Leedham-Green, Charles R. Special polycyclic generating sequences for finite soluble groups. J. Symbolic Comput. 38 (2004), no. 5, 1445–1460. MR2168723 DOI:10.1016/j.jsc.2004.05.003

  • Seress, Ákos. Permutation group algorithms. Cambridge Tracts in Mathematics, 152. Cambridge University Press, Cambridge, 2003. x+264 pp. ISBN: 0-521-66103-X MR1970241 Google:books

  • 0
    Wow! Thanks a lot for your great answer. I'll check these references and GAP.2011-06-14