Page 1 of 9 1 2 3 ... LastLast
Results 1 to 10 of 85

Thread: My ultimate commutator challenge

  1. #1
    Member mrCage's Avatar
    Join Date
    Jun 2006
    Posts
    653

    Default My ultimate commutator challenge

    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. #2
    Super-Duper Moderator Lucas Garron's Avatar
    Join Date
    Jul 2007
    Location
    Where the rolling foothills rise
    WCA Profile
    2006GARR01
    YouTube
    LucasGarron
    Posts
    3,192

    Default

    Quote Originally Posted by mrCage View Post
    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).
    garron.us | cubing.net | twisty.js | ACube.js | Mark 2 | Regs | Show people your algs: alg.cubing.net | Cube on your smartphone! cubing.net/touch

  3. #3
    Member mrCage's Avatar
    Join Date
    Jun 2006
    Posts
    653

    Default

    Quote Originally Posted by Lucas Garron View Post
    Well, the first part is pretty trivial to see with some cubing intuition, especially since most of this relies on 3-cycles.
    Elaborate. I fail to see the triviality...

    Per

  4. #4
    Super-Duper Moderator Lucas Garron's Avatar
    Join Date
    Jul 2007
    Location
    Where the rolling foothills rise
    WCA Profile
    2006GARR01
    YouTube
    LucasGarron
    Posts
    3,192

    Default

    Quote Originally Posted by mrCage View Post
    Elaborate. I fail to see the triviality...

    Per
    EP, CP: Generated by 3-cycles. Easy with commutators.
    EO, CO: Orient two at a time using commutators. Also easy.
    garron.us | cubing.net | twisty.js | ACube.js | Mark 2 | Regs | Show people your algs: alg.cubing.net | Cube on your smartphone! cubing.net/touch

  5. #5
    Member
    Join Date
    Jun 2008
    WCA Profile
    2008COUR01
    Posts
    1,653

    Default

    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. #6
    Member mrCage's Avatar
    Join Date
    Jun 2006
    Posts
    653

    Default

    Quote Originally Posted by Lucas Garron View Post
    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

  7. #7
    Member
    Join Date
    Jun 2011
    Posts
    1

    Default

    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. #8
    Member Ravi's Avatar
    Join Date
    Mar 2006
    Location
    Kirksville, MO, USA
    WCA Profile
    2005FERN01
    YouTube
    ravi12346
    Posts
    113

    Default

    Quote Originally Posted by mrCage View Post
    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.

  9. #9
    Member reThinking the Cube's Avatar
    Join Date
    Dec 2009
    Posts
    295

    Default

    Quote Originally Posted by Ravi View Post
    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.

    Quote Originally Posted by Lucas Garron View Post
    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/sh...ath-Problem-12
    "Only fools would argue tuning, with an ape that plays the pitchpipe" -- reThinkerô

  10. #10
    Colourful Kirjava's Avatar
    Join Date
    Mar 2006
    WCA Profile
    2006BARL01
    YouTube
    snkenjoi
    Posts
    6,007

    Default

    reThinking the Cube; are you implying that the Sune produces an odd number of swaps in each orbit?

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •