Date: Mon, 24 Oct 94 21:58:00 -0700 (PST)
~~~ From: Martin Schoenert <Martin.Schoenert@math.rwth-aachen.de >
~~~ ~~~ Subject: Shift invariant processes
```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 D2
```

This 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
```