• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 40,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

My ultimate commutator challenge

Christopher Mowla

Premium Member
Joined
Sep 17, 2009
Messages
1,184
Location
Earth
YouTube
Visit Channel
you gave one set of conditions (B = D etc) under which merging is possible, as [A, B][C, B] = [AC, B].
Well, you forgot to mention that pieces affected by A != pieces affected by C. That's very important to remember. In fact, that very fact can be used as a generalized process of doing this. I made an effort to come up with a different example where B != D (since that appeared to be too trivial).

With [A, B] = [R U2 R',F] and [C, D] = [[B' D': M' D L' D' M D L D'], S' R2 S R2],
both C and D are "independent" from A, B and [A, B].

That is, [R U2 R',F] [[B' D': M' D L' D' M D L D'], S' R2 S R2] can be merged to
[F: [F' [B' D': M' D L' D' M D L D'] , S' R2 S R2 R U2 R']]

(Notice that I conjugated once to make this work, but this is still a commutator nonetheless.)

Does this example show things better for you? If you were to ask me when two commutators cannot be merged, if their pieces are not independent (whether both pieces from one commutator are from the other commutator--this example--or if one piece from each is independent--first example), one could merely attempt to combine any two commutators that do not follow the restrictions I gave. To me, that's proof that those particular two commutators cannot be merged into one (well, not to one that yields the same permutation as the product of the two commutators).

Why? If no pieces from the commutators are independent, then one will conflict with the other, at some level or another. You can still possibly merge them into a commutator, but that commutator will not have the exact same effect on the cube as their product due to the moves from one commutator affecting pieces the other affects.

I still don't see why when two commutators cannot merge doesn't mean one of them cannot merge with another that does the same permutation of the other, as long as the new commutator being used follows the restrictions I illustrated here.

If I am still not understanding what is being asked, I apologize. I mainly wanted to show another example which elaborated my method more.
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
those particular two commutators cannot be merged into one (well, not to one that yields the same permutation as the product of the two commutators).

*Any* two can be merged into one (if I understood Bruce/Joyner correctly). You seem to misunderstand what's meant with "merging" - you don't have to reuse "the moves from" the given commutators to build your output commutator. Think about the cube group elements, not about some move sequences representing them.
 

TMOY

Member
Joined
Jun 29, 2008
Messages
1,802
WCA
2008COUR01
If I understand Bruce/Joyner correctly, their result is not sufficient to prove Per's challenge. It only implies that any non-disorienting even permutation of the cube (that is any even permutation A such that A^n has no pieces in place but disoriented for any n) can be written as a commutator, you still have to deal with the disorienting ones.
 

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
I just checked again (page 229 here) and I think it says that half of all cube group elements are commutators and that the requirement is exactly that corner permutation and edge permutation are even.
 

macky

Premium Member
Joined
Apr 4, 2006
Messages
402
Location
Stanford, CA
WCA
2003MAKI01
Stefan, that links gives me a 403. But the condition you mention is the "obvious" one Ravi gave, and Lucas and TMOY disagree in their interpretation of Bruce/Joyner. I think the result you're citing is the rather trivial one (as Lucas and Ravi showed) about the commutator subgroup (that is, the subgroup _generated by_ the commutators).

Can someone send me Joyner?
 

cuBerBruce

Member
Joined
Oct 8, 2006
Messages
914
Location
Malden, MA, USA
WCA
2006NORS01
YouTube
Visit Channel
Stefan, that links gives me a 403. But the condition you mention is the "obvious" one Ravi gave, and Lucas and TMOY disagree in their interpretation of Bruce/Joyner. I think the result you're citing is the rather trivial one (as Lucas and Ravi showed) about the commutator subgroup (that is, the subgroup _generated by_ the commutators).

Can someone send me Joyner?
I was able to access it using a Google "Quick View" link rather than the normal link.

But yes, I think I have to agree with macky that Joyner is only proving that the elements can be written as a finite product of commutators, not necessarily a single commutator.
 
Last edited:

Stefan

Member
Joined
May 7, 2006
Messages
7,280
WCA
2003POCH01
YouTube
Visit Channel
The link works fine for me. Try again? Alternatively, google joyner adventures in group theory and you'll probably find it.

Oops, yes, I might have misunderstood Joyner's definition of the commutator subgroup. In my defense, his definition...

Joyner said:
The group G′ generated by all the commutators {[g, h] | g, h belong to G}.

... doesn't even look like a complete sentence to me (and I find it unclear).
 
Last edited:

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
G' is generated by the set of all commutators in G - his set as written means {commutator of g and h, such that g and h belong to G}.

Can anyone find a cube position in the commutator subgroup which can provably NOT be created by a single commutator?
 

siva.shanmukh

Member
Joined
Jan 19, 2008
Messages
85
Location
Chennai, India
WCA
2008SHAN01
YouTube
Visit Channel
Commutator for every even move sequence

Since commutators produce only even permutations in any given orbit in an nxnxn super cube. I questioned myself if the following statement is true.

All states that occur on an nxnxn super cube by applying a move sequence which has even number of quarter turns for each layer(assuming the number of layers = ceil(n/2)) can be represented as a commutator or a conjugate.

The answer is obviously yes, since the above case produces an even permutation in each orbit and we can always come up with a commutator/conjugate which does this.

But my question is if any even move sequence (Even with respect to each layer) be expressed as a commutator/conjugate which is simplified by move cancellations?

For example

R U' [U R U R U, z' y2] U R' is a commonly used U perm in the form of C A B A' B' C'

Can we write any even move sequence (Even with respect to each layer) in the same way as the above alg?
 

Christopher Mowla

Premium Member
Joined
Sep 17, 2009
Messages
1,184
Location
Earth
YouTube
Visit Channel
It's interesting that you mentioned the supercube and not just the regular 6-colored cubes. One exception that I believe is a possibility is just a half turn, say, U2.

We can express U2, for example, as a commutator if we consider the non-supercube by letting X be an N-Perm in the U layer and letting Y be U.
[R' U R2 B2 U R' B2' R U' B2 R2' U' R U', U].

However, representing U2 on the supercube as a commutator might not be possible (the commutator above twists the composite center 180 degrees too). I would be very interested to see someone do this (if it's possible).

Interesting enough though, if we consider the same case for the inner layer by letting X be an "interior N-Perm" in slice r and Y being r, then it does work on the supercube inner slice.
[D2 r' D2 F2 l' U2 l U2 r' U2 r U2 F2 r D2 r D2, r]

This problem is too complex for me to even guess at an answer for it in general, but I think the first example I gave above might be a trivial counterexample for the nxnxn supercube, which is what I am understanding to be your stated problem.
 

TMOY

Member
Joined
Jun 29, 2008
Messages
1,802
WCA
2008COUR01
Since commutators produce only even permutations in any given orbit in an nxnxn super cube. I questioned myself if the following statement is true.

All states that occur on an nxnxn super cube by applying a move sequence which has even number of quarter turns for each layer(assuming the number of layers = ceil(n/2)) can be represented as a commutator or a conjugate.

The answer is obviously yes, since the above case produces an even permutation in each orbit and we can always come up with a commutator/conjugate which does this.
Did you read the thread ? Your "obvious" assertion not only is far from obvious, but is not proved yet, not even for the 2^3 cube.

Actually, thanks to Bruce/Joyner proving it for any size of cube isn't more difficult than proving it for the 3^3 but we still need to complete the proof of Per's challenge.
 

qqwref

Member
Joined
Dec 18, 2007
Messages
7,834
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
Visit Channel
However, representing U2 on the supercube as a commutator might not be possible (the commutator above twists the composite center 180 degrees too). I would be very interested to see someone do this (if it's possible).
On the 3x3x3, at least, no commutator can twist a single face by 180 degrees. A little proof:
- Let q be the sum of all centers' orientations, mod 4. Let q(A) be the effect on q when we perform sequence A. Observe that the order we do operations doesn't affect q (that is, q(AB) = q(BA)), and also cube rotations don't affect q (that is, q(A) = q([any rotation] A)).
- A commutator of form A B A' B' must thus have the following effect on q: q(ABA'B') = q(AA'BB') = q(identity) = 0.
- Since a 180-degree center twist affects q by 2, a commutator of form A B A' B' cannot accomplish this.

On even cubes we can, though: try [Lw Rw Dw2 Lw' Rw', U] on the 4x4x4.
 

siva.shanmukh

Member
Joined
Jan 19, 2008
Messages
85
Location
Chennai, India
WCA
2008SHAN01
YouTube
Visit Channel
Did you read the thread ? Your "obvious" assertion not only is far from obvious, but is not proved yet, not even for the 2^3 cube.

Actually, thanks to Bruce/Joyner proving it for any size of cube isn't more difficult than proving it for the 3^3 but we still need to complete the proof of Per's challenge.

My statement is now not just far from obvious but wrong like qqwref formalized. But it is not yet wrong for even super cubes like qqwref exemplified. And the spirit of making that statement is to signify the difference of the 4 centers of each orbit and not the non-moving center.

Can we try to prove/disprove my statement either by ignoring centers or by restricting the move sequence, that we start with, to have only total face quarter turns to be a multiples of four for each face.

i.e.,

If any move sequence, even with respect to each slice and multiple of 4 with respect to each face be expressed as a commutator/conjugate which is simplified by move cancellations?
 
Last edited:

Christopher Mowla

Premium Member
Joined
Sep 17, 2009
Messages
1,184
Location
Earth
YouTube
Visit Channel
@qqwref,

Thanks! Obviously, as siva.shanmukh noted, it follows that it is not possible on any odd cube size. Just adjusting your commuator a little, we can see that the closest we can get to doing U2 on the 5x5x5 and larger odd supercubes is moving all of the pieces except the fixed center piece: [Lw Rw (Uw2 y2) Lw' Rw', U'] (on the 5x5x5).

We can treat this algorithm as a conjugate of U2 in order to have all pieces in the U-Layer rotated 180 degrees [[Lw Rw (Uw2 y2) Lw' Rw', U']:U2], however, you have already proved that U2 cannot be expressed as a commutator on the 3x3x3 odd supercube, and thus we cannot express the above as a conjugated commutator for larger odd cube sizes because the composite center on the nxnxn odd cube behaves exactly like the fixed center on the 3x3x3 supercube.

For some reason I only looked at the 3x3x3 and not the 4x4x4 for the outer layer turns. Thanks again for pointing out that we can divide a face into 4 equal parts, which means we can do an X-perm 2 2-cycle of \( 1\times \frac{n}{2}\times \frac{n}{2} \) blocks!
 
Last edited:

Christopher Mowla

Premium Member
Joined
Sep 17, 2009
Messages
1,184
Location
Earth
YouTube
Visit Channel
Possible Proof for Wing Edges

I think I have an idea of how to prove this, at least for a single orbit of wings in the nxnxn.

Almost everyone who knows how to solve a 4x4x4 cube knows Stefan's PLL Parity algorithm, r2 F2 U2 r2 U2 F2 r2. Some know that this is just a conjugate of the move r2, as it can be expressed as [r2 F2 U2: r2].

Now, I can comfortably make the claim (without any possibility of doubt) that ANY 2 2-cycle of wing edges case in the "cage" of big cubes can also be made with a conjugate of the move r2. Like Stefan's alg, they of course will not be supercube safe, but I will later show that this will not be an issue (if you are concerned about having a supercube safe commutator).

For those who have never seen the two 2 2-cycle of wings algorithms I made in the past, see Algs_Sorted.pdf, 2 2-cycles.pdf, and the F3L documents in this post just to get an idea of what I mean by 2 2-cycle conjugates, in general.

In addition, we can create every 2 2-cycle of wing cases in the "cage" of big cubes by just conjugating the move r2.

Note that we can generate any even permutation with products of 2 2-cycles because every 2 2-cycle can be expressed as a product of two overlapping 3-cycles.

So suppose we have a conjugate A for one 2 2-cycle of wings A X A', where X = r2. In addition, we have a different conjugate B, for another 2 2-cycle of wings: B X B'. (Note that in both algorithms, X is present because I previously claimed that every 2 2-cycle case can be expressed as a conjugate of the same move, r2).

Now, a few posts ago in this thread, I showed that the move r2 can be expressed as the commutator [D2 r' D2 F2 l' U2 l U2 r' U2 r U2 F2 r D2 r D2, r] for the nxnxn.

So both A X A' and B X B' are commutators since the equality [O:[P,Q]] = [[O:p],[O:Q]] holds.

If we multiply these two commutators, we have
A X A' B X B'

Since r2 = (r2)'
= A X A' B X' B'

Now, the commutator B' A X A' B X' can be conjugated to obtain the above:
B
B' A X A' B X'
B'
= A X A' B X' B'
, which shows that the product (A X A') (B X B') merges to the commutator [B: [B' A, X] ].

Now, if we were to multiply three 2 2-cycles together, where each 2 2-cycle is composed of only one conjugation of the move r2, then we would have a problem because we would have an odd number of Xs (X = r2 = commutator). Since a commutator must have an even number of every move it contains, then these three 2 2-cycles could not possibly be merged to a single commutator.

However, note that we can freely create each and every 2 2-cycle of wings with two 2 2-cycle of wings. Here are two examples of this:
([l2 U' B2 U' x U' R' U: l2] ) (y' [R B: [l2 U' F2 U': l2]] y)
(y2 [r2 U F2 U: r2] y2) ([y x U2 l2 U F' L U R2 F': r2])

Therefore, we can always have an even number of Xs in our product.

Now let's confirm that we can merge three 2 2-cycle of wings (which are commutators) as one commutator.

Let one 2 2-cycle of wings algorithm be C X C' and another be D X D', and let's suppose that combining them yields a 2 2-cycle of wings.

Before we found that A X A' B X B' merged to the commutator [B: [B' A, X] ] and therefore A X A' B X B' is a commutator. Similarly, C X C' D X D' is also a commutator.

The equality [O:[P,Q]] = [[O:p],[O:Q]] tells us that a conjugated commutator is a commutator (which shows why A X A' and B X B' are commutators), which also means that a shifted commutator is a commutator (which will justify what follows).

Let's combine these four 2 2-cycle algorithms (which is combining three 2 2-cycles, by definition of (C X C')(D X D') ).

(A X A' B X B') (C X C' D X D')
Since X = X',
(A X A' B X' B') (C X C' D X' D')
Since [O:[P,Q]] = [[O:p],[O:Q]], we rotate the moves in parenthesis and still have a product of two commutators.

Moving A to the end and D' to the beginning,
(X A' B X' B' A) (D' C X C' D X')

Since [O:[P,Q]] = [[O:p],[O:Q]], we can also rotate pieces at the end positions of the parenthesis to the beginning or end of the entire product to still have a product of two commutators.
Rotating X to X', they cancel to leave us with:
(A' B X' B' A) (D' C X C' D)

Moving C' D from the end to the beginning of the entire product,
C' D A' B X' B' A D' C X
= [C' D A' B, X'], which is a single commutator, which means that (A' B X' B' A) (D' C X C' D) is also a single commutator.

To handle merging four 2 2-cycles in which their effect is literally four 2 2-cycles (no consecutive pair of 2 2-cycles merges to a single 2 2-cycle), we still can use the above argument.

Now this can be extrapolated to any number number of 2 2-cycles of wings.

Since every even permutation of wings can be reached with a product of 2 2-cycle wing algorithms, every 2 2-cycle of wings can be expressed as a commutator, and these commutators can be merged into one commutator,
then every even permutation of wings can be expressed as a single commutator.

Lastly, as I mentioned at the beginning about the issue that a single 2 2-cycle conjugate is not supercube safe, note that we can construct all of these algorithms to affect the same centers. Since there must be an even number of Xs in order for all 2 2-cycle algorithms to merge as a single commutator, then doing a 2 2-cycle of four 1x(n-2) center blocks an even number of times yields the identity (the centers on supercubes would be untouched once the entire commutator is fully executed). But this is not at all required, as we can have consecutive 2 2-cycle algorithms involve different 1x(n-2) center blocks.

EDIT:

Maybe I should make it clear how we can extrapolate it to any number of 2 2-cycles of wings.

A X A B X B can be interpreted as either one 2 2-cycle (if the 2 2-cycles of A X A and B X B overlap two pieces) or two 2 2-cycles. So, to represent any number greater than or equal to one 2 2-cycle, we have

(A X A' B X B')(C X C' D X D')(E X E' F X F')....(Y X Y' Z X Z')...

I believe if we just look at the following example, we can see enough evidence. (Note that X = X').
(A X A' B X B')(C X C' D X D')(E X E' F X F')
We just rotate the outer most parenthesis so that X will be on the ends:
(X A' B X B' A)(C X C' D X D')(F' E X E' F X)
Then we cancel the Xs
(A' B X B' A)(C X C' D X D')(F' E X E' F)
We can continue rotating the outer most
(X B' A A' B)(C X C' D X D')(E' F F' E X) = (X)(C X C' D X D')(X)
Until we can get rid of the outer-most parenthesized groups completely
(C X C' D X D')
So that we will eventually end up with the single product of (C X C' D X D'), which merges to a single commutator.

Similar to this entire argument with conjugates, every ODD permutation of wing edges on even cubes at least, can be represented as a product of conjugates of the moves r and r', based on the method I showed in my 4-cycle conjugates in this post.
 
Last edited:

Christopher Mowla

Premium Member
Joined
Sep 17, 2009
Messages
1,184
Location
Earth
YouTube
Visit Channel
Possible Proof for all pieces of the nxnxn cube

I think I have now found a way to prove Per's challenge in its entirety.

For those who read my previous post before I edited it (several hours after I first posted it), I changed the first sentence. That post was merely supporting the idea that all even permutations of one orbit of wing edges in the nxnxn cube could be expressed as a single commutator. However, I believe I have now generalized it to the entire cube.

My previous post focused on taking just one orbit of wings at a time. But obviously this is not at all near to what Per's challenge was.

To start off, I want to give a few examples of how to express moving different piece types separately.

The idea is to have Rw2 instead of just r2, as in my previous post. That is, Rw2 represents all \( \left\lfloor \frac{n}{2} \right\rfloor \) slices on the right half of the nxnxn cube (for \( n\ge 1 \)).

Recall that in my previous post, I just called r2 X. Here, we just call Rw2 X. And just as r2 could be expressed as a commutator, so can Rw2.
Rw2 = [D2 Rw' D2 F2 Lw' U2 Lw U2 Rw' U2 Rw U2 F2 Rw D2 Rw D2, Rw].

And of course since Rw2 = Rw2', then X = X'.

So if we can see that all piece types (corners, middle edges, wing edges, and non-fixed centers) can be handled separately with conjugates of the same move, Rw2, then just as I was able to merge the commutators in my previous post as one (because they all consisted of the same move, X) we can merge all of these commutators into one commutator because we claimed that the conjugates A, B, C, D, etc. did not have to be the same.

The Method
All we need to do to affect each and every piece type with a product of conjugates ([A:Rw2][B:Rw2])([C:Rw2][D:Rw2]),etc., is to

1) Let A = Moves which ultimately just affect the piece type of our choice in the layers Rw2.
2) Form the conjugate [A:Rw2]
3) Do another conjugate [B:Rw2] in which B are moves which also only affect the piece type of our choice in the layers Rw2.

(A must not equal B, otherwise we will have the identity).

So we will be able to affect each and every piece type with a PAIR of conjugates of Rw2.
That is,
[A: Rw2]
[B: Rw2]

This is actually no different than my previous post because we needed to have an EVEN number of Xs (here, Rw2s) in order to be able to merge all of them into a single commutator. Wing edges are the only piece type which do not require a pair of conjugates of r2 to be able to visually just swap wings (because swapping same color centers with each other cannot be seen on a regular cube), but we still needed to have an even number of Xs to be able to merge all conjugations of X into a single commutator.

Examples

Corners
http://alg.garron.us/?alg=[[F-,_RB_R-]:Rw2] [[F-,_RB_R-]-:Rw2]&cube=7x7x7&notation=WCA[[F', RB R']:3r2]
[[F', RB R']':3r2]


Wing Edges(Note that we can take all orbits at once or only a subset)
[[2F', U F' U']: 3r2]
[[2F', U F' U']': 3r2]


Middle Edges
[S' U F' U' S U F U': 3r2]
[M' U' R U M U' R' U: 3r2]


X-Center Pieces
[e' m' e 2R U' 2L' U 2R' U' 2L U e' m e: 3r2]
[m e' m' e 2R U' 2L' U 2R' U' 2L U e' m e: 3r2]


...etc.

As you might be thinking, yes these pairs of conjugations of Rw2 affect more than 4 pieces (thus they are not 2 2-cycles). However, since any even permutation can be decomposed to a product of 3-cycles, every cycle type can generate all even permutations. In addition, there is no limitation to the number of moves it takes to show that Per's challenge is true or false, and there is no limitation to what cycle type the commutators being merged ought to be (each can be a different cycle type if necessary). So actually making a commutator that generates a random even permutation scramble of the nxnxn is very difficult, but it is definitely possible. However, being able to construct an actual algorithm isn't necessary to see that they exist. Besides, we could just construct simple ones if we need to see concrete examples.

Therefore, even though I thought that strictly having just 2 2-cycles in my previous post was necessary, the only necessity for proving Per's challenge was being able to construct commutators which all have a common element (in my previous post, it was the move r2, but here, it is Rw2 for the general case).

Hence, I think this post and my last post might be all we need to confirm that Per's challenge is indeed true for the nxnxn (not for the nxnxn supercube, of course).
 
Last edited:

macky

Premium Member
Joined
Apr 4, 2006
Messages
402
Location
Stanford, CA
WCA
2003MAKI01
I think I have an idea of how to prove this, at least for a single orbit of wings in the nxnxn.

Hi cmowla,
Your proof is wrong.

...which shows that the product (A X A') (B X B') merges to the commutator [B: [B' A, X] ].
Up to here is fine (though this is a direct calculation, and you don't need the fact that r2 is a commutator). The problem is the following.

(A X A' B X' B') (C X C' D X' D')
Since [O:[P,Q]] = [[O:p],[O:Q]], we rotate the moves in parenthesis and still have a product of two commutators.

Moving A to the end and D' to the beginning,
(X A' B X' B' A) (D' C X C' D X')
The identity [O:[P,Q]] = [[O:p],[O:Q]] follows from the fact that conjugation is a homomorphism (in fact an isomorphism). Here, you conjugated the part within the first set of parentheses by A, and the second part by D. There's no reason to expect that this takes a direct commutator to a direct commutator. If you're not convinced, try following your argument in reverse to write down (A X A' B X' B') (C X C' D X' D') explicitly as a direct commutator.
 
Last edited:
Joined
Oct 1, 2010
Messages
361
I just checked again (page 229 here) and I think it says that half of all cube group elements are commutators and that the requirement is exactly that corner permutation and edge permutation are even.

I always wondered, how big the distance is form any non-commutator case to the nearest commutator Sub Group element.

Is it just a quater turn, half turn, more?
 
Top