# Message #627

From: rev_16_4 <rev_16_4@yahoo.com>

Subject: Re: Parity on MC m^n

Date: Sun, 01 Feb 2009 07:20:16 -0000

Roice, you bring up a very good point. I wasn’t sure there were

positions on a 4^d that, using a reduction method, would generate

impossible positions on a 3^d (I’m going to switch to your notation,

it’s been around longer). I thought it might be possible, seeing that

was the gereral consensus. But I hadn’t experienced one myself. Can

someone email me a 4^4 log file with such a position?

I’m still retaining my nontraditional definition of parity errors

essentially as odd parity (and in my n^d solution double odd as

well). Ignoring this definition, check out the "single flipped"

parity error on a 4^3. It will take an odd number of inner slice

quarter twists to solve this.

On a 3^3, a single swapped pair has odd parity. This cannot happen

due to the even (aka double odd) parity of a single quarter twist on

a 3^3. However, using reduction, the "single swapped edge pair" (with

correct orientation) parity err on a 4^3 can seem to occur. This will

alway take an even number of quarter twists to solve.

You can see a similar phenomenon with a 3^3. If you have an even

number of corner pair-swaps to perform, you will have an even number

of edge pair-swaps also. It took an even number of quarter twists to

generate this position, and it will take an even number of quarter

twists to solve. The same goes for odd. An odd # of Corner pair-swaps

will always be accompanied by an odd # of Edge pair-swaps and an odd

# of twists. This is my double odd parity.

Now with the case of n=4, d>3, this rule above is not the case. you

can generate any position with an even number of twists, or an odd

number of twist. I’d write out all the actual pair-swaps from a

single quarter twist, but I’m too lazy right now. In a nutshell there

are 6 corner pairs, 18 edge pairs, 18 face pairs, and 6 center pairs

swapped during an outer slice rotation. An inner slice rotation has 6

edge pairs, 18 face pairs, and 18 center pairs swapped. As you can

see, all are even, hence even parity (the faces and centers are

irrelevent). You can never generate an odd parity position, hence my

belief there are no parity errors for this puzzle.

With the reduction method, sometimes the pairs are swapped in such a

manner that a simple even parity position for the caging method I

use, if attempted to be solved using reduction, would result in an

unsolvable 3^4 position. (I’m trying to think of a position where

this could occur… SOMEONE PLEASE SEND ME AN EXAMPLE LOG FILE!) If

someone can show me a log with a "single 3C w/ two stickers flipped"

4^4 parity position, and how to generate it, I’d be grateful (and

completely shocked!). Other than that, I can’t think of a 4^4 parity

that I think would be unsolvable with (non-caging) techniques similar

to a 3^4.

-Levi

— In 4D_Cubing@yahoogroups.com, Roice Nelson <roice3@…> wrote:

>

> Hi guys,

>

> Thank you Levi. This deepened my understanding, especially the

discussion

> of what you termed "double odd", as well as the "why" of single

corner swaps

> on the 4^3. And thank you David for enumerating the parity

conditions for

> d>=4. I would like to go over what I took from this discussion,

and hope

> the current state of my understanding can help clarify what we mean

by

> "parity".

>

> Levi preferred definitions of parity based on the permutations of

the pieces

> during twists, for which one can identify the possible cycle

parities (even,

> odd, or double odd) that arise for the various piece types. In

this sense

> odd parities indeed do *not* occur for n^d puzzles where n is even

and d>=4

> (sorry to differ on the labels btw, I’m too set in my ways).

>

> This discussion of parities of sticker permutations is

enlightening, but I’m

> left with the feeling that saying "no parity conditions exist for

the 4^4"

> misses some real effects the solver encounters when using the common

> reduction method on this puzzle. It’s been almost a decade, but I

for one

> was pulling my hair out when working through the 4^4 due to

encountering

> impossible 3^4 configurations.

>

> So what is going on here?

>

> We can figure out whether twists cycle pieces in an odd/even

fashion, but as

> long as we never limit the full set of twists that can be done on

the

> puzzle, we will never encounter a "parity *problem*", by which I

mean an

> unsolvable state. Without trickery via disassembly, the puzzle is

always

> solvable (though the parity conditions do say something about how

the

> solution must go). What I’m coming to here is that *"odd parity

> condition" != "parity problem", and there is some confusion because

the term

> "parity" is being overloaded with both meanings. This overloading

is a bit

> unfortunate in my opinion (I’ve never nailed down the haziness I

felt about

> this term until now), but both uses of parity seem legitimate if

the meaning

> is clear.*

>

> So here is my take: "Odd parities" will arise in various

situations due to

> the way twists end up cycling stickers, and solving these requires

an odd

> number of certain twists. "Parity problems" or "parity errors"

will arise

> when we artificially limit the full set of twists used on a puzzle

midway

> through a solution, and solving these problems will necessarily

involve

> disavowing the artificial twist restrictions we tried to work with.

>

> To use a 4^3 example Levi mentioned, consider "two pair of joined

edges

> swapped that look like a single pair swapped on a 3^3 during the 4^3

> reduction method". In the context of restricted twisting, this

*is* a

> parity problem because it is unsolvable using only the limited 3^3

twist set

> - it is effectively a single swap of two edges, an odd parity

condition. In

> the context of unrestricted twisting, it is not a parity problem or

an odd

> parity condition (aside: assuming "even parity moves" means outer

twists,

> which are even for edges, the statement that you can solve this

state using

> even parity moves appears incorrect). In short, parity problems

(I’ll never

> again just say parities!) occur when we use a limited 3^d model of

cycle

> parities on an n^d puzzle.

>

> I hope my thoughts on this are clear. Maybe there are better terms

we could

> adopt for the distinction between these two uses of the word parity?

>

> All the best,

> Roice

>

> P.S. David, I’m sure this was implicit in your statement, but when

you said

> "For example, on an n^5, a single corner can be in any possible

orientation

> while the rest of the cube is solved!" I thought I’d remark

explicitly that

> this excludes mirror orientations

> (enantiomorphs<http://en.wikipedia.org/wiki/Enantiomorph>).

> So e.g. you can twirl 3 of the stickers leaving 2 fixed, you can

cycle 4 of

> them leaving one fixed, etc., but you still can’t swap 2 stickers

leaving 3

> fixed.

>

>

> On 1/28/09, David Smith <djs314djs314@…> wrote:

> >

> > Thanks for your definition of parity and detailed explanation!

> > Everything you

> > said was right on. Based on your permutation-based definition of

parity, I

> > thought I would let you know what I have discovered about m^n

cubes.

> > You were absolutely right about parity conditions existing for

all m^3

> > cubes

> > where m>1. And you were also right about parity conditions not

existing on

> > m^n puzzles where n>=4 and m is even. When m is odd, the only

parity

> > condition

> > that exists is what you call Double Odd Parity, and only on the

central

> > groups

> > of 2-colored and 3-colored pieces.

> >

> > I would be more interested about what you have to say on

orientations,

> > whenever

> > you get the chance. Orientations can be very tricky when the

dimension is

> > greater than 3. For example, on an n^5, a single corner can be

in any

> > possible

> > orientation while the rest of the cube is solved! The non-central

> > 4-colored pieces

> > behave like the corners on an n^4; there can be a single pair of

pieces,

> > each of

> > which can have 4 different orientations, or a single piece could

have 4

> > different

> > orientations, the rest of the cube unaffected. And there is even

a group

> > of

> > 3-colored pieces that can have a pair of pieces in different

orientations

> > without

> > affecting the rest of the cube. I have pretty much figured out

all

> > possible permutation

> > and orientation possibilities for an m^n, so feel free to email

me if you

> > need

> > more information. The only reason I haven’t figured out the m^n

formula

> > yet

> > is counting the number of groups (what you call identical type

pieces) for

> > all

> > possibilities. They get horrendously complicated for large n.

> >

> > I hope I was able to help, and good luck with your project!

> >

> > David

> >

> > — On *Wed, 1/28/09, rev_16_4* wrote:

> >

> > From: rev_16_4

> > Subject: [MC4D] Parity on MC m^n

> > Date: Wednesday, January 28, 2009, 1:17 AM

> >

> > I was hoping mentioning parity would get a discussion started on

> > this, as parity was my biggest hang-up on announcing my m^n

solution.

> > A traditional definition of parity, with regards to a m^n puzzle,

> > usually is along the lines of "A position that cannot occur on a

> > standard 3^n, when solving a m^n with m>=4 and using the reduction

> > method." A definition along these lines is perfectly suitable for

the

> > m^3 puzzles. I don’t particularly like this definition because it

> > never really explains parity. I wish I could remember the site I

> > first read and UNDERSTOOD parity. What’s crazy is once you

> > reach a complete understanding of parity, you’ll realize any

parity

> > condition can be corrected with a single quarter twist on the

parity

> > affected layer. (corrected, not solved…)

> >

> > I prefer a definition of parity more along the lines of "A

position

> > with an odd number of pairs of IDENTICAL TYPE pieces (without

> > duplicates) swapped. (Odd Parity)" This definition actually

allows a

> > parity condition on all m^3, including the standard 3^3. The

3^3’s is

> > usually explained away because people say you’re always swapping

an

> > even number of pairs of pieces on the final layer (Even Parity). I

> > disagree because sometimes its actually one pair of corners, and

one

> > pair of edges. (Double Odd Parity as I call it.) I also ignore

> > orietation as far as parity is concerned which I hope will become

> > clear why later. Another definition for parity I like is "Any

> > position that cannot be solved using only even parity moves for

each

> > unique type of piece."

> >

> > Let me explain this all a little better. What is the basic unit of

> > movement on a m^3 (and the m^n in general)? I consider it a 90

degree

> > turn of a layer along an axis. All other turns and positions can

be

> > created from a sequence of these basic units. So if we can figure

> > what type of parity each basic unit has, we can figure what type

of

> > parity any number of these basic units have added together. We’ll

use

> > this simple movement to start our analysis of parity. I’m also

going

> > to start with the pieces on a single face on a 2^3 puzzle, then

show

> > a 3^3, and finally a 4^3. Here’s my Up face on my solved 2^3:

> >

> > ———

> > | 1 | 2 |

> > ———

> > | 4 | 3 |

> > ———

> >

> > Let’s say I could somehow swap just a single pair of corners, 1

and 2.

> >

> > ———

> > | 2 | 1 |

> > ———

> > | 4 | 3 |

> > ———

> >

> > I would write this as (1,2). This would signify "Swap the piece in

> > position 1 with the piece in position 2."

> >

> > Let’s say I swapped another single pair of corners, 2 and 3.

> >

> > ———

> > | 3 | 1 |

> > ———

> > | 4 | 2 |

> > ———

> >

> > Since 2 is in position one, I would write this as (1,3). "Swap

piece

> > in pos 1 with piece in pos 3."

> >

> > Finally, I perform one last swap, 3 and 4.

> >

> > ———

> > | 4 | 1 |

> > ———

> > | 3 | 2 |

> > ———

> >

> > 3 is again in position one, so I would write this as (1,4).

> >

> > after a single clockwise quarter turn on my Up face, I have:

> >

> > ———

> > | 4 | 1 |

> > ———

> > | 3 | 2 |

> > ———

> >

> > This looks just like my position after three pair-swaps. So a

single

> > quarter turn can be written as (1,2)(1,3)(1, 4). A quarter twist

on a

> > 2^3 is an odd parity position.

> >

> > Now let me show you a different sequence: (I removed the 4 for

> > clarification) (Here’s the sequence if you have a cube handy: R’

F R’

> > B2 R F’ R’ B2 R2)

> >

> > ——— ———

> > | 1 | 2 | | 3 | 1 |

> > ——— -> ———

> > | | 3 | | | 2 |

> > ——— ———

> >

> > This is a common move, known by almost anyone who can solve the

cube.

> > As shown above, it’s generated from two pair-swaps, aka an even

> > parity position. (1,2)(1,3)

> >

> > Now I’m sure some of you are asking "What happens when I perform a

> > second quarter twist?" I’ll let you verify for yourselves, but the

> > end results is an even parity position. Parity works like basic

> > addition. Add the number of pair-swaps performed, odd is odd,

even is

> > an even parity position. Also note that the move (1,2)(1,3)

required

> > 12 odd parity quarter twists to generate an even parity position.

> >

> > I’m going to skip to the meat and potatoes of the 3^3 and 4^3. For

> > the 4^3, I need to perform two different quarter twists due to the

> > inner Up layer.

> >

> > 3^3

> > ———— - ———— -

> > | 1 | 2 | 3 | | 7 | 8 | 1 |

> > ———— - ———— -

> > | 8 | X | 4 | -> | 6 | X | 2 |

> > ———— - ———— -

> > | 7 | 6 | 5 | | 5 | 4 | 3 |

> > ———— - ———— -

> > (1,3)(1,5)(1, 7)(2,4)(2, 6)(2,8)

> >

> > This is traditionally called even parity. This is also where the

> > issues come in with solving the parity problems using the 4^3

> > reduction method. You CANNOT generate odd parity positions using

even

> > parity positions. It’s just simple addition. However, since

there’s

> > no physical way to swap a corner with an edge, I’d write the

position

> > above as:

> > (1,3)(1,5)(1, 7) and (2,4)(2,6)(2, 8)

> >

> > Hence my terminology "Double Odd." I cannot use a combination of

> > double odd positions to generate a single odd position - the math

is

> > still there (2 odds equals an even). However I CAN’T use a

> > combination of even parity moves (like 2 corner swaps and 2 edge

> > swaps) to generate a double odd position.

> >

> > 4^3out

> > ———— —– ———— —–

> > | 1 | 2 | 3 | 4 | | a | b | c | 1 |

> > ———— —– ———— —–

> > | c | d | e | 5 | | 9 | g | d | 2 |

> > ———— —– -> ———— —–

> > | b | g | f | 6 | | 8 | f | e | 3 |

> > ———— —– ———— —–

> > | a | 9 | 8 | 7 | | 7 | 6 | 5 | 4 |

> > ———— —– ———— —–

> > (1,4)(1,7)(1, a)(2,5)(2, 8)(2,b)(3, 6)(3,9)(3, c)(d,e)(d, f)(d,g)

> >

> > I’d write this as:

> > (1,4)(1,7)(1, a) and (2,5)(2,8)(2, b)(3,6)(3, 9)(3,c) and (d,e)

(d,f)(d, g)

> >

> > Why did I only make three groups? Simply, all the edges are

> > identical, and from my definition of parity: "A position with an

odd

> > number of pairs of IDENTICAL TYPE pieces swapped." How do I

determine

> > if two pieces are identical? Well here’s where my math knowledge

> > fails me, but if you can physically rotate a puzzle so that one

piece

> > occupies the same space as another, then they are identical type

> > pieces.

> >

> > I’d actually call an outer 4^3 quarter twist odd corner, even

edge,

> > even face parity. I know a couple of you are saying "Hey, dummy!

> > Based on what you’ve told us so far, the faces have odd parity!"

Let

> > me explain why I said even. The math is simpler. If I say "odd,"

that

> > means I MUST use an odd number of pair swaps to fix it. If you can

> > generate a position with an even number of pair swaps, then I say

it

> > defaults to an even parity position, even if it appears to be an

odd

> > number of pair swaps. You can swap an odd number of faces using an

> > even number of swaps because some of the faces are colored

> > identically. ((RED,RED)(RED, BLUE) - the first swap could just as

> > easily not happened.) Anthony, this is exactly what you mentioned

in

> > your post.

> >

> > Incidentally, this even edge parity, with odd corner parity, is

what

> > allows the 4^3 to exhibit the single corner swap positions

impossible

> > on the 3^3. (This is also why I don’t consider the two pair of

joined

> > edges swapped that look like a single pair swapped on a 3^3 during

> > the 4^3 reduction method a parity condition. This is actually even

> > parity, and is solvable using even parity moves.)

> >

> > 4^3in

> > ———— —– ———— —–

> > | 1 | 2 | 3 | 4 | | a | b | c | 1 |

> > ———— —– ———— —–

> > | c | | | 5 | | 9 | | | 2 |

> > ———— —– -> ———— —–

> > | b | | | 6 | | 8 | | | 3 |

> > ———— —– ———— —–

> > | a | 9 | 8 | 7 | | 7 | 6 | 5 | 4 |

> > ———— —– ———— —–

> >

> > (1,4)(1,7)(1, a)(2,5)(2, 8)(2,b)(3, 6)(3,9)(3, c)

> >

> > I’d write this as:

> > (1,4)(1,7)(1, a) and (2,5)(2,8)(2, b)(3,6)(3, 9)(3,c)

> >

> > This is odd for edges and even for faces (remember this is the

inner

> > slice). This is the cause for the familiar "Single reverse

oriented

> > edge" parity condition. It is actually a single swapped pair of

edges

> > that can’t help but be disoriented.

> >

> > In summary, on each puzzle:

> > A quarter twist here: Causes odd parity here:

> > 2^3 Corner

> > 3^3 Corner and Edge

> > 4^3 Out Corner

> > 4^3 In Edge

> >

> > Easy, huh? I’ll let you guys work on the higher order puzzles to

see

> > why I say parity conditions do not exist for m^n puzzles for n>=4

and

> > all m that are even. I do think they exist on the m^3 for ALL m>1.

> > They are just not the major problem people think they are. And

using

> > the caging method I use does eliminate the typical manifestation

of

> > parity. It’s simply fixed by a quarter twist of the appropriate

> > layer, then progress is continued on the pieces with fewer

stickers.

> >

> > The fact that I believe parity conditions cannot exist on pieces

with

> > duplicates is exactly why I used the caging method for my m^n

> > solution. After you reach the pieces with n-2 stickers, the

solution

> > is trivial for puzzles with an even m. With an odd m, it takes a

> > little more work. A quarter twist affecting only the pieces w/o

> > duplicates (the center pieces) and w/ odd parity is all that’s

> > required (plus several 100’s of twists, an even number of course,

to

> > fix any additional pieces repositioned) .

> >

> > I reread this post and realized I never explained why I don’t

> > consider orientation when considering parity. If anyone wants I

can

> > go into this later. This post is already quite long, so I’m not

going

> > to proceed here.

> >

> > Happy Hyper-cubing!

> >

> > -Levi

> >

> >

> > .

> >

> >

> >

>