From:

~~~ Subject:

In my previous message I introduced the basic puzzle and the essential

puzzle and their models. There is one more thing I would like to say

about models for the cube.

The situation is the same as in my previous message.

Assume we have a puzzle modelled by a group G of basic elements with

a generating system S of simple elements and their inverses.

Assume that we have a subgroup F of essentially free elements, and that

we call two elements essentially equal if the lie in the same left coset

of F in G.

Given a system of representatives for the cosets of F in G, we define

the product of two cosets as the coset containing the product of the

representatives of the two cosets. If this multiplication turns G/F

into a group, we call this group a model for the essential puzzle.

Note that such a model need not exist, i.e., it may happen that no system

of representatives gives a group. Also such a model need not be unique,

i.e., different systems of representatives may give nonisomorphic models.

The cost of an element in G is the length of a shortest process effecting

this element, where we count only the simple elements from S, not the

essentially free elements from F.

Then the cost of an element in G is equal to the cost of its left coset

in G/F wrt. the generating system { (<f> <s> F) | <f> in F, <s> in S }.

The Real Puzzle ---------------

Assume that we call two elements <g_1> and <g_2> in G to be *really

equal* if there are essentially free elements <f_1> and <f_2> in F, such

that <f_1> <g_1> <f_2> = <g_2>. Then the sets of really equal elements

are the double cosets (F <g> F). Obviously two really equal elements

have the same costs. The set of all double cosets is usually written

F\G/F. Let us call the size of F\G/F the *real size* of the puzzle.

Note that each double coset (F <g> F) is a disjoint union of single

cosets of F. On the other hand let H be the largest subgroup of F such

that (H <g> F) = (<g> F). Then the number of single cosets in the double

cosets is the index of H in F. So we see that the size of each double

coset is a multiple of |F| and a divisor of |F|^2.

Furthermore note that the size of the double coset (F <g> F) is |F|, i.e., (F <g> F) is a single coset, if and only if <g> normalizes F, i.e., (<g> F) = (F <g>).

Now in general F\G/F is notoriously badly behaved. For example the size

of F\G/F is in general not a divisor of the size of G. So there is no

hope that we can turn F\G/F into a group that has anything to do with G.

That means that we cannot model the real puzzle with a group.

But that shouldn't stop us from investigating this real puzzle. One

question we can ask is, what is the real size of the puzzle? Another

question might be, what are the elements that lie in small double cosets.

For an example, let us again take Rubik's cube. Here we have a very nice

description of when two states are really equal. This is because the

premultiplication with <f_1> corresponds to a recoloring of the cube and

the postmultiplication with <f_2> corresponds to a rotation of the cube.

So two states are really equal if we can recolor and rotate one state to

get the other state. This idea has come up several times in this list,

for example in Jerry Bryan's message about 1152 fold symmetry

(see Jerry_Bryan__1152-fold_Symmetry_and_24-fold_Symmetry of 1993/12/08).

Note that we must be a little bit more careful with the real cube than

with the essential cube. With the essential cube it doesn't matter

whether the subgroup of essentially free elements is the subgroup C of

rotations of the rigid cube or the subgroup M of rotations and

reflections of the rigid cube. That is the group G generated by the face

turns is a model for the essential cube in both cases, i.e., G is a

supplement of C in CG and is also a supplement of M in MG. But for the

essential cube it does matter which subgroup we take.

Dan Hoey computed the real size of M\MG/M as 901083404981813616 (see Dan_Hoey__The_real_size_of_cube_space of 1994/11/04). He used the fact that, since the supplement G is a normal subgroup of MG, the number of double cosets in M\MG/M is equal to the number of conjugacy classes in G under the operation of M. With the same idea we can compute the real size of C\CG/C as 1802166805653080256, which is slightly less than 2*901083404981813616.

Dan Hoey and Jim Saxe searched for elements <g> such that the double

coset (M <g> M) has size 48, 96, or 192

(see Dan_Hoey__Symmetry_and_Local_Maxima_(long_message) of 1980/12/14).

More precisely, they classified the elements for which the subgroup H

that fixes the single coset (<g> M) operates transitively on the set

of quarter face turns, because those elements must be local maxima

(except for the identity). They found 4 double cosets of size 48,

10 double cosets of size 96, and 12 double cosets of size 196,

or 72 local maxima.

Have a nice day.

Martin.

-- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany