26
$\begingroup$

The period of a sequence of moves on a Rubik's Cube is the number of times it must be performed on a solved cube before the cube returns to its solved state. For example, a $90$° clockwise turn on the right face has a period of four; a $180$° clockwise turn on the right face and a $180$° turn on the top face has a period of $12$.

Let's make a $3\times3\times3$ Rubik's Cube group $G$. Each element of $G$ corresponds to each possible scramble of the cube - the result of any sequence of rotations of the cube's faces. Any position of the cube can be represented by detailing the rotations that put a solved cube into that state. With a solved cube as a starting point, each of the elements of $G$ directly align to each of the possible scrambles of the Rubik's Cube.

The cardinality of $G$ is $|G|=43{,}252{,}003{,}274{,}489{,}856{,}000=2^{27}3^{14}5^{3}7^{2}11$ and the largest order/period of any element in $G$ is $1260$. To elaborate, no algorithm needs to be performed on a cube more than $1260$ times to return it to the solved state.

Now let's say we extended $G$ for other sizes of cubes, so $G_3$ is the group of a $3\times3\times3$ and $G_4$ is a the group of a $4\times4\times4$. (If this isn't a valid naming convention, forgive me, I've just begun learning group theory).

Is there a way to find the highest order for any sequence of moves in $G_x$? For example, could I define a function $f$ such that $f(x)$ would give the highest order for any sequence of moves in $G_x$? What would $f$ look like? Would such a function be possible for any size of cube?

Thanks a lot in advance. Once again I apologize for any mistakes I've made; feel free to point them out or correct them.

$\endgroup$
  • 5
    $\begingroup$ How do you know that "the largest order/period of any element is $1260$"? This is an interesting fact! How many "algorithms" have period $1260$? $\endgroup$ – Zubin Mukerjee Aug 14 '17 at 5:30
  • 1
    $\begingroup$ The question refers to the highest order of an element of the Rubik Cube group. This has nothing to do with algorithms. $\endgroup$ – Derek Holt Aug 14 '17 at 9:36
  • 2
    $\begingroup$ IIRC (it was about 35 years ago when I tested it) the operation of turning the right face +90 degrees and then rotating the entire cube about the bottom/top axis +90 degrees (a sequence you can very mechanically repeat many times) has order 1260. I never tried to check that with group theory, but one of these days I might :-) $\endgroup$ – Jyrki Lahtonen Aug 14 '17 at 9:53
  • 4
    $\begingroup$ @JyrkiLahtonen Unfortunately, while it conflicts with the common usage of the word "algorithm" in other contexts, I think the use of "algorithm" to mean "sequence of moves" is very common in the Rubik's cube community ("cubing" community?). $\endgroup$ – Mark S. Aug 14 '17 at 14:28
  • 2
    $\begingroup$ I guess there is an absolute bound (maybe 48?) on the orbits of the faces of the $x \times x \times x$ so there must be an absolute bound on $f(x)$ which is presumably equal to $f(x)$ for large enough $x$. $\endgroup$ – Derek Holt Aug 17 '17 at 7:34
7
$\begingroup$

The maximum orders for a $n\times n\times n$ Rubik's cube group: \begin{align*}n=2: &\quad 3^2\cdot 5 = 45\\ n=3: &\quad 2^2\cdot 3^2\cdot 5\cdot 7 = 1260\\ n=4: &\quad 3^2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17 = 765765\\ n=5: &\quad 2^4\cdot 3^2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 23 = 281801520\\ n\ge 6: &\quad 2^4\cdot 3^2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23 = 5354228880\end{align*}

In general, there are five types of piece to consider:

  • For odd $n$, each face has a center. By convention, we treat these as fixed. If we don't, they can be rotated like a solid cube, for a copy of $S_4$. Highest order $4$, least common multiple $2^2\cdot 3=12$. As the largest possible order is divisible by $12$ for all odd $n\ge 3$, whether we include these doesn't affect the answer.
  • For any $n\ge 2$, there are $8$ corner pieces which can be permuted and rotated, a semidirect product of $S_8$ and $(\mathbb{Z}/3)^8$ - except that that the "sum" of those rotations is zero, dropping one factor of $3$ from the latter part. The order of an element is at worst $3$ times the order of an element of $S_8$. Highest possible order $15\cdot 3=45$, least common multiple $2^3\cdot 3^2\cdot 5\cdot 7$.
  • For any odd $n\ge 3$, there are $12$ centers of edges, which can be permuted and reflected. The number of reflections must also be even, for a semidirect product of $S_{12}$ and $(\mathbb{Z}/2)^{11}$. Highest possible order $60\cdot 2=120$, least common multiple $2^4\cdot 3^2\cdot 5\cdot 7\cdot 11$.
  • For any $n\ge 4$, there are $\left\lfloor\frac{n}{2}\right\rfloor-1$ orbits of 24 off-center edges, which can't change how far from the center of their edge they are. The pair of edges on each side are distinguishable due to being reflections of each other, and the group for each set of these pieces is a copy of $S_{24}$. Highest possible order $8\cdot 7\cdot 5\cdot 3 = 840$, least common multiple $2^4\cdot 3^2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23$.
  • For any $n\ge 4$, there are $\left\lfloor\frac{(n-2)^2}{4}\right\rfloor$ orbits of 24 off-center face pieces each. These can be rotated in their face, but not reflected; mirror images across a symmetry line within a face (in size $\ge 6$) are separate orbits. Each piece of the same color in one of these sets is indistinguishable, so that gets us an action of $S_{24}$, with $\frac{24!}{24^6}$ possible states. The possible orders are the same as in the previous case. In terms of what we need to solve the cube, there are three variants based on whether they lie on a symmetry line of a face - but they're all the same for the count we care about here.

So then, the highest possible order in any Rubik group is the least common multiple of all of these, namely $2^4\cdot 3^2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23$. This is achieved for all $n\ge 6$; we have at least six of the size-24 orbits, which we can use to produce orders of $16\cdot 5$, $9\cdot 11$, $7\cdot 13$, $17$, $19$, and $23$.

Now, all of this assumes that we can modify the pieces in each orbit independently. That isn't quite true - several combinations must be even permutations. First, for odd $n$, the combined permutation of corners and edge centers is even; they're modified by face rotations, each of which is a 4-cycle of edges and a 4-cycle of corners. Second, for $n\ge 4$, the combined permutation of the corners and an orbit of pieces on face diagonals is even. Next, for $n\ge 6$, each mirrored pair of orbits of off-center face pieces must have a combined even permutation; each face rotation and each relevant slice rotation is a 4-cycle in each of the orbits. Finally, for odd $n\ge 5$, the combined permutation of off-center edge pieces, pieces on face diagonals, and pieces on face midlines at a fixed distance from the center is even. These parity restrictions are the only additional restriction; other than that, the orbits can be manipulated independently.
How does this change things? For the $n\ge 6$ case, all we have to do is implement the order $16\cdot 5$ piece as the product of a $16$-cycle, a $2$-cycle, and a $5$-cycle. Then all of the permutations we're working with are even, so there aren't any problems. In the smaller cases, we'll have to check.

For $n=2$, only the corners matter, and the highest order is $45$.
For $n=3$, we have corners and edge centers. With $17$ possible orders for the first and $31$ for the second, we can just scan all of the possible combinations. The highest LCM is $2520$, from order $45$ (3-cycle, 5-cycle, rotations in the 3-cycle don't add to zero) in the corners and order $56$ (4-cycle, 7-cycle, reflections in the 4-cycle don't add to zero) in the edges. This, however, doesn't pass the parity check; the combined permutation is odd, and there's no wiggle room to change that. That leaves us dropping down to the second-highest possibility of $1260$, possible in several ways ($45$ and $28$, $45$ and $84$, $35$ and $36$, $70$ and $36$). Three of those fail the parity check, leaving only the pair of order $45$ in the corners and order $28$ (Two 2-cycles, a 7-cycle, reflections in at least one 2-cycle don't add to zero) in the edges. Highest order $1260$, as previously noted.
For $n=4$, we have the corners, one orbit of off-center edges, and one orbit of off-center face pieces. With over a hundred possible orders in $S_{24}$, finding the least common multiple isn't the easiest search. Pruning everything with an order that divides another gets that down to a manageable total of $27$, and $5$ for the corners. Running it in the spreadsheet I've been using, the LCM is $765765=3^2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17$; $45$ in the corners, $11\cdot 13$ in the edges, and $7\cdot 17$ in the faces. Checking parity... all the pieces are odd permutations, so we'll actually have something of that order.
For $n=5$, we have corners, edge centers, three size-24 orbits, and two parity restrictions that cross orbits. The best I've got here is $2^4\cdot 3^2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 23 = 281801520$; it could use an independent check, but I'm pretty sure it's right. The three size-24 orbits get us orders of $23$, $7\cdot 17$, and $11\cdot 13$ while the corners give us order $45$ and the edges give order $16$ (an 8-cycle and a 2-cycle, with an odd number of reflections in the 8-cycle). They're all odd permutations, so the parity checks pass.
For $n\ge 6$, as previously noted, we reach the maximum possible order $2^4\cdot 3^2\cdot 5\cdot 7\cdot 11\cdot 13\cdot 17\cdot 19\cdot 23 = 5354228880$.

$\endgroup$
-1
$\begingroup$

Notations are from https://ruwix.com/the-rubiks-cube/notation/

$RY$ is an element of order 1260. It's easy to check that $(RY)^{36}$ keeps all the corners intact but permutes the edges in 2 disjoint groups of order 5 and 7, respectively. So, the total order is $36*5*7=1260$.

$RY$ applied 36 times - https://ruwix.com/saved-rubiks-cube/?moves=RYRYRYRYRYRYRYRYRYRYRYRYRYRYRYRYRYRYRYRYRYRYRYRYRYRYRYRYRYRYRYRYRYRYRYRY

$\endgroup$
  • 3
    $\begingroup$ How does this determine the highest order of a larger group, e.g. one for a 5x5x5? $\endgroup$ – MD XF Feb 21 '18 at 3:59

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.