[next] [prev] [up] Date: Wed, 01 Feb 95 13:02:00 WET
[next] [prev] [up] From: Martin Schoenert <Martin.Schoenert@math.rwth-aachen.de >
~~~ [prev] [up] Subject: Re: Re: Re: Re: Models for the Cube

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 Sch"onert,   Martin.Schoenert@Math.RWTH-Aachen.DE,   +49 241 804551
Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany

[next] [prev] [up] [top] [help]