# Rigorous Proof of Laws



## PeterNewton (Jun 3, 2010)

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 (Jun 4, 2010)

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 (Jun 4, 2010)

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


----------



## Matt S (Jun 4, 2010)

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 (Jun 4, 2010)

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 (Jun 4, 2010)

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 (Jun 4, 2010)

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 (Jun 4, 2010)

blah said:


> 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 (Jun 4, 2010)

StefanPochmann said:


> blah said:
> 
> 
> > 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.
> ...



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.



StefanPochmann said:


> 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 (Jun 4, 2010)

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 (Jun 4, 2010)

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 (Jun 4, 2010)

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 (Jun 4, 2010)

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 (Jun 4, 2010)

riffz said:


> 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 (Jun 4, 2010)

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


----------



## Stefan (Jun 4, 2010)

blah said:


> StefanPochmann said:
> 
> 
> > 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.
> ...


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



blah said:


> 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.



blah said:


> 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.



PeterNewton said:


> 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 (Jun 4, 2010)

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 (Jun 4, 2010)

PeterNewton said:


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


DYOH


----------



## blah (Jun 4, 2010)

StefanPochmann said:


> blah said:
> 
> 
> > StefanPochmann said:
> ...


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 (Jun 5, 2010)

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.


----------



## Stefan (Jun 5, 2010)

Matt S said:


> 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.



Matt S said:


> _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 (Jun 5, 2010)

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


----------



## Stefan (Jun 5, 2010)

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 (Jun 5, 2010)

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 (Jun 5, 2010)

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 (Jun 5, 2010)

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



blah said:


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





blah said:


> 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 (Jun 5, 2010)

*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 (Jun 6, 2010)

@ 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 (Jun 6, 2010)

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 (Jun 6, 2010)

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 (Jun 6, 2010)

> 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 (Jun 6, 2010)

Herbert Kociemba said:


> 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.



Herbert Kociemba said:


> 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.



Herbert Kociemba said:


> 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.



PeterNewton said:


> 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 (Jun 6, 2010)

PeterNewton said:


> 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 (Jun 6, 2010)

Herbert Kociemba said:


> 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 (Jun 6, 2010)

PeterNewton said:


> 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 (Jun 6, 2010)

StefanPochmann said:


> 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 (Jun 7, 2010)

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...



StefanPochmann said:


> PeterNewton said:
> 
> 
> > This is precisely where my confusion about his rigour lies.
> ...



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 (Jun 8, 2010)

PeterNewton said:


> Herbert Kociemba said:
> 
> 
> > 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.
> ...



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 (Jun 8, 2010)

riffz said:


> 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 (Jun 8, 2010)

StefanPochmann said:


> riffz said:
> 
> 
> > 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?
> ...



Yes, I meant swaps, not permutations. :fp

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


----------



## PeterNewton (Jun 9, 2010)

All right Stefan, I understand that stuff about parity now. Took some time, but I get it, thanks. But like you and Herbert said, only the impossible is proven, so it is only an upper bound. How would I go about proving the possible, the lower bound? Only then can one say that since lower bound = upper bound, this is the exact fraction of all conceivable states that are possible to reach through legal moves.


----------



## Matt S (Jun 9, 2010)

The lower bound is proven by construction. Essentially, you demonstrate a method of generating any cube state that isn't explicitly disallowed by the Laws.

I think the most straightforward way is to prove that T-Perm (or any other that swaps two edges and two corners), a two edge flipper, a two corner twister, and congugates are sufficient to generate the positions. Actually, T-Perm and congugates alone are sufficient to do the orienting also, but that's more complicated to prove.


----------



## Stefan (Jun 9, 2010)

Yeah, show a way to actually construct (or equivalently, solve) the possible states. Again have a look at this:
http://arcsecond.wordpress.com/2008/12/06/answer-parity-of-permutations/
Note how part one proves that any permutation is possible by describing a way to do it.


----------



## PeterNewton (Jun 10, 2010)

Hmmm ok I was able to do this for the 3x3 without too much difficulty, since I am familiar with the 3x3 laws. But my friend and I are doing a project on the general formulas for the number of combinations of any odd nxn cube and any even nxn cube (one for odd, one for even).
Unfortunatly, neither of us are very good with big cubes and so, while we understand orbits and such, we do not know the laws for a general odd or even cube. Do you mind listing them or linking them?
The upper bounds should not be too difficult to derive then using methods similar to the 3x3. But then what would the construction algorithms be for deriving the lower bounds? I'm guessing they constitute of things like 'there is an alg to transpositon (transepose?) two wing edges in orbit in an odd cube' and obviously a fair bit of additional logic to show that it can be extended to any two wings in orbit. What kind of these type exist in general for odd and/or even cubes?


----------



## mrCage (Jun 10, 2010)

Me and commutators are even 

Per


----------



## PeterNewton (Jun 10, 2010)

mrCage said:


> Me and commutators are even
> 
> Per



Huhhh? I think you forgot to finish typing or something.


----------



## PeterNewton (Jun 11, 2010)

All right. Forget what I said earlier. There are only 4 things that I need now to complete the proof.

I need confirmation that:
1) There is an algorithm that can switch two center pieces in the same orbit without disturbing the rest of the cubies, even or odd. Any pair case will do since the argument can then be extended to all possible pairs.
2) There is an algorithm that can switch two wing edges in the same orbit in an odd cube, or two edges in the same orbit in an even cube, without disturbing the rest of the cubies. Again, any pair case will do.

Proof that:
1) There is only one possible orientation of any center piece on even or odd cubes, other than central centers, for each location it can occupy in its orbit.
2) There is only one possible orientation of any non-central edge on odd cubes and any edge on even cubes for each location it can occupy in its orbit.

For the two proofs, I know that you can talk about how Verdes' general nxnxn design does not allow it because of the internal structure, but I will use that only as a last resort, since it is not very elegant.

EDIT: maybe I should explicitly say that some help for the above 4 would be nice...


----------

