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