# Rubik’s cube notes – orbits, actions, cosets

Definition: Let X be a set and let G be a group. We call X a G-set and we say G acts on X provided the following conditions hold:
(1) each g belongs to G gives rise to a function

```                              g : X ---> X,
```

(2) the identity 1 belonging to the group G defines the identity function on X,
(3) if g, h belong to G then the composite

```                             gh : X ---> X
```

defined by

```                      g        h
X -----> X -----> _ X
\________________/|
gh

(gh)(x) = h(g(x)).

```

Definition: Let G act on a set X. We call the action transitive if for each pair x, y belonging to X there is a g in G such that y = g(x). We call the action free if the only g in G which fixes some x in X is the element g=1 (i.e., g(x)=x => g=1).

Example: Let X be a set and let G = S_X be the symmetric group of X. Then X is a G-set and g acts on X.

Exercise: Show that the action in the previous example is both free and transitive.

Example: Let G be the “symmetric group of the square”: i.e., the group of symmetries of the square generated by the rigid motions

```                    g1 = reflection about l1,
g4 = 90 degrees clockwise rotation about O,
```

where l1, l2, l3 denote the lines of symmetry in the picture below:

```                        \        |        /
\_______|_______/
|\      |      /|
| \     |     / |
|  \    |    /  |
|   \   |   /   |
|    \  |  /    |
|     \ | /     |
___|______\|/______|___ l2
|      /|\      |
|     / |O\     |
|    /  |  \    |
|   /   |   \   |
|  /    |    \  |
| /     |     \ |
|/______|______\|
/       |       \
/        |        \
l1        l3
```

Let X be the set of vertices of the square. Then G acts on X.

Example: Let X be the set of labels of the facets on the Rubik’s cube. Let G be the permutation group generated by the permutations R, L, U, D, F, B, regarded as elements of S54. Then G acts on X.

Exercise: Let G be a group and let X = G. Define “left multiplication of G on X” by:

```                          g : X ---> X
g(x) = g*x.
```

(a) Show that this defines an action of G on X.
(b) Show that this action is transitive.
(c) Show that this action is free.

Exercise: Let G be a group and let X = G. Define “conjugation on X” by:

```                          g : X ---> X
x |-> g(x) = g*x*g^(-1).
```

Show that this defines an action of G on X.

Exercise: Let G be a group and let X denote the set of all subgroups of G. Define “conjugation on X” by:

```                         g : X ---> X
g(x) = g*x*g^(-1).
```

Show that this defines an action of G on X.

Remark: In general, the actions in the last two exercises are not transitive.

Definition: Let G be a group acting on a set X. For each x belonging to X, the set

```
Gx = { g(x) | g in G }
```

is called the orbit of x in X under G.

```
Algorithm
Input: A set S of generators of a permuation group G and an x
belonging to X
Output: The orbit of x, G*x

orbit = {x}
for y in orbit do
for g in S do
if g*y not in orbit then orbit = orbit union {g*y} endif
endfor
endfor
```

Note that the size of the list orbit in the for loop changes after each iteration of the loop. As mentioned before, the meaning of this is that the if-then command is to be executed exactly once for each element of the list.

Exercise: Let G be the group of moves of the Rubik’s cube and let X be the set of vertices of the cube. Let H be the subgroup of G generated by U*R. Find:

(1) the order of U*R,

(2) the orbit (in the Singmaster notation) of the ufr vertex in X
under H.

Definition: Let G be a group acting on a set X. For each x belonging to X, the subgroup

```                           stab_G(x) = G_x = { g in G | g(x) = x }
```

is called the stabilizer of x in G.

Example: Let G be the group of symmetries of the square, let X be the set of vertices of the square, and let x0 be the vertex in the lower right hand corner. Then stab_G(x0) = .

Exercise: Let G be any group and let X=G. Let G act on X by “left multiplication”:

```                          g : X ---> X
x |-> g(x) = g*x.
```

Show that stab_G(x) = {1}, for all x belonging to X=G.

Exercise: Let G be any group and let X=G. Let G act on X by “conjugation”:

```
g : X ---> X
x |->  g(x) = g*x*g^(-1).
```

Show that

```                       stab_G(x) = { g in G | g*x=x*g },
```

for all x belonging to X=G. (This subgroup { g in G | g*x=x*g } is called the “centralizer” of x in G.)

Example: Let X be the set of consisting of the 48 facets of the Rubik’s cube which are not center facets – i.e., the “movable” facets. Let Xc denote the subset of facets which belong to some corner subcube, Xe the subset of facets which belong to some edge subcube. Let G denote the Rubik’s cube group. Note that G acts on X, Xc, Xe. The action of G on X induced an equivalence relation as follows: we say that a facet f1 is “equivalent” to a facts f2 if there is an element of G (i.e., a move of the Rubik’s cube) which sends one facet to the other. There are exactly two equivalence classes, or orbits, of G in X: Xc and Xe. In particular, the action of G on Xc is transitive and the action of G on Xe is transitive.

Cosets

Let G be a group and H a subgroup of G. For g belonging to G, the subset g*H of G is called a “left coset” of H in G and the subset H*g of G is called a “right coset” of H in G.

Exercise: If H is finite, show |H| = |g*H| = |H*g|.

Exercise: If X is a left coset of H in G and x is an element of G, show that x*X is also a left coset of H in G.

The set of all left cosets is written G/H and the set of all right cosets of H in G is denoted H\G. These two sets may not be groups in themselves but they are useful none-the-less. For example, we have the following relationship between the orbits and the cosets of
the stabilizers.

Lemma: Let G be a finite group acting on a set X. Then

|G*x| = |G/stab_G(x)|,

for all x belonging to X.

proof: The map

```                         g*stab_G(x) |----> g*x
```

defines a function f : G/stab_G(x) –> G*x. This function is a bijection since it is both and injection (Exercise: Check this) and a surjection (Exercise: Check this). QED

Exercise: Let G be the group of symmetries of the square. Using the notation above, compute G/ and G*x0.

Theorem (Lagrange): If G is a finite group and H a subgroup then

|G/H| = |G|/|H|.

Corollary: If H, G are as above then the order of H divides the order of G.

proof of Theorem: Let X be the set of left cosets of H in G and let G act on X by left multiplication. Apply the previous lemma with x=H. QED

Exercise: Let G = S3, the symmetric group on 3 letters, and let H = , in the notation above.
(a) Compute |G/H| using Lagrange’s Theorem.
(b) Explicitly write down all the cosets of H in G.

Definition: Let H be a subgroup of G and let C be a left coset of H in G. We call an element g of G a coset representative of C if C = g*H. A complete set of coset representatives is a subset of G

x1, x2, …, xm,

such that

```                     G/H = {x1*H, ..., xm*H },
```

without repetition (i.e., all the gi*H are disjoint).

Exercise: For g1,g2 in G, define g1 ~ g2 if and only if g1 and g2 belong to the same left coset of H in G.
(a) Show that ~ is an equivalence relation.
(b) Show that the left cosets of H in G partition G.

Dimino’s Algorithm

We saw in an earlier chapter an algorithm for computing all the elements of a permutation group G. We shall discuss a more efficient algorithm for doing this in this section. For more details, see [Bu].

Notation: Let S = {g1, g2, …, gn} be a set of generators for a permutation group G. Let

```
S_0 = EMPTY,
S_i = { g1, ..., gi },
G_0 = {1},
G_i =  = the group generated by the elements in S_i,
```

for 1 <= i <= n.

```         Algorithm (inductive step):
Input: The generators S of G and a list L of all the elements of the
permutation subgroup G_{i-1}.
Output: A list of elements of G_i

C = {1}
for g in C do
for s in S_i do
if s*g not in L then
C = C union {s*g}
L = L union s*g*G_{i-1}
endif
endfor
endfor

Algorithm (Dimino):
Input: The generators S of G
Output: A list of elements of G

(Initial case S_1 = )
order = 1, element = 1, g = g1
while g <> 1 do
order = order + 1
element[order] = g
g = g*g1
endwhile

(General case)
for i from 2 to n do

endfor
```

Example: Let G = S3 = <s1, s2>. We use Dimono’s algorithm to list all the elements of G. We have

```                     G0 = {1}  <  G1 =   <  G2 = G.
```

First, we list the elements of G1 = . Since s1 = (1 2), it is order 2, so

G1 = { 1, s1 }.

This is our list L which we will apply the “inductive step” of Dimino’s algorithm to (with i=2). We start with C={1}. Now we look at the left cosets of G1 in G2=G. We have (with g=1, s=s1)

s1*G1 = G1,

so we don’t increase the size of C or L. Next, we have (with g=1, s=s2)

```                  s2*G1 = { s2, s2*s1 } != G1,
```

so L = {1, s1, s2, s2*s1}, C = {1, s2}. Next, we have (with g=s2, s=s1)

```                  s1*s2*G1 = { s1*s2, s1*s2*s1 } != G1.
```

(We know s1*s2*G1 <> G1 since neither of the two elements in s1*s2*G1 is the identity.) Thus, we increase L, C:

```                   L = {1, s1, s2, s2*s1, s1*s2, s1*s2*s1},
```

and C = {1, s2, s1*s2}. We know we may stop here since we know |S6| = 6 but the algorithm still has one more statement to execute. Next, we have (with g=s2, s=s2)

s2*s2*G1 = G1,

so we don’t increase the size of C or L (as expected). This step terminates the algorithm and S3 = L.

Exercise: Perform Dimino’s algorithm on

```                 S4 = <s1=(1 2), s2=(2 3), s3=(3 4)>.
```