February

Apocalypse on Charles Bridge

February’s picture, called “Apocalypse on Charles Bridge”, is a composite: the silhouettes are figures from the famous Charles Bridge in Prague; the sky behind is over St Andrews, the picture was taken from just outside my front door.

Charles Bridge is on the natural route from the Old Town Square to the castle, and also on the route from the Karolinum to the former Jesuit college which now houses the Applied Mathematics department. But it is so crowded these days that often when I have to go between the last two places I prefer to detour over one of the adjacent bridges.

Posted in geography | Tagged , | Leave a comment

From M12 to M24

On 20 January 2015, Paul Hjelmstad posted the following question on the GAP forum:

Is there an easy way to generate a Steiner system S(5,8,24) for the Mathieu Group M24, if a Steiner system S(5,6,12) for the Mathieu Group M12 is known?

I learned about the Mathieu groups when I was a student. I read Heinz Lüneburg’s book Transitive Erweiterungen endlicher Permutationsgruppen in the Springer Lecture Notes series, in which he constructed the Steiner system (and group) by extending three times the projective plane of order 4.

But, at about the same time, I attended a remarkable series of lectures by Graham Higman. In these lectures, he constructed the outer automorphism of the symmetric group S6, and used it to construct and prove the uniqueness of the projective plane of order 4, the Moore graph of valency 7, and the Steiner system S(5,6,12), and hence deduce properties of their automorphism groups. He then gave an analogue of the “doubling” construction from S6 to M12, starting with M12, constructing its outer automorphism, and using this to build M24 and its Steiner system.

I don’t think he published any of this, and I doubt whether any notes are now available. I used the first part of the material in chapter 6 of my book Designs, Graphs, Codes, and their Links with Jack van Lint. The outer automorphism of S6 is described here.

So I have written out a description of the path from the small to the large Mathieu group, and put a copy here with my lecture notes. This document could be regarded as a supplement to Chapter 6 of my book with Jack. It may be of interest to someone else; let me know if you find it so.

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

Ramon Llull

Last Saturday the Guardian had a review of The Serpent Papers by Jessica Cornwell (granddaughter of John Le Carré). Set in Barcelona and Mallorca, the book is a murder mystery and more; its presiding genius is Ramon Llull, the mediaeval Mallorcan who was described by Donald Knuth as “an energetic and quixotic Catalan poet, novelist, encyclopedist, educator, mystic and missionary” (in his article “Two thousand years of combinatorics” in Combinatorics Ancient and Modern).

If you read The Da Vinci Code, you may remember the absurd claim by Dan Brown that public-key cryptography was invented by Leonardo Da Vinci. Well, in Gwyneth Jones’ review of The Serpent Papers, she almost claims that Ramon Llull invented programming languages! She actually describes Llull’s Ars Magna as “a form of algebraic logic expressed in complex diagrams (an ancient forerunner of all programming languages, by the way)”. I haven’t read the book, so I don’t know whether this notion is in it or not.

So I checked on Wikipedia, and found this: “Some computer scientists have adopted Llull as a sort of founding father, claiming that his system of logic was the beginning of information science,” an altogether more modest claim.

So what did Llull do? This is how it seems to me, but I disclaim any expertise on Llull. He was interested in combinatorics, without a doubt. Knuth describes a chapter of his Ars Compendiosa Inveniendi Veritatem which begins by enumerating sixteen attributes of God: goodness, greatness, eternity, power, wisdom, love, virtue, truth, glory, perfection, justice, generosity, mercy, humility, sovereignty, and patience. Then Llull takes each of the 120 combinations of two of these attributes, and writes a short essay on their relationship.

There is much more along the same lines in Llull’s extensive writing. But, perhaps more significantly, he invented mechanical gadgetry for generating all the combinations. His works are full of beautiful diagrams of complete graphs, rotating discs, and so forth.

He seems to have believed that any moral question could be settled by analysis of all possible combinations of attributes, virtues and vices, etc. I am not quite sure how. Neither am I sure where the logic or computer programming comes in.

There was much more to Llull than this. Before his conversion, he was a secular writer and troubador; he wrote the first novel in Catalan (which is possibly the first European novel). Afterwards he set out to convince Jews and Muslims of the truth of Christianity by rational argument (a hopeless quest, you might think – but he always believed in discussion rather than violence). His works also include Latin squares.

I will leave the last word to Jorge Luis Borges:

At the end of the thirteenth century, Raymond Lully was prepared to solve all arcana by means of an apparatus of concentric, revolving disks of different sizes, divided into sectors with Latin words; John Stuart Mill, at the beginning of the nineteenth, feared that some day the number of musical combinations would be exhausted and there would be no place in the future for indefinite Webers and Mozarts; Kurd Lasswitz, at the end of the nineteenth, toyed with the staggering fantasy of a universal library which would register all the variations of the twenty-odd orthographical symbols, in other words, all that it is given to express in all languages. Lully’s machine, Mill’s fear and Lasswitz’s chaotic library can be the subject of jokes, but they exaggerate a propensity which is common: making metaphysics and the arts into a kind of play with combinations.

Posted in mathematics and ... | Tagged , , , , , , , , , | 2 Comments

Chains of semigroups

I have written here about the lovely formula for the length of the longest chain of subgroups in the symmetric group Sn: take n, increase it by 50% (rounding up if necessary), subtract the number of ones in the base 2 representation of n, and subtract another 1, to get the answer.

Last year, James Mitchell and I, talking about possible projects, wondered whether we could get a similar nice formula for the length of the longest chain of sub-semigroups in the full transformation semigroup Tn.

We didn’t succeed in getting a formula. But soon after that, Max Gadouleau came to visit, and got interested; he came up with a method which produces long chains.

Briefly, it goes like this. We look for a long chain among the semigroup of transformations of given rank m (with an added zero, so that if the product of two maps has rank less than m, we re-define it to be zero). Now in a zero semigroup (one with all products zero), any subset is a semigroup, so there is a chain of length one less than the order of the semigroup. So the trick is to find large zero semigroups.

This is done as follows. A map of rank m has an image (a subset of size m) and a kernel (a partition with m parts); the product fg will have rank less than m (so be zero in our semigroup) if and only if the image of f is not a transversal for the kernel of g. So we need a large collection of m-sets and a large collection of m-partitions such that no subset is a transversal for any of the partitions. Max invented the term league for this combinatorial object; the content of a league is the product of the numbers of subsets and partitions.

By finding leagues with large content, we were able to show that the longest chain of sub-semigroups of Tn has length at least a positive fraction 1/e2 of the whole semigroup. (A sharp contrast with groups, where the length of a subgroup chain is bounded by the logarithm with the group order.)

At this point the investigation broadened, and involved James’ former student Yann Peresse, as we tried our hand at various other semigroups. In some cases we were able to find exact results (either as an explicit formula, or in terms of the length of various groups involved). These cases include the inverse semigroup In of partial 1–1 maps on an n-set, another close analogue of the symmetric group.

Our paper has just appeared on the arXiv.

Posted in exposition, open problems, symmetric group | Tagged , , , , , , | 2 Comments

A niggling problem

Preparing my talk for the Research Day, I was reminded of a problem I can’t solve, that has niggled me for many years. Maybe someone else can solve it, or maybe I will be encouraged to do it myself. Here it is with some background.

A quasigroup is a set Q with a binary operation whose “Cayley table” is a Latin square. The Cayley table has rows and columns indexed by Q, and the entry in row a and column b is the composition or product ab. The Latin square condition means that

  • each element occurs once in each row; that is, given a and b, there is a unique x such that ax = b.
  • each element occurs once in each column; that is, given a and b, there is a unique y such that ya = b.

A loop is a quasigroup with an identity element e (satisfying ex = xe = x). If we label the first row and column with e, we see that the row labels coincide with the elements in the first column, and the column labels coincide with the elements in the first row.

In a quasigroup Q, the operatiions “left multiplication by a” (given by λa:xax) and “right multiplication by a” (given by ρa:xxa) are permutations. These permutations generate a subgroup of the symmetric group on Q, which is clearly transitive: to map a to b, we multiply by the element given by the “division axiom”. The group generated by all the left and right multiplications is called the multiplication group of Q.

In a loop, it is also important to consider the subgroup of the multuiplication group which is the stabiliser of the identity element e: this is called the inner multiplication group.

The multiplication group of Q may be the full symmetric group. Indeed, this is the “uninteresting case”. (This is one of the situations in which a smaller group is more interesting.) There are a couple of motivations for this view:

  • Jonathan Smith and Ken Johnson have developed a character theory of quasigroups, based on that for groups. In their theory, the character theory of Q is “trivial” if and only if the multiplication group of Q is doubly transitive.
  • A class of loops defined by Bruck and Paige in 1956 consists of the automorphic loops, those for which the inner multiplication group consists of automorphisms of the loop. This class includes groups, for which the inner multiplication group consists precisely of the inner automorphisms (conjugations) xa−1xa. The automorphism group of a loop is never the symmetric group except in some small cases, since there exist elements a and b for which ab is different from a and b (provided that |Q| ≥ 4), and the stabiliser of a and b in the automorphism group fixes their product.

Since it is no secret that there are a huge number of quasigroups, most not very interesting, the following result is not a surprise:

Theorem Almost all quasigroups have the property that their multiplication group is the symmetric group.

“Almost all” here means that the proportion of n-element quasigroups with this property tends to 1 as n tends to infinity.

(There is a diversion necessary here, and a small story. As I have set it up, we are counting “labelled” quasigroups, in which the elements are numbered q1, …, qn. It would be more natural to count them up to isomorphism. In fact this is the same, since almost all quasigroups have trivial automorphism group and so have n! labellings.

The fact that almost all Latin squares have trivial automorphism group was proved independently by Laci Babai and me at about the same time; the proof also works for Steiner triple systems and 1-factorisations of complete graphs. Laci got the result for Steiner triple systems into print first, and the rest became “folklore” for a while. It depended on the proof of the van der Waerden permanent conjecture by Egorychev and Falikman — more precisely, a weaker version proved earlier by Bang suffices.)

The proof is interesting, as it relies on a lovely theorem of Łuczak and Pyber:

Theorem Almost all elements of the symmetric group Sn lie in no proper transitive subgroup of Sn except possibly the alternating group An.

Now the multiplication group of a quasigroup is transitive, as we noted, and it contains the first row of the Latin square (regarded as a permutation); for a random quasigroup, this is a random permutation. So it is almost always the symmetric or alternating group. The final step uses a theorem of Häggkvist and Janssen, according to which the proportion of Latin squares whose rows are all even permutations is exponentially small.

Now the niggling problem is:

Problem Is it also true that almost all loops have multiplication group the symmetric group?

The above argument doesn’t work, because the first row of the Cayley table of a loop is the identity. However, the second row is a derangement. One of the oldest results in probability theory is that a positive proportion of elements of the symmetric group (in the limit, 1/e) are derangements; and since almost none of them lie in “small” proper subgroups of Sn, the argument concludes as before.

But this is not correct. The second row of a random Latin square whose first row is the identity is not a uniform random derangement, since the fist two rows can be extended to a Latin square in different numbers of ways depending on the chosen derangement.

For example, of the nine derangements in S4, three of them are products of two transpositions, and have four extensions to a Latin square; the other six are 4-cycles, and have only two extensions. So each derangement of the first type has probability 1/6, whereas one of the second type has probability 1/12.

Remarkably, it turns out (empirically) that this non-uniformity rapidly washes out as n increases:

Conjecture The probability distribution on derangements defined as above (where the probability of a derangement is the probability that a random Latin square with first row the identity has that derangement as its second row) tends very rapidly to the uniform distribution as n tends to infinity.

For example, for n = 7, the numbers of extensions of the first two rows to a Latin square for the various cycle structures of derangements are

  • (7): 6566400
  • (2,5): 6604800
  • (2,2,3): 6635520
  • (3,4): 6543360

So, from differing by a factor of 2 for n = 4, the probabilities agree to within a little over 1% for n = 7. For larger values, the agreement is even more striking.

There are some results by Nick Cavenagh, Catherine Greenhill and Ian Wanless on bounding the ratios of these probabilities, but they are very far even from showing that the ratios tend to 1.

If it could be shown that this distribution tends to uniform faster than the error term in the Łuczak–Pyber theorem, we would have solved the problem. But there may be other ways to attack it which I haven’t thought of yet.

While I am on the subject, I would like to say a bit more about the Häggkvist–Janssen theorem.

Problem What can be said about the distribution of the number of rows of a random Latin square which (as permutations) have even parity?

Since the message of the preceding conjecture is that there is a lot of near-independence in quite large pieces of a random Latin square, the natural conjecture would be that the distribution is close to binomial with parameter 1/2, at least for large n.

Evidence supports this conjecture fairly well, but the tails of the distribution seem a little heavier than it would predict. The exponential bound in the Häggkvist–Janssen theorem is substantially larger than 1/2n, and examination of small Latin squares suggests that this is with good reason.

But my feeling is that this is an effect of the small sizes which we can deal with. “Interesting” Latin squares are likely to be far from typical in this respect. For example, in the Cayley table of a group, either all rows have the same parity, or there are equally many even and odd rows. (The first alternative holds if the Sylow 2-subgroups of the group in question are cyclic.) These and other interesting quasigroups may be biasing the statistics. I expect it to hold for large squares.

Posted in open problems | Tagged , , , , | Leave a comment

Polymath

I told here the story of W. E. Opencomb, a nom de plume for a set of ten mathematicians (including me) at a research week at the Open University.

This and other examples show that large collaborations in mathematics, though not yet common, are not a new thing. But it is true that technology, and the leadership of people like Tim Gowers and Terry Tao, have changed the character of such collaborations.

Gowers proposed an experiment in collaboration on his blog in 2007, and receiving an enthusiastic response, set up the first Polymath project. The aim was to find an “elementary” combinatorial proof of the density version of the Hales–Jewett theorem. Success was declared in six weeks, though the write-up took a bit longer. The collaborators chose the name D. H. J. Polymath to publish the result: the initials for the theorem they had proved, and Polymath for the generic name of the collaboration, which used technological facilities such as blogs and wikis to enhance the collaboration.

There have been several Polymath projects since, not all of them so successful. But Polymath 8 has achieved much mathematics, and much notoriety, and is described by an article by D. H. J. Polymath in the current Newsletter of the European Mathematical Society, which I recommend.

The impetus for the project was the astonishing result by Yitang Zhang, that there are infinitely many prime pairs differing by at most 70000000. Tao fairly soon decided that improving the bound would make a good Polymath project, since there are many places where Zhang’s estimates could be refined, and these would involve a variety of mathematical and programming skills. Many people contributed, and eventually the bound was reduced to 4680.

Then James Maynard came up with a different argument which reduced Zhang’s bound to 600. (He has just been awarded the 2014 Ramanujan Prize for this and other work.) So it was decided to enlist him in the second phase of Polymath 8, and see how far this bound could be improved. They have got it down to 246, and there are various generalisations and conditional results as well.

One of the reasons for the wide interest created is that there was a “headline” figure, namely the best value so far achieved, and mathematicians on the sideline could watch this figure decreasing as the project continued, and read and understand the arguments used.

The EMS Newsletter article collects the perspectives of ten of the participants (Tao, Andrew Gibson, Pace Nielsen, Maynard, Gergely Harcos, David Roberts, Andrew Sutherland, Wouter Castryck, Emmanuel Kowalski, and Philippe Michel) on their involvement in the project. Some common themes run through their accounts:

  • One of the hardest things was to get used to making mistakes in public, with no chance to suppress them; but all the participants who commented on this felt that it was crucial for the success of the project that everyone was prepared to contribute and risk looking foolish.
  • Several participants, especially the younger ones, remarked on the danger for a non-tenured mathematician taking part in a Polymath collaboration, since no proper academic credit can be given; but none of them regretted their own involvement.
  • There was a lot of praise for the way that Tao as “ringmaster” handled the project, which was felt to have contributed to its success.
  • Everyone spoke of the excitement of the collaboration, and the exhaustion which it produced!

(In the Opencomb collaboration, the first point was not an issue, since we could stick our necks out and only appear foolish to the other nine participants; in Polymath 8, if not all the world, then a good crowd of spectators was watching.)

Posted in doing mathematics, the Web | Tagged , , , , , | Leave a comment

Research Day

Yesterday we had a very enjoyable event: the first-ever Research Day in the School of Mathematics and Statistics at St Andrews.

Seventeen of us spoke, the brief being to explain to the whole school what we are excited about. In addition there were a number of posters from students and others.

I learned a great deal about what my colleagues in various parts of Applied Maths and Statistics are up to: solitary waves in the interface between liquids of different densities, the interaction of the solar wind with the earth’s magnetosphere, analysis of spatially distributed data (or, do koalas have favourite trees?), and much more.

But perhaps the highlight for me was the prizewinning student poster, by Jonathan Hodgson, on doing magnetohydrodynamics in seven dimensions. It is clear how to generalise the scalar product, but what about the vector product? His approach was to use the purely imaginary octonions (the next step up from an interpretation in three dimensions using the purely imaginary quaternions, and so this struck a chord after the talks at the LMS event last Friday). He gave a very clear description of the structure (starting from the Fano plane with arrows on it which gives the simplest definition of the octonions) and of the problems which arise with this project. I have seen in a couple of places that some brave physicists wonder whether the octonions have a place in the “theory of everything”: this seemed a sober attempt to put the groundwork in place.

The down side of the day was that the university caterers hadn’t managed to deliver most of the sandwiches that had been ordered, so we had to sit through the afternoon talks less than fully satisfied. Perhaps this helped keep us awake.

I enjoyed myself, and I very much hope that this becomes a tradition!

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