2013-04-09T19:47:59Z

Dave3457: Dave3457 uploaded a new version of "File:COMM Effects Twist Corn.png": color change

Summary to come

Dave3457: This JPG image was created for the speedsolving.com wiki page Commutators (www.speedsolving.com/wiki/index.php/Commutator) . It is an example that helps understand the terms J, K, N, NA’,NB’ used to describe how the commutator works. It is PNG ve...

This JPG image was created for the speedsolving.com wiki page Commutators (www.speedsolving.com/wiki/index.php/Commutator) . It is an example that helps understand the terms J, K, N, NA’,NB’ used to describe how the commutator works.

It is PNG version of a SVG image. (Presently (2013 04 10) the Wiki does not support SVG images)
It was created using the free opensource program Inkscape. If there is an error or something needs to be changed contact Dave3457.

Colors used
White: 5% Grey F2F2F2 (242,242,242)
Red: BB0000 (187,0,0) L=94
Blue: 000077 (0, 0, 119) L=60
Green: 005500 (0,85,0) L=43
Orange: DD6000 (255,68,0) L=128
Yellow: FFCC00 (255,204,0) L=128 (same)
Light grey: 808080 (128,128,128) L=128
Dark grey: 404040 (64,64,64) L=64

File:COMM Effects section Definitions.png

2013-04-08T18:03:59Z

Dave3457: This image was created for the speedsolving.com wiki page Commutators (www.speedsolving.com/wiki/index.php/Commutator) . It defines the terms J, K, N, NA’,NB’ used to describe how the commutator works. It is PNG version of a SVG image. (Presently...

Rubik's Cube Group

2013-04-03T22:19:12Z

Dave3457: added link group

The Rubik's Cube group is a [[wikipedia:group|group]] of order 43,252,003,274,489,856,000, and represents the states of the [[3x3x3|3x3x3 Rubik's Cube]].

As every group can be represented as a subgroup of a permutation group, the Rubik's Cube group can be represented as a subgroup of the permutations of its stickers.

The diameter of the Rubik's Cube group is known as [[God's Number]] for 3x3x3.

[http://games.groups.yahoo.com/group/speedsolvingrubikscube/message/41594 Macky explaining some things].

== See also ==
* [http://en.wikipedia.org/wiki/Rubik's_cube_group Wikipedia entry on the Rubik's Cube Group]
* [[Thistlethwaite Algorithm]]

[[Category:Puzzle theory]]

Commutator

2013-04-03T22:10:47Z

Dave3457: added word..one

A '''commutator''' is a sequence of moves that consists in doing a sequence A, then a sequence B, then the inverse of the sequence A and finally the inverse of the sequence B. As a result, only specific pieces are affected. It allows one to finish the cube without disturbing pieces that are already in place.

== Mathematical definition ==

Given a group, a '''commutator''' is an element of the form ghg'h' (also denoted [g, h]), where g and h are elements of the group with inverses g' and h'.

Cube notation is very close: A B A' B' = [A, B]

== Fundamental principle ==

It is straightforward that A A' does nothing, as well as B B', because A' is the inverse of A and B' the inverse of B.

So the commutator A B A' B' does change something only because B A' is not the same as A' B. When B A' = A' B, or B A = A B, we say that the elements A and B commute. In this case, A B A' B' = A (B A') B' = A (A' B) B' = I where I is the identity.

For example for L and R or U and D. In this case, the commutator does nothing:
L R L' R' = L L' R R' = I

So in some way, the commutator allows you to measure to which extent the moves do not commute.

== Effect ==

The sequence A changes a set of pieces located at some locations '''J''' on the cube. The sequence B affects some locations '''K'''. If '''J''' and '''K''' have no intersection, then A and B commute, and the commutator does nothing (for example [L, R]). Otherwise, '''J''' and '''K''' have an intersection '''N'''.

Pieces that are brought into the intersection by A are '''N'''A' (apply the inverse of A to the locations '''N'''). Pieces that are brought into the intersection by B are '''N'''B'.

The pieces that are affected by the commutator [A, B] = A B A' B' are located in the union of '''N''', '''N'''A' and '''N'''B'. In other words, pieces that are affected by a commutator are those who are at the intersection of both moves, or are brought into the intersection by A or B. Other pieces, even if they are temporarily mixed up by A and B, will be put back at their original location with A' and B'.

=== Trivial case ===

When '''J''' and '''K''' have an empty intersection, A and B commute, so the commutator does nothing.

=== B inplace ===

If '''N'''B' = '''N''', the sequence B only moves affected pieces that are inside the intersection. It may also move pieces that are outside the intersection, but those moves will be cancelled at the end. Affected pieces will only be '''N''' and '''N'''A'. So those pieces will be in '''J''', i.e. among pieces that are directly affected by A.

In this case, it is relevant to consider that [A, B] = (A B A') B' = [A: B] B'. First part is the [[conjugate]] of B by A, and second part is the inverse of B.

If [A: B] and B' interfere, there is a quirk part PQ (see general case).

==== Examples ====
Let's consider [M', U2] = M' U2 M U2

In this example, '''N''' are the top-front and top-back edges. '''N'''B' is '''N'''U2, which is exactly '''N''', and '''N'''A' are front-bottom and front-top edges. So affected pieces are top-back, top-front, and front-bottom edges, which are directly affected by M and M'. In other words, affected pieces are in the middle slice.

The conjugated move is U2. Because only middle slice pieces are changed at the end, we can safe ignore top-left and top-right pieces. The relevant part of U2 is just a swap of top-back and top-front edges. Thus, M' U2 M swaps front-top and front-bottom edges.

So [M', U2] can be understood as: swap front-top and front-bottom edges, then swap top-back and top-front edges, which yields a 3-cycle of edges.

There is a quirk part, the front-bottom edge, which is affected by both [M': U2] and U2, i.e. by all four moves of the commutator.

Let's consider [M2, U2] = M2 U2 M2 U2

Again, '''N''' are the top-front and top-back edges. But there is no more interference between [M': U2] and U2, thus no quirk part. Simply, top-front and top-back edges are swapped, as well as bottom-front and bottom-back edges.

=== A inplace ===

This is a symmetrical case. Affected pieces will only be '''N''' and '''N'''B'. So those pieces will be in '''K''', i.e. among pieces that are directly affected by B.

In this case, it is relevant to consider that [A, B] = A (B A' B') = A [B: A']. First part is A and second part is the [[conjugate]] of A' by B.

==== Examples ====

Let's consider the inverse of [M', U2] which is (M' U2 M U2)' = U2 M' U2 M = [U2, M'] = U2 [M': U2]. The relevant part of U2 consists in swapping top-back and top-front edges, and [M': U2] swaps top-front and front-bottom edges.

Other examples:
* A = "rotating a corner" like [R' D' R D R' D' R, U]
* A = "flipping an edge" like [R' E' R2 E2 R', U]
* A = "exchanging two corners" like [R' L' D2 R L, U]
* A = "exchanging two edges" like [M2 D2 M2, U]

=== Three different sets ===

When '''N'''A' and '''N'''B' are not included in '''N''', there are three sets involved in the commutator:
* '''N'''A' : pieces that are brought into the intersection by A
* '''N'''B' : pieces that are brought into the intersection by B
* '''N''' : the intersection of '''J''' and '''K''', i.e. where A and B interfere.

Note that '''N'''A' can have locations in common with '''N''' and '''N'''B' can have locations in common with '''N'''. In other words, it is possible that a sequence (A or B) does two different things in the context of a commutator:
# moving pieces inside the intersection (from '''N''' to '''N''')
# bringing pieces into the intersection (from '''N'''A' \ '''N''' to '''N''' or from '''N'''B' \ '''N''' to '''N''')

When there is only case 1, it is in fact the cases studied before. So we are left with those possible cases:
* Case 2 only: the three sets '''N'''A', '''N'''B' and '''N''' are completely separated (no overlap)
* Case 1 and 2 at the same time: the three sets overlap

==== No overlap ====

Referring to the animation below, when sets do not overlap, the commutator can be summed up by:
* A stores the content of the intersection PN in '''N'''A, and replace it with some pieces PA from '''N'''A'
* B stores PA in '''N'''B, and bring some pieces PB from '''N'''B' into the intersection
* A' retrieves PB from the intersection and places them in '''N'''A', and brings to the intersection previously stored pieces PN in '''N'''A
* B' retrieves PN from the intersection and places them in '''N'''B', and finally places PA in the intersection.

So it is a 3-cycle of (PN, PA, PB) into (PA, PB, PN)

We notice that '''N'''A and '''N'''B are used as temporary storage:
* The content of the intersection, PN, is first hidden by A in its storage '''N'''A, and comes back with A', so that the only transformation applied to these pieces is B'.
* The content of '''N'''A' is brought by A, and is then hidden by B in '''N'''B, so that the only transformation applied to these pieces is A.
* The content of '''N'''B' is brought by B, and then is placed immediately in '''N'''A' by A'. So the transformation applied to these pieces is B A'.

Note that '''N'''A may or may not overlap with '''N'''A', and '''N'''B may or may not overlap with '''N'''B', but that it does not have any implication, except that the location where the pieces come from can also be the location where they are temporarily stored. The most obvious case is when '''N'''A equals to '''N'''A', or '''N'''B equals to '''N'''B', which means that pieces of the intersection '''N''' are swapped with pieces of '''N'''A' or '''N'''B', as in [R2, F2]

In other words, all the commutator does is:
* PA goes A
* PB goes B A'
* PN goes B'
[[File:Break down of Commutator A B A B If there is no overlap.gif]]

===== Examples =====

* [R' E2 R, U'] is a 3-cycle of edges, where PA is the back-left edge, PB is the top-front edge and PN is the top-right edge.
* [R' D' R, U'] is a 3-cycle of corners

==== Overlap ====

This is the most complex case, because it is like the "no overlap" case, but with additional interferences.

===== Safe part =====

Some pieces in the intersection '''N''' are hidden in a storage, thus protecting them from being scrambled by the interference due to the overlap.

Let's call '''H'''B the location of pieces hidden by B:

'''H'''B = (('''N'''B) \ '''N''') B'

Similarly, pieces are hidden by A:

'''H'''A = (('''N'''A) \ '''N''') A'

We will also use pieces that are hidden by A' so that they are not affected by B':

'''H'''A' = (('''N'''A') \ '''N''') A

In order to get the same results as in the "no overlap" case, we will redefine the set of pieces:
* PA will be pieces that are brought into '''H'''B by A, i.e. pieces that are at the beginning in '''H'''BA'. This set may overlap with the intersection '''N'''.
* PB will be pieces that are brought into '''H'''A' by B, i.e. pieces that are at the beginning in '''H'''A'B' \ '''N'''
* PN will be pieces that are hidden by A, which are at the beggining in '''H'''A.

We get the same result as before:
* PA goes A
* PB goes B A'
* PN goes B'

====== Example ======

Let's consider [R', F]. The intersection '''N''' is the front-right column (containing the front-right-top corner, the front-right-bottom corner and the front-right edge).

'''H'''B = (('''N'''B) \ '''N''') B' = (('''N'''F) \ '''N''') F'
which is the set of locations containing the front-right edge and the front-right-bottom corner.

So PA are front-right-top corner and top-right edge.

'''H'''A = (('''N'''A) \ '''N''') A' = (('''N'''R') \ '''N''') R

So PN are front-right edge and front-right-bottom corner.

'''H'''A' = (('''N'''A') \ '''N''') A = (('''N'''R) \ '''N''') R'
which is the set of locations containing the front-right-top corner and the front-right edge.

PB are pieces at '''H'''A'B, i.e. front-top edge and front-top-left corner.

So the safe part of [R', F] is similar to a 3-cycle pairs, but is clearly not a 3-cycle of pairs.
* PA goes R', thus replacing PN
* PN goes F, thus replaces a part of PA and a part of PB
* PB goes FR, thus replacing a part of PA and the top-right-back corner (the quirk part '''Q''')
* the top-right-back corner is affected by all moves, R'FRF' = [R': F] F' equivalent to UF', or R'FRF' = R' [F: R] equivalent to R'U, thus going to the top-front-right position, replacing a part of PB

The quirkiness is that the locations of those pairs overlap, and that an extra location is used, the top-right-back corner. Pieces that are initially in this location are moved according a special scheme (see below).

In this example, the top-right-back corner goes to the top-front-right position, thus being separated from the edges around it.

===== Quirk and conjugated part =====

Some pieces are outside of the pseudo 3-cycle and never hidden. Let's call their starting location the quirk part '''Q'''.

'''Q''' = ('''H'''A' \ '''H'''B) A'

Those pieces PQ are never hidden, thus being affected by all moves of the commutator:
* PQ goes A B A' B'

Some pieces are outside of the pseudo 3-cycle, but are hidden by A or B at some point. So they are [[conjugate|conjugated]]. Let's call them PC and their starting location '''C'''.

'''C''' = ('''J''' union '''K''') \ ('''H'''A union '''H'''BA' union '''H'''A'B union '''Q''')

In the overlap case, either '''Q''' or '''C''' is non empty, so there are at least 4 sets of pieces: PA, PB, PN and PQ or PC.

In complex cases, there may be five sets with both PQ and PC.

The quirk part and the conjugated part are used as final locations for pieces that go outside of the pseudo 3-cycle.

====== Example ======

Let's consider [R', F']

'''H'''A is the front-right edge and the front-right-bottom corner. So PN is the set of pieces at these locations.

'''H'''B is the front-right edge and the front-right-top corner. So PA is the top-right edge and the top-right-back corner.

'''H'''A' is the front-right edge and the front-right-top corner. So PB is the front-bottom edge only.

The quirk part is :
'''Q''' = ('''H'''A' \ '''H'''B) A' = empty

The conjugated part is :

'''C''' = ('''J''' union '''K''') \ ('''H'''A union '''H'''BA' union '''H'''A'B union '''Q''') = front-right-top corner and front-bottom-left corner

The front-right-top is affected by R'F'R so it is equivalent to x'F'x which is U'.

The front-bottom-left is affected by F'RF so it is equivalent to z'Rz whichi is D.

So this move does :
* PN, i.e. front-right edge and front-right-bottom corner, goes F
* PA, i.e. top-right edge and top-right-back corner, goes R'
* PB, i.e. front-bottom edge, goes F'R
* the front-right-top corner goes U'
* the front-bottom-left goes D

== General case ==

Pieces can be affected by one, two, three of four elements of the sequence A B A' B'. The gives use the different sets of pieces. For each element of the sequence, there are two possibilities, either a piece is affected by this element, or it is not. So there is a maximum of 24 = 16 sets.

If a piece is not affected by any element, it means that it is completely outside of the commutator.

=== Pieces affected by one element only ===

If a piece is affected by A only, then it is not affected by B and then it is necessarily affected by A', so it is impossible. Same thing for B. If a piece is affected by A' only, it means that it was not affected by B before that, so that it was affected by A. Impossible again. If a piece is affected by B' only, it means that it was not affected by A' before that, so that it was affected by B. Impossible again.

=== Pieces affected by two elements ===

If a piece is affected by A and A', or by B and B', it means that it comes back finally where it comes from. We can ignore them.

If a piece is affected by A and B only, it means that it is not affected by A', so it is necessarily affected by B'. Impossible. If a piece is affected by A and B' only, it is not affected by B, so it is necessarily affected by A'. Impossible again.

If a piece is affected by B and A', it means that it is brought into the intersection by B. They are denoted PB.

=== Pieces affected by three elements ===

If a piece is affected by A and A' B', it means that it is hidden by A so that it is not affected by B. These pieces are denoted PN because they come from the intersection.

If a piece is affected by A B and B', it means that it is brought into the intersection by A, and then hidden by B from A'. These pieces are denoted PA.

If a piece is affected by B A' B', it means that it is brought into the intersection by B and then moved inplace by A. If a piece is affected by A B A', it means that it is affected by the conjugate of B. In both of these cases, let's denote them PC to express that they are affected by conjugates.

=== Pieces affected by all four elements ===

If a piece is affected by all four elements, it means that it is never hidden from the intersection. Thus it is in the quirk part. They are denoted PQ.

=== Summary of sets of pieces ===

In all cases, pieces that are moved by the commutator are in one of these sets:
* PA : pieces moved into the intersection by A and then hidden by B
* PB : pieces moved into the intersection by B and then hidden by A
* PN : pieces hidden by A and then moved out of the intersection of B'
* PC : pieces affected by a conjugate, in all inplace cases and some overlap cases
* PQ : pieces moved by all elements of the sequence of the commutator, in complex inplace cases and some overlap case

== Classification ==

If PA is not empty, then B can hide pieces, thus PB is not empty either. Conversely, if PB is not empty, then PA is not empty.

If PN is not empty, then A and B can hide pieces, thus PA and PB are not empty. Conversely if PA is not empty, it means that pieces are brought into the intersection so that pieces are brought out of the intersection by A, thus PN is not empty.

So either the three sets PA, PB and PN are not empty or the three sets are empty. If these sets are empty, it means that at least A, B or both A and B move pieces inside the intersection '''N''' only. So it is either a trivial case or an inplace case. If both A and B move pieces inside the intersection, let's call it "double inplace".

If it is an inplace case and not a "double inplace", then some pieces are affected by a commutator. Thus PC is not empty.

If the sets PA, PB and PN are not empty, we cannot deduce anything about PQ or PC. If it is the no overlap case, then pieces are hidden either by A or B, so PQ is empty. Conversely, if PQ is empty, then pieces brought by A into the intersection are completely hidden by B. The inverse of the commutator B A B' A' shows that also A hides pieces brought by B, so that it is a no overlap case.

So we get the following possible types of commutators:
* trivial commutator which is equivalent to the identity: [L, R]
* double inplace, A and B move pieces inside the intersection
* single inplace without quirk part, the same transformation is applied twice (the second time in reverse order) without interference: corner twist, edge flip, double swap
* single inplace with quirk part, there is an interference between the conjugated and the non conjugated version of the transformation: [M', U2]
* no overlap, 3-cycle: [R' D' R, U']
* overlap with quirk part and without conjugated part: [R', F]
* overlap with conjugated part and without quirk part: [R', F']
* overlap with both quirk and conjugated part

== See also ==
* [[Commutators and Conjugates]]
* [[Conjugate]]

[[Category:Puzzle theory]]