Message #569

From: "thibaut.kirchner" <thibaut.kirchner@yahoo.fr>
Subject: Re: On Higher-Dimensional Parity
Date: Wed, 17 Sep 2008 13:47:48 -0000

— In 4D_Cubing@yahoogroups.com, "noel.chalmers" <ltd.dv8r@…> wrote:
> The possible parities are as follows:
> In 3D:
> Single edge flipped
> Two edges switched
> In 4D:
> Single 2-colour cubie flipped
> Two 2-colour cubies switched
> Single 3-colour cubie flipped
> Two 3-colour cubies switched

In fact, in 3D, we can also switch two corners, but this is the same
as switching to edges, since a quarter-turn of a face transfers one
parity error on the other.
In 4D, switch two 2-colour cubies is the same parity error as
switching two 3-colour cubies, as a quarter-turn of a cell transfers
one parity error on the other.

> In 3D, there exist complex sequences that will correct parities and
> leave the rest of the cube unscrambled. I was not lucky enough to
> think up a sequence in 4D or 5D that would do the same but I’m
> confident it could be done and it would relieve much of the
> frustrations of solving the 4x4 puzzles if they were discovered.
We can recycle the sequences for the 3D parity errors to solve some of
the 4D parity errors:

• flip only one edge on 4^3 –> twist only one face on 4^4
  
• switch only two edges (or two corners, this is equivalent) on 4^3
  –> switch only two faces (or two edges, this is equivalent) on 4^4.
  But there remains the case where we have to flip only one edge of a
  4^4 which has no equivalent in 4^3… I thought it was impossible but
  didn’t try to prove it.
  

> hear people’s thoughts as to the exact causes of parity (and ways to
> avoid it) ;)

Here are my thoughts about 3D parity errors, their causes, the
properties of sequences to solve them, and the ways to avoid them.
I’ll try to see what remains true for 4D parity errors, and what changes.

There are three kinds of parity errors:

• one due to indistinguishable pieces in a puzzle where only even
  permutations are authorized (classical example : the 6-color Megaminx
  compared to the 12-color Megaminx), or hidden orientation of some
  pieces where there is a link between all the orientations (classical
  example : Rubik’s barrel compared to the 3^3 Rubik’s cube)
  
• those in a puzzle where the parity of the permutation of pieces / of
  stickers can vary (examples : every cube, compared to the Megaminx).
  
• and another one which I have not yet studied, which seems to be
  proper to reduction methods on even-sized big cubes.

First, let’s study the first kind of parity errors.
How to solve it?
Do a permutation which involves a pair of indistinguishable pieces and
at least another piece of the same type. Often it will be a 3-cycle
between the two pieces we’d like to switch and a piece which is
indistinguishable from one of the first two pieces.
How to avoid it?
Keep as long as possible an unsolved zone containing two
indistinguishable pieces (resp. a piece with hidden orientation), and
solve this zone only when the number of remaining pieces is small
enough to check the parity of their permutation. In a 6-color
megaminx, the indistinguishable pieces are opposite, therefore my idea
doesn’t apply. In a Rubik’s barrel, it leads to some interesting methods:

• in corner first methods, there is no parity problem
  
• in layer-by-layer methods, don’t use an octogonal face as last layer
  to avoid parity problems.

Now, the second kind of parity errors:
In these puzzles, the parity of permutation of pieces / of stickers
depends on the parity of rotations of each kind.
Examples:
In a 2^3, there are only one kind of basic rotations: the quarter-turn
twists of the faces. Each one inverts the parity of the permutation of
the corners (one 4-cycle) and the parity of the permutation of the
stickers (three 4-cycles).
Then we have a parity error when we’ve done an odd number of
quarter-turn twists. In this case, the solution is really easy: just
do a quarter-turn somewhere where there is something not solved.
In a 3^3, there are two kinds of basic rotations; the quarter-turn
twists of the faces, and the global quarter-turn rotations of the
cube. Let’s study their parity effects:

• A quarter turn twist of a face acts evenly on the faces (identity),
  oddly on the edges (one 4-cycle), oddly on the corners (one 4-cycle),
  evenly on the stickers from edges (two 4-cycles), and oddly on the
  stickers from the corners (three 4-cycles).
  
• A global quarter turn of the cube acts evenly on the corners (two
  4-cycles), oddly on the edges (three 4-cycles), oddly on the faces
  (one 4-cycle), evenly on the stickers from the corners (six 4-cycles),
  and evenly on the stickers from the edges (six 4-cycles).

Now, let’s denote p the parity morphism, F the permutation of faces, E
the permutations of edges, C the permutation of corners, ES the
permutation of the stickers from edges, CS the permutation of the
stickers from corners, T the number of quarter-turn twists of the
faces and R the number of global quarter-turn rotations.
The equations we get are
p (F) = p (R)
p (E) = p (R) + p (T)
p (C) = p (T)
p (CS) = p (T)
p (ES) = 0.
Since the global rotations cost nothing, we can reduce the equations to:
p (F) = p (ES) = 0
p (E) = p (C) = p (CS) = p (T).
Conclusion: there is exactly one parity case, as for the 2^3.
In layer-by-layer methods, we fix it while solving the last layer by a
single twist of the last layer. In corners first methods we fix it in
the first step: when we solve the corners, also by a single twist.

So, in the small cubes parity errors occur but they’re not real
problems as we can solve it with a single move.
Now, let’s study the case of the 7^3 cube, then the odd-sized
super-cubes (because there is also intervention of indistinguishable
pieces) and the even-sized cubes (and super-cubes; here,
indistinguishability changes almost nothing).
As we saw in the small cubes cases, the permutation of the stickers of
the pieces is not interesting, as it is always even for the edges and
has same parity as the permutation of corners for stickers of the corners.
So, notations:
K = permutation of corners
W1 = permutation of external wings
W2 = permutation of internal wings
E = permutation of center of edges
CC1 = permutation of external corners of centers
CC2 = permutation of internal corners of centers
EC1 = permutation of external edges of centers
EC2 = permutation of internal edges of centers
OC = permutation of oblic centers

FT = number of quarter-turn face twists
LT1 = number of quarter-turn external layer twists.
LT2 = number of quarter-turn internal layer twists.
(For convenience, we assume that the centers are fixed ; we don’t lose
any generality).
After a study of how the three kinds of elementary action permute each
kind of pieces, we get the following parity equations:
p (K) = p (E) = p (FT)
p (W1) = p (EC1) = p (LT1)
p (W2) = p (EC2) = p (LT2)
p (OC) = p (LT1) - p (LT2).
Then we have three parity errors, each associated to its type of twist.
The face twist parity error is no more a problem in the 7^3 than in
the smaller cubes.
In the cage methods (where we start with two opposite faces and then
equatorial edges and then the last four centers), the parity errors
are easy to fix: they appear when we solve the edges, and we can
correct them by twisting the corresponding equatorial layer of a
single quarter-turn.
In the reduction methods, they indeed are a problem, because once
we’ve solved the centers, the indistinguishability of the EC and of
the OC prevent us from seeing the parity error, where as it is already
fixed: when we solve the edges, we do an even number of layer twists.
So we can see the parity error when all but two edges are solved and
then, a single quarter-turn of a layer destroys everything. That’s why
we have to use more sophisticated sequences.
Their common point is that:

• they have an odd number of quarter-turn twists of the layers where
  there are the parity errors
  
• they have an even nulber of quarter-turn twists of the layers where
  there are no parity errors
  
• where things were solved, it is still solved (centers were solved,
  they’re still solved but differently, most of edges were solved,
  they’re still solved).
  The point is that the more there are things solved that we want to be
  preserved, the more sophisticated is the sequence we need. So, to
  avoid them, use cages-methods.

Now, special case of odd-sized super-cubes (with reduction methods):
Here we can see the parity errors as we solve the last center. So we
can use a shorter and simpler formula to solve it, because we don’t
need edges to be preserved.
Now, the case of even-size cubes (still with reduction methods): Here,
even when we solve the edges, we still can’t see the parity errors,
because of the lack of centers of edges. An odd permutation of the
wings results in a bad oriented edge in the 3^3 cube, and a double
2-cycle permutation of the wings results in the permutation parity
error. We can see these parity errors only once we have nearly solved
all the cube. The permutation parity error is the only example I know
of the third type of parity problems, and I as said at the beginning,
I have not studied it enough to really understand what causes it and
how to avoid it (a part from avoid the reduction method on the
even-sized big cubes).
To finish with the 3D cubes, in the case of the even-sized supercubes,
we can adjust parity when we solve the oblic centers of the last
center such that all the layers have the same parity, but we cannot
tell if they are the rightor not. For this, we have to solve the edges
and then nearly all the 3^3 cube resulting from the reduction.

Now, let’s see the 4D cubes case (4^4 to begin with).
We can decompose each superficial rotation as a succession of
quarter-turns of a cell around a pair of opposite faces, so these are
the basic rotations, and the same holds for the inner-layer rotations.
Notations:
1SP : permutation of 1-sticker pieces (cells)
2SP : permutation of 2-stickers pieces (faces)
3SP : permutation of 3-stickers pieces (edges)
4SP : permutation of 4-stickers pieces (corners)
(The permutation of the stickers themselves is only interesting to
study the 2^4 and the 3^4 puzzles, so I don’t list them).

FT : number of quarter-turns of cells
LT : number of quarter-turns twists involving inner layers.

A quarter-turn of a cell acts: evenly (identity) on the cells, evenly
(six 4-cycles) on the faces, evenly (six 4-cycles) on the edges, and
evenly (two 4-cycles) on the corners.
An inner quarter-turn acts: evenly (six 4-cycles) on the cells, evenly
(six 4-cycles) on the faces, evenly (two 4-cycles) on the edges, and
evenly (identity) on the corners.
The parity equations are therefore very easy to write:
p (1SP) = p (2SP) = p (3SP) = p (4SP) = 0 (note the difference with
the odd-sized four-dimensionnal hypercubes and with the three
dimensionnal cubes).
It follows from there that there are no parity errors of the second
type in the even-sized four-dimensionnal hypercubes, and all have the
third type.
Now, let’s come back to your list of 4D parity errors in the reduction
methods:
> In 4D:
> Single 2-colour cubie flipped
> Two 2-colour cubies switched
> Single 3-colour cubie flipped
> Two 3-colour cubies switched
The only case which is unknown from the 3D big cubes is the third.
I thought it cannot exist, I know have the proof: to flip a single
3-colour cube, you have to flip and switch its two elements, and
that’s an odd permutation, which is not allowed by the constraint p
(3SP) = 0 proved above.

I’ll come back to study the odd-sized four-dimensionnal parity errors
in some time, as for now, thank you if you read my whole message until
here.

Thibaut.