From mschoene@math.rwth-aachen.de Wed Feb 1 07:05:22 1995 Return-Path: Received: from samson.math.rwth-aachen.de by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA22110; Wed, 1 Feb 95 07:05:22 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rZdll-000MP6C; Wed, 1 Feb 95 13:02 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rZdlk-00025cC; Wed, 1 Feb 95 13:02 WET Message-Id: Date: Wed, 1 Feb 95 13:02 WET From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu In-Reply-To: "Martin Schoenert"'s message of Tue, 24 Jan 95 23:12 WET 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) | in F, in S }. The Real Puzzle --------------- Assume that we call two elements and in G to be *really equal* if there are essentially free elements and in F, such that = . Then the sets of really equal elements are the double cosets (F 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 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 F) = ( 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 F) is |F|, i.e., (F F) is a single coset, if and only if normalizes F, i.e., ( F) = (F ). 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 corresponds to a recoloring of the cube and the postmultiplication with 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 such that the double coset (M 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 ( 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