TGroup class

One of the foundational classes in Group Explorer is the TGroup class, because it is the program's internal representation of a group.  For that reason, the technical documentation of this website should address the implementation of that class, and so we do so here.

Listed below are the important/interesting member functions for this class, and a discussion of the algorithms that implement them.  Some are discussed informally, others with pseudocode.  The functions are separated into categories: input/output, group operations, group generation, and special subgroups.

The most interesting functions are those in the group generation section.  Note that the TCayleyDiagram class page also reveals some interesting internal workings of Group Exlporer (specifically, how Cayley diagrams are auto-generated).

Input/output

function getEltRepresentation (e : TGroupElt) : String;

A group contains several ways to represent its elements, each of which is loaded from the .gp file that defines the group.  At any moment, a TGroup object has one of these representations flagged as the active one.  Calling getEltRepresentation(e) applies that representation function to the group element e and returns the string representation it yields.

Although the group author can define representations several ways (see the Group Authoring page), Group Explorer stores them all internally as a table and does a linear lookup.  Although a hash would be better, all these groups are small, so the time savings is not crucial.

procedure loadFromFile (Ini : TIniFile);

Calls functions from GroupParsing.pas to read and parse information from a .gp file.  The TIniFile class is a Borland Delphi class which reads all settings in a text file of the appropriate format into a data structure in memory, so that they can then be accessed in any order (rather than in the linear order of the file).  Group Explorer adopts the .INI file format for its .gp files (see the Group Authoring page), and so this loadFromFile procedure can simply ask, for each piece of information it needs to build a group, whether that information exists in the data structure Ini that is the parameter.

Pieces of information this routine extracts from the file are listed here.  Note that no pictures or shapes are discussed, because that is the purvey of a TVisualGroup object.

1. Names for the group in plain text
2. Name of group author in plain text
3. Factors that product to form the group, if the group is defined that way (see the Group Authoring page)
4. At least one set of generators for the group (or for each factor)
5. At least one representation for the group (or for each factor)

While reading a list of generators for the group, it ensures that each is a member of the same permutation group S_n.  While reading different lists of generators for the same group, it ensures that each list generates the same subgroup of S_n.

Group operations

function groupOp (e1, e2 : TGroupElt) : TGroupElt;

This function returns the value of e₁ * e₂ in the group.  The elements e1 and e2 are stored as indices into S_n (numbers between 0 and n!-1) and the class TPermutation is used to covert those indices into permutations and to compose them.

function groupInv (elt : TGroupElt) : TGroupElt;

This function returns the value of elt^-1 in the group.  The element elt is stored as an index into S_n (a number between 0 and n!-1) and the class TPermutation is used to covert that index into a permutation and to invert it.

function groupConjugate (e1, e2 : TGroupElt) : TGroupElt;

This functions returns the conjugate of e2 by e1, that is e₁ * e₂ * e₁^-1, by performing groupOp(e1,groupOp(e2,groupInv(e1))).

function elementOrbit (e : TGroupElt) : TGroupElts;

This function returns an array of elements that are the orbit of the element e.  That is, they are the powers e⁰, e¹, e², ... up to e^n-1, where n is the smallest positive power of e that equals the identity element in the group.  The algorithm for computing this is simply a linear loop that generates successive powers of e until it finds the identity.  The TPermutation class is again used to simulate the group operation.

function elementOrder (e : TGroupElt) : TGroupElt;

This function returns the smallest positive number n such that eⁿ is the identity element of the group.  The TPermutation class contains a member function for determining the order of a permutation by repeated composition, and this function simply calls that one.

Group generation

function subgroupGeneratedBy (elts : array of TGroupElt) : TGroupElts;

This function turns a set of generators elts into a complete list of the elements of the subgroup generated by those elements.  This function is useful when checking to see if a .gp file is well written (i.e. all generator lists generate the same group) and when highlighting different subgroups when editing a Cayley diagram or editing a Multiplication table.  We include commented pseudocode for the algorithm that implements this function here.  Its running time is mn, where m is the size of the array elts, and n is the size of the resulting subgroup (bounded above by the size of the whole group).

// begin with a copy of the generators:
group := copy of elts;

// loop through every element we've found so far:
for each element g in the array group do {
  // (this loop over g will get longer as we add new elements, below)

  // loop through every generator we were given, and use each one on g:
  for each generator h in the array elts do {

    newguy := groupOp(g,h);
    // if we have generated another element, add it to our running list:
    if newguy not already in group then append newguy to group;
    // g will eventually be that new element later in the outer loop
  }

}
// group is the final result

function subgroupToGenerators (elts : array of TGroupElt) : TGroupElts;

This function is the converse of subgroupGeneratedBy, in that it accepts an array of group elements which form a subgroup, and it creates a set of generators for that subgroup.

It begins by ensuring that the array elts is in an order that makes it a sublist of the list of all elements in the group.  That is, if we let G stand for the list of all elements in the group, G := subgroupGeneratedBy(any list of group generators), then whenever elts[i1] = G[i2] and elts[j1] = G[j2] then we have i1 < j1 if and only if i2 < j2.  We do this to ensure that we find pretty generators sooner than ugly ones.  That is, most often the group representation the user is seeing gives representations like a and b to generators of the group, and representations like aaba to non-generators.  Thus if we ensure that elts is sorted the same way as the current generation scheme for the whole group, we stand a better chance of selecting subgroup generators that have simpler representations.

After re-sorting elts to fit this criterion, the algorithm then proceeds to find generators for elts as shown in the following commented pseudocode.

// initialize currentgenerators (eventually our answer) to empty,
// and the set of things it generates is also therefore empty:
currentgenerators := empty list;
currentsubgroup := empty list;

// loop until we build up the whole currentsubgroup to equal elts:
while currentsubgroup < elts do {

  // try the first thing in elts to see what it generates:
  highest := elts[0];
  append highest to currentgenerators;
  currentsubgroup := subgroupGeneratedBy(currentgenerators);

  // now search all of elts for something that generates even more:
  for each g in elts do {
    change last element of currentgenerators to g;
    tempsubgroup := subgroupGeneratedBy(currentgenerators);

    // if we find something that generates more, remember it:
    if tempsubgroup > currentsubgroup then {
      currentsubgroup := copy of tempsubgroup;
      highest := g;
    }

  }

  // keep the generator that did the most:
  change last element of currentgenerators to highest;
  // and now restart the main loop, to see if we're done or not
}

The reason we try to find the generator that makes the largest increase in the size of the subgroup each time through the main loop is to avoid picking out powers of such generators.  That is, it would be bad if trying to generate a cyclic subgroup of order 4, to choose the square of the generator.  One is guaranteed this way to produce a minimal-length set of generators, because if there were a shorter set of generators, at least one of them would have to be stronger (i.e. generate more) than one of the ones we selected, which is not possible.  (This is, of course, only a hint at a proof.)

function potentGens (gs : TGroupElts) : integer;

Is the full list gs of generators for a subgroup necessary, or are some redundant?  That is, if gs has 4 entries, perhaps gs[0], gs[1], gs[2] would generate the whole group and gs[3] is superfluous.  Knowing the answer to this question is important when trying to make a Cayley diagram from the given generators, and trying to determine how many dimensions it will have visually.

This function returns the highest integer i such that generator g[i] is necessary.  That is, the highest integer i such that g[0], ..., g[i-1] is not the same subgroup as g[0], ..., g[i].  The algorithm is simply to iterate i beginning at 0 and stopping when the generators have run out, or when g[0], ..., g[i] generates the same subgroup as g[0], ..., g[i+1].

function orbitGrid (elts : array of TGroupElt) : TGroupElts; overload;

This routine is half of the inner workings that auto-generate Cayley diagrams; the other half is the makeFromGroup function.  This routine is entirely too fraught with careful handling of minutiae for me to document it in full.  Rather, I will give an basic understanding of what a routine like this one must do, and then discuss some of the other details that need to be cared for.

Priorities

Consider the rectangular Cayley diagrams for S₃.  There are essentially two of them, although they can be oriented differently in space based on axis assignments.  The difference is the priority of the generators, which is the main concern of orbitGrid.

Cayley diagram for S3 with generator f (shown in blue lines) given lower priority (more local effects).

Cayley diagram for S3 with generator r (shown in red arrows) given lower priority (more local effects).

We will compare the generations of these grids as a way to understand how orbitGrid works.  But first note that describing this algorithm in terms of diagrams is deceptive, because all this processing takes place only in memory, and not in Euclidean three-space.  The makeFromGroup routine mentioned above is what assigns locations to each element of the grid.  However, it's convenient to speak in terms of diagrams so that the reader has a reference for what the text is talking about.

The grid of elements in the left picture was generated by beginning first from the identity (shown with a gray halo) and generating the subgroup < f >.  Then one red arrow was followed from the identity to the top center, and the generator f used to create the next column.  Then one red generator was followed from the top center to the top right, and the generator f used to create the rightmost column of elements.  The higher priority element r connects larger pieces of the diagram, and the lower priority element f connects local pieces of the diagram.  This caused the bottom row of red arrows to not be flowing the same way as the top row, but it kept the blue-line-connected pieces identical.

Now consider the picture on the right.  This was created using the generators in opposite priority.  First, the top row was generated using r, and then the blue line for f was followed from the identity to find the next place to start an r-orbit.  This arrived at the lower left portion of the grid, and from there the red arrow r was followed again until it returned upon itself.  This caused the r-triads in the diagram to be identical, but for the blue-line-connected portions of the diagram to be different shapes/orientations.

Other concerns

Given such a simple Cayley diagram as the one above, it may seem straightforward to write the orbitGrid algorithm.  Indeed, if all groups were as simple as S₃, it would be straightforward.  However, there are several features of more complex groups that require orbitGrid to be a bit more sophisticated.

1. This algorithm, naively implemented, only generates elements of the form aⁿb^m, for generators a and b and positive integers n and m.  This does not always reach every element of a group.  When it does not, orbitGrid needs to notice, and start a new grid from a new point, then "concatenate" the two grids in some intelligent way.
2. Concatenating two grids (as mentioned in point 1.) is often straightforward, because they are of identical dimensions, and therefore together form a one-higher-dimensional structure.  Or maybe one of the grids is one dimension higher than the other, and so the smaller can just be appended as a new element in the latter.  But this will not always be so, depending on the complexity of the group and the choice of generators.  In such cases, the grids may need to be fluffed with empty space to ensure they can be glued together.  (For example, open the group S₄ and change to generators < (1 2), (2 3), (3 4) >, then open a rectangular solid Cayley diagram.)

Special subgroups

The functions in this section compute subgroups of a group.  They are used by the Edit Cayley Diagram and Edit Multiplication Table dialog boxes, which allow users to pick out subgroups like the ones mentioned below for highlighting.

function Center : TGroupElts;

The group's center is the set of all elements that commute with every element of the group.  Thus the algorithm for finding the group's center is simply a quadratic search through all pairs of group elements, as shown in the pseudocode below.

// start with center empty, and search for elements to add:
center := empty list;
for each element g in the group do {
  // let's assume it belongs to the center, then search for counter-evidence:
  belongstocenter := true;

  // if any element h can be found to not commute with g, then it doesn't belong:
  for each element h in the group do
    if groupOp(g,h) <> groupOp(h,g) then belongstocenter := false;

  // if no evidence turned up to remove g from the center, toss it in:
  if belongstocenter then append g to center;
}

This algorithm could be made more efficient by stopping the inner loop as soon as belongstocenter became false, but since GroupExplorer currently deals with small groups, this is not a large concern.

function CommutatorSubgroup : TGroupElts;

The commutator subgroup of a group is the subgroup generated by all elements that are the commutator of any two elements.  For two elements a and b, their commutator [a,b] is defined to be aba^-1b^-1.  Thus the commutator subgroup can be written as { [a,b] | for a,b in G }.  A simple algorithm for finding the commutator subgroup is therefore to find all commutators by a quadratic listing of all pairs of elements of the group, and then generate a subgroup from them.  That is the algorithm used by Group Explorer.

function CentralizerOf (elt : TGroupElt) : TGroupElts;

The centralizer of an element is the largest subgroup such that all of its elements commute with the given element.  This is equivalent to saying that the centralizer of an element is everything that commutes with it.  This subgroup can be found by a simple linear search through the elements of the group, for each one adding it to the result only if it commutes with the given element.  This is the algorithm Group Explorer uses.

function ConjugateSubgroup (subg : TGroupElts; elt : TGroupElt) : TGroupElts;

The conjugate of a subgroup H by an element g is the subgroup gHg^-1.  Being able to compute such a thing is useful for testing whether a subgroup is normal, because normal subgroups have the property that their conjugate with any element is the normal subgroup itself.  To compute the conjugate of a given subgroup by a given element, one simply loops through the elements of the subgroup, and conjugates each one by the given element, using the subroutine groupConjugate from the group operations section, above.  Thus this algorithm runs in time proportional to the size of the given subgroup.

function NormalizerOf (subg : TGroupElts) : TGroupElts;

The normalizer of a subgroup is the largest subgroup of the whole group in which the given subgroup is normal.  This is equivalent to saying that the normalizer of a subgroup is all elements such that conjugating the subgroup by that element gives the same subgroup as a result.  Thus the normalizer of a subgroup H can be found by examining each element g of the group and testing whether gHg^-1 = H.  If they are equal, include g in the answer; otherwise, do not.  This is the algorithm Group Explorer uses, calling ConjugateSubgroup as a subroutine, and it therefore runs in time mn, where m is the size of the subgroup and n is the size of the whole group.