Alan Hoffman

I have just heard the news that Alan Hoffman has died, at the age of 96.

There is much to say about Alan; I will restrict myself to my own person perspective, and not even all of that; I didn’t know him well, but met him several times and regarded him as a friend.

Alan was interested (among many other things) in eigenvalues of graphs, in particular the smallest eigenvalue, and more particularly still the class of graphs with smallest eigenvalue −2 (or greater). To describe such graphs, it is enough to describe the connected ones.

Alan knew that line graphs have least eigenvalue −2 (or greater, in a few simple cases). One of his results from the 1950s characterized the line graph of the complete graph Kn by its spectrum if n is not equal to 8. (For n = 8, there are three exceptional graphs, characterized by Chang.)

Alan further invented the class of generalized line graphs, which also have least eigenvalue −2. He knew that this class did not capture all such graphs (the Petersen graph, unsurprisingly, being an exception), but he conjectured that “most” connected graphs with least eigenvalue −2 are generalized line graphs, and around 1970 wrote a long manuscript attempting to prove a result along these lines. I never saw this legendary manuscript, so I am not quite sure what it did; I think perhaps “most” meant a lower bound on the minimum valency of a vertex.

Anyway, it was this manuscript which led Jean-Marie Goethals and Jaap Seidel to a geometric analysis, where they embedded the graph as a set of vectors of fixed length in a Euclidean space, any two making an angle of 90 degrees or 60 degrees. They also showed that the lines spanned by such a set could be enlarged to a maximal set, which was “star-closed” (that is, if two lines in a plane make an angle of 60 degrees, then the third line at 60 degrees to both is also in the set). I realised that these star-closed sets were exactly the lines spanned by the vectors in a root system of type ADE. This gave rise to a very simple proof of Hoffman’s theorem, in stronger form: a connected graph with least eigenvalue −2 is either a generalized line graph or one of a finite set (up to isomorphism), all of which were embeddable as above in the root system E8.

I think Alan was very pleased with this theorem (not least because he had no need to struggle to complete his long manuscript). The paper is among my most cited.

So rest in peace, Alan.

Posted in Uncategorized | Tagged , , | 3 Comments


The coincidence of Peter Neumann’s funeral and Eric Lander’s elevation in the last few days has inevitably made me think about family (in the mathematical sense).

First, pictures of my aunts and uncles, brothers and sisters, sons and daughters, taken nearly fifteen years ago at Ambleside in the Lake District.

mily, 1
Family, 2

Families always have hidden secrets, joys and sorrows; but they do matter. Tim Penttila was in love with projective geometry for as long as I knew him; I well remember his delight when he discovered that he was a descendant of Oswald Veblen, a great pioneer in the subject. Henry Whitehead, who said “Combinatorics is the slums of topology” (this was told to me by Graham Higman, his student and my mathematical grandfather), has a fourth-generation descendant who has a doctorate in combinatorics and who became director of the Whitehead Institute.

Incidentally, Peter Neumann told me that Whitehead was not really Veblen’s student, though they worked together very closely. Well, who knows? Even the Mathematical Genealogy Project admits that Lagrange was not really a student of Euler, being self-taught. In his Miscellany, Littlewood credits (I think) Hardy with the observation that a proof of a theorem with a couple of gaps is like being descended from William the Conqueror with a couple of gaps. (So I am descended from Leibniz with possibly a couple of gaps.)

So this is an opportunity to tell briefly something about Eric. He arrived in Oxford on a Rhodes Scholarship to do research in algebraic topology. But before the term started, he had changed his mind and decided to do coding theory instead. By chance, it happened that I was the only person in Oxford at the time who claimed to know anything about coding theory. (I had worked with Jack van Lint, and at the instigation of Dan Hughes had written the book with Jack which in its latest version is Graphs, Codes, Designs and their Links.) So I got to supervise Eric.

As it happened, I had something much vaguer than a conjecture which I thought he might like to think about. I had observed that there were two techniques in design theory which, where they overlapped, gave similar results. One, going back to the Bruck–Ryser and Chowla–Ryser theorems, had been used by Dan Hughes to investigate automorphisms of designs. It applied whenever there was a prime which divided a certain parameter to an odd power. The other was the construction of a self-dual code from a design, which was later crucial in the nonexistence proof of the projective plane of order 10; it required a prime to divide the same parameter to the first power only. I thought there might be a common generalisation, which would extend the power of the first technique and the scope of the second.

Eric, with a good background in algebraic number theory, took to it immediately. The coding theorists had taken an integer matrix and considered its row space over the finite field with p elements. Eric observed that, if instead you took the row space over the p-adic numbers, then you could reduce it modulo arbitrary powers of p, and get a chain of codes, with the property that duality reversed the order in the chain (so if the power of p involved was odd then the code in the middle was self-dual).

Eric’s thesis took off from there, and at the end he turned it into a book with the title Symmetric Designs: An Algebraic Approach. So, when he came to Ambleside to talk at my birthday conference, he called his talk “The Human Genome: An Asymmetric Design”.

This reminds me of another story, which I have probably told before. It is a family failing (and I mean my real family here) that as we get older we forget that we have told stories before and tell them again to the same people.

The American Mathematical Society had (maybe they still do) a slot for a talk at their meeting for somebody who uses mathematics in their work in another area. One year they invited Eric to talk. On the plane, he was sitting next to someone who was obviously a mathematician, so they introduced themselves to each other. Eric’s companion was amazed. “Not the Eric Lander, of Symmetric Designs: An Algebraic Approach?” Eric told me this with great delight.

Now back briefly to Peter Neumann. At his funeral yesterday, Sylvia mentioned his love of music (he played violin and viola). I was transported back to a room at a British Mathematical Colloquium (not sure where or when), where Peter Neumann and Philip Higgins played some of Bartók’s Duos for Violin. I was absolutely spellbound by this beautiful music, and lost no time in finding a copy of the score. I found that it adapts well to the guitar, with no transposition necessary. A few times in my life I have been fortunate to have a guitar player to perform the duets with.

Posted in history, mathematics | Tagged , | 8 Comments

Eric Lander

One of my first doctoral students, Eric Lander, has been appointed science advisor in Joe Biden’s cabinet:

I have had so many congratulatory emails that it almost seems as if I have done something good myself …

Posted in Uncategorized | Tagged , | 7 Comments

Memories of Peter Neumann

What follows are memories, and at my age my memory is not totally reliable, so don’t take any of this as absolute truth.

But it is important to say that Peter was one of the kindest people. I owe him a huge amount, but he was always supportive and never once reminded me of this debt. However, with his kindness, he was in no way a soft touch.

Peter was born in Hull, and always regarded himself as a Yorkshireman. He told me that when he was born his mother was living in a caravan, writing her thesis on a portable typewriter; to get him out from under her feet, he was put on a lead and allowed to crawl round the garden.

Sometime around 1970, the British Mathematical Colloquium was in York, and Peter took me and another of his students, Graham Atkinson. He rented a car and we drove up to York. Along the way, after a stop, he suggested that Graham should drive for a bit. It was a very windy day, and Graham lost control of the car on the motorway; we crossed the central reservation and ended up on the hard shoulder on the wrong side, completely unscathed. Peter took over and drove the rest of the way. But he regarded it as important to get Graham back behind the wheel of the car, so he would not lose confidence; so at the meeting they went out driving a couple of times.

Back then, contributed talks at the BMC were in subject-specific “splinter groups”, to which you signed up at the meeting. John Conway was there; it may have been his first BMC as well as mine. He thought that if he signed up for several splinter groups, he would increase his chances of being offered a place in one of them. Inevitably he gave all the talks he signed up for. I remember that one of them was about octonions. He showed us an identity which he called the “plaiting rule”; but his Liverpool accent was sufficiently thick that I heard it as the “punting rule”. I couldn’t see what it had to do with punting, but I was aware that punting at Cambridge was rather different from punting at Oxford …

Peter was only six years older than I, but I was his sixth student. When I came to Oxford, the intention was that I would be Graham Higman’s student. But Graham was on leave at the time, so I began with Peter, and transferred to Graham when he got back. After a short time he decided to trasnsfer me back to Peter. (It is claimed that he said, “You ask too many questions; you can go back to Peter”, though I don’t actually remember him saying this.)

Peter was the ideal supervisor for me. He gave me Wielandt’s book on permutation groups to read at the start. After that, he let me find my own direction, but he was always there with suggestions and questions. At the time, he had just extended Wielandt’s theorem on primitive permutation groups of degree twice a prime to degree three times a prime. The argument was based on Donald Higman’s theory of coherent configurations, so I had an early acquaintance with that. One of the rare examples of such a permutation group is PSL(2,19), with degree 57. Fortuitously it happens that one of the orbital graphs is 2-arc-transitive, though we didn’t call it that back then: the point stabiliser is A5, acting 2-transitively on an orbit of size 6. (This graph is now called the Perkel graph, after Manley Perkel, who studied it in the late 1970s; but perhaps Peter Neumann should get some credit.) W. A. Manning had shown that if a primitive but not 2-transitive group has the property that the point stabiliser is 2-transitive on an orbit of size greater than 2, then this is not the largest orbit. I happened to notice that the reason for this is that the group is transitive on paths of length 2 in the orbital graph, and so points at distance 2 from α form an orbit of the stabiliser of α, larger than the starting orbit. This short proof of a theorem that cost Manning much more effort was the subject of my first paper, and led to my thesis topic.

Peter had four students in my year; as well as me, there were Gareth Jones, Elizabeth Morgan (now Billington), and Mary Tyrer. Gareth and Mary got married and spent their career in Southampton. My relationship with Liz was a bit different: we changed places. I moved from Brisbane to Oxford; she moved in the other direction, and finished her thesis with Sheila Oates. We remained on opposite sides of the world, though we managed to continue as friends. So Liz and I are mathematical cousins rather than siblings.

Peter ran a “Kinderseminar” for his research students and selected other people. When I was appointed to a fellowship at Merton College, and had students of my own, I tried to replicate this on a small scale; but, to my great delight, soon Peter invited me and my students to join the Kinderseminar. We would meet at 11, have coffee and chat, and then someone would talk about some interesting mathematics. At the end of the talk, Peter would discretely take the student to one side and go over the talk, not criticising but making friendly suggestions about what could have been done better. If you want to know why all of Peter’s students are good lecturers, look no further than this.

Peter was one of the pioneers of the combinatorial approach to permutation groups associated with the names of Donald Higman and Charles Sims, and I was very fortunate to learn about this early on. But he did much more. He has an influential paper with both his parents and Gilbert Baumslag on varieties generated by a finitely generated group, published in 1964 when he was in his early 20s. His doctoral thesis contained results about wreath products, among other things. He was perversely proud of the fact that it was the only doctoral thesis ever to be stolen from the Whitehead Library of the Oxford Mathematical Institute!

Peter was always interested in the history of algebra. I recall one occasion when I was in his rooms and we were discussing something, I no longer remember what, but probably connected with the O’Nan–Scott Theorem. Peter reached up to a high shelf and pulled down Camille Jordan’s Traité des Substitutions; he turned to the page where Jordan proves most of the O’Nan–Scott Theorem. In the case where the socle of a primitive group is non-abelian and not simple, Jordan clearly states the crucial case division that leads to wreath products on one hand and diagonal groups on the other. I feel that a fitting tribute to Peter would be on the history of the O’Nan–Scott Theorem: What exactly did Jordan prove? Why was it forgotten? What happened subsequently?

All of 19th century algebra was Peter’s playground, and in particular he became an expert on Galois, editing all of his writings with detailed commentary.

He gave a lot of time to serving various organisations in various capacities, especially the London Mathematical Society, the British Society for History of Mathematics, and the UK Mathematics Trust. With the LMS, he dealt with publications for some time. This was back in the days of hot-metal printing. The LMS printers were a small specialist firm in Leytonstone, who may have been called Hodgson and Son; Peter used to make fairly frequent trips to East London to discuss printing matters with them. (All his students will testify that he instilled in them a sense of how printed mathematics should look, with simple but oft-forgotten rules such as: Don’t start a sentence with notation; don’t put two formulae adjacent in a sentence.)

It must have been at about this time that the LMS started up its Bulletin, to contain short papers, as well as surveys, records of meetings, book reviews, and obituaries. I don’t know what role Peter had in establishing this journal. But I was fortunate to have my first paper published in the first volume, along with John Conway’s paper introducing his groups.

He was awarded an OBE in the New Year Honours in 2008, for his services to education; I think this primarily referred to his work with the UK Mathematics Trust.

Peter had a hand in getting me involved in the connections between permutation groups and transformation semigroups, especially synchronization. The push came from the coincidence of three things. First, Cristy Kazanidis, who had been a postdoc at Queen Mary, was back in London and came to see me looking for a research problem. I suggested that we could look at cores of rank 3 graphs. So when I needed it, I had the information about graph homomorphisms required to characterise synchronizing groups to hand. Second, Robert Bailey, my former student, came back to Britain for Christmas, and told me about a conversation he had had with Ben Steinberg about synchronization at a bus stop in Ottawa. This sounded interesting to Robert, but halfway through, Ben’s bus had come along and the conversation was never finished. Finally, someone asked me for the notes of an Oberwolfach meeting on permutation groups the previous summer. On looking them out, I found also the notes of Peter Neumann’s talk on synchronization, based on an exchange he had had with João Araújo. This got me in touch with João, and the rest is history (or may be one day, it is still going on!). João told me later that he had had the big idea of using advances in group theory based on CFSG to make progress on semigroup theory. When he talked to Peter, he had just had a paper proposing this idea rejected (see the preceding post). But Peter reassured him that it was beautiful mathematics and encouraged him to continue.

One final memory. One year in the 1970s, there was a finite geometry conference at the Isle of Thorns (the University of Sussex conference centre in Ashdown Forest). Peter, Jan Saxl and I decided to walk there from Oxford. We took three and a half days, staying overnight in Reading, Guildford, and East Grinstead, and arriving at the conference about lunchtime. It was beautiful autumn weather. Peter and Jan each had to skip a bit of the way because of minor injuries, and use public transport. Now, after this dreadful year, I am the only survivor of that walk …

Posted in history, mathematics, the LMS | Tagged | 9 Comments

Publication: an author’s view

One of the few positives about this strange year is that I have done a lot more mathematics than usual. Sitting on the sofa with nothing to see but occasional people walking along the wynd outside has given me time to think, though I admit I felt a bit like the Lady of Shalott at times.

More papers written, more papers submitted, and a higher proportion of papers rejected. If everyone is writing more papers and the capacity of journals has not increased the result is to be expected.

I am beginning to think that I am not very good at judging the quality of my own papers. Some that I consider fairly routine are accepted by journals, while others that I consider quite groundbreaking are turned down so quickly that the editors can hardly have had time to think about them.

Now, at my age, it doesn’t matter a great deal if I publish papers or not; and I could save myself a lot of trouble by simply putting them on the arXiv and encouraging people to read them there.

There are a few arguments for not doing that.

  • The standard argument is that the refereeing process is a guarantee of quality; referees will catch the mistakes and you have a chance to put them right before the paper gets published. There are a couple of things wrong with this. First, often mistakes are not spotted by referees but are pointed out by readers after the paper has appeared. Second, referees do more than just point out mistakes. Once I had a fairly positive referee’s report on a paper which, at a certain point, said “page 13, line 5: This is wrong.” The referee gave no indication of why it was wrong; I read it carefully and wrote to the editor saying “I stand by what I wrote”, and the paper was published without any change to that point. Another more recent referee’s report, one of the most positive I have ever had, ended by saying “The open questions that the authors state: I think they could probably answer some of these.” The editor took this to mean that the paper could not be published without major revisions. We wrote back inviting the referee, if (s)he knew how to answer these questions, to be a co-author – we certainnly couldn’t do it – and heard nothing for two years, after which there was no alternative but to withdraw the paper.
  • An argument that does carry weight with me is that many of my papers have coauthors, many of whom are researchers at the start of their careers, and for their sake the paper should be published in the best journal that will accept it. Yes, that is true, and that is the main reason why I still submit papers to journals.
  • The final reason is that universities are judged by the quality of their research, and the rules of the game specify that this research must be published in journals; conference proceedings essentially don’t count. Why? Because the people who judge the quality are incompetent to do it themselves, and rely on the gold standard given by refereeing (but see the first point). So while I am in employment, I have no choice.

On the last point, when you put a paper in the St Andrews repository, the first question, before any details of the paper itself, is: Peer reviewed or not? This is clearly the most important piece of information for the bureaucrats. The difference in attitude is reflected by the fact that almost inevitably I forget to answer it and when I try to upload the form I am told to go back and answer that question.

Some of my papers which have been turned down by journals have stood the test of time and are now among my most cited papers. Back in the days when submitting a paper to a journal meant printing it out and putting it in an envelope with a covering letter, one paper came back from a journal appearing not even to have been taken out of the envelope and unfolded. This paper is now sometimes cited as a pioneering document in the theory of mutually unbiased bases in quantum computing (although we had no idea about this at the time).

Thinking about all this has led me to a theory. It is the interdisciplinary papers that are most likely to be rejected by journals without proper scrutiny. (The paper referred to above was so interdisciplinary that we felt it necessary to include a “road map” of the concepts discussed.) A paper which is simply an incremental improvement of already known results is more likely to be taken seriously. This despite the fact that journals claim that the opposite is the case. And of course I much prefer finding unexpected links between very different areas.

Sad. But maybe true, and maybe inevitable. And I must make clear that, as hinted above, I find no fault with journal editors, who have been facing huge difficulties with the every-increasing pressure to publish.

Posted in publishing | 29 Comments

Peter Neumann

This terrible year has claimed another victim. Peter Neumann died this morning in Oxford, peacefully, of Covid.

Peter was my DPhil supervisor, later colleague, always friend. I will not say more now.

Posted in Uncategorized | Tagged , | 7 Comments

Induced subgraphs of power and commuting graphs

For those who like thinking about these things, here is a small observation and a few problems.

As I have recently discussed, the power graph of a group is perfect. This means that all its induced subgraphs are perfect, and in particular they all have clique number equal to chromatic number.

Problem 1 Is every perfect graph an induced subgraph of the power graph of some group?

For the commuting graph, things are different: every finite graph is an induced subgraph of the commuting graph of a group. To see this we use the following simple construction. Let V be a vector space over the field F with two elements. Let B be a bilinear form on V. Define an operation on V×F by the rule

(v,a) * (w,b) = (v+w,a+b+B(v,w)).

It is easily checked that this is a group operation. Now let {v1,…vn} be a basis for V. The values of B(vi,vj) can be prescribed arbitrarily, and the resulting function extended to V×V by bilinearity. So, given a graph on the vertex set {1,…n}, put B(vi,vj) equal to 0 if i ≤ j, while for i > j put the value equal to 0 if i and j are joined, 1 otherwise. This works because the commutator of (v,0) and (w,0) is (0,B(v,w)+B(w,v)).

Problem 2 Given a graph on n vertices, consider the group defined above. Which other graphs can be realised by changing the basis for V?

It follows that, for every n, there is a group whose commuting graph contains every n-vertex graph as an induced subgraph.

Problem 3 What is the smallest group G with this property?

Problem 4 Is every graph an induced subgraph of the enhanced power graph of a group?

Problem 5 Is every graph an induced subgraph of the generating graph of a 2-generator group?

Posted in open problems | Tagged , , | 3 Comments


I have just spent the last four days in Kochi, Kerala, at the International Conference on Number Theory and Discrete Mathematics, commemorating Srinivasa Ramanujan, the great Indian mathematician, on the 100th anniversary of his far-too-early death.

The conference had perhaps more discrete mathematics than number theory. I did not attend every session, which would have involved getting up before 4am every day, but took in over half of the plenary lectures and a couple of others.

Why number theory and discrete mathematics? Ramanujan’s work was in number theory, although some of it (for example the work with Hardy on the asymptotics of the partition function) was certainly on the boundary of discrete mathematics. I think a better answer to the question is as follows.

There is a remarkable connection between the smallest non-trivial Laplacian eigenvalue of a graph and important global properties of the graph such as isoperimetric number and speed of convergence of the random walk. The larger the smallest eigenvalue, the better network properties the graph has.

(The Laplacian eigenvalues are the eigenvalues of the symmetric matrix DA, where A is the usual adjacency matrix and D is the diagonal matrix whose entries are the valencies of the vertices. This matrix is positive semidefinite, and the multiplicity of the “trivial” zero eigenvalue is equal to the number of connected components. From the definition, we see that if the graph is regular, say with valency k, then the Laplacian eigenvalues are obtained by subtracting the adjacency matrix eigenvalues from k. Hence having the first non-zero Laplacian eigenvalue large is equivalent to having a big gap between the largest and second-largest eigenvalue of the adjacency matrix.)

The Alon–Boppana theorem asserts that, for given k, there are only finitely many connected regular graphs of valency k with second eigenvalue greater than 2√(k−1). Thus an infinite family of such graphs will almost all have second eigenvalue below this bound. If the limit superior of the second eigenvalue meets this bound, the family is called a family of Ramanujan graphs. The name was given by Lubotzky, Phillips and Sarnak, who, along with Margulis, were the first people to find such a family; it marks the fact that the proof used a conjecture by Ramanujan on sums of four squares. The result they needed had been proved by Igusa. This is one of my favourite papers, in Combinatorica in 1988 and free to download; I urge you to read it.

Anyway, this connection opens the way for discrete mathematicians to invoke and honour the name of Ramanujan, as many speakers in the conference did.

Peter Sarnak gave a similar talk to his Hardy lecture earlier this year, which I have discussed here. The Alon–Boppana theorem and the construction of Ramanujan graphs shows that there is a “gap” in the spectra of connected trivalent graphs from 2√2 to 3 which contains only finitely many graphs, and that it is maximal in the sense that no longer interval containing it has this property.

There were several talks on Ramanujan. George Andrews proposed his conjecture about how Ramanujan hit upon the mock theta functions, one of his last pieces of work. His talk described an analysis, using things that Ramanujan knew very well, which would lead to these functions. This no doubt would have been “chalk and talk” in earlier times; George wrote it all out in longhand in real time, even the complicated double summations.

One of the most remarkable talks was by Neal Koblitz. G. H. Hardy described number theory as “gentle and clean”, and Neal set out to convince us that applied mathematics is not always so. He began by describing two failures of technology (or applied mathematics) which caused very great harm in the USA. First was a prediction based on epidemic modelling from a group in his own university, which suggested that if masks were worn and social distancing observed, the pandemic would be over by June and the death toll would be limited to 60000. The President and his advisers heard the conclusion but not the sufficient condition, failed to enforce masks or social distancing, and the rest is history. The second was over-reliance on cryptography in the Test-and-Trace system in the US. The modellers had failed to realise that Bluetooth signals travel through walls and floors, and so people living in small apartments are more likely to be reported by the system as having been in contact with an infected person; moreover, this group are disproportionately poor and black, and will be much harder impacted by the result of this, standing to lose their jobs and possibly even face eviction. The modellers were unaware of this because the reliance on cryptography meant that these patterns were not visible.

He moved on to talk about quantum computing. He took us through the basics, and described Shor’s algorithm for factorization in detail, keeping an eye on how many qubit registers are required. For current sizes of integers used in RSA, this number is somewhere around 4000. Each qubit register needs thousands of classical gates to preserve it from interference. He thinks it unlikely that such a machine will be built this century. Moreover, cryptographers have had plenty of notice, and have developed quantum-safe cryptographic methods. He ended with some comments about how bad we are at predicting future developments in science and technology. In the golden age of science fiction in the 1950s and 1960s, it was thought that space travel would become commonplace by the end of the 20th century, and that nuclear power would become cheap and portable (even nuclear-powered wristwatches were suggested!). The writers completely failed to predict the miniaturization of computing technology, and the resulting growth of the internet and social media.

One talk that caught my attention was by Kannan Soundarajan. Apparently it is known that, if you choose a random character of the symmetric group and evaluate it on a random group element, then the probability that the result is 0 tends to 1 as the degree of the symmetric group grows. He and his coauthor had attacked a different question: what if instead you choose a random entry of the character table (that is, a random character evaluated on elements of a random conjugacy class)? What changes is that we are choosing a random conjugacy class instead of a random group element. The conjugacy class sizes in the symmetric group vary from tiny (the transpositions) to huge, essentially a fraction 1/n of the group order for the symmtric group of degree n, for elements with a cycle of length close to n. They cannot prove that the entry is zero with high probability, but can show that for a fixed prime the entry is divisible by that prime with high probability. (“Random” here means “from the uniform distribution”.)

I could see no reason for choosing the character at random. It seemed to me more natural to use the Plancherel measure, which makes the probability of a character proportional to the square of its degree (so that, in the symmetric group, the probability of the character indexed by a partition λ is equal to the number of pairs of Young tableaux of shape λ divided by n!. This gives two further problems, since we may choose a random element or a random conjugacy class. I don’t know whether this variant is easier or harder than using the uniform distribution.

As to distribution of group elements, there has been a lot of research on choosing a random element in an arbitrary group, for example using the “product replacement algorithm”. For a random conjugacy class, this can be chosen by taking a random walk on the commuting graph. In fact in the symmetric group it is easy to choose a random element: take an integer between 0 and n!−1, write it in “factoradic” form, and decode this into a permutation.

I will finish this account with a brief mention of the public lecture by Ram Murty, entitled “Ramanujan, number theory and the pandemic”. Ramanujan had been faced with the problem of finding a power series expansion for the Lambert w-function, the inverse of the function mapping z to zez. To do this, he re-invented the Lagrange inversion formula. The Lambert function appears in solving the basic differential equation of the SIR model (susceptible, infected, recovered) of the spread of an epidemic.

Posted in doing mathematics, events, open problems | Tagged , , , , | 4 Comments

Oligomorphic groups: topology or geometry?

One perhaps unexpected result of the pandemic is that there is a huge volume of really interesting mathematics flying around the internet at the moment, courtesy of Zoom and other platforms.

This week I went to a talk by Joy Morris in which the view was expressed (not by her) that “Algebraic Graph Theory” means “Cayley graphs of finite groups”. The next day I heard a talk by Matt Zaremsky in which it was said, maybe not quite so forcefully, that “Geometric Group Theory” means “Cayley graphs of finitely generated infinite groups”.

I had gone along to this talk on embedding groups in simple groups because it looked interesting. I remembered some results along these lines from my Oxford days, when Graham Higman proved the Boone–Higman Theorem and talked about it in his advanced class. It was indeed a very interesting talk. Every finite group is embeddable in a finite simple group (this is Cayley’s Theorem with a very small twist); the game is to replace “finite” in this theorem by some other property. Philip Hall proved this for finitely generated groups. Matt talked about some work he has done with my colleague James Belk.

Let me describe briefly the groups they use. These are generalisations of Thompson’s group V, which is a certain group of homeomorphisms of Cantor space. You can think of Cantor space as the set of all infinite sequences of zeros and ones, with the product topology. It is a fractal, that is, it can be cut into two pieces each homeomorphic to the original space in a canonical way. (These are just the sequences starting with 0 and the sequences starting with 1.) Thompson’s group is defined as follows. Do this division m times, for some m (that is, bisect the whole space, then choose a piece and bisect it, and so on.) Then do it again starting from the top to get a possibly different set of m pieces. Now take the canonical isomorphisms between these pieces, and put them together; this gives an element of the group.

The first variation is that you can do this instead with s-dimensional Cantor space, simply the direct product of s copies of the original Cantor space. Now each bisection should be done to one coordinate. For s = 2, thinking of Cantor space as a square, you bisect it by a line parallel to one of the axes, and then repeat this with each piece. This gives the group known as sV.

In the previous paragraph, it seems as if s is finite, but it is allowed to be infinite here. I will write SV, where S is the index set.

For the second variation, we take a group G which acts faithfully on the set indexing the coordinates. Do the divisions as before, but now apply an arbitrary element of G to each piece before taking the canonoical maps between them. (In the 2-dimensional case, flip some of the pieces by interchanging horizontal and vertical.) This gives a simple group called SVG. It is clear that G embeds into SVG (take subdivisions with m = 1); if both G and SVG are finitely generated, then the embedding is a quasi-isometry (that is, it doesn’t distort too much the metric defined by the Cayley graph).

The next job is to investigate finiteness conditions of these groups. A group is said to be of type Fn if it acts “geometrically” on an (n−1)-connected CW-complex. It is of type F if it is of type Fn for all n. It turns out that type F1 means “finitely generated” while F2 means “finitely presented”. So can we find an action of a group G such that SVG has property Fn?

Now here came a big surprise for me. Their theorem says that, if the permutation group G on a countable set S is oligomorphic (diligent readers will recall that this means that G has only finitely many orbits on k-sets, for all natural numbers k), and the stabiliser of any finite set in G is of type Fn, then SVG is also of type Fn; if in addition G is not of type Fn+1, then neither is SVG. Thus if we can find suitable G we get a simple construction of simple groups with any finiteness condition Fn.

Now came the second surprise. I will explain later why this was surprising to me. An example of an oligomorphic group satisfying the requirements of this theorem is the Houghton group Hn. This group acts on the disjoint union of n copies of the natural numbers N; apart from a finite subset, the action on the ith copy is a translation by, say, ai (where, for consistency, these translation steps must sum to 0).

Why is the Houghton group oligomorphic? Well, any finite set can be permuted arbitrarily, so it contains the finitary symmetric group; it actually has the much stronger property of being highly transitive.

The first surprise was that here were my old friends, oligomorphic groups, in quite a different context from the one where I usually meet them. The second surprise went deeper. The kind of oligomorphic groups I am most friendly with are things like the automorphism group of the random graph. This group is simple, but it is uncountable, hence certainly not finitely generated; so it does not fall within the domain of geometric group theory at all!

The difference is that I think of oligomorphic groups as being groups of automorphisms of relational structures like the random graph. Taking the closure in the symmetric group (in the topology of pointwise convergence) does not change the orbits on k-sets; but if the group is closed and oligomorphic then it is certainly uncountable. So my “topologically nice” oligomorphic groups are completely different from the “geometrically nice” groups which are required by the theorem of Belk and Zaremsky.

Is there any common ground here?

The Houghton group Hn is commonly drawn as acting on the set of equally-spaced points on n rays radiating from the origin in the plane. Looked at “from a distance”, we see only the translations, which form a group Cm−1; whereas, close up, we see no structure at all, arbitrary permutations of a finite set, and a highly transitive group. So it is all in the point of view.

I would like to construct an oligomorphic group which is interesting at both scales. So let me try to formulate this as a precise question. Does there exist an oligomorphic permutation group on a finite set which has property Fn for some but not all finite n and is not highly transitive?

The remarks above hint that such a group should contain finitary permutations. Now Wielandt’s extension of a theorem of Jordan says that if a primitive permutation group on an infinite set contains finitary permutations then it contains the finitary alternating group (the set of all finitary even permutations), and so is highly transitive. So indications are negative!

However, all is not lost. Dugald Macpherson has constructed (alone or with co-authors) various interesting actions of finitely generated free groups. These could at least give examples where the theorem could construct simple groups of type F, which. Perhaps applying these methods one could get other examples.

As a final note, Matt Zaremsky observed that he was not sure how to pronounce “oligomorphic”: is the initial O short or long? It is certainly short in British English, but I don’t know about the US version. How do you pronounce “oligarch”, as in “friend of Vladimir Putin”?

The word “oligomorphic” is not in my Chambers dictionary, but I understand that it has another usage, in computer science. A computer virus is oligomorphic if it exists only in a few different forms; such viruses are more easily recognised than the polymorphic ones.

Which brings us back to Covid …

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

A rant

When the Great Helmsman died in 1976, Jung Chang was able to put on a convincing display of abandoned grief. But afterwards, she decided to think through Mao’s philosophy, and how he had been able to exert such control. She decided that he had been a “restless fight promoter”, who understood and exploited the ugly side of human instincts such as envy and resentment, and used them together with the ignorance of his followers to eliminate possible challengers.

The Chairman might have been interested to know that this process has now been automated. The Internet and the World Wide Web, inventions which huge potential for good, can be exploited in much the same way. Start a rumour on social media, and there will be people who believe it without checking, and are ready to take up aggressive stances for the cause.

Take BLM, for example. This is absolutely necessary and vitally important; our society is shamefully riven with racism, and black people find themselves on the end of it on a daily basis. So the movement has become a vital force for change.

But it can be used for more sinister motives. Cancel culture has a good side; it is surely wrong that someone who made a fortune trading other humans with scant respect for their lives should be memorialised, even if he donated some of this fortune to the good of his city.

But this is a convenient weapon for taking down your enemies, even if they are not here to speak for themselves. It would be a shame if the whole movement were to be tainted by such activity.

This brings me to my real topic, the statistician and geneticist R. A. Fisher.

Earlier this year, Fisher was denounced as a racist by a historian, who was so on top of her subject that she could actually claim that Fisher invented Latin squares. The movement was taken up by others, the walls of Gonville and Caius College in Cambridge were defaced, and the governing body of the College yielded to popular pressure and removed the stained glass window in their dining hall in which Fisher is commemorated by a Latin square. (I will say more about this in a moment.) In any case, I am a member of the College, having been admitted during my tenure of a G. C. Steward fellowship there in 2008, so I feel entitled to put my head above the parapet.

The complaint against Fisher is that be belonged to (and was for a time the president of) the University of Cambridge Eugenics Society. This proves he was a racist, right? Well no, actually, if you look a little closer.

Eugenics was in its origin a plan to use genetic information to “improve” the human stock, as humans have been doing to other life forms for many millennia. If you have ever had genetic counselling, or have employed embryo testing, then you could be said to be making use of eugenics.

Of course, what constitutes an improvement is not entirely clear, and a lot hinges on the interpretation of this. There is no doubt that, in the first half of the twentieth century, eugenics meant different things to different people. In Germany and the USA, it was enmeshed with racism from quite early on. (Read about David Starr Jordan, the founding president of Stanford, to see the extent to which this was true.)

But in Britain, as always, class was the most important determining factor; the Eugenic Society was mainly populated by people from the middle classes who were uneasy about the rise of the lower classes. It encouraged the middle classes to have more children. The wider attitude persisted. In a book of commentary on the Sokal hoax, published by the editors of Lingua Franca, the Introduction gives a brief account of the field of Cultural Studies, and we read, “The discipline’s first institutional incarnation was the Centre for Contemporary Cultural Studies, a postgraduate research institute established in 1964 at the University of Birmingham in England. […] American cultural studies is often said to be characterized by a movement away from the Birmingham school’s emphasis on social class towards other aspects of identity, such as race and gender […]”.

For Fisher, a particular point at issue was intelligence. He regarded himself (correctly) as intelligent, and so (more dubiously) felt it his duty to have many children himself. He was not a person who found it easy to change his opinions or admit his mistakes. But he did leave the Eugenics Society. I have no hard evidence for this, but I suspect there were two reasons: first, his own research in genetics and that of others was showing that “things were not so simple”; and second, when the society appeared to be moving from discussion to action, he felt he could not be part of it.

As hinted above, nobody regarded Fisher as an easy-going or pleasant colleage. But that is not the same as being a racist; students from Africa and India, Jewish refugees from Nazi Germany, seem to feel affection for him and what he contributed to the discipline and to their careers. (Read Walter Bodmer’s account here.) And that he was a great scientist there is no doubt. Sticking to statistics (since I know little about genetics), his principles for experimental design and analysis, notably his insistence on randomization, replication, and blocking, have enormously improved the accuracy of experimental results, which have given us better agricultural practices (and so more food to feed the world) and better drugs (because of randomized clinical trials). It would not be easy to count the number of lives saved as a result.

So I will not be removing Fisher’s inequality from my teaching material any time soon.

On Latin squares: The window in Caius was based on the cover of his book The Design of Experiments. It appeared on every one of the many editions the book went through. Nobody knows where it came from. It seems it does not occur anywhere in Fisher’s works, and it has been suggested that someone at the publisher, who knew what a Latin square is, sat down and produced one essentially at random. This is reinforced by the fact that on the cover of one edition (the sixth, I think), it was printed upside down.

And if you don’t know who did invent Latin squares, Wikipedia has this to say: “The Korean mathematician Choi Seok-jeong was the first to publish an example of Latin squares of order nine, in order to construct a magic square in 1700, predating Leonhard Euler by 67 years.” (Euler was also constructing magic squares when he came up with the idea.)

In conclusion, a remark. If you visit St Andrews, walk along Lade Braes. You will find that a number of citizens of the town are commemorated by trees, marked with plaques at ground level. The plaques are quite unobtrusive, and hopefully not upsetting to anyone who found that person’s views offensive. Also, one presumes that by the time the trees die, those who remember the person commemorated will also have gone, so the fame will be no more permanent than it should be. Moreover, if some future movement demanded that such monuments would fall, and people showed up to chop down a tree and throw it into the river, it should not be hard to recognise them as vandals. This is a solution that might be more widely adopted …

Posted in Uncategorized | Tagged , | 7 Comments