From mschoene@math.rwth-aachen.de Wed Dec 7 19:55:00 1994 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 AA18723; Wed, 7 Dec 94 19:55:00 EST Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0rFSM4-000MPbC; Wed, 7 Dec 94 20:48 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0rFSM3-0000PsC; Wed, 7 Dec 94 20:48 PST Message-Id: Date: Wed, 7 Dec 94 20:48 PST From: "Martin Schoenert" To: cube-lovers@life.ai.mit.edu Subject: Distance Respecting Automorphisms Dan Hoey writes in his e-mail message of 1994/11/08 ... [conjugation by] M fixes the set of the generators of G and their inverses. M is fact the largest subgroup of the outer autmorphism group with this property, which makes it rather important. In a 1983 Cubic Circular article (of which I know only Stan Isaacs's summary) David Singmaster observed that the group is larger for larger cubes, provided we work what I call the ``theoretical invisible group''. That is, we solve not only the surface of the cube, but the hypothetical interior (n-2)^3 cube, and all the smaller (n-2k)^3 cubes as well. I blithered at length about this in my article of 1 June 1983 archived (I think I've got it right this time) at . Try http://www.math.rwth-aachen.de:8000/~mschoene/Cube-Lovers/ Dan_Hoey__Eccentric_Slabism,_Qubic,_and_S&LM.html instead (must be on a single line). Dan continues The idea is that a mapping called evisceration allows us to permute the layers of the cube. On the 4x4x4 cube, this for instance allows us to exchange each inner slab with its adjacent outer slab. It also allows us to conjugate each inner slab move by central inversion, while leaving the outer slab moves alone. In general, evisceration of a d-dimensional cube by f maps each feature (cubie, colortab, or face-center arrow) at coordinates (x[1],x[2],...,x[d]) to (f(x[1]),f(x[2]),...,f(x[d])), where f is a permutation of the intervals between the cleavage coordinates of the cube. I believe that if f commutes with the central inversion, then conjugation by evisceration is an outer automorphism of the Rubik's cube group. (I think I have proved this for d=3, and I think the proof in higher dimensions should not be difficult given the right notation.) The group of all eviscerations includes the central inversion; we can of course augment it by the rotation group in d-space. Is this the maximum outer automorphism group that respects generators of the Rubik's cube? For this we take the generators to be turns of slabs between adjacent cleavage planes. (Turns are direct d-1-dimensional isometries.) Allow me to reformulate your description again slightly. Let P be a d-dimensional n*n*...*n cube. Let m be (n-1)/2 if n is odd and n/2 if n is even. The position of each cubie is described by its position vector (p_1,p_2,...,p_d). If n is odd, then each p_i comes from [-m..m]. If n is even, then each p_i comes from [-m..-1,1..m] (no middle slice in this case). The orientation of a cubie is described by its orientation vector (o_1,o_2,...,o_d), where each o_i comes from the set [-1,1]. I consider the puzzle solved, if each cubie is in its original position and in its original orientation (this is stronger than we usually require for the 3x3x3 Rubik's cube, where we ignore the orientation of the centre cubies, but remember, we *see* the usually invisible faces). If F is a bijection on [-m..m] (n odd) or [-m..-1,1..m] (n even), then F induces a permutation of the cubies (ignoring orientation) via F( (p_1,p_2,...,p_d) ) = (F(p_1),F(p_2),...,F(p_d)). Let I_k be defined by I_k(k) = -k, I_k(-k) = k, and I_k(l) = l for l <> k. The permutation of the cubies induced by I_k is the inversion of the k-th slab of the cube. If A is a permutation on [1..m], we write l^A for the image of l under A, and we define (-l)^A := -(l^A) (you enforce the condition (-l)^A = -(l^A) by requiring that the permutation commutes with the central inversion). The permutation induced by A permutes the slabs of the cube. The group of all eviscerations is generated by all the I_k and all permutations A of [1..m]. Each evisceration first inverts certain slabs, and then permutes the slabs. Put differently, the group of all eviscerations is the wreath product of {-1,1} and S_m. Repeating the definition of the wreath product, this means that the group of all eviscerations is the semidirect product of the normal subgroup generated by the I_k and the symmetric group generated by the A. This group, together with the group C of symmetries of the d-dimensional cube P, is a subgroup of the automorphism group of P, which fixes the set of generators (with any reasonable definition of what the generators of P are), and thus respects the distance of elements in the Cayley graph. Is this the largest such group? In the case that d = 3, this is true. In the case of larger d, I am quite certain it is true if the generators are rotations of 2 dimensional subsets of P. If we choose the generators to be symmetries of d-1 dimensional subsets of P, then I still believe it is true. But I have been fooled often enough in such situations, to not trust my intuition without a proof. If we can agree on a precise definition of what the generators of the d dimensional cube are, I would be happy to compute the largest subgroup of the automorphism group that respects the distance of elements in the Cayley graph. 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