• 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 35,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

Joined
Jun 17, 2006
Messages
654
Likes
1
Thread starter #1
Show that every even permutation on a nxnxn cube can be obtained by a series of commutators. If 2 consecutive comms is a single comm (somehow) then every even permutation is also a direct commutator. No restriction on number of layers used here ...

Per
 

Lucas Garron

Moderator
Staff member
Joined
Jul 6, 2007
Messages
3,554
Likes
86
Location
California
WCA
2006GARR01
YouTube
LucasGarron
#2
Show that every even permutation on a nxnxn cube can be obtained by a series of commutators. If 2 consecutive comms is a single comm (somehow) then every even permutation is also a direct commutator. No restriction on number of layers used here ...
Well, the first part is pretty trivial to see with some cubing intuition, especially since most of this relies on 3-cycles. The second one is gnarlier, and I never managed to get a satisfactory answer (despite Bruce's reference).
 

TMOY

Member
Joined
Jun 29, 2008
Messages
1,802
Likes
0
WCA
2008COUR01
#5
Either I missed somethng or the 2nd part is trivial too, you just have to use the first part and a basic recursion.(if N-1 comms can be replaced by one single comm, than N comms are N-1 comms + 1 comm -> 1 comm + 1 comm = 2 commq -> 1 comm).

The really nontrivial part would be to prove that 2 comms can actually be merged into one.
 
Joined
Jun 17, 2006
Messages
654
Likes
1
Thread starter #6
EP, CP: Generated by 3-cycles. Easy with commutators.
EO, CO: Orient two at a time using commutators. Also easy.
True if we have even permutation in every orbital effected by the "total permutation". Hmmm .... And where are the centers in your sketchy proof?? I didn't mean solely 3x3x3 cube but any size nxnxn regular cube!!

Per
 
Joined
Jun 8, 2011
Messages
1
Likes
0
#7
Hi,

It has already been proved that the alternating group An, which is the group of even permutations on the set {1...n}, consists only of (direct) commutators for n >= 5.

More details, including links to published papers on group theory and examples applied to a 7x7x7 cube using an on-line app, are given in document CommutatorSubgroup.

I hope this may be of help.
 
Joined
Mar 21, 2006
Messages
113
Likes
0
Location
Kirksville, MO, USA
WCA
2005FERN01
YouTube
ravi12346
#8
True if we have even permutation in every orbital effected by the "total permutation".
If we don't have an even permutation in every orbit, then we aren't in the commutator subgroup. Commutators (and products of commutators) can only do even permutations, even if you restrict to a particular orbit (such as edges or corners on a 3x3). So the commutator subgroup G' is contained in the group H of operations that do even permutations on every orbit. But if we mod out orientations (which, as Lucas pointed out, are easy) then H/{orientations} = H_perm is just a direct product of alternating groups A_n (where n=8, 12, or 24, the sizes of the orbits). Then, as glazik pointed out, every element of A_n is a commutator, so everything in H_perm (and therefore H) should be a single commutator.

There's one catch, though: glazik's article only says that everything in A_n is a commutator of two elements of S_n, not necessarily of A_n. So it could be that some element of H_perm is a commutator of two permutations, but that one or both of these is an odd permutation on some orbit; this may give an impossible position of the NxNxN supercube. The question is: is every element of A_n (at least for n=8, 12, and 24) a commutator of two other elements of A_n?

Perhaps we can use E. Bertram's result from glazik's link (bottom of the first page) to prove this. If we set l = n-1 (which is odd for even n), then we get that every element of A_n can be written as a product of two l-cycles, and therefore as a commutator of one l-cycle (an even permutation) with some tau in S_n. But it may be that tau is an odd permutation--for example, (1234567) and (1234576) are conjugate in S_8, but only by the odd permutation (67). So we must instead use l = n-3. Then we can force tau to be an even permutation, so every element of A_n will be a commutator of two even permutations. The final problem is that in the case n=8, n-3 is less than the bound of 3n/4 required by Bertram. For this case, I went through all the possible cycle structures of permutations in A_8, and with a bit of permutation-matrix-multiplying dirty work from Mathematica, I believe I have found direct commutators for all of them. (Exercise for the reader?) Now let's go back up the chain of reasoning and see what we've proved:

- For n=8 or (from Bertram, using l = n-3) n>=12, every element of A_n is a commutator in A_n.
- Since H_perm is a direct product of groups A_n with n=8, 12, or 24, every element of H_perm is a commutator of elements in H_perm (and therefore in the NxNxN supercube group G).
- Since orientations are easy, every element of H is a commutator in G.
- Since all commutators in G belong to G' by definition of the commutator subgroup, and since G' is contained in H, it follows that {commutators} = G' = H.

Thus the commutator subgroup of the NxNxN supercube group is simply the set of operations that are even permutations on all orbits, and all such operations can be written as single commutators.

It's interesting to note, however, that a similar statement about commutator subgroups of more general groups is not true. Dummit and Foote's Abstract Algebra (page 180 in the third edition) gives a rather convoluted-looking group of order 96 in which one element belongs to the commutator subgroup despite not being a commutator of any two elements in the group.
 
Joined
Dec 11, 2009
Messages
294
Likes
0
#9
If we don't have an even permutation in every orbit, then we aren't in the commutator subgroup. Commutators (and products of commutators) can only do even permutations, even if you restrict to a particular orbit (such as edges or corners on a 3x3)...
Hmmm.

I think he meant to write [R U R2, R U2 R2]. The Sune is one of the most important algs in cubing, and it is curious that the alg itself can be written as a commutator (because it's not obvious at a glance).
See http://www.speedsolving.com/forum/showthread.php?5783-Math-Problem-12
 
Joined
Jun 17, 2006
Messages
654
Likes
1
Thread starter #12
There seems to be a confusion as to which sequence exactly is a sune: R' D' R D' R' D2 R or R' D' R D' R' D2 R D2.
Both permutations can be achieved be a singular commutator.

Per
 

Lucas Garron

Moderator
Staff member
Joined
Jul 6, 2007
Messages
3,554
Likes
86
Location
California
WCA
2006GARR01
YouTube
LucasGarron
#14
There seems to be a confusion as to which sequence exactly is a sune: R' D' R D' R' D2 R or R' D' R D' R' D2 R D2.
Both permutations can be achieved be a singular commutator.

Per
When a speedcuber is talking about a Sune, it's generally assumed that R U R' U R U2 R'. The inverse is an anti-Sune, and both algs have 48 symmetries, of which your former is one.
 
Joined
Mar 21, 2006
Messages
113
Likes
0
Location
Kirksville, MO, USA
WCA
2005FERN01
YouTube
ravi12346
#15
Then, as glazik pointed out, every element of A_n is a commutator, so everything in H_perm (and therefore H) should be a single commutator.
Wait, now I can't remember why I thought it follows that everything in H is a single commutator. Orientations are easy to write as products of commutators, and maybe even single commutators... but can they just be inserted into an existing permutation commutator? I'm too tired to make sense of this right now. It should at least still be true that H = G' and that everything in H_perm is a single commutator.
 
Joined
Sep 17, 2009
Messages
870
Likes
28
Location
New Orleans, LA
YouTube
4EverTrying
#16
The really nontrivial part would be to prove that 2 comms can actually be merged into one.
Do you mean that a composite commutator composed of two commutators has the same result as if the two commutators are performed one after the other in either order?

For example,
[U' L' U, R'] [U' M2 U2 M2 U2 U, R'] can be merged to

U' L' U
U' M2 U2 M2 U2 U
(R')
U' U2 M2 U2 M2 U
U' L U
(R)

= [U' L' U U' M2 U2 M2 U2 U, R'] = [U' L' M2 U2 M2 U', R'].

The restriction for this is, given a commutator [A, B] and a commutator [C, D], the two can definitely be merged if B = D and A does not affect pieces in C and vice versa. In addition, both A and C affect different pieces touched by the move(s) B = D.

In my example, A = U' L' U, B = R' = R' = D, and C = U' M2 U2 M2 U2 U.

Of course, the two commutators in my example affect two different piece types. You could merge two commutators which affect just corners, but I think one of the two commutators would need to be much longer than its counterpart so that it restores the portion of the cube affected by the first part of the other.
 

macky

Premium Member
Joined
Apr 4, 2006
Messages
402
Likes
4
Location
Stanford, CA
WCA
2003MAKI01
#17
cmowla, I didn't work out your example, but the question is whether or not it is possible to write the product of any two commutators as a single commutator. So we want to show either
(T) that the product of any two commutators can be written as a single commutator, or that
(F) some product of two commutators cannot be written out as a single commutator.
Your general approach merely shows one special case where merging is possible (by simple considerations, it seems); I'm sure you and others could come up with many more. But unless it suggests a general approach towards a constructive proof of (T), it does nothing to resolve our question.

And Per, I hope you realize that being good at FMC doesn't say much about being "brainy" on cube theory.
 
Last edited:
Joined
Jun 17, 2006
Messages
654
Likes
1
Thread starter #18
And Per, I hope you realize that being good at FMC doesn't say much about being "brainy" on cube theory.
Yes i know! I'm, still a bit uncertain how i would approach my own challenge.

Here are s few clues i would follow:
if 2 comms can always be combined into one, then so can any any number of comms. Proof by induction.

If we limit to one orbital it's not all that hard so see that an even permutation can be achieved by comms. Can we somehow "parallellize" the comm's first parts to schieve a general proof?? Hence combinig all orbitals involved.

I wish Jaap would come with some input :)

Per
 
Joined
Sep 17, 2009
Messages
870
Likes
28
Location
New Orleans, LA
YouTube
4EverTrying
#19
cmowla, I didn't work out your example, but the question is whether or not it is possible to write the product of any two commutators as a single commutator.
I don't see why this would be necessary to prove that any even permutation can be written as a single commutator because my approach doesn't limit the length of the commutators combined (and hence the two commutators could theoretically cover every permutation when combined). There many commutators which cause the same permutation of pieces as other commutators but are obviously composed of different moves.

If you look at my definition, isn't that what is meant by merging commutators? In what other combination can two commutators be merged into one, besides the trivial case when the same exact commutator is applied to more than one orbit of wings or big cube center pieces?

If my approach does not apply to your definition of merging two commutators into one commutator, please define what you think that means. If you cannot define it, then how can anyone prove or disprove it? ;)

I'm sure you and others could come up with many more.
Sure, anyone who can follow my definition can come up with more examples.
 
Last edited:

macky

Premium Member
Joined
Apr 4, 2006
Messages
402
Likes
4
Location
Stanford, CA
WCA
2003MAKI01
#20
[edit] Ravi, I haven't ignored your post.

I don't see why this would be necessary to prove that any even permutation can be written as a single commutator because my approach doesn't limit the length of the commutators combined (and hence the two commutators could theoretically cover every permutation when combined). There many commutators which cause the same permutation of pieces as other commutators but are obviously composed of different moves.
You're correct. But I was answering your question
TMOY said:
The really nontrivial part would be to prove that 2 comms can actually be merged into one.
Do you mean that a composite commutator composed of two commutators has the same result as if the two commutators are performed one after the other in either order?
because it wasn't clear to me from this that you understood what TMOY said.

"Merging," as TMOY or whoever first used it used it, means writing some [A, B][C, D] in the form [E, F] for some E and F. You didn't define anything; you gave one set of conditions (B = D etc) under which merging is possible, as [A, B][C, B] = [AC, B].

cmowla said:
If you look at my definition, isn't that what is meant by merging commutators? In what other combination can two commutators be merged into one, besides the trivial case when the same exact commutator is applied to more than one orbit of wings or big cube center pieces?
That's part of TMOY's question. In fact, if you can find even one product of two commutators that cannot be merged (provably, not just because the obvious methods don't work or "according my experience and theory"), then that's an even permutation that cannot be written as a single commutator and a counterexample to Per's question.

But ok, you seem to be trying to answer Per's question directly without inducting, by writing any even permutation first in the specific form you brought up, as [A, B][C, B] with A, B, C satisfying certain conditions. Your example does not seem to indicate a general approach for doing this. Maybe you can; you've certainly worked more closely with commutators than most cubers (including me). Which is why I hope that you in particular understand the obvious reductions suggested in the first posts, so that you can put your intuition to best use.
 
Last edited:
Top