ProjectsBlogpscoAbout

45 | Smiting the Demon Number: How to Solve a Rubik's Cube

23 October, 2022 - 38 min read

I talk to God as much as
I talk to Satan 'cause
I want to hear both sides1

Introduction

Lots of posts about numbers recently, eh? Well, here's another: in which, we solve a Rubik's Cube.

Two dueling, and even contentious properties of Rubik's Cubes are (1) the massive number of possible scrambles, and (2) that any of these scrambles is only 20 or so (contentious) moves away from being returned to the solved state. Due to the at-first unintitive idea that, no matter how many twists we apply to a Rubik's cube to make it thorughly jumbled, it can be solved in just twenty moves, that number has been dubbed God's Number.2 For the sake of motivating this post, I choose to anthropomorphize the search space of solutions to be the Demon Number.

The goal of this post is then to mathematically describe the process of moving the pieces of a valid configuration of a standard 3x3x3 Rubik's cube, and –in doing so– smite the Demon Number.

Group Theory

I have a couple other poasts that provide brief summaries of basic group theory.3 If you're starting from zero, those might be worth checking out, but this post should also be comprehensive enough (in terms of definitions, perhaps not proofs) to fill in the gaps to get the average reader up to speed. If you feel out of your depth, that's the fault of my shite writing, and not at all an indication of the readers' competency. Also worth noting that this post largely stands on the shoulders of the research and lectures of Janet Chen,4 once again I offer my meager commentary and observations about the mathematics in terms of cubing.

A Group G,\langle G, * \rangle consists of a set GG, and a binary operator * such that:

  1. GG is closed under *, that is if a,bGa, b \in G, then abGa * b \in G
  2. The operator * is associate: a,b,cG\forall a, b, c \in G, a(bc)=(ab)ca * (b *c) = (a *b) * c
  3. There exists exactly one identity element eGe \in G satisfying g=eg=ge,gGg = e * g = g * e, \forall g \in G
  4. Every element in GG has exactly one inverse: gG,hG\forall g \in G, \exists h \in G such that gh=hg=eg * h = h * g = e. We might also refer to the inverse hh as g1g^{-1}.

The order of an element of a group gGg \in G is the smallest nn such that gng^n is the identity. For example, the order of the sexy move M=RURUM = RUR'U' is six, since the move is a 6-cycle, meaning that 6 repetitions of that sequence of twists returns the cube to whatever state it started in, which is equivalent to the identity: doing nothing. The largest order of a move MGM \in G is 1260 – one such move is M=RU2DBDM = RU^2D'BD' which is like the least sexy move.

Taxonomy of The Cube

For this post, I focus on only the original 3x3x3 cube ("The Cube"), but the techniques described later on can be (in some cases, non-trivially) generalized to other l×m×nl \times m \times n cubes.

The standard cube is composed of 26 pieces (333^3 external faces 1- 1 center core piece which we can't see or meaningfully manipulate, so we don't have to worry about solving). There are 8 corners, 12 edges, and 6 center pieces; the center pieces we can also largely ignore since they are fixed in place relative to one another.5 One of the first intuitions that novice cubers acquire is that, for standard color schemes, white is opposite yellow, green opposite blue, and red opposite orange; with the additional piece of relative positioning information that yelow is left of orange and also adjacent to blue, we can form the complete standard color scheme.

The cube obviously has 6 faces, which we've established have positions derived from their fixed centers, allowing us to completely describe the "correct" solved position of any piece in terms of the face it belongs to. For example, listing a corner's faces in clockwise order unambiguously refers to precisely one piece.6

For example, urf\sf urf refers to the yellow, red, blue piece:

It is also conventional to refer to corner pieces by their face labels listed in clockwise order when the orientation matters. Edges only have two possible orientations, so there is less ambiguity.

Along with the pieces themselves, it's useful to uniquely denote the position they belong in: their cubicles. Cubicles form the skeleton of the cube; they do not move, but pieces move in and out of them.

A move is any 90º turn of a face.7 Thus, we have six primitive moves and their inverses (denoted with an apostrophe, or sometimes a negative superscript), from which we can completely manipulate the cube, for a total of 12 primitives:

{U,D,L,R,F,B,U,D,L,R,F,B}\{ U, D, L, R, F, B, U', D', L', R', F', B' \}

I'll refer to this set of primitives as P\mathbb{P}. Typically, (as in, in my head, I read the inverse moves as MM "prime").8

As mentioned above, we have four distinct categories for pieces: corners, edges, centers, and core(s) – only two of which we care about (corners and edges) since the rest cannot be meaningfully manipulated. These categories are distinct since edges can never inhabit corner cubicles and vice versa.

The Demon Number

The complexity of the cube is given by the number of permutations of each piece in each possible cubicle, confounded with the number of possible orientations each piece can have in each cubicle. Straightforwardly, we arrive at:

8!corner perms12!edge perms38corner orientation212edge orientation=519 quintillion\underbrace{8!}_{\text{corner perms} } \cdot \underbrace{12!}_{\text{edge perms}} \cdot \underbrace{3^8}_{\text{corner orientation}} \cdot \underbrace{2^{12}}_{\text{edge orientation}} = 519 \text{ quintillion}

The Demon Number.

Here, we delineate between permutation and orientation, which are likely familiar notions to any students of intermediate speed cubing techniques such as CFOP: a method where the executor first solves the (C)ross, then completes the (F)irst two layers, then (O)rients the pieces on the last later (OLL), and finally (P)ermutes the pieces of the last layer to their final positions (PLL).9

We'll shortly convince ourselves that –though daunting– this number/search space can be drastically thinned by discounting invalid configurations. For example, one single corner twist is considered an invalid configuration due to the concept of parity. Formal definitions of what a configuration is, what makes one valid are forthcoming, and what the hell parity means in the context of a puzzle-toy. Thus, our immediate goal is to widdle away at the Demon Number.

We say that a configuration or cube-state is valid if it can be reached from the initial, pristine and solved cube-state using only the legal moves described above. We call this solved configuration C0\mathcal C_0. Notably absent from the list of legal moves is anything resembling "pealing the stickers off" or "just taking the pieces out." These are trash.

Though we have yet to show that the standard cube is in fact group, the general goal of "solving" is to produce a sequence of moves that can take us from any valid state to the solved state C0\mathcal C_0.

The Cube is a Group, Dammit!

We can construct our cube group with the set of all possible moves GG, which includes sequences of the primitive moves described above. Two moves are identicial if they result in the same configuration when applied to the cube. E.g.

U2UUUUU^2 \equiv U'U' \equiv UU

The group operation is composition, denoted \circ, such that for M1,M2GM_1, M_2 \in G, M1M2M_1 \circ M_2 is the move consisting of M1M_1 followed by M2M_2. Note that, though M1M2M_1 \circ M_2 is clearly more than just one twist, we can refer to the composition as still just a single move. So, moves can be sequences of twists.

Thus, G,\langle G, \circ \rangle is a group since the behavior we've described adheres to the four fundemental properties of groups defined earlier:

  1. GG is closed under \circ since, if M1,M2M_1, M_2 are moves, M1M2M_1 \circ M_2 must also be a move.
  2. The identity on GG is the no-op MeM,MGM \circ e \equiv M, \forall M \in G, so GG has a right identity.
  3. If MM is a move, we can reverse all the steps of MM to get an inverse MM' which is also equivalent to the no-op ee, therefore every move in GG also has a right inverse.
  4. Lastly, \circ is associative. Recal that a move is also described by the spacial permutation and orientation it leaves each piece in. If we care about the orientation of a piece, we write M(c)M(c) for the oriented cubicle that the piece cc ends up in after application of move MM, with the faces of M(c)M(c) written in the same order as the faces of cc. That is, the first face of M(c)M(c) should end up in the first face of cc, and so on.

For example, the move RR puts the piece ur\sf ur in the br\sf br cubicle, with the u\sf u face of the piece lying on the b\sf b face of the cubicle and the r\sf r face of the piece lying in the r\sf r face of the cubicle. Thus, we would write R(ur)=brR(\sf{ur}) = \sf br.

For the move M1M2M_1 \circ M_2 , M1M_1 moves cc to M1(c)M_1(c), and M2M_2 moves it to M2(M1(c))M_2(M_1(c)), so

(M1M2)(c)M2(M1(c))(M_1 \circ M_2)(c) \equiv M_2(M_1(c))

To show that \circ is associative, we need to show that

(M1M2)M3M1(M2M3)(M_1 \circ M_2) \circ M_3 \equiv M_1 \circ (M_2 \circ M_3)

for all M1,M2,M3GM_1, M_2, M_3 \in G. That is, both the sinistral side and dextral sides of this equivalence relation must do the same thing to every piece cc, leaving the cube in identical configurations.

  [(M1M2)M3](c)[M1(M2M3)](c)M3([M1M2])(c)(M2M3)(M1(c))M3(M2(M1(c)))M3(M2(M1(c)))\begin{aligned} \; [(M_1 \circ M_2) \circ M_3] (c) &\equiv [M_1 \circ (M_2 \circ M_3)](c) \\ M_3([M_1 \circ M_2])(c) &\equiv (M_2 \circ M_3)(M_1(c)) \\ M_3(M_2(M_1(c))) &\equiv M_3(M_2(M_1(c))) \end{aligned}

So, composition is associative, and therefore G,\langle G, \circ \rangle is a group!

Subgroups and Generators

The Demon Number is frightening because, in order to find our solution, we have sparse moves in an infinite10 search space. To hack away at the :ghost: spooky number, we first want to examine the subgroups of GG to extract any patterns or properties that might be helpful in our quest.

Any nonempty subset HH of GG (HG,H)(H \subseteq G, H \neq \varnothing) is called a subgroup of GG.11 A group is always a subset of itself.

Let G,\langle G, \circ \rangle be a group. A nonempty subset HH of GG is a subgroup of GG iff a,bH,ab1H\forall a,b \in H, ab^{-1} \in H.12

If HH is a subgroup of some group GG, we say that HH generates GG if G=SG = \langle S\rangle; that is, every element of GG can be written as a finite product (under group operation, whatever it is) of elements of SS and its inverses.

This is useful in reducing The Demon Number since we can more thoroughly state that center positions need not be considered.13

Peter uses subgroups, it's super effective.

The Symmetric Group and Cycles

Recall that there are 8!8! possible positions of the set of corners in the cubicles. To better understand how these possibilities impact our solution attempts, consider the general case of configuring nn objects labeled 1,2,...,n1, 2, ..., n into nn buckets, similarly labeled.

We define a bijection between pieces and labeled cubicles:

σ:{1,2,...,n}{1,2,...,n}\sigma: \{ 1, 2, ..., n\} \rightarrow \{ 1, 2, ..., n\}

by σ(i)\sigma(i) being assigned to the object put into slot ii, where 1in1 \leq i \leq n.

The symmetric group on nn letters is the set of bijections from {1,2,...,n}{1,2,...,n}\{ 1, 2, ..., n\} \rightarrow \{ 1, 2, ..., n\}, with the operation of composition; we write this group as SnS_n.

For example, let σ,τS3\sigma, \tau \in S_3 be defined by

σ(1)=3,  τ(1)=1σ(2)=1,  τ(2)=3σ(3)=2,  τ(3)=2\begin{aligned} \sigma(1) = 3, \; \tau(1) = 1 \\ \sigma(2) = 1, \; \tau(2) = 3 \\ \sigma(3) = 2, \; \tau(3) = 2 \\ \end{aligned}

which implies

(στ)(1)=τ(3)=2(στ)(2)=τ(1)=1(στ)(3)=τ(2)=3\begin{aligned} (\sigma\tau)(1) = \tau(3) = 2 \\ (\sigma\tau)(2) = \tau(1) = 1 \\ (\sigma\tau)(3) = \tau(2) = 3 \end{aligned}

Notice that these subsets of the symmetric group, as well as their composition, form cycles. We can express cycles in groups as

σ(i  j  k  l)(m  n)(o)\sigma(i \; j \;k \; l)(m \; n)(o)

where σ(i)=j,σ(j)=k,...,σ(l)=i\sigma(i) = j, \sigma(j) = k, ..., \sigma(l) = i and so on. So we have three cycles in this arbitrary mapping σSwhatever\sigma \in S_\text{whatever}.

Formally, a cycle (i1  i2  ...  ik)(i_1 \; i_2 \; ... \; i_k) is the element τSn\tau \in S_n defined by

τ(i1)=i2,τ(i2)=i3,...,τ(ik1)=ik,τ(ik)=i1\tau(i_1) = i_2, \tau(i_2) = i_3, ..., \tau(i_{k-1}) = i_k, \tau(i_k) = i_1

where τ(j)=j\tau(j) = j if jir,rj \neq i_r, \forall r. The length of a cycle is kk and the support of the cycle is the set {i1,...,ik}\{ i_1, ..., i_k\} of elements which appear in the cycle, denoted supp τ\text{supp } \tau.

Two cycles σ,τ\sigma, \tau are disjoint if they have no supporting elements in common: supp σ    supp τ=\text{supp } \sigma \; \cap \; \text{supp } \tau = \varnothing.

If σSn\sigma \in S_n is the product of disjoint cycles of lengths k1,k2,...,krk_1, k_2, ..., k_r (including its 1-cycles), then the integers k1,k2,...,krk_1, k_2, ..., k_r are the cycle-type of σ\sigma.

Applying this ish to The Cube

We can use a modified cycle notation to describe what happens to each corner piece after applying a move to a configuration with respect to both its permutation and its face's orientations.

To illustrate this, we "unfold" part of the cube and examine the partial diagram of its faces after a DD move, we can see the effect the move has on all the pieces in that slice.

We can describe this effect on a single piece, e.g. D(dlf)=dfrD(\sf {dlf}) = \sf{dfr} since the piece dlf\sf {dlf} goes to the dfr\sf {dfr} cubicle. Using the above cycle notation, we can describe the effect for all the impacted pieces as:

D=(dlf  dfr  drb  dbl)(df  dr  db  dl)D = (\sf{dlf} \; \sf{dfr} \; \sf{drb} \; \sf{dbl})(\sf{df} \; \sf{dr} \; \sf{db} \; \sf{dl})

where each piece just traverses the clockwise orbit around the d\sf d centerpiece.

Configurations

Recall that a configuration is completely described by:

  1. The positions of the corners
  2. The positions of the edges
  3. The orientations of the corners
  4. The orientations of the edges

1 and 2 can be described by σS8,τS12\sigma \in S_8, \tau \in S_{12} respectively, where S8,S12S_8, S_{12} are the symmetric sets of moves that take the corners or edges from their starting positions to new positions.

To tackle 3 and 4, we need some more notation to describe the orientation of a piece relative to its starting state.

Corner Configuration

Each corner has three possible orientations which we number 0,1,20, 1, 2. We then systematically label each face of every corner cubicle:

1uufl5ddbl2uurf6ddlf3uubr7ddfr4uulb8ddrb\begin{aligned} 1 &\rightarrow \sf{u} \in \sf{ufl} \quad &5 &\rightarrow \sf{d} \in \sf{dbl} \\ 2 &\rightarrow \sf{u} \in \sf{urf} \quad &6 &\rightarrow \sf{d} \in \sf{dlf} \\ 3 &\rightarrow \sf{u} \in \sf{ubr} &7 &\rightarrow \sf{d} \in \sf{dfr} \\ 4 &\rightarrow \sf{u} \in \sf{ulb} &8 &\rightarrow \sf{d} \in \sf{drb} \end{aligned}

So each corner piece has 1 face lying in a labeled cubicle. We label this corner face 00, then continue around the cube clockwise, labeling the other corner faces 11 and 22.

Now, each corner piece has each face labeled. For any integer i[1,8]i \in [1, 8], we can find the cubicle face with that label, and let xix_i be the number of the corner piece face which indicates its orientation on this face. This gives us an ordered 8-tuple

x=(x1,x2,...,x8)\mathbf {x} = (x_1, x_2, ..., x_8)

which contains all the corner orientation information for a configuration. We can think of each xixx_i \in \mathbf {x} as the number of clockwise twists that that corner ii is away from having it's 00-face in the numbered face of the cubicle (the solved orientation). Observe that a corner piece that is 3 twists away from being solved is identically oriented to that of a piece which is already solved (0 twists away), so we can think of elements of each xix_i as being elements of the Z/3Z\mathbb Z / 3\mathbb Z. Thus, x\mathbf x is an 8-tuple of elements of Z/3Z\mathbb Z / 3\mathbb Z, where each element xi(Z/3Z)8x_i \in (\mathbb Z / 3\mathbb Z)^8.

For example, examining the R\sf R slice of the cube:

The L\sf L face is unaffected by an RR move, so we have:

x=(x1=0x2=1x4=0x3=2x5=0x7=2x6=0x8=1)=(0,1,2,2,0,0,2,1)\mathbf x = \Bigg ( \begin{aligned} x_1 = 0 \quad &x_2 = 1 \\ x_4 = 0 \quad &x_3 = 2 \\ x_5 = 0 \quad &x_7 = 2 \\ x_6 = 0 \quad &x_8 = 1 \\ \end{aligned} \Bigg )= (0,1,2,2,0,0,2,1)

Edge Configuration

We can repeat this same labeling process for edges. First, we assign cubicle labels (somewhat arbitrarily, as long as the system is internally consistent):

1uub5blb9ddb2uur6brb10ddr3uuf7frf11ddf4uul8flf12ddl\begin{aligned} 1 &\rightarrow \sf{u} \in \sf{ub} \quad &5 &\rightarrow \sf{b} \in \sf{lb} &9 &\rightarrow \sf{d} \in \sf{db} \\ 2 &\rightarrow \sf{u} \in \sf{ur} \quad &6 &\rightarrow \sf{b} \in \sf{rb} &10 &\rightarrow \sf{d} \in \sf{dr} \\ 3 &\rightarrow \sf{u} \in \sf{uf} \quad &7 &\rightarrow \sf{f} \in \sf{rf} &11 &\rightarrow \sf{d} \in \sf{df} \\ 4 &\rightarrow \sf{u} \in \sf{ul} \quad &8 &\rightarrow \sf{f} \in \sf{lf} &12 &\rightarrow \sf{d} \in \sf{dl} \\ \end{aligned}

Each piece now has a face lying on a numbered edge cubicle. We label this edge face 00 and the other one 11. We let yiy_i be the number of the edge piece face in the cubicle face labeled ii yielding

y(Z/2Z)12\mathbf y \in (\mathbb Z / 2 \mathbb Z)^{12}

With this orientation notation, we can completely describe any configuration of

σS8,τS12x(Z/3Z)8,y(Z/2Z)12\begin{aligned} \sigma &\in S_8, &\tau &\in S_{12} \\ \mathbf x &\in (\mathbb Z / 3 \mathbb Z)^{8}, &\mathbf y &\in (\mathbb Z / 2 \mathbb Z)^{12} \end{aligned}

as a 4-tuple C=(σ,τ,x,y)\mathcal C = (\sigma, \tau, \mathbf x, \mathbf y).

Example

A common algorithm used in the beginner's method during the last step –orienting the corners of the last face– is a six-cycle DRDRDRD'R'.14 If we jot down the 4-tuple for this algorithm, we get:

D=(dlf  dfr  drb  dbl)(df  dr  db  dl)R=(rfu  rub  rbd  rdf)(ru  rb  rd  rf)\begin{aligned} D = (\sf{dlf} \; \sf{dfr} \; \sf{drb} \; \sf{dbl})(\sf{df} \; \sf{dr} \; \sf{db} \; \sf{dl}) \\ R = (\sf{rfu} \; \sf{rub} \; \sf{rbd} \; \sf{rdf})(\sf{ru} \; \sf{rb} \; \sf{rd} \; \sf{rf}) \\ \end{aligned}

from which, we also get their inverses:

D=(dbl  drb  dfr  dlf)(dl  db  dr  df)R=(rdf  rbd  rub  rfu)(rf  rd  rb  ru)\begin{aligned} D' = (\sf{dbl} \; \sf{drb} \; \sf{dfr} \; \sf{dlf})(\sf{dl} \; \sf{db} \; \sf{dr} \; \sf{df}) \\ R' = (\sf{rdf} \; \sf{rbd} \; \sf{rub} \; \sf{rfu})(\sf{rf} \; \sf{rd} \; \sf{rb} \; \sf{ru}) \\ \end{aligned}

So, the composition of the crycles listed in the complete algorithm DRDRDRD'R' is:

DRDR=(dlf  dfr  lfd  frd  fdl  rdf)(drb  bru  bdr  ubr  rbd  rub)(df  dr  br)\begin{aligned} DRD'R' = (\sf{dlf} \; \sf{dfr} \; \sf{lfd} \; \sf{frd} \; \sf{fdl} \; \sf{rdf}) (\sf{drb} \; \sf{bru} \; \sf{bdr} \; \sf{ubr} \; \sf{rbd}\; \sf{rub})(\sf{df} \; \sf{dr} \; \sf{br}) \\ \end{aligned}

which has two 6-cycles in terms of corner orientation, and a single 3-cycle in terms of edges.15

Recall that τ\tau, an element of S12S_{12}, is a bijection from the set of 12 un-oriented edges to the 12 edge cubicles, and can be expressed in disjoint cycle notation. Here, DRDRDRD'R' moves dfdr\sf {df} \rightarrow \sf {dr} , drbr\sf {dr} \rightarrow \sf {br}, and brdf\sf {br} \rightarrow \sf {df}, so τ=(df  dr  br)\tau = (\sf{df} \; \sf{dr} \; \sf{br}). And, similarly, σ\sigma can be expressed (without regard to orientation) as σ=(drb  bru)(dfl  dfr)\sigma = (\sf{drb} \; \sf{bru})(\sf{dfl} \; \sf{dfr}).

From our labeling scheme for corners, we can see that DRDRDRD'R' leaves x1,x2,x4,x5x_1, x_2, x_4, x_5 unaffected, and that this algorithm puts the b\sf b face of corner drb\sf {drb} into the u\sf u face of ubr\sf{ubr}, so the b\sf b face of drb\sf {drb} is 2: x3=2x_3 =2, and similarly x6=2,x7=0,x8=2x_6 = 2, x_7 =0, x_8 = 2. All together:

x=(0,0,2,0,0,2,0,2)\mathbf x = (0, 0, 2, 0, 0, 2, 0,2)

Similarly for the edges, DRDRDRD'R' only affects edges of the df,dr,br\sf{df, dr, br} edges. We know from the labels that only y6,y10,y11y_6, y_{10}, y_{11} may be non-zero, but incidentally, their orientations remain unchanged after 1 iteration of the 6-cycle, so y=0\mathbf y = \overline{0}.

Group Homomorphisms

homomorphism is a weaker condition than the structural and relational equivalence defined by an isomorphism. A homorphism exists when sets have the same algebraic structure, but they might have a different number of elements.

Formally, if we let G,\langle G, \diamond \rangle and H,\langle H, \star \rangle be two groups. A homomorphism from GG to HH is a map ϕ:GH\phi: G \rightarrow H such that

ϕ(ab)=ϕ(a)ϕ(b)a,b,G\phi(a \diamond b) = \phi(a) \star \phi(b) \quad \forall a, b, \in G

We can define a map ϕ:GS8\phi: G \rightarrow S_8 as any move in GG which rearranges the corners (that is, all moves other than the identity and equivalent moves). That is, for any MG  \  eM \in G \;\backslash\; e , define some permutation σS8\sigma \in S_8. Let ϕcorner=σ\phi_{corner} = \sigma such that ϕcorner(M)\phi_{corner}(M) is the element of S8S_8 which describes what MM does to the unoriented pieces. Taking the familiar DRDRDRD'R' which has the disjoint cycle composition

(dlf  dfr  lfd  frd  fdl  rdf)(drb  bru  bdr  ubr  rbd  rub)(df  dr  br)(\sf{dlf} \; \sf{dfr} \; \sf{lfd} \; \sf{frd} \; \sf{fdl} \; \sf{rdf})(\sf{drb} \; \sf{bru} \; \sf{bdr} \; \sf{ubr} \; \sf{rbd} \; \sf{rub})(\sf{df} \; \sf{dr} \; \sf{br})

Therefore, ϕ(DRDR)=(dlf  dfr)(drb  bru)\phi(DRD'R') = (\sf{dlf} \; \sf{dfr})(\sf{drb} \; \sf{bru}). That is, the corner without respect to orientation.

Similarly, we define ϕedge:GS12\phi_{edge}: G \rightarrow S_{12} by letting ϕedge(M)\phi_{edge}(M) be the element of S12S_{12} which describes what MM does to the twelve unoriented edges e.g. ϕedge(DRDR)=(df  dr  br)\phi_{edge}(DRD'R') = (\sf{df} \; \sf{dr} \; \sf{br}).

With these two homomorphisms, we can define the "cube" homomorphism:

ϕcube:GS20\phi_{cube}: G \rightarrow S_{20}

which describes the permutations of the twenty unoriented edges and corners.

The Sign Homomorphism

We know from properties of generators that SnS_n is generated by the 2-cycles in SnS_n. That is, any permutation in SnS_n can be written as a finite product of 2-cycles. However, any given permutation of SnS_n can be written as a finite product of 2-cycles in infinitely many ways (actually infinite, not just like "big numbie" infinity). So this isn't super useful.

Some permutations in SnS_n can be expressed as aproduct of even number 2-cycles; aptly referred to as even permutations. Conversely, all the other permutations of SnS_n, written as a product of an odd number of 2-cyrcles are called odd permutations. At the moment, it might seem like there's no reason why a permutation couldn't be both odd and even, but as the name suggests: that is –in fact– impossible.

The direct proof is gross, so we'll indirectly approach this statement.

Proof of Permutation Parity

We fix nn and let P(x1,...,xn)P(x_1, ..., x_n) be a polyomial in nn variables. That is, if n=1,P(x1)n=1, P(x_1) is a polynomial in the variable xix_i so that P(xi)P(x_i) has the shape:

amx1m+am1x1m1++a0a_mx_1^m + a_{m-1}x_1^{m-1} + \dots + a_0

So P(x1)P(x_1) is a sum of terms that look like axiax_i. For n=2n=2, P(x1,x2)P(x_1, x_2) is the sum of terms that look like ax1ix2jax_1^ix_2^j. In general, P(x1,...,xn)P(x_1, ..., x_n) is the sum of terms that look like

ax1i1x2i2xninax_1^{i_1}x_2^{i_2}\dots x_n^{i_n}

If σSn\sigma \in S_n, we say PσP^\sigma is the polynomial defined by

(Pσ)(x1,...,xn)=P(xσ(1),...,xσ(2))(P^\sigma)(x_1, ..., x_n) = P(x_{\sigma_{(1)}}, ..., x_{\sigma_{(2)}})

We simply replace xix_i with xσ(i)x_{\sigma_{(i)}}. For n=4n=4, P(x1,x2,x3,x4)=x13+x2x3+x1x4P(x_1,x_2,x_3,x_4) = x_1^3 + x_2x_3 +x_1x_4, and σS4\sigma \in S_4 has a cycle decomposition σ=(1  2  3)\sigma = (1 \; 2 \; 3). Then

(Pσ)(x1,x2,x3,x4)=xσ(1)3+xσ(2)xσ(3)+xσ(1)xσ(4)=x23+x3x1+x2x4\begin{aligned} (P^\sigma)(x_1, x_2, x_3, x_4) &= x^3_{\sigma_{(1)}} + x_{\sigma_{(2)}}x_{\sigma_{(3)}} + x_{\sigma_{(1)}}x_{\sigma_{(4)}} \\ &= x^3_2 + x_3x_1 + x_2x_4 \end{aligned}

And note that, for any σ,τSn,(Pσ)τ=Pστ\sigma, \tau \in S_n, (P^\sigma)^\tau = P^{\sigma\tau}. To prove the assertion about disjoint even and odd permutations, we apply the above decomposition to the following polynomial:

Δ=1i<jn(xikj)\Delta = \prod_{1 \leq i < j \leq n} (x_i - k_j)

E.g., for n=3,Δ=(x1x2)(x1x3)(x2x3)n=3, \Delta = (x_1 - x_2)(x_1 - x_3)(x_2 - x_3). So, for any σSn,Δσ=±Δ\sigma \in S_n, \Delta^\sigma = \pm \Delta. For σ=(1  3  2)\sigma = (1 \; 3 \; 2):

Δσ=(x3x1)(x3x2)(x1x2)=(x1x2)(x1x3)(x2x3)=Δ\begin{aligned} \Delta^\sigma &= (x_3 - x_1)(x_3 - x_2)(x_1 - x_2) \\ &= (x_1 - x_2)(x_1 - x_3)(x_2 - x_3) \\ &= \Delta \end{aligned}

Alternatively, for σ=(1  2)\sigma = (1 \; 2)

Δσ=(x2x1)(x2x3)(x1x3)=Δ\begin{aligned} \Delta^\sigma &= (x_2 - x_1)(x_2 - x_3)(x_1 - x_3) \\ &= -\Delta \end{aligned}

with the idea being that we match terms of Δ\Delta with the terms of Δσ\Delta^\sigma. That is, for each (xixj)Δ(x_i - x_j) \in \Delta, either (xixj)(x_i - x_j) or its negation appears in Δσ\Delta^\sigma. It follows from the definition of Δ\Delta that

Δ=1i<jn(xixj)Δσ=1i<jn(xσ(i)xσ(j))\begin{aligned} \Delta &= \prod_{1 \leq i < j \leq n} (x_i - x_j)\\ \therefore \Delta^\sigma &= \prod_{1 \leq i < j \leq n} (x_{\sigma_{(i)}} - x_{\sigma_{(j)}}) \end{aligned}

The unrigouresness proof of this follows from the definition of a map ϵ:Sn{1,1}\epsilon: S_n \rightarrow \{-1, 1 \} by σΔ=ϵ(σ)Δ\sigma\Delta = \epsilon(\sigma)\Delta. We know that

Δστ=(Δσ)τ=[ϵ(σ)Δ]τ=ϵ(σ)ϵ(τ)Δ\Delta^{\sigma\tau} = (\Delta^\sigma)^\tau = [\epsilon(\sigma)\Delta]^\tau = \epsilon(\sigma)\epsilon(\tau)\Delta

Therefore, ϵ(στ)=ϵ(σ)ϵ(τ)\epsilon(\sigma\tau) = \epsilon(\sigma)\epsilon(\tau), so ϵ\epsilon is a homomorphism called the sign homomorphism. We define that if σ\sigma is a 2-cycle, then ϵ(σ)=1\epsilon(\sigma) = -1.

Proof: Let σ=(1  2)\sigma = (1 \; 2), so for the sign homomorphism we have:

Δ=1i<jn(xixj)\begin{aligned} \Delta &= \prod_{1 \leq i < j \leq n} (x_i - x_j) \\ \end{aligned}

and expanding for i=1,2i = 1, 2 separately we have

Δ=1<jn(x1xj)2<jn(x2xj)3i<jn(xixj)=(x1x2)2<jn(x1xj)2<jn(x2xj)3<jn(xixj)Δσ=(xσ(1)xσ(2))2<jn(xσ(1)xσ(j))2<jn(xσ(2)xσ(j))3<jn(xσ(i)xσ(j))=(x2x1)2<jn(x2xj)2<jn(x1xj)3<jn(xixj)=Δ\begin{aligned} \Delta &= \prod_{1 < j \leq n} (x_1 - x_j) \prod_{2 < j \leq n} (x_2 - x_j) \prod_{3 \leq i < j \leq n} (x_i - x_j) \\ &= (x_1 - x_2) \prod_{2 < j \leq n} (x_1 - x_j) \prod_{2 < j \leq n} (x_2 - x_j) \prod_{3 < j \leq n} (x_i - x_j) \\ \\ \therefore \\ \\ \Delta^\sigma &= (x_{\sigma(1)} - x_{\sigma(2)}) \prod_{2 < j \leq n} (x_{\sigma(1)} - x_{\sigma(j)}) \prod_{2 < j \leq n} (x_{\sigma(2)} - x_{\sigma(j)}) \prod_{3 < j \leq n} (x_{\sigma(i)} - x_{\sigma(j)}) \\ &= (x_2 - x_1) \prod_{2 < j \leq n} (x_2 - x_j) \prod_{2 < j \leq n} (x_1 - x_j) \prod_{3 < j \leq n} (x_i - x_j) \\ &= -\Delta \end{aligned}

So we've proved the theorem for σ=(1  2)\sigma = (1 \; 2), which can be generalized to any 2-cycle, but there's an easier, softer way. If we let σ\sigma be any 2-cycle, we say that σ\sigma is a conjugate to (1  2)(1\;2), meaning

σ=τ(1  2)τ1;τSn\sigma = \tau(1 \; 2)\tau^{-1}; \quad \tau \in S_n

Since ϵ\epsilon is a homomorphism,

ϵ(σ)=ϵ(τ)ϵ(1  2)ϵ(τ)1=ϵ(1  2)=1\epsilon(\sigma) = \epsilon(\tau)\epsilon(1 \; 2)\epsilon(\tau)^{-1}= \epsilon(1 \; 2)= -1

and since ϵ\epsilon is multiplicative, if ϵ(σ)=1\epsilon(\sigma) = 1, then σ\sigma must be a product of an even number of 2-cycles. Similarly, if ϵ(σ)=1\epsilon(\sigma) = -1, it must be the product of an odd number of 2-cycles. So, σ\sigma is even iff ϵ(σ)=1\epsilon(\sigma) =1, and odd iff ϵ(σ)=1\epsilon(\sigma) = -1.

For example, (1  2)(1  3)(1 \; 2)(1 \; 3) is even, and just (1  2)(1 \; 2) is odd. ϵ(1  6  3  4    2)=1\epsilon(1 \; 6 \; 3 \; 4 \; \; 2) = 1 since

(1  6  3  4    2)=(1  6)(1  3)(1  4)(1  2)(1 \; 6 \; 3 \; 4 \; \; 2) = (1\;6)(1\;3)(1\;4)(1\;2)

is the product of four (an even number!) 2-cycles. In general, if σ\sigma is a kk-cycle, then

ϵ(σ)=(1)k1\epsilon(\sigma) = (-1)^{k-1}

The Alternating Group and Parity

Like the set of real numbers, the parity of a group is multiplicative. That is, the product of an even permutation and an odd permutation is odd, the product of two even permutations or two odd permutations as even. The inverse of an even permutation is even, the inverse of an odd is odd, so we can define a subgroup of of the symmetric group consisting of all even permutations called the Alternating Group: AnSnA_n \subset S_n:

An={σ    ϵ(σ)=1,σSn}A_n = \{\sigma \; \vert \; \epsilon(\sigma) = 1, \sigma \in S_n \}

If MGM \in G is a face twist, then ϕcube(M)\phi_{cube}(M) is a product of two 4-cycles. A 4-cycle:

(m1  m2  m3  m4)=(m1  m2)(m1  m3)(m1  m4)(m_1 \; m_2 \; m_3 \; m_4) = (m_1 \; m_2)(m_1 \; m_3)(m_1 \; m_4)

is a product of an odd number of 2-cycles, is also odd, so two 4-cycles is even. Therefore ϕcube(M)\phi_{cube}(M) is even. And since the face twists generate all of GG, ϕcube\phi_{cube} is even for all MGM \in G. So ϕcube(M)A20MG\phi_{cube}(M) \in A_{20} \forall M \in G.

Recall that ϕcube(M)=ϕcorner(M)ϕedge(M)\phi_{cube}(M) = \phi_{corner}(M)\phi_{edge}(M), so either the edge homomorphism or corner homomorphism are both even, or both odd– but they must have the same sign. So, for any valid configuration C\mathcal C, the sign of σ,τ\sigma, \tau must be the same.

Kernels

The kernel of a homomorphism ϕ:GH\phi: G \rightarrow H is defined to be the pre-image of the identity of gg in GG

ker(ϕ)={g    ϕ(g)=1H,gG}\text{ker}(\phi) = \{ g \; \vert \; \phi(g) =1_H, g \in G\}

The kernel consists of all moves of the cube which do not change the permutations of any pieces. That is, only the moves that change the orientations, which is straightforwardly useful. In particular, AnA_n is the kernel of ϵ:Sn{1,1}\epsilon: S_n \rightarrow \{-1, 1\}.

TODO: how we use them

Group Actions

If the cube is in some configuration C\mathcal C, the applying some move M1GM_1 \in G takes the cube state to a new configuration we call CM1\mathcal C \circ M_1. If we take another move M2GM_2 \in G, we can compose or chain the resulting states together:

(CM1)M2(\mathcal C \circ M_1) \circ M_2

which is the same as executing (M1M2)(M_1 \circ M_2) on C\mathcal C directly. This is the essence of group actions.

Formally, a right Group Action of G,\langle G, \circ \rangle on a non-empty set AA is a map A×GAA \times G \rightarrow A. That is, given aA,gGa \in A, g\in G we can produce another element of AA, for which we write aga \cdot g satisfying the following properties:

  1. (ag1)g2=a(g1g2);g1,g2G,aA(a \cdot g_1) \cdot g_2 = a \cdot (g_1 \circ g_2); \quad \forall g_1, g_2 \in G, a \in A
  2. ae=a;aAa \cdot e = a; \quad \forall a\in A

These are called right group actions since we associate group elements on the right. When we have a group action of GG on AA, we say that "GG acts on AA." GG acts on the set of configurations of the cube (both valid and invalid).

Oftentimes, we are interested in the case where the set AA is the group itself. For a,gGa, g \in G we def ag=aga \cdot g = ag to just be group multiplication. If GG acts on a set AA, the orbit of aAa \in A under this action is the set {ag    gG}\{ ag \; \vert \; g \in G \}. We can think of orbits as the configurations that are reachable by repeating some (sequence of) move(s).

If GG acts on the set of configurations of the cube, the orbit of the starting configuraiton under this action is exactly the set of valid configurations of the cube. This is a super nifty tid bit which further eradicates the spookiness of the Demon Number.

If a group action only has one orbit, we say that the action is transitive, or that the group acts transitively. We often want to prove something about all the elements of an orbit, like oh I don't know, all valid configurations of a cube.

Suppose a finite group GG acts on a set AA, and let SS be a set of generators of GG, and PP be some set of conditions such that the following is true: whenever aAa \in A satisfies PP and sSs \in S, asa \cdot s also satisfies PP. Then, if a0Aa_0 \in A satisfies PP, then every element in the orbit of a0a_0 also satisfies PP! In the case of the cube, we will apply this theorem to the action of GG on the set AA of configurations, where S=P,a0=C0S = \mathbb P, a_0 = \mathcal C_0 in order to prove other statements about the set of valid configurations.

Pragmatically speaking, GG acts on the set of configurations of the cube. The valid configurations, then, form a single orbit of this action, so it makes sense that the statements we make about valid configations can be generalized to other orbits.

Valid Configurations of the Cube

Six and a half thousand words in and I'm just now getting pissed that there's no Rubik's cube emoji. WTF unicode, get it together.

Using all this notation and abstraction of the innocuous toy from the seventies into dumb made up math, we can form characterizations of the cube which actually help us solve it. Only a couple more theorems, I promise.

THEOREM!! : A configuration C=(σ,τ,x,y)\mathcal C = (\sigma, \tau, \mathbf x, \mathbf y) is valid iff each of the following conditions are met:

sign(σ)=sign(τ),xi0mod3,yi0mod2,\begin{aligned} \text{sign}(\sigma) &= \text{sign}(\tau), \\ \sum x_i &\equiv 0 \mod 3, \\ \sum y_i &\equiv 0 \mod 2, \end{aligned}

Lemma: If C1,C2\mathcal C_1, \mathcal C_2 are configurations in the same orbit, then

sign(σ)sign(τ)=sign(σ1)sign(τ1)\text{sign}(\sigma)\text{sign}(\tau) = \text{sign}(\sigma^{-1})\text{sign}(\tau^{-1})

Proof of this lemma provides some further insight into the notion parity. It is sufficient to show that C=CM\mathcal C' = \mathcal C \circ M where MM is one the six primitives P\mathbb P. Then,

sign(C)=sign(C)σ=σϕcorner(M)τ=τϕedge(M)sign(σ)sign(τ)=sign(σ)sign(ϕcorner(M))sign(τ)sign(ϕedge(M))\begin{aligned} \text{sign}(\mathcal C') &= \text{sign}(\mathcal C) \\ \sigma' &= \sigma \phi_{corner}(M) \\ \tau' &= \tau \phi_{edge}(M) \\ \\ \therefore \\ \\ \text{sign}(\sigma')\text{sign}(\tau') &= \text{sign}(\sigma)\text{sign}(\phi_{corner}(M))\text{sign}(\tau)\text{sign}(\phi_{edge}(M)) \end{aligned}

and if MGM \in G (which it better be, let's be honest. When have we dealth with MGM \notin G), then ϕcorner,ϕedge\phi_{corner}, \phi_{edge} are both 4-cycles with sign 1-1, so

sign(σ)sign(τ)=sign(σ)sign(τ)\text{sign}(\sigma')\text{sign}(\tau') = \text{sign}(\sigma)\text{sign}(\tau)

This can be generalized to all valid configurations: sign(σ)=sign(τ)\text{sign}(\sigma) = \text{sign}(\tau) which is why we know a single corner or edge twist is invalid as a direct consequence of all valid configurations being in the orbit of C0=(1,1,0,0)\mathcal C_0 = (1, 1, \mathbf 0, \mathbf 0).

Lemma: If C\mathcal C' is in the same orbit as C\mathcal C, then

xiximod3,yiyimod2,\begin{aligned} \sum x_i' &\equiv \sum x_i \mod 3, \\ \sum y_i' &\equiv \sum y_i \mod 2, \end{aligned}

Once more, it suffices to show that if C=CM,MP\mathcal C' = \mathcal C \circ M, M \in \mathbb P, then =mod\sum \cdot' = \sum \cdot \mod \cdot.

We can illustrate this with a table and diagram: TODO: check these

MM x,y\mathbf {x', y'}
UU (x2,x3,x4,x1,x5,x6,x7,x8),(y4,y1,y2,y3,y5,y6,y7,y8,y9,y10,y11,y12(x_2, x_3, x_4, x_1, x_5, x_6, x_7, x_8), \\ (y_4,y_1,y_2, y_3, y_5, y_6, y_7, y_8, y_{9},y_{10},y_{11},y_{12}
DD (x1,x2,x3,x4,x8,x5,x6,x7),(y1,y2,y3,y4,y5,y6,y7,y8,y10,y11,y12,y9)(x_1, x_2, x_3, x_4, x_8, x_5, x_6, x_7), \\ (y_1,y_2,y_3, y_4, y_5, y_6, y_7, y_8, y_{10},y_{11},y_{12},y_9)
RR (x1,x7+1,x2+2,x4,x5,x6,x8+2,x3+1),(y1,y7,y3,y4,y5,y2,y10,y8,y9,y6,y11,y12)(x_1, x_7 + 1, x_2 + 2, x_4, x_5, x_6, x_8 + 2, x_3 + 1), \\ (y_1, y_7, y_3, y_4, y_5, y_2, y_{10}, y_8, y_{9},y_{6},y_{11},y_{12})
LL (x4+2,x2,x3,x5+1,x6+2,x1+1,x7,x8),(y1,y2,y3,y5,y12,y6,y7,y4,y9,y10,y11,y8)(x_4 + 2, x_2, x_3, x_5 + 1, x_6 +2, x_1 + 1, x_7, x_8), \\ (y_1, y_2, y_3, y_5, y_{12}, y_6, y_{7}, y_4, y_{9},y_{10},y_{11},y_{8})
FF (x6+1,x1+2,x3,x4,x5,x7+2,x2+1,x8),(y1,y2,y8+1,y4,y5,y6,y3+1,y11+1,y9,y10,y7+1,y12)(x_6 + 1, x_1 + 2, x_3, x_4, x_5, x_7 + 2, x_2 + 1, x_8), \\ (y_1, y_2, y_8 + 1, y_4, y_{5}, y_6, y_{3} + 1, y_{11} + 1, y_{9},y_{10},y_{7} + 1,y_{12})
BB (x1,x2,x8+1,x3+2,x4+1,x6,x7,x5+1),(y6+1,y2,y3,y4,y1+1,y9+1,y7,y8,y5+1,y10,y11,y12)(x_1, x_2, x_8 + 1, x_3 + 2, x_4 + 1, x_6, x_7, x_5 + 1), \\ (y_{6} + 1, y_2, y_3, y_4, y_{1} + 1, y_9 + 1, y_{7}, y_8, y_{5} + 1,y_{10},y_{11},y_{12})

To make sense of this table, let's examine how we arrive at x\mathbf x' for M=RM = R. The cubicles of the right face and are:

TODO: img demon number 4

So x=(x1,x7+1,x2+2,x+4,x5,x6,x8+2,x3+1)\mathbf x' = (x_1, x_7 + 1, x_2 + 2, x+4, x_5, x_6, x_8 + 2, x_3 + 1) , implying

xi+6ximod3\sum x_i' + 6 \equiv \sum x_i \mod 3

Furthermore, any configuration C\mathcal C where xi0mod3,yi0mod2\sum x_i \equiv 0 \mod 3, \sum y_i \equiv 0 \mod 2 is a valid configuration as a direct consequence of the previous assertion that valid configurations are in the orbit of the starting configuration (1,1,0,0)(1, 1, \mathbf 0, \mathbf 0). Recall the ultimate goal: to show that there exists a sequence of moves from some initial, valid conifugration which takes us to C0\mathcal C_0. We do this by writing down the steps of solving a cube (5head moment).

Solving the Cube

  1. If C\mathcal C is a configuration where
sign(σ)=sign(τ),xi0mod3,yi0mod2,\begin{aligned} \text{sign}(\sigma) &= \text{sign}(\tau), \\ \sum x_i &\equiv 0 \mod 3, \\ \sum y_i &\equiv 0 \mod 2, \end{aligned}

then there exists some move MGM \in G such that CM\mathcal C \circ M has the form (1,τ,x,y)(1, \tau', \mathbf x', \mathbf y') with

sign(σ)=sign(τ),xi0mod3,yi0mod2,\begin{aligned} \text{sign}(\sigma') &= \text{sign}(\tau'), \\ \sum x_i' &\equiv 0 \mod 3, \\ \sum y_i' &\equiv 0 \mod 2, \end{aligned}

In other words, there exists a move to put all the corner positions into their correct positions.

  1. If (1,τ,x,y)(1, \tau, \mathbf x, \mathbf y) is a configuration where
sign(τ)=1xi0mod3,yi0mod2,\begin{aligned} \text{sign}(\tau) &= 1 \\ \sum x_i &\equiv 0 \mod 3, \\ \sum y_i &\equiv 0 \mod 2, \end{aligned}

then there exists some move MGM \in G such that CM\mathcal C \circ M has the form (1,τ,0,y)(1, \tau', \mathbf 0, \mathbf y') with

sign(τ)=1yi0mod2,\begin{aligned} \text{sign}(\tau') &= 1 \\ \sum y_i &\equiv 0 \mod 2, \end{aligned}
  1. If (1,τ,0,y)(1, \tau, \mathbf 0, \mathbf y) is a configuration where
sign(τ)=1yi0mod2,\begin{aligned} \text{sign}(\tau) &= 1 \\ \sum y_i &\equiv 0 \mod 2, \end{aligned}

then there exists a move MGM \in G such that CM\mathcal C \circ M has the form (1,1,0,y)(1, 1, \mathbf 0, \mathbf y') with yi0mod2\sum y_i' \equiv 0 \mod 2. That is, we can permute all the edges (without wrecking all the corner work we've proved we can achieve).

  1. Finally, if (1,1,0,y)(1, 1, \mathbf 0, \mathbf y) is a configuration with yi0mod2\sum y_i \equiv 0 \mod 2, then there exists a move MGM \in G such that CM=(1,1,0,0)\mathcal C \circ M = (1, 1, \mathbf 0, \mathbf 0) WHICH IS C0\mathcal C_0!!!!!!!!!

In proving the viability of these steps, it's worth pointing out that if some C\mathcal C satsifies

P={sign(σ)=sign(τ),xi0mod3,yi0mod2P = \begin{cases} \text{sign}(\sigma) &= \text{sign}(\tau), \\ \sum x_i &\equiv 0 \mod 3, \\ \sum y_i &\equiv 0 \mod 2 \end{cases}

then, for any subsequent configuration C=(σ,τ,x,y)\mathcal C' = (\sigma', \tau', \mathbf x', \mathbf y') in the same orbit as C\mathcal C, also satisfies PP. So we only have to prove the existence of:

  1. MGM \in G such that (σ,τ,x,y)(\sigma, \tau, \mathbf x, \mathbf y) satisfying PP contains in its orbit a configuration (1,τ,x,y)(1, \tau', \mathbf x', \mathbf y')
  2. MGM \in G such that (1,τ,x,y)(1, \tau', \mathbf x', \mathbf y') satisfying PP contains in its orbit a configuration (1,τ,0,y)(1, \tau', \mathbf 0, \mathbf y')
  3. MGM \in G