Edge Flip and Corner twist Proof?

pyraminx said:

ok..if i understand well,a more general way to state this is
center orientation parity matches with corner permutation or edge permutation(correct me if i am wrong)

Click to expand...

And. Not or. Bot corner permutation parity and edge permutation parity match center orientation parity. But one is enough for a proof. I chose corners because there are fewer and they're in a simpler shape.

pyraminx said:

but how can we extend to NxNxN super cube?
first of all we should have a definition of orientation of center as the centers
also permute

Click to expand...

Since they can't rotate in place, it's enough to consider only their permutation.

Stefan said:

If you temporarily switch to a nicer orientation scheme for the duration of the turn, the proof generalizes rather easily.

[...details...]

So... overall, instead of directly analyzing the R turn, we did three substeps. The first and third each changed the os%3, but cancel. And the second doesn't change it. So overall, the os%3 didn't change.

Click to expand...

It took me a while to work through your post, but I think basically you're saying that:
- changing the orientation scheme changes co%3 by a constant (the "difference" between the two schemes)
- while in an orientation scheme which is rotationally symmetric on one layer, turning that layer does not affect co%3
- so, we can prove that each turn does not affect co%3 by changing to an orientation scheme symmetric about that turn's layer, doing the turn, and changing back, for a net co%3 affect of 0.

Interesting idea, for sure. And the really cool thing is that it works for any puzzle where a rotationally symmetric orientation scheme is possible, and it should work for EO as well. So this proof even works for Pentultimate and Helicopter Cube; you can only not find such a scheme on a corner turning puzzle, which is in my experience the only puzzle type which allows a single corner twist (bar Skewb type puzzles, which are a notable exception). And the EO version works for everything which isn't edge turning (although mine does too), which again is the only puzzle type which allows a single edge twist.

Yeah, that's it. I like the term "rotationally symmetric", good way to put it. I know it was long, but I hope it was worth reading . And yeah, I think I originally came up with this for megaminx corner orientation a while back and was very pleased that it is so general and applies to many things. I really wasn't keen on defining certain arbitrary orientation schemes for every single puzzle and analyzing them one turn at a time, like Chris did for 3x3x3 early in this thread. I mean, it's not *that* bad, but it's still ugly repetitive work.

qqwref said:

And the EO version works for everything which isn't edge turning (although mine does too)

Click to expand...

What are you referring to there?

I just had to bump this thread because this post is genius!

qqwref said:

Simpler proof for edges: Consider the stickers on the edges, and label each one uniquely. Now, a quarter turn of any layer on any axis does two 4-cycles of edge stickers, which is an even permutation. Every move sequence can be written in terms of quarter turns, so every move sequence performs an even permutation on the edge stickers. But flipping one edge does one 2-cycle of edge stickers, which is an ODD permutation. So no move sequence can have the effect of flipping a single edge (or an odd number of edges, since an odd number of odd permutations is odd).

Incidentally this proof works perfectly (well, with slight variations in some of the numbers I wrote) on similar puzzles, such as the Pyraminx and Megaminx.

Click to expand...

Well I'm glad for the bump. Really interesting thread.

I am not saying this is correct, but this might be a corner twist proof similar to qqwref's edge flip proof.

Axiom 1:
The identity (solved cube) is an even permutation of fixed centers (or X-center pieces on big even cubes) by the properties of a supercube.

Axiom 2:
If the fixed centers (or X-center pieces on big even cubes) are in an odd permutation, then the minimum number of corners which can be unsolved is 2, and the minimum number of edges which can be unsolved is 2. (Think of a J-Perm, T-Perm, etc.)

Axiom 3:
When the centers are in an odd permutation, one can twist the corners with algorithms just as one can twist the corners when the cube is in an even permutation (the ability to twist corners does not depend on whether the permutation of the centers is even or odd).


The the sum of clockwise (or anti clockwise, but not both) twists of corners is always evenly divisible by 3.
Proof
Consider the stickers on the corners and label each one uniquely. Each corner has 3 stickers.
By axiom 2, there is a minimum of 2(3) = 6 corner stickers which must be unsolved if the fixed centers (or X-center pieces on even cubes) are in an odd permutation.

By axiom 1, when there is an even permutation of centers, a minimum of 0 corners and 0 edges can be unsolved (despite that the edges and corners are independent from each other when the centers have an even permutation).

Note that 3 corner stickers is neither the minimum amount to be unsolved for even or odd permutations.

Now, to take care of the last case, that is, to determine the second to least minimum number of corner stickers which can be unsolved for even permutations of centers,

When the centers are in an odd permutation, since the minimum number of corner stickers to be unsolved is 6, then it is not possible to have only 3 corner stickers unsolved. This implies that one corner cannot be twisted once (in either direction) when the centers are in an odd permutation.
By axiom 3, the previous statement implies that 3 corner stickers cannot be unsolved when the centers are in an even permutation.

To take care of all other cases for which the sum of the clockwise (or anti clockwise, but not both) twists of corners is not evenly divisible by 3, it follows that since one cannot twist a single corner (in either direction), one cannot generate any other of the possible situations in which the sum of clockwise (or anti clockwise, but not both) twists of corners is not evenly divisible by 3.

Lastly, notice that even if this proof were true (it might be, but...), it does not fully justify the 2x2x2 case. However, note that a quarter turn (say, R) does a 3 4-cycle of corner stickers (an odd permutation), and R2 does a 6 2-cycle of corner stickers (an even permutation). Hence the centers in an odd permutation if and only if the corner stickers are in an odd permutation (so you can just substitute "centers in an odd permutation" with "corner stickers in an odd permutation" for the 2x2x2 case to generate both the axioms and the proof). I didn't do this so that it's easier to see.

Feedback anyone?

cmowla said:

Feedback anyone?

Click to expand...

I think your axioms are more like lemmas. An axiom is something you want to be true but can't prove (so you assume it).

(Also, I think a fixed-corner proof would be simplest.)

You seem to forget the case where two corners are swapped and one of them is misoriented.

edit: lolfact: While I still had this thread open, I played with my cube and somehow managed to misorient one corner.

qqwref said:

Simpler proof for edges: Consider the stickers on the edges, and label each one uniquely. Now, a quarter turn of any layer on any axis does two 4-cycles of edge stickers, which is an even permutation. Every move sequence can be written in terms of quarter turns, so every move sequence performs an even permutation on the edge stickers. But flipping one edge does one 2-cycle of edge stickers, which is an ODD permutation. So no move sequence can have the effect of flipping a single edge (or an odd number of edges, since an odd number of odd permutations is odd).

Click to expand...

qqwref, I believe your edge orientation proof proves corner orientations as well.

For those who cannot visualize what a 2 4-cycle of edges stickers is, here is an image. (The image below illustrates what happens to the edge stickers in slice R when we do the move R to a solved 3x3x3 cube.)


When you mentioned

qqwref said:

But flipping one edge does one 2-cycle of edge stickers, which is an ODD permutation

Click to expand...

, we cannot say that twisting a corner is a 3-cycle of corner stickers as we could say that flipping an edge is a 2-cycle because there are two different 3-cycles in 3 objects (where as there is only one unique 2-cycle in 2 objects--for the edge).

To keep a corner "intact", we cannot move one sticker without removing the remaining two. (We could keep an edge "intact" by choosing to switch its stickers as you illustrated in your proof.)

Therefore there is only one version of a "3-cycle" of corner stickers in a corner, and thus we can abstract any twist of a single corner as the 2-cycle (sticker A joined with sticker B)↔(sticker C).

Interesting read!

cmwola, as far as I can tell your proof is correct.

cmowla said:

Therefore there is only one version of a "3-cycle" of corner stickers in a corner, and thus we can abstract any twist of a single corner as the 2-cycle (sticker A joined with sticker B)↔(sticker C).

Click to expand...

Hm, I am not convinced. What is the difference between a clockwise twist and an anticlockwise twist using your 2-cycle?
And what happens, if you do three times the same twist? This should be equivalent to no twist - but three 2-cycles cannot cancel.

Herbert Kociemba said:

Hm, I am not convinced. What is the difference between a clockwise twist and an anticlockwise twist using your 2-cycle?
And what happens, if you do three times the same twist? This should be equivalent to no twist - but three 2-cycles cannot cancel.

Click to expand...

Although I did not claim it to be a proof, below is an image I made which illustrates what went through my mind when I posted, at least.


As far as the = (rotate) sign, let's look at the counterclockwise rule (in the image above), for example.

Let 1 = the white sticker, 2 = the red sticker, and 3 = the green sticker on the solved cube to the left. We have the list {1,2,3} when the corner is solved.

For the counterclockwise rule, we say we have {1,{2,3}}.

Interpretation 1
When we want to swap either 2 or 3 with 1, we have {{2,3},1} = {2,3,1}, which is a 3-cycle.

Interpretation 2
When we want to swap either 2 or 3 with 1, we have {{2,3},1} = {1,{3,2}} = {1,3,2}, which is a 2-cycle. (When you swap two objects, there isn't a rule that says that you cannot change the orientation of one or both of the objects: as long as you exchange their locations, the swap is valid.)

That is, as you can see after the = (rotate) sign in the counterclockwise example, we can either view us swapping the green and red stickers (flip the 1x2 bar of the green and red sticker horizontally) and then swapping it with the white "rectangle"/square (flip the two bars vertically) (2-cycle),
or
we can view it at rotating both rectangles 180 degrees (3-cycle).

I'm not disputing your mention of the 2-cycle being repeated 3 times is not the identity permutation, but we cannot rule out "interpretation 2" just because it "behaves" like a 3-cycle since when either the clockwise or counterclockwise rule is applied three times, it returns the stickers to their original state. (If this was easy to see, I'm sure someone would have posted it earlier.)

Lastly, when I mentioned that we cannot view a corner twist as a 3-cycle (which is incorrect from one interpretation), I had in mind that since a 3-cycle is a composition of two overlapping 2-cycles, then if we can do a 3-cycle, we should also be able to do just a 2-cycle. However, I just realized that when qqwref mentioned that a quarter face turn does a 2 4-cycle of edge stickers, we cannot do one 4-cycle, as this destroys edge stickering. (In short, disregard that statement.)

I'm not sure if this helps because you have to "redefine" the corners after every move. That is, when you move a corner along two different axes, you now have to choose the pair differently to consider it as a swap. So I don't think you can apply a sequence of moves and meaningfully ask whether the total orientation of corners is an odd permutation (and thus whether one corner is twisted).

qqwref said:

I'm not sure if this helps because you have to "redefine" the corners after every move. That is, when you move a corner along two different axes, you now have to choose the pair differently to consider it as a swap. So I don't think you can apply a sequence of moves and meaningfully ask whether the total orientation of corners is an odd permutation (and thus whether one corner is twisted).

Click to expand...

I'm confused (I'm not calling you wrong, I just really don't understand) as to why we need to see how the moves R U, for example, affect the orientation of the ufr corner in terms of 2 to 1 corner sticker pairing when we can observe that the move R and the move U do a 2 4-cycle of corner stickers independently.

Again, if my interpretation about a corner twist being a 2-cycle is incorrect, then I understand completely, and we can put this one approach for finding another proof for corner orientations behind us. However, if I successfully justified my 2-cycle interpretation, then why can't we treat corner orientations just like how you treated middle edge orientations using just one face quarter turn?

I think I can prove a quite general theorem about the orientations of a permutation puzzle under the following conditions:

1. Applying a move to the puzzle does not change its shape.
2. If a piece p has k possible orientations in a place P, p has a k-fold rotational symmetry axis which defines the k possible orientations.

For a move M we call a place P M-unambiguous if it is not possible to apply only M several times such that piece p moves to P again, but in a different orientation.

Then for an arbitrary orientation scheme for the pieces we have:

1. If a place P is M-unambiguous and p a piece in P with k possible orientations, the sum of the orientations of all pieces which are in the same orbit (with respect to M) as p does not change modulo k if M is applied.

Simple but important conclusions are

2. If a place P is unambiguous for several moves M1, M2,... Mn and p a piece in P with k possible orientations, then the sum of the orientations of the pieces in the union of the orbits does not change modulo k if any move M1,.. Mn is applied.

and

3. If place P is unambiguous for all moves of a puzzle it is impossible to rotate a piece in P in place without changing the orientation of other pieces.

For nxnxn Cubes all conceivable moves M are M-unambiguous for all places P for example (except for odd n the centerplace in the middle of a face).

Edit: I now put the proof here.
Edit2: And without using the "unambiguous" term we have:

Let us have a rotational permutation puzzle which does not change its shape and where the moves are spacial rotations of some of its pieces. Let a certain kind of piece have a k-fold rotational symmetry which allows it to take k different orientations within a place.
Then if these pieces do not intersect with the axes of the spacial rotations of the moves the sum of the orientations of these pieces modulo k is an invariant.