13
$\begingroup$

Associated to the Rubik's cube is a group as described in this Wikipedia article: $G = \langle F, B, U, L, D, R\rangle$. For example, the element $F$ corresponds to rotating the front face clockwise by $90$ degrees.

According to the article the order of the group is: $2^{27} 3^{14} 5^3 7^2 11$.

I have come across several places (for example here) where this order has been found by just counting various ways to arrange edges and such. Is there a nice way to compute the order by appealing to more "group theoretic" tools?

$\endgroup$
10
$\begingroup$

Most explanations of the order of the cube group don't use a group-theoretic wording because it is felt to be easier to understand it in more concrete terms, given that the cube is a physical object.

But if you want to, we can certainly phrase the same calculation in more abstract group-theoretic language.

In that case, we could start by defining $G$ to be a certain subgroup of the group $S_{54}$ of permutations of all the color stickers, given by its six generators.

$G$ acts on the 20 movable cubies, so there's a homomorphism $G\to S_{20}$. Its kernel is a group of $H$ operations that twist and flip cubies in-place, and the quotient is the group of legal cubie permutations. To count the order $G$ itself we multiply the order of the kernel with the order of the quotient.

The quotient, as a subgroup of $S_{20}$ turns out to be $A_{20}\cap(S_{12}\times S_{8})$, which we can prove by noting that each of the 6 generators is in this subgroup, and finding a set of generators for $A_{20}\cap(S_{12}\times S_{8})$ that can be realized as concrete cube operations.

The kernel $H$ (the group of twists-and-flips that don't permute the cubies) is a subgroup of $G$, but is is clearly abelian and isomorphic to a subgroup of $(C_2)^{12}\oplus(C_3)^8$, and I will view it as such henceforth. $H$ contains each of its projections to $(C_2)^{12}$ and $(C_3)^{8}$ -- namely, they are $\{x^3\mid x\in H\}$ and $\{x^4\mid x\in H\}$, respectively (this can be generalized to any subgroup of a direct sum of abelian groups of coprime orders) -- and is therefore their direct sum, and its order is the product of the orders of the components.

Consider the intersection with the corner-twist group $(C_3)^8$. We can count it by viewing it as a subspace of $(\mathbb F_3)^8$ and applying linear algebra (and it is a subspace: multiplying by an scalar from $\mathbb F_3$ just corresponds to iterating the operation). It is easy to show that it has dimension $\ge 7$, by showing 7 linearly independent elements, say, combinations that turn the FRU corner together with each of the 7 other ones. So if only we can show that it has dimension $<8$, it will follow that it and has $3^7$ elements.

To show this, assign a canonical orientation of each cubie in each location as described in this answer. Each configuration of the full cube now describes an element of $(\mathbb F_3)^8$, with components given by how the cubie that happens to be found in a given position is twisted from its canonical orientation. The entire $G$ then acts on $(\mathbb F_3)^8$, and each action preserves the hyperplane $x_1+x_2+\cdots+x_8=0$ (which can be checked for each of the six generators). The corner-twist subspace is contained in the orbit of $(0,0,\ldots,0)$, which is contained in the hyperplane, and therefore cannot be all of $(\mathbb F_3)^8$.

The handling of the edge-flip group is the same, mutatis mutandis.


Is all of this more enlightening than the usual more concrete way of counting? I doubt it.

$\endgroup$
  • 1
    $\begingroup$ +1 Exactly, I was just about formulating something similar (that the usual counting boils down to counting the number of orbits of the - by definition - faithfully acting Rubik group, xada, yada) $\endgroup$ – Hagen von Eitzen Jan 31 '15 at 21:57
5
$\begingroup$

For the mere purpose of counting the number of positions, I can't see why a group theoretical method would be more efficient as the conventional approach.

However, if you are interested to know what those positions "look like", then perhaps a group theoretical approach can give you the details you are looking for.


One thing that comes to my mind is some research I did with Bruce Norskog about the number of last layer OLL cases for the nxnxn cube. Using the Fridrich (first layer edges, first two layers, orientation of last layer, and permutation of last layer) method, there are 57 3x3x3 cases for orienting the last layer (making all of the final layer yellow, but not necessarily solving the cube). I wanted to know how many such cases there are in general for the nxnxn cube.

Bruce came up with a method to compute the number of last layer OLL cases for the nxnxn cube by calculating raw cases and assigning a vector function to describe relationships. I used math to find a closed formula of his algorithm. (This is an alternate version of my formula, which you can view at Wolfram Alpha.)


As another nxnxn cube last layer example illustrating how we can visualize what the cases are rather than just counting their number alone, I calculated the number of distinct 3-cycles of wing edges per set (orbit) of wing edges in the last layer of the nxnxn cube. 3-cycles. I did a follow-up and calculated the number of 4-cycles and 2 2-cycles of wing edges.


Now, I know you are specifically just talking about calculating all possible states of the entire 3x3x3 cube, and therefore now I shift into that.

No matter what method you use to compute the number of positions, you must take into account the "cube laws" of permutation and orientation. Therefore all explanations you have seen which mention that there are only 3^7 corner orientations, 2^11 middle edge orientations, and only 1/2 of corner or middle edge permutations are possible (depending on your chosen perspective), there are no "group theoretical methods" to bypass this. These are the laws of "arithmetic" which every theoretical study of the cube assumes to be true.


Since group theory is centered around taking advantage of symmetry, I believe if someone (maybe you) comes up with an alternate approach for computing the number of positions of the 3x3x3 cube,

  1. It must assume the cube laws to be true.
  2. It most likely will involve programmatically computing "raw" cases (by first computing all possible raw cases and then using symmetry to minimize the number of raw cases) for every possible combination of cubie slots (e.g., the number of 3-cycles, 2 2-cycles and 4-cycles calculation) and cube slot orientations (e.g., the number of OLLs calculation), where the number of permutations of each cycle type are taken into account for each "structure" combination of slots and slot orientations.

As I've stated at the beginning of this response, merely calculating how many positions there are is one thing, but describing what they are is an entirely different topic altogether.


Perhaps what you're looking for is a study on representation theory of the cube.

I have recently proved (but have not published or shown my proof publicly) that all elements in the commutator subgroup of the nxnxn cube has a commutator length of one. (This means that there exists a single commutator move sequence which generates/solves exactly half of all 43 quintillion positions for the 3x3x3 cube, for example. Here's an example solve of a random 3x3x3 position, and here's an example solve of a random 4x4x4 position.)

My paper shows that there are 1002 corner positions which can represent all (8!/2)(3^7) even permutation corner positions and 3351 middle edge positions can represent all (12!/2)(2^11) even permutation middle edge positions. Therefore, in essence, the 3x3x3 Rubik's cube group has "only" about 2(1002)(3351) different representations, when you actually break them down and exploit symmetry to the maximum.

The reason I am mentioning this is because I had to construct this set of 1002 corner and this set of 3351 middle edge positions from taking into account symmetry. I can also simply calculate how many positions each of the corner cases represent, for example. When I sum them all together, I get (8!/2)(3^7).


If anything I mentioned in this response sounds like what you're looking for, please comment and let me know.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.