~~~ From:

~~~ ~~~ Subject:

Mark Longridge wrote in is e-mail message of 1994/04/02

The resultant position generated by process p8 is invariant under

shifting, specifically 2 X on the Left and Right sides.P8 2 x ORDER 2: shift 0 D2 F2 T2 F2 B2 T2 F2 T2 1 T2 D2 F2 T2 F2 B2 T2 F2 ... 7 F2 T2 F2 B2 T2 F2 T2 D2This is the longest process I've found so far. Certainly this property

is not true of all squares group processes. I suspect there are no

processes in the full group with this property (of any significant

length). Perhaps the fact that the L and R faces never rotate will

give some clue on how to generate processes with this property.

I have classified all such shift invariant processes, using a little bit

of group theory and the computer algebra system GAP.

Let me first repeat the definition.

A *process* g_1 g_2 ... g_n, where the letters g_i come from the set

{U,U2,U3,D,D2,D3,...,B,B2,B3}, is called *shift invariant* if each of

the processes g_1 g_2 ... g_n, g_2 ... g_n g_1, ..., g_n g_1 ... g_{n-1}

effects the same element g in the cube group G.

In the following I will be a bit sloppy and neither distinguish between

letters and the corresponding generators of the cube group nor between

processes and the elements of the cube group they effect.

With this terminology a shift invariant processes would be one where

g_1 g_2 ... g_n = g_2 ... g_n g_1 = g_n g_1 ... g_{n-1}.

So lets assume that g = g_1 g_2 ... g_n is a shift invariant process. Then for every letter g_i in g we have g_i' g = g_i' (g_i g_{i+1} ... g_{i-1}) = (g_{i+1} ... g_{i-1}) = (g_{i+1} ... g_{i-1} g_i) g_i' = g g_i'. That means that g commutes with (the inverses) of each of its letters.

Because g commutes with each of its letters, it also commutes with all

elements of the subgroup H = < g_1, g_2, ..., g_n > generated by its

letters. The set of those elements of H which commute with all elements

of H is called the centre of H. Thus g lies in the centre of H.

Obviously the other direction is also true. If g lies in the centre of

H = < g_1, g_2, ..., g_n >, i.e., if it commutes with every element of H,

then it especially commutes with its letters, and so the corresponding

process is shift invariant.

This says that if we have an element g in the centre of a subgroup

H = < g_1, g_2, ..., g_n >, then *every* process that effects g and

uses the letters g_1, g_2, ..., g_n will be a shift invariant process.

So there are finitely many such elements (after all there are only

finitely many elements in the entire cube group), but each gives

rise to infinitely many different shift invariant processes.

In particular there is *no* longest shift invariant process.

So the task is to search for subgroups H generated by subsets of

{U,U2,U3,D,D2,D3,...,B,B2,B3} that have non-trivial centres.

There are 729 = 3^6 such subgroups. Of course we are only interested in

representatives under the operation of M (the subgroup of symmetries of

the entire cube), which leaves us with 56 subgroups.

Of those 21 have a non-trivial centre (for this computation I used GAP).

The centres are all very small and contain mostly the same elements,

i.e., the same element lies in the centre of different such subgroups.

I do not want to bore you with the details. Allow me to jump to the

discussion of the results.

There are 5 different types of elements that give rise to shift invariant

processes.

1) The ``trivial'' element.

The identity element lies in the centre of every subgroup H.

Thus every process that effects the identity is shift invariant.

There is exactely one such element in the entire group.

2) The ``central'' element.

The superflip, which flips all edges, is in the centre of G.

Thus every process that effects the superflip is shift invariant.

There is exactely one such element in the entire group.

3) The ``abelian'' elements.

The subgroups < U > and < U, D > (and their conjugates under M)

are abelian, and are therefore equal to their centre.

Therefore every element in < U > and < U, D > is shift invariant.

There are 45 such elements in the entire group.

4) The ``odd'' element.

The element (UR)^140 lies in the centre of the subgroup <U,R>.

It is the only shift invariant element of odd order (hence the name).

Thus this process and its inverse are shift invariant.

There are 24 such elements in the entire group (two for each edge).

5) The ``square'' elements.

The following elements live in the ``square ring'' group <U2,D2,R2,L2>

(though some of them are central in proper supergroups of it).

5a) The ``single square'' elements.

The element (U2 R2)^3 lies in the centre of <U2,D,R2,L>.

Thus this process is shift invariant.

There are 12 such elements in the entire group (one for each edge).

5b) The ``edge square'' elements. The element (U2 R2)^3 (U2 L2)^3 = (D2 R2)^3 (D2 L2)^3 lies in the centre of <U,D,R2,L2>. Thus this process is shift invariant. There are 6 such elements in the entire group (two for each axis). 5c) The ``diagonal square'' elements. The element (U2 R2)^3 (D2 L2)^3 = (U2 L2)^3 (D2 R2)^3 lies in the centre of <U2,D2,R2,L2>. Thus this process is shift invariant. There are 3 such elements in the entire group (one for each axis).

For me the most amazing elements were the ``odd'' element and the

``diagonal square'' element.

They are special in the sense that the smallest subgroup in which they

lie and the largest subgroup in which they are central are equal.

That means that you have no choice which letters to choose to write

them (you have lots of choices how arrange those letters and how often

to repeat them of course). You cannot use less, because they do not

lie in a smaller group, and you cannot use more, because they are not

central in a larger group.

Let me return to Mark's e-mail and discuss it in the light of the above.

Mark writes

The resultant position generated by process p8 is invariant under

shifting, specifically 2 X on the Left and Right sides.P8 2 x ORDER 2: shift 0 D2 F2 T2 F2 B2 T2 F2 T2 ...

Believe it or not, this is a process for the ``diagonal square'' element.

Mark writes

This is the longest process I've found so far.

How about (UR)^140 or (UR)^1400? As mentioned above, you can make the

processes as long as you wish.

Mark writes

Certainly this property is not true of all squares group processes.

No, only for processes that effect one of the 21 elements mentioned above

(31 if you want to count the ``trivial'' and ``abelian'' elements in the

square group).

Mark writes

I suspect there are no processes in the full group with this property

(of any significant length).

Not true. The interesting ones are the processes effecting the

``central'' element and the ``odd'' elements.

Mark writes

Perhaps the fact that the L and R faces never rotate will give some

clue on how to generate processes with this property.

Now this remark makes me very suspicious. Did Mark know the full story?

The squares subroup has trivial centre (containing only the identity),

you have to leave out at least two generators belonging to opposite

faces, to get a subgroup with non-trivial centre.

Mark writes in another e-mail message of 1994/04/10

The following processes are also shift invariant:

2 Swap D2 R2 D2 R2 D2 R2 (6) (symmetry level 12, SI level 2) p21 2 H L2 R2 B2 L2 R2 F2 (6) (symmetry level 6, SI level 6)Amazingly, the process p3 (found using Dik Winter's program) is actually

a series of 20 processes which all result in the same displacement!p3 12 flip R1 L1 D2 B3 L2 F2 R2 U3 D1 R3 D2 F3 B3 D3 F2 D3 R2 U3 F2 D3 (20) (symmetry level 1, SI level 20)

The first is obviously a ``single square'' element, the second is a

``edge square'' element, and 'p3' is the ``central'' element.

Thus at this time all non-trivial such elements had been found, except

for the ``odd'' element.

Have a nice day.

Martin.

PS: GAP is really a nice program to analyze the cube group from the

group-theoretical side, though I would not use it to enumerate

positions in search for god's algorithm.

PPS: Of course I am biased, because I am one of the main authors of GAP ;-)

-- .- .-. - .. -. .-.. --- ...- . ... .- -. -. .. -.- .- Martin Sch"onert, Martin.Schoenert@Math.RWTH-Aachen.DE, +49 241 804551 Lehrstuhl D f"ur Mathematik, Templergraben 64, RWTH, 52056 Aachen, Germany