With the notable exception of number theory, the computer has been neglected as a useful practical tool in pure mathematics. For historical reasons it has been used extensively in applied mathematics. The body of knowledge which has accumulated in the course of attempts to find approximate numerical solutions to the equations of applied mathematics now forms the well-established discipline of numerical analysis. The problems of the pure mathematician have, until very recently, been neglected. There are two main reasons for this: the enormous apparent computational size of the problems and the pure mathematician's distaste in dirtying his hands using a computer.
Where problems look at first sight enormous, new techniques may be found to solve them. For example, in a far-sighted paper [1] in 1951 Professor M. H. A. Newman suggested that an exhaustive computer investigation into the number of groups of order 28 would be quite a hopeless problem because of its size, but advances in algebra and faster machines have led to this being a feasible proposition today. If a computer is initially conceived of as the vehicle to the solution then this may affect the theoretical techniques developed.
The charge, by a pure mathematician, of having to dirty his hands is no longer justified, since we are on the threshold of having private multiple access consoles in our own rooms, and high level languages can be assimilated in a couple of days. One no longer has to be a professional programmer to use a computer.
Significant results otherwise unobtainable are the best way of demonstrating the place of a machine in algebra. We give such a result here. Background reading for what follows may be found in books by LEDERMANN [2] and BURROW [3] and a paper by LEECH [4].
A representation of degree n of a finite group G = {x1,x2,...xg} is a set of linear invertible transformations: {T(xi)}: in a vector space Vn of dimension n such that
xixj = xk implies T(xi)T(xj) = T(xk).
By choosing a basis for Vn we may represent each transformation T(x) by an n × n matrix R(x). We may regard the set: {C-1R(x)C} as representing the same transformations as {R(x)} itself but described by a different coordinate system. Two representations R and S are said to be equivalent if S = C-1RC for some constant matrix C, otherwise R and S are inequivalent.
If the representation R can be split as described later into two representations R1 and R2, we say R is reducible and the components of R are R1 and R2 otherwise R is irreducible.
Thus, R is reducible if there is a constant non-singular matrix C such that
We write
This splitting may be repeated until eventually
and each of the Ri is irreducible.
There is a 1 - 1 relation between the conjugacy classes of G and the irreducible representations of G, thus r is both the number of classes of G as well as the number of inequivalent irreducible representations G possesses. It can also be shown that the multiplicity and the degree of the irreducible components of R are each essentially unique, thus the representation R is characterized up to equivalence by the ordered set {k1. k2...., kr}. A table containing the traces of the inequivalent irreducible representation of a group is known as its character table.
Let G be S3, the group of all permutations on three symbols. This is the symmetry group of the equilateral triangle.
It is generated by a 120° rotation about the centre together with a reflection about a perpendicular bisector. Denoting these operations by a and b respectively, we see that:
(1) a3 = b2 = (ab)2 = I.
We say that G is generated by a and b and that the equations (1) are the defining relations for G.
There are 3 classes of conjugates corresponding to the sets of permutations
C1 = (1)(2)(3), C2 = (12)(3),(23)(1),(13)(2), C3 = (132),(123).
The three inequivalent irreducible representations are:
Period 1 2 2 2 3 3
R1 1 1 1 1 1 1
R2 1 0 1 0 0 -1 -1 1 0 -1 -1 1
0 1 1 -1 -1 0 0 1 1 -1 -1 0
R3 1 -1 -1 -1 1 1
and so the character table is
Class C1 C2 C3 Period 1 2 3 Order h1=1 h2=3 h3=2 R1 1 1 1 R2 2 0 -1 R3 1 -1 1
This table may appear to be a rather esoteric object in group theory but it is really nothing more nor less than a table of the number aijk of solutions (x,y) to the equations
xy = z for fixed z, where x is in Ci, Y is in Cj, Z is in Ck,
although this is not immediately apparent. Much information about G can be read from its character table. Frequently the character table characterizes G uniquely.
I have written a program that computes the character table of finite group G from its definition in terms of generators and relations (see [5]). This involves ultimately solving an eigenvalue problem for unsymmetric real matrices. The character table of Janko's recently discovered simple group of order 175,560 can be determined from generators and relations within 30 minutes using Atlas.
The reverse problem has arisen recently: given the character table of a postulated group, does the group exist? In 1967 the possible existence of two more new simple groups was announced by Janko on the basis of their character tables. One is of order 604,800 which has been constructed by Marshall Hall [5] as a group of permutations on 100 symbols. The other, which I shall discuss here, is of order 50,232,960.
The first problem is to check the accuracy of the character table. This is done by testing several necessary conditions that the table must fulfil.
Let Χij denote the character of an element of class Cj (C1 = I) in the irreducible representation Ri. Write di (= Χi1) for the degree of Ri.
If
then necessarily UU* = U*U = I where * denotes complex conjugate transpose. These orthogonality tests localize the position of certain errors.
We have further that the ajjk are non-negative integers where
and for each i and s
To each subgroup H of G there exists a permutation representation of G on the cosets of H. Let the multiplicities of this permutation representation be {k1, k2, . . ., kr}, that is, where R is the induced permutation representation and the Rj are irreducible components.
We deduce, by taking the trace of the identity, that
where n is the degree of R and di is the degree of Ri. In fact we can show that, in addition, n|g and 0 ≤ ki ≤ di. Further conditions may be found by taking traces of elements other than the identity, but these need not concern us here (see [6]).
If there is no set {ki} satisfying our requirements then there exists no subgroup of order g/n in G. In this way we can show for Janko's group of order 50,232,960 that the smallest possible non-trivial value of n is 6156 and so the largest possible order of a proper subgroup is 8160. Using this fact, Professor Higman of Oxford University has been able to construct a set of generators and relations for the group, and then coset enumeration has been used to show that the given relations do indeed define a group of the required order by enumerating the 6156 cosets of the subgroup - a task which uses all of Atlas' one-level storage capacity of 100,000 words. Since this was written the existence of a new simple group of order 4,030,387,200 has been demonstrated in a similar manner.
1. Newman, M. H. A. 1951. The Influence of Automatic Computers on Mathematical Methods.' In the Proceedings of the Inaugural Conference of the Manchester Mark II computer. Manchester University.
2. Ledermann, W. 1964. 'An Introduction to the Theory of Finite Groups,' Oliver & Boyd, Edinburgh.
3. Burrow, M. 1965. 'Representation Theory of Finite Groups.' Academic Press, New York.
4. Leech, J. 1963. Coset enumeration on digital computers, Proc. Camb. Phi/os. Soc. 59, 257-267.
5. Leech, J. (ed). 1969. 'Computational Problems in Abstract Algebra.' (Proceedings of the Oxford Conference on Computational Algebra), Pergamon Press.
6. Littlewood, D. E. 1940. The Theory of Group Characters.' Oxford University Press.