Permutation groups and Sims-Schreier algorithm

In mathematics, when you change the order of elements in some collection it is called a permutation. You can “multiply” permutations by taking their composition and for given permutation you can always find inverse one which simply reverses its action. And also we can imagine identity permutation which does nothing with order of elements. This means permutations can form a very special algebraic structures, groups (remember, compositions are associative). Such permutation groups has been studied a lot and there’s a whole world of algorithms around them. In this article we’ll look at Sims-Schreier algorithm in context of group order computation and in the end I’ll show a fun way to represent Rubick’s cube. Let’s dive in!

Introduction

First let’s define basic operations with permutations. Permutations are stored coordinatewise: x({1, …, n}) = {x₁(1), …, x_n(n)}. With multiplication let’s follow rightmost first notation, which means that it’s viewed as composition from right to left.

For Q = {1, …, n} we define x * y = x(y(Q)). Then inverse is defined as permutation x_inv such as x(x_inv(Q)) = Q or x * x_inv = identity.

Here’s the code:

def mult(*p_chain):
    res = []
    for i in range(0, len(p_chain[0])):
        image = i
        # x o y = x(y(S)), rightmost first
        for p in reversed(p_chain): 
            image = p[image] - 1 
        res.append(image + 1)
    return tuple(res)
        
def inv(x):
    res = list(deepcopy(x))
    for i in range(0, len(x)):
        res[x[i] - 1] = i + 1
    return tuple(res)

Group order

Requirement: before reading this article make sure that you have some basic understanding of group theory: what is group, group operation, subgroup. I’ll give some definitions later, but it may be better to get this knowledge from well-structured learning book about group theory.

Every set of permutations generate some group, minimal set of permutations which contains starting permutations and closed under multiplication. Starting permutations called generators, if G generated by set S it can written as G = 〈 S 〉.

Algorithm for group generation is straightforward: start from generating set, then multiply permutations with each other and append new elements until new ones will stop to appear.

This can be rewritten as depth-first search. Start from identity permutation and explore group as graph:

def BuildGroupDfs(p, S, group):
    for g in S:
        h = mult(g, p)
        if h not in group:
            group.add(h)
            BuildGroupDfs(h, S, group)

Size of group is called group order (written as |G|). Often we want to know order of the group generated by some permutations without enumerating its elements because in practice resultings groups are often expected to be huge. In such a case Sims-Schreier algorithm comes in handy.

By the way, tree of recursive calls here can degenerate to long chain. Build an example.

Basic definitions

Before we start we need to define most fundamental things in group theory.

First, group H is called subgroup of the group G if its elements are subset of elements of G, let’s write it H ≤ G.

Orbit of element q ∈ Q and group G is subset of Q that for every q_o ∈ Orb(q) there’s g ∈ G: q_o = g(q). In other words it’s just possible positions where G can “move” our element q.

Stabilizer subgroup of G and element q is subgroup which leaves element q fixed on the place. Definition can look like this: Stab(G, q) ≤ G and h(q)=q for every h ∈ H.

Now, let’s define cosets:

• for subgroup H ≤ G and g ∈ G right coset Hg is set of elements h * g and h ∈ H;
• for subgroup H ≤ G and g ∈ G left coset gH is set of elements g * h and h ∈ H.

Every g ∈ G is contained in exactly one coset. You can think about cosets as about partition of elements of G.

And probably the most tricky thing in Sims-Schreier algorithm is transversal. Let’s define it as system of representative elements of each coset of some subgroup H ≤ G (including identity element).

Transversals are just permutations, which have been chosen by special rule. Sounds simple, but it requires me some time to get it when I was reading about Sims-Schreier first time.

Now we are ready.

Sims-Schreier algorithm

Main idea of Sims-Schreier algorithm is to decompose our group G into the chain of subgroups. It means that each group in chain G_i should be a subgroup of previous one G_i-1:

G = G₀ ≥ G₁ ≥ … ≥ G_n = 〈 identity 〉.

For such chain it can be proved that every element g ∈ G has unique representation as product of right transversals R_i of G_i ≤ G_i-1:

g = r₁ * r₂ … * r_n for r₁ ∈ R₁, r₂ ∈ R₂, …, r_n ∈ R_n.

Start from observation that for subgroup H ≤ G, cosets partition and chosen transversals it is true that every g ∈ G can be uniquely expressed as g = t_Hg h. Repeat same reasoning for subgroup of H.

This logic works for every chain of subgroups, however for efficient computations we need stabilizer subgroups in our chain. It is because in such a case we can use Schreier lemma which will be discussed later.

Ok, since transversal representation is unique it is now easy to see that the order of G is the product of |R_i|.

By iterating through every R_i it’s easy to list elements of G without repetition. There’s also a way to return random g ∈ G by picking transversals randomly.

Let’s get back to stabilizer chain and technical details.

• How to compute transversals?

First we need to answer a question: if we have a stabilizer G_u what is the structure of cosets G_u ≤ G?

The answer is that different cosets correspond to different mappings u ∈ Q to v ∈ Q possible for group G. For example coset containing elements of G_u will contain mapping from u to u. Therefore there’s natural bijection between point orbit elements and cosets. This is enough to compute every transversal. For given generator set compute set of permutations for every possible mapping. This can be made in dfs-like fashion and corresponding tree is called Schreier Tree.

def BuildSchreierTree(i, S, orbit):
    for g in S:
        if g[i-1] not in orbit:
            orbit[g[i-1]] = mult(g, orbit[i])
            BuildSchreierTree(g[i-1], S, orbit)

• How to compute stabilizer subgroup? Use Schreier lemma to compute generators of subgroups.

For G = 〈 S 〉 and u ∈ Q, p ∈ Q let R be right transversal for cosets G_u ≤ G and let r_p ∈ R be transversal element mapping u to p. Then stabilizer subgroup G_u is generated by the following set {r_s(p)^-1 s r_p, for p ∈ u^G and s ∈ S} called Schreier generators.

This is Schreier lemma for stabilizers.

Note: r_s(p)^-1 s r_p in rightmost-first notation, compare with standard r_p s r_s(p)^-1 in leftmost-first notation.

            
def BuildSchreierGenerators(S, orbit):
    S_gen = set()
    for g in S:
        for u in orbit:
            schreier_generator = mult(inv(orbit[g[u-1]]), g, orbit[u])
            S_gen.add(schreier_generator) 
    return S_gen

After orbit is computed and generators are found this new generator set can be much larger then previous one. At the same time many of Schreier generators often turns out to be redundant, that means there exists smaller set of generators for the same group. This will cause unnecessary combinatorial growth unless new set will be filtered by some procedure.

Sims filter is the best option here, it guarantees resulting set to be O(|Q|²) in size. Main idea of this algorithm to construct generating set including only one permutation for every pair (i, j) which maps i to j in Gauss-elimination style.

Here’s my modified Python version of this algorithm based on the code from internet article and Charles Sims survey.

            
def SimsFilter(S, n):    
    u = [[-1]*n] * n 
    # only for j > i

    for g in S:
        h = g        
        for i in range(1, n+1):
            j = h[i-1]
            if j > i:
                if u[i-1][j-1] == -1:
                    u[i-1][j-1] = h
                    break
                else:
                    h = mult(inv(u[i-1][j-1]), h)
    
    S_reduced = set()
    
    for i in range(0, n):
        for j in range(0, n):
            if u[i][j] != -1:
                S_reduced.add(u[i][j])

    return S_reduced
    
def SchreierSims(S):
    n = len(S[0])    
    ans, group_order, i = [], 1, 1
    
    while len(S) != 0 and i <= n:
        orbit = {i : tuple(range(1, n+1))}
        BuildSchreierTree(i, S, orbit)
       
        R = [orbit[j] for j in orbit]
        S = SimsFilter(BuildSchreierGenerators(S, orbit), n)
        
        ans += [R]
        group_order, i = group_order * len(R), i + 1 
        
    return ans, group_order

You can find full code here.

Instead of conclusion

Recently, I came across this nice way to represent Rubick’s cubes as planar graphs (left on the picture and cube net is shown for comparison). This representation is very helpful for understanding which permutations are equivalent to cube rotations. Note, for this scheme there’s two “different” types of possible rotations. There’s inner rotation and outer rotation. They are coincide (up to enumeration) with each other and different only on the picture.

It’s easy to see that corresponding to pictures generating permutations are

[[1 , 13, 9, 3 , 23, 6 , 7 , 14, 10, 4 , 24, 12, 11, 5 , 15, 16, 17, 18, 19, 20, 21, 22, 8 , 2 ],
 [1 , 2 , 3, 14, 11, 5 , 7 , 8 , 9 , 16, 12, 6 , 13, 18, 15, 20, 17, 22, 19, 24, 21, 4 , 23, 10],
 [22, 2 , 3, 4 , 5 , 16, 21, 8 , 9 , 10, 11, 15, 13, 14, 1 , 7 , 19, 17, 20, 18, 6 , 12, 23, 24]]

For 2x2 version of Rubick’s cube they are enough to generate whole permutation group. Let’s check our algorithm:

>>> R, group_order = SchreierSims(generators)
>>> print(group_order)
>>> 88179840

This number coincides with known results.