For those of you familiar with the solution to the Rubik's cube, you will know that a single-corner twist is not a valid position. It can neither be attained by scrambling, nor can it be solved if it occurs.
I understand that there's some fundamental group theory at work here; the corners on a Rubik's cube can only be rotated in groups of three. This logically implies that one can't have a single (or two, in the same direction) corners rotated.
Why, mathematically, is this the case?
Answer
Okay, I'll give a group-theoretic answer, since that was requested, which goes most of the way to a proof. I'm assuming you mean a 3x3x3 Rubik's cube. For larger cubes, the proof is just a little bit less convenient, because these cubes don't form groups (or more precisely, the action of the group of all moves on the cube on the states of the cube is not free). Basically everything still holds though for all cubes larger than 3x3x3 when talking specifically about the corner pieces, except that if the number of layers is even nothing fixes the orientation. Edge pieces and centers can get a bit more complicated though. Also, throughout, I'll use the notation $\mathbb Z_n = \mathbb Z / n \mathbb Z$ for the cyclic group of order n.
There are a number of groups one could be referring to when using the term "cube group". Here, by the "full cube group" $G$, I mean the set of all states of the cube that can be reached by disassembling it and reassembling it, keeping all the center pieces fixed in position. In order to define the product, we'll identify it as a subset of the permutation group on the stickers. Note that each corner/edge sticker is distinguishable from all 47 other stickers. This is because on the 3x3x3 cube, each cubie has a unique collection of sticker colors. Hence, each state $\Sigma$ corresponds uniquely to a permutation $\sigma_\Sigma \in S_{48}$, where $\sigma_\Sigma(s_i)$ is the sticker in the position that sticker $s_i$ would be in the state $\Sigma_0$ corresponding to the solved cube. The product structure on the full cube group is induced by this map. As a trivial consequence of this definition, the identity of the cube group is the solved cube position $\Sigma_0$. (If this multiplication looks a bit backwards to you, it's because I want my permutation group to act on the right, which is primarily since the standard notation of cube moves (e.g. R U R' U R U2 representing the Sune) is read left-to-right.)
There are $8! \; 3^8$ ways of putting in the 8 corner pieces (because each can be rotated any of 3 ways, and they can be permuted), and independently $12! \; 2^{12}$ ways of putting in the 12 edge pieces. Hence, the full cube group has order $8! \; 3^8 \; 12! \; 2^{12}$.
This group is too big for cubing purposes. When cubing, there are 6 basic moves you can make, specifically, U, D, L, R, F and B (as well as their inverses, which are typically denoted by primes e.g. U'). The cube group $H$ is the subgroup of the full cube group generated by these 6 permutations, i.e. which can be written as words in these 6 letters and their inverses. These represent the states of the cube which are reachable with a finite sequence of turns. On this subgroup, the product operation is especially easy to understand. Let $a_1 \cdots a_n$ be any word in the generators which takes you from $\Sigma_0$ to $\Sigma_1$, and $b_1 \cdots b_m$ any word taking you from $\Sigma_0$ to $\Sigma_2$. Their product $\Sigma_1 \Sigma_2$ is the state you reach from the sequence of moves $a_1 \cdots a_n b_1 \cdots b_m$. Now that we have this identification, I'll be a bit cavalier in equating moves with states, but it should always be clear in context what is meant.
We want to prove that a particular state $\Sigma'$, that with a single corner turned by $120^\circ$, is not reachable, which is to say that it is not in the cube group (though it is in the full cube group). To do this, we'll define a homomorphism $\varphi: G \rightarrow \mathbb Z_3$. We'll then show that $\varphi(a_i) = 0$ for any one of the 6 generators $a_i$. Since any state $\Sigma$ in the cube group can be written as a word in the generators, that means that $\varphi(\Sigma) = 0$. That is to say that $\varphi$ is an invariant under the cube group. However, we can compute $\varphi(\Sigma') \ne 0$, which shows that $\Sigma' \not \in H$.
Aside: I'll just point out that this sort of approach of defining invariants that are preserved under a set of transformations is very common in mathematics; for instance, point-set topology could be characterized broadly as the study of invariants of topological spaces under homeomorphisms. Here, we're dealing with an algebraic invariant. To be a bit fancier, we're trying to define a surjective homomorphism $\varphi$ so that the composition $H \hookrightarrow G \overset{\varphi}{\twoheadrightarrow} \mathbb Z_3$ is the trivial homomorphism. Keep in mind though that this isn't an exact sequence-I haven't required that the kernel of $\varphi$ is exactly $H$. It isn't a chain complex either, at least not in standard parlance, since $H$ and $G$ are nonabelian groups.
To define the invariant, label each of the corner cubie stickers in the solved state with a number 0, 1, or 2, according to this diagram of a net of the cube:
Define $\varphi(\Sigma)$ to be the total number on the stickers on the up and down faces mod 3 in the state $\Sigma$. This of course gives a (surjective) map from the full cube group to the group $\mathbb Z/3\mathbb Z$, which is not clearly a homomorphism. I won't give a full proof that it is, but I'll take you most of the way there.
You may wonder where this particular choice comes from. In fact, the only reason I chose it is because it makes it very easy to see that $\varphi(a_i) = 0$ for each generator $a_i$. For the up and down moves, these don't even change any of the numbers at all. For the other 4 moves, the numbers do change, but they change the same way for all 4. Hence, you only need to check one position, and it's easy to check $\varphi(F) = 0$. For the proof I give below, it's a bit more convenient to check that the inverses of the generators also preserve $\varphi$, which only requires checking one more state $\varphi(F')=0$.
This ambiguity of choice of edge-labels for the solved state turns out to be important for proving that $\varphi$ is a homomorphism. Specifically, you'll want to prove the following lemma: Any choice of numbering will define the same function $\varphi$ provided is satisfies two criteria:
- Each cubie contains each of the numbers 0, 1, 2, exactly once, and they are in that cyclic order when read counter-clockwise around the vertex.
- The solved state still satisfies $\varphi(\Sigma_0)=0$ for this choice of numbering.
This isn't too hard to prove, but I'll skip it here. Once you can prove that, the homomorphism property of $\varphi$ comes basically for free. For simplicity, I'll just prove that the restriction $\varphi |_H$ is a homomorphism (specifically the trivial homomorphism), which is all we need. The proof is by induction. The base case is the identity. Suppose we can show that for every word of length $n$ in the generators, $\varphi(a_1 \cdots a_n) = \varphi(a_1) \cdots \varphi(a_n) = 0$. Consider an arbitrary word $a_1 \cdots a_n a_{n+1}$. Now note that for $\Sigma = a_1 \cdots a_n$, we could define a different numbering on the cube, specifically, the one we would get by first doing $\Sigma$, then numbering the cube as in the above figure (and then of course returning it to the initial solved state). By inductive hypothesis, $\varphi(\Sigma^{-1}) = \varphi (a_n^{-1} \cdots a_1^{-1}) = 0$. But $\Sigma^{-1}$ has the same numbering in the original scheme as $\Sigma_0$ in the new one, because to get to $\Sigma_0$ from the above we just undo the moves we did before by applying $\Sigma^{-1}$. Thus, this alternate numbering pattern fulfills both requirements of the lemma (the second one is clear), so it gives a different method to compute the same function $\varphi$.
However, then the state $a_1 \cdots a_n a_{n+1} = \Sigma a_{n+1}$, by construction in the new edge-numbering, will have the same numbering as if you started with the original edge-numbering in the figure above and did the single turn $a_{n+1}$, which we know will still give $\varphi(a_1 \cdots a_{n+1}) = 0$. Hence, for any reachable state $\Sigma \in H$, we'll have $\varphi(\Sigma) = 0$, so $\varphi |_{H} = 0$.
That's all you need, but I'll just say that proving that $\varphi$ is a homomorphism on $G$ isn't too much harder. You have to choose a different generating set though, since the generators for the cube group don't generate the full cube group. The generators you want to choose are basically "swap corners i and i+1" and "twist corner 1 by $120 ^\circ$". Those generate all possible configurations of the corner pieces (you should prove this). Of course, you also need to include things which generate the edge permutations, though these aren't important at all since we only care about the corners. The proof will proceed much the same as above, with a bit of special consideration taken for the "twist corner 1" generator.
Now, once you know $\varphi(\Sigma) = 0$ whenever $\Sigma \in H$, you just have to compute $\varphi(\Sigma')$ for the state with a single corner turned. This is easily seen to be either 1 or 2 depending on which direction you twist the single corner. So $\Sigma' \not \in H$, and we're done with the proof. As you can see, it's not really that hard, though it is very detailed and long.
I'll take a moment to mention some nice group theoretical stuff that we're actually not far off from proving. Note that as I said before, the sequence of homomorphisms $H \hookrightarrow G \twoheadrightarrow \mathbb Z_3$ is not exact. However, we can basically completely understand the group structure of the cube group. It is a normal subgroup of the full cube group, and the quotient is given by $H \hookrightarrow G \twoheadrightarrow \mathbb Z_3 \times \mathbb Z_2 \times \mathbb Z_2$ (which is exact). The latter factors of $\mathbb Z_2$ are also describable simply in terms of cube positions. The first represents edge orientation; a state with a singe edge flipped is not solvable. The second represents odd permutations. A state with 2 corner pieces (or 2 edge pieces, but not both) swapped, but with all other pieces in the right position, is not solvable. It's impossible to permute a single pair of pieces, though it is possible to permute 2 pairs simultaneously. For any cube state, when solving it, you'll either eventually come to a fully solved cube, or you'll reach something which has a single corner twisted and/or a single edge flipped and/or a single pair of either corners or edges swapped. In any of these latter cases, the cube is not solvable and will need to be disassembled to return it to the solved state.
From the above, the cube group $H$ is an index 12 subgroup of the full cube group $G$, which means that 1/12 of the positions will be solvable. The cube group $H$ thus has order $8! \; 3^7 \; 12! \; 2^{10}$. Furthermore, if you know a bit of group theory, it's pretty easy to see that the full cube group is isomorphic to $\mathbb Z_3 \wr S_8 \times \mathbb Z_2 \wr S_{12}$. The edge and corner orientations are just the diagonal homomorphisms of their respective wreath products (which incidentally is the easiest way to prove the above lemma by showing that this gives you the same homomorphism), while the permutation parity is a bit more complicated to understand. Once you've understood these fully, you can compute that the cube group is isomorphic to $(\mathbb Z_3^7 \times \mathbb Z_2^{11}) \rtimes ((A_8 \times A_{12}) \rtimes \mathbb Z_2)$.
Finally, since it's relevant to my interests, I'll briefly note that much of what I said here still works for higher dimensional cubes. See, for instance, this MO question.
No comments:
Post a Comment