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 R3=1 (the unity operation of doing nothing). The operation R generates the group which has the relation R3=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 A2=1, B2=1 and C2=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.
A2=1, D2=1, C3=1, C−1ACA=1, DC−1DC, DBDB=1, C−1BCB−2, B7=1, (AB−1AB)2=1, AB−2AB−1AB3=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.
A2=1, C2=1, D2=1, B3=1, ABAB=1, AB−1CBD=1, B−1DBDC=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.
A2=1, B2=1, C2=1, D2=1, E2=1, F2=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 pp465-466.
[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 A3 = B5 = 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 TEX by TTH, version 3.81.
On 19 Sep 2010, 11:28.