NBSAN in St Andrews

This week, during a spell of lovely spring weather and new blossom, the 20th meeting of the North British Semigroups and Applications Network was held in St Andrews, organised by Markus Pfeiffer.

It was good to see old friends such as Rick and Hilary Thomas, Vicky Gould, John Fountain, John Meldrum, and Mark Kambites.

I’ll just discuss here a few talks which for me were highlights.

First among these was Bob Gray’s opening talk of the meeting, entitled “Crystal monoids”. It was mostly about the plactic monoid, and fortunately (since that word is not in my dictionary – it is “plaxique” in French, but this is not clear either – a correspondent on MathOverflow derives it from Greek “plax”, plaque, which could perhaps be linked with “tableau”) he spent most of the talk telling us what this monoid is, taking us on his journey of “learning new things”. He gave us three completely different descriptions of it:

• The first description was in terms of generators and relations. The plactic monoid P_n is generated by n elements, which are ordered (and which we can take to be 1,2,…,n), satisfying the Knuth relations: if x < y < z, then zxy = xzy and yzx = yxz; and if x < y, then xyx = xxy and xyy = yxy.
• A description using the Robinson–Schensted–Knuth insertion rule for semi-standard tableaux (see below);
• A description using Kashiwara’s notion of crystal graphs, crystal bases, and Kashiwara operators, which I won’t even attempt to describe here.

The next post in my series on the symmetric group was always intended to be about Young diagrams and tableaux and their connection to the representation theory of the symmetric group. I still intend to do this sometime, but it hasn’t been done yet. If it had, I could have referred you to it for the procedure of inserting an element into a tableau, except for one thing: there are several conventions about tableaux, and even Bob and his co-author Alan Cain couldn’t agree! Indeed, Ian Macdonald, in his great book on Symmetric functions and Hall polynomials, says, after explaining the British and French conventions for tableaux, that Francophone readers of his book should read it upside-down in a mirror!

Here is a brief account, in the form that Bob Gray used. A Young diagram is a collection of boxes aligned at the top and the left, so that row lengths are weakly decreasing going from top to bottom. A semi-standard tableau is obtained by putting numbers from the set {1,2,…,n} into the boxes so that rows are weakly increasing from left to right and columns are strictly increasing from top to bottom.

To insert a number x into a tableau: first, try to put it at the end of the first column. If it is strictly larger than the last entry in the first column, this is fine, and we can add the number in a new box and stop. Otherwise, we go up the column until we find the first number y which is not greater than x; x “bumps” y out of its box, and we then (recursively) insert y into the tableau consisting of the remaining columns.

(If you compare this with the version in my Combinatorics book, there are three differences: first, I insert elements into rows rather than columns; secondly, I assume that the numbers are all distinct, so that the tableaux are standard (rows and columns both strictly increasing); and third, I maintain a second tableau to record the boxes in order of creation. This gives rise to a bijection between permutations and pairs of standard tableaux of the same shape.)

Now there is an equivalence relation defined on words over the alphabet {1,2,…,n}: two words are equivalent if, when we successively insert them into the empty tableau, the results are equal. This equivalence relation turns out to be a congruence on the free monoid generated by the alphabet (the set of all words with the operation of concatenation), and so the quotient is a monoid. This is the plactic monoid.

One can recover a word from a tableau by reading it “Japanese fashion”: down each column, and columns from right to left. This word belongs to the congruence class corresponding to the tableau, and can be regarded as a “canonical representative” (though there are other possible choices for this).

The results of Cain, Gray and Malheiro (which he had little time to describe) are that the plactic monoid has a finite complete rewriting system and an automatic structure. He did explain these terms, but for me the most valuable thing was, as I said, the three descriptions of the monoid.

Later the first afternoon, Alan Cain spoke further about this work. They have done similar things for several other monoids.

The essential idea is to take any combinatorial structures with a notion of “insertion”. As well as semistandard tableaux (giving the plactic monoid), they have considered the hypoplactic monoids (from “quasi-ribbon tableaux”), the sylvester monoids (from binary search trees), and a couple of others. (Alan insisted on the lower-case letter here since sylvester does not commemorate the mathematician of that name but the association with trees. My dictionary doesn’t give it as a word but does list “sylvestrian” as the adjectival form.)

After the conference dinner in the newly-reopened Byre Theatre, I walked home along the Kinness Burn where I heard a thrush singing a magnificent song, and saw a couple of bats flying over the river in the twilight, while a crescent moon and Venus hung in the western sky.

The next day, the opening talk was by Paul Bell. He tried so hard to give us careful background explanations that he ran a bit short of time; but better that way, in my view. He was talking about decidability and complexity of problems about matrix semigroups. He gave us clear accounts of the undecidable problems which he and his coauthors have coded into matrix semigroups for the negative results.

One of these was the Post Correspondence Problem PCP(k). We are given k dominoes, aligned vertically. On the top and bottom halves of each domino are written words over the two-letter alphabet {a,b}. (There are an unlimited number of copies of each domino available.) The task is to choose a sequence of dominoes and put them in a row such that, when the words on the top parts of the dominoes are read and concatenated in order, and the same for the bottom parts, the results are equal. This problem is known to be decidable for k = 2, and undecidable for k = 5.

Another problem used in this way was Hilbert’s 10th (solvability of Diophantine equations). For NP-completeness he used the subset sum problem.

Matthew Taylor introduced us to the tropical semiring T, whose elements are the real numbers together with −∞; addition is the maximum function, and multiplication in T is addition in R. The tropicalisation of schemes (from algebraic geometry) has some connection to quotients of free T-modules in finitely many variables (based on work a couple of years ago by the Giansiracusa brothers), so he embarked on the classification of 2-generated T-modules, involving lots of pictures of plane configurations involving horizontal, vertical and diagonal lines, as you might expect. [25/04/2015: Wording changed at Mark Kambites’ suggestion. I don’t understand the tropicalisation of schemes well enough to be precise here! Mark says that in the Giansiracusa approach the tropicalisation of a scheme is a sheaf of T-algebras, but for some purposes it is enough to consider T-modules; also, there are other approaches to the problem.]

And why is it called “tropical”? Not, as I first thought, to contrast it with “polar geometry”; but in honour of one of the pioneers, the Brazilian mathematician Imre Simon, though there seems to be some disagreement about who actually coined the term (and in any case São Paulo, where he worked, is barely tropical, lying 23 1/2 degrees south of the equator).

A very nice conference, crossing many boundaries, and with some excellent expositions.

I concluded the conference with a talk entitled “Finding where you are”, involving two aspects of synchronization for automata, both of which I have discussed here before. (Perhaps appropriate: we were in the third lecture room that had been used for the meeting.) My slides are in the usual place.