Rigorous Proof of Laws

[PeterNewton]

Is there a website or video where there are rigorous proofs for the Cube Laws? Specifically, the following four:
1) Only one pair of edges cannot be swapped.
2) Only one pair of corners cannot be swapped.
3) Only one edge cannot be flipped.
4) Only one corner cannot be twisted.

I've tried Heise's site but his proofs are... not very good. For example, he says that one quarter turn equals 6 swaps, which is even, and since half of the conceivable states are represented by even swaps, only half are then solvable. HUH? There are several missing points here (mostly dealing with 'mutually exclusive' issues), but even if those are ignored, from my view, the only thing he has proven is that all legal states can be solve with a number of swaps that is a multiple of 6; i.e. at least 1/6 of all conceivable states are solvable, NOT 1/2.

Something that involves understandable logic, and not group theory, would be nice because I'm still in high school.
Oh and this is for a paper I have to write.

 

[Stefan]

I disagree. Ryan's page is very good, especially for the orientations. But have a look at these as well:

http://www.jaapsch.net/puzzles/theory.htm
http://en.wikipedia.org/wiki/Parity_of_a_permutation

For those who might not know Ryan's page: http://www.ryanheise.com/cube/cube_laws.html

 

[riffz]

Heise's explanation makes perfect sense to me...

 

[Matt S]

Heise's "proofs" are nice informal outlines of what a formal proof would contain, but I can see how the part about permutations would be tough to follow for someone who hasn't studied permutations in group theory. It takes for granted the fact that even permutations (permutations that make an even number of inversions) can't be replicated as odd permutations (odd number of inversions), and that the composition of even permutations is always another even permutation.

By the way, you might notice that a quarter turn is actually an odd permutation on edges and corners when each is considered independently. This is the reason why all algorithms that leave either corner or edge permutation untouched must contain an even number of quarter turns.

 

[Forte]

I always thought that was funny too, because for example, if you have a double turn scramble and do an R2, then R2 is an even permutation, but you can't assume that because of that, all even permutations are possible. I'm not sure if the OP and I are wondering about the same thing, but I was wondering if there was a proof as to why all of the even permutations are possible. (The R move shows that all the positions have to have even permutation, but that doesn't mean that all of the even permutations are possible)

Of course, I could just use conjugated PLLs to prove it, but it's always bothered me that I haven't been able to come up with anything cleaner

 

[blah]

Heise's "explanation" says nothing about why it's okay to use the "most common frame of reference for corner/edge orientation," or how/why such a frame of reference came about, or how/why such a frame of reference is "legit," etc.

Throwing such facts out there and expecting everyone to just accept them as they are is not what I would call good explanation; it bothers me.

 

[keemy]

I just read Heise's site and they seem like pretty good outlines for why such positions are impossible to reach (the only really hazy parts are the definitions for orientation imo but if you accept them the rest should be fine) now some of the complaints I see are that he doesn't show that all 'even' permutations are reachable but like notice the original questions you have only talk about the impossibility of of these positions not the possibility of all other positions.

But as for a proof of the possibility of all other positions you can have a constructive proof by showing that you have a 3 cycle for corners and edges (which are 2 2 cycles) you have a 2 edge flip and you have a way to rotate 2 corners (one to orientation 1 and another to orientation 2) and a lets just say J perm (1 2cycle for edges and 1 2 cycle for corners what you use doesn't matter) then just show that every position (with the properties we wanted) is solvable using these (basically make a method using these as your only moves) thus every position is reachable by doing the reverse.

 

[Stefan]

Heise's "explanation" says nothing about why it's okay to use the "most common frame of reference for corner/edge orientation," or how/why such a frame of reference came about, or how/why such a frame of reference is "legit," etc.

For what he's proving, isn't it sufficient to do it with *one* frame of reference? Basically you're requesting "Ok so you proved it one way, but can you also prove it another way?".

Besides, I can give you a definition of EO where an odd number of misoriented edges is possible. It's just not a very useful definition.

 

[blah]

Heise's "explanation" says nothing about why it's okay to use the "most common frame of reference for corner/edge orientation," or how/why such a frame of reference came about, or how/why such a frame of reference is "legit," etc.

For what he's proving, isn't it sufficient to do it with *one* frame of reference? Basically you're requesting "Ok so you proved it one way, but can you also prove it another way?".

That is not what I'm requesting. You missed my point, I think.

Using P to prove Q without first showing P's validity (especially when P is not at all trivial/obvious) is not what I'd call sound logic. All Heise did was declare that "Oh, so most people happen to use this definition for correct orientation, now let's move on to prove other stuff using this..." It just so happens that in this case the "most common frame of reference" turns out to be valid. It's the assumption that such an "arbitrary" frame of reference is valid that bothers me.

And the fact that both P and Q turn out to be necessary and sufficient for each other bothers me too.

Besides, I can give you a definition of EO where an odd number of misoriented edges is possible. It's just not a very useful definition.

That'd be a good addition to the proof, but still not enough to make it "rigorous," whatever that means.

The fact that he used *one* frame of reference to prove it without explaining its origins simply suggests that he's trying to get away with a proof by example. Of course, I highly doubt that he has any motivation to do something like that. It's the proof I'm attacking, not the person.

--------------------------------------------------

To establish this, it is necessary to decide on a frame of reference for correct edge orientation [But why?], regardless of where an edge is positioned on the cube. The most common frame of reference is to say that an edge in the wrong position has correct orientation if, when it is moved to its correct position using only the left, right, top and bottom faces, it would have correct orientation [But why? How do you know it's okay to use this frame of reference?]. Using this frame of reference, it is easy to see that any move on the left, right, top and bottom faces will always flip zero edges, which is an even number [Circular? I think the frame of reference originated from this definition. Of course, I may be wrong.].

 

[Matt S]

Remember, Heise's proofs don't need to define orientation in any special way. He just needs to specify a property that is maintained through all possible turns on the cube that is broken in the "misoriented" cube (which is basically what Stephen said). His definition of edge orientation is well defined (the orientation as defined is unique for each edge (ie. no edge can be both oriented and disoriented by his definition)), and he outlines the proof that all turns on the cube maintain parity (even number of disoriented edges). Since the solved cube has even parity, and the one edge flipped cube has odd parity, he has proven that you can't generate the one-edge-flipped Cube from the solved state.

 

[blah]

And it is precisely the fact that you needed to explain all of this right here that makes Heise's proofs simply outlines, as you said it was, not rigorous ones.

 

[PeterNewton]

Most of the points made by you guys are ones that I was wondering about too, like assuming the frame of reference and proof of all even permutations.

And I read most of Jaap's page, which is not very rigorous in its treatment either. It is better than Heise's page in some ways, but it is also worse in some ways. An example of the lack of rigour would be his talk of the Crossing Points; he never even proves that these points of crossing have anything to do with cubes or swapping pieces.

What I, and a lot of other people, are noticing is that there are either leaps in imagination that cannot be followed or that the site-makers do not know what they're talking about either.

So going back to my original request, is there a more rigorous non-group theory source for proofs?

 

[riffz]

But taking any frame of reference would lead to the same conclusion... The fact that it's arbitrary doesn't make a difference in the end.

 

[PeterNewton]

But taking any frame of reference would lead to the same conclusion... The fact that it's arbitrary doesn't make a difference in the end.

My problems with the frame of reference are the same as blah's.

Also, similar to my first post, even if we take the frame of reference for granted, Heise says that "... a 90 degree move will flip all 4 edges, which is again an even number of flips. Therefore, it is never possible, using only legal moves, to flip an odd number of edges."
Ok sure, but by this logic, he has only established that at least 1/4 of the edge orientations are reachable. His title is "Only half of the edge orientations are reachable". He only set a lower bound. To prove his point, he must show that 1/2 is both the minimum that it cannot be exceeded, therefore also being the maximum.

 

[Swordsman Kirby]

Flip edges ABCD, and then BCDE. There, half.

 

[Stefan]

Besides, I can give you a definition of EO where an odd number of misoriented edges is possible. It's just not a very useful definition.

That'd be a good addition to the proof

Um... no? It's obviously totally worthless for it?

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

Why? Because if you don't define edge orientation, you can't prove or even claim anything about it in the first place? Geez.

And it is precisely the fact that you needed to explain all of this right here that makes Heise's proofs simply outlines

Just because you misunderstand it doesn't mean it's not there.

And I read most of Jaap's page, which is not very rigorous in its treatment either. It is better than Heise's page in some ways, but it is also worse in some ways. An example of the lack of rigour would be his talk of the Crossing Points; he never even proves that these points of crossing have anything to do with cubes or swapping pieces.

You're kidding, right?

Though yeah, while Ryan does a good job proving the impossible, he doesn't really bother to prove the possible. I assume that's cause it's the more cumbersome and boring part.

 

[PeterNewton]

Nope I'm not kidding. Maybe you could tell me your interpretation of Jaap's 'Permutations'? I especially don't understand the part about 'If you think of the lines as loose threads, and that you physically untangle them, you will see that each time you uncross two threads, the number of crossings always decreases by 2. When you untangle all the threads, the number of crossings then decreases by a multiple of 2. '

And, so is there a place where I can see the "more cumbersome and boring part"?

EDIT: erm, i meant Crossing NUMBER in my earlier post, sorry.

 

[Johannes91]

And, so is there a place where I can see the "more cumbersome and boring part"?

DYOH

 

[blah]

Besides, I can give you a definition of EO where an odd number of misoriented edges is possible. It's just not a very useful definition.

That'd be a good addition to the proof

Um... no? It's obviously totally worthless for it? [Condescending]

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

Why? Because if you don't define edge orientation, you can't prove or even claim anything about it in the first place? Geez. [Condescending]

And it is precisely the fact that you needed to explain all of this right here that makes Heise's proofs simply outlines

Just because you misunderstand it doesn't mean it's not there. [Condescending]

I'm done trying to bring my point across.

Putting me down and making assumptions about me simply because you don't get my argument is cheap and stupid and you know it.

The questions I asked do *not* reflect my ignorance or misunderstanding; they were posed to show that there are still holes in his proof waiting to be answered, thereby showing that it's "not rigorous." This is rigor.

 

[Matt S]

blah, while I completely agree that Heise's proofs are informal and not fully rigorous (heck, it's one short html page for three proofs), I don't understand your objection to him arbitrarily defining edge orientation. His sole requirement is to define a property of the cube that is maintained by all legal moves but broken in the state he wants to prove impossible. The parity of edge orientations as he defines them is such a property. No more, no less. It's not really about defining edge orientation at all.

As Stephen mentioned, there are other reasonable definitions of edge orientation that allow for an odd number of misoriented edges to be created by legal moves. These are totally uninteresting for the proof, because they aren't useful for proving the bad cube impossible, and (obviously) they can't be used to prove it possible either.

For the curious, here's a definition of edge orientation that doesn't have its parity maintained:

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.

I'd call that an honest orientation definition, because no matter what position an edge is on the cube, its orientation flips between correct and incorrect if it's physically flipped without being permuted. However, there is no guarantee that there will be an even number of correctly oriented edges under this definition. Performing R U (thanks Stephen) on a solved cube demonstrates this. All edges are correctly oriented (by this definition) except the uf edge.

This is neat, I think, but totally extraneous to what Heise is proving.