Date:  1 February 1981 0612-EST (Sunday)
From: Dan Hoey at CMU-10A
To: Cube-lovers at MIT-MC
Subject:  Algorithm for computing cube group orders
Message-Id: <01Feb81 061255 DH51@CMU-10A>

	Oops... you have just received part 3.  This is part 1....

	This note is in somewhat delayed response to the note by
David C.  Plummer (31 DEC 1980 1115-EST) regarding the 5x5x5 Rubik
cube, and some related ideas.  In that note he tried to calculate
the size of that cube's Rubik group, but left several of the values
open to conjecture.  I will complete the answer, and answer a few
others that haven't been addressed here.

	Computing the size of a Rubik group is a special case of
computing the size of a permutation group, given generators for
that group.  The technique we have already seen in these pages is in
two parts.  The first part seems relatively easy:  certain invariants
must be observed in the generators, such as "Corner Orientation
Parity" and "Total Permutation Parity."  [In this general setting,
such invariants as "Colortabs on the same cubie move together" must
also be considered.]  It may take some thought to dig out the
invariants, but once you have seen them demonstrated for Rubik's
Cube, you have an idea of what to look for.  The second part is the
devil:  it must be demonstrated that every permutation satisfying
those invariants is actually generated.  This involves developing a
solution method for the puzzle.  Given the days or weeks (or
eternity) it takes most people to develop such a method--with cube
in hand!--it is hardly surprising that few answers have been
developed.

	Well, the second part is no longer a hard problem.  The
answer lies in a paper by Merrick Furst, John Hopcroft, and Eugene
Luks, entitled "Polynomial-Time Algorithms for Permutation Groups,"
which was presented at the 21st Annual Symposium on Foundations of
Computer Science, October 1980.  Among the results is an algorithm
which takes as input a set of permutations on n letters, and
reports the size of the group G which is generated by those
permutations.

	The algorithm operates by decomposing G into a tower of
groups I=G[0], G[1], ..., G[n]=G, where G[i] contains those
permutations p in G for which p(k) = k whenever i < k <= n.  The
index of G[i-1] in G[i] is developed explicitly by the algorithm;
in fact, a representative g[i,j] of every coset of G[i-1] in G[i]
is exhibited.  These coset representatives generate G; in fact,
every element of G is representable as a product of the form
(g[1,j1])(g[2,j2])...(g[n,jn]).  For this reason the coset
representatives are called "strong generators" for G.  There is a
good deal of structure that can be learned from the strong
generators, in addition to the size of G.

	I have coded this algorithm in Pascal, and offer the
program for the use of anyone who needs to find group orders.  The
relevant files are on CMU-10A, from which other sites may FTP
without an account.  The relevant files are
    all:group.pas[c410dh51]	The source
    all:rubik.gen[c410dh51]	A sample input -- the supergroup
    all:rubik.lst[c410dh51]	Sample output.
Of course, CMU Pascal is probably slightly different from yours,
and OS-dependent stuff like filenames is likely to be wrong.  I'll
be glad to help out in cases of transportability problems.  The
other problem you may run into is resource availability.  The
running time of the algorithm is proportional to (nm)^2, where m is
the total number of strong generators; the supergroup (n=72, m=279)
takes 639 cpu seconds on a KL-10, and bigger problems grow rapidly.
The program also requires 47000+47m words.

	It might seem that the problem has been answered, but I
find that simply knowing the size of a group is not very
satisfying.  There doesn't seem to be a better way of demonstrating
lower bounds, but the upper bounds that come from invariants are
much more elegant than a simple numerical answer.  Unfortunately, I
know of no mechanical way of finding the invariants.  Furthermore,
using group theory does not help much when we ignore the
Supergroup.  Consider the 4x4x4 cube.  If we are only concerned with
the color pattern on the cube, then a twist may or may not affect
the four face centers--it depends on whether they are the same
color or not.

	In summary, the algorithm has inverted the hard and easy
parts of cube analysis.  The size of the group is now easy to
determine, making invariant-finding the hard part.  Further, the
algorithm works on the Supergroup, making counting distinct color
patterns the part which requires further analysis.  Two messages
follow, supplying these answers for the 4x4x4 and 5x5x5 cubes.