The symmetric group, 6

I quote here the review on MathSciNet for a paper which appeared in a conference proceedings in 1970. (This review, of course, was published in Mathematical Reviews, and now has been put on the website.) I have made one correction, which I will discuss below.

Tritter, A. L.,
A module-theoretic computation related to the Burnside problem. 1970 Computational Problems in Abstract Algebra (Proc. Conf., Oxford, 1967) pp.189-198 Pergamon, Oxford

To obtain a bound on the derived length of groups of exponent 4, the author studies the Burnside group G of exponent 4 with 8 generators. He wishes to compute whether or not the third derived group G(3) of G is contained in the ninth term of the lower central series of G (it is elementary to show that G(3) is contained in the eighth term). By considering the associated Lie ring the author observes that this problem is equivalent to computing a certain set of 8! vectors in a vector space of dimension 7! over GF(2), and determining whether or not a particular vector is linearly dependent on this set. In his algorithm for generating the vectors the author uses methods from campanology (bell-ringing).

At the time of publication the computations described had not been completed.

I don’t know whether the computations ever were completed. Alan Tritter is only credited with three publications on MathSciNet, one an (unreviewed) solution to a problem in the American Mathematical Monthly (with eleven co-authors, presumably the other eleven people who solved the problem), and one on the Morse distribution in IRE Transactions. The reason for mentioning it here is the word “campanology” (incorrectly given as “companology” in the on-line review – I haven’t checked the original). (Though, on second thoughts: perhaps the reviewer intended “companology” as a portmanteau word for “computational campanology”!)

Back in 1967 (the year before I arrived in Oxford as a graduate student), computers were not as big or fast as they are now. As the review suggests, the 8! vectors were obtained from a given vector by applying all the permutations in the symmetric group S8 in its action on the 7-dimensional space. The computer was unable to store all 8! images, or even all 8! permutations, so the procedure used was to generate and process the permutations one at a time, so that only one permutation needed to be stored. That is where campanology comes in: in fact, The Nine Tailors, a detective story by Dorothy L. Sayers which contains a good exposition of the subject, is in the bibliography of Tritter’s paper.

Campanology seems to be a peculiarly English art. Where else can you lie in bed on Sunday morning listening to the bellringers, or hear the sound across fields in the country on a weekday evening as they practise their art?

A bell tower contains a number of bells, tuned to the notes of the scale. (If you are in London, one of the best tourist experiences is a tour of the Whitechapel bell foundry, under the shadow of the minaret of the East London Mosque. The craft is a remarkable mixture of old and new: the bells are cast in moulds made of goat manure, and tuned using an oscilloscope.

“Ringing the changes” on a set of bells involves starting with “rounds” (the bells rung in sequence from highest to lowest) and returning to “rounds” after passing through every permutation of the order. (Actually, sometimes the lowest or tenor bell keeps last place throughout the changes; I will ignore that and consider just the bells that move.) The physical constraints of bellringing (they are very heavy, and are swung by pulling on ropes) restrict severely the possible moves which can be made from one change to the next: it is only possible to speed up or slow down a bell sufficiently to make it change places with its neighbour in the sequence, so that each permutation differs from the preceding one by a product of adjacent transpositions. There is also a human constraint: it takes several hours to ring the changes on a medium-sized peal of bells, and if one ringer makes a mistake once in this time then the whole thing is invalidated. So only a few permutations should be used, and the sequence should be made up of simple subsequences with as little complicated interchange between them as possible.

Of course these rules make a change-ringing procedure a very good way for a small computer to generate all elements of the symmetric group in turn! This was the use that Tritter made of campanology.

So the fact that it is possible to ring the changes on any set of bells is the theorem that the symmetric group is generated by adjacent transpositions. Indeed, these are the Coxeter generators, which demonstrate that the symmetric group of degree n is a group generated by reflections in Euclidean space of dimension n–1. However, it is not usual to use single transpositions exclusively in campanology. We also note that any two involutions generate a dihedral group, and the symmetric group is not dihedral for n>3, so at least three different generators will be needed.

There is one small technicality to discuss. Two bells can be transposed if their positions in the current sequence are adjacent, not if their numbers (their positions in “rounds”) are adjacent. This seems to mean that the actual generator applied depends on the current permutation. But, if we compose left-to-right, the effect is realised by multiplying on the left by the appropriate permutation. For example, to get from the permutation [2,3,5,4,1] to the permutation [2,5,3,1,4], we swap the 2nd and 3rd bells in the sequence, and also the 4th and 5th; this is accomplished by multiplying on the left by (2,3)(4,5). (I use square brackets for the “passive form” of the permutation, the ordered sequence which results from applying it to the natural order, and round brackets for the expression as a product of transpositions.)

Note, incidentally, that in the nineteenth century the term “permutation” meant the ordered sequence, and the corresponding mapping was called a “substitution”, so that the great nineteenth-century group theorists studied “substitution groups”. I think this is a much more sensible terminology. I do not know when it was lost. but I very much doubt that we can get back to using it!

Anyway, the permutations (1,2)(3,4)… and (2,3)(4,5)… (where the last point n is fixed by the first permutation if n is odd, and by the second if n is even) generate a dihedral group of order 2n (the group of symmetries of a regular n-gon with a slightly unusual numbering). This contains the n-cycle (1,2,4,6,…,5,3); so, as is well-known, these two involutions together with the transposition (1,2) generate Sn. How to take the human limitation into account? By alternating the first two permutations for 2n–1 steps, we work around a coset of the dihedral group. If we can use the remaining permutation to move from coset to coset, then most of the sequence will consist of a simple memorable pattern, and only the moves from coset to coset can potentially give trouble.

Incidentally, the book Music and Mathematics: from Pythagoras to Fractals, edited by John Fauvel, Raymond Flood and Robin Wilson, contains an excellent exposition of campanology by Dermot Roaf and Art White. I remember standing under an umbrella at Carfax in Oxford listening to the world premiere of one of Art White’s compositions several years ago!

There is much more to be said about generating the symmetric group, not all of which can be covered here. A few things in brief:

  • If we choose two random permutations, with probability 1/4 they are both even permutations and cannot generate the symmtric group. But this is the only significant obstruction. I mentioned (in Part 5) John Dixon’s beautiful theorem asserting that two random permutations generate the symmetric or alternating group with high probability. If we choose two random permutations, the probability that they have a common fixed point is easily calculated to be about 1/n; if so, then they lie in the subgroup Sn-1 fixing a point. This is now known to be the leading term in the asymptotic probability that the two permutations fail to generate the symmetric or alternating group.
  • Extensions are known: if we choose three random involutions, or a random involution and a random element of order 3, then with high probability they will generate the symmetric or alternating group.
  • A remarkable result of John Bray, Marston Conder, Charles Leedham-Green and Eamonn O’Brien (preprint here) shows that there is a presentation for the symmetric group with an absolutely bounded number of generators and relations and where the entire presentation can be written with O(log n) bits.

Previous | Next

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in books, exposition, symmetric group and tagged . Bookmark the permalink.

3 Responses to The symmetric group, 6

  1. Pingback: The symmetric group, 5 « Peter Cameron's Blog

  2. Pingback: Reimann, average calculations for cryptanalysis | Peter's ruminations

  3. Pingback: From Turing to Cameron | Peter's ruminations

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s