GAP Lesson 6

Change to the directory where you store your GAP files, and then start up GAP.

gap> LogTo("GAPlesson6");
gap> At:=KnownAttributesOfObject;

On the page where you accessed this lesson there is a link to a file called lesson6code. Save the file lesson6code in your filespace, with that name. The purpose of the following is simply to get that code entered into GAP in an economical way.

gap> Read("lesson6code");

The file lesson6code that you just read in contains three groups, and three functions images, righttransversal and gentable. We will come to the functions later. To find out what the groups are do:

gap> s4;
gap> gl32;
gap> m11;

Records

gap> k:=Group((1,2,3),(1,2));
gap> kinfo:=rec();
gap> kinfo.size:=6;
gap> kinfo;
gap> kinfo.name:="s3";
gap> kinfo;
gap> RecNames(kinfo);
gap> RecFields(kinfo);
gap> kinfo.size:=7;
gap> kinfo;

Discuss: What is the difference between a record and a list? Are there circumstances where we might prefer to set up a record rather than a list? Are there circumstances where we might prefer to set up a list rather than a record?

How GAP works: Stabilizer chains
References: ?Stabilizer Chains
Also: Chapter 8 of A.M. Cohen et al. (eds.), Some tapas of computer algebra, Springer-Verlag.
D.F. Holt, B. Eick, E.A. O'Brien, Handbook of Computational Group Theory, Chapman and Hall, Chapter 4.

gap> sc:=StabChain(s4);
gap> RecNames(sc);
gap> BaseOfGroup(s4);
gap> sc.orbit;
gap> sc.stabilizer;
gap> sc.stabilizer.orbit;
gap> sc.stabilizer.generators;
gap> Print(sc);

How many different 'top-level' fields are defined in the record sc?
How many different fields in the record sc are themselves records?

The following lines are optional. If you do them, discuss why GAP might want to set up structure with the properties exhibited by these lines.

gap> ksc:=StabChain(k);
gap> ksc.orbit:="garbage";
gap> At(k);
gap> scm:=StabChainMutable(k);
gap> RecNames(scm);
gap> scm.orbit:="garbage";
gap> scm.orbit;
gap> StabChainMutable(k).orbit;

At this point the terms base, strong generating set, and stabilizer chain will be defined. See the handout on stabilizer theory.

gap> m11sc:=StabChain(m11);

Exercises: a) Find the orbit lengths of the stabilizers of m11. Verify that their product is the size of m11.
b) What is the largest possible size that a permutation group can be that acts on 11 symbols and has a base of size 4? Is it (i) < |m11|, (ii) = |m11|, or (iii) > |m11|.
c) What is the smallest possible size that a permutation group can be that acts transitively on 11 symbols and has a base of size 4?

Because GAP seems to want to use [2,1] as a base for s4 if we do nothing about it, we are going to force the base to be [1,2] by doing

gap> s4sc:=StabChain(s4,[1,2]);
gap> Print(s4sc);

At this point we probably understand what the record fields labels, genlabels, stabilizer, orbit, and generators are, but check on this.

gap> Print(images);
gap> images(s4sc);

Explain what it is that images computes. Which field(s) of the record s4sc contain(s) the information that images produces? Explain why it is that 1 is sent to 1 by generator 1, but the first generator of s4 does not send 1 to 1.

Exercise: a) find an element of s4 that sends 1 to 4, expressing it as a word in the generators that appear in the list sc.generators. Observe how the labeling of the generators is done via lists translabels and genlabels (this is used in the code of images). Draw the trees that are encoded in s4sc.transversal and m11.stabilizer.transversal .

b) find an element of m11 that sends 1 to 1 and sends 8 to 7.

Next we recall how a right transversal to the stabilizer of a point is constructed. Examine the following code:

gap> Print(righttransversal);
gap> righttransversal(s4sc);
gap> s4sc.transversal;

Observe any differences and similarities between righttransversal and s4sc.transversal. What is going on?

gap> righttransversal(m11sc);

Observe that the transversal element in position i sends the first base element to i.
Exercise: Find the element of righttransversal(s4sc) that represents the same stabilizer coset as (1,4,6,3)(2,5).

Consider next the algorithm presented on the handout to test whether a permutation belongs to a group.
Exercise: does the permutation (1,4,5) belong to s4? Justify your conclusion.

We now study how GAP produces a list of elements of a group. Compare the two commands:

gap> righttransversal(s4sc.stabilizer);
gap> Elements(s4);

What similarity do you notice in the answers? How did GAP produce the list of elements? Did it use the same transversal that we computed?

We have seen how GAP produces transversals, but not how it produces generators for a stabilizer. Study Schreier's theorem on the handout. Study the following:

gap> Print(abstractrighttransversal);
gap> abstractrighttransversal(s4sc);

Compare the result of this with the tree we drew earlier.

gap> Print(gentable);
gap> gentable(s4sc);

Questions: a) Work out why the first entry in the generator table is what it is.
b) Express the second entry as a word in the generators that appear in s4sc.generators.
c) Work out why the second row of the table is what it is.

We now study Schreier transversals, and why they are a good idea. If a group has d generators and a subgroup of index h then a Schreier transversal produces h(d-1)i+1 elements that generate the subgroups. This number of elements is the minimum number that always works, and is needed for subgroups of free groups.