Apology

To my friends in the United States of America: I am sorry, but I do not expect I will be visiting you during the term of office of the current President.

This for two reasons. First, I find his policies terrifying (his encouragement of a new nuclear arms race, his disregard for the facts about climate change) or despicable (his attitude to those of different gender, skin colour, religion or sexual orientation to himself); and second, in the current climate I would be scared for my own safety in the USA (if I would even be allowed in).

It is sad to see the much-praised constitutional system of checks and balances torn up with such ease.

Posted in Uncategorized | 4 Comments

Reciprocity

The cycle index of a finite permutation group is a multivariate polynomial (with one variable si for each index i not exceeding the degree of the group) which is the generating function for the numbers of cycles of different lengths of the permutations in the group. Thus, it is a rather elaborate gadget. Its role in enumeration under group action is well known; that is not my subject here. Because of that, I will simplify things: the cycle index is traditionally divided by the order of the group, but to keep my polynomials integral I will not do this.

Because of its relative complication, certain specialisations of it have been studied. Christopher Harden wrote his PhD thesis at the University of Essex on the fixed point polynomial, the generating function for the numbers of fixed points of elements of G (obtained by putting all variables except s1 equal to 1); he wrote a paper with his supervisor David Penman, which is available here in the Electronic Journal of Combinatorics.

Recently, Jason Semeraro from Bristol proposed to me another specialisation, the cycle polynomial, FG(x), the generating function for the numbers of cycles of elements of G (including fixed points), obtained by putting all the variables of the cycle index equal to x. Again, it is a monic polynomial whose degree is the degree of G. Jason asked me a question about it, but before I could reply, he had answered his own question. But he had caught my interest, and we have just posted a paper on the cycle polynomial on the arXiv.

I’d like to draw attention to one interesting feature, and introduce it in a rather different way from the paper.

First, observe that since all the terms are positive, the cycle polynomial has no positive roots.

The parity of a permutation is the degree minus the number of cycles. As is well known, a permutation group either contains no odd permutations, or half its elements have even parity and half have odd parity. In the first case, all terms of the polynomial have exponents congruent to the degree modulo 2, and so the cycle polynomial is an even or odd function of x according as the degree is even or odd. It follows that the polynomial has no real roots at all except for 0.

The case where the group contains both even and odd permutations is more interesting. It can be shown that the integer roots are 0,−1,−2,…,−a for some positive integer a; this integer is a curious new invariant of a permutation group.

Does that remind you of anything?

The chromatic polynomial PΓ(x) of a graph Γ is the polynomial whose value at a positive integer q is the number of proper vertex-colourings of the graph with q colours. It has no negative real roots; its integer roots are 0,1,2,…,a, where a is one less than the chromatic number of Γ, the smallest number of colours required for a proper vertex-colouring.

Is there any connection between FG(x) and PΓ(−x)?

It turns out that there is a better question lurking here. In 2008, Bill Jackson, Jason Rudd, and I defined the orbital chromatic polynomial of a pair (Γ,G), where Γ is a graph and G a group of automorphisms of Γ. Evaluated at a positive integer q (and, with a slight modification to fit what is going on here, divided by the order of G), it counts orbits of G on proper vertex-colourings of Γ with q colours. Koko Kayibi and I wrote another paper examining the location of its roots.

Now it happens surprisingly often that, given a permutation group G, there is a G-invariant graph Γ such that the orbital chromatic polynomial of the pair (Γ,G) is (−1)nFG(−x).

This is an example of what Richard Stanley called a combinatorial reciprocity theorem.

I have made the two polynomials different in one respect: with the cycle polynomial, the coefficients count things; with the orbital chromatic polynomial, it is the evaluations that count. But this is not a real difference. The cycle polynomial evaluated at the positive integer a (and divided by the order of G) counts orbits of G on unrestricted colourings of the domain with a colours, whereas the orbital chromatic polynomial counts orbits on proper vertex-colourings of Γ.

For example, take Γ to be a 4-cycle, and G the dihedral group of order 8. The cycle polynomial is x(x+1)(x2+x+2), while the orbital chromatic polynomial is x(x−1)(x2x+2). So G has six orbits on 2-colourings, one of which is a proper vertex-colouring. (This was the example that first alerted me to what was going on.)

I won’t go through listing examples; there are several in the paper, and in particular we have decided exactly which pairs satisfy this reciprocity. But the big open question is:

For which pairs (Γ,G) does this reciprocity hold?

We have determined them in the case where Γ is a complete or null graph or a tree. But there is more to do. In particular, a solution which simply involved a classification would be less enlightening than one which gave some conceptual reason for the phenomenon.

I would be very interested to know if this reciprocity has been observed in similar situations involving a permutation group! (Stanley gave several examples, none of them involving permutation groups. In particular, he gives the correct reciprocity theorem for the chromatic polynomial; it involves acyclic orientations. I have no idea if there is a connection.)

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

70

The days of our years are threescore years and ten; and if by reason of strength they be fourscore years, yet is their strength labour and sorrow; for it is soon cut off, and we fly away.

So today I have achieved the days of my years; I hope that I will have strength enough to prolong them a bit, since I am enjoying myself at the moment, and don’t want to fly away just yet.

In the past year, I have put eleven papers (including one update) on the arXiv, involving 26 coauthors and totalling 292 pages. Quite a good record, I think, and one that should keep the REF accountants off my back for a while.

On my birthday, I lectured at 12 and saw a project student at 3. So I’m spending quite a bit of time on teaching as well.

And, even better: Jason Semeraro and I have nearly finished writing a paper, which I hope to write about here shortly; and on Saturday, Nicolas Thiéry and Justine Falque came to St Andrews to talk about oligomorphic permutation groups (one of my favourite topics, which is overdue a mention here) and to walk on West Sands.

Posted in Uncategorized | Tagged | 5 Comments

Impact update

My comments on impact were cited by Ursula Martin and her co-author Laura Meagher here. Worth a look.

PS Here’s the abstract:

This empirical study explored how research can generate impacts by investigating different sorts of impacts from one academic field—mathematics—and the diverse mechanisms generating them. The multi-method study triangulated across: (1 and 2) content analysis of impact case studies and environment descriptions submitted to the UK Research Excellence Framework (REF) assessment; (3 and 4) a survey and focus group of heads of mathematics departments; and (5) semi-structured interviews. Mathematics has had a full range of impact types, particularly conceptual impacts, although more tangible instrumental impacts were prioritized for REF. Multiple mechanisms were utilized, but seldom appeared in REF case studies. Long-term relationship building and interdisciplinarity are particularly important. Departmental culture and certain knowledge intermediaries can play proactive roles. In sharp contrast to simplistic linear narratives, we suggest that appreciation of diverse impact types, multiple, often informal, mechanisms and dynamic environments will enhance the likelihood of meaningful impacts being generated.

Posted in Uncategorized | Tagged | Leave a comment

Automorphism groups of transformation semigroups

I have been in the transformation semigroups game for nearly ten years now, but I still feel that I am finding my feet.

Here is apparently a huge difference between permutation groups and transformation semigroups, one which is still not fully understood. A permutation group may have automorphisms which are not induced by conjugation in the symmetric group. The most spectacular example of this is the symmetric group of degree 6, which has an outer automorphism, as I have discussed here. (This is the only symmetric group, finite or infinite, which has an outer automorphism.) This beautiful configuration is intimately connected with other interesting phenomena; I outlined here how to use this to construct the Mathieu groups M12 (which also has an automorphism not induced by a permutation) and M24, and one can go on to the Conway groups and the Monster. Chapter 6 of my book with Jack van Lint explains also how to use it to construct (and show uniqueness of) the projective plane of order 4 and the Moore graph of valency 7 (the Hoffman–Singleton graph).

Could anything similar happen for transformation semigroups?

It appears not. Forty years ago, R. P. Sullivan proved a very general theorem which implies, in particular, that a transformation semigroup on a set X which contains all the constant maps on X has the property that its automorphisms are all induced by permutations of X, so that its automorphism group is isomorphic to its normaliser in the symmetric group on X. (To show this, observe first that an automorphism of the semigroup must preserve the set of constant maps, which is naturally bijective with X; then we must show that an automorphism which fixes all the constant maps must be the identity.)

Now this is something interesting. The synchronization project, which was my introduction to semigroup theory, is concerned with those permutation groups G with the property that any transformation semigroup containing G and at least one singular transformation necessarily contains all the constant maps. It follows that if a transformation semigroup contains a synchronizing group, then all its automorphisms are induced by permutations. Moreover, we know that the class of synchronizing groups contains the 2-transitive groups (even the 2-homogeneous groups) and is contained in the class of primitive groups; this is a large and interesting class of permutation groups.

So what about transformation semigroups which contain a singular transformation and whose group of units is a non-synchronizing permutation group? For these, João Araújo, Wolfram Bentz and I have made the first small breakthrough. Embarrassingly small, I would say.

Assume that G is a primitive permutation group. We say that G synchronizes the singular map t if the semigroup generated by G and t contains a constant map (and, hence, contains all constants). Now we know, from our paper with Gordon Royle and Artur Schaefer which just appeared in the Proceedings of the London Mathematical Society, that a primitive group of degree n synchronizes any map whose rank (cardinality of the image) is 2 or at least n−4 (and, indeed, we conjecture that the upper value can be improved to n−5, but the labour involved in showing this with our techniques would be prohibitive). So the obvious case to consider is maps of rank 3.

Our theorem says that, if a transformation semigroup contains a primitive group and a map of rank 3, then all its automorphisms are inner.

There are some interesting examples of such groups to be found in the paper. These include the automorphism groups of the Heawood, Tutte–Coxeter, and Biggs–Smith graphs, acting on the edge sets of the graphs, and two different actions of the Mathieu group M12 on 495 points. The last two stand in a curious relation: they are automorphism groups of a pair of graphs where the vertices of one graph correspond to the triangles (images of endomorphisms of minimal rank) of the other, adjacency of vertices corresponding to intersection of triangles.

We go so far as to conjecture that the “rank 3” assumption can be dropped; all we need is a primitive group and a singular map. But we are a long way from the proof of this at the moment. Still, hopefully we have taken the first step, so here is a nice project for the new year.

Posted in doing mathematics, open problems, Uncategorized | Tagged , , | Leave a comment

Research Day 2017

Yesterday was the School’s third Research Day, a successful and enjoyable event involving contribution from all divisions. Hopefully the event is now self-sustaining.

Short summaries of a few of the talks follow.

The first two speakers both had “automata” in their titles and both apologised for not talking about them due to shortness of time. Alan Hood told us about avalanche models of solar flares; these have been done using cellular automata, which don’t really take the physics into account. He and his colleagues have produced the first demonstration based on the differential equations of magnetohydrodynamics.

Then Tom Bourne spoke about regular languages. These are obtained from some basic building blocks (the empty set, the set containing the empty word, and the set containing a single one-letter word) by closing under union, concatenation, and the “star operation”. In these terms, the “star-height” is a measure of the complexity of a language. Noting that the set of regular languages is closed under complementation, he defined a “modified star-height” which allows the use of complementation in the construction. Now not a single regular language with modified star-height greater than one is known; do any exist?

Isobel Falconer told us about Maxwell’s encounter with the inverse square law of electrostatic attraction. It was basic to his main work; towards the end of his life he turned his attention to testing it experimentally. The inverse square law implies that there is no charge inside a closed conductor; this can be tested experimentally, but does the converse hold? Maxwell’s demonstration of this was flawed since the “no charge inside” principle implies the inverse square law if it holds for all possible radii of the conducting sphere, while he only tested one radius.

Helen Burgess talked about transfer of energy to larger scales (inverse cascades) in turbulent flow with vorticity, and found universal phenomena (in particular, three different scaling regimes) which seem to apply in completely different phenomena also.

From Patrick Antolin’s talk, I learned something I didn’t know: it rains on the sun! This puts the song “The sun has got his hat on” in an entirely new light!

Jonathan Fraser and his student have a remarkable result. Erdős and Turán posed the problem: if X is a set of natural numbers such that the sum of reciprocals of its members diverges, does X necessarily contain arbitrarily long arithmetic progressions? (The special case of the primes was solved fairly recently by Green and Tao, and was a big breakthrough.) The problem appears inaccessible, but they have proved an approximate version: such a set contains subsets which are arbitrarily close to long arithmetic progressions, in a suitable sense. Indeed, they prove this under the weaker assumption that X has Assouad dimension 1.

Negative feedback loops in gene regulation can produce oscillatory behaviour. The mechanism was not clear until Mark Chaplain showed that diffusion was a necessary part of the process. Cicely Macnamara told us about further investigations of this process, which can generate segmentation of bodies in embryonic development.

Finally, Alex Craik told us about William Welwood, St Andrews’ first professor of mathematics. He lived in difficult times, in the troubles between Episcopalians and Presbyterians following the Scottish reformation, and indeed was stabbed more than once and later forced to resign his chair. His one known output is a scheme for removing water from coal mines, which he proposed to do with a siphon, although he admitted that tests of the principle had been unsuccessful. (This was in the 16th century, before the work of Galileo and Torricelli; atmospheric pressure was not understood then.) Purely by chance, we had been reading about Culross, a village in western Fife which had a coal mine in the 16th century extending under the Firth of Forth, which eventually closed because of the water that leaked in; Welwood’s invention would not have helped in this case!

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

Diversions

These days I travel fairly often on the East Coast Main Line between London and Leuchars (for St Andrews).

Last spring, for one journey they had announced when I made the booking that the train would leave Kings Cross 13 minutes earlier than usual. I kept a lookout to see if I could spot the reason. Just after Peterborough we turned off onto a line that took us through the very flat daffodil fields around Spalding, and the city of Lincoln with its cathedral, before rejoining the main line just before Doncaster.

Last weekend, we had a similar (but unplanned) diversion. When we boarded at Kings Cross there was no indication of any problem. But, unusually, I tried using the 15 minutes of free wi-fi. The main page showed the train’s progress, and timings for the trip. They showed us on time to Newcastle, but 53 minutes late at Berwick-upon-Tweed. They were right about the latter, but wrong about the former.

On arriving into York, it seems they had realised there was a problem (caused by overrunning engineering work). So we would have to take a diversion, and not stop at Darlington; passengers for Darlington were told to go to Newcastle and take a bus from there. (It might have been kinder to put them on a bus in York.) We waited twenty minutes, while they located a driver who knew the route the train was going to take.

We started off, and hurried along to Northallerton. Then we turned off on a line that was new to me, passing through Hartlepool and Sunderland, until finally rejoining the main line just before crossing the Tyne bridge at Newcastle, where we arrived almost an hour late.

Inevitably, then, we lost more time, and were an hour and four minutes late at Leuchars.

A question: How long do I have to commute between London and Leuchars before I can expect to have seen all possible diversions from the main line?

As a matter of record, when my daughter started her university course at Manchester, I went up from Oxford on the train; because of weekend engineering works we were diverted via Worcester and Nuneaton, quite an indirect route!

Posted in geography | Tagged , , | 2 Comments