Intereting Posts

$\prod_{k=1}^\infty \cos(x2^{-k})$
Connections and Ricci identity
Is there more than one way to divide the “L”-shaped tromino into four congruent, connected pieces?
Maybe is right $\frac{n^2 + 1}{4k + 3} \notin \mathbb{Z}, n, k \in \mathbb{N}^{+}$
cusp and node are not isomorphic
Verification of Proof that a nonabelian group G of order pq where p and q are primes has a trivial center
Prove if an element of a monoid has an inverse, that inverse is unique
Is there a coherent sheaf which is not a quotient of locally free sheaf?
How does one create a partition of unity for a complex manifold?
Integrating $\int_\Gamma1/z \, dz$ Through a “Branch Cut”
Probability in multiple choice exams
The number of geodesics of a complete Riemann manifold with non-positive sectional curvature
Integration of a differential form along a curve
How can I construct a sequence of injections $\langle f_\alpha\colon\alpha\to\omega\mid\alpha<\omega_1\rangle$ with a particular coherence property?
Eigenvalues of the principal submatrix of a Hermitian matrix

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?

- Implementation of Monotone Cubic Interpolation
- Find the Theta class for the recursion $T(n) = T(3n/4) + T(n/6) + 5n$
- Simple explanation and examples of the Miller-Rabin Primality Test
- Why is the number of possible subsequences $2^n$?
- Determining if an arbitrary point lies inside a triangle defined by three points?
- Why does this algorithm to plot implicit equations work?

- Math Analysis Designing Algorithms
- Mathematically representing combinations with integers uniquely?
- Efficiently calculating the logarithmic integral with complex argument
- Recovering a finite group's structure from the order of its elements.
- Merge Sort time complexity analysis
- An algorithm for making conditionally convergent series take arbitrary values?
- Count arrays with each array elements pairwise coprime
- Fast exponentiation algorithm - How to arrive at it?
- Algorithms for solving the discrete logarithm $a^x \equiv b\pmod{n}$ when $\gcd(a,n) \neq 1$
- Simple algorithm for generating Poisson distribution

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).

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 ) ) );
```

$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)
```

- Integral classes in de Rham cohomology
- In a finite ring extension there are only finitely many prime ideals lying over a given prime ideal
- Equalities and inequalities for quadrilaterals in hyperbolic space
- Abelian groups of order n.
- Can this standard calculus result be explained “intuitively”
- Product of all elements in finite group
- Distribution of the lifetime of a system consisting of two exponentially distributed components, one being backup
- When a change of variable results in equal limits of integration
- Axiom of Replacement (Question of notation)
- Infinite Degree Algebraic Field Extensions
- Why aren't there any coproducts in the category of $\bf{Fields}$?
- a generalization of normal distribution to the complex case: complex integral over the real line
- Fourier series of function $f(x)=0$ if $-\pi<x<0$ and $f(x)=\sin(x)$ if $0<x<\pi$
- Proving $\lim_{x\to x_0}f(x)$ with epsilon delta definition
- About the limit of the coefficient ratio for a power series over complex numbers