From mschoene@math.rwth-aachen.de Mon Oct 24 16:59:39 1994 Return-Path: Received: from samson.math.rwth-aachen.de by life.ai.mit.edu (4.1/AI-4.10) for /com/archive/cube-lovers id AA05394; Mon, 24 Oct 94 16:59:39 EDT Received: from hobbes.math.rwth-aachen.de by samson.math.rwth-aachen.de with smtp (Smail3.1.28.1 #11) id m0qzWSu-000MP8C; Mon, 24 Oct 94 21:58 MET Received: by hobbes.math.rwth-aachen.de (Smail3.1.28.1 #19) id m0qzWSu-0000PrC; Mon, 24 Oct 94 21:58 PST Message-Id: Date: Mon, 24 Oct 94 21:58 PST From: Martin.Schoenert@math.rwth-aachen.de To: cube-lovers@life.ai.mit.edu 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 . 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 (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 . 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 . 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 . 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