Coset enumeration on KDF9
Brian Wichmann
Abstract
I found in my loft documentation and a listing of an interesting
mathematical program written in 1963. This paper explains what the program does
and the result of running it on an emulator.
1 Introduction
In 1963, John Leech wrote a KDF9 Usercode program to undertake
coset enumeration [2] (to be explained below).
I was in correspondence with John Leech for two reasons: my
thesis was related to coset enumeration and I had written a paper
on restricted difference bases [3] which was also an area of his
expertise. Fortunately, I have kept both my files on these topics,
and the coset enumeration file contains a listing of his program.
(As can often happen, I have John Leech's letters, but not mine to him.)
1.1 Generators and relations
To understand coset enumeration, one needs the concept of generators and relations,
and some rudimentary group theory. Consider the operation of rotating tthe plane
about a point by 120^{°}. If the operation is R, then R^{3}=1 (the unity operation
of doing nothing). The operation R generates the group which has the relation R^{3}=1.
As another example, consider the triangle on the surface of the sphere whose angles
are π/2, π/3 and π/5. Let the reflections along the three edges be
A, B and C. Then we clearly have A^{2}=1, B^{2}=1 and C^{2}=1. The
rotations about the vertices are AB, BC and CA. We then have (AB)^{2}=1,
(BC)^{3}=1, and (CA)^{5}=1. These are the generators are relations for the symmetry
group of the triangle on the sphere.
1.2 Coset enumeration
Given a group G and a subgroup S, then the cosets are the members of gs where s is in S.
For a finite group, one may be able to count the size of S and the number of cosets, thus
giving the size of the group (being the product of the two).
In the early 1960's, one of the leading questions was to determine all the finite
simple groups. Several infinite families were known, and a few others. One
question was to determine if a simple group could exist of the specified order (size).
Coset enumeration could sometimes be used to solve this problem. In 1965, Graham
Higman, my old supervisor from Oxford, asked if I could run John Leech's
program to determine if a specific set of generators and relations gave a simple
group of the expected order. Unfortunately, I don't have this specific request
documented.... John Leech could not run this example since the Glasgow KDF9 had
only 16K store which was insufficient for this.
It seems that coset enumeration by computer has been done since the early 1950's
[1].
2 Enumerations undertaken
2.1 Example 1
This was undertaken by John due to a request I made:
 Generators of group.
 A, B, C, D, E, F.
 Generators of subgroup.
 A, B, C.
 Relations.
 A^{2}=1, D^{2}=1, C^{3}=1, C^{−1}ACA=1, DC^{−1}DC, DBDB=1,
C^{−1}BCB^{−2}, B^{7}=1, (AB^{−1}AB)^{2}=1, AB^{−2}AB^{−1}AB^{3}=1, (AD)^{5}=1,
(ABCDE)^{7}=1.
 Answer.
 1045
 Comment.
 I have no recollection what this was about!
2.2 Example 2
This is the first of 2 examples dated 17th February 1966 and hence cannot be
an investigation by me and so I hope it was part of the search for sporadic
simple groups.
 Generators of group.
 A, B, C, D.
 Generators of subgroup.
 A, B.
 Relations.
 A^{2}=1, C^{2}=1, D^{2}=1, B^{3}=1, ABAB=1,
AB^{−1}CBD=1, B^{−1}DBDC=1, (CD)^{2}=1,
(AC)^{8}=1.
 Answer.
 Not recorded
 Comment.
 Charlie Sims has examined this example and concluded that it could not be from
a search for the finite simple groups.
2.3 Example 3
This is the second of 2 examples dated 17th February 1966 and hence cannot be
an investigation by me and so I hope it was part of the search for sporadic
simple groups.
 Generators of group.
 A, B, C, D, E, F.
 Generators of subgroup.
 A, D.
 Relations.
 A^{2}=1, B^{2}=1, C^{2}=1, D^{2}=1, E^{2}=1, F^{2}=1,
ABAB=1, BCBC=1, CACA=1, DEDE=1, EFEF=1, FDFD=1,
(ABC)^{3}=1, (DEF)^{3}=1, (AD)^{3}=1, (BE)^{3}=1,
(CF)^{3}=1.
 Answer.
 Not recorded
 Comment.
 Charlie Sims has examined this example and concluded that it could not be from
a search for the finite simple groups.
3 Conclusions
Apart from the program listing, my records are too incomplete to find out how,
if at all, running this program at NPL assisted in the search for finite simple
groups. The program was useful in providing another example of an application
program to debug the emulator. It also showed that an application program was
run in October 1963  much earlier that we had recorded previously.
References
 [1]

Sims, Charles C. Computation with finitely presented groups.
Cambridge University Press, 1994. ISBN: 0521432138.
 [2]

Wikipedia.
Coset enumeration.
Good introduction.
 [3]

Brian Wichmann.
A note on restricted difference bases.
J. Lond. math. Soc., 1963. Vol 38 pp465466.
 [4]

David M Yates. Turing's Legacy. Science Museum. 1997.
ISBN 0 901805 94 7
A Information available
I have 7 letters from JL in my restricted difference bases file
dating from 5th March 1962 to 4rd March 1964. My coset enumeration
file has 6 letters in 1965 from 14th January to 18th October.
Actually, the subject of the letters overlaps slightly.
JL's letter of 7th October 1963 states "on KDF9 at
Birmingham I got the 3720 cosets of {E} in A^{3} = B^{5} = AB^{−2} in 42
seconds". This raised problems with other information about the
Birmingham machine. I suspect the small JL program was being used
to test the hardware!
I have three listings of the program: an two undated Flexowriter versions
and a line printer version dated 19/10/65 (which has the amendments
applied to use the 32K store of the NPL machine). (I started work
at NPL in October 1964.)
Unfortunately, the data files for the enumerations undertaken
cannot be dated (in general) or related the specific letters
except by analysis.
A.1 Data files
 Data 1 and 2.
 This looks like two cases on one data tape.
The listing I have is surely the output which includes the number
of cosets in both cases. The listing is marked "3 mins" which I assume
is the time taken for both cases. The paper used seems to indicate
that this was run at NPL.
File translated from
T_{E}X
by
T_{T}H,
version 3.81.
On 19 Sep 2010, 11:28.