# Can all parity be explained?



## Randomno (Apr 16, 2015)

The title's a bit ambiguous but I'm not really sure how to ask the question.

For example, 4x4 parity (for reduction) occurs when the last layer centers are switched, and parity algs will solve the edges as well as moving around the centers.

For other puzzles, such as the void cube and 3x3x2, can also have a state unobtainable on a 3x3, because of pieces on a 3x3 that do not exist on those puzzles. This isn't really a good explanation of it though, since the pieces are imaginary unlike the 4x4 centers.

There's also Square 1 parity, which (AFAIK) can't be compared to any other similar puzzle.


----------



## Berd (Apr 16, 2015)

It's to do with pieces being able to have multiple permutations but look right. That's 4x4 paritys I think.


----------



## Randomno (Apr 16, 2015)

Berd said:


> It's to do with pieces being able to have multiple permutations but look right. That's 4x4 paritys I think.



That's what I was talking about with the 4x4 centers.


----------



## Lucas Garron (Apr 16, 2015)

Randomno said:


> For example, 4x4 parity (for reduction) occurs when the last layer centers are switched, and parity algs will solve the edges as well as moving around the centers.



This isn't actually true! That's actually a cool fact about 4x4x4 (and 2x2x2).

2R U2 2L' 2R2 U2 2R U2 2R' U2 2L U2 2R' U2 2R U2 2R' U2 2R'(R' U' R U')5 swaps only the two wings on UF.



Randomno said:


> For other puzzles, such as the void cube and 3x3x2, can also have a state unobtainable on a 3x3, because of pieces on a 3x3 that do not exist on those puzzles. This isn't really a good explanation of it though, since the pieces are imaginary unlike the 4x4 centers.



Both of those puzzles can be mapped to a 3x3x3, so all states are of course "obtainable" on 3x3x3. I would say that the missing pieces make it *look* like they're unobtainable, because the most obvious mapping suggests a 3x3x3 position that has parity.



Randomno said:


> There's also Square 1 parity, which (AFAIK) can't be compared to any other similar puzzle.



It's actually mostly the same thing. Once you're in cube shape, each slice move swaps two pairs of edges and two pairs of corners.
Label each piece with a unique number, and cube shape preserves traditional permutation parity.


----------



## Ranzha (Apr 16, 2015)

Is Square-1 parity even parity at all?

Take a look at the start to a common parity alg:
/ 3, 3 / 1, 0 / -2, -2 /
Unlike 4x4, where there are multiple types of pieces being permuted, here, there is a clear opportunity for a 6-cycle of corners. What can be said about this?


----------



## Randomno (Apr 16, 2015)

Lucas Garron said:


> Both of those puzzles can be mapped to a 3x3x3, so all states are of course "obtainable" on 3x3x3. I would say that the missing pieces make it *look* like they're unobtainable, because the most obvious mapping suggests a 3x3x3 position that has parity.



I think I phrased that badly. With void cube for example, parity is causes by the centers being switched. But because there are no centers, that doesn't really make sense.


----------



## martinss (Apr 16, 2015)

Lucas Garron said:


> 2R U2 2L' 2R2 U2 2R U2 2R' U2 2L U2 2R' U2 2R U2 2R' U2 2R'(R' U' R U')5 swaps only the two wings on UF.


This isn't actually true!
It also swaps centers but you can't see them (let's try on a supercube...)


----------



## Christopher Mowla (Apr 16, 2015)

martinss said:


> This isn't actually true!
> It also swaps centers but you can't see them (let's try on a supercube...)


Did you look at the algorithm he posted? The algorithm doesn't affect any 4x4x4 supercube centers. See Supercube Centers and Odd Parity and my post to see that this is possible and to see a more general pattern for the nxnxn supercube.


----------



## qqwref (Apr 16, 2015)

4x4x4 centers have nothing to do with parity, it's true. When solving a supercube, after correctly putting all the centers together, OLL and PLL parities are still possible. In fact, all x-centers are unaffected by parity. Parity is, however, related to the positions of the T-centers (which appear on odd cubes) and obliques (which start to appear on the 6x6x6).


There are really two types of parities: permutation parity (or BLD parity), used in BLD and puzzles like the Void Cube, and reduction parity, used in puzzles like 4x4x4 and Square-1. There is a whole bunch of info out there, which you can search for if you're curious, so I'll just give a quick explanation.

Permutation parity is all about whether a position can or can't be solved with 3-cycles. We say the position has "even" parity if it can be solved with 3-cycles, and "odd" otherwise. Typically you will notice an odd parity at the end, when you are left two pieces of one type swapped. Different puzzles have different rules for what types of pieces can have odd permutation parity. For instance, on the 3x3x3 the corner parity and edge parity must be the same (you can have a T perm, which is two edges swapped and two corners swapped); on the domino or void cube, any parity is possible (you can have just two edges swapped, or just two corners swapped, or both); on the megaminx, neither corners nor edges can have odd parity (a 3x3x3 style T perm is impossible). And of course, depending on the puzzle, a given two-piece swap can be easy to solve or difficult.

Reduction parity is different, and a bit more subtle. It occurs when you think you have reduced the puzzle down to a position where it can be solved with fewer allowed moves, but in fact you have reached a position where this is impossible, because your position doesn't obey the permutation parity constraints that it must. Let's take Square-1: you reduce the puzzle to cubeshape, which means that you expect it can be solved using only moves that keep the puzzle in cubeshape. As Lucas Garron mentioned, these moves keep the permutation parity of the edges the same as the permutation parity of the corners: either they are both even, or both odd. But in Square-1 parity, one is odd and the other is even, so you will end up with something like a swap of two edges at the end. So, you thought you reduced the puzzle down to a position where it could be solved by cubeshape-only moves, but the position actually didn't obey the permutation parity constraints it needed to. In these cases, the only way to fix the parity is to do some kind of algorithm which moves you out of the reduced state. In Square-1 you have to leave cubeshape, and in 4x4x4 (where you tried to reduce to a 3x3x3) you have to break the centers apart.


----------



## martinss (Apr 17, 2015)

cmowla said:


> Did you look at the algorithm he posted? The algorithm doesn't affect any 4x4x4 supercube centers. See Supercube Centers and Odd Parity and my post to see that this is possible and to see a more general pattern for the nxnxn supercube.



We agree together. The alg also swaps centers pieces. These pieces are hidden pieces (my 4x4x4s are 5x5x5 with hidden pieces). So you cannot see the swapping pieces on a 4x4x4. Let's try on a supercube 4x4x4, you'll see that you really can't see the swapping pieces on a 4x4x4 even if you look at one of them during the algorithm... We're saying the same thing...


----------



## Christopher Mowla (Apr 17, 2015)

martinss said:


> We agree together. The alg also swaps centers pieces. These pieces are hidden pieces (my 4x4x4s are 5x5x5 with hidden pieces). So you cannot see the swapping pieces on a 4x4x4. Let's try on a supercube 4x4x4, you'll see that you really can't see the swapping pieces on a 4x4x4 even if you look at one of them during the algorithm... We're saying the same thing...


No we're not saying the same thing. In your post,



martinss said:


> Lucas Garron said:
> 
> 
> > 2R U2 2L' 2R2 U2 2R U2 2R' U2 2L U2 2R' U2 2R U2 2R' U2 2R'(R' U' R U')5 swaps only the two wings on UF.
> ...


you are saying that what Lucas said was _wrong_, but I was saying what he said is _correct_. Both he and I never talked about the "invisibility" of center swapping on a non-supercube: we talked about algorithms which DO NOT swap any centers _on the 4x4x4 supercube_.


----------



## cuBerBruce (Apr 18, 2015)

martinss said:


> The alg also swaps centers pieces. These pieces are hidden pieces (my 4x4x4s are 5x5x5 with hidden pieces). So you cannot see the swapping pieces on a 4x4x4.



The alg does not swap any of the 24 4x4x4 center pieces. It will swap _internal_ pieces if the puzzle is constructed as 5x5x5 without all the pieces being externally visible. These pieces would be center pieces if viewing the puzzle as a 5x5x5; but viewed as a 4x4x4, they would be regarded as internal pieces. 

You might be technically right that the alg _can_ swap pieces (albeit internal ones, assuming the puzzle is constructed using internal pieces other than the core) other than the obvious edge pieces that are swapped, but I think it is obvious that Lucas and cmowla were only talking about the effects of the 56 pieces that we consider a 4x4x4 puzzle must have.



martinss said:


> Let's try on a supercube 4x4x4



If your point was about the effect on internal pieces, I don't see what you're point is about a supercube. A 4x4x4 stickered as a supercube only helps to show the point Lucas was making. It does nothing to help show how internal pieces are affected.


----------



## blade740 (Apr 18, 2015)

"Parity" happens when you restrict solving to a specific moveset, and you encounter a state that can't be solved within that moveset. For example, in 4x4 reduction limits you to only outer layer turns. Similarly, after solving cubeshape, generally it's solved using 2x2 algs and turns that don't leave cubeshape.

Odd permutations are generally parities, but not all "parities" are odd permutations.


----------



## cuBerBruce (Apr 19, 2015)

blade740 said:


> "Parity" happens when you restrict solving to a specific moveset, and you encounter a state that can't be solved within that moveset. For example, in 4x4 reduction limits you to only outer layer turns. Similarly, after solving cubeshape, generally it's solved using 2x2 algs and turns that don't leave cubeshape.



Well, personally, I think this is a very bad definition of parity. Under this definition of parity, the 6 orbits of 2x2x2 pieces when moves are restricted by <U, R> would qualify as a parity. But the word parity was never meant to be used for something where you have 6 separate cases. So this is really not a parity.

Why, I ask, do we even need to define parity? The word is already defined. *We don't need to redefine it.*

Basically, anything that can be described as being either "odd" or "even" can be called a parity.

*That's it.* That is the essence of what the word parity means in the "real world." Corner permutation parity, 4x4x4 OLL parity, 4x4x4 PLL parity, square-1 parity, and square-2 parity can all be described as things that are either "odd" or "even." Often, we in the cubing community often talk about a puzzle as "having parity" or "not having parity" rather than calling it "odd parity" or "even parity," but otherwise the term parity as used in the speedcubing community is mostly consistent with how the word is used in the "real world." The fact that how well this simple concept of parity fits with many situations encountered with twisty puzzles is why the term has come to be used so much within the cubing community in the first place.

The various parities talked about in the speedcubing community can usually be related to something called permutation parity. Permutation parity refers to whether the number of swaps required to bring a permutation back to some original arrangement (null permutation) is either odd or even. It can also be defined as whether the number of even length cycles (if you break down a permutation into constituent cycles, a concept BLD solvers are generally familiar with) is odd or even. With respect to cubing or twisty puzzles, we simply need define what "odd" means and what "even" means with respect to some puzzle puzzle parity we want to talk about, and this is most often done in terms of the permutation parity of some set of pieces or pseudo pieces (e.g. "dedges").

In summary, in my view we don't need to _define_ parity. The word has a well established meaning and I believe we have no need to invent a new meaning for it.


----------



## qqwref (Apr 19, 2015)

It seems like people missed my post  blade740 is talking about reduction parity whereas cuBerBruce is talking about permutation parity (the mathematical definition of parity). The fact is, parity is used in cubing in two subtly different ways. Reduction parity cannot explain what happens in blindfold solves, and mathematical parity cannot explain why 4x4x4 speedsolvers talk about "having parity" but 3x3x3 speedsolvers never do.


----------



## bcube (Apr 19, 2015)

Randomno said:


> The title's a bit ambiguous but I'm not really sure how to ask the question.
> 
> For example, 4x4 parity (for reduction) occurs when the last layer centers are switched, and parity algs will solve the edges as well as moving around the centers.
> 
> ...



I believe this thread could be useful for you (it definitely was for me).


----------



## cuBerBruce (Apr 19, 2015)

qqwref said:


> It seems like people missed my post  blade740 is talking about reduction parity whereas cuBerBruce is talking about permutation parity (the mathematical definition of parity). The fact is, parity is used in cubing in two subtly different ways. Reduction parity cannot explain what happens in blindfold solves, and mathematical parity cannot explain why 4x4x4 speedsolvers talk about "having parity" but 3x3x3 speedsolvers never do.



It looks like it's qqwref who didn't read my post. I was discussing the word parity, not permutation parity (although I did mention it). I never said a parity had to be a permutation parity. Nor is permutation parity _the_ mathematical definition of parity. Qqwref, reread the sentence I posted in red, and the boldface sentence after it. Where is the word permutation in those two sentences?

And blade70 said "pariity" and not "reduction parity." OK, I may have been a little harsh on his definition, but as it was stated, it would allow some things that don't fit the concept of what parity is to be called a (reduction) parity. I personally would not call anything a parity if it does not meet (in some way) the criteria I gave in the sentence in red. I think it's ridiculous to call something a reduction parity if it doesn't even fit the general concept of parity. The familiar Square-1 parity, OLL parity, and PLL parity, of course, are all fine examples of reduction parities.


----------



## blade740 (Apr 19, 2015)

qqwref said:


> Reduction parity cannot explain what happens in blindfold solves



At least by my definition, it can. BLD methods generally involve solving using only commutators and conjugates to solve each piece type separately. A state with odd cycles of both corners and edges is unsolvable using only even-cycle commutators.

I understand that the mathematical definition of parity is different from how it's used by speedsolvers. "Algorithm" is the same way. I think my definition is the simplest one that describes what cubers know as "parity".


----------



## qqwref (Apr 19, 2015)

cuBerBruce said:


> Nor is permutation parity _the_ mathematical definition of parity. Qqwref, reread the sentence I posted in red, and the boldface sentence after it. Where is the word permutation in those two sentences?


You don't have to use the word "permutation" if you don't want to. I am using that to describe one version of parity, as opposed to "reduction parity" which is another thing people will call "parity". The word has two different definitions and you are using one of them. To be even more clear, when I say "permutation parity" I don't mean "the parity that shows up in permutations on a twisty puzzle" but "parity of a permutation" in the mathematical sense, which - as far as I can tell, and please correct me if I'm mistaken - is exactly what you have been talking about.



cuBerBruce said:


> And blade70 said "pariity" and not "reduction parity."


Right, that's exactly what I'm talking about when I say the word has two separate meanings in cubing. I am trying to make a distinction that others are not making.



blade740 said:


> At least by my definition, it can. BLD methods generally involve solving using only commutators and conjugates to solve each piece type separately. A state with odd cycles of both corners and edges is unsolvable using only even-cycle commutators.


Fair enough - you certainly can argue that BLD solvers do no moves (or up to one move, if using premoves to fix parity - does anyone do this?) but aim to "reduce" the puzzle to a position that can be solved with only commutators. There's probably a better example out there, where mathematical parity matters but has nothing to do with any kind of move restrictions.


----------



## cuBerBruce (Apr 20, 2015)

qqwref said:


> You don't have to use the word "permutation" if you don't want to. I am using that to describe one version of parity, as opposed to "reduction parity" which is another thing people will call "parity". The word has two different definitions and you are using one of them. To be even more clear, when I say "permutation parity" I don't mean "the parity that shows up in permutations on a twisty puzzle" but "parity of a permutation" in the mathematical sense, which - as far as I can tell, and please correct me if I'm mistaken - is exactly what you have been talking about.



Yes, there are a number of different things called parities. There's permutation parity, reduction parity (as in OLL parity, PLL parity, square-1 parity), integer parity, parity bits, 15-puzzle parity, and chess/checkerboard parity. All these examples have something in common. They all relate to a single, basic notion of _parity_ that is essentially *universally accepted* in the "real world." See my red sentence a few posts back if you need to refresh yourself about that basic notion.

So why on earth would we want redefine "reduction parity" to include things that violate the universally accepted notion of what parities are? It makes no sense to me. It would invite the term to be ridiculed, in my opinion. I certainly will not subscribe to such a definition.

Is there anything specifically in cubing that you want to be called a reduction parity that isn't consistent with the universally accepted notion of _parity_?


----------



## cmhardw (Apr 20, 2015)

cuBerBruce said:


> So why on earth would we want redefine "reduction parity" to include things that violate the universally accepted notion of what parities are? It makes no sense to me. It would invite the term to be ridiculed, in my opinion. I certainly will not subscribe to such a definition.
> 
> Is there anything specifically in cubing that you want to be called a reduction parity that isn't consistent with the universally accepted notion of _parity_?



I've been following this thread with interest, but now I'm confused.

Are we no longer calling situations where one reduces a puzzle such that it can now be solved with a subset of the puzzle's possible turns, only to find that this subset of turns is incapable of solving the puzzle "reduction parity"?

This is how I interpret the discussion so far.

Should we be calling this situation a "reduction error" or some other such term?


----------



## cuBerBruce (Apr 20, 2015)

cmhardw said:


> I've been following this thread with interest, but now I'm confused.
> 
> Are we no longer calling situations where one reduces a puzzle such that it can now be solved with a subset of the puzzle's possible turns, only to find that this subset of turns is incapable of solving the puzzle "reduction parity"?



I am not aware of anything being called a reduction parity that doesn't divide the relevant configurations into two mutually exclusive sets. OLL parity, PLL parity, and square-1 parity all do. That's why I asked the question. I mentioned earlier something that divides the relevant configurations into 6 sets. But I've not been aware of that being called a parity (and which it certainly isn't in any normal usage of the word).



cmhardw said:


> Should we be calling this situation a "reduction error" or some other such term?



Well, that reminds me of people using "parity error" in cubing, which I've never really liked. I don't generally think of parity conditions as being errors. But I suppose (to me) "reduction error" is a little better than "reduction parity" if the condition isn't really a parity situation.


----------



## blade740 (Apr 20, 2015)

cuBerBruce said:


> I am not aware of anything being called a reduction parity that doesn't divide the relevant configurations into two mutually exclusive sets. OLL parity, PLL parity, and square-1 parity all do. That's why I asked the question. I mentioned earlier something that divides the relevant configurations into 6 sets. But I've not been aware of that being called a parity (and which it certainly isn't in any normal usage of the word).



If one was using a 2x2 method that involved reducing the puzzle to 2gen, I could see the "orbit fix" step being referred to as "fixing parity", even though it isn't a binary state. 

If you assembled the pieces of a 3x3 at random, and the corner orientation was wrong, you might call that problem "corner orientation parity". This divides into 3 sets, rather than 2, but I think most speedsolvers would consider it a sort of parity.


----------



## cmhardw (Apr 20, 2015)

cuBerBruce said:


> I am not aware of anything being called a reduction parity that doesn't divide the relevant configurations into two mutually exclusive sets. OLL parity, PLL parity, and square-1 parity all do. That's why I asked the question. I mentioned earlier something that divides the relevant configurations into 6 sets. But I've not been aware of that being called a parity (and which it certainly isn't in any normal usage of the word).





blade740 said:


> If one was using a 2x2 method that involved reducing the puzzle to 2gen, I could see the "orbit fix" step being referred to as "fixing parity", even though it isn't a binary state.
> 
> If you assembled the pieces of a 3x3 at random, and the corner orientation was wrong, you might call that problem "corner orientation parity". This divides into 3 sets, rather than 2, but I think most speedsolvers would consider it a sort of parity.



Perhaps these orbits could be called "unsolvable subsets" or "unsolvable reductions" with the implication being that the orbit cannot get to the puzzle's solved state by way of moves within the reduced subset only.

I also like "false reduction" or "unsolvable reduction" as terms too.


----------

