Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Sun Apr 20, 2014 7:10 am

All times are UTC - 5 hours



Post new topic Reply to topic  [ 3 posts ] 
Author Message
 Post subject: Sketch of proof that "rotation" of sequences preserves order
PostPosted: Tue Dec 18, 2012 7:03 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Hey all. I've known that rotating a useful sequence preserves a lot of properties of the sequence but only recently did I realize it wasn't that hard to prove.

First, by rotation I meant that if you have a sequence of moves, [1, 2, 3, ... N] then rotating left by 1 would be the sequence [2, 3, ... N, 1]. Or more concretely, the rotations of the sequence [a, b, c] are [b, c, a] and [c, a, b].

By "preserve order" I mean that if you have a sequence that is a 3-cycle in a particular piece type, it will always be a 3-cycle in that piece type regardless of rotation.

Here is an example on the Rubik's cube. Take the move sequence [R', F, R, B', R', F', R, B]:
Attachment:
3x3x3_base_cycle.png
3x3x3_base_cycle.png [ 5.89 KiB | Viewed 865 times ]


Then if you rotate the move sequence left by 1 you get [F, R, B', R', F', R, B, R']:
Attachment:
3x3x3_rotate_l_1.png
3x3x3_rotate_l_1.png [ 5.81 KiB | Viewed 865 times ]


And if you rotate it left by 2 you get [R, B', R', F', R, B, R', F]:
Attachment:
3x3x3_rotate_l_2.png
3x3x3_rotate_l_2.png [ 5.9 KiB | Viewed 865 times ]


Notice that although the pattern of the pieces getting cycled changes, the sequence is still a 3-cycle in the corners? This is always true for rotation, regardless of the structure of the sequence (it doesn't have to be a commutator).

Sketch of Proof:

To simplify things I'm going to use a sequence that performs a 3-cycle but this can be arbitrarily extended.

Assume you have some move sequence S of length N [x1, x2, x3, ...xN] that performs a pure 3-cycle. Since the sequence performs a 3-cycle it has order 3 and S^3 = Identity

That is, S performed 3 times has no effect.

If you look at the sequence of moves performed for S^3 they are [x1, x2, x3, ... xN, x1, x2, x3, ... xN, x1, x2, x3, ... xN] and the move sequence traverses a cycle in the Cayley graph of the group. That is, the the sequence of moves forms a cycle of length 3N where the state of the puzzle repeats.

Since the moves x1, x2, x3, ... xN, x1, x2, x3, ... xN, x1, x2, x3, ... xN form a repeating cycle, you can start at any move in the S^3 sequence and after performing 3N moves you will be back at the state you started at. For example starting at x2:

x2, x3, ... xN, x1, x2, x3, ... xN, x1, x2, x3, ... xN, x1 = Identity

But as you can see, starting anywhere in S^3 is still a subsequence of moves performed 3 times. In this case x2, x3, ... xN, x1 3 times.

If a sequence performed 3 times is the Identity then the sequence order must be 3 (or divide 3 evenly).

But, starting anywhere in the S^3 cycle is the exact same thing as rotating the original sequence S.

That is, rotate_left(S) = x2, x3, ... xN, x1

So rotating a sequence always preservers the order.

The only hole in this proof that I can spot is that it actually only proves that rotating must either preserve the order or produce a sequence with order that is a factor of the original order. For 3, since 3 is prime that would mean it would either have to preserve the order 3 or produce a sequence with order 1 (an Identity sequence). I'm pretty sure it actually always preserver order and never reduces order but I'm not quite sure how to prove handle that case in the proof. It doesn't affect the usefulness of rotating sequences though so it doesn't matter.

Motivation for rotations:
As you can see in the screenshots above, even though rotating a sequence preserves the order, it doesn't necessarily preserve the pattern of the pieces being cycled (relative to each other). This means that if you have a sequence that performs a cycle and you don't like the pattern / shape of the cycle, you can rotate the sequence to see what other patterns are possible.

Also, in some cases you can rotate a sequence to cancel or combine moves. for example a conjugate sequence like A X A' where A is 1 move can always be reduced to just X. If you rotate it you get X A A' and the A and A' cancel, leaving just X.

Another useful reason for rotating a sequence is that for some commutator constructions, you can rotate an inner, nested commutator in such a way that it has a move cancel with some outer moves.

Finally, as we all know, move sequences can be inverted, mirrored (sometimes they are self-mirror though), and re-oriented on the puzzle. On a Rubik's cube with 24 orientations this means a single move sequence could have up to 2 * 2 * 24 = 96 variations. Rotating each of these variations has the chance of producing additional useful sequences.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: Sketch of proof that "rotation" of sequences preserves o
PostPosted: Tue Dec 18, 2012 7:59 pm 
Offline
User avatar

Joined: Fri Feb 18, 2011 5:49 pm
Location: New Jersey
I always thought of alg rotations as move-canceled conjugates:

If x1, x2, ... xn is a 3-cycle, then x1', x1, x2, ... xn, x1 is also a 3-cycle. Since x1', x1 is the identity, this is effectively the same as x2, x3, ... xn, x1

Is there something I'm missing as to why this doesn't qualify as a proof?


Top
 Profile  
 
 Post subject: Re: Sketch of proof that "rotation" of sequences preserves o
PostPosted: Tue Dec 18, 2012 8:07 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
DKwan wrote:
I always thought of alg rotations as move-canceled conjugates:

If x1, x2, ... xn is a 3-cycle, then x1', x1, x2, ... xn, x1 is also a 3-cycle. Since x1', x1 is the identity, this is effectively the same as x2, x3, ... xn, x1

Is there something I'm missing as to why this doesn't qualify as a proof?

I considered this too but I wasn't sure how to prove that a conjugate preserves order besides "it's obvious".

My hand-wavy reasoning is that any changes you make with A in A X A' must be undone with A' and so the only remaining effects are those that came from X.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 3 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: megaminxwin and 4 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group