How do Gap generate the elements in permutation groups?

Question

I understand that permutationgroups in Gap are represented by generators, which seems to be far more efficient than groups represented by all it's elements, but how could then for example

gap>Elements( Group( (1,2,3,4,5,6,7,8),(1,2) ) );

so fast list all $8!$ elements of $S_8$? Can someone describe the algorithm or the method used?

Answer 1

Alex's answer is very good, but I'd like to add a somewhat simplified explanation of the Schreier-Sims Algorithm, since @Lehs asked for it.

I want to emphasis that this is not the actual Schreier-Sims algorithm but it contains the essential ideas in the Schreier-Sims algorithm, and I think it will serve to illustrate why it is preferable to the brute force exhaustive algorithm.

I will try to describe this not the Schreier-Sims algorithm using an example.

Let $G$ be the group generated by the permutations: $$a=(2\ 3),\quad b=(1\ 2\ 3)(4\ 5).$$ We will use not the Schreier-Sims Algorithm to find the size of this group. This is a bit simpler than finding the actual elements of the group.

We require two concepts:

• the orbit of a point $\alpha$ under the action of a group $G$ on a set $\Omega$ is the set $$\alpha \cdot G = \{\alpha\cdot g\in \Omega : g \in G\}.$$ In the example above: $1\cdot G =\{1, 2, 3\}$.
• the stabliser of a point $\alpha$ under the action of a group $G$ is the subgroup $$G_{\alpha} = \{g\in G: \alpha \cdot g = \alpha\}.$$ In our example, $G_1 = \langle (2\ 3), (4\ 5)\rangle$.

By the Orbit-Stabilizer Theorem, $|G| = |\alpha \cdot G|\cdot |G_{\alpha}|$, i.e. the size of $G$ is the size of the orbit of $\alpha$ multiplied by the size of the stabiliser of $\alpha$. This is also important, and we will use this later.

But how do we calculate the stabiliser? One way (bad!) would be to enumerate all of the elements of $G$ and check which elements fix $1$. Another way (good!) is to use the following lemma:

Schreier's Lemma. If $G$ is generated by a set $X$ and $G$ acts on a set $\Omega$, then $$G_\alpha = \langle u_ixu_j^{-1} : 1\leq i, j\leq n, x\in X, \alpha_i \cdot x = \alpha_j\rangle$$ where $\alpha\cdot G = \{\alpha_1, \alpha_2, \ldots, \alpha_n\}$.

In other words, if you keep track of what maps what to what when enumerating the orbit of $\alpha$, then you get a generating set for the stabiliser for free (more or less).

Returning to our example $$ 1\cdot G = \{1, 2, 3\}\quad G_1 = \langle (2\ 3), (4\ 5)\rangle.$$ Note that it is possible to find the generators for the stabiliser $G_1$ using Schreier's Lemma, but this is a bit tedious so I have not given any of the details. We repeat this process on the stabiliser $G_1$: $$ 2\cdot G_1 = \{2, 3\} \quad G_{1, 2} = \langle (4\ 5)\rangle$$ where $G_{1,2}$ means the stabiliser of $2$ in $G_1$ (again omitting the details). We repeat this process again on $G_{1,2}$: $$4\cdot G_{1,2} = \{4, 5\} \quad G_{1, 2, 4} = \{\text{id} \}.$$ Here is where our algorithm ends, by the Orbit-Stabilizer Theorem (applied 3 times to $G$, then $G_1$, then $G_{1,2}$): $$|G| = |1\cdot G|\cdot |G_1| = |1\cdot G| \cdot |2\cdot G| \cdot |G_{1,2}| = |1\cdot G |\cdot |2\cdot G| \cdot |4\cdot G| \cdot |G_{1,2,4}| = 3\cdot 2 \cdot 2 \cdot 1 = 12.$$ The set of initial points in the orbits $\{1, 2, 5\}$ is often called a base, the union of the generators of $G$ with the generators of the stabilisers $G_1$, $G_{1,2}$, and $G_{1,2,4}$ is called strong generating set, and the orbits and stabilisers a called a stabiliser chain. You can use a stabiliser chain to answer more questions than just finding the size, for example, it can be used to check membership in the group $G$ and it can be used to find the elements in $G$.

In this rather simple example, to do the exhaustive algorithm (to find the size) is not much more difficult than the algorithm proposed above. But think about the example of, say, the symmetric group on 10 points, forgetting that we know its size already. You only have to compute 10 orbits of length 10 to 1 (that 55 points in total). In the absolute worst case (which won't happen in practice), finding the generators of the stabiliser of a point whose orbit is of length $n$ involves $2n$ multiplications of permutations producing (again in the worst case, which doesn't occur) $n$ generators for the stabiliser. So in total we require 350 applications of permutations to points (to calculate the orbits) and 110 multiplications of permutations (to find the generators in Schreier's Lemma). From this you get that the size of this group is $10! = 3628800$.

Compare this to the exhaustive algorithm where we'd require $7257600$ products of permutations on 10 points (never mind anything else).

Answer 2

I will just show how to find this information in GAP - a skill that may be useful in a number of situations.

GAP has is a function PageSource which can show the source code of a function (with comments, if present). The argument of PageSource should be a function (not an operation - see later how to handle that case). In the case of Elements, that is indeed a function:

gap> Elements;
function( coll ) ... end

so one could call PageSource and see the location of the source code and the code itself:

gap> PageSource(last);
Showing source in gap4r8p2/lib/list.gi (from line 3718)
#M  Elements( <coll> )
##
##  for gap3 compatibility. Because `InfoWarning' is not available
##  immediately this is not in coll.gi, but in the later read list.gi
##
InstallGlobalFunction(Elements,function(coll)
  Info(InfoPerformance,2,
    "`Elements' is an outdated synonym for `AsSSortedList'");
  Info(InfoPerformance,2,
    "If sortedness is not required, `AsList' might be much faster!");
  return AsSSortedList(coll);
end);

Besides other useful details, we see that Elements delegates to AsSSortedList, which is an attribute:

gap> AsSSortedList;
<Attribute "AsSSortedList">

Attribute is an operation, so PageSource will not work for it in the same way as above:

gap> PageSource(AsSSortedList);
Cannot locate source of kernel function AsSSortedList.

This happens because AsSSortedList is actually a bunch of methods, and you need first to find the one which will be applied to the group in question via

gap> f:=ApplicableMethod(AsSSortedList,[Group( (1,2,3,4,5,6,7,8),(1,2) )]);
function( G ) ... end

Now one could see it as follows:

gap> PageSource(last);
Showing source in gap4r8p2/lib/grpperm.gi (from line 2031)
#############################################################################
##
#M  AsSSortedList( <G> ) elements of perm group
##
InstallMethod( AsSSortedList,"via stabchain",true, [ IsPermGroup ], 0,
function( G )
  return ElementsStabChain( StabChainMutable(G));
end );

Both of these functions are documented, type ?ElementsStabChain and ?StabChainMutable in GAP to see further details.

Note that if the value of the attribute is already stored in the object, ApplicableMethod will not be helpful, as it will return the so called "system getter" which retrieves the stored information:

gap> G:=Group( (1,2,3,4,5,6,7,8),(1,2) );
Group([ (1,2,3,4,5,6,7,8), (1,2) ])
gap> Size(G);
40320
gap> ApplicableMethod(Size,[G]);
function( object ) ... end
gap> PageSource(last);
Cannot locate source of kernel function GetterFunc(Size).

In this case, to find the actual method being used to compute the attribute, you would have to create the object from scratch:

gap> G:=Group( (1,2,3,4,5,6,7,8),(1,2) );
Group([ (1,2,3,4,5,6,7,8), (1,2) ])
gap> ApplicableMethod(Size,[G]);
function( G ) ... end
gap> PageSource(last);
Showing source in gap4r8p2/lib/grpperm.gi (from line 482)
##
InstallMethod( Size,
    "for a permutation group",
    true,
    [ IsPermGroup ], 0,
    G -> SizeStabChain( StabChainMutable( G ) ) );

Answer 3

$8! = 40320$ is very very small in computing terms. The cheapest personal computer today can do about $100$ million operations per second, and so any algorithm that takes time proportional to the group size will be able to list $S_8$ within a split second. Exhaustive search with memoization (such as breadth-first or depth-first) would be sufficient.

James Mitchell points out that GAP does not use this method, so this is just one possible way that works for small number of generators. The advantage of this general purpose approach is merely that it works for all other types of generated structures. It is asymptotically optimal for constant number of generators and where all elements have constant description length.

Say we use depth-first search (aka DFS) with memoization to generate the group elements given its (finitely many) generators. We use a recursive procedure that, given any group element as input, generates all possible group elements that can be obtained from the input by right-multiplying by a generator or its inverse (left-multiplying would be fine as well). For each obtained element the procedure calls itself with that element as input. Of course, we always use memoization, meaning that we never execute the procedure with the same input twice. This is easily accomplished by checking at the start of the procedure whether the input has been processed before, and terminating if so. Note that the procedure must record that it processed the input before it makes any recursive calls, otherwise it will go into an infinite loop. Also, since the generators are given as permutations, there are only finitely many elements and so the procedure is guaranteed to terminate. Here is some pseudo-code:

MemTable reach
Procedure group(Set<Perm> S,Perm x):
  If reach.have(x):
    Return
  reach.record(x)
  Output(x)
  For each g in S:
    group(S,x*g)
    group(S,x*inverse(g))

and to print out all elements of a group generated by a set S of permutations one would do:

reach.clear()
group(S,identity)