# Define "Parity"



## brunson (Jul 15, 2009)

With respect to cubes. 

It's thrown around a lot, I know what it means in computer science and mathematics, but, in the words of Inigo Montoya, "You keep using that word. I do not think it means what you think it means."

I'd just like to see a rigorous definition of what people that use the term think it means.


----------



## StachuK1992 (Jul 15, 2009)

http://en.wikipedia.org/wiki/Parity

Apart from (mostly false) wiki definitions, I would say that, in a cubing sense, that there are different definitions for different situations.

For example, while speedsolving a 3x3, one may encounter a turned corner, a flipped edge, or an 'impossible' permutation case, while in blindfolded cubing, the cube may be completely solvable, yet still have 'parity.'

Therefore, we can make no and infinite definitions.


----------



## Johannes91 (Jul 15, 2009)

brunson said:


> With respect to cubes.


It's a mystical magic synonym for "trouble".


----------



## soccerking813 (Jul 15, 2009)

Parity means: Bad


----------



## JBCM627 (Jul 15, 2009)

1. What Tim enjoys doing to Dan's cubes. (Will I ever stop referencing that?)
2. http://www.jaapsch.net/puzzles/theory.htm#permpar


----------



## blah (Jul 15, 2009)

The parity of a permutation refers to whether that permutation is even or odd. An even permutation is one that can be represented by an even number of swaps while an odd permutation is one that can be represented by an odd number of swaps.


----------



## jcuber (Jul 15, 2009)

IMO, parity is when there is an "impossible" case (as in impossible on a 3x3). Also synonym for bad, horrible, suckish, etc. 

As well as what Tim likes doing to Dan's cubes.


----------



## Lord Voldemort (Jul 15, 2009)

Does parity only apply to permutation or to orientation as well?
From what I know, it's the number of 2-Cycles done of the cube (because 3-cycles can be broken down as 2 two cycles). The reason you can have parity in blindsolving is because you're doing edges and corners separately, but an odd number of swaps + an odd number of swaps (edges and corners) = a total even number of swaps for the whole cube.
@ jcuber - Only odd parity is an impossible case...


----------



## Tim Reynolds (Jul 15, 2009)

JBCM627 said:


> 1. What Tim enjoys doing to Dan's cubes. (Will I ever stop referencing that?)
> 2. http://www.jaapsch.net/puzzles/theory.htm#permpar



1. Apparently not? Oh, and I wasn't the only one as I recall...I just did the obnoxious ones like v-cubes and megaminx.

As for parity...the problem is that it is colloquially used in so many different ways. My attempt at a definition for the way that it is most frequently used:
A position of a puzzle which, due to an odd permutation of some set of pieces, requires additional steps to solve the cube beyond the standard solving method.

Or basically, these



Johannes91 said:


> It's a mystical magic synonym for "trouble".





soccerking813 said:


> Parity means: Bad



work.


----------



## Ton (Jul 15, 2009)

brunson said:


> With respect to cubes.
> 
> It's thrown around a lot, I know what it means in computer science and mathematics, but, in the words of Inigo Montoya, "You keep using that word. I do not think it means what you think it means."
> 
> I'd just like to see a rigorous definition of what people that use the term think it means.



The mathematics term would be odd and even permutation

In plain English 

If you swap two element it is odd - one swap of two pairs- 
If you swap three elements it is even -this will need two swaps of two pairs
if you swap four elements it is odd -this will need three swaps of two pairs
etc 

Examples :

if you need to swap ( 1 2 3 ) to e.g. (3 1 2)

You can swap position 1 with 2 and position 1 with 3 (even)

so (1 2 3 4 ) swap to (4 1 2 3)
Swap position 1 with 2 and position 1 with 3 and position 1 with 4
So this is odd permutation (parity)

so will be (1 2 3 4) to (3 4 1 2) even as this needs two swaps of pairs


odd parity is an impossible case for a normal 3x3 , but possible on a void cube


----------



## Johannes91 (Jul 15, 2009)

blah and others: Yes, we are aware of _that_ definition, but it's not how a lot of speedcubers use it. One difference is that it's usually "parity" or "no parity" instead of even or odd, and often it's used for something completely unrelated because many just don't know the real meaning. See for example posts #4 and #7 in this very thread.


----------



## Lord Voldemort (Jul 15, 2009)

How does a 4x4 orientation parity happen?
Isn't that 2 pieces being swapped?


----------



## blah (Jul 15, 2009)

Johannes91 said:


> blah and others: Yes, we are aware of _that_ definition, but it's not how a lot of speedcubers use it. One difference is that it's usually "parity" or "no parity" instead of even or odd, and often it's used for something completely unrelated because many just don't know the real meaning. See for example posts #4 and #7 in this very thread.



Oh, so this was supposed to be a sarcastic thread for people (who don't know what parity means) to look silly 

Edit:


brunson said:


> I'd just like to see a rigorous definition of what people that use the term *think* it means.


Kinda missed that earlier on


----------



## blah (Jul 15, 2009)

Lord Voldemort said:


> How does a 4x4 orientation parity happen?
> Isn't that 2 pieces being swapped?



It's an odd permutation parity of two edge pieces that appears to be an "orientation parity" (which doesn't exist) at first sight.

That's why it's called OLL parity, not orientation parity.


----------



## Stefan (Jul 15, 2009)

It comes from solving 4x4 with the reduction method and describes the two problems you can run into after building the edge pairs. Therefore it's actually not "parity" but "pa*i*rity" which is derived from "pair" and "pity".


----------



## JLarsen (Jul 15, 2009)

The way that I think of parity on say...a 4x4, is looking at the laws of the cube, and how something like OLL/PLL parity does not actually break the laws of the cube. The thing that people don't realize, is that even though during the final solve of a 4x4 we treat paired dedges as a single edge, they are not. OLL parity is not one flipped edge, but two, thus it does not violate the laws of the cube. The same goes for PLL parity. That's just my way of understanding it best.


----------



## Lord Voldemort (Jul 15, 2009)

It's not possible, on a 4x4, to have a permuted correctly but not oriented correctly, right? So isn't the OLL parity 2 edges swapped?


----------



## rjohnson_8ball (Jul 15, 2009)

This is what I believe. I am a long time computer programmer, so maybe I am biased.

The term "parity" was originally derived from data transfer for computers. Occasionally, when data got sent and received, a single bit was accidentally interpreted the wrong way (as "on" when it should be "off" or the other way around). If it was toggled the wrong way it was called a "parity error". This was sometimes a problem with magnetic tapes -- a very common way of storing and transferring large amounts of data back in the 60's through 80's. Someone devised a solution -- append one extra bit to each piece of data and assign it "on" or "off" so that the sum of "on" bits would be even. Then as the data got read it would do parity checking, and re-read a piece of data if it looked odd. The chances of two bits being wrong in a piece of data (causing a parity error to go unnoticed) would be very slim.

Today we use checksums in executables for a similar purpose.

_EDIT: Okay, I suppose the word existed before the computer data transfer problems. Generally I think "parity error" signifies a missing pair, when things should be paired._


----------



## JLarsen (Jul 15, 2009)

Lord Voldemort said:


> It's not possible, on a 4x4, to have a permuted correctly but not oriented correctly, right? So isn't the OLL parity 2 edges swapped?



I believe it is possible to have 2 edges permuted correctly but not oriented. I'll try it. Having 2 sets of edge swapped is PLL parity.

Edit:Yes you can flip just 2 edges.


----------



## Tim Reynolds (Jul 15, 2009)

Lord Voldemort said:


> It's not possible, on a 4x4, to have a permuted correctly but not oriented correctly, right? So isn't the OLL parity 2 edges swapped?



Assuming that you mean an edge piece, no, it is physically impossible (as in, the piece won't fit upside down)


----------



## JLarsen (Jul 15, 2009)

Tim Reynolds said:


> Lord Voldemort said:
> 
> 
> > It's not possible, on a 4x4, to have a permuted correctly but not oriented correctly, right? So isn't the OLL parity 2 edges swapped?
> ...



Yeah one edge piece is a no. Even if it would physically fit in there upside down.


----------



## beingforitself (Jul 15, 2009)

StefanPochmann said:


> Therefore it's actually not "parity" but "pa*i*rity" which is derived from "pair" and "pity".



meh, i lol'd


----------



## Lord Voldemort (Jul 16, 2009)

Tim Reynolds said:


> Lord Voldemort said:
> 
> 
> > It's not possible, on a 4x4, to have a permuted correctly but not oriented correctly, right? So isn't the OLL parity 2 edges swapped?
> ...



That's what I'm saying though. 
They're swapped and flipped, but that still means only 2 edges are switched.


----------



## fanwuq (Jul 16, 2009)

Lord Voldemort said:


> Tim Reynolds said:
> 
> 
> > Lord Voldemort said:
> ...



Really? http://speedcubing.com/chris/4speedsolve3.html


----------



## brunson (Jul 16, 2009)

So the consensus seems to be, there is a rigorous definition of parity, but is mostly tossed around incorrectly on the forums.


----------



## lowonthefoodchain (Jul 21, 2009)

Parity: Bombs your standard deviation for big cubes.


----------



## JLarsen (Jul 22, 2009)

Another reason even numbered cubes are less pleasant than odd numbered ones.


----------



## qqwref (Jul 22, 2009)

There is indeed a mathematical definition for parity, but in cubing we actually use "parity" as a shorthand for "parity problem", that is, something which is the wrong parity and thus cannot be solved using normal moves but which must instead be dealt with by a special algorithm. Hence we don't talk about even parity or odd parity, just parity or no parity (and I prefer it this way; it makes much more sense for speedsolving). Of course the standard for "normal moves" changes from puzzle to puzzle... for 3BLD a normal move is a commutator, for the last step of reduction a normal move is an outer layer move, for Square-1 a normal move is any short sequence which stays in cubeshape (or very close to it). So for all of these things, what we call parity is actually slightly different, but the concept is really the same.

The only type of parity problem I can think of that this doesn't work for is corner orientation parity, which nobody seems to have brought up (but if you did and I missed you I apologize). Instead of traditional parity where everything has to add up to 0 mod 2, in corner orientation parity everything has to add up to 0 mod 3. The concept is the same, but there's no nice way to refer to things that have to add up mod 3. Fortunately it is still fine to talk about parity problems (i.e. anything that isn't 0 mod 3), and the cubing definition of "parity" still makes sense


----------



## Stefan (Jul 22, 2009)

qqwref said:


> Fortunately it is still fine to talk about parity problems (i.e. anything that isn't 0 mod 3)


It can certainly be considered a "problem", but I have doubts about "_parity_ problem". Cause parity really seems to be a two-cases thing. If I had to use a word for corner orientation, I might use invariant. But you can also just say "corner orientation is violated" or "false corner orientation" or something like that.


----------



## AvGalen (Jul 22, 2009)

I think the simplest way to describe parity is by doing a J-Perm on a 2x2x2. You should now have 2 corners swapped.

On 3x3x3 this would be an impossible position
On 2x2x2 you can just do a U or U' and now you have a 3-cycle of corners left.

Try to think about this example for a while.



I like Stefans pair-pity
And Michaels "everything that is not considered normal" is the best description for the way most people use it.


----------



## blah (Jul 22, 2009)

AvGalen said:


> I think the simplest way to describe parity is by doing a J-Perm on a 2x2x2. You should now have 2 corners swapped.
> 
> On 3x3x3 this would be an impossible position
> On 2x2x2 you can just do a U or U' and now you have a 3-cycle of corners left.
> ...


Sorry, but I really don't get the message you're trying to convey  Can you make it a little clearer?


----------



## mrCage (Jul 22, 2009)

AvGalen said:


> I think the simplest way to describe parity is by doing a J-Perm on a 2x2x2. You should now have 2 corners swapped.
> 
> On 3x3x3 this would be an impossible position
> On 2x2x2 you can just do a U or U' and now you have a 3-cycle of corners left.
> ...


 
What would not be normal about 4x4x4 parity (parities). They happen all the time.
More interesting is to analyse how the parities can arise. First of all i do not see the 4x4x4 PLL parity as a parity at all, It is commonly called a parity because you are supposed to be in the "3x3x3 stage" when you spot it, when using reduction at least. This parity is indeed solvable by doing 2 3-cycles on edges. This is not the case with the OLL parity. This parity can occour because a 4-cycle on edges is possible by an inner layer turn. In fact the effect on centers by this inner layer turn is completely fixable also on a 4x4x4 supercube. On bigger cubes the OLL parity (or parities) are fixable (of course), but it (they) cannot occur without a centers side effect. The inner layer quarter turn centers side effects are not completely fixable.

Hope this makes sense to most of you!

Per

PS! You see more parities on larger cubes when you do direct solving than with reduction solving. The reason why should be quite obvious by now ...


----------



## qqwref (Jul 22, 2009)

StefanPochmann said:


> qqwref said:
> 
> 
> > Fortunately it is still fine to talk about parity problems (i.e. anything that isn't 0 mod 3)
> ...


That would work, but it's kind of long and convoluted, isn't it? The concept of a parity problem works fine IMO for things that must be divisible by 3 or some other number, if you disregard the fact that parity means the state of something mod 2. Personally I prefer to refer to this kind of thing in our own internally consistent single-word way, rather than use a lot of words (or longer words) even if it might be more technically correct. As a special community, after all, we are allowed our own jargon 



mrCage said:


> First of all i do not see the 4x4x4 PLL parity as a parity at all, It is commonly called a parity because you are supposed to be in the "3x3x3 stage" when you spot it, when using reduction at least. This parity is indeed solvable by doing 2 3-cycles on edges. This is not the case with the OLL parity.


Indeed, and this goes back to what I was saying about normal moves. If you reduce 4x4 to a 3x3, then both PLL and OLL parity are real parity cases, because they are both things that you can't solve with just outer layer turns. On the other hand, if you use some kind of centers-first/F3L-first direct solving method, PLL parity isn't a parity anymore because doing commutators is also counted as a normal type of move to do, whereas OLL parity still needs an algorithm. (If you use something like cage, where you are free to do an r-slice move until you are solving the very last edges, even OLL parity could be considered as not a parity case, because r is a normal move and you don't have to fix centers afterwards.)


----------



## Stefan (Jul 23, 2009)

qqwref said:


> Personally I prefer to refer to this kind of thing in our own internally consistent single-word way, *rather than use a lot of words (or longer words)*


Huh? How is _"corner orientation parity"_ shorter than _"false corner orientation"_?


----------



## AvGalen (Jul 23, 2009)

blah said:


> AvGalen said:
> 
> 
> > I think the simplest way to describe parity is by doing a J-Perm on a 2x2x2. You should now have 2 corners swapped.
> ...


Hint: Parity has to do with even cycles. What does a U or U' turn do?


----------



## cmhardw (Jul 23, 2009)

parity => partaaaay

anyone? anyone?

Chris ;-)

P.S. on a somewhat serious note, I can't be the only one who has that word association between those words when written out. Or maybe I am?? :-s


----------



## Dene (Jul 23, 2009)

cmhardw said:


> parity => partaaaay
> 
> anyone? anyone?
> 
> ...



I can assure you that you are not the only one. Lucas in particular seems to be a fan.


----------



## qqwref (Jul 23, 2009)

I've made that mistake several times as well, and I think it's part of where the name "Martini" comes from too. (Maybe us non-Europeans should start calling it that as well, to avoid confusion.)


----------



## DavidWoner (Jul 23, 2009)

qqwref said:


> I've made that mistake several times as well, and I think it's part of where the name "Martini" comes from too. (Maybe us non-Europeans should start calling it that as well, to avoid confusion.)



http://www.youtube.com/watch?v=b9_60vDnbLY


----------



## blah (Jul 23, 2009)

AvGalen said:


> blah said:
> 
> 
> > AvGalen said:
> ...


I'm really confused now :confused: I always thought what I thought was true was true... Now I'm starting to get confused.

I really have no idea what you meant by "to describe parity". I know what you're talking about in the whole example, I've thought about it for a while, but no, I still don't see where the "description of parity" is, I can't seem to pinpoint that description in your example  In fact, I don't even know what parity is. I always thought I knew. Now I realize all I know is odd parity and even parity, but I don't know what parity itself means.

Here's how I understand odd and even permutation parities:

When a quarter turn is done on any face of the cube, the corners can be solved by a 4-cycle, same goes for the edges. A 4-cycle can be seen as 3 2-cycles, hence permutation parity for corners is odd since they can be solved by an odd number of 2-cycles (3), permutation parity for edges is also odd (3). The sum of parities, however, is even (6).

When a half turn is done on any face of the cube, the corners can be solved by either (a) 2 3-cycles, or (b) 2 2-cycles, same goes for the edges. (a) 2 3-cycles can be seen as 4 2-cycles, (b) 2 2-cycles _are_ 2 2-cycles, so either way, permutation parity for corners is even since they can be solved by an even number of 2-cycles (4 or 2), permutation parity for edges is also even (4 or 2). The sum of parities is even too.

(On a solved cube, the corners can be solved with a 0-cycle, same goes for the edges. A 0-cycle can be seen as 0 2-cycles, hence permutation parity for corners can is even (0), permutation parity for edges is also even (0). The sum of parities is even (0).)

So we can see that the sum of the permutation parities of corners and edges must be even on a legal cube. However, the respective permutation parities of corners and edges are not necessarily even. The odd-/even-ness of the permutation parity of each piece type (corners/edges) is "toggled" with every quarter turn applied to the cube, hence a cube scrambled with an even number of quarter turns can only be solved with an even number of quarter turns, same goes for odd.

Since there are no edges on a 2x2x2, the permutation parity of the corners can be odd or even depending on the odd-/even-ness of the "invisible edges", i.e. the sum of the permutation parities of the corners and the "invisible edges" must still be even.

I hope this is right because this is what I thought was right all along. But I don't see the connection between this and the example you provided


----------



## AvGalen (Jul 23, 2009)

@blah: You are overthinking because I used the word "describe". I should have used the word "explain".

You know exactly how odd/even permutation parity works. You just didn't realise this from my example so I will explain:

On 3x3x3 a J-Perm swaps 2 corners and 2 edges. *Solving that with 3 cycles (A-Perm, U-Perm) is impossible so you have parity* that you need to fix with a quarterturn (U or U')

because this might already be to complicated it is also possible to explain this on a 2x2x2 where there are no edges.

On 2x2x2 a J-Perm swaps 2 corners and 2 (imaginary) edges. Solving that with 3 cycles (A-Perm) is impossible so you have parity that you need to fix with a quarterturn (U or U')


----------



## Weston (Jul 23, 2009)

parity is the relationship between pieces

not necessarily whether its possible on a 3x3 cube.
but you have even and odd parity


----------



## Muesli (Jul 31, 2009)

Bit of Self Advertising here.

http://www.speedsolving.com/wiki/index.php/Parity


----------



## qqwref (Jul 31, 2009)

Musli4brekkies said:


> Bit of Self Advertising here.
> 
> http://www.speedsolving.com/wiki/index.php/Parity



If you wrote a good part of the article I don't mean to offend you, but... that article is terrible. The definition of parity makes no sense, the entire thing seems to be about NxNxN cubes (does the writer not even understand what parity is? or what it means on Square-1, for instance?) and uses weird notation, and the "switched corner parity" shouldn't be there at all. I'd fix it but I've long since abandoned the wiki for being impossible to maintain quality-wise.


----------



## CuBeOrDiE (Jul 31, 2009)

brunson said:


> With respect to cubes.
> 
> It's thrown around a lot, I know what it means in computer science and mathematics, but, in the words of Inigo Montoya, "You keep using that word. I do not think it means what you think it means."
> 
> I'd just like to see a rigorous definition of what people that use the term think it means.



a nuisance


----------



## mrCage (Aug 1, 2009)

Come on. This is very easy to define. If after reduction to a "3x3x3" cube you vannot solve the cube with solely outer layer turns you have some kind of parity issue. You can have a "flipped edge" on even size cube. Or 2 "swapped edges" also on even sized cube. On odd sized cube you cannot have any kind of parity after full reduction.

You may however have to do some "special algorithm" to complete the full reduction.

Per


----------



## Johannes91 (Aug 1, 2009)

mrCage said:


> Come on. This is very easy to define. If after reduction to a "3x3x3" cube you vannot solve the cube with solely outer layer turns you have some kind of parity issue.


Uh... Parity is a much more general concept than that. It applies to other puzzles than big cubes and other methods than reduction. You should know that.


----------



## mrCage (Aug 1, 2009)

Johannes91 said:


> mrCage said:
> 
> 
> > Come on. This is very easy to define. If after reduction to a "3x3x3" cube you vannot solve the cube with solely outer layer turns you have some kind of parity issue.
> ...


 
Yes i'm aware of that. But the first post was about cubes, not other puzzles. I'm also aware that parity may also be on corners as well as edges. And yes of course on bigger cubes also appear for other solving methods than reduction. But about 95% use reduction ...

Sometimes a short answer is better than a fuller more detailed answer

Per


----------



## Am1n- (Aug 2, 2009)

http://www.ryanheise.com/cube/parity.html

The parity of a permutation refers to whether that permutation is even or odd. An even permutation is one that can be represented by an even number of swaps while an odd permutation is one that can be represented by an odd number of swaps.

When considering the permutation of all edges and corners together, the overall parity must be even, as dictated by laws of the cube. However, when considering only edges or corners alone, it is possible for their parity to be either even or odd. To obey the laws of the cube, if the edge parity is even then the corner parity must also be even, and if the edge parity is odd then the corner parity must also be odd.

An interesting fact is that a commutator always represents an even permutation on both edges and corners. Given a commutator X.Y.X-1.Y-1, regardless of whether X.Y involves an even or odd number of swaps, X-1.Y-1 will involve the exact same number of swaps, and 2 times any number gives us an even number overall. What this means is that commutators cannot directly solve positions where the edges and corners have odd parity.

While parity tends not to be an issue at the beginning of a solve, it may become an issue in the endgame. If the edges and corners have odd parity, the easiest way to correct them is to apply a single 90 degree turn of any face. However, in the endgame, we typically have a need to employ sequences that affect only a select few pieces while preserving everything else, and a single 90 degree turn does quite the opposite, dislodging 8 pieces. Commutators allow us to affect a small number of pieces while preserving the rest, however these do not directly apply when the parity of the edges and corners are odd.


----------

