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

TwistyPuzzles.com Forum

It is currently Wed Apr 16, 2014 10:50 pm

All times are UTC - 5 hours



Post new topic Reply to topic  [ 19 posts ] 
Author Message
 Post subject: Piece Adjacency & Lower Bounds for Commutator Lengths
PostPosted: Tue Jan 15, 2013 3:39 am 
Offline
User avatar

Joined: Fri Feb 18, 2011 5:49 pm
Location: New Jersey
Piece Adjacency

For a physical puzzle, or even a virtual puzzle with a visual representation like the ones on Gelatinbrain, pieces can be said to be adjacent if the stickers are immediately next to one another. However, this definition is insufficient for a puzzle that has no current visual interpretation such as the complex dodecahedron. Furthermore, what properties of piece types results in them actually having those adjacent stickers to begin with?

I am now defining adjacent pieces as ones whose grip patterns are identical except for a single grip. That is to say, when comparing the grip patterns between the two pieces, one pattern will include a grip that the other does not, and they will be otherwise identical. When I say "grip pattern" I mean the set of face-turns which move the piece. Here are two simple examples:

Attachment:
AdjacentPieces1.png
AdjacentPieces1.png [ 18 KiB | Viewed 2395 times ]

Attachment:
AdjacentPieces2.png
AdjacentPieces2.png [ 19.3 KiB | Viewed 2395 times ]

(black centers denote the grips for the yellow-highlighted piece)

Notice how in both cases, the grip which is different between the two pieces is actually the only grip which can be used to separate the two pieces. This should make intuitive sense, as the two pieces should move around together until the cut that goes between the two pieces is used.

If you start checking other puzzles to see how well this definition works, you will find there are some puzzles which seem to defy this interpretation of adjacency. Here is the dino cube as a simple example:

Attachment:
AdjacentPieces3.png
AdjacentPieces3.png [ 13.47 KiB | Viewed 2395 times ]

(the grey circles represent the grips for the highlighted piece)

These two edges are clearly "adjacent" on the physical puzzle, but according to my definition based on the grip patterns, they are not adjacent pieces because they differ by two grips. This can happen because this puzzle has lines on the surface cut pattern which are actually representative of more than one grip; in this case grips ULF and URB share the surface-cut between the UF and UR edges. Under my definition of adjacent pieces, I therefore interpret this puzzle as having additional "missing" pieces which have 0 surface-area, essentially "filling in the gaps" between the pieces you can see. Cases like this with missing pieces will occur if and only if there are cut-lines on the surface which are used for multiple grips.

Attachment:
AdjacentPieces4.png
AdjacentPieces4.png [ 7.85 KiB | Viewed 2395 times ]


In this picture of the dino cube, I am interpreting there being an additional piece along the yellow lines which spans the gap between the two edge pieces but has surface area of 0, so it does not need to be solved. In this way, under my definition of adjacent pieces, the UR edge is adjacent to this invisible piece which is adjacent to the UF edge. UR and UF are not adjacent pieces. Other simple examples of pieces that are not adjacent under my definition can be found with the 2x2x2 and the helicopter cube.


Lower Bound for Commutator Lengths (one application of this definition of piece adjacency)

When trying to find a pure commutator for a piece, there is a certain amount of "work" that has to be done, which directly affects how long the commutator must be at a minimum. Let us first assume we are aiming for an algorithm of the form [x,y] where y=1. For the commutator to be pure, the moves in the x-part must replace a single piece within the set of pieces moved by the y-move grip, and leave the rest untouched. This requires separating the target piece from all adjacent pieces, swapping it with a new piece, and then reassembling the new piece with the adjacent pieces. In other words, I hypothesize that the best possible case for efficient commutators is if it can be written in the form [[n:1],1] where the number of setup moves required for n is sufficiently large to separate the target piece from all adjacent pieces.

Because the y-move and the move nested in the middle of the conjugate x-part are both capable of separating adjacent pieces from the target piece, the minimum length for n can be 2 less. In other words, [[(n-2):1],1] where n is the number of adjacent pieces to the target piece. This means a lower bound of length for the x-part of a pure-commutator is 2(n-2)+1 = 2n-3. This lower bound assumes that slice moves count as two moves because they can potentially break away two adjacent pieces from the target piece, one on either side of the target piece.

Megaminx Example:
Corners: 3 adj. pcs. --> 2(3)-3 = 3 --> lower bound = [3,1] --> [C, B, C',D, C, B', C', D']
Edges: 4 adj. pcs. --> 2(4)-3 = 5 --> lower bound = [5,1] --> [B, D',C, D, B', A, B, D', C',D, B', A']

Dino Cube Example:
Edges: 2 adj. pcs. --> 2(2)-3 = 1 --> lower bound = [1,1] --> [URF, LUF, URF', LUF']
Note: The formula uses my definition for adjacent pieces explained above, so it is only 2 pieces, not 4.

For these two examples, the shortest pure commutators just happen to be equal to the lower bound, but in many other cases the shortest commutator will be longer.

Slice moves actually create an exception to this lower bound. If a slice move is used for the y-move or the move nested in the x-part conjugate, it is possible for it to do more "work" in fewer moves than would normally be possible. It can separate two adjacent pieces and make the piece swap from the conjugate in only 2 moves. Normally, without a slice move, this would require 3 moves minimum. This happens because the slice move lets you split an extra adjacent piece without having to undo this move as a normal setup in the conjugate. In all other cases, slice moves do not accomplish any extra "work", therefore we can simply subtract 2 from the equation to compensate for these two exception cases. Because this case is actually pretty rare (I think), it is perhaps more useful to stick with the 2n-3 equation as the general case, but with a caveat that in some special cases 2n-5 may be possible.

The 3x3 edges offer an example of this exception: [F, U&2, F', U, F, U'&2, F', U']
Counting the slice moves as double-moves, this is a [4,1], which falls under the unmodified lower bound of [5,1], but not under the modified lower bound of [3,1].

One interesting combination of both of these concepts is the complex dodecahedron. In that puzzle, every single piece has exactly 12 adjacent pieces (found by changing each of the 12 grips one at a time). Therefore, I can say there is a lower bound of pure commutators for the complex dodecahedron of 2(12)-5 --> [19,1], regardless of which piece you choose. Quite intimidating! I am guessing the shortest actual pure commutator for the complex dodecahedron may be much much longer than this since it is just a lower bound.


Other Potential Applications of These Ideas

Algorithm Searching

When searching for pure commutators for a puzzle, either by hand or with a computer program, knowing a lower bound can help eliminate what needs to be searched. Furthermore, because you know that all of the cuts adjacent to the target piece must be used in the algorithm to have a pure commutator, you can probably approach the search more efficiently than just trying every combination of turns.

Generating Visualizations of Theoretical Puzzles

Although I haven't tried doing this myself yet, I believe the concept of adjacent pieces can be used in developing a process to go from a given set of piece types to a visualization of a puzzle which would contain exactly those specified pieces. I haven't thought through any details for this yet though.

________________

I've been throwing these ideas at Brandon over the past few days, so hopefully by now my explanation of them is "refined" enough to be comprehensible. Perhaps these concepts can spark some other ideas/applications. I'm interested to hear what others think of this definition of piece adjacency.


Top
 Profile  
 
 Post subject: Re: Piece Adjacency & Lower Bounds for Commutator Lengths
PostPosted: Tue Jan 15, 2013 8:55 am 
Offline
User avatar

Joined: Mon Jul 21, 2008 4:52 am
Location: Brighton, UK
DKwan wrote:
When trying to find a pure commutator for a piece, there is a certain amount of "work" that has to be done, which directly affects how long the commutator must be at a minimum. Let us first assume we are aiming for an algorithm of the form [x,y] where y=1. For the commutator to be pure, the moves in the x-part must replace a single piece within the set of pieces moved by the y-move grip, and leave the rest untouched. This requires separating the target piece from all adjacent pieces, swapping it with a new piece, and then reassembling the new piece with the adjacent pieces.
I made the same assumption until I discovered a counter-example, which was a [10,1] pure cycle for the Little Chop where two extra pieces opposite each other change places after 10 moves, and the extra exchange cancels out. A short while later Brandon and Katja found an even more interesting example with non-symmetric changes that cancel out: Little Chop pure [7,1] cycle. Brandon also found a remarkable pure [9,1] algo to cycle the Little Chop equivalent pieces of Gelatinbrain 3.3.6 or 4.3.4, where the puzzle looks quite mangled within the region to be twisted by the y move, but again all the changes cancel each other out.

I suspect that your assumption is often true though, and if we are considering the length of commutators that can reasonably be found by a human being rather than via a computer search (because it is so much harder to see where extra exchanges of pieces will cancel out), it is probably a reasonable one to work with.

Thanks for your interesting post! Brandon may have some interesting things to add to this thread, as I believe he has been working on a theory along similar lines. I'm going to be on the move for the next several days but I will be catching up whenever I can.


Top
 Profile  
 
 Post subject: Re: Piece Adjacency & Lower Bounds for Commutator Lengths
PostPosted: Tue Jan 15, 2013 9:07 am 
Offline
User avatar

Joined: Fri Feb 18, 2011 5:49 pm
Location: New Jersey
Hi Julian!

The "temporary swap principle" doesn't actually get you past this lower bound equation though. You still need to break away the piece from all adjacent pieces, the temp swap only lets you leave the pieces in the y-grip less pure. Furthermore, I am hypothesizing that even in cases where the shortest commutator may take another form, that commutator will be less efficient than what my formula prescibes. If you check all of the examples you listed, those algs are longer than what my rule suggests as a minimum.


Top
 Profile  
 
 Post subject: Re: Piece Adjacency & Lower Bounds for Commutator Lengths
PostPosted: Tue Jan 15, 2013 9:17 am 
Offline
User avatar

Joined: Mon Jul 21, 2008 4:52 am
Location: Brighton, UK
DKwan wrote:
The "temporary swap principle" doesn't actually get you past this lower bound equation though. You still need to break away the piece from all adjacent pieces, the temp swap only lets you leave the pieces in the y-grip less pure. Furthermore, I am hypothesizing that even in cases where the shortest commutator may take another form, that commutator will be less efficient than what my formula prescibes. If you check all of the examples you listed, those algs are longer than what my rule suggests as a minimum.
Oops, I see what you mean. I can't imagine how a pure commutator could work and be shorter than the length given by your formula.


Top
 Profile  
 
 Post subject: Re: Piece Adjacency & Lower Bounds for Commutator Lengths
PostPosted: Tue Jan 15, 2013 12:17 pm 
Offline
User avatar

Joined: Fri Jan 29, 2010 2:34 pm
Location: Scotland, UK
DKwan wrote:
The 3x3 edges offer an example of this exception: [F, U&2, F', U, F, U'&2, F', U']
Counting the slice moves as double-moves, this is a [4,1], which falls under the unmodified lower bound of [5,1], but not under the modified lower bound of [3,1].

I'm probably misunderstanding something about your post here, but M' U2 M U2 (I'm not sure how to do this in Gelatinbrain notation and it isn't loading for me just now for some reason so I can't check) is a 6-move [2,1] commutator for edges using slice moves. This is an unusual scenario to have for general solving though, I don't even know if similar sequences even exist on other puzzles.


Top
 Profile  
 
 Post subject: Re: Piece Adjacency & Lower Bounds for Commutator Lengths
PostPosted: Tue Jan 15, 2013 12:20 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
bobthegiraffemonkey wrote:
I'm probably misunderstanding something about your post here, but M' U2 M U2 (I'm not sure how to do this in Gelatinbrain notation and it isn't loading for me just now for some reason so I can't check) is a 6-move [2,1] commutator for edges using slice moves. This is an unusual scenario to have for general solving though, I don't even know if similar sequences even exist on other puzzles.

The caveat is that this lower bound is for "pure" commutators. The sequence you posted twists two centers.

EDIT: I should also point out that if you don't care about centers then you don't have to count them as adjacent pieces. In that case only the two corners are adjacent so you get ((2 * 2) - 3) = [1,1] lower bound.

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


Top
 Profile  
 
 Post subject: Re: Piece Adjacency & Lower Bounds for Commutator Lengths
PostPosted: Tue Jan 15, 2013 1:14 pm 
Offline

Joined: Fri Apr 01, 2011 10:58 am
Location: Stockholm, Sweden
bobthegiraffemonkey wrote:
DKwan wrote:
The 3x3 edges offer an example of this exception: [F, U&2, F', U, F, U'&2, F', U']
Counting the slice moves as double-moves, this is a [4,1], which falls under the unmodified lower bound of [5,1], but not under the modified lower bound of [3,1].

I'm probably misunderstanding something about your post here, but M' U2 M U2 (I'm not sure how to do this in Gelatinbrain notation and it isn't loading for me just now for some reason so I can't check) is a 6-move [2,1] commutator for edges using slice moves. This is an unusual scenario to have for general solving though, I don't even know if similar sequences even exist on other puzzles.

Well, if I'm not mistaken, M counts as two moves :P (R, L')

Also, what Bmenrigh already said.

_________________
I'm just a swedish speedsolver/twisty puzzler.

This is my WCA-profile.


Top
 Profile  
 
 Post subject: Re: Piece Adjacency & Lower Bounds for Commutator Lengths
PostPosted: Tue Jan 15, 2013 1:22 pm 
Offline
User avatar

Joined: Fri Jan 29, 2010 2:34 pm
Location: Scotland, UK
bmenrigh wrote:
The sequence you posted twists two centers.


I'm guessing then that the analysis assumes every piece has visible orientation? I don't think that was stated (I'll re-read the post anyway to understand it better) and the images don't show puzzles with visible orientation of centres, so I assumed it wasn't relevant.


Top
 Profile  
 
 Post subject: Re: Piece Adjacency & Lower Bounds for Commutator Lengths
PostPosted: Tue Jan 15, 2013 1:34 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
bobthegiraffemonkey wrote:
bmenrigh wrote:
The sequence you posted twists two centers.


I'm guessing then that the analysis assumes every piece has visible orientation? I don't think that was stated (I'll re-read the post anyway to understand it better) and the images don't show puzzles with visible orientation of centres, so I assumed it wasn't relevant.
Dan's lower bound calculation and adjacency definition don't "know" anything about the adjacent pieces, how many of them there are, how many orientations they have, etc. The calculation simply says you can't separate a piece from the adjacent pieces below the lower bound so if you have a commutator under the lower bound you must have affected adjacent pieces.

How those pieces were affected is totally open-ended and could be permutation or orientation or both.

You can (always?) separate a piece from its adjacent pieces within the lower bound but the restrictions on an [x,1] commutator are a bit higher than that. In addition to separating a piece from its neighbors, you must do so in a way that leaves room for the Y portion of the commutator (one move in a [x,1] sequence). This is why many practical commutators are above the lower bound.

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


Top
 Profile  
 
 Post subject: Re: Piece Adjacency & Lower Bounds for Commutator Lengths
PostPosted: Tue Jan 15, 2013 1:41 pm 
Offline
User avatar

Joined: Fri Feb 18, 2011 5:49 pm
Location: New Jersey
Bob,

My apologies for the lack of clarity. In my opinion, it doesn't matter whether or not the center rotation is visible. That algorithm rotates 2 face centers so it isn't pure regardless of how the puzzle looks. For a different example, consider a puzzle with identical pieces. You can simulate a single swap by doing a 3 cycle with 2 pieces of the same color and a third of a different color. Despite this I would not call it a 2 cycle, it is still a 3 cycle even though you cannot tell the difference.

However to answer your question directly I suppose the answer has to be "yes it assumes visible orientations for all pieces".


Top
 Profile  
 
 Post subject: Re: Piece Adjacency & Lower Bounds for Commutator Lengths
PostPosted: Tue Jan 15, 2013 3:18 pm 
Offline
User avatar

Joined: Fri May 06, 2005 10:13 am
Location: Norway
Grip has nothing to do with adjacency. It is a physial property. If two pieces have an external surface with some touching edge they are adjacent. No more and no less.

A commutator has a minimum of 4 turns. ABA'B' where A and B both are single turns. A' is inverseof the A sequence of turns etc. I fail to see how the 2 things are connected. For a commutator to make up something useful (like a 3-cycle) we must replace some piece in some layer by part A and turn that same layer with B and complete the commutator with A'B'. Of course this principle has exceptions. On bigger cubes cycles on corners, edges or centers can be made with short simple commutators. On centers a "long" cycle may seem like a swap - because pieces of same color are involved. Example: do r' u r U2 r' u' r U2 on a solved 4x4x4 cube. This is a commutator of the form i gave with A=r'ur and B=U2.

Enough babbling ... :wink:

Per

_________________
"Life is what happens to you while you are busy making other plans" -John Lennon, Beautiful Boy


Top
 Profile  
 
 Post subject: Re: Piece Adjacency & Lower Bounds for Commutator Lengths
PostPosted: Tue Jan 15, 2013 3:33 pm 
Offline
User avatar

Joined: Fri Feb 18, 2011 5:49 pm
Location: New Jersey
perfredlund wrote:
Grip has nothing to do with adjacency. It is a physial property. If two pieces have an external surface with some touching edge they are adjacent. No more and no less.

Yes, as I mentioned at the top of my post, the definition of physical pieces touching is the "obvious" definition for puzzles which have a visual model for them. However, what would you say defines adjacent pieces on a theoretical puzzle like the complex dodecahedron which has no physical or visual representation? There is no way to know which pieces would physically be touching. That is why I have come up with an alternate definition for "adjacent" in a more abstract sense.

perfredlund wrote:
A commutator has a minimum of 4 turns. ABA'B' where A and B both are single turns. A' is inverseof the A sequence of turns etc. I fail to see how the 2 things are connected. For a commutator to make up something useful (like a 3-cycle) we must replace some piece in some layer by part A and turn that same layer with B and complete the commutator with A'B'. Of course this principle has exceptions. On bigger cubes cycles on corners, edges or centers can be made with short simple commutators. On centers a "long" cycle may seem like a swap - because pieces of same color are involved. Example: do r' u r U2 r' u' r U2 on a solved 4x4x4 cube. This is a commutator of the form i gave with A=r'ur and B=U2.

The section about commutators isn't really trying to explain how/why a commutator works, but rather trying to come up with a lower bound for how long a pure commutator has to be for a given piece (for which we might not yet know the most efficient algorithm for). So with your example of creating a 3-cycle on a 3x3, yes it is easy to make a [3,1] 3-cycle for the corners, but how can you "prove" that this is the shortest possible algorithm (without enumerating all possible sequences)? The intent of this idea isn't really meant for standard nxnxn cubes, but rather for more complex puzzles with piece types that are not yet fully understood.


Top
 Profile  
 
 Post subject: Re: Piece Adjacency & Lower Bounds for Commutator Lengths
PostPosted: Wed Jan 16, 2013 1:40 am 
Offline
User avatar

Joined: Thu Jul 23, 2009 5:06 pm
Location: Berkeley, CA, USA
This is an EXCELLENT analysis. I've been thinking along this grip pattern thing for a long time since the complex puzzles were proposed. But I've never thought about defining adjacency based on gripping. It's very interesting and inspiring.

I view the following argument as the center of your analysis:

DKwan wrote:
Because the y-move and the move nested in the middle of the conjugate x-part are both capable of separating adjacent pieces from the target piece, the minimum length for n can be 2 less.


Basically you are saying, "it takes n steps to separate n adjacent pieces from a given piece." It's not a trivial argument, but I think it can be made rigorous quickly. I'd call it "Separation Lemma". This would be a standalone result of independent interest.

I see some counter examples coming in the replies. They are mainly about the traditional commutator construction is not necessarily the best way to find 3-cycle. When you apply Separation Lemma in a more rigorous way, maybe the eventual result is not about commutators. What is the eventual result? I don't know...


Top
 Profile  
 
 Post subject: Re: Piece Adjacency & Lower Bounds for Commutator Lengths
PostPosted: Wed Jan 16, 2013 1:51 am 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
schuma wrote:
I see some counter examples coming in the replies. They are mainly about the traditional commutator construction is not necessarily the best way to find 3-cycle. When you apply Separation Lemma in a more rigorous way, maybe the eventual result is not about commutators. What is the eventual result? I don't know...

I haven't been able to find any counter-examples and in most cases the shortest commutator (as found by a computer) is much longer than the lower bound due in part to the need to isolate a piece in a move, not just separate it from its adjacent neighbors.

In the distant future when I have more time I plan on trying to find a way to use the adjacent piece grip deltas to dramatically prune the moves the program tries. There may even be a way to nearly construct a commutator directly by looking at the grip patterns and adjacent piece grip deltas.

I would also like to revisit the short (10 and 11 move) Pentultimate Corner routines. There are probably hidden insights in those routine that could be used for shortening commutators to non-commutator sequences in special cases.

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


Top
 Profile  
 
 Post subject: Re: Piece Adjacency & Lower Bounds for Commutator Lengths
PostPosted: Wed Jan 16, 2013 6:14 am 
Offline
User avatar

Joined: Fri May 06, 2005 10:13 am
Location: Norway
Sorry DKwan. My interest lies solely with existing physical puzzles where my (and your) definition of adjacency would apply. By definition a commutator MUST be ABA'B'. A and B can minimally have 1 turn. So minimum WILL be 4 turns.

Proving minimality in turns by commutation for some special case is something else.

For 3x3x3 cube using solely outer layer trns the shortest known edge 3-cycles done with commutation are of length 10. Allowing slice turns shortens this to a mere4 turns (example MD2M'D2).

To prove anything about minimal number of turns becomes really hard indeed.

For 3x3x3 (which is about the only known puzzle with a known efficient computer solver) one can search for solutions on special cases and see if they come up as commutators ...

Per

_________________
"Life is what happens to you while you are busy making other plans" -John Lennon, Beautiful Boy


Top
 Profile  
 
 Post subject: Re: Piece Adjacency & Lower Bounds for Commutator Lengths
PostPosted: Wed Jan 16, 2013 4:10 pm 
Offline
User avatar

Joined: Fri Feb 18, 2011 5:49 pm
Location: New Jersey
schuma wrote:
Basically you are saying, "it takes n steps to separate n adjacent pieces from a given piece." It's not a trivial argument, but I think it can be made rigorous quickly. I'd call it "Separation Lemma". This would be a standalone result of independent interest.

I think you are right to identify this as a core idea on which the rest of the commutator-length idea is based. I think the "Separation Lemma" can be sort of proved with the following train of thought:

Based on my definition of "adjacent" as meaning a single grip alteration between pieces...
If A is adjacent to B, and B is adjacent to C, then there must be a 2-grip difference between A and C (otherwise A would equal C). One of these 2 grips MUST separate A from B, while the other MUST separate B from C (in order to span the 2-grip total difference from A to C). If one of these grips could also simultaneously separate the opposite pair, then you would have two grips both capable of separating a pair of adjacent pieces which is a contradiction to my definition of adjacent. Therefore any grip which separates an adjacent piece cannot also separate any other adjacent piece, so to separate n adjacent pieces from a given piece requires using n unique grips and therefore requires n moves.


Top
 Profile  
 
 Post subject: Re: Piece Adjacency & Lower Bounds for Commutator Lengths
PostPosted: Fri Feb 08, 2013 8:44 am 
Offline
User avatar

Joined: Tue Jun 26, 2007 2:59 pm
Location: Houston, TX, USA
I always love reading this type of theory, although I admit that it's gotten advanced enough that it's a little over my head :oops: One comment though: I feel like people almost always talk of the [n,1]-length commutators only. Could commutators with a B sequence of more than one move affect this lower bound?

Probably my favorite commutator that I've found is a [4,3] length one for the wing pieces on GelatinBrain's 3.3.3 (QuadX?). I've always had the hunch that there must be some beautiful commutators out that that have longer B sequences, but I haven't solved any of the really crazy puzzles out there.

That's awesome that someone found a [7,1] three-cycle for the little chop, though! When I did that puzzle, I used a 32-move non-commutator as a three-cycle (it was ABAB form, not ABA'B')

perfredlund wrote:
For 3x3x3 cube using solely outer layer trns the shortest known edge 3-cycles done with commutation are of length 10. Allowing slice turns shortens this to a mere4 turns (example MD2M'D2).


I had never realized this, but:
1) M U2 M' U2 is obviously a commutator with slice moves
2) R L' U2 R' L F2, the equivalent non-slice sequence, is not a commutator because U2 is not the inverse of F2.

Interesting.

_________________
http://www.geocities.com/sxsk17/umcproject/umchome.html
My website, IT DOESN'T WORK ANYMORE but it used to be the only site with "official" guides for the Helicopter Cube, SuperX, Master Skewb, and many more! :D


Top
 Profile  
 
 Post subject: Re: Piece Adjacency & Lower Bounds for Commutator Lengths
PostPosted: Fri Feb 08, 2013 11:31 am 
Offline
User avatar

Joined: Fri Feb 18, 2011 5:49 pm
Location: New Jersey
AndrewG wrote:
Could commutators with a B sequence of more than one move affect this lower bound?

As already compensated for in my formula, if y is a slice move (2 moves), this can potentially save a move if it separates two adjacent pieces at the same time. I don't believe any other case of having a different length for y will result in a shorter alg length than what can be done with an [x,1] for the same piece. One reason for this is because if y is a conjugate, the full alg can be "rotated" into an equivalent alg of the form [x,1] anyway.

For example:
Starminx [4,3] for tips: [C',F,C,F', E', D',E, F,C',F',C, E',D,E]
You can "rotate" the last move E to the front of the alg changing it to this:
Starminx [6,1] for tips: [E,C',F,C,F',E', D', E,F,C',F',C,E', D]

Although there are other cases for y, I don't think any will be more efficient than conjugates (in the same way that I believe this to be true for the x part too). Perhaps someone will find a counter-example to this?

EDIT: To clarify on this point, I am NOT saying that the shortest ACTUAL commutator for a piece must be a conjugate, I am only saying that the optimal case is that the short conjugate is possible. Sometimes, when short conjugates are not possible for a specific puzzle, other forms will be shortest, but they will still not be shorter than those conjugates that didn't work (which is what my lower bound represents).

AndrewG wrote:
I had never realized this, but:
1) M U2 M' U2 is obviously a commutator with slice moves
2) R L' U2 R' L F2, the equivalent non-slice sequence, is not a commutator because U2 is not the inverse of F2.

You will find that this is the case for ANY alg that uses slice moves. When you re-hash the alg without the slice move, simulating it with 2 moves, you will end up with an alg that doesn't have a normal commutator form. This is because you are missing a "cube rotation" in the alg (you can change it back to "true" commutator form if you include cube rotations as moves). However since I wanted to encompass slice moves in my hypothesis, I simply counted the slice moves as 2 moves instead of using this as a reason for ignoring slice move algs altogether. Of course, as already mentioned, this alg isn't truly pure anyway, so it isn't a counter-example. It is still a very nice alg for fewest-moves solving though, so it demonstrates a practical limitation of my original hypothesis.


Top
 Profile  
 
 Post subject: Re: Piece Adjacency & Lower Bounds for Commutator Lengths
PostPosted: Fri Feb 08, 2013 6:02 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
I'm struggling to coherently articulate this idea but here goes.

There aren't any minimal commutators of the from [X,Y] where both the X and Y portion are themselves commutators.

That is, you may be able to find a [4,4] == [[1,1],[1,1]] or other "commutator of commutators" sequence but it will always be possible to create an equivalent (and shorter) sequence where X is a commutator and Y in a conjugate. Once this is done you can rotate the sequence until Y is 1 move.

The basic insight as to why this is comes from the definition of what a commutator is and why it works. Recall that a commutator is the resulting affect of taking two elements of a group, g, and h and performing group multiplication of the form ghg'h'. If the result is the identity element then g and h are commutative and hgh'g' will also be the identity.

For twisty puzzles, we find a sequence of moves X (group element g) and a sequence Y (group element h) that are nearly commutative but share (overlap) by one piece. Then X Y X' Y' results in a 3-cycle.

Since the goal of finding a useful commutator (one that performs a 3-cycle) is to find a set of moves X and Y that overlap by 1 pieces, we often say we're trying to "isolate" a piece since once a piece is isolated the Y portion is only a single move.

I've already shown sequence rotation (conjugate + move cancellation) allows you to move all of the conjugate setup moves from X to Y or from Y to X while still preserving the effect of the commutator.

Obviously that doesn't work if both X and Y are commutators so insight is needed to understand why they don't need to be.

Assume you have a commutator-of-commutators sequence [[A,B],[C,D]] that performs a pure 3-cycle. Then we know the effect of [A,B] and [C,D] overlap by one piece (we'll call the overlap Ov). Since the effect of [C,D] is Ov (with possibly more side-effects), we know that C has a way of moving Ov so that D can replace it. Since all that matters from the effect of [C,D] is the Ov portion that overlaps with [A,B] it is possible to turn [C,D] into an equivalent conjugate sequence [E:F] where E moves the important overlap Ov into a move F to replace it, and then bring it back with E' so that it can commute with [A,B].

I think this can be viewed as a strange form of "move cancellation" when the Y portion of both commutators is shared. Imagine [[A,B],[C,D]] where B and D are the same move Y. Then A B A' B' C D C' D' -> A Y A' Y' C Y C' Y' -> invert [C, Y] -> A Y A' Y' Y C Y' C' -> A Y A' C Y' C' -> rotation -> C' A Y A' C Y' -> [C' A, Y]

The argument is that you can always have one move do "double duty" by re-arranging one or both of the commutators until they share a Y portion. The A and C parts of the two commutators already tell you how to move the Ov portion around so making them coincide should not be hard.


Edit: since I haven't actually provided a concrete construction for how to do this conversion, I'd say this is more a conjecture that one exists in all cases.

_________________
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  [ 19 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: Pithecanthropus and 5 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