understand parity

[Die_d00pel_Null]

Hi

I just got a 4x4x4 cube and I was able to solve it to a certain point without having to watch a tutorial. But once it came to parity I had no idea what to do.
I know I could just memorize the algorithms for the parity cases but I would very much like to understand what I'm doing there. So I got a few questions:

1. What exactly is parity and how does it occur? ( why does it only occur with a 4x4x4 and not a 3x3x3?)
2. What concept is behind these algorithms which can solve parity?

-Tim

 

[cmhardw]

I'm not trying to come across as rude, but your question has been asked many times before. I went through and searched the term "parity" and found the threads that directly related to the parity on the 4x4x4. This parity is the same concept as for 5x5x5 and on the larger cubes. There is also a different kind of parity that you get when trying to solve as a 3x3x3 cube at the end of the reduction step on any even sized cube.

Hope these help,
Chris

http://www.speedsolving.com/forum/showthread.php?t=9382&highlight=parity

http://www.speedsolving.com/forum/showthread.php?t=8494&highlight=parity&page=2

http://www.speedsolving.com/forum/showthread.php?t=7462&highlight=parity

http://www.speedsolving.com/forum/showthread.php?t=7399&highlight=parity

http://www.speedsolving.com/forum/showthread.php?t=7198&highlight=parity

 

[AJelsma]

Parity can be explained very fancily but here is your questions
1. Parity is basically something on the cube (or puzzle) it just is the way the puzzle has been made (all the same) it occurs on a 3x3x3 in times like bld solving
2.just do the algs and be happy

 

[Die_d00pel_Null]

I looked into the threads you posted but most of them just showed the algs and how/when you should apply them to your cube.
I don't really believe that nobody understands what they really do so why couldn't somebody just explain it to me?!

I found some scattered information about parity on some sites and from what I understood its all about the center pieces which can move on the 4x4x4 and not on the 3x3x3.
So I got the theory that these parity algs let some of the center pieces switch positions while solving the incorrect pieces. So you do get the even number of swaps but you just can't see them because the centers look identical. Is this correct?

 

[Lux Aeterna]

The term is borrowed from algebra (abstract algebra, not the silly solve-for-x high school algebra sense of the word.) Put very simply, the Rubik's cube is a permutation group. Elements of a permutation group (i.e. possible states that the cube can attain) can be described as a product of various cycles (i.e. these two pieces need to switch positions, these five pieces all need to occupy their neighbor's position, etc).

So let's say you have a scrambled cube. That position has a "unique" decomposition into various cycles, and if you apply all those cycles in the right order, the cube becomes solved. (Well, technically you're applying the inverse of those cycles, for obvious reasons, but that doesn't matter). Now, in that cyclic decomposition there's going to be some number of two element cycles, or transpositions, where two pieces just have to swap places with each other. Here's where parity comes in. If there's an even number of transpositions in the given state, we call that an even permutation, and if there's an odd number of transpositions in the given state, we call that an odd permutation. That's all parity is, it's the sign of the permutation, even or odd.

Now, on the 3x3 you can ONLY solve the cube if the parity is even. For example, if you swap two edge pieces in the last layer, that's unsolvable, but if you swap two pairs of edges, then you can solve it (i.e. Z-perm or H-perm). On the 4x4, you have more freedom to move the cubies around, and in particular you have enough freedom to get to odd parity states. So when you use your favorite reduction method and turn your scrambled 4x4 into a scrambled 3x3, there's a chance that that scramble would be unsolvable as a 3x3 cube. So you need to use special algorithms to fix those cases which necessarily have no analog on the 3x3.

Hope that helped.

 

[cmhardw]

Take a solved 4x4x4 cube and do the turn r (only the inner right layer once clockwise). You now have edge parity. What parity means is that you have to perform an odd number of transpositions (2-swaps) to solve the edges again. The centers have no concept of parity on the 4x4x4 because they are split into 6 groups of 4 indistinct pieces.

To solve edges after following my example you would swap the UFr and UBr edges. Then you would swap the UBr and BDr edges. Then you would swap the BDr and FDr edges. This solves the edges again, but you would have to do three 2-swaps (transpositions) to do so. That means you had parity.

The reason parity comes up in the edges of a 4x4x4 is not because two centers are switched (even though this is not noticeable because of the indistinctness of some centers). Parity comes up because of one of the following situations below.

1) The cube was scrambled with an odd number of inner slice quarter turns, and you solved centers with an even number of inner slice quarter turns. Overall this is a net odd number of inner slice quarter turns, resulting in edge parity.

2) The cube was scrambled with an even number of inner slice quarter turns, and you solved centers with an odd number of inner slice quarter turns. Overall this is a net odd number of inner slice quarter turns, resulting in edge parity.

Even if you did have a supercube 4x4x4 and you swapped two centers, you would not create parity in the edges. To keep the cube still solvable you would have also had to have swapped 2 corners. The parity of the corners and the parity of the centers must match on a supercube 4x4. The parity of the edges is completely independent of the other pieces on a supercube 4x4x4. This is not true for any larger supercube, which as a side note is why I think the 4x4x4 supercube is the most beautiful cube from a mathematical viewpoint.

Chris

 

[Johannes91]

(Isn't odd/even parity more correct terminology than parity/no parity?)

The reason parity comes up in the edges of a 4x4x4 is not because two centers are switched [..]

Yep, because they might not be (I know you know this, but just to clarify for others).

The parity of the edges is completely independent of the other pieces on a supercube 4x4x4. This is not true for any larger supercube

Are you sure? I thought it's true for all even big cubes.

 

[cmhardw]

The parity of the edges is completely independent of the other pieces on a supercube 4x4x4. This is not true for any larger supercube

Are you sure? I thought it's true for all even big cubes.

Yep, I've even sketched proofs of this on paper :-D That is what fascinates me so much about the 4x4x4 supercube. Back when I was trying to come up with a general formula for the number of combinations to the n x n x n supercube (http://tinyurl.com/nggpn) I was wondering how knowing the parity of every edge orbit as well as the parity of the corner orbit affected the parity of all the center orbits. It turns out that it completely determines the parity of every single center orbit on the cube if you know the parity of all edge orbits as well as the parity of the corner orbit.

Imagine a n x n x n supercube where n is even and greater than 2. Let's say the 6x6x6 supercube for ease of picturing. Now we will do the turn r[1] or in standard notation I mean R' 2R. There are 4 different center orbits on the cube. I will say that the piece occupying position Ur[1]f[1] is orbit 1. The piece occupying position Ur[1]f[2] is orbit 2. The piece occupying Ur[2]f[2] is orbit 3, and the piece occupying Ur[2]f[1] is orbit 4.

Notice that there are 8 pieces from orbit 1 on the r[1] slice. I have 4 cycled four of them and four cycled the other four leaving two 4-cycles which is an even permutation. I have not affected any pieces from orbit 3 with the r[1] turn.

Now look at orbits 2 and 4. There are 4 pieces from orbit 2 on the r[1] slice, and I have 4 cycled them. There are 4 pieces from orbit 4 on the r[1] slice and I have four cycled them. This creates an odd permutation in both orbit 2 and orbit 4. So I have changed the parity of two center orbits by changing the parity of the r[1] edge orbit. So the r[1] edge orbit is not independent of the rest of the cube. I could argue the same way for the r[2] edge orbit. Notice also that I have accounted for the expected 16 centers that are on the r[1] slice.

Basically, centers on a supercube are broken into 2 types. "x" centers and "not x" centers. X centers are ones that are in a diagonal line with the corners. Notice that on a 4x4x4 supercube that the centers are "x" centers.

You could prove the general case by noticing that any slice on the n x n x n supercube (n is a natural number greater than 3) contains one orbit of "x" centers and n-4 orbits of "not x" centers. However, you may have noticed that this does not apply to the centralmost row on an odd n x n x n supercube, which contains only (n-3)/2 "not x" centers. Let's agree to ban the turning of the centralmost slice of an odd n x n x n cube, just like we do for counting the number of permutations on a 3x3x3 cube. Now to be more precise we can prove that changing the parity of any given edge orbit will change the parity of every "not x" center orbit on that slice. It is for this reason that the parity of the edges are not independent of other pieces on the general n x n x n supercube. The 4x4x4 supercube is the only exception to this, and this is because it has no "not x" centers at all, only "x" centers.

I've done a lot of thinking about the orbits for centers for supercubes. What prompted me was attempting the 5x5x5 supercube blindfolded. These are the conclusions I came too. I have hand written proofs of these claims sketched out, but I don't know how to truly formalize them to be 100% mathematically rigorous. I have a neat, and simple, method using matrices to determine the parity of any given "not x" center orbit once you know the parity of all edge orbits and the parity of the corners if you are interested. Lastly, notice I only mentioned "not x" centers. This is because the parity of the "x" centers will always match the parity of the corners. I suppose that writing up this process in a very precise way would constitute a constructive proof of my claims above, which is how I have been approaching the most formal version of my proof thus far.

Chris

 

[Stefan]

So let's say you have a scrambled cube. That position has a "unique" decomposition into various cycles, and if you apply all those cycles in the right order, the cube becomes solved. (Well, technically you're applying the inverse of those cycles, for obvious reasons, but that doesn't matter). Now, in that cyclic decomposition there's going to be some number of two element cycles, or transpositions, where two pieces just have to swap places with each other. Here's where parity comes in. If there's an even number of transpositions in the given state, we call that an even permutation, and if there's an odd number of transpositions in the given state, we call that an odd permutation.

Wrong.

The parity of the edges is completely independent of the other pieces on a supercube 4x4x4. This is not true for any larger supercube

Are you sure? I thought it's true for all even big cubes.

Oblique centers.
(This is Johannes, I doubt he needs a lengthy complicated explanation)

 

[AvGalen]

The parity of the edges is completely independent of the other pieces on a supercube 4x4x4. This is not true for any larger supercube

Are you sure? I thought it's true for all even big cubes.

Oblique centers.
(This is Johannes, I doubt he needs a lengthy complicated explanation)

But normal mortals (like me) are reading this as well and really appreciated Chris thorough explanation

 

[cmhardw]

The parity of the edges is completely independent of the other pieces on a supercube 4x4x4. This is not true for any larger supercube

Are you sure? I thought it's true for all even big cubes.

Oblique centers.
(This is Johannes, I doubt he needs a lengthy complicated explanation)

But normal mortals (like me) are reading this as well and really appreciated Chris thorough explanation

I know Johannes is very strong on his math, and everything cube math related. I wasn't try to imply that I thought he didn't know most of what I was writing, but I wanted to write out the post in case others were following and also to formulate my own thoughts and make sure it made sense when saying it out loud.

Haha
[insert joke about Hardwick's ridiculously long posts here]
*bum dum* *ching*

;-)

--edit--
actually now that I think about it, part of the reason for such a long post is that I was making a broad claim about all n x n x n supercube sizes, and the 4x4x4 supercube being the one exception to this, so I felt compelled to at least provide a detailed explanation of my proof of that claim.

And yes I know that in general I suck at elegant proofs. However if anyone is interested in my matrix method for determining parity of the oblique center orbits once you know the parity of all edge and corner orbits, I will describe it. I feel it is a fairly elegant way to show that the parity of every center orbit is determined once you know the other parity conditions I just mentioned. Hopefully this is at least a step in the direction of making this proof short, and concise.

Chris

 

[Die_d00pel_Null]

Take a solved 4x4x4 cube and do the turn r (only the inner right layer once clockwise). You now have edge parity. What parity means is that you have to perform an odd number of transpositions (2-swaps) to solve the edges again.

Does that mean that you can solve every parity case by just doing r and then solve the cube with commutators?

 

[cmhardw]

Does that mean that you can solve every parity case by just doing r and then solve the cube with commutators?

Absolutely, you can solve the 4x4x4 parity created when two edges are swapped at the end of reduction (OLL parity) using this approach. In fact this works on any n x n x n cube. If you have parity in an edge orbit, do one quarter turn of one of those inner slices and you could solve the rest via commutators.

If you want a slightly, but not much more, elegant way to do that use this algorithm:
[r' (U2)]*4 r'

This will scrambled and resolve the centers using 5 inner slice quarter turns, an odd number, thus changing the parity. You can now solve the rest of the edges again using reduction, or via commutators. This is a very short, very simply intuitive algorithm for fixing parity. However, it is extremely inefficient for speedsolving.

Chris

 

[AvGalen]

Does that mean that you can solve every parity case by just doing r and then solve the cube with commutators?

Absolutely, you can solve the 4x4x4 parity created when two edges are swapped at the end of reduction (OLL parity) using this approach. In fact this works on any n x n x n cube. If you have parity in an edge orbit, do one quarter turn of one of those inner slices and you could solve the rest via commutators.

If you want a slightly, but not much more, elegant way to do that use this algorithm:
[r' (U2)]*4 r'

This will scrambled and resolve the centers using 5 inner slice quarter turns, an odd number, thus changing the parity. You can now solve the rest of the edges again using reduction, or via commutators. This is a very short, very simply intuitive algorithm for fixing parity. However, it is extremely inefficient for speedsolving.

Chris

[r' (U2)]*4 r' works and in this high-quality I like the way it actually shows what is going on and why this fixes the parity.
For beginners, it might be easier to remember (r U2)*5 or (2R U2)*5
And for everyone that is serious about speedsolving, just learn one or more parity-fixes

 

[Die_d00pel_Null]

hm I don't really mind about efficienty at the moment cause I'm just beginning to learn 4x4x4.
Okay I now got these 2 very simple algs:
r 2U r 2U r 2u r 2U r
2r 2U 2r 2D* 2l 2D* 2U
I think thats all I need to solve parity isn't it?

 

[rjohnson_8ball]

hm I don't really mind about efficienty at the moment cause I'm just beginning to learn 4x4x4.
Okay I now got these 2 very simple algs:
r 2U r 2U r 2u r 2U r
2r 2U 2r 2D* 2l 2D* 2U
I think thats all I need to solve parity isn't it?

Be careful of notation. U2 means "turn the U face layer 180 degrees", but putting the number in front, like 2U, can mean "turn the upper 2 layers in U direction" like Uw. In addition, lower case "r" means the slice next to the R face and "u" means the slice next to the U face.

All you need is either (r U2)*5, which involves the slice near R, or (Rw U2)*5 which involve the two layers on R. Either of them can be used to move the "r" slice by an odd offset.

 

[Die_d00pel_Null]

okay so the algs should be:

r U2 r U2 r U2 r U2 r
r2 U2 r2 2D2 l2 2D2 U2


Hm I looked closer into these algs and I'm kinda confused:/
The first one solves the OLL parity and the second solves PLL parity.(at least I think so...)
But I'm a bit confused about how they work.
The first one does an even number of swaps on centers(2) and an uneven number of swaps on the edges (3).
The second one does an even number of swaps on centers (4) and an even number of swaps on the edges (2).

Did I miss something there?

 

[AvGalen]

hm I don't really mind about efficienty at the moment cause I'm just beginning to learn 4x4x4.
Okay I now got these 2 very simple algs:
r 2U r 2U r 2u r 2U r
2r 2U 2r 2D* 2l 2D* 2U
I think thats all I need to solve parity isn't it?

Be careful of notation. U2 means "turn the U face layer 180 degrees", but putting the number in front, like 2U, can mean "turn the upper 2 layers in U direction" like Uw. In addition, lower case "r" means the slice next to the R face and "u" means the slice next to the U face.

All you need is either (r U2)*5, which involves the slice near R, or (Rw U2)*5 which involve the two layers on R. Either of them can be used to move the "r" slice by an odd offset.

I probably caused this confusion because I wrote (2R U2)*5 where I should have written (Rw U2)*5. Sorry for that, I am so used to the x[UFRBLD]['2] notation that I constantly assume that it's the official notation. My mistake

The first one does an even number of swaps on centers(2) and an uneven number of swaps on the edges (3).
The second one does an even number of swaps on centers (4) and an even number of swaps on the edges (2).

Did I miss something there?

Yeah, you missed the part that explains that swaps on centers are not what parity is about. The first alg doesn't change centers, but has 5 quarterturns in it which is odd so it changes parity (very simplified)

 

[Die_d00pel_Null]

Yeah, you missed the part that explains that swaps on centers are not what parity is about. The first alg doesn't change centers, but has 5 quarterturns in it which is odd so it changes parity (very simplified)

uhm okay well could you explain this a bit more maybe not simplified?^^

 

[AvGalen]

Yeah, you missed the part that explains that swaps on centers are not what parity is about. The first alg doesn't change centers, but has 5 quarterturns in it which is odd so it changes parity (very simplified)

uhm okay well could you explain this a bit more maybe not simplified?^^

I won't. Just keep reading everything that has been posted already until you understand