whauk
Member
the question i will discuss here is the following:
for a (random) given permutation A, does there exist a permutation B with B A B'=A' (which is equivalent to B A B' A= id)? or in other words: can you invert any permutation by conjugation?
i start by discussing the problem in the symmetric group and will try to expand the results to the cube group. so for understanding this article it might be helpful to know a little bit about group theory and also cycle notation will be used to describe permutations. and as always: id = () = identity = cycle of nothing and € means "element of a set".
motivation (this can be skipped without missing relevant information):
as we all know R U R' U R U2 R' L' U' L U L' U2 L twists two corners on the cube. as linus discovered this one R U2 R' L' U' L U' R U' R' L' U2 L U also twists two corners but is not reached by setup-moves from the original algorithm. however it seems to be very similar and becomes a conjugate of the original alg if you replace the bold part by L' U2 L R U R' which does the same thing. so: R U' R' L' U2 L=L' U2 L R U R'. with A=R U' R' and B=L' U2 L the equality simplifies to AB=B'A' and this is equivalent to BAB'=A'. so it might be possible to simplify/modify algorithms if you find a B for A such that BAB'=A'. this might not work very often but the question became so interesting that i started thinking about it seriously.
theoretical approach:
any permutation can be written as a disjunct cycle of stickers. we will consider those cycles as elements of a symmetric group. so lets look at one of these cycles, namely (1 2 ... n):=A first:
there is an obvious B with the property BAB'=A' because the "mirror" of the cycle does what we want. so set M as M:=(1 n) (2 n-1) (3 n-2).... in general M(i)=n+1-i for every i between 1 and n. it is very easy to verify that this works so i don't feel like writing it down. probably this image helps you to understand how it works:
take a polygon with n corners labeled 1 ... n in clockwise direction. the cycle (1 2 ... n) represented on the polygon is a rotation by one corner in clockwise direction. if you mirror the polygon first ("flipping the paper it is drawn on") rotate it clockwise and flip the paper over again it will result in being turned counterclockwise which occurs to be the inverse of turning to the right.
to keep it as general as possible we notice that if C and D are in the commutator group of A (the subgroup of all elements that commute with A (=> also with A')) CMD:=B has the same property BAB'=A' since BAB' = CMDA(CMD)' = CMDAD'M'C' = CMDD'AM'C' = CMAM'C' = CA'C' = CC'A' = A'.
remark: i am not sure whether there are even more elements in the group with the desired property. i couldn't find any and tried to prove that there are none but i didn't succeed. if you have an answer let me know
also the set {B | B = CMD for M is mirror of A and C,D commute with A} seems very strange to me. its like the left coset of a right coset?! did you ever encounter such a structure? does it have a name or any cool properties?
for now we have only looked at one cycle. however if you are confronted with a permutation consisting of the cycles A1,...,Am you can just find Bi for every Ai (that doesn't disturb Aj with i≠j) and B1...Bm will do the job.
applying the theoretical results on the cube (edges):
stickers on the same piece always stay on the same piece so they actually do not move around freely. (therefore a possible B might actually not exist with the restriction that stickers must stay on their piece) the funny thing is that our theoretical works perfectly out for arbitrary edge permutations.
if the edge-cycle is "pure" (the sticker-cycle does not hit a piece twice. so no edge in the cycle is additionally "flipped") we can replace "stickers" with "pieces" and the restriction does not longer bother us. (example: A= (UR UF UL), => B=S2 D2 S2 which is just the mirror)
if not (the cycle is not pure) things get a little more complicated but it still works:
so k edges are cycled and the sticker cycle can be written as (1 2 ... 2k):=A. i hope this makes sense to everyone. at k the cycle reaches its original edge but on the "other sticker", then proceeds on the "other stickers" of each edge and reaches its original position at 2k. therefore two stickers are on the same edge if and only if their distance is k in the cycle which also defines our restriction.
the mirroring M applied on stickers gives: M(i)=2k+1-i and M(i+k)=2k+1-i-k=k+1-i. => M(i)-M(i+k)=2k+1-i-(k+1-i)=k which means that stickers on the same edge (they have difference k) still have difference k after applying M. so in fact M exists as a permutation of edge pieces (before we only knew it existed as a permutation of stickers which might not be doable on a cube).
and on corners:
this very satisfying conclusion does not work with non-pure corner permutations. (you would have to replace 2k with 3k and everything gets weird).
i actually found a proof that for A given by U' L' U F2 U' L U2 L' F2 L F2 U' F2 (basically a corner 3-cycle and two twisted corners, one in the 3-cycle, the other one not. this was the easiest example of what doesn't work with the standard method. (later i found that a 3-corner twist is a much more obvious counterexample. however i still think its interesting to know that this one doesn't work either)) no B with the desired property exists. i will only provide a sketch as i do not feel writing it all out correctly:
lets first assume B exists. there are two cases:
1. the solely twisted corner (DFL) is not moved into the 3-cycle by B (or B'). the corner must be solved again by BAB'A. but A doesn't affect the corner's permutation => the permutation of our corner after BAB'A is already given by BB'=id and this also means that the corner orientation is given only by AA. we know that A twists the corner once and two corner twists will not solve it again. => BAB'A is not id in this case.
2. B makes the corner (DFL) interact with corners in the 3-cycle. in this case consider only the corner permutation. A can then be written as (1 2 3) and B is a permutation that has 1 and/or 2 and/or 3 and sth else in the same cycle.
i will now look on what is happening in detail when applying BAB'A to the cube which should be the identity.
without loss of generality lets assume that applying B makes the DFL corner go to 1 (an arbitrary corner in the 3-cycle that i name 1). applying A then makes this corner go to 2 and after another B' it has to go back to DFL because the permutation of this corner is A-invariant. so this means B(DFL)=1 and B'(2)=DFL. this is equivalent to B(DFL)=1 and B(DFL)=2 which cannot be possible.
as we have covered all possibilities for B and none of them has the desired property of BAB'A=id we know that B cannot exist. therefore the permutation given by U' L' U F2 U' L U2 L' F2 L F2 U' F2 is indeed one that cannot by inverted by conjugation.
Conclusion:
i believe that any permutation of the cube that has only pure corner cycles and as many corners twisted in spot clockwise as counterclockwise can be inverted by conjugation. (heuristic explanation: two corners twisted in different directions need a swap of themselves as setup move (so it works). furthermore i think the length and number of unpure corner cycles doesn't change much from the above counterexample and it still doesn't work. aaaaand finally i think in the case A where you would need a setup move M that violates the permutation laws of the cube you can consider the group <R,U,L,F,B,D,two-edge-swap> and you will find "enough" elements C,D there such that a B€{B | B = CMD for M is mirror of A and C,D commute with A} lies in the cube group.) or in other words: i think you do not get problems because of the fact that you cannot swap only two pieces on a cube.
this is what i guess is true! finding a proof for everything i claimed in the last paragraph would probably result in disastrous case differentiations and the only people you would like to read it might be your mortal enemies. if you find something out let me know about your results.
i hope you found the question (and answer) an interesting-to-discuss problem and hope you understand everything (as i tried to make it as easy to read as possible). however if anything is unclear, dont hesitate to ask me
edit:
TLDR version: the answer is no.
for a (random) given permutation A, does there exist a permutation B with B A B'=A' (which is equivalent to B A B' A= id)? or in other words: can you invert any permutation by conjugation?
i start by discussing the problem in the symmetric group and will try to expand the results to the cube group. so for understanding this article it might be helpful to know a little bit about group theory and also cycle notation will be used to describe permutations. and as always: id = () = identity = cycle of nothing and € means "element of a set".
motivation (this can be skipped without missing relevant information):
as we all know R U R' U R U2 R' L' U' L U L' U2 L twists two corners on the cube. as linus discovered this one R U2 R' L' U' L U' R U' R' L' U2 L U also twists two corners but is not reached by setup-moves from the original algorithm. however it seems to be very similar and becomes a conjugate of the original alg if you replace the bold part by L' U2 L R U R' which does the same thing. so: R U' R' L' U2 L=L' U2 L R U R'. with A=R U' R' and B=L' U2 L the equality simplifies to AB=B'A' and this is equivalent to BAB'=A'. so it might be possible to simplify/modify algorithms if you find a B for A such that BAB'=A'. this might not work very often but the question became so interesting that i started thinking about it seriously.
theoretical approach:
any permutation can be written as a disjunct cycle of stickers. we will consider those cycles as elements of a symmetric group. so lets look at one of these cycles, namely (1 2 ... n):=A first:
there is an obvious B with the property BAB'=A' because the "mirror" of the cycle does what we want. so set M as M:=(1 n) (2 n-1) (3 n-2).... in general M(i)=n+1-i for every i between 1 and n. it is very easy to verify that this works so i don't feel like writing it down. probably this image helps you to understand how it works:
take a polygon with n corners labeled 1 ... n in clockwise direction. the cycle (1 2 ... n) represented on the polygon is a rotation by one corner in clockwise direction. if you mirror the polygon first ("flipping the paper it is drawn on") rotate it clockwise and flip the paper over again it will result in being turned counterclockwise which occurs to be the inverse of turning to the right.
to keep it as general as possible we notice that if C and D are in the commutator group of A (the subgroup of all elements that commute with A (=> also with A')) CMD:=B has the same property BAB'=A' since BAB' = CMDA(CMD)' = CMDAD'M'C' = CMDD'AM'C' = CMAM'C' = CA'C' = CC'A' = A'.
remark: i am not sure whether there are even more elements in the group with the desired property. i couldn't find any and tried to prove that there are none but i didn't succeed. if you have an answer let me know
also the set {B | B = CMD for M is mirror of A and C,D commute with A} seems very strange to me. its like the left coset of a right coset?! did you ever encounter such a structure? does it have a name or any cool properties?
for now we have only looked at one cycle. however if you are confronted with a permutation consisting of the cycles A1,...,Am you can just find Bi for every Ai (that doesn't disturb Aj with i≠j) and B1...Bm will do the job.
applying the theoretical results on the cube (edges):
stickers on the same piece always stay on the same piece so they actually do not move around freely. (therefore a possible B might actually not exist with the restriction that stickers must stay on their piece) the funny thing is that our theoretical works perfectly out for arbitrary edge permutations.
if the edge-cycle is "pure" (the sticker-cycle does not hit a piece twice. so no edge in the cycle is additionally "flipped") we can replace "stickers" with "pieces" and the restriction does not longer bother us. (example: A= (UR UF UL), => B=S2 D2 S2 which is just the mirror)
if not (the cycle is not pure) things get a little more complicated but it still works:
so k edges are cycled and the sticker cycle can be written as (1 2 ... 2k):=A. i hope this makes sense to everyone. at k the cycle reaches its original edge but on the "other sticker", then proceeds on the "other stickers" of each edge and reaches its original position at 2k. therefore two stickers are on the same edge if and only if their distance is k in the cycle which also defines our restriction.
the mirroring M applied on stickers gives: M(i)=2k+1-i and M(i+k)=2k+1-i-k=k+1-i. => M(i)-M(i+k)=2k+1-i-(k+1-i)=k which means that stickers on the same edge (they have difference k) still have difference k after applying M. so in fact M exists as a permutation of edge pieces (before we only knew it existed as a permutation of stickers which might not be doable on a cube).
and on corners:
this very satisfying conclusion does not work with non-pure corner permutations. (you would have to replace 2k with 3k and everything gets weird).
i actually found a proof that for A given by U' L' U F2 U' L U2 L' F2 L F2 U' F2 (basically a corner 3-cycle and two twisted corners, one in the 3-cycle, the other one not. this was the easiest example of what doesn't work with the standard method. (later i found that a 3-corner twist is a much more obvious counterexample. however i still think its interesting to know that this one doesn't work either)) no B with the desired property exists. i will only provide a sketch as i do not feel writing it all out correctly:
lets first assume B exists. there are two cases:
1. the solely twisted corner (DFL) is not moved into the 3-cycle by B (or B'). the corner must be solved again by BAB'A. but A doesn't affect the corner's permutation => the permutation of our corner after BAB'A is already given by BB'=id and this also means that the corner orientation is given only by AA. we know that A twists the corner once and two corner twists will not solve it again. => BAB'A is not id in this case.
2. B makes the corner (DFL) interact with corners in the 3-cycle. in this case consider only the corner permutation. A can then be written as (1 2 3) and B is a permutation that has 1 and/or 2 and/or 3 and sth else in the same cycle.
i will now look on what is happening in detail when applying BAB'A to the cube which should be the identity.
without loss of generality lets assume that applying B makes the DFL corner go to 1 (an arbitrary corner in the 3-cycle that i name 1). applying A then makes this corner go to 2 and after another B' it has to go back to DFL because the permutation of this corner is A-invariant. so this means B(DFL)=1 and B'(2)=DFL. this is equivalent to B(DFL)=1 and B(DFL)=2 which cannot be possible.
as we have covered all possibilities for B and none of them has the desired property of BAB'A=id we know that B cannot exist. therefore the permutation given by U' L' U F2 U' L U2 L' F2 L F2 U' F2 is indeed one that cannot by inverted by conjugation.
Conclusion:
i believe that any permutation of the cube that has only pure corner cycles and as many corners twisted in spot clockwise as counterclockwise can be inverted by conjugation. (heuristic explanation: two corners twisted in different directions need a swap of themselves as setup move (so it works). furthermore i think the length and number of unpure corner cycles doesn't change much from the above counterexample and it still doesn't work. aaaaand finally i think in the case A where you would need a setup move M that violates the permutation laws of the cube you can consider the group <R,U,L,F,B,D,two-edge-swap> and you will find "enough" elements C,D there such that a B€{B | B = CMD for M is mirror of A and C,D commute with A} lies in the cube group.) or in other words: i think you do not get problems because of the fact that you cannot swap only two pieces on a cube.
this is what i guess is true! finding a proof for everything i claimed in the last paragraph would probably result in disastrous case differentiations and the only people you would like to read it might be your mortal enemies. if you find something out let me know about your results.
i hope you found the question (and answer) an interesting-to-discuss problem and hope you understand everything (as i tried to make it as easy to read as possible). however if anything is unclear, dont hesitate to ask me
edit:
TLDR version: the answer is no.
Last edited: