Message #625

From: Roice Nelson <roice3@gmail.com>
Subject: Re: [MC4D] Parity on MC m^n
Date: Wed, 28 Jan 2009 21:48:57 -0600

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

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@yahoo.com> 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
>
>
> .
>
>
>