My ultimate commutator challenge

Discussion in 'Puzzle Theory' started by mrCage, Jun 2, 2011.

Welcome to the Speedsolving.com. You are currently viewing our boards as a guest which gives you limited access to join discussions and access our other features. By joining our free community of over 30,000 people, you will have access to post topics, communicate privately with other members (PM), respond to polls, upload content and access many other special features. Registration is fast, simple and absolutely free so please, join our community today!

If you have any problems with the registration process or your account login, please contact us and we'll help you get started. We look forward to seeing you on the forums!

Already a member? Login to stop seeing this message.
  1. mrCage

    mrCage Member

    654
    0
    Jun 17, 2006
    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
     
  2. Lucas Garron

    Lucas Garron Super-Duper Moderator Staff Member

    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).
     
  3. mrCage

    mrCage Member

    654
    0
    Jun 17, 2006
    Elaborate. I fail to see the triviality...

    Per
     
  4. Lucas Garron

    Lucas Garron Super-Duper Moderator Staff Member

    EP, CP: Generated by 3-cycles. Easy with commutators.
    EO, CO: Orient two at a time using commutators. Also easy.
     
  5. TMOY

    TMOY Member

    1,802
    0
    Jun 29, 2008
    WCA:
    2008COUR01
    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.
     
  6. mrCage

    mrCage Member

    654
    0
    Jun 17, 2006
    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
     
  7. glazik

    glazik Member

    1
    0
    Jun 8, 2011
    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.
     
  8. Ravi

    Ravi Member

    113
    0
    Mar 21, 2006
    Kirksville, MO, USA
    WCA:
    2005FERN01
    YouTube:
    ravi12346
    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.
     
  9. reThinking the Cube

    reThinking the Cube Member

    294
    0
    Dec 11, 2009
    Hmmm.

     
  10. Kirjava

    Kirjava Colourful

    6,129
    4
    Mar 26, 2006
    WCA:
    2006BARL01
    YouTube:
    snkenjoi
    reThinking the Cube; are you implying that the Sune produces an odd number of swaps in each orbit?
     
  11. reThinking the Cube

    reThinking the Cube Member

    294
    0
    Dec 11, 2009
    NO, and that also implies that Sune+U cannot be written as a direct commutator, but Sune+U2 can.
     
  12. mrCage

    mrCage Member

    654
    0
    Jun 17, 2006
    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
     
  13. Kirjava

    Kirjava Colourful

    6,129
    4
    Mar 26, 2006
    WCA:
    2006BARL01
    YouTube:
    snkenjoi
    Might be worth elaborating on what you mean in the future then. If your post just consists of two quotes by other people it's quite difficult to understand what you're going on about.
     
  14. Lucas Garron

    Lucas Garron Super-Duper Moderator Staff Member

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

    Ravi Member

    113
    0
    Mar 21, 2006
    Kirksville, MO, USA
    WCA:
    2005FERN01
    YouTube:
    ravi12346
    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.
     
  16. Christopher Mowla

    Christopher Mowla Premium Member

    828
    2
    Sep 17, 2009
    New Orleans, LA
    YouTube:
    4EverTrying
    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.
     
  17. macky

    macky Premium Member

    400
    0
    Apr 4, 2006
    Stanford, CA
    WCA:
    2003MAKI01
    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: Sep 15, 2011
  18. mrCage

    mrCage Member

    654
    0
    Jun 17, 2006
    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
     
  19. Christopher Mowla

    Christopher Mowla Premium Member

    828
    2
    Sep 17, 2009
    New Orleans, LA
    YouTube:
    4EverTrying
    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? ;)

    Sure, anyone who can follow my definition can come up with more examples.
     
    Last edited: Sep 15, 2011
  20. macky

    macky Premium Member

    400
    0
    Apr 4, 2006
    Stanford, CA
    WCA:
    2003MAKI01
    [edit] Ravi, I haven't ignored your post.

    You're correct. But I was answering your question
    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].

    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: Sep 16, 2011

Share This Page