and G is for …

I am in Oxford for the birthday conference for Dan Segal and Aner Shalev. I will write something about that when time permits.

This is just to report a discovery. There is now an official “Oxford Mathematical Alphabet”. I have lost count of the number of lectures I heard in Oxford which began “Let G be a group.” But not any more, it seems. In the Oxford mathematical alphabet, G is for … Growth Tensor.

Advertisements
Posted in Uncategorized | Tagged | 3 Comments

Q is for quantum?

The letter q has three, or maybe four, standard uses in mathematics.

It stands for “quantum”, and it is fashionable now to produce quantum versions of everything from chromatic number of a graph to the symmetric group.

Related to this, q occurs as a “deformation parameter” in quantised versions of standard algebraic structures. That is, there is an algebra depending on a parameter q, and as q tends to 1, the algebra becomes a “classical algebra”. There can be real advantages to doing this. It may be that the representation theory of the classical algebra is difficult, but that of the deformed algebra is easier, and we can get some information about the classical case by taking a limit.

It is also quite common to use q as a formal parameter in certain power series counting objects of interest. For example, consider the problem of counting lattice paths from the origin to the point (m,n), where m and n are non-negative integers. Each step in the path must be a unit step in either the easterly or the northerly direction. We have to take altogether m+n steps, of which m must be easterly and n northerly; these steps can be taken in any order, so the number of paths is the binomial coefficient, which I shall write as Bin(m+n,m). But now let us refine the count. Each such path, together with the X-axis and the line x = m, encloses a certain area A (between 0 and mn inclusive). Now if, instead of counting 1 for each path, we count qA to a path enclosing an area A, the sum we get is the Gaussian coefficient Gauss(m+n,m)q. This is calculated by replacing each integer k in the expression for the binomial coefficient by the “q-integer” qk−1. Since the number of factors in numerator and denominator is the same, an application of l’Hôpital’s rule shows that the Gaussian coefficient tends to the binomial as q→1.

Finally, the number of elements in a finite field (which is a prime power) is universally referred to as q. This is so ingrained that the finite fields community call their annual conferences Fq, a standard notation for a field of q elements.

Now something unexpected and wonderful holds. The binomial coefficient Binom(n,k) counts the number of k-element subsets of a set of size n; and the Gaussian coefficient Gauss(n,k)q counts the number of k-dimensional subspaces of an n-dimensional subspace over the field Fq.

There are many analogies and parallels between the combinatorics of subsets of a set and the combinatorics (or projective geometry) of subspaces of a vector space, especially over a finite field. This leads us to sometimes describe the former as “geometry over the field with one element”, as I have discussed on another occasion.

This long introduction finally brings me to my topic, a paper entitled “Defining the q-analogue of a matroid” by Relinde Jurrius and Ruud Pellikaan, which appeared in the Electronic Journal of Combinatorics last month.

Matroids are combinatorial structures which describe many kinds of “independence”: linear independence in a vector space; algebraic independence over a ground field in an algebraically closed field; forests in a graph; partial transversals of a set system; affine independence in an affine space; and so on. They were introduced by Whitney, and their theory was developed by Tutte, Rota, welsh, and many other mathematicians. Take a look at the Matroid Union blog to learn more.

Jurrius and Pellikaan are not producing a quantum version of matroid theory. Rather, as in the last case above, they are defining a structure over a field with q elements to be the analogue of a matroid in the usual sense over the “field with one element”. More precisely, they define a q-matroid to be a finite-dimensional vector space E over Fq, together with a rank function r from the set of subspaces of E, satisfying exactly the same conditions as for a matroid, namely, for all subspaces A and B of E,

  • 0 ≤ r(A) ≤ dim(A);
  • if A ⊆ B, then r(A) ≤ r(B);
  • r(A+B)+r(AB) ≤ r(A)+r(B).

Of course, matroids can be defined in many other ways: in terms of their independent sets, bases, circuits, and so on. Something a little unexpected emerges. For the analogue of independent sets, for example, we have a collection of subspaces called independent spaces, satisfying exact analogues of the independent-sets axiom for matroids, but with an extra axiom, which cannot be dispensed with. It states that if A,B are subspaces, and I,J are maximal independent subspaces of A,B respectively, then there is a maximal subspace of A+B which is contained in I+J.

About halfway through the paper comes the motivation for studying q-matroids. Just as ordinary (representable) matroids arise from (linear) codes, it turns out that q-matroids arise from “rank metric codes”, structures using the rank of the difference between matrices as a measure of how far apart they are.

Right at the end of the paper, they mention that the notion of a quantum matroid has been defined by Paul Terwilliger; it is closely related to that of q-matroid. There is also related work by Henry Crapo.

The paper contains many research topics. One of these concerns the Tutte polynomial. How should it be defined in such a way that Greene’s link between Tutte pollynomial of a matroid and weight enumerator of the corresponding linear code has an analogue for q-matroids and rank metric codes?

Posted in Uncategorized | Tagged , , , , | 2 Comments

Linstat 2018

Or, to give the full title, International Conference on Trends and Perspectives in Linear Statistical Inference, with Celebration of Tadeusz Caliński’s 90th Birthday.

Będlewo Castle

The conference was in Będlewo Castle, once a private residence for a noble family which had more than its share of scandal, now a mathematics conference centre something along the lines of Oberwolfach, with nearby woods for walking, and in a village with a stork’s nest (now inhabited by house martins) on top of the church tower.

I have been to several statistics conferences before, but this is the first time I have ever spoken at one. And more: I organised a session on Combinatorics with applications to experimental designs. I will say a little bit about this later; but here is my team.

Special session speakers

It was a very enjoyable conference (or would have been, had I not had so many urgent jobs hanging over my head, including two MSc dissertations to read which arrived while I was at the conference). On Tuesday there was a special session for Tadeusz Caliński’s 90th birthday. His career has been truly remarkable. He is responsible for the close links that have existed for more than 50 years between Polish statisticians and those in many other countries including the UK, France, Italy and the Netherlands. He managed to travel to France even after the declaration of martial law in Poland, because the collaboration had been agreed at high level between the French and Polish governments. (But a couple of years later he was refused permission to travel to Canada, ostensibly for some stupid reason which I do not recall, but actually because he was not a party member but, worse, a supporter of Solidarity.) Many friends he met in the 1960s on his early travels to the west are now dead, but many of those who are still alive had come to the conference to honour him, including Gavin Ross and Rob Verdooren. (But, on the other hand, there were many talented young people there.)

On Tuesday evening there was a concert of music by a string quartet, slightly marred by the fact that people were unsure about when each piece was finished. But the musicians did a good job, and we were regaled with stories about the composers.

On Wednesday there was a choice of excursions, to Kórnik Castle, or to walk in Wielkopolska National Park – I chose the latter. The park was very dry because of the unusual weather, and we were told that the lakes were somewhat polluted (indeed, we saw a machine whose purpose was to help oxygenate the lake water). After the walk they had put out an impressive spread of food for us, but we didn’t fall on it like locusts, since we knew that there would be a barbecue when we got back to Będlewo. The barbecue, as well as huge amounts of food, featured entertainment by a group of musicians in some kind of traditional dress playing violins and bagpipes.

Castle and frog

Thursday was the Conference dinner, and presentation of prizes to the young
researchers. A pianist entertained us during the dinner.

I will mention just two talks, which for me were the highlights of the meeting.

Friedrich Pukelsheim, from Augsburg, was a statistican, who wrote a book on optimal design. He switched fields, and is now a sociologist, or political scientist, who looks at electoral systems (with a mathematician’s eye).

Many legislatures have, in some form, a principle known as degressive proportionality: the higher the population of a region, the larger the ratio of electors to representatives. But the European parliament is unusual in having this as a formally stated law. Unfortunately, the last election failed to meet this requirement precisely. Friedrich was on a small committee of mathematicians charged with ensuring that the principle is complied with in future. The European parliament is also unusual in trusting mathematicians to do this job, though they don’t trust them enough to accept a formula for the allocation of seats to countries, so the process will have to be repeated for the following election. Friedrich gave us an analysis of the case of Catalonia, where the legal requirements are somewhat contradictory, and in any case are based on population figures from the 1970s. He has written a book, which he recommended as a present for our loved ones.

I have worked a bit on optimality criteria for block designsl the most commonly used of these can be expressed in terms of the Laplacian eigenvalues of the concurrence graph of the design. Thus, A- and D-optimality maximise the harmonic and geometric means of the nontrivial eigenvalues, while E-optimality maximises the smallest eigenvalue.

In a nice but fast-paced talk, young researcher Samuel Rosa used graphs in a different way. We are comparing n different treatments, with no blocking factors, and we have a collection of pairs of treatments whose comparisons we are most interested in. A classical case involves a comparison of just two treatments; we should allocate experimental units as equally as possible to the two treatments.

In the general case, the interesting comparisons form the edge set of a graph; our task is to allocate weights to the treatments, giving the proportion of experimental units which should be allocatedd to them, in an optimal way. (Here, unlike the former case, the graph is given in advance.) It turns out that, again, the optimal allocations are determined by the Laplacian matrix of the graph. If I got the details right, assuming that the Laplacian has rank n−1, then the D-optimal assignment is uniform; the A-optimal weights are proportional to the square roots of the vertex degrees; and the E-optimal weights are proportional to the vertex degrees.

Quite a few statisticians use Jordan algebras in their work. So I put my neck on the block and talked about the notion of Jordan schemes (a generalisation of association schemes). However, from some of the other speakers, I realised that there was a mismatch between the statisticians’ notion of Jordan algebra and mine. After a robust discussion with Roman Zmyślony, things became a bit clearer to me, and I offered to write up some notes on this. I will report when I have done the job.

I had a bit of trouble getting the Polish ogonek on the first e in Będlewo in my slides. The solution I finally used was a package optimised for Computer Modern and Times Roman, but even the package authors agrees it is not entirely satisfactory for other fonts.

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

The existential transversal property

One of the first things that João Araújo introduced me to when we started collaborating, after synchronization, was the universal transversal property: a permutation group G on the set {1,…,n} has the k-universal transversal property (k-ut for short) if, given any k-subset A and k-partition P of the domain, there is an element of G mapping A to a transversal to P. (Here I say “k-subset” for a subset with k elements, and “k-partition” for a partition with k parts.

This appealed to me because it resembles the classical notion of k-homogeneity (or k-set transitivity): G has this property if, given any two k-sets A and B, there is an element of G mapping the first to the second.

One of the first results on this was by Livingstone and Wagner in 1964. Their paper has three main theorems; the first says that, if k ≤ n/2, then a k-homogeneous group is (k−1)-homogeneous. The proof of this theorem is a short and elegant application of character theory, which can be rewritten as pure combinatorics. João and I were able to prove that, under the same restriction, a group with the k-ut property also has the (k−1)-ut property. Our proof, however, was much less short and elegant, involving some nontrivial group theory (including the Classification of Finite Simple Groups.)

It turns out that this is relevant to semigroup theory. Let t be a mapping of the domain which has rank k (image of size k). Semigroup theorists will not be surprised to learn that, if G has k-ut, then every such map is regular in ⟨G,t⟩ (that is, has a von Neumann inverse). But then our result implies that the same is true for all elements of smaller rank as well; that is, the entire semigroup ⟨G,t⟩ is regular.

In the paper we went on to classify the groups with k-ut (with some exceptions we were unable to decide) for 3 ≤ k ≤ n/2. (It turns out, happily, that the 2-ut property is exactly equivalent to primitivity, so we didn’t feel obliged to give a complete list.)

So what next? We went on to consider the k-existential transversal property, or k-et for short. This requires that there is a “witnessing” k-set A such that, for any k-partition P, there is an element of G mapping A to a transversal for P. This is substantially weaker than the k-ut property, but does have the consequence for semigroups that, if the image of t is a witnessing set for k-et, then t is regular in ⟨G,t⟩. The problems are considerably harder, and we had to recruit Wolfram Bentz to help us.

It turns out that one can say quite a bit. We suppose that G satisfies k-et, with k ≤ n/2, as before. We can deal completely with the case that G is intransitive: for k ≥ 3, it must fix a point and act (k−1)-homogeneously on the remaining points. So we can suppose that G is transitive. Here are some of our conclusions.

  • If k ≥ 8, then G must be the symmetric or alternating group. 8 is best possible here: the Mathieu group M24 has the 7-et property.
  • There are groups satisfying k-et but not (k−1)-et: indeed, just two of them, the groups 24:A8 and 24:A7, with degree 16, satisfy k-et for k = 1,2,3,4,6 but not for k = 5.
  • If k ≥ 4, then G is is primitive (for n ≥ 9); and it is 2-homogeneous, with just two exceptions: the Higman–Sims group and its automorphism group, acting on 100 points.

Now if G is k-et with witnessing set A, and also is (k−1)-ut, and t is a map with image A, then ⟨G,t⟩ is regular; since as we explained above the elements of rank k (whose images are of the form Ag for gG) are regular, and the (k−1)-ut property ensures that all maps of smaller rank in the semigroup are regular. But the condition of (k−1)-ut is not necessary for regularity; if it fails, then the semigroup may or may not be regular, and in most cases we can say which possibility occurs.

The methods we needed to develop to tackle this harder problem turn out to be useful in advancing further our knowledge of groups with the k-ut property, so we also had a glance at this, which included correcting a couple of small mistakes in the earlier paper.

The et paper has just appeared on the arXiv: 1808.06085.

What next? There is a dual form of k-et, where we specify a witnessing k-partition P, and ask that any k-set has an image under G which is a transversal for P. A job for another day.

Of course, the ultimate in this line would be a complete characterisation of the pairs (G,t) for which ⟨G,t⟩ is regular. This is not currently on our radar screen, though.

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

Anniversary

Today is the 50th anniversary of my arrival in Europe. I arrived in Southampton on the Shaw Savill Line ship “Southern Cross” on 21 August 1968, after a 36-day voyage from Sydney. I intended to stay three years or so to get my doctorate, but in the event I am still living here, having been given indefinite leave to remain in the United Kingdom in 1971.

Southern Cross

When I visit Autralia, it always feels like home. But I feel comfortable in Europe (though a bit less so now, since the rise of nationalism in many parts of the continent, something I don’t understand).

I suppose that in some sense I count as one of the “Windrush generation”.

Posted in history | Tagged , , , | 11 Comments

Migrations

Derek Robertson

Derek Robertson is an artist based in Balmerino in Fife, site of a ruined abbey and subject of a poem by William McGonagall. His studio is right on the Fife Coastal Path. His main interest is wildlife, and in my view he is extremely good at depicting it. Take a look at his website.

One of his interests was in depicting migrating birds, and he had travelled to North Africa and the Middle East in his researches. A couple of years ago, when the world watched appalled at the plight of human migrants, he recognised some of the places he had visited, and decided that he had to get involved. So he travelled there, helped the migrants in various ways, and produced a series of paintings with the title “Migrations”, combining images of migrating birds and migrating humans (the latter often in terrible conditions).

Indeed, the picture he is pointing to in the photo (work in progress) is based on a remarkable event that he witnessed in Jordan; but I can’t really tell it here, and anyway you can’t even see the incomplete picture very well in my photo.

He was a featured exhibitor at the recent Pittenweem Arts Festival. His exhibition in the Old Town Hall was of wildlife pictures, but a smaller exhibition in the Church Hall showed pictures from his Migrations series.

Enough to say that I was blown away by these, although they were not for sale. But we met Derek later when we got to the Town Hall, and he said that he could arrange for one to be printed for us.

The one I chose was called “For the wayfarer that you meet”, and featured a bee-eater against a background showing the hospitality of the people of Jordan to travelling guests. Apart from the fact that I think it is a great painting, the bee-eater brings back memories of being entertained by this colourful and extremely agile flier in a park in Cairns some years ago. If you go to this page and scroll down, you can see an image of the picture, and also read about the creation of this remarkable series.

Today the print was ready, so I took the bus from St Andrews to Balmerino Road End and walked down into the village to Derek’s cottage to collect the print. Derek was kind enough to make me a cup of tea and then take me to the bus stop afterwards.

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

Congratulations to Ali Nesin

I was delighted to see, among the list of prizewinners at the ICM, that Ali Nesin has been awarded the Leelavati Prize (for outstanding contributions to public outreach in mathematics by an individual). The citation says the prize is awarded

for his outstanding contributions towards increasing public awareness of mathematics in Turkey, in particular for his tireless work in creating the “Mathematical Village” as an exceptional, peaceful place for education, research and the exploration of mathematics for anyone.

Posted in Uncategorized | Tagged , , | 4 Comments