Date:  9 January 1981 0629-EST (Friday)
From: Dan Hoey at CMU-10A
To: Cube-lovers at MIT-MC
Subject:  The Supergroup -- Part 2: At least 25 qtw, and why
Message-Id: <09Jan81 062915 DH51@CMU-10A>

	Alan Bawden (31 JUL 1980 2159-EDT) calculated that it must
take at least 21 quarter-twists to solve an ordinary cube, and 24
qtw to solve a cube in the Supergroup.  This message explains how
the first bound can be obtained, improves the second, and points
toward a technique for possible further improvements.

Express any (optimal) sequence of twists as a sequence of segments,
where each segment is a sequence of twists on two opposite faces,
and no two adjacent segments operate on the same pair of faces.
Because the quarter-twist has period four, and opposite faces
commute, a segment operating on faces X and Y has one of the forms
	X, X', Y, Y'				(1 qtw -- 4 ways)
	XX, YY, XY, YX, X'Y, Y'X, XY', Y'X	(2 qtw -- 6 ways)
	XXY, XXY', XYY, X'YY			(3 qtw -- 4 ways)
	XXYY					(4 qtw -- 1 way).
There are 3 ways of choosing X and Y for the first segment, and two
ways of choosing them for every succeeding segment.  Let P[n] be the
number of positions that are exactly n qtw from SOLVED.  Then
bounding P[n] by the number of n-qtw sequences,
	P[0]   = 1
	P[1]  <= 4*3*P[0]
	P[2]  <= 4*2*P[1]   + 6*3*P[0]
	P[3]  <= 4*2*P[2]   + 6*2*P[1]   + 4*3*P[0]
	P[4]  <= 4*2*P[3]   + 6*2*P[2]   + 4*2*P[1]   + 1*3*P[0]
	P[n]  <= 4*2*P[n-1] + 6*2*P[n-2] + 4*2*P[n-3] + 1*2*P[n-4]
						for n > 4.
Evaluating this recurrence, substituting strict (in)equality where
I have personally verified it, and rounding truthfully yields:

P[0]  =           1	P[9]  < 724,477,008	P[18] < 4.048*10^17
P[1]  =          12	P[10] < 6.792*10^9	P[19] < 3.795*10^18
P[2]  =         114	P[11] < 6.366*10^10	P[20] < 3.557*10^19
P[3]  =       1,068	P[12] < 5.967*10^11	P[21] < 3.334*10^20
P[4]  =      10,011	P[13] < 5.594*10^12	P[22] < 3.125*10^21
P[5]  <=     93,840	P[14] < 5.243*10^13	P[23] < 2.930*10^22
P[6]  <     879,624	P[15] < 4.915*10^14	P[24] < 2.746*10^23
P[7]  <   8,245,296	P[16] < 4.607*10^15	P[25] < 2.574*10^24
P[8]  <  77,288,598	P[17] < 4.319*10^16

	There are 4.325*10^19 positions in the standard cube; since
P[0]+P[1]+...+P[20] < 3.982*10^19, there must be a position at
least 21 qtw from SOLVED (The number 22 has appeared in Cube-lovers
recently, but it was an error).  There are 8.858*10^22 positions in
the Supergroup; since P[0]+P[1]+...+P[23] < 3.280*10^22, there must
be a position at least 24 qtw from SOLVED.  But this can be
improved:  half of the positions in the Supergroup are an odd number
of qtw from SOLVED, and since P[1]+P[3]+...+P[23] < 2.963*10^22 is
less than half the Supergroup, there must be some odd-length
elements of the Supergroup at least 25 qtw from SOLVED.  QED.  (If
you think there's something fishy here, mail to Hoey@CMU-10A for
clarification.  I am responsible for any cruft that has crept into
the original, elegant, formulation due to Jim Saxe.)

	The recurrence on which this bound relies is due to the
relations F^4 = FBF'B' = I (and their M-conjugates.)  It may be
possible to improve the recurrence by recognizing other short
relations.  Exhaustive search has shown that there are none of
length less than 10.  The most promising ones I know of come from
Singmaster:
		I = FR'F'R UF'U'F RU'R'U	(12 qtw),
		I = (FFBB RRLL)^2		(16 qtw),
and a 14-qtw relation which holds only in the standard group, since
it twists a face center 180o (see part 3).  Unfortunately, the
number of intermediate terms grows too large to be comfortably
hand-computable, and there are a few conceptual problems to hacking
it out.  If you can improve this, or know of any other relations
shorter than 24qtw, I'd like to hear about it.

	Coming up next: SPOILERS