From mschoene@math.rwth-aachen.de Tue Jan 24 18:01:35 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 AA13203; Tue, 24 Jan 95 18:01:35 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rWuBw-000MPHC; Tue, 24 Jan 95 23:58 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rWuBw-00025hC; Tue, 24 Jan 95 23:58 WET Message-Id: Date: Tue, 24 Jan 95 23:58 WET From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu In-Reply-To: "Jerry Bryan"'s message of Wed, 18 Jan 1995 11:53:21 EST <9501181654.AA27651@life.ai.mit.edu> Subject: Re: Re: Re: Models for the Cube Jerry Bryan wrote in his message of 1995/01/18 It is well known that G[E] must have an equal number of even and odd permutations. If we generate G[E] as , it is also the case that there are just as many positions an even distance from Start as an odd distance from Start because the parity of the distance from Start is the same as the parity of the permutation if we restrict ourselves to quarter turns. If you view the elements of G[E] as permutations on 24 facelets, then all elements are even. But if you forget for the moment the orientations of the edges, and view each element as only permuting the 12 edges, then there is an equal number of even and odd elements in G[E]. And then, since each quarter face turn cyclically permutes four edges, there must indeed be just as many states an even distance from Start as there are states an odd distance from Start. Jerry continued But in the computer search for God's Algorithm for edges only cubes, there were not equal numbers of positions an even distance from Start as an odd distance from Start. The computer search used the coset model G[E]/C[E], where this notation means the set of cosets of C, *not* the factor group. In and of itself, the mismatch between the number of positions at an even distance from Start and at an odd distance from Start should not pose a problem. It is not clear to me what it means to speak of the "parity" of a coset of C, and half of each coset will be even and the other half will be odd. Hence, it is not clear that a particular coset must *a priori* be an odd or even distance from Start. Allow me to translate this into the language I introduced in my other message. G[E] is the model for the basic puzzle. C[E] is the subgroup of essentially free elements. We consider two elements of G[E] to be essentially equal if they lie in the same left coset of C[E] in G[E]. The cost of an element of G[E] (or the distance from the Start), is the length of a shortest process effecting , where we only count the quarter face turns, not the rotations of the rigid cube. It is clear that two essentially equal elements have equal costs. Jerry continued But if we map each coset to an element of G[E], it is meaningful to speak of the parity of the element of G[E]. And if the elements of G[E] to which we map the cosets form a subgroup, then there must be an equal number of odd and even elements in the subgroup (unless they are all even?!). If the mapping respects costs in the sense of maintaining the same distance from Start, then I don't understand how we can avoid a conflict between the equal number of even and odd permutations in the subgroup of G[E] and the unequal number of even and odd distances from Start in the coset model G[E]/C[E]. Pick one edge, say the right upper edge. Then each coset of C[E] contains one representative that fixes this edge. The set of those representative is a subgroup U, generated by L[E],D[E],F[E],B[E]. Formally U is a supplement for C[E] in G[E]. It is a model for the essential edges only cube. And indeed it contains the same number of even and odd permutations. So far so good. But we must now be carefull how we measure the cost of elements in U. If we measure by taking the length of a shortest process effecting such an element in U using only the generators L[E],D[E],F[E],B[E] (and their inverses), then some elements will appear more expensive than they really are. For example r[E]'*R[E] should have cost 1, but there is no process of length 1 effecting this element using only the generators above. So we must take a larger generating system. As I described in my other message, the generating system to take is the set of all elements in U that should have cost 1. This gives us the generating system { L[E], D[E], F[E], B[E], r[E]'*R[E], u[E]'*U[E], L[E]', ... }. Still, so far so good. So where is the problem? Well the new generators r[E]'*R[E] and u[E]'*U[E] are *even* permutations. And since not all generators are odd permutations any more, the argument that the number of elements with even cost and the number of elements with odd cost must be equal, simply doesn't work anymore. 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