Sage Tutorial for Permutation Groups

You can use sage for a lot of group theory tests. The following should give you an idea of how things work in Sage.

Sage has a lot of built-in groups that you can call. The following are a few examples.

In [1]:
S4 = SymmetricGroup(4)
In [2]:
D4 = DihedralGroup(4)

These are a few examples of groups. There is a whole lot of other 'named groups' that Sage has; you can look up the manual for it.

Even if you find a new group, and you want to understand it more, you can ask for it to print the multiplication table:

In [3]:
D4.cayley_table()
Out[3]:
*  a b c d e f g h
 +----------------
a| a b c d e f g h
b| b a d c f e h g
c| c g a e d h b f
d| d h b f c g a e
e| e f g h a b c d
f| f e h g b a d c
g| g c e a h d f b
h| h d f b g c e a

Or just list the elements:

In [4]:
D4.list()
Out[4]:
[(), (1,3)(2,4), (1,4,3,2), (1,2,3,4), (2,4), (1,3), (1,4)(2,3), (1,2)(3,4)]

Or even show the Cayley graph of it:

In [5]:
show(D4.cayley_graph())

Whenever you are unsure of what a specific command does, you can always ask for help

In [6]:
D4.cayley_graph?

Working with group elements

You can use the disjoint cycle notation to refer to a specific element of the group.

In [7]:
rho = S4([(1,2),(3,4)])
pi = S4([(1,4),(2,3)])
In [8]:
tau = rho * pi * rho.inverse()
tau
Out[8]:
(1,4)(2,3)

You can also make membership queries (and a LOT more)

In [9]:
tau in D4
Out[9]:
True

You can also specify permutations as a single array (where the i-th element represents the image of i under this permutation).

In [10]:
sigma = S4([4,3,2,1])
sigma
Out[10]:
(1,4)(2,3)

Building a group

Let us consider the rotations of the cube:

In [11]:
S8 = SymmetricGroup(8)
rot_R = S8([(1,8,6,7),(4,5,2,3)])
rot_U = S8([(5,8,1,4),(2,6,7,3)])
rot_F = S8([(4,1,7,3),(5,8,6,2)])
G = PermutationGroup([rot_R, rot_U, rot_F])
In [12]:
G.order()
Out[12]:
24

Hmm... wonder what this group is...

In [13]:
G.is_isomorphic(S4)
Out[13]:
True

Rubik's cube group (3x3x3)

Sage has a built-in named group for the 3x3x3 Rubik's cube.

In [14]:
R3 = CubeGroup()
R3
Out[14]:
The Rubik's cube group with generators R,L,F,B,U,D in SymmetricGroup(48).
In [15]:
R3.display2d("")

             +--------------+
             |  1    2    3 |
             |  4   top   5 |
             |  6    7    8 |
+------------+--------------+-------------+------------+
|  9  10  11 | 17   18   19 | 25   26  27 | 33  34  35 |
| 12 left 13 | 20  front 21 | 28 right 29 | 36 rear 37 |
| 14  15  16 | 22   23   24 | 30   31  32 | 38  39  40 |
+------------+--------------+-------------+------------+
             | 41   42   43 |
             | 44 bottom 45 |
             | 46   47   48 |
             +--------------+
In [16]:
# What the cube looks like after a move sequence
R3.display2d("R D R-1")

             +--------------+
             |  1    2   14 |
             |  4   top   5 |
             |  6    7    8 |
+------------+--------------+-------------+------------+
|  9  10  11 | 17   18   19 | 25   26  40 | 46  34  35 |
| 12 left 13 | 20  front 21 | 28 right 39 | 47 rear 37 |
| 22  23  48 | 32   29   24 | 30   31   3 | 33  15  16 |
+------------+--------------+-------------+------------+
             | 38   36   43 |
             | 42 bottom 45 |
             | 41   44   27 |
             +--------------+
In [17]:
len(R3.orbit(2))
Out[17]:
24
In [18]:
R3.stabilizer(1)
Out[18]:
Subgroup generated by [(14,22,30,38)(15,23,31,39)(16,24,32,40)(41,43,48,46)(42,45,47,44), (7,37,45,23,15,28,29,39,13)(8,22,48,25,41,32,19,16,38)(12,31,42,44,21,36,47,20,18)(14,40,46), (6,25,43,16)(7,28,42,13)(8,30,41,11)(17,19,24,22)(18,21,23,20), (3,38,43,19)(5,36,45,21)(8,33,48,24)(25,27,32,30)(26,29,31,28), (2,47,4)(10,34,39)] of (The Rubik's cube group with generators R,L,F,B,U,D in SymmetricGroup(48).)
In [19]:
len(R3.orbit(1)) * R3.stabilizer(1).order() == R3.order()
Out[19]:
True

However, if you are interested more in the visualisation of moves rather than the group directly, there is a related class called RubiksCube.

In [20]:
C = RubiksCube("R D R-1")
C.plot3d()
Out[20]:

Building the nxnxn Rubik's cube group

As a concrete example, we can try to build the general nxnxn Rubik's cube group. However, in order to build that, we need a way to label the stickers to make it easier to talk about precisely how the various moves work.

Convention for sticker names

A natural way is to just think of each "piece" of the cube specified by the slice numbers in each direction.

  • x-slices: Start in L, and end at R
  • y-slices: Start at D, and end at U
  • z-slices: Start at F, and end at B

Hence, for example, the (0,0,0) piece refers to the LDF corner. However, this alone isn't enough as we also need the face it belongs to. Well, it is enough to just specify the direction of the face as the face is determined by the slice number in that direction. We will therefore specify stickers using the notation:

(face_direction, x-slice-index, y-slice-index, z-slice-index)

Thus, in general for an $n \times n \times n$ cube, there are $3n^2 \cdot 2 = 6n^2$ stickers overall (once you fix a direction, the slice index in that direction can only be 0 or (n-1)).

Sticker notation

In [21]:
num_layers = 3
stickers = [
    (face_direction, x_idx, y_idx, z_idx) 
        for face_direction in range(3)   # 0 => L/R, 1 => D/U, 2 => F/B
        for x_idx in range(num_layers) 
        for y_idx in range(num_layers)
        for z_idx in range(num_layers)
        if [x_idx, y_idx, z_idx][face_direction] in [0, num_layers - 1]   
            # eg. If we are staring at L/R, then x-cord must be 0 or n-1
]
SymStickers = SymmetricGroup(len(stickers))
SymStickers
Out[21]:
Symmetric group of order 54! as a permutation group

Now we can specify what "moves" are. Once again, we can specify the standard moves by mentioning the direction and the slice index.

In [22]:
def rotate_cube(direction, slice_idx, stickers, num_layers):
    '''
    Returns an array of permuted sticker indices (an array that is 1,...,len(stickers) permuted)
    '''
    output = []

    for sticker in stickers:
        face_dir, x_idx, y_idx, z_idx = sticker
        indices = [x_idx, y_idx, z_idx]
        
        if slice_idx != indices[direction]:
            # Then this piece doesn't move at all
            new_sticker = sticker
        else:
            if face_dir == direction:
                new_direction = direction
            else:
                # The new direction is the 'other' direction
                new_direction = [d for d in [0,1,2] if d != face_dir and d!=direction][0]
            
            new_indices = [0,0,0]
            new_indices[direction] = indices[direction]
            new_indices[(direction + 1) % 3] = indices[(direction + 2) % 3]
            new_indices[(direction + 2) % 3] = num_layers - 1 - indices[(direction + 1) % 3]

            new_sticker = (new_direction, new_indices[0], new_indices[1], new_indices[2])
        
        new_sticker_index = stickers.index(new_sticker) + 1
        output.append(new_sticker_index)
    return output
In [23]:
generators = [
                  SymStickers(rotate_cube(direction, slice_idx, stickers, num_layers))
                      for direction in [0,1,2]
                      for slice_idx in range(num_layers)
             ]
In [24]:
R = PermutationGroup(generators)
In [25]:
R.order()
Out[25]:
1038048078587756544000
In [26]:
CubeGroup().order()
Out[26]:
43252003274489856000
In [27]:
R.order() / CubeGroup().order()
Out[27]:
24

Can you see where the factor of 24 is from?

In [28]:
CubeGroup().display2d('')

             +--------------+
             |  1    2    3 |
             |  4   top   5 |
             |  6    7    8 |
+------------+--------------+-------------+------------+
|  9  10  11 | 17   18   19 | 25   26  27 | 33  34  35 |
| 12 left 13 | 20  front 21 | 28 right 29 | 36 rear 37 |
| 14  15  16 | 22   23   24 | 30   31  32 | 38  39  40 |
+------------+--------------+-------------+------------+
             | 41   42   43 |
             | 44 bottom 45 |
             | 46   47   48 |
             +--------------+

Ah! We happen to be moving our centres as well! Let's fix that

In [29]:
generators = [
                  SymStickers(rotate_cube(direction, slice_idx, stickers, num_layers))
                      for direction in [0,1,2]
                      for slice_idx in range(num_layers) if slice_idx != 1
             ]
R = PermutationGroup(generators)
R.order() == CubeGroup().order()
Out[29]:
True

Some general tutorials online

You have a pretty good tutorial here. Play around with sage to get a better hang of things.