Peter Sarnak’s Hardy Lecture

Yesterday, Peter Sarnak gave the London Mathematical Society’s 2020 Hardy Lecture (remotely). He talked about gaps in the spectra of connected cubic graphs. It was a talk properly described as a tour de force, applying to the problem ideas from algebraic geometry (Weil’s proof of the Riemann conjecture for curves over finite fields), probability (Benjamini–Schramm measure), and fractal geometry (the Julia set of a real quadratic), among many other things.

I won’t attempt to describe more than the first few ideas in the talk. I think it was filmed, and a video will no doubt appear at some point; I do urge you to watch it.

Let X be the set of all finite connected cubic graphs (graphs of valency 3). We are interested in spectral questions; the spectrum of a member of X is the set (or multiset) of eigenvalues of its adjacency matrix. Since the graphs are regular, the adjacency spectrum is a simple transform of the Laplacian spectrum. It is well known that the eigenvalues of such a graph are all real, and lie in the interval [−3,3]; the value 3 is always a simple eigenvalue, and −3 is an eigenvalue if and only if the graph is bipartite.

A subinterval I of [−3,3] is a gap if there exist arbitrarily large graphs in X with no eigenvalues in this interval; it is maximal if there is no strictly larger interval which is a gap.

The first gap is (2√2,3), due to Alon and Boppana; the maximality of this gap depends on the existence of Ramanujan graphs, shown in the 1980s by Margulis and by Lubotzky, Phillips and Sarnak. As the name suggests, the construction of such graphs uses a substantial amount of number theory related to work of Ramanujan. The speaker told us that he had been rash enough to state that the construction would not be possible without number theory; but he was proved wrong (and taught to be more cautious) when a group of physicists found a construction using Lee–Yang theory in statistical mechanics.

I was so impressed with the Lubotzky–Phillips–Sarnak paper when it came out that I gave a seminar talk to the pure mathematicians at Queen Mary expounding it.

Then Peter Sarnak mentioned two other potential gaps, interest in which had come from real applications: gaps at −3, important in the theory of waveguides; and gaps at 0, important in the Hückel theory of fullerenes (molecules made of carbon atoms forming polyhedra with only pentagonal and hexagonal faces, like the football (which chemists call the buckyball). I will just repeat some of what he said about the first of these two.

He and Alicia Kollár (and others) have shown the remarkable result that [−3,−2) is a maximal gap. He associates the name of Alan Hoffman with this gap. The name is entirely appropriate. Hoffman did a lot of work on graphs with least eigenvalue −2, but in the end it was Jean-Marie Goethals, Jaap Seidel, Ernie Shult and I who proved the theorem he had been trying to prove, giving a virtually complete description of such graphs. I have described our result here; Peter Sarnak was kind enough to describe the paper as “beautiful”, and I don’t mind shining in reflected glory for a moment.

So here is the path from our theorem to the gap described above; the details were not given in the lecture.

We showed that, with finitely many exceptions (all realised in the exceptional root system E8), all connected graphs with smallest eigenvalue −2 (or greater) are what Hoffman called generalised line graphs. Fortunately I don’t have to tell you what these are, since it is an easy exercise to show that if a generalised line graph is regular, then it is either a line graph or a cocktail party (n couples attend a cocktail party, and each person talks to everyone except his/her partner). Moreover, if a line graph is regular, then it is the line graph of either a regular graph or a semiregular bipartite graph.

The cocktail party graph has valency 2n−2, which is even; so is not possible in our situation. The line graph of a regular graph of valency k has valency 2k−2, which is also even. The line graph of a semiregular bipartite graph with valencies k and l has valency k+l−2. So in our situation we only have to consider line graphs of semiregular bipartite graphs where the valencies in the two bipartite blocks are 2 and 3.

Now such a graph is obtained from a smaller graph Y in X (namely, the induced subgraph of the distance-2 graph on the set of vertices of valency 3) by inserting a vertex in each edge. So its line graph is built from Y by replacing each vertex of Y by a triangle, or sewing in triangles.

We conclude that, with finitely many exceptions, any graph in X with no eigenvalues in [−3,−2) is obtained from a graph in X by sewing in triangles. Moreover, such graphs are line graphs of graphs with more edges than vertices, and so really do have −2 as an eigenvalue; so the gap is maximal.

Posted in events, exposition | Tagged , , , , , | Leave a comment

National Windrush Day

Today is National Windrush Day. I’d like to put on record (for what it’s worth) my wholehearted support and sympathy for the Windrush generation.

Although I have never suffered the ill-treatment meted out to some of the Windrush generation by the Home Office, I feel close enough to them to have some appreciation. I arrived in the UK by ship from a Commonwealth country in 1968, and was given indefinite leave to remain in 1971. The only proof I have for this is a smudged stamp in an expired passport. On one occasion I was told by an immigration officer that I had no right to stay in the UK, and that he could exclude me with no right of appeal.

According to today’s news, the government, having received a report on the Windrush generation, have responded by setting up yet another inquiry. Will anything change?

Posted in history | Tagged | Leave a comment

Jan Saxl

This morning brought the news that Jan Saxl died on Saturday.

Jan arrived in Britain in the early autumn of 1968, as did I: a very significant time for Czechoslovakia. (I spent six weeks in Earls Court, in London, before term started in Oxford; the first I knew about events was when I went to see a Soviet exhibition in Holland Park and found the exhibition hall surrounded by demonstrators.)

He is my mathematical brother, a student of Peter Neumann, taking his DPhil just two years after I did. (I have a vague memory that I was nominally his supervisor for a very short time while Peter Neumann was away, but I may be confusing him with David Cooper.) We collaborated on four papers; the best-known is the proof of the Sims conjecture, joint also with Cheryl Praeger and Gary Seitz.

Of course he had many collaborations with other mathematicians, especially Martin Liebeck and Cheryl Praeger, and produced some work of very great significance to the finite group theory community and more widely.

Jan was a good friend. When I directed a six-month programme on Combinatorics and Statistical Mechanics at the Isaac Newton Institute in 2008, he arranged for me to have a visiting fellowship, with a flat in Rose Crescent (up the stairs above the famous Gardenia) and lunches and dinners with the College fellows; the small price I had to pay was to give “three or four lectures” to the maths students in the College, which of course I was delighted to do.

Jan is someone who touched many people deeply. The world seems a greyer place without him. I hardly know what to say.

Posted in Uncategorized | Tagged , | 5 Comments

S. S. Shrikhande

News reached me today of the death of S. S. Shrikhande, at the age of 102.

I have written about him before; in particular, here, I discussed two things for which he was perhaps best known, which can bear repeating.

One of these is his role, with Bose and Parker, as one of the trio of Euler spoilers who showed that a pair of orthogonal Latin squares (i.e. a Graeco-Latin square) exists for all orders except 2 and 6, disproving a conjecture of Euler (who thought that such a thing would not exist for orders congruent to 2 modulo 4).

The other is a lovely characterisation of a class of strongly regular graphs. The n×n grid graph (with two vertices joined if they lie in the same row or column of a square array) is regular, has the property that two adjacent vertices have n−2 common neighbours, while two non-adjacent vertices have 2 common vertices. Shrikhande showed that there is just one further graph with this property; it is now known as the Shrikhande graph.

The link arises because the 4×4 grid graph and the Shrikhande graph have the properties that their complements are Latin square graphs: the vertices are again the points of the n×n array, filled with the letters of a Latin square, so that two vertices are joined if they lie in the same orw or column or contain the same letter. There are just two different Latin squares of order 4, the Cayley tables of the Klein group and the cyclic group; the first gives the grid graph of order 4, the second the Shrikhande graph.

We know now that the Shrikhande graph is not an unexpected accident, but is related to the existence of the exceptional root system of type E8.

Posted in Uncategorized | Tagged , | 3 Comments

The geometry of diagonal groups

This is an interim report on ongoing work with Rosemary Bailey, Cheryl Praeger and Csaba Schneider. We have reached a point where we have a nice theorem, even though there is still a lot more to do before the project is finished.

Primitive permutation groups

This is an attempt to understand and characterise a class of permutation groups. So I begin with some reminders. We always assume that G is a permutation group on a set Ω, usually but not always assumed finite. We say that G is transitive if any point of Ω can be moved to any other by an element of G (in other words, G preserves no non-empty proper subset of Ω). We also say that G is primitive if it preserves no non-trivial equivalence relation on Ω (the trivial equivalence relations, equality and the “universal” relation with a single class, are preserved by any permutation group).

In the interests of full disclosure, I should point out that the only equivalence relations on a 2-element set are the trivial ones, so even the identity group of degree 2 is primitive according to this definition. This is usually excluded by adding to the definition the requirement that the group is transitive.

According to a simplified version of the O’Nan–Scott Theorem, there are four kinds of finite primitive group:

  • non-basic groups;
  • affine groups;
  • diagonal groups;
  • almost simple groups.

Almost simple groups are the ragbag here. The reason that the O’Nan–Scott Theorem is almost contemoraneous with Gorenstein’s announcement of the Classification of Finite Simple Groups is that, without CFSG, there is almost nothing we can say about this class, since all we know is that they lie between a non-abelian simple group and its automorphism group, and we have no information at all about the way they act except that it is primitive. For the other classes, the action is specified, and we are in a stronger position, as I will describe.

In the affine and non-basic cases, the groups are automorphism groups of well-known and well-studied geometric/combinatorial structures. The aim of the project is to understand the structures on which diagonal groups act.

Affine groups

These are groups of permutations of vector spaces which contain the translation group of the space as a normal subgroup, and are generated by this together with a group of linear transformations of the space. The maximal affine group (for any given vector space) takes the group of linear transformations to be the full general linear group on the space (all invertible linear transformations).

These groups preserve a well-known structure, the affine geometry on the vector space, whose points are the vectors, and whose subspaces are the cosets of the vector subspaces.

We may always assume that the field is a prime field (that is, the integers mod p for some prime p), by simply restricting scalars.

Non-basic groups and Cartesian lattices

Let A be an alphabet of size q, and let Ω be the set of all words of length n over A. The maximal non-basic group is generated by two kinds of transformation:

  • independent permutations on the letters in the ith coordinate of a word, for all i (these form the direct product of n copies of the symmetric group on the alphabet A);
  • permutations of the coordinates (these form the symmetric group of degree n).

The group generated is the wreath product of the symmetric groups of degree q and n.

What natural structure is preserved by this group? There are two possible answers.

A coding theorist would say, the Hamming graph, whose vertex set is the set of all words, in which two words are adjacent if they differ in just one position (that is, a single error will transform one into the other). So the distance of two vertices in the Hamming graph is the number of errors required to turn one into the other. The automorphism group of the Hamming graph is the wreath product just constructed.

We need a slightly different answer. For every subset I of {1,…,n}, define an equivalence relation ≡I on Ω as follows: two words are equivalent if they agree in all coordinates except those in I. The corresponding partitions PI of Ω form a sublattice of the partition lattice on Ω, and the map I → PI is an isomorphism from the Boolean lattice of subsets of {1,…,n} to this lattice just constructed, which we call a Cartesian lattice associated with A and n. Its automorphism group is again the wreath product of symmetric groups. Its dimension is n.

Two features of the Cartesian lattice should be noted.

The maximal proper partitions in the lattice (corresponding to the case where I = {1,…,n}\{i} for some i) form what Cheryl Praeger and Csaba Schneider call a Cartesian decomposition of Ω in their book Permutation Groups and Cartesian Decompositions. They generate the lattice by taking meets (infima).

The minimal proper partitions in the lattice correspond to the case where I contains just a single element. The parts of each minimal partition are maximal cliques in the Hamming graph. These minimal partitions also generate the lattice, by taking joins (suprema).

For n = 3, think of a cube; the maximal partitions are those into slices parallel to the faces of the cube (which we will call layers), while the minimal partitions are those into lines parallel to the edges.

Latin squares

A Latin square can be regarded as a square array of size q×q with entries from an alphabet of size q, so that each letter occurs once in each row and once in each column of the array.

Latin squares exist in great profusion. (The Cayley table of a group is a Latin square; but these form only a tiny fraction of the total.) The precise number (as function of q) is not known for q > 11; upper and lower bounds are known, both growing faster than the exponential of q2.

We need to interpret Latin squares a bit differently. Let Ω be the set of q2 cells. We have three partitions of Ω:

  • the partition R into rows;
  • the partition C into columns;
  • the partition L into letters (two cells in the same part if they contain the same letter).

These three partitions together with the partitions E (equality) and U (universal) form a sublattice of the partition lattice. For us, the crucial property is:

Any two of R,C,L, together with E and U, form a Cartesian lattice of dimension 2.

Latin cubes

Before plunging into the general case, I will describe Latin cubes; it turns out that the heart of our proof involves this case.

Here we have to face the fact that there are different definitions of Latin cubes. In all cases we have a q×q×q array of letters. I will use the term layer for a slice of the cube parallel to one of the faces (containing q2 cells), and line for the intersection of two non-parallel layers (containing q cells).

By far the commonest definition of Latin cube requires an alphabet of q letters, arranged so that each letter occurs once in each line. But this is not what we want. So I will call it a Latin cube of the first kind, and move on to the definition we do want.

A Latin cube of the second kind has an alphabet of q2 letters, arranged in the cube such that each layer contains each letter exactly once.

Another definition. A Latin cube of the second kind is regular if the sets of letters on two parallel lines are either equal or disjoint. Thus, for each parallel class of lines, the letters are partitioned into q sets of size q so that each line has the letters from one of these sets, and all q sets occur on the lines in a given layer.

This definition is from a paper of Preece, Pearce and Kerr. They do not attempt to classify these things, naturally enough: if Latin squares are wild, you might expect Latin cubes to be even wilder! But, surprisingly, it is not so.

Now let A be a group of order q. We can take the three coordinates of the cube as being elements of A. Take the set of q2 letters to consist of all triples [x,y,z] of group elements satisfying xyz = 1. In cell (a,b,c), put the triple [b−1c,c−1a,a−1b]. It is not too hard to see that this is a Latin cube of the second kind, and is regular.

Now here is our theorem about these:

Theorem Every regular Latin cube of the second kind comes by the above construction from a group, unique up to isomorphism.

As I said, this is the heart of the argument; the proof of it is the most complicated part of the whole thing, and I will not attempt to describe it here. Note that the group emerges naturally from the combinatorial structure.

Diagonal structures and groups

After that interlude, back to the main business. Let A be a group and m a positive integer. We take Ω = Am. Consider the following subgroups of Ω:

  • Ai, the ith coordinate subgroup (with the identity in all positions different from the ith), for i = 1,…,m;
  • A0, the diagonal subgroup consisting of the m-tuples with all entries equal.

Let Pi be the partition of Ω into right cosets of Ai, for i = 0,…,m.

We claim that any m of these m+1 partitions are the minimal non-trivial elements of a Cartesian lattice. This is clear for P1,…,Pm. For the others, note that we can swap P0 and P1, fixing the other partitions, by the map taking (a1,a2,…,am) to (a1−1,a1−1a2,…,a1−1am), and so we can permute the m+1 partitions arbitrarily.

The set-theoretic union of the Cartesian lattices generated by all these m-tuples of partitions is closed under join (but not meet), and so forms a join-semilattice. This is the diagonal semilattice.

The full diagonal group D(A,m) is the automorphism group of the (m+1)-set of partitions, or of the semilattice it generates. It contains (and is generated by)

  • the group Am, acting by right multiplication;
  • the diagonal group A0, acting by left multiplication;
  • automorphisms of A, acting simultaneously on all coordinates;
  • the symmetric group of degree m+1, permuting the partitions (generated by the symmetric group of degree m permuting the coordinate subgroups, and the transposition defined above swapping P0 and P1).

The main theorem

Now I can state the main theorem.

Theorem Let P0,…,Pm be partitions of Ω, for m ≥ 2. Suppose that any m of these partitions are the mimimal non-trivial elements of a Cartesian lattice on Ω.

  • If m = 2, then the three partitions, together with the two trivial partitions, form a Latin square, unique up to isotopy.
  • If m > 2, then there is a group A, unique up to isomorphism, such that the m+1 partitions are the minimal non-trivial elements in a diagonal semilattice for D(A,m).

This theorem has a similar structure to the Veblen–Young characterisation of projective spaces. In the low-dimensional case, the objects are “wild” (projective planes there, Latin squares here); in all higher dimensions, they are described by algebraic structures (skew fields there, groups here).

The proof is not so difficult from what we have already seen. For m = 2, the assertion is almost obvious. For m = 3, we have to match up the description of the Latin cube with that of the diagonal structure. Finally for m > 3, the proof is by induction.

Final note: The theorem makes sense in the infinite case (m is finite but the set Ω and the output group A are allowed to be infinite). We think our proof works for these as well. All this, of course, is subject to careful checking!

Posted in doing mathematics, exposition | Tagged , , | 3 Comments

John Conway

News came this morning that John Conway has died.

I hardly know where to begin paying tribute to such a polymath. But perhaps I will just tell a story which shows several things about him, not least his breadth of interest and love of fun.

This happened at a conference somewhere in North America. I was chairing the session at which he was to speak. When I got up to introduce him, his title had not yet been announced, and the stage had a blackboard on an easel. I said something like “The next speaker is John Conway, and no doubt he is going to tell us what he will talk about.” John came onto the stage, went over to the easel, picked up the blackboard, and turned it over. On the other side were revealed five titles of talks. He said, “I am going to give one of these talks. I will count down to zero; you are to shout as loudly as you can the number of the talk you want to hear, and the chairman will judge which number is most popular.”

So he did, and so I got to hear the talk I wanted to hear.

RIP John, the world is a poorer place without you.

Posted in Uncategorized | 4 Comments

The B. B. Newman Spelling Theorem

This is a guest post by Carl-Fredrik Nyberg Brodda, a recent Masters student at St Andrews and currently a PhD student at the University of East Anglia. The story has personal resonance for me, because it turns out that B. B. Newman was a student at the University of Queensland at about the same time I was, though at a campus 1500km away from Brisbane where I studied – so perhaps I can be forgiven for never having met him. Anyway, here is the extraordinary story.

The full version of this can be found on the arXiv.

A group presentation is a very compact and natural way to define a group, and can carry a great deal of information about the group it presents. For example, if we take the presentation ⟨a, b | ab=ba⟩, we can directly read that the group it presents is 2-generated, abelian, and torsion-free, and hence must be isomorphic to Z×Z. Beyond compactness, group presentations have a key selling point: they allow us to ask questions about presentations of groups of a combinatorial nature, and, by extension, ask such questions about the groups themselves. A typical example of such a question is asking about the structure of groups defined by presentations ⟨A | w=1⟩ with only a single defining relation, commonly called one-relator groups. Examples of one-relator groups include free groups, the fundamental groups of closed surfaces, and the famous Baumslag-Solitar groups ⟨a, b | b−1amb=an⟩ for m,n non-zero integers. There is a natural partition for one-relator groups into those that have elements of finite order, the torsion case, and those that are torsion-free.

It is known that a one-relator group has torsion if and only if the defining word is a proper power of some other word, i.e. the only time that one has torsion is precisely when one expects it. A common adage in the theory of one-relator groups is that the torsion case is generally more well behaved than the torsion-free. This is in great part because of the following important result from 1968.

Theorem (The B. B. Newman Spelling Theorem)
Let G = ⟨A | Rn=1⟩ be a one-relator group with torsion such that R is cyclically reduced and not a proper power. Let wF(A) be a word representing the identity element of G. Then w contains a subword u such that either u or u−1 is a subword of Rn, and such that the length of u is strictly more than (n−1)/n times the length of Rn.

This is similar to a spelling theorem obtained by Dehn for fundamental groups of closed surfaces, and to Greendlinger’s Lemma in small cancellation theory. There are numerous consequences of the theorem for one-relator groups with torsion, with the most important that it shows that such groups are word-hyperbolic, in the sense of Gromov, paving the way for the use of methods from geometric group theory to one-relator groups with torsion. However, seemingly no information about the history of the theorem or of B. B. Newman was available online, which led me to investigate this matter for myself.

The spelling theorem is originally from 1968, and the proof first appears in the PhD thesis of B. B. Newman, at the University of Queensland. However, this thesis was not available anywhere online, and neither was any information as to what two names the Bs were abbreviating. And so, writing to the university library, the hunt was on. Queensland knew some details about Bill Bateup Newman, born in 1936. At Queensland, he had there received an MSc and a BSc, but there was no sign of a doctoral degree, nor any sign of a thesis, nor even any record of who might have supervised Bill. They did have his master’s thesis, however, which was entitled Almost Just Metabelian Groups. There, in the preface, Bill had thanked his supervisor, a Dr M. F. Newman. After some digging, I wrote to now Prof Emeritus Michael Frederick Newman, at the Australian National University in Canberra. He knew some more: Bill’s PhD supervisor had been Gilbert Baumslag, one of the most influential combinatorial group theorists of the 20th century. This came as quite a shock, since Baumslag had been based most of his academic life at the City College of New York, more or less antipodal to Queensland.

Nevertheless, I wrote to New York, and received an email a few days later. However, this email was not from New York. Out of nowhere, I had received an email from B. B. Newman; I learned much later that Mike Newman had contacted Bill, finding his email through a colleague of a widow of a former colleague’s (?!) of Bill’s. Now long since retired, Bill filled in the pieces of the picture I was missing. His doctoral studies had started at Queensland, but not at the main campus in Brisbane. Instead, he had been based in Townsville, almost a thousand miles away, at the University College of Townsville, a college of Queensland. By 1968, he had finished writing his thesis, and was ready to graduate by 1969. Around that time, however, the college officially became James Cook University, the second university in Queensland; hence Bill was given the option to graduate with a degree from either Queensland or James Cook, and chose the latter. This explained why Queensland did not have a copy of his thesis, as no copy was ever submitted there.

As to the matter of his supervision, it was sporadic – Bill recalls a story of how Baumslag sent him a letter written on a German hotel letterhead, told him he was writing from England, and had two weeks later posted the letter from South Africa. It was enough that even Bill himself was not entirely certain on the matter. He thought it might have been Mike Newman initially, which then changed when Baumslag visited Australia in 1964: Baumslag agreed to supervise Bill, but disappeared almost as soon as he had appeared. Not long thereafter, Baumslag sent Bill a copy of a draft of a chapter on one-relator groups from a forthcoming book on combinatorial group theory by Magnus, Karass, and Solitar, and, in Bill’s own words, this was “the most useful help [Baumslag] provided”. This prompted the fruitful investigation into one-relator groups that would culminate in the Spelling Theorem.

After spending some time working with one-relator groups, Bill was due for a sabbatical leave, and Baumslag was in 1967 able to set up a lectureship for him at Fairleigh Dickinson University in Teaneck, New Jersey. This meant that the two mathematicians were able to meet face to face again. At their very first meeting, when explaining how far he had come in proving a Spelling Theorem, Bill realised that his proof was correct. Baumslag, enthusiastically, suggested that the theorem be presented at Magnus’ weekly group theory seminar at the State University in Washington Square, and this came to pass. In the audience that day were both Magnus and Solitar, two of the three who had taught Bill extensively about one-relator groups. What was more, one of these was, of course, Wilhelm Magnus, the man who had proven the Freiheitssatz, the most significant result on one-relator groups to date. Unfazed, Bill presented his results, and concluded his presentation. At that point, Magnus had a remarkable reaction. He jumped to his feet, and exclaimed for the entire room to hear: “I don’t believe this! I don’t believe this!”. In Bill’s own words, he was saying that “he could not believe that an unheard of mathematician, from some unknown university in outback Australia, could have come up with these results”. But the proof was correct.

After my correspondence with Bill, there yet remained a major unresolved issue in the recovery of the thesis. I wrote an abridged email to James Cook containing only the essentials of the story up to that point, for fear of the thesis slipping through my fingers in the time it would take them to read the entire story. Due to time differences, I woke up the next morning pleasantly surprised, having discovered that I had been copied into an overnight flurry of emails sent back and forth between the archivists, heads of research, and librarians at James Cook. Then, at last, the final email of the conversation stated that the thesis had been found, alive and well, and I could not have been happier. Shortly thereafter, I received an email containing the scanned thesis. I was able to read through the original proof, just as I had wanted, and I do not believe that I will ever read a proof with as much enthusiasm again. The thesis was later uploaded to James Cook’s online archives, and also passed on to Queensland, so that they may quickly help anyone in the future digging into the same story.

Carl-Fredrik Nyberg Brodda

Posted in exposition, guest posts, history | Tagged , , , , , , | 2 Comments

More on derangements

Francis Bacon, in The New Organon, developed a famous metaphor:

Those who have handled sciences have been either men of experiment or men of dogmas. The men of experiment are like the ant, they only collect and use; the reasoners resemble spiders, who make cobwebs out of their own substance. But the bee takes a middle course: it gathers its material from the flowers of the garden and of the field, but transforms and digests it by a power of its own. Not unlike this is the true business of philosophy; for it neither relies solely or chiefly on the powers of the mind, nor does it take the matter which it gathers from natural history and mechanical experiments and lay it up in the memory whole, as it finds it, but lays it up in the understanding altered and digested. Therefore from a closer and purer league between these two faculties, the experimental and the rational (such as has never yet been made), much may be hoped.

At present, the ants and bees are under lockdown, and are unable to go out and collect their experimental material. But the spiders (the pure mathematicians) can keep themselves sane by sitting at home spinning, so that is what I have been doing for the last couple of weeks. Parts of the resulting web may appear here from time to time.

Last word from the Isaac Newton Institute

At the third (and final) workshop in the GRA programme at the Isaac Newton Institute, Aner Shalev gave a talk remotely.

One topic he mentioned was derangements. Jordan proved in the nineteenth century that a finite transitive permutation group on a set of size bigger than 1 contains a derangement, an element with no fixed points. Since the derangements form a union of conjugacy classes, a finite simple group (in any transitive permutation action) is generated by its derangements. Aner announced that he and his coauthors (Michael Larsen and Pham Huu Tiep) were close to a proof that, if the simple group is sufficiently large, then any element of the group is the product of two derangements. The proof has subsequently been completed, and the paper is on the arXiv.

In the discussion, Michael Giudici mentioned a result that he, together with Rosemary Bailey, Gordon Royle, and me, have had on the back burner for a few years now, because we are stuck on one seemingly small point. But I see no harm in announcing here what we have been able to do. (We started work on this when Rosemary and I visited Perth in 2016: I was recovering from shingles, and had just had a few weeks’ holiday in Adelaide, where I did a little side project on the voyage of Nicolas Baudin reported here and in two preceding posts.)

I have discussed derangements before, for example here, but not this particular aspect.

The basic set-up

First, a finite transitive permutation group G actually contains many derangements. Arjeh Cohen and I showed that, if the group acts on n points, then at least a fraction 1/n of the elements of the group are derangements. More relevant here is a discussion of the subgroup of G generated by derangments. In 1982, H. Zantema (who I think was a student of Arjeh Cohen) published a 50-page paper in Manuscripta Mathematica entitled “Integer valued polynomials over a number field”. To stress once again that there are important connections between number theory and derangements, the paper contains a proof of the following theorem. I will use D(G) for the subgroup of the finite transitive permutation group G which is generated by the derangements in G.

Let G be a finite transitive permutation group of degree n>1. Then D(G) is transitive and contains every element of G whose number of fixed points is different from 1.

I will give the proof, since it follows easily from the Orbit-Counting Lemma (asserting that the average number of fixed points of elements of a finite permutation group is equal to the number of orbits of the group). Let G be a transitive permutation group. Then ∑G(fix(g)−1) = 0, where fix(g) is the number of fixed points of g. Let H = D(G), and suppose that H has d orbits. Then ∑H(fix(g)−1) = (d−1)|H|. So ∑G\H(fix(g)−1) = −(d−1)|H|. But this sum is non-negative, since all the elements g with fix(g)−1 < 0 have been included in H. We conclude that d = 1 and that every element g in G\H has fix(g) = 1.

My coauthors and I added an extra piece to this: D(G) permutes semiregularly the set of G-orbitals (the orbits of G on ordered pairs of distinct elements).

From this we see that the index of D(G) in G divides n−1, with equality if and only if G is sharply 2-transitive.

The easiest examples of groups G with D(G) ≠ G are Frobenius groups, transitive (but not regular) permutation groups in which the stabiliser of any two points is the identity. Frobenius showed that, in such a group, the identity and the derangements form a normal subgroup, the so-called Frobenius kernel. Thus, in this case, D(G) is the Frobenius kernel, and G/D(G) is isomorphic to the Frobenius complement (the one-point stabiliser).

This is already enough to draw one conclusion: for any Zassenhaus group G, we have D(G) = G. (A Zassenhaus group is a 2-transitive group in which the 3-point stabilisers are trivial but the 2-point stabilisers are not.) Suppose for a contradiction that G is a Zassenhaus group with D(G ≠ G. If H is the 1-point stabiliser, then HD(G) is a proper subgroup of H, and all the elements of H outside this subgroup are derangements (since they fix only the point stabilised by H); so H is generated by these derangements, thus H = D(H). But H is a Frobenius group; so this contradicts Frobenius’ Theorem.

We conjectured that, if G is not a Frobenius group, then the index of D(G) in G is at most √n−1. This is true if G is imprimitive, or if it is primitive but not of affine type. As I will explain below, the affine type is the most mysterious …

But that is not what I want to explain here.

Frobenius complements

The structure of Frobenius groups is now well understood. A famous theorem of Thompson shows that the Frobenius kernel must be nilpotent. The possible Frobenius complements were determined by Zassenhaus. There is a detailed account of this in Passman’s book Permutation Groups; I used to have a copy but alas it disappeared some time ago. A Frobenius complement is either metacylic (that is, has a cyclic normal subgroup with cyclic quotient) or has a subgroup of index at most 2 which is a direct product of SL(2,3) or SL(2,5) with a metacyclic group of odd order.

I will say a bit more about this. A group H is a Frobenius complement if and only if it acts as automorphisms of a group N so that non-identity elements of H fix only the identity of N. By Thompson’s theorem, N is nilpotent, so it has a characteristic elementary abelian subgroup T, on which H acts. Thus we can assume without loss of generality that N is elementary abelian, so that H is a linear group over a finite prime field. Linear groups will reappear later …

Here is a proof that a Frobenius complement has at most one element of order 2. Remember that elements of the Frobenius complement act as automorphisms of the Frobenius kernel. So the claim is that an automorphism of order 2 of a finite group, which fixes only the identity, must be the inversion map.

This is proved by a nice two-step argument. Let α be an automorphism of G. For the first step, assume that α fixes only the identity. Consider the map that takes g to g−1.gα. This is one-to-one; for if g−1.gα = h−1.hα, then hg−1 = (hg−1)α, and so by assumption g = h. Since G is finite, this map is onto, so every element is of the form g−1.gα.

For the second step, we assume that α has order 2. Then applying α to g−1.gα, we see that

(g−1.gα)α = g−α.g = (g−1.gα)−1,

so α maps every element of G to its inverse.

Incidentally, a group having such an automorphism must be abelian (of odd order), since

gh = (h−1g−1)−1 = (hα.gα)α = hg.

Now groups G with a unique involution have cyclic or generalized quaternion Sylow 2-subgroups, so if Z is the central subgroup of order 2, then G/Z has cyclic or dihedral Sylow 2-subgroups. Conversely, a group with cyclic or dihedral Sylow 2-subgroups has a unique central extension by a group of order 2 which contains a unique involution. This is discussed here.

But Frobenius complements are much more restricted, as described in the result mentioned earlier.

But that’s not all

The vast majority of transitive groups up to degree 47, or primitive groups of degree up to 4095, satisfy D(G) = G. Of those which don’t, a considerable number are Frobenius groups, and almost all the rest have the quotient G/D(G) isomorphic to a Frobenius complement.

But before we could make a serious conjecture along these lines, we found two primitive groups of degree 625 where this was not so; in one of them, the quotient was the Klein 4-group, in the other the symmetric group of degree 3.

So we are left with the question:

Which finite groups H can occur as G/D(G) for some finite permutation group G?

Note in passing that this is an “inverse problem” in group theory of the sort that Carlo Casolo and I, along with João Araújo and Francesco Matucci, were working on just before Carlo’s untimely death in March.

While we were in the Isaac Newton Institute before the shutdown, Michael Giudici and I managed to find an explanation for some of these examples, and to give a construction which produces more examples. However, we are very far from being able to show that every finite group arises. In fact, all our examples are quotients of Frobenius complements, and we are tempted to conjecture that this is the answer.

I will give a brief hint. The paper will go on the arXiv soon, and I will provide the link.

An extension to the Orbit-Counting Lemma

The Orbit-Counting Lemma asserts, in particular, that the average number of fixed points of elements of a finite transitive permutation group G is 1. More generally, the same holds for the elements of any coset of G in the symmetric group.

Here is the proof; it is only a very slight modification of the proof of the original. I give the proof for left cosets; note that any right coset Gt of a transitive group G is a left coset of another transitive group, namely t(t−1Gt).

Count pairs (a,g) with a∈Ω (the permutation domain) and gG such that atg = a. For each of the n choices of a, there are |G|/n elements g mapping at to a. So there are |G| such pairs. But, counting the other way, we get the sum of the numbers of fixed points of the |G| elements of the coset tG.

Affine groups

Let V be a finite vector space. An affine group on V is a group of transformations of the form v → vt+c, where cV and tH, where H is a group of linear maps on V. This group is a semidirect product of the additive group T of V by H.

Let G = T.H be an affine group. Certainly all the non-zero translations are derangements, so T ≤ D(G). By the extended Orbit-Counting Lemma, the average number of fixed points of the elements of a coset Th is 1, so there are two possibilities:

  • Th contains a derangement, whence tD(G);
  • every element of Th has exactly one fixed point. In particular, h fixes no non-zero vector, and so does not have 1 as an eigenvalue.

The conclusion is that, if R(H) is the subgroup of H generated by elements which have an eigenvalue 1, then D(G) is the semidirect product T.R(H).

Thus our questions for affine groups are equivalent to the following question for linear groups:

Let H be a linear group on a finite vector space V, and R(H) the subgroup of H generated by elements having eigenvalue 1. What can be said about

  • the index |H:R(H)|,
  • the structure of H/R(H)?

An example

We found a number of examples, including an infinite family. I will just present one here.

Let V be the tensor product of two 2-dimensional vector spaces over the field of five elements. Thus |V| = 625. Let H be the central product of the dihedral group of order 12 acting on the first factor and the quaternion group of order 8 acting on the second.

In the dihedral group of order 8, non-central involutions all have eigenvalues 1 and -1, the other non-central elements do not have eigenvalues in the field of order 5. In the quaternion group, the eigenvalues of the non-central elements are fourth roots of unity in the field. We get the eigenvalues of elements of the central product by multiplying eigenvalues of the constituents. Thus we see that the elements of the dihedral group lie in R(H) while those of the quaternion group (outside the centre) do not. So H/R(H) is the Klein group.

Posted in doing mathematics, exposition | Tagged , , , | 1 Comment

Carlo Casolo


Terrible news: Carlo Casolo died last week, possibly of a heart attack.

I have one paper with him, on “Integrals of groups”, published last year. In February, as I reported, I visited Florence to carry on with this work and push further, along with Francesco Matucci, who was Carlo’s student and (for the first time on this project) his collaborator.

I cannot speak too highly about Carlo’s ability – he stormed through some of the difficulties we faced – or his generosity.

Posted in Uncategorized | Tagged | Leave a comment

Hall’s Marriage Theorem

Philip Hall was one of the greatest group theorists of the twentieth century. But it may well be that he is known to more people for a result which on the face of it is pure combinatorics, with nothing to do with group theory: Hall’s Marriage Theorem.

In the story form in which it is usually told, it goes like this. Let g1,…,gn be girls. Suppose that each girl gi has a list Bi of boys she would be prepared to marry. Then a necessary and sufficient condition for it to be possible that all the girls marry boys from their list is that, given any set of k girls, their lists contain at least k boys altogether.

Said more formally, if B1,…,Bn are finite sets, a system of distinct representatives or SDR for these sets consists of n elements b1,…,bn such that

  • they are representatives of the sets, that is, bi belongs to Bi for all i;
  • and they are distinct, that is, bi ≠ bj for i ≠ j.

Then Hall’s theorem says that a necessary and sufficient condition for the sets to have an SDR is that the union of any k of them has cardinality at least k.

A moment’s thought shows that the condition is necessary; if the lists of k girls don’t contain at least k boys, then these girls cannot be married to boys on their lists. The proof that the condition is sufficient, that is, guarantees that the marriage arrangement is possible, is more difficult, but several very different proofs are known.

My purpose here is not to expound the proof, but to explain why a group theorist should be interested in this.

Let G be a finite group and H a subgroup of G. As you will know if you have done group theory up to Lagrange’s theorem, the right cosets of H in G (the sets Hg = {hg:hH}) are pairwise non-overlapping and cover G. Moreover, each coset has the same number of elements as H, since the map from H to Hg taking h to hg for all hH is a bijection.

If g1,…gn are elements such that the right cosets Hg1,…Hgn are distinct and cover the whole of G, we call these elements right coset representatives.

Similar statements hold for the left cosets, the sets gH = {gh:hH}. And from Lagrange’s Theorem, it follows that the numbers of left and right cosets are equal.

But in fact there is a much more elementary proof that these numbers are equal, which works equally well if G, H, or the number of cosets is infinite. Can you find it?

What Hall was after was the following statement:

Let H be a subgroup of the finite group G, with n cosets. Then there are elements g1,…gn of G which are simultaneously right and left coset representatives.

To see how this follows from Hall’s marriage theorem, we argue like this. Let x1,…xn be right coset representatives, and y1,…yn be left coset representatives. For each i∈{1,…,n}, let Bi be the set of indices j for which the left coset yjH has non-empty intersection with the right coset Hxi.

Now we claim that these sets of indices satisfy Hall’s condition for the existence of an SDR.

Let I be any set of indices, and let J be the set of all j belonging to the union of the Bi for iI. This means that the union of the right cosets Hxi for iI is contained in the union of the left cosets yjH for jJ. Since all cosets have the same size, this entails I ≤ J, as required.

So, by Hall’s marriage theorem, there exists an SDR for the sets B1,…Bn, that is, n distinct elements bi where biBi. This means that the intersection of the right coset Hxi and the left coset ybiH is non-empty. Take an element gi in this intersection. Then g1,…gn are both left and right coset representatives for H in G.

This is not the end of the story. Marshall Hall Jr. (another great 20th century mathematician who gave us textbooks on both group theory and combinatorics) extended Hall’s marriage theorem to the case where we have an infinite number of finite sets (that is, an infinite number of girls, but each has only finitely many boys on her list).

Using this, it is easy to see that Philip Hall’s observation about simultaneous left and right coset representatives holds also when the group G is infinite, provided that the subgroup H is finite.

As far as I can recall (and I admit my memory might be wrong), I have never actually used this nice result for anything; but I have always felt that there should be an application of it. Any thoughts?

Posted in exposition | Tagged , , , , | 13 Comments