Based on Steve Linton's talk at the Second CoDiMa Training School in Computational Discrete Mathematics (ICMS, Edinburgh, 17-21 October 2016, https://www.codima.ac.uk/school2016/)

- GAP has two somewhat contradictory design goals
- to allow users to pose questions in a way that seems natural to a working mathematician and get answers
- to allow the expert computational mathematician to implement and apply the most advanced techniques to solve hard problems

- The first is achieved to a limited extent.

**Motivating problem:** find an element of $S_9$ which is NOT an involution

In [1]:

```
Filtered(Elements(SymmetricGroup(9)), x-> x*x <> ())[1];
```

Out[1]:

- Replace 9 by 10 and it is already visibly longer

In [2]:

```
Filtered(Elements(SymmetricGroup(10)), x-> x*x <> ())[1];
```

Out[2]:

- Put
`n:=15`

and you quickly run out of memory: $15!$ is roughly $1.3 \times 10^{12}$

- Of course GAP is capable of doing the latter calculation
- But you need to acquire certain expertise to ask questions in the right way
- This talk is about how to start thinking like an expert

```
n:=9;; Filtered( Elements(SymmetricGroup(n) ),
x-> x*x <> () )[1];
```

- First this computes and stores the full list of elements of $S_n$
- Then it checks each of them to see if it has order 2
- It stores a second list of all of those which don’t
- Finally it returns the first one

- Instead, we can stop looking when we find one. GAP even provides a built in function to do this:

In [3]:

```
First(Elements(SymmetricGroup(9)), x-> x*x <> ());
```

Out[3]:

- Stopping things as soon as possible is an important principle
- In this case, however, the real problem is computing and storing all the elements of $S_n$
- Let's explore some other alternatives

`Enumerator`

returns a list of elements of a domain- this list may be virtual
- also
`EnumeratorSorted`

— but only if you need it

- For many objects it is quick to construct, but may be slower to access

In [4]:

```
# Do not remove the 2nd semicolon below yet
# See https://github.com/gap-packages/JupyterKernel/issues/72
e := Enumerator(SymmetricGroup(99));;
```

In [5]:

```
Length(e);
```

Out[5]:

In [6]:

```
e[10^100];
```

Out[6]:

See also `EnumeratorOfTuples`

and `EnumeratorOfCombinations`

(both documented) and `EnumeratorOfCartesianProduct`

(currently undocumented)

- Even an Enumerator can be too heavyweight
- sometimes you don’t need to even number the elements, or know how many there are

- For this GAP has
*Iterators*`IsDoneIterator`

and`NextIterator`

operations

In [8]:

```
n := 9;; i := Iterator(SymmetricGroup(n));;
```

In [9]:

```
while not IsDoneIterator(i) do
x := NextIterator(i);
if x*x <> () then
break;
fi;
od;
```

In [10]:

```
x;
```

Out[10]:

Or more concisely, thanks to some built-in magic:

In [12]:

```
n := 9;;
for x in SymmetricGroup(n) do
if x*x <> () then
break;
fi;
od;
```

In [13]:

```
x;
```

Out[13]:

Or even shorter:

In [15]:

```
n := 9;; First(SymmetricGroup(n), x->x*x <> ());
```

Out[15]:

- Sometimes you can’t even make an iterator for your group easily, but you know the elements you want exist and are not too rare
- So make pseudo-random elements of the group until you find one

In [16]:

```
g := SL(10,3);
```

Out[16]:

In [17]:

```
repeat
x := PseudoRandom(g);
until Order(x) = (3^10-1)/2;
```

In [18]:

```
x;
```

Out[18]:

In [19]:

```
Display(x);
```

- Element order is a conjugacy invariant
- For many groups there are ways of finding conjugacy class representatives that are faster than listing all elements
- or they might be already known and stored

In [21]:

```
n := 9;;
Representative(First(ConjugacyClasses(SymmetricGroup(n)),
c->Representative(c)^2 <> ()));
```

Out[21]:

- This is one of the most powerful techniques, especially for non-abelian simple groups and things close to them
- Of course if you are really working in $S_n$ you can simply construct the answer as a permutation

In [22]:

```
First(SymmetricGroup(11),
x-> OnTuples([1,2,3,4,5],x) = [1,3,5,7,9] and
Order(x) = 7);
```

Out[22]:

- For values larger than 12, this gets slow
- because it searches lots of elements that fix 2 before it looks at anything that moves 1 to 2

- Use a bit of maths
- the elements that maps
`[1,2,3,4,5]`

to`[1,3,5,7,9]`

lie in a coset of a sequence stabilizer

- the elements that maps

In [24]:

```
g := SymmetricGroup(12);; s := Stabilizer(g,[1,2,3,4,5],OnTuples);;
```

In [25]:

```
r := RepresentativeAction(g,[1,2,3,4,5],[1,3,5,7,9],OnTuples);
```

Out[25]:

In [26]:

```
First(s,x->Order(x*r) = 7)*r;
```

Out[26]:

- Don’t write down the list of elements first
- Stop when you’ve found it
- Stop looking at other elements as soon as you know they’re not it
- order of a matrix can be large and a bit slow to compute
- if all you care about is whether it is 2, just check for
`IsOne(x*x) and not IsOne(x)`

- Try to identify a subgroup, or coset or conjugacy class that it lies in
- remember Sylow subgroups!
- automorphism group sometimes helps too

- Search only in there

- Even worse — quite small groups can have very many subgroups
- Some kinds that are eas(ier) to find
- Cyclic subgroups (via
`ConjugacyClasses`

) `NormalSubgroups`

- Derived, Lower Central etc. series
- Sylow subgroups
- ...

- Cyclic subgroups (via

- Some kinds that are eas(ier) to find
- ...
- Maximal subgroups (for some groups)
`MaximalSubgroups`

will return all subgroups. You are likely to want ony`MaximalSubgroupClassReps`

- Ask yourself if one of these lists might include the one you want, or at least help you on your way

**Conjecture:** $U_3(3)$ cannot be generated by three involutions

In [27]:

```
g := PSU(3,3);
```

Out[27]:

- list all 216G triples of elements of $U_3(3)$ and filter out all the ones that generate the group and consist of involutions
- use
`IteratorOfTuples`

to run through all 216G ... - use
`IteratorOfCombinations`

to run through 36G of unordered triples - the same, but test for involutions first
- would take a few hours on a laptop

- find the involutions first (there are just 63 of them) and run over triples

In [28]:

```
invs := Filtered(g, x -> IsOne(x*x) and not IsOne(x));;
```

In [29]:

```
Length(invs);
```

Out[29]:

In [32]:

```
iter := IteratorOfCombinations(invs,3);; ct := 0;;
while not IsDoneIterator(iter) do
x := NextIterator(iter);
if Subgroup(g,x) = g then
break;
fi;
ct := ct+1;
od;
```

In [33]:

```
ct;
```

Out[33]:

In [34]:

```
Binomial(63,3);
```

Out[34]:

- We still haven’t used conjugacy
- Could choose the 1st involution to be a conjugacy class representative
- there is only one conjugacy class of involutions
- reduce search from
`Binomial(63,3)`

to`Binomial(62,2)`

- The 2nd involution can be chosen up to conjugacy in the centraliser of the first one
- just 4 cases to consider, so the search is now $4 \times 61$ cases

- Of course the 3rd one can be chosen up to conjugacy in the normaliser of the subgroup generated by the first two
- If the things you are searching for are not all the same, then the order in which you look at them also matters

- This type of search for sequences of elements that generate something is nicely implemented by Alexander Hulpke in a part of the GAP library called
**Morpheus** - There are various functions that access morpheus documented in the library under "Searching for Homomorphisms"
- Our example is asking whether $U_3(3)$ is a quotient of the free product of three cyclic groups of order 2

In [35]:

```
g:=PSU(3,3);;
```

In [36]:

```
F:=FreeGroup(3);
```

Out[36]:

In [37]:

```
F:=F/[F.1^2,F.2^2,F.3^2];
```

Out[37]:

In [38]:

```
GQuotients(F,g);
```

Out[38]:

In [39]:

```
F:=FreeGroup(2);
```

Out[39]:

In [40]:

```
F:=F/[F.1^2,F.2^6];
```

Out[40]:

In [41]:

```
qs:=GQuotients(F,g);
```

Out[41]:

In [42]:

```
Length(qs);
```

Out[42]:

- So $U_3(3)$ is (2,6)-generated in two distinct ways
- Presented as homomorphisms — easy to recover the generators if you want them
- Other Morpheus functions:
`AllHomomorphisms`

,`AutomorphismGroup`

,`IsomorphicSubgroups`

- A powerful tool for many purposes

- Mathematicians are very sloppy: they constantly identify isomorphic groups
- So $A_5$ "is" $PSL(2,5)$ and $SL(2,4)$ and $\langle a,b \mid a^2=b^3=(ab)^5=1 \rangle$ and $\langle (1,3,6,2,4), (1,2,3)(4,5,6) \rangle$
- Computationally these are different, so you must choose the right one to work in
- Two tools for moving between them: homomorphisms and straight-line programs

- Lots of functionality in GAP for fp groups — mostly to do with identifying unknown ones
- Lots of textbooks that define groups by presentations, e.g. $$D_{2n} = \langle a,b \mid a^n = (ab)^2 = b^2 = 1 \rangle $$
- GAP supports some general group theoretic computation with fp groups that turn out to be finite
- But it’s usually the wrong way to do things

In [43]:

```
f := FreeGroup("a","b");
```

Out[43]:

In [44]:

```
AssignGeneratorVariables(f);
```

In [45]:

```
g := f/[a^2,b^3,(a*b)^7, Comm(a,b)^8];
```

Out[45]:

In [46]:

```
Sum(Elements(g), Order);
```

Out[46]:

In [47]:

```
x := Random(g);
```

Out[47]:

In [48]:

```
Print(x);
```

In [49]:

```
g := f/[a^2,b^3,(a*b)^7, Comm(a,b)^8];
```

Out[49]:

In [50]:

```
phi := IsomorphismPermGroup(g);
```

Out[50]:

In [51]:

```
Print(phi);
```

In [52]:

```
h := ImagesSource(phi);
```

Out[52]:

In [53]:

```
Sum(Elements(h), Order);
```

Out[53]:

In [54]:

```
x := Random(h);
```

Out[54]:

In [55]:

```
y := PreImagesRepresentative(phi,x);
```

Out[55]:

In [56]:

```
Print(y);
```

**Other Isomorphism Constructors**

`Isomorphism[Special]PcGroup`

- pcgroups are usually the fastest representation for solvable groups

`IsomorphismFpGroup`

- basically only if you want a presentation of your group

`SmallerDegreePermRep`

- heuristic

- GAP will sometimes do this for you
- see
`?NiceMonomorphism`

or`?NiceObject`

- but it can be better to do it by hand

- see

- Part of general mapping (relation) machinery
`Source`

and`Range`

(domain and codomain)- given when the morphism is constructed
- morphism does not need to be total or onto, so they may be bigger than you expect
`ImagesSource`

and`PreImagesRange`

may be what you want

`Image`

specialised to`ImageElm`

and`ImagesSet`

- which don’t check that the input is in the source

`PreImagesRepresentative`

gives just ONE preimage`InverseGeneralMapping`

`CompositionMapping`

In [57]:

```
g:=Group((1,2,3,4),(1,2),(5,6,7));
```

Out[57]:

In [58]:

```
iso:=IsomorphismPcGroup(g);
```

Out[58]:

In [59]:

```
h:=Image(iso);
```

Out[59]:

In [60]:

```
z:=Centre(h);
```

Out[60]:

In [61]:

```
SetCentre(g,PreImage(iso,z));
```

In [62]:

```
cl:=ConjugacyClasses(h);
```

Out[62]:

In [63]:

```
ncl:=[];
```

Out[63]:

In [64]:

```
for c in cl do
nc:=ConjugacyClass(g,PreImage(iso,Representative(c)));
SetSize(nc,Size(c));
SetStabilizerOfExternalSet(nc, PreImage(iso,StabilizerOfExternalSet(c)));
Add(ncl,nc);
od;
```

In [65]:

```
List(ncl,Size);
```

Out[65]:

In [66]:

```
SetConjugacyClasses(g,ncl);
```

- Even if you can’t find an isomorphism to a nicer group, you may be able to find a homomorphism
- Solve your problem in the image first and refine

In [67]:

```
g := Group((1,2),(3,4),(5,6),(7,8),(9,10,11),(11,12,13));
```

Out[67]:

In [69]:

```
Number(g, x-> Order(x) mod 2 = 1); Size(g);
```

Out[69]:

Out[69]:

In [70]:

```
Orbits(g,MovedPoints(g));
```

Out[70]:

In [71]:

```
phi := ActionHomomorphism(g,[1..8]);
```

Out[71]:

In [72]:

```
Print(phi);
```

In [73]:

```
h := ImagesSource(phi);
```

Out[73]:

In [74]:

```
odds := Filtered(h, x->Order(x) mod 2 = 1);
```

Out[74]:

In [75]:

```
p := PreImagesSet(phi,odds);
```

Out[75]:

In [77]:

```
Length(p); Number(p, x->Order(x) mod 2 = 1);
```

Out[77]:

Out[77]:

- If you just make a
`GroupHomorphismByImages`

(by giving images of generators)- it can be slow to make because it checks (use
`GroupHomorphismByImagesNC`

if you are sure you are right) - Image and preimage computation can be slow, or preimages can be “nasty” (long words in FP group)
- essential because factorisation in terms of generators is not always easy

- it can be slow to make because it checks (use
`ActionHomorphism`

is usually good- So are most things produced by
`IsomorphismXXXGroup`

Avoid long lists of mutable objects

- since the objects in the list might change “under its feet” the list can’t remember
- whether it’s sorted
- whether the entries are all from the same family

- so whenever you try and search it or call an operation on it, it has to look at every element
- can become very slow

- lists of immutable objects are much better
- sorted lists of immutable comparable objects can use binary search

- There are space and time efficient representations of vectors and matrices over finite fields
- up to order 256 in the kernel
- bigger fields in package
`cvec`

- Vectors and matrices are not always in these representations by default
- among other reasons because deciding whether this vector is “really” over GF(3) or GF(9) requires prescience

`ConvertToVectorRep(v, q)`

and`ConvertToMatrixRep(m,q)`

convert in place`cvec`

has its own functions- working with large uncompressed vectors or matrices is a bad idea

- A lot of this talk was taken from Alexander Hulpke’s talk “Using GAP”, especially section 4
- You can read the original paper by Alexander Hulpke at http://www.math.colostate.edu/~hulpke/paper/gap4tut.pdf
- A lot of similar ideas are found in Steve Linton's paper "The Art and Science of Computing in Large Groups" (in Bosma & van der Poorten: Computational Algebra and Number Theory, 1995, Springer)