# 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