Problem Set 1 - Part A

This part of problem set 1 has 2 questions and a total of 30 points.

Question 1 (On the 4x4x4 Rubik's cube group action)

This question is going to deal about the 4x4x4 Rubik's cube. Of course, we want to think of it as a group acting on 96 stickers. We'll use the following natural numbering.

                    Up
              +-------------+
              |  1  2  3  4 |
              |  5  6  7  8 |
              |  9 10 11 12 |
     Left     | 13 14 15 16 |    Right         Back
+-------------+-------------+-------------+-------------+
| 17 18 19 20 | 33 34 35 36 | 49 50 51 52 | 65 66 67 68 |
| 21 22 23 24 | 37 38 39 40 | 53 54 55 56 | 69 70 71 72 |
| 25 26 27 28 | 41 42 43 44 | 57 58 59 60 | 73 74 75 76 |
| 29 30 31 32 | 45 46 47 48 | 61 62 63 64 | 77 78 79 80 |
+-------------+-------------+-------------+-------------+
              | 81 82 83 84 |
              | 85 86 87 88 |
              | 89 90 91 91 |
              | 93 94 95 96 |
              +-------------+
                    Down
  1. [0 points] Without running any code, how many different orbits do these 96 stickers get partitioned into when considering all valid Rubik's cube moves?
  1. [2 points] Use Sage to actually compute the orbits and see how many there are.
In [ ]:
S96 = SymmetricGroup(96)
moves = {
    "1L": S96([(1,33,81,80),(5,37,85,76),(9,41,89,72),(13,45,93,68),
               (17,20,32,29),(18,24,31,25),(19,28,30,21),(22,23,27,26)]),    
    "2L": S96([(2,34,82,79),(6,38,86,75),(10,42,90,71),(14,46,94,67)]),
    "1R": S96([(4,77,84,36),(8,73,88,40),(12,69,92,44),(16,65,96,48),
               (49,52,64,61),(50,56,63,57),(51,60,62,53),(54,55,59,58)]),
    "2R": S96([(3,78,83,35),(7,74,87,39),(11,70,91,43),(15,66,95,47)]),
    "1F": S96([(13,49,84,32),(14,53,83,28),(15,57,82,24),(16,61,81,20),
               (33,36,48,45),(34,40,47,41),(35,44,46,37),(38,39,43,42)]),
    "2F": S96([(9,50,88,31),(10,54,87,27),(11,58,86,23),(12,62,85,19)]),
    "1B": S96([(1,29,96,52),(2,25,95,56),(3,21,94,60),(4,17,93,64),
               (65,68,80,77),(66,72,79,73),(67,76,78,69),(70,71,75,74)]),
    "2B": S96([(5,30,92,51),(6,26,91,55),(7,22,90,59),(8,18,89,63)]),
    "1D": S96([(29,45,61,77),(30,46,62,78),(31,47,63,79),(32,48,64,80),
               (81,84,96,93),(82,88,95,89),(83,92,94,85),(86,87,91,90)]),
    "2D": S96([(25,41,57,73),(26,42,58,74),(27,43,59,75),(28,44,60,76)]),
    "1U": S96([(1,4,16,13),(2,8,15,9),(3,12,14,5),(6,7,11,10),
               (17,65,49,33),(18,66,50,34),(19,67,51,35),(20,68,52,36)]),
    "2U": S96([(21,69,53,37),(22,70,54,38),(23,71,55,39),(24,72,56,40)])
}
R4 = PermutationGroup(list(moves.values()))
  1. [2 points] What was perhaps surprising about the previous answer?

  1. [6 points] Use the site alg.cubing.net and construct a suitable sequence of moves that cycles through 3 edge pieces (pieces such as (14,34) or (15,35) etc.).

    [+4 points] if your sequence happens to cycle through three edge pieces on the same face.

  1. [1 point] Check if the move permutation $(14, 34)(15, 35)$ is present in the group R4 or not.

    [1 point] What about the permutation $(14, 35) (15, 34)$?

  1. [4 points] Use the site alg.cubing.net and try out the following sequence:

    1R 2R 1U 1U 1R 2R 1F 1F 2R 1F 1F 2L 2L 2L 1U 1U 2L 1U 1U 2R 2R 2R 1U 1U 2R 1U 1U 1R 1R 1R 2R 2R 2R 1U 1U 1R 1R 1R 2R 2R 2R

    Explain the fallacy that you observe.

Question 2 (Action on vertices to action on edges)

There are situations where you have a group $G$ acting on $[n]$ vertices. We had discussed a few situation where shuffling the vertices naturally ends up shuffling the edges.

[10 points] Write a function that takes as input a permutation on $n$ elements and outputs its representation as an permutation on the $n^2$ pairs.

In [ ]:
def lift_permutation_to_pairs(sigma, n = None):
    '''
    Write a function that takes as input a permutation sigma on [1,...,n]
    and returns a permutation on [1,...,n^2] that is meant to be the 
    representation of sigma when interpretted as a shuffling of pairs.
    '''

    if n is None: n = 10
    
    vertices = [ i + 1 for i in range(n) ]
    pairs = [ (i + 1, j + 1) for i in range(n) for j in range(n) ]
    
    Sn = SymmetricGroup(vertices)
    
    # Can't directly feed 'pairs' as the argument as SymmetricGroup() either
    # expects an integer, or an array of distinct integers as input.
    
    Sn2 = SymmetricGroup([ i + 1 for i in range(n * n)]) 

    # Let say n = 10.
    # We can use 1, ... , 100 to refer to these pairs in the order of the above list. 
    # 
    # For example, the pair (5,3) corresponds to pair number 'edges.index((5,3)) + 1'
    # And you can access the pair corresponding to 17 via edges[17 - 1]
    #
    # (The annoying +1/-1 is to deal with the fact that indices go from 0 onwards in arrays)
    

    # do blah blah blah
    # return pi
    
    pass

Here is an example run (for n = 4):

Sn = SymmetricGroup(4)
sigma = Sn([(1,2,3,4)])
lift_permutation_to_pairs(sigma, 4)

# output is (1,6,11,16)(2,7,12,13)(3,8,9,14)(4,5,10,15)
#
# The first cycles corresponds to (1,1) -> (2,2) -> (3,3) -> (4,4) -> (1,1)
# and the second cycle corresponds to (1,2) -> (2,3) -> (3,4) -> (4,1) -> (1,2)
# etc.