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