GAP Lesson 6

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

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

Save the file lesson6code in your filespace:

gap> Read("lesson6code");

The file lesson6code which you just read in contains three groups, and three functions images, righttransversal and gentable. We will come to the functions later. Do

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


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

What is the difference between a record and a list?

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.

gap> sc:=StabChain(s4);
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.

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 which 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 which 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. What commands are you going to use to answer this? Explain why it is that 1 is sent to 1 by generator 1, but neither the first generator of s4 nor the first generator in s4sc.generators sends 1 to 1.

Exercise: a) find an element of s4 which sends 1 to 4, expressing it as a word in the generators which 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 which are encoded in s4sc.transversal and m11.stabilizer.transversal .

b) find an element of m11 which 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 the difference between
righttransversal and s4sc.transversal.

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) which 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 which 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) elements which generate the subgroups. This number of elements is the minimum number which always works, and is needed for subgroups of free groups.