The taming of the Monster

Robert A Wilson Wednesday 4th December 2002

Auckland Groups are the abstract embodiment of symmetry in mathematics, and as such their study is of fundamental importance wherever symmetry can be used to simplify problems.

The trouble is that groups are complicated objects, despite their simple definition, and a complete classification of them is hopeless.

We can however sometimes break them down into smaller groups: if N is a normal subgroup of a group G, then the set G/N = {Ng : g ∈ G} of cosets Ng = {ng : n ∈ N} forms a quotient group. In these circumstances, we can study G by studying the smaller groups N and G/N, and the way they are stuck together to form G.

If we cannot break the group down in this way, it is called simple. Clearly a group of prime order is simple, as it has no subgroups at all. All other simple groups are non-abelian (i.e. non-commutative).

Galois initiated the study of non-abelian simple groups in the 1830s: the fact that the alternating group A_{5} is simple proves that the general quintic equation is not soluble by radicals.

He found a number of other simple groups, including what we now call PSL_{2}(p), for primes p ≥ 5.

The obvious question is, can we find all the finite simple groups? Well, to cut a long story short …

CFSG

the Classification theorem for Finite Simple Groups Every finite simple group is either:

• a cyclic group of prime order

• an alternating group of degree at least 5 • a group of Lie type, or

• one of 26 sporadic simple groups

Alternating groups

The symmetric group of degree n consists of all permutations of n points. Half the n! permutations are even, which means they can be written as the product of an even number of transpositions.

The alternating group A_{n} of degree n consists of these \frac{1}{2}n! even permutations. For every n ≥ 5, A_{n} is a simple group.

Groups of Lie type

can be thought of as matrix groups.

E.g. GL_{n}(q) consists of all invertible n × n matrices over the field of q elements.

SL_{n}(q) is the subgroup of matrices of determinant 1.

PSL_{n}(q) is the quotient of SL_{n}(q) by the subgroup of scalar matrices, and is simple for almost all values of n and q.

Sporadic groups

The sporadic simple groups range in size from the smallest Mathieu group, M_{11} , discovered by Emile Mathieu in 1860, and having just 7920 elements, to the Monster, 𝕄, discovered by Fischer and Griess in about 1973, and having

808017424794512875886459904961710

757005754368000000000

elements.

Families of sporadic groups

• The five Mathieu groups, M_{11} , M_{12} , M_{22} , M_{23} and M_{24} , permutation groups on 11, 12, 22, 23, 24 points respectively. The biggest one, M_{24} , contains all the others (as subgroups).

• The seven Leech lattice groups, J_{2}, Suz, HS, McL, Co_{3}, Co_{2}, Co_{1}, matrix groups in (up to) 24 dimensions. The biggest one, Co_{1}, involves all the others (as quotients of subgroups), as well as all the Mathieu groups.

• The three Fischer groups, Fi_{22} , Fi_{23} , Fi′_{24} . The biggest one, Fi′_{24} , involves all the others (as quotients of subgroups), as well as all the Mathieu groups.

• The Monstrous groups, He, HN, Th, B and 𝕄. The Monster 𝕄 involves all the groups we’ve seen so far.

• The Pariahs or oddments, J_{1}, J_{3}, J_{4}, Ru, ON, Ly, not involved in the Monster. These do not really form a family, although J_{1} is a subgroup of ON.

Apart from the Monster and the Baby Monster B, all these groups are named after their discoverers: Mathieu, Janko, Suzuki, Higman, Sims, McLaughlin, Conway, Fischer, Held, Harada, Norton, Thompson, Rudvalis, O’Nan and Lyons.

How to calculate in the sporadic groups

as permutation groups:

Group Number of points
M_{11}  11
M_{12}  12
M_{22}  22
M_{23}  23
M_{24}  24
J_{2}  100
HS  100
McL  275
Co_{3}  276
Suz  1782
Co_{2}  2300
Co_{1}  98280 if you dare!
Fi_{22}  3510
Fi_{23}  31671
Fi′_{24}  306936 ouch!

Group Number of points
J_{1}  266
J_{3}  6156
J_{4} 173067389 this is getting silly!
Ru  4060
ON  122760
Ly  8835156
He  2058
HN  1140000
Th  143127000
B 13571955000 seriously hard
𝕄  c. 10^{20} impossible

or as matrix groups (over finite fields, sometimes modulo scalars):

Group Dimension Field size
M_{11}  5  3
M_{12}  6  3
M_{22}  10  2
M_{23}  10  2
M_{24}  11  2
J_{2}  6  4
Suz  12  4
HS  20  2
McL  21  3
Co_{3}  22  2
Co_{2}  22  2
Co_{1}  24  2
Fi_{22}  77  3
Fi_{23}  253  3
Fi′_{24}  781  3 biggish

Group Dimension Field size
J_{1}  7  11
J_{3}  9  4
J_{4}  112  2
Ru  28  2
ON  45  7
Ly  111  5
He  50  7
HN  132  4
Th  248  2
B  4370  2 quite big
𝕄  196882  2 rather tricky

All these representations except the really big ones are available on my website

http://www.mat.bham.ac.uk/atlas/

But how can we calculate in the Monster, when each matrix occupies 5 gigabytes, and a matrix multiplication takes weeks of CPU time?

We want to represent an element of the Monster, in effect as a matrix. But what is a matrix really? It is encoding an action on the underlying vector space. And the action is computed by a familiar algorithm called ‘matrix multiplication’.

But what if we encode the action in a different way, and devise a more efficient algorithm for computing the action of a particular group element on a particular vector?

Joint work with RA Parker, PG Walsh, SA Linton (published 1998), constructed the 196882dimensional representation over 𝔽_{2} (i.e. the field {0, 1} defined by 1 + 1 = 0) in this way.

The idea is to

take some nice, big, 3-local subgroups (i.e. normalizers of 3-subgroups),

write their elements in a reasonably compact (‘sparse’) form,

and glue them together to make the whole group.

Joint work with PE Holmes (to appear in JLMS), constructed the 196882-dimensional representation over the field 𝔽_{3} = {0, 1, 2} of integers modulo 3.

Here we can work with 2-local subgroups, which are much bigger and nicer than the 3-local subgroups we used before.

We start with the centralizer C_{𝕄}(x) of an element x of order 2. This subgroup has the shape

2^{1+24} .Co_{1}

and the 196882-space breaks up as

298 ⊕ 98280 ⊕ 98304

But what makes this really nice is that the 98304 is a tensor product 24 ⊗ 4096, and the 98280 is monomial, so that all the information for this representation can be stored in a relatively small amount of space.

Moreover, the action of such an element on a vector in the 196882-space is easy to compute.

Also, the product of two elements in this subgroup can be computed fairly quickly, as can the inverse of an element.

Now all we need is one more element to generate the Monster.

To find one, centralize another involution:

C_{𝕄}(x, y) = 2^{2}.2^{11} .2^{22} .M_{24}

acting on the space as

(22 ⊕ 276)
⊕
(276 ⊕ 276 ⊕ 48576 ⊕ 49152)
⊕
(49152 ⊕ 49152)

Then we adjoin a suitable element t cycling the three 276-spaces and the three 49152-spaces.

To summarise, we generate the Monster with three elements

a, b generating the centralizer 2^{1+24} .Co_{1} of a certain involution x.

t conjugating x to y and y to xy, where y is a certain involution in C(x).

a and b are each stored as: a 24 × 24 matrix, a 4096 × 4096 matrix, a 298 × 298 matrix, and a monomial permutation on 98280 points and their negatives.

t is stored as a monomial permutation on 147456 points, a 64 × 64 matrix (acting identically on 759 64-spaces), and an 850 × 850 matrix.

Words in a and b can be readily evaluated, to give another element of C(x) in the same format.

Words involving t cannot be evaluated.

Applications

Elements of the Monster are now stored as words x_{1}t_{1}x_{2}t_{2} ⋯ where x_{i} ∈ C(x) and t_{i} = t^{±1}.

Element orders can be guessed by picking a ‘random’ vector v and finding the smallest n such that v(x_{1}t_{1}x_{2}t_{2} ⋯)^{n} = v.

Indeed, we can use the structure of 𝕄 to find two vectors v_{1} and v_{2} with the property that if v_{1}g = v_{1} and v_{2}g = v_{2} then g = 1. Thus we can prove that an element has the order we guessed.

The Monster is a Hurwitz group

i.e. it can be generated by X of order 2 and Y of order 3, with XY of order 7.

Proof: take random elements of orders 2 and 3, until you find a pair whose product has order 7. (Patience will be required: the probability in each case is about 10^{−8}, roughly equal to the chance of throwing ten sixes in a row.)

Check the orders of lots of words in X and Y, until you find elements of orders incompatible with being in a proper subgroup (orders 71 and 94, say).

The central problem

is that we cannot multiply elements of the Monster together: the words just get longer and longer until we are completely swamped. We need:

a word-shortener

We have one!

which relies on

• the fact that if a word represents an element of C(x), then we can calculate the compact form of this element by evaluating just 36 rows of the full 196882×196882 matrix, and

• if an involution conjugate to x commutes with x, then we can find a word of length 4 giving an element which realises this conjugation.

With these amazing tools, we can tackle real problems, such as determining the

maximal subgroups

It is easy to show that if H is a maximal subgroup of a simple group G, and K is a minimal normal subgroup of H, then

• H = N_{G}(K), and

• K is a direct product of isomorphic simple groups

Now let G = 𝕄. The case when K is a p-group was handled by RAW for p odd and Meierfrankenfeld and Shpektorov for p = 2.

The case when K is non-abelian was studied by Norton, RAW, etc., and reduced to the case K simple, and isomorphic to one of a specified list of 22 simple groups.

The 22 cases are: PSL_{2}(q) for q = 7, 8, 9, 11, 13, 16, 17, 19, 23, 27, 29, 31, 59, 71, and PSL_{3}(3), PSL_{3}(4), PSU_{3}(3), PSU_{3}(4), PSU_{3}(8), PSU_{4}(2), Sz(8) and M_{11} . Joint work with PE Holmes: we have dealt with 15 of these 22 cases. In particular there are (previously unknown) maximal subgroups PSL_{2}(59), PSL_{2}(71), PGL_{2}(29), PGL_{2}(19).