# 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.