Message #1648

From: David Smith <djs314djs314@yahoo.com>
Subject: Generalized corner orientation theorem
Date: Tue, 03 May 2011 16:41:52 -0700

Hello all,

Okay, I’m going to really check what I say here before posting, it’s a bit abstracted!
But if I have to correct myself, I guess that’s okay.  I realized earlier I had said that
this theorem applies for any piece, not just corners.  It does, but it needs to be
modified in one of two ways, depending on whether the pieces are normals or wings
(see my Notation page on the wiki for a somewhat detailed explanation of these
terms), and it would be difficult to describe the difference here.  So, I’ll stick to
corners, and if anyone wants to know more, feel free to ask.  Permutations are
actually much easier to determine than orientations (so that as long as I
understand the puzzle, I pretty much have a determined procedure for evaluating
the number of reachable configurations!), but there is an additional detail in that
multiple families of pieces can interact: when they all have odd permutations, we
only divide by two once. (As in the normal 3^3 Rubik’s Cube; the permutations of
edges and corners bust both be odd or both be even.)

The following is a very generalized theorem regarding the orientations of the corners
of virtually any n-dimensional puzzle for any n.  For some rare cases, it will not
work, as the (very undemanding) conditions below need to be met for the theorem
to apply.  Only puzzles with special rules will fail.  The Gearcube/Gearcube Extreme
is one example, as it fails because one can only rotate certain faces 180 degrees,
and in fact the orientations of the corners of those puzzles never change.  The
Latch cube would meet the conditions.  Any n-dimensional physical puzzle with
no restrictions on moves will meet the conditions.  Any MagicTile or Magic
Hyperbolic Tile puzzle imaginable would satisfy the conditions.  In short, it applies
to nearly every possible puzzle, in a very practical manner!

We will first state the definitions we will be using for our highly abstracted corners,
in order to state the conditions that must apply to them.  This discussion will be
somewhat technical, despite the fact that I will not prove the theorem, and I
apologize to anyone who finds it less than appealing.

Definitions:

We will unify all of the possible corners of any puzzle into a single concept.
In order to do this, we remove the corners from the puzzle and imagine them
floating in n-dimensional space.

Definition 1: A corner will be an n-dimensional hypersphere, n >= 3, floating at
a fixed position in n-dimensional space with n stickers on its surface.

Definition 2: A sticker will be a colored 0-dimensional point.

Explanation: We are removing the corners from the puzzle, turning them into
hyperspheres, and imagining the stickers as colored points.  This is all done
without loss of generalization, as will be seen.  Any set of corners on any puzzle
can be imagined to be hyperspheres, with the stickers replaced by points.  When
we rotate the corners of a puzzle, we can imagine the hyperspheres moving in the
same way, and the points on the hyperspheres  occupying the appropriate positions.
In MagicTile, the pieces are 2-dimensional, but in fact pieces that are considered
to be corners in that program will in fact be isomorphic to 3-dimensional spheres
satisfying the following properties and conditions.  Similarly, in MagicTile, we have
stickers on the inside of the pieces.  This does not matter, it can be easily seen
that such corners are isomorphic to the 3-dimensional spheres with the points on
their surface.

Properties:

The following two properties will describe the method by which our modified corners
will function in order to mimic the corners of any Rubik-like puzzle.  These properties
are not conditions of the actual puzzle we are considering; but in Condition 1 we will
see that these properties will have to be satisfied as a whole by our puzzle, of course
as an isomorphic description.  The first will automatically hold for any puzzle, the
other can appear to not hold when it actually does (in an isomorphic fashion).

Property 1: Any two corners are a finite, nonzero distance from each
other.

Comments: Obviously!

Property 2: Each corner is the same size as the others, and has the same
number of stickers in the same positions.

Comments: This implies nothing about the sizes of the actual corners of the
puzzle; they could in fact be different sizes (such as in the mirror cube, to
which this theorem applies).  This property is a necessity for the following
conditions to make sense.

Conditions:

Condition 1: The corners of the puzzle we are applying the theorem to must be

isomorphic to the corners of Definition 1, with Properties 1 and 2 holding.

Comments: I cannot even think of a Rubik-like puzzle in which this condition does

not hold, but need to include it so that the theorem applies to any puzzle that

we are examining.

Condition 2: Every corner must have a set of stickers which are all of different colors.

Comments: In other words, no corner can have two identical stickers.  There
is no restriction on more than one corner having the same set of stickers, for
example as in the 6-color megaminx.

Condition 3: The stickers on a corner must all lie on the vertices of a regular
simplex, and this simplex cannot lie in an (n-1)-dimensional hyperplane which
bisects the corner into two equal halves.

Comments: The first portion of this condition helps ensure that the corner behaves
like the corners of a Rubik-like puzzle.  That is, when a corner changes orientation
or moves, the stickers occupy positions that were previously occupied by stickers.
The second portion prevents a technical issue in which all of the stickers would
lie on a ‘great (n-1)-dimensional hypersphere’, which could enable the corner to
rotate in ways that would be unanalogous to a Rubik-like puzzle (and the theorem
would not hold).

Condition 4: At regular intervals, the corners will go through a process called a
move: Each member of a nonempty subset of them will move to the exact position
of a corner that just left its position.  Thus, a move permutes the corners in any
possible way.  Additionally, each corner that moves must align itself so that each
of its stickers occupies a position previously occupied by a sticker.

Comments: This condition emulates a face rotation in a very nonrestrictive manner,
compared to what we usually think of as a face rotation moving corners, allowing
a huge variety of possible puzzles to satisfy the requirements of this theorem.
We are told that any permutation of the corners is allowed to occur.  The second
portion of this condition, along with the previous condition, ensures that stickers
always replace other stickers.  Note that this condition does not say that the
permutation has to be the same at each point in time, which makes sense because
in Rubik-like puzzles different face rotations produce different permutations.  One
very noteworthy fact to observe is that since the condition places no restrictions
on the nature of the permutations, we can introduce our own restrictions into
a Rubik-like puzzle, and the theorem would still hold.  For example, we could
use a regular 3^3 Rubik’s Cube, but state that the first move must swap two
adjacent corners, followed by swapping two corners along a face diagonal,
followed by swapping two corners on opposite ends of a space diagonal, and
repeat.  As long as the puzzle satisfies the next condition on moves, any
possible restriction is allowable.

Condition 5: The corners must constitute a family; that is, there exists a
permissible sequence of moves such that every corner would occupy the position
of every other corner using this sequence.  Also, every corner would be required
to eventually occupy each position in every possible permutation of its stickers
given by the rotations of the corner.

Comments: The first portion of this condition means that each corner must
eventually have the freedom to have moved everywhere.  This is naturally satisfied
by any ‘regular’ Rubik-like puzzle I can imagine.  The second portion implies
that each orientation can occur freely in any position.  This is the condition
that the Gearcube/Gearcube Extreme fails to meet, as it turns out each corner
can only occupy one of the three possible orientations in each position.

The preparatory work has been accomplished, and we can finally present the
theorem!

Generalized Corner Orientation Theorem:  If a permutation puzzle’s corners
satisfy Condition 1 by using k n-dimensional hyperspheres as corners, and
the isomorphic versions of the puzzle’s corners and moves satisfy Conditions 2
through 5, then the number of orientations the corners of the puzzle can achieve
is:

((n!/2)^k)/3  if n = 3 or 4

and

(n!/2)^k if n >= 5.

The proof relies heavily on others’ work and thus I cannot really claim it as my
own.  But neither the authors of The Rubik Tesseract nor An n-dimensional Rubik
Cube applied their results to anything other than the 3^n cube, so I made the
generalization.

It took me over 3.5 hours to write this email (I had no formulation of the theorem
in my mind before I started; I had to come up with the entire sphere/point/simplex
idea as I wrote, and there were many parts rewritten or rephrased).  Given that,
I hope that this post has been interesting to some of you!  I would appreciate
any comments or questions you have for me.  Thanks to Roice for the suggestion!

All the best,
David