Home »

Irreducible Loops

Submitted by Peter on Wed, 04/18/2007 - 09:20.
Some ideas for how to possibly proove that the diameter of the Cube-Group would be X.

Hi, I am new to the Cube problem, so probably the ideas are not new, or too naive, but I could not find them anywhere. This is possibly due to my lack of knowledge of terminology. (My background is theoretical solid states physics.)

Thus I would like to share these ideas with you, which you hopefully find useful, or can tell me that these ideas are not new or possibly that they are useless. I kindly ask you to comment. I just go ahead...

How could one calculate the diameter of the Group?

Let A be a random permutation. I start by choosing a (not optimal) path from id to A, say in quarter turn metric, with A=prod_i(ai) (i=1,...,N) where ai in {U,U',D,...}.

Could one possibly proove, that the path can _always_ be 'simplified' to a lenght smaller or equal to X (which then would be the diameter)?

How could such a simplification look like? The only way I see is through the usage of irreducible loops.

So, what do I mean by an irreducible loop. I define it to be a sequence of operations xi, i=1,...,n such that prod_i(xi)=id and the path is in a certain sense topologically nontrivial. Here xi= U, U', D, etc.. For example, D*D*D*D=id is such an irreducible loop. The simplification of the path A wrt to this loop is already implicit in the notation that is commonly used. E.g. D*D*D is replaced by D'. But there exist loops which are longer...

Now, given a loop of length n (which at least in quarter turn metric is even):
IF the path A and the loop contain a common sequence of length n/2+1, THEN this sequence in A can be replaced by a sequence of length n/2-1, which is the 'other half' of the loop. As a result one has reduced the length of the path for A to N-2.

If one would have knowledge of ALL irreducible loops in the Cube Group, then one possibly could proove that ANY path can be reduced to a length X.

Thus we should ask, how could one possibly generate all irreducible loops.

I admit, I don't know. But I know how to systematically generate a large number of them. The key is to consider optimal paths to symmetric permutations (i.e. states of the cube). Namely, the optimal path to a symmetric state is always degenerate, i.e. there is always at least a second path to this state. By going one path to the symmetric state and the other back, one automatically has a loop. As an example, the state generated by D*D is also generated by D'*D', thus D*D=D'*D', or equivalently D*D*D*D=id. As an other example, we could go the path down to the supertwist and choose another one back. Whether such a loop is really irreducible can then be checked straightforwardly.

Finally, several questions turn up.

First, and most important, do the optimal paths to the symmetric states give all irreducible paths? Or, stated differently, can there be an irreducible loop that does NOT run over a symmetric state? My feeling is, that there should be a simple proof to this one, using symmetry arguments. What do the mathematicians say?

Second, if indeed we can obtain all irreducible loops through this procedure, would they allow to make the second part of the proof, namely that all paths can be simplified to a length smaller or equal to X?

In light of the analysis performed by Herbert Kociemba, Silviu Radu and others such an undertaking sounds worthwile.

So please tell me, what you think about it. If you think, this is worth consideration, I would be ready to invest efforts in further analysis.

Peter Jung
» login or register to post comments | previous forum topic | next forum topic

Comment viewing options

Select your preferred way to display the comments and click 'Save settings' to activate your changes.

Hi,

Submitted by jaap on Mon, 04/23/2007 - 16:08.
Hi,

I've written a little bit about this kind of thing on my website too, on a page about Cayley graphs:
http://www.geocities.com/jaapsch/puzzles/cayley.htm

Such a loop in the graph represents an identity (a move sequence with no effect), and I called them irreducible identities.

The Rubik's Cube is not the best kind of puzzle for this technique because there are very long irreducible identities. Ideally you'd want a puzzle which has many short identities, preferrably because many of the moves commute. I proposed the Cmetrick and the Gripple puzzles as good candidates, but never got around to trying that out. The Cmetrick has since been calculated through using more traditional methods.

Jaap

Jaap's Puzzle Page: http://www.geocities.com/jaapsch/puzzles/
» login or register to post comments

The Dangling String Analogy

Submitted by Jerry Bryan on Thu, 04/26/2007 - 12:53.
I've been very fond of Jaap's Web site for a long time, and I'm especially fond of his Cayley Graph page mentioned above (the one at http://www.geocities.com/jaapsch/puzzles/cayley.htm). I particularly like his Dangling String analogy.

Let me quote one sentence from the Dangling String analogy: "Cayley graphs are uniform, so this dangling string net will look exactly the same regardless of which node you picked it up at."

The quote from Jaap's Web site is exactly correct, or course. However, I'm embarrassed to say that when I first started working on Rubik's Cube I knew so little group theory that I would have sworn that a graph of Cube space was not uniform. In fact, there are several posts that I made to Cube-Lovers that reflect this incorrect point of view, and I dearly wish I could retract those posts.

In my defense, there was a somewhat reasonable basis for my mistake, especially since I knew so little group theory. None of my cube programs have ever searched a complete Cube space. Rather, my programs have always searched a space that is Cube space reduced by symmetry. It never occurred to me to search a complete Cube space because a complete Cube space is so much larger than the equivalent Cube space reduced by symmetry.

Cube space reduced by symmetry is not a group and is not uniform. For example, when Cube space is reduced by symmetry, the Start position in the quarter turn metric has only 1 neighbor rather than 12, and the Start position in the face turn metric has only 2 neighbors rather than 18. Hence, a Dangling String model of Cube Space reduced by symmetry will look very different depending on which node you pick it up at. But in my early naive posts to Cube-Lovers I didn't realize that such a reduced search space was not a group.
» login or register to post comments

Thanks for those complimentar

Submitted by jaap on Fri, 04/27/2007 - 02:50.
Thanks for those complimentary words, Jerry.

> Cube space reduced by symmetry is not a group and is not uniform.

That's correct.
It is a coset space (or quotient space) that the group acts on by ordinary group multiplication.

Last Monday I presented a guest lecture for first year mathematics students. They had learnt the beginnings of group theory (cosets, actions, but not yet normal subgroups), and I was asked to give a talk that showed them what it all means.

If you don't mind, I'll write some of it out below. It is something I want to add to my site some time, and I'll use this opportunity to put some of it into words.

One of the things I presented was the Rubik's Cube. There is an obvious action here - the group of permutations acts on the set of positions. Given any permutation you can apply it to a position to get another position.

This action is free, meaning that if the permutation actually moves something then the position will change. This leads to the conclusion that the number of permutations in the group is exactly the same as the number of positions you can reach.

Then do the same with a cube that has only three colours, each layer a different colour. Now permutations sometimes seem to do nothing, for example turning one of the monochrome layers when in the solved position. It moves pieces, but you can't see it.

Suppose you apply a permutation g to the starting position. You would get the same result if you did a permutation h that kept the starting position looking the same before applying g. So g and hg have the same effect on the starting position, where h is an element of the stabiliser of the starting position.

Let H be the stabiliser of the starting position. All elements of Hg all look the same as g when applied to the starting position. In fact, you can actually say that each coset Hg represents a position, with H itself representing the starting position.

The coset space H\G = {Hg | g in G} represents all the positions the puzzle can have. G acts on this set by right-multiplication.


Reducing the cube space through symmetry is actually no different. Here you use H as the group of cube rotations and reflections. These are permutations of the 54 cube stickers that leave the position looking the same (just in a different orientation in space). When you reduce the cube space by symmetry, you are actually looking at the coset space of H\G, treating each coset as a single position.

As you've noticed, the 'Cayley graph' of a coset space is usually not uniform, as it does not form a group. When it does form a group, then H\G is called a quotient group and H is called a normal subgroup of G.

I wonder whether it is possible for a coset space to not be a group, but to still have a uniform graph.



Jaap
Jaap's Puzzle Page: http://www.geocities.com/jaapsch/puzzles/
» login or register to post comments

Cube Space Reduced by Symmetry

Submitted by Jerry Bryan on Fri, 04/27/2007 - 12:16.
I think some clarification is needed. We may not be meaning the same thing as each other when we say "cube space reduced by symmetry".

The way I do it, the full cube space is partitioned into equivalence classes by symmetry, and the equivalence classes are not cosets. The smallest example I can think of to illustrate would be something like the group <F>={I,F,F2,F-1}.

Reducing this group by symmetry only reduces it from 4 elements in the group to 3 equivalence classes, namely {I}, {F,F-1}, and {F2}. These 3 equivalence classes are not all the same size, and they definitely are not cosets.

Is there another interpretation of "cube space reduced by symmetry" that can be modeled with cosets?
» login or register to post comments

Oh, and as a part of the "cla

Submitted by Jerry Bryan on Fri, 04/27/2007 - 13:08.
Oh, and as a part of the "clarification", I should mention that I do understand your example of the three colored cube, and your example definitely is cosets. It's just that reducing the number of colors is not what I normally think of when I think of "reducing the search space by symmetry". It is reducing the search space, but it feels like it's reducing it by something other than symmetry, I just don't know what to call it.

Let me come at this from a slightly different direction. Consider what I have been calling partial permutations and what Cube Explorer calls incomplete cubes. In terms of modeling this concept on an actual physical cube, I think of it as graying out certain of the cubies. And graying out of certain of the cubies may certainly be thought of in terms of cosets.

To match your three color model, suppose we take a cube in the Start position, gray out the top layer, and scramble the cube. Any resultant position may certainly be thought of as a coset. Suppose we then return to the Start position, gray out the top layer, and gray out the middle layer with another shade of gray. We get cosets again, and I'm just using shades of gray the same way you are using your three colors.

Now, let's return to the Start position and gray out seven of the corner cubies and all twelve edge cubies (all with the same shade of gray). If you scramble this incomplete cube, there are 24 different positions in which the corner cubie that is not grayed out can be placed. And those 24 different positions correspond to 24 cosets. The subgroup of which they are cosets is the subgroup that fixes the corner cubie that is not grayed out.

I would then go further and reduce those 24 positions by symmetry. For example, suppose the corner cubie that were not grayed out were the flu cubie and suppose the flu cubie were in its Start position in the flu cubicle. I would regard the position of the flu cubie after the six following moves (applied to Start in each case) to be an equivalence class under symmetry: F, F', L, L', U, U'.
» login or register to post comments

I got confused again. You're

Submitted by jaap on Tue, 05/01/2007 - 03:17.
I got confused again.
You're right, and things are not so simple as I made them out to be. The problem is that rotations and reflections of the cube are not only permutations of the stickers, they also redefine what the moves are. In other words, the recolouring of the centres messes things up.

In the 3-colour cube case we had a coset H representing the solved cube, and if we apply moves g1 and then g2 to it we get H.g1.g2, a different coset. The group G acts on the cosets in this way by right-multiplication.

In the cube reduced by symmetry case we have something different. Let H be the set of rotations/reflections of the cube as a permutation of the 54 facelets. After applying g1 to the solved position we get g1.H as the set of all legal sticker permutations that represent the same position. When we apply another move g2 we get g1.g2.H, and this is not an action in the same way as before.

Let's take a particular element of the set g1.g2.H, say g1.g2.h, i.e. two moves followed by a cube rotation. We can rewrite this as h.(h'.g1.h).(h'.g2.h), where h' is the inverse of h. Since the initial h has little effect on the solved position (except to swap colours), this is just as if two moves were performed, but not g1 and g2 themselves but g1 and g2 changed under the rotation/reflection h.

This cube symmetry stuff keeps tripping me up.

Jaap
Jaap's Puzzle Page: http://www.geocities.com/jaapsch/puzzles/
» login or register to post comments

Relations

Submitted by Jerry Bryan on Wed, 04/18/2007 - 21:31.
I believe that the concept you are calling irreducible loops is called relations in Cube-Lovers. For example, check out

http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Dan_Hoey__No_short_relations_and_a_new_local_maximum.html

http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Dan_Hoey__Generating_Rubik's_Cube.html

http://www.math.rwth-aachen.de/~Martin.Schoenert/Cube-Lovers/Dan_Hoey__Presenting_Rubik's_Cube.html


This notion is very much tied to "duplicate positions" that arise in a breadth first search of cube space. It's not really the positions that are duplicate; it's the multiple maneuvers that create the same position that create the "duplication". In any case, if you think in terms of traversing a Cayley graph for a particular set of generators for a group, you do have to be very careful to visit each node of the graph only once (or if you visit each node more than once, to count only one visit).

As a trivial example of duplicate positions, RL=LR. It's obviously the case that from RL we can get back to Start simply by saying (RL)(L'R'). It's almost as obvious or trivial that from RL we can get back to Start by (RL)(R'L') because moves of opposite faces commute. But (RL)(L'R') simply lists the inverses of the generators in reverse order to get back to Start, and (RL)(R'L') does do something slightly different. Namely, (RL)(R'L') takes advantage of the fact that RL=LR and combines RL with the inverse of LR.

I think the case of DDDD=DD(D'D') that you cite is a little more interesting. From DD, you can go forward to Start via (DD)(DD), or you can go back to Start via (DD)(D'D'). The back to Start case is not very interesting, but the forward to Start case is interesting, even for a such a trivial example as DDDD. It's the "forward to Start" cases that correspond to duplicate positions. In this case, the duplicate positions are DD and D'D'. So you combine DD with the inverse of D'D', and you get (DD)(DD) to go forward to Start from DD.

The way I think of it is that any time you find duplicate maneuvers for the same position you can create a relation. And from half way through a relation, you can find duplicate maneuvers for the same position (provided of course that your relation doesn't simply list the inverses of the generators in the opposite order like RLL'R').

To the best of my knowledge, nobody really knows how many unique relations there are, nor even precisely how to define "unique". For example, are relations unique if they differ only by commuting moves from opposite faces? Are relations unique if they are reducible in trivial way (and what is a "trivial way"). Are relations unique if they contain segments that can be replaced by symmetrical segments? Are relations unique if they contain segments that can be commuted?

I have thought about at least trying to come up with a definition for "unique" in this context, but I've never come up with anything I'm happy with. So I content myself with brute force detection of duplicate positions as exemplified by positions whose Starts-With and/or Ends-With values include more than one generator. And as I have posted previously, the ability to calculate Starts-With and Ends-With is just an artifact of the way I do a breadth first search of Cube space.

Finally, it has always seemed to me that the problem of finding relations really just recasts the problem of finding God's Algorithm in new language. It feels like it's still the exact same problem, still just as difficult. I could be wrong, but that's the way it seems. That's because to me the fundamental God's Algorithm problem is duplicate positions. Were it not for duplicate positions, God's Algorithm would be easy. And I think that duplicate positions and relations are just two sides of the same coin.
» login or register to post comments