Rigorous Proof of Laws

[Stefan]

It's not really about defining edge orientation at all.

Exactly. It's just a tool needed to get the actual job done. Doesn't matter that there are other tools that also could get the job done or yet other tools that can't get the job done.

An edge is correctly oriented iff at least one of its stickers has the same color as either the center piece adjacent to it or the center on the opposite side.

That's really neat, much better than what I might've shown (glad I didn't ). You did screw up your algorithm (this is a great tool), but I think a simple R U also works, then the edge at UF is the only misoriented one.

 

[Matt S]

Heh, of course R U works. I'm not sure why I tried to make things more complicated.

 

[Stefan]

And now I'm curious whether your definition allows the proof. Of course we can't *just* look at the edge orientation, but maybe it works in combination with edge permutation. While you *can* have just a single edge misoriented, you can't with all edge permutations. For example the identity permutation, all edges at their correct spot. Obviously only an even number of misoriented edges is possible there. So if we combine your edge orientation property with some edge permutation property, maybe that combination allows the desired conclusion that only half of all orientations are possible and that you can't just flip one edge and keep the rest of the cube the same. I suspect it'd be ugly, though, Ryan's choice was definitely better

 

[Matt S]

Orientation as I defined it is pretty unwieldly for this sort of thing, because turning a given face doesn't always switch the orientation of the same edges.

For correctly oriented edges, you need to know whether they are oriented because of the face that is turning or because of one of the side faces. If it's correct because of the face that is being turned, it will still be correct in its new position, otherwise it will switch to incorrect. Incorrectly oriented edges will become if the side sticker is not the same as the color of the turned face (or opposite).

A neat property is that there are no preferred faces. All are treated equal.

 

[Stefan]

And now that I'm thinking about it this way, orientation and permutation interacting and depending on each other... I just noticed that we all always just multiply 1/2 * 1/2 * 1/3 = 1/12, not proving independence of the three parts. But they don't have to be independent! The Skewb is an example where this is not the case, you can't independently orient and permute its corners (at least not with the usual reference orientation scheme).

 

[Stefan]

Ok ok, here comes the big apology and hopefully the resolution of the misunderstanding...

it is necessary to decide on a frame of reference for correct edge orientation [But why?]

says nothing about why it's okay to use the "most common frame of reference for corner/edge orientation,"

I thought you didn't like that he chose a particular definition at all (first quote above) or that he chose this particular one (second quote, with my understanding bolded). But now I think you were bothered that he didn't explain the definition scheme much and why it works. Is that right? I guess I'm just too used to that and it's just as clear to me as that there are edges and corners, hence I didn't think of the necessity to explain it just like I didn't see a necessity to explain that there are edges and corners (I guess it's clear to you as well, but you were also capable to see it's not clear to everybody). However one writes it, one has to assume a level of knowledge in the reader (at minimum the capability to read), things that don't need to be explicitly stated and explained, and I guess we just had different base levels in mind, which in turn led me to misread your complaints. Mea culpa. And I agree that it would be nice to have the orientation definition scheme explained, I've had a vision of that for a while actually (part of what I want to put on cubemath.com).

 

[Herbert Kociemba]

Frame of reference for edges

It is quite interesting to observe how much confusion there is concerning the frame of reference for the edge orientation.
The most general method I can think of is to use a different frame of reference for each edge. That is, tag one facelet of a certain edge E. Then tag exactly one facelet for all 12 edge positions on the cube, if we assume that the edge E is unflipped in its home position, there are 2^11 possibilities to do this.
The tags on the edge positions do not change when doing a face turn, only the tag on the edge itself is moved by the faceturn.

If E is in an arbitrary position, we define E as unflipped/flipped, if the tag on the edge positions which E has matches/does not match the tag on the edge E itself.
Repeat this procedure for each edge. So there are (2^11)^12 ways to define a frame of reference for the edges.

But of course this is far too general because it is much simpler to use the same frame of reference for all 12 edges. Then we have to tag one facelet for all 12 edge positions only once, there are 2^12 possibilities. The tags on each of the edges is determined by the requirement that in the solved state the edge is unflipped.
All these different frames of reference work, but there are just a few which are nicer, for example those who allow to prove some property of the cube

There is a simpler reference frame as the one discussed in this thread to show the desired result. Use a reference frame where each quarter move flips the orientation of each involved edge. To do this tag for example the U-facelets of the UR and UL edges, the D-faclets of the DR and DL edges, the R-facelets of the RF and RB edges, the L-facelets of the LF and LB edges, the F-facelets of the FU and FD edge and the B-facelets of the BU and BD edges.
Each quarter move flips 4 edges. If 0 of the 4 edges were flipped before, 4 are flipped afterwards (0->4). The other possibilities are (1->3), (2->2), (3->1) and (4->0). In each case the number of flipped edges changes by an even number. So the number of flipped edges is always even and you can reach at most 1/2 of all possible edge orientations.

 

[PeterNewton]

@ Herbert Kociemba, wow. Now THAT made sense. Would you happen to have similar logic for only 1/3 of corner orientations being legal, and 1/2 of permutations being legal.
I have trying to figure it out for a week but I keep running into snags.

 

[Herbert Kociemba]

I should add that Ryan Heises argumentation is almost correct except the formulation "In both of these cases, a 90 degree move will flip all 4 edges, which is again an even number of flips", which is a bit unclear and could be replaced by the argument above which looks at all 4 possible cases which may happen when flipping the 4 edges.

Concerning the corner orientations and the permutations I do not see an easier way for a proof than the proofs given by Ryan. In the last line his "Combining these laws, only 1/12 (1/2 * 1/2 * 1/3) of the conceivable cube states are reachable by legal moves" should be of course "... at most 1/12 (1/2 * 1/2 * 1/3) of the conceivable cube states...".

 

[PeterNewton]

Hmmm I suppose the Heise's corners arguments are understandable, but I think there are some holes in his permutations arguments. Have you read my original post in the beginning?
Also, like blah was saying, where are these definitions of orientations coming from? You have explained edge orientation, but the corners are still confusing. Heise says "The most common frame of reference for correct corner orientation is to say that a corner has correct orientation if its top/bottom sticker is facing up or down. If it is facing in any other direction, then this corner is not correctly oriented." But why?? What IS correct orientation?

 

[Matt S]

But why?? What IS correct orientation?

Corner orientation was defined that way because doing so was useful and convenient. Read Herbert's post directly above yours. You can define orientation many, many ways, most of which have no logic or useful properties. Heise's proof chooses a definition that is both logical and useful.

 

[Stefan]

But of course this is far too general because it is much simpler to use the same frame of reference for all 12 edges. Then we have to tag one facelet for all 12 edge positions only once, there are 2^12 possibilities.

I'd say it's rather only 2^11 possibilities, as each is equivalent to its negation, where the other facelet is chosen for each position. Because of the desire to call all edges oriented correctly when the cube is solved, all *piece* references get flipped as well, so all edges in a certain cube state have the same orientation in both definitions.

The most general method I can think of is to use a different frame of reference for each edge.

You're restricting it to solely the position relative to the centers, though. You could alternatively define an edge's orientation depending on where it is relative to a certain corner or edge. Or where it is relative to a pair of pieces. Or more. The most general way I see is to specify orientation for each piece for each of the 10^21 possible cube states (the familiar 4.3*10^19 times 24 whole cube orientations). It is desirable to define it so that the solved cube has everything oriented correctly and that flipping two edges in place without changing the rest of the cube also flips their orientation value (corners similarly), though I'd say that's not even necessary. Just more pretty and useful.

There is a simpler reference frame as the one discussed in this thread to show the desired result. Use a reference frame where each quarter move flips the orientation of each involved edge.

Simpler in theory, yes. Though most cubers are familiar with the other one and not this one, so for them, the other one is probably simpler. For that reason, I still think it's the best choice for the proof.

What IS correct orientation?

Whatever you want it to be! There's no single god-given definition, you just choose one that's beneficial for your actual task. That's also why Ryan writes "The most common frame of reference". It really is the most common (what most programmers and (blind)solvers use), but it's not the only one. And that is precisely one reason I like Ryan's page, because other people rarely even acknowledge the possibility of other definitions.

 

[Herbert Kociemba]

Hmmm I suppose the Heise's corners arguments are understandable, but I think there are some holes in his permutations arguments. Have you read my original post in the beginning?
Also, like blah was saying, where are these definitions of orientations coming from? You have explained edge orientation, but the corners are still confusing. Heise says "The most common frame of reference for correct corner orientation is to say that a corner has correct orientation if its top/bottom sticker is facing up or down. If it is facing in any other direction, then this corner is not correctly oriented." But why?? What IS correct orientation?

I cannot see a hole in the permutation argument. A quarter move consists of 2 4-cycles, one for the corners and one for the edges. A 4-cycle is an odd permutation, you need an odd number of swaps to do this permutation. But the overall permutation is even. Applying another move means applying another even permutation. The product of two even permutations is an even permutation, so you will never get an odd permutation.

If a corner is not in its home position it depends on the frame of reference what is the meaning of correct orientation. There is no crrect orientation per se for a corner which is in a different place.

 

[PeterNewton]

I cannot see a hole in the permutation argument. A quarter move consists of 2 4-cycles, one for the corners and one for the edges. A 4-cycle is an odd permutation, you need an odd number of swaps to do this permutation. But the overall permutation is even. Applying another move means applying another even permutation. The product of two even permutations is an even permutation, so you will never get an odd permutation.

This is precisely where my confusion about his rigour lies.
How do you know that, regardless of the swap sequence applied, that there will be an even number of swaps? Sure, if you add up the swaps in the individual quarter turns, there will be an even number of swaps, since even+even=even. But how do you know that there is not some obscure sequence of an odd number of swaps that can cause a transition between two legal states?

 

[Stefan]

This is precisely where my confusion about his rigour lies.

This is precisely why I gave you the two links in the very first reply, both explaining parity of permutation.

 

[Herbert Kociemba]

I'd say it's rather only 2^11 possibilities, as one is equivalent to its negation, where the other facelet is chosen for each position. Because of the desire to call all edges oriented correctly when the cube is solved, all *piece* references get flipped as well, so all edges in a certain cube state have the same orientation in both definitions.

You are right. Thanks for the correction.

 

[Stefan]

Yeeesss. Corrected Tom and Herbert in one day (and made a fool of myself with Chester, but let's generously ignore that ). Maybe one day I'll reach their level of math+code cube foo...

This is precisely where my confusion about his rigour lies.

This is precisely why I gave you the two links in the very first reply, both explaining parity of permutation.

Maybe third time's a charm, here's yet another explanation, similar to what I once made up myself so I like it

http://arcsecond.wordpress.com/2008/12/06/answer-parity-of-permutations/

My view, though, is that Ryan is writing a cube proof. He's not writing a math book. It's not his job to explain and prove all the math he uses that is perfectly explained and proven elsewhere. It's totally fine to just *apply* that math to the topic at hand, the cube proof. When you take a taxi, do you complain that it's an incomplete and bad ride just because the driver doesn't explain to you how the engine works?

 

[riffz]

I cannot see a hole in the permutation argument. A quarter move consists of 2 4-cycles, one for the corners and one for the edges. A 4-cycle is an odd permutation, you need an odd number of swaps to do this permutation. But the overall permutation is even. Applying another move means applying another even permutation. The product of two even permutations is an even permutation, so you will never get an odd permutation.

This is precisely where my confusion about his rigour lies.
How do you know that, regardless of the swap sequence applied, that there will be an even number of swaps? Sure, if you add up the swaps in the individual quarter turns, there will be an even number of swaps, since even+even=even. But how do you know that there is not some obscure sequence of an odd number of swaps that can cause a transition between two legal states?

I don't understand what you could possibly be confused about.

Doesn't it follow that since any legal state on the cube is reached by applying quarter turns, that the resulting state will also have an even number of permutations?

 

[Stefan]

Doesn't it follow that since any legal state on the cube is reached by applying quarter turns, that the resulting state will also have an even number of permutations?

No.

First of all, "even number of permutations" is nonsense, you mean even number of *transpositions*.

The effect of one quarter turn can be described as six transpositions, but if you make a thousand quarter turns, do you need 6000 transpositions to solve the cube, and is doing the scramble backwards the only way to solve it? No, of course not. The permutations combine and cancel out. And it's not completely obvious that this combining keeps the parity of the number of transpositions.

 

[riffz]

Doesn't it follow that since any legal state on the cube is reached by applying quarter turns, that the resulting state will also have an even number of permutations?

No.

First of all, "even number of permutations" is nonsense, you mean even number of *transpositions*.

The effect of one quarter turn can be described as six transpositions, but if you make a thousand quarter turns, do you need 6000 transpositions to solve the cube, and is doing the scramble backwards the only way to solve it? No, of course not. They permutations combine and cancel out. And it's not completely obvious that this combining keeps the parity of the number of transpositions.

Yes, I meant swaps, not permutations. :fp

I guess isn't as intuitively clear as I arrogantly assumed. My apologies.