# How do I find a square root of a Rubik's cube?



## unixpickle (May 28, 2013)

I recently came up with a Rubik's configuration which, when applied twice to a 3x3x3 cube, will put it in the super flip (R' F' D R D B2 D F L F' L' F2 R2 U D L2 F2 [17 HTM]). What I found is clearly not the only such square root for the super flip. However, when you look at something simple like R, it seems that a square root is not quite as obvious. In fact, with the following reasoning, I do not believe that there exists a square root for an R turn:

- Consider representing just the position of the corners in an 8x8 permutation matrix. Then, doing an R turn will result in a permutation matrix with a negative determinant. If such a matrix, let's call it A, is the square root of this permutation matrix, then A would need a complex determinant in order for det(A)^2 = -1. Thus, such a square root cannot exist.

With this in mind, I can see myself perhaps finding the square root of a cube group element by representing it's corners and edges as matrices and diagonalizing them to find the square roots. Has anybody fully implemented or developed a method for doing such a thing? Is there even a use for finding such roots of cube group elements?


----------



## irontwig (May 28, 2013)

Well after R the parity is odd, so of course you couldn't solve this with doing a certain sequence twice (which what I assume you mean) since that would involve a even number of quarter turns.


----------



## Lucas Garron (May 28, 2013)

In the case of the superflip, you need a permutation such that every sticker maps to its opposite sticker two spots further in the cycle. This happens if you group the edges into 6 pairs any way you want, and swap each pair with parity.

I'm not sure taking square roots of matrices makes sense here. Consider (1, 2, 3), whose square root is (2, 3, 1). Taking the square root of the matrix in Mathematica gives me a matrix with fractions. Wikipedia says there should be multiple square roots, but I'm not sure if finding them all is efficient.

I think it's better to look at permutations. That already tells you some interesting things. For example, there are a lot of swaps possible, so the identity has a *lot* of square roots. It also shows you how to construct things:

If you have a cycle C with k pieces where k is odd and the cycle doesn't have parity, then \( C^k = I \), so \( C^{k+1} = C \) and \( C^{(k+1)/2} = sqrt(C) \). You've already seen an example of parity in an even cycle, etc.


----------



## qqwref (May 28, 2013)

Yeah, it's like irontwig said. In a little more detail, ignoring orientation, if you do any scramble twice, you will end up with an even permutation of the pieces. That means that any position with an odd permutation (that is, solved with an odd number of quarter turns) has no square root.

But I'm curious now... do all even permutations have a square root? Some observations:
- Here's one for a 2-2 cycle (specifically H perm): (D2 B2 F2 U L2 R2 D' F2 L2 R2 F2)2
- If O^2 = P, then (Q O Q')^2 = Q P Q'.


----------



## unixpickle (May 28, 2013)

Lucas Garron said:


> If you have a cycle C with k pieces where k is odd and the cycle doesn't have parity, then \( C^k = I \), so \( C^{k+1} = C \) and \( C^{(k+1)/2} = sqrt(C) \). You've already seen an example of parity in an even cycle, etc.



I used your suggestion to find a square root of (R U): L U2 R2 U' L' D R' U2 R D' R U2 B2 R2 B2 R2 (16 HTM). It is obvious that your method is efficient and straight forward, at least for cubes which have an odd order in the cube group.

However, there are some situations which I am still unsure about. For example, the sequence R L has an even parity with respect to both the edges and the corners. However, R L has a cyclic order of 4, so (k+1)/2 = 2.5, and you can't computer (R L)^2.5 without knowing it's square root in the first place. Does this mean that a square root does not exist for R L?


----------



## qqwref (May 28, 2013)

(R D U' B2 F2 D U')2 = R L.

I'm not sure what the best way to deal with even cycles is.


----------



## jaap (May 28, 2013)

Consider a permutation consisting of just a 2-cycle and a 4-cycle. I claim that such a permutation has no square root.

Let p = (12)(3456), and suppose that q were its square root, i.e. q[SUP]2[/SUP] = p.
Then q[SUP]4[/SUP] = p[SUP]2[/SUP] = (35)(46).
So q[SUP]4[/SUP] acts as the identity on items 1 and 2, but q[SUP]2[/SUP] does not.
Therefore q must behave as a 4-cycle on the items 1 and 2, i.e. it has a disjoint cycle (1 a 2 b) for some items a and b not equal to 1 or 2.
But then q[SUP]2[/SUP] must also have the disjoint cycle (a b).
However p= q[SUP]2[/SUP] only has the one 2-cycle (1 2).
Therefore no such q exists, and p does not have a square root.

I'm pretty sure you can generalise this a bit to prove that the only permutations with square roots are those for which all the even length cycles come in pairs.


----------



## qqwref (May 28, 2013)

Ah, great point. When you square a cycle of length N, you either get another cycle of length N (if N is odd), two cycles of length N/2 (if N is even and at least 4), or no cycles (if N=2). So only cycle types that can be formed only from odd cycles and pairs of cycles of the same length can have square roots.

I also think other cycle types may be impossible due to the way cubes are constructed. Imagine a pair of edge 6-cycles plus a corner 7-cycle. The only possible square root includes a 12-cycle of edges and a 7-cycle of corners. Unless we are allowed to move centers around, this position is impossible, as there are not enough free pieces we can make 2-cycles out of to fix the parity problem.


----------



## KongShou (May 28, 2013)

qqwref said:


> Ah, great point. When you square a cycle of length N, you either get another cycle of length N (if N is odd), two cycles of length N/2 (if N is even and at least 4), or no cycles (if N=2). So only cycle types that can be formed only from odd cycles and pairs of cycles of the same length can have square roots.
> 
> I also think other cycle types may be impossible due to the way cubes are constructed. Imagine a pair of edge 6-cycles plus a corner 7-cycle. The only possible square root includes a 12-cycle of edges and a 7-cycle of corners. Unless we are allowed to move centers around, this position is impossible, as there are not enough free pieces we can make 2-cycles out of to fix the parity problem.



Qq how fast can you type?


----------



## qqwref (May 28, 2013)

Around 120wpm or so, but it depends, and I can't decide what to write that fast 

Here's a position from Cube Explorer with the cycle types I mentioned: L2 U' L2 U' B2 U L2 B2 F2 U B' R2 U2 R2 B' U2 (16f)


----------



## cuBerBruce (May 29, 2013)

qqwref said:


> I also think other cycle types may be impossible due to the way cubes are constructed. Imagine a pair of edge 6-cycles plus a corner 7-cycle. The only possible square root includes a 12-cycle of edges and a 7-cycle of corners. Unless we are allowed to move centers around, this position is impossible, as there are not enough free pieces we can make 2-cycles out of to fix the parity problem.





qqwref said:


> Here's a position from Cube Explorer with the cycle types I mentioned: L2 U' L2 U' B2 U L2 B2 F2 U B' R2 U2 R2 B' U2 (16f)



As qqwref mentioned, no square root for this will exist in the standard cube group <U,D,R,L,F,B>, but there could be a square root if we are allowed to permute centers. That is, if we use the extended group that cubing notation is based on. Indeed there is:
R2 D2 R2 U F2 L D U2 b2 D' B' R F' R d D B L D2

(lower case representing double-layer turns)


----------



## unixpickle (Jun 1, 2013)

So I finally sat down and wrote a program to take nth roots of elements in the cube group. The program itself figures out the positions and orientations of the edges and corners for the root rather than attempting to represent the square root with the standard group basis (i.e. <R, U, L, D, B, F>). Of course, the program checks parity and validates the orientations of the edges and corners. With this program, I have calculated a few roots as a proof of concept:

(R2 U2)3 = (F2 R D R' U2 R D' R F R2 U2 F2)2
sqrt(E Perm) = B L2 F2 U B' U F2 U R2 F U2 B2 U' L2 B2 D2 F2 D
(R2 U2)3 (L2 D2)3 = (U2 F L2 B' L2 D2 L2 B' U2 B D2 R2)3

Excuse the lengths of some of those root algorithms. While my program does find as many roots as you want it to, it does not point out the ones with the briefest solutions since it does not itself _find_ solutions.

For any programmers who are interested, the source to my root taker is part of my Rubiks solver project: https://github.com/unixpickle/Rubiks/tree/master/math/roots. Documentation coming soon!


----------



## cuBerBruce (Jun 2, 2013)

I noticed today that the latest version of GAP has a built-in function called NthRootsInGroup that supposedly will return a list of all elements of a given group that are nth roots of a given element of the group (and for a given n, of course). That is, an element from the list raised to the power of n will yield the element specified. It appears to have problems with very large groups like the Rubik's Cube group, however. It appears to first need to calculate all the conjugacy classes of the group, and that alone can require a lot of time and a lot of memory.


----------



## cuBerBruce (Jun 5, 2013)

Some results I've obtained with GAP for the number of square roots within <U,D,R,L,F,B>:

There are 1920 square roots of R L.

There are 632 square roots of U R.

There are 632 square roots of U R'.

There are 1592 square roots of (U R)3.

There are 533792 square roots of (U R)5.

There are 272 square roots of L F R B.

There are 374016 square roots of F U L2 U L2 D2 F' D U2 F R2 D B' L2 D2 B R2 U.

There are 0 square roots of R U R' U'.


----------



## qqwref (Jun 5, 2013)

Wait, we can't make twisted corner cycles? I'm playing around with them and I don't see any easy way, but I'd like to see some kind of proof.


----------



## cuBerBruce (Jun 5, 2013)

qqwref said:


> Wait, we can't make twisted corner cycles? I'm playing around with them and I don't see any easy way, but I'd like to see some kind of proof.



I think to have a square root for a position with twisted corner cycles, you need two same-length cycles with the same twist direction. You'll need at least another twisted corner (or pair of twisted corner cycles) to balance the twists.

EDIT:
The above isn't quite right. It essentially only applies to the situation of having two misoriented 2-cycles. Basically odd-length misoriented cycles don't seem to be a problem.

For misoriented 2-cycles, you need to have a 4-cycle that when squared gives two 2-cycles. However, that always seems to generate two misoriented 2-cycles that are both twisted in the same direction as the 4-cycle. This means there must be another piece or cycle that is misoriented so that the net twist is zero (mod 3).

Similarly for two misoriented 4-cycles, you would need both cycles to be twisted the same direction. But since all 8 corners are used in the two 4-cycles, you have no remaining corners to fix the net twist. So I believe you can't have a square root for any position having two misoriented 4-cycles of corners.


----------



## Christopher Mowla (Jun 5, 2013)

qqwref said:


> Wait, we can't make twisted corner cycles? I'm playing around with them and I don't see any easy way, but I'd like to see some kind of proof.


Probably cuBerBruce answered your question, but, assuming that you were asking about the corners for the sequence


cuBerBruce said:


> There are 0 square roots of R U R' U'.


I apologize for posting material that you probably already know, but just in case you were asking about this and didn't catch everything I have in this post...

I made a model of the problem, and it basically came down to a simple puzzle. Before I can describe the puzzle, I have to give you my numbering system and other needed information so that I can construct a step by step transition from the problem to my "puzzle".

Let ufr = 1, ubr = 2, ubl = 3, ufl = 4, and dfr = 5 and let {1,2,3,4,5} = the solved state of those corner pieces.

So the sequence R U R' U' generates the corner cycle {5,3,2,*4*,1} (4 is not affected).

The 4-cycle (3→5→2→1→3) repeated twice on the solved state will generate {5,3,2,4,1}. That is,
{1,2,3,4,5} solved state
{2,5,1,4,3} (executed once)
{5,3,2,4,1} (executed again)

The signs of each of the corner pieces 1,2,3 and 5 (after we have executed this 4-cycle to the solved state) are:
(their sign after the 4-cycle is executed the first time)
+
(sign of the slot they move to when the 4-cycle is executed for the second time. That is, the sign of the piece (after the 4-cycle is executed the first time) which was originally in the slot (in the solved state before the 4-cycle was executed at all) they move to on the second iteration).

So, for example, my potential square root algorithm for R U R' U' is:
U2 F' U2 F U2 F U2 R U R' U2 F L F L' F

So the signs of each of the corner pieces 1, 2, 3, and 5 after we execute this on a solved cube are as follows:
2: -
5: -
1: -
3: 0

When we repeat the 4-cycle (3→5→2→1→3), we can represent it as the following matrix (each row represents an application of the 4-cycle of my potential square root algorithm).

\( +\underline{\begin{matrix}
2^{-} & 5^{-} & 1^{-} & 3^{0} \\
5^{-} & 3^{0} & 2^{-} & 1^{-} \\
\end{matrix}} \)

which, if we add the signs of the pieces in the first and second rows in each column and assign them to the numbers in the second row of each column, we get

\( \begin{matrix}
5^{+} & 3^{-} & 2^{+} && 1^{-} \\
\end{matrix} \)

Executing my potential square root algorithm twice on a solved cube, we get the same result above (which we should, since my model models my potential square root algorithm).

Comparing this result to the effect of executing R U R' U' on a solved cube, we should, but do not, have

\( \begin{matrix}
5^{-} & 3^{-} & 2^{0} & 1^{-} \\
\end{matrix} \)

So the challenge/"puzzle" is to change the signs of the numbers 1, 2, 3, and/or 5 in the above 2x4 matrix so that the sum of the signs of the two rows for each column sum to the above signs (where + + = -, + - = 0, etc.). If we change the sign for 3 in the first row, we must change the sign of 3 is in the second row, etc.

You will see that there are no solutions which yield our desired result. This might be sufficient proof.

Lastly, note that changing the signs of the numbers 1, 2, 3 and 5 assumes that we include a shared orientation with some corner piece besides 1, 2, 3, and 5, should the sum of the signs of 1, 2, 3, and 5 not be in mod 3 (because these 4 corners pieces in my potential square root algorithm are in mod 3 right now). But if the sum is still in mod 3, then we can just assume that we have twisted them with each other in our potential square root algorithm.


----------



## TMOY (Jun 5, 2013)

Much shorter proof: since a square root of R U R' U' includes a disorienting 4-cycle of corners, it must include another disorienting cycle of corners, and that cycle must be of order 2. But the order of any disorienting cycle of corners is a multiple of 3, hence a square root of R U R' U' cannot exist. QED


----------

