The 42 professors

The street atlas of Lisbon in the apartment lists 50 streets named after professors, from Rua Professor Abel Salazar to Rua Professor Vitor Fontes.

Because some of the names are duplicated, there are only 42 or 43 professors who are actually commemorated in this way. (I put 42 in the title because I guess that Professor Fernando Fonseca is probably the same person as Professor Fernando de Fonseca.)

Nonetheless, it seems like a very large number. Can you think of any other city which commemorates so many professors in this way?

You might expect them to cluster round the University, but in fact the Universidade de Lisboa has just two streets in this category, Av. Professor Gama Pinto and Av. Professor Anibal de Bettencourt.

This suggests a society in which a professor is respected, and more generally in which learning is valued. I hear hollow laughter from my Portuguese colleagues, but I think this must at least have been so once in order for this riot of naming streets after professors to have occurred.

Posted in Uncategorized | Tagged | 2 Comments

The planets

This morning, after being woken at 4am by the garbage trucks emptying bins in the street outside, I walked to the back of the apartment and saw a wonderful sight. The clouds had mostly cleared, and in the eastern sky three planets in close conjunction blazed over the city: Venus, Jupiter, and Mars.

The planets

The snapshot, taken with a handheld camera, doesn’t in any way capture the scene (indeed, it doesn’t capture Mars, the faintest of the three, at all).

This led me to think. In the ages of geocentric, Ptolemeian astronomy, did no clever person ever wonder about the huge difference between Mercury and Venus (which stay close to the sun) and the other planets (which wander over the whole zodiac)? Of course this can be (and was) explained with epicycles, but conceptually it is so much simpler to have a heliocentric model, with the orbits of Mercury and Venus inside that of the earth.

Also, was there no pre-telescopic astronomer sharp-eyed enough to observe the phases of Venus (a crucial piece of evidence for the heliocentric theory for Galileo, when he saw them through his telescope)?

Posted in history, Uncategorized | Tagged , , , | 4 Comments


12160 is an interesting number; but I didn’t know that until last night.

As part of the work on semigroups, we are looking at the following problem.

Given n and k, with n ≥ 2k, suppose that G is a k-homogeneous subgroup of Sn. How many orbits does G have on partitions of {1,…,n} with nk parts?

First, some information. A permutation group is k-homogeneous if it acts transitively on the set of k-element subsets of {1,…,n}. Clearly k-homogeneous is equivalent to (n−k)-homogeneous, hence the restriction n ≥ 2k is sensible.

According to well-known results in permutation group theory (depending on the Classification of Finite Simple Groups), all the k-homogeneous groups with k ≥ 2 are known. For k ≥ 6, the only such groups are the symmetric and alternating groups; and for these, the number of orbits on (nk)-partitions is p(k), the number of partitions of k, independent of n. For the shape of such a partition is obtained by taking a partition of k, extending it with zeros so that it has nk parts, and then adding 1 to each part.

For k = 5, there are only two further groups to consider, the Mathieu groups M12 and M24. Clearly these will have only a finite number of orbits, so again it is true that the number is bounded by a function of k, independent of n. Also, for n = 4, there are only finitely many further groups, though the list is a little bit longer.

For k = 3, there are two infinite families of groups, together with a finite number of further examples. For one of the families (the affine groups over the 2-element field) the number of orbits is bounded independent of the degree; but for the other, it grows as a cubic in n. For k = 2, the situation is similar but even more complicated.

So can we compute the numbers?

My first attempt was to write a little program to generate all the (nk)-partitions of {1,…,n}, and count orbits under the group action. This worked fine up to about n = 12, and in particular showed that for k = 5, the Mathieu group M12 has 30 orbits on 7-partitions. But the program ran out of memory when I tried it on the large Mathieu group.

The second approach was to note that, if a partition of {1,…,n} has nk parts, then the union of the parts of size greater than 1 has a number of points between k+1 and 2k. So I could compute orbits of the group on sets of these sizes; for each orbit, choose a representative, calculate the group induced on it by its setwise stabiliser, and count orbits of this group on appropriate partitions. This involves many orbit counts, but they are of small groups. (For example, for M24, we have groups with degrees from 6 to 10 rather than 24.) This program ran for M24, and showed that it has 77 orbits on 19-partitions.

However, it still ran out of memory for the one remaining group, PΓL(2,32), a 4-homogeneous group of degree 33. It worked fine for sets of sizes 5, 6 and 7, but ran into problems for 8-sets.

So finally I implemented the following rather baroque idea. Start with a list of all the 4-subsets of {5,…,33}. Take the first subset in the list, take its union with {1,2,3,4}, take the orbit of this set under the group, filter out the sets containing {1,2,3,4}, and remove them from the list, until the list is empty. Keep an auxiliary list of the chosen 4-sets during the process, and adjoin {1,2,3,4} to each of them. Now these are orbit representatives for the group on 8-sets, and the rest of the computation is plain sailing.

The final number of orbits turned out to be 12160. (For the other 4-homogeneous groups, they are 5 – for symmetric and alternating groups – 26, 12, 21, 13, 38, and 15.)

Of course, it would be nice to have independent confirmation of this number …

Posted in doing mathematics, exposition | Tagged , , | 3 Comments

Lisbon sunrise

Lisbon sunrise

I am living for a month in an apartment in Benfica, belonging to a semigroup theorist; so of course I am doing semigroup theory!

The view from the back of the apartment looks east, over a grassy slope. At most times of day there are egrets browsing on the grass, sometimes over twenty of them. The exception is caused by an old man who walks his dogs there and frightens the egrets away.

The sun rises over the buildings to the east, and there have been some spectacular (and very different) sunrises in my first week here.

Posted in geography | Tagged , | Leave a comment

An Aveiro theorem

When I was a child, one of the radio serials we listened to was The Lone Ranger. Typically, when the Lone Ranger with his sidekick Tonto had cleared up another mess of wrongdoing or whatever, he would say to Tonto, “Our work here is done”, and they would ride off into the sunset. At that moment, not everything would be smoothed out; he would leave the last bit to others. This was because, obviously, he didn’t want to appear in court, when the judge might order him to remove his mask (a big no-no for superheroes!); but also, like Bob Dylan’s John Wesley Harding a decade or so later, his methods were not necessarily entirely above board.

Last Friday, I awoke thinking “Our work here is done”. It took me a while to remember where that line came from; but it turns out to be quite appropriate.

In three earlier posts about regular polytopes (the first one here), I explained how finding an abstract regular polytope with given automorphism group G can be translated into a purely group-theoretic property of G, that it should be a so-called string C-group: this means that G can be generated by a set S of involutions with the two properties

  • the involutions can be arranged in a sequence so that two involutions which are not adjacent in the sequence commute (the string property); and
  • if U and V are subsets of S, then the intersection of the subgroups generated by U and V is the subgroup generated by the intersection UV (the intersection property).

So an interesting question is: Given a finite group G, describe all the regular polytopes with automorphism group G; or, at least, describe the largest possible rank of such a polytope. (The rank of a polytope corresponds, in nice geometric cases, to the dimension of the space in which it is embedded; in the string C-group formulation, it is the size of the generating set S.)

This question was examined, among other people, by Maria Elisa Fernandes, Dimitri Leemans, and Mark Mixer. It is not hard to show that the largest possible rank for the symmetric group Sn is n−1; apart from a few small cases, equality is realised only by the regular simplex of dimension n−1, and the corresponding generating set consists of the Coxeter generators

(1,2), (2,3), …, (n−1,n).

These three authors also did more. They made a remarkable conjecture about polytopes for the symmetric group:

There exists a function f with the property that, for sufficiently large n, the number of different regular polytopes of rank nk for the symmetric group Sn is f(k).

They proved this conjecture for k = 1,2,3,4, with the values of f(1),…,f(4) being 1, 1, 7, 9. On the basis of computational results, they conjectured that the next value f(5) is equal to 35, and that “sufficiently large” means n ≥ 2k+3.

They also went on to consider regular polytopes whose group is the alternating group An. The largest rank they could find was much smaller, namely ⌊(n−1)/2⌋ for n > 11. (The group A11, exceptionally, is the automorphism group of a regular polytope of rank 6.)

Cameron, Fernandes, Leemans

After a very hard month of work in Aveiro, we believe we have a proof of the theorem that this is indeed the largest possible rank for a regular polytope for the alternating group.

I won’t describe the proof here. Suffice to say that we went down to the wire. On Friday, just before lunch we discovered a problem with the penultimate lemma in the paper; not a serious problem, just a lapse of attention which can easily be fixed, but we didn’t have time to fix it that day. The very last lemma, like a number of other results in the paper, also has a small problem in that its proof requires n to be “sufficiently large” (this typically means n > 16 or so; smaller values can be handled either by computer or by being just a little more careful in the proofs.

Assuming it stands up, it is a big theorem. Apart from the symmetric group, most results of this sort have concerned groups of Lie type of very low rank, where the subgroup lattice is much less complicated than that of the alternating group. (Note that, if G is the automorphism group of a regular polytope of rank r, then the subgroup lattice of G contains the Boolean lattice of subsets of an r-set as a sublattice, in a very special way.)

Unlike the Lone Ranger, riding off without a backward glance, I cannot escape the next stages: producing a manuscript, checking it carefully, and so on. But I think the main job is done. Dimitri flew off to Durban yesterday, and I make a smaller journey, by train to Lisbon, today.

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

Open science again

Just after my three pieces on open science (covering open publication, data, and software) was published on the CoDiMa blog, a message came round telling us to do something about ResearchFish. This, if you are fortunate enough not to have come across it, is another piece of bureaucracy imposed on research grant holders: it is not enough to acknowledge the source of your funding in a publication, you must also enter it in some database somewhere. (To be fair, the message was about easing the burden on us by taking the information automatically from the university’s publication repository.)

I think that research funding is more complicated and nuanced than the research councils seem to believe, so in the style of Douglas Adams I wrote a fourth part to the trilogy. It is now posted here.

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

Orthogonal arrays and codes over rings

I have just posted to the arXiv a preprint of a paper with Josephine Kusuma about the subject in the title of this post. (Josephine is on the left in the picture, with Taoyang Wu; the water behind is Windermere.)

Josephine Kusuma, Taoyang Wu

Given a set S of words of length n over an alphabet A, we can imagine that the words are stacked in an N×n array, where N is the number of words. We say that S is an orthogonal array of strength t if, given any t columns of the array, each word of length t over A occurs the same number of times in the chosen positions. The strength of S is the largest t for which this holds.

One of Delsarte’s old results is that, if A is a finite field and S a linear code over A, then the strength of S is one less than the minimum Hamming weight of the dual of S. (The dual of S is the set of words having inner product 0 with every word in S; and the Hamming weight of a word is the number of non-zero coordinates.)

Our first theorem is that the same holds if A is a finite commutative ring with identity, and S a linear code over A (meaning a submodule of the free A-module An).

Not so surprising, you might say; but the real surprise is the difficulty of the proof. It depends on a property of finite rings which I didn’t know before this work. (I will from now on say “ring” to mean “commutative ring with identity”.) This is the property:

If I is a proper ideal of A, then the annihilator of I is non-zero.

The proof of this requires a structure theorem for finite rings which I couldn’t find written down anywhere: a finite ring is a direct sum of finite local rings. This is a special case of a general result about completions of semi-local rings (rings with only finitely many maximal ideals), using the observation that any finite ring is semi-local, and a finite ring is its own completion.

The rest of the proof of the extension of Delsarte’s theorem is a fairly easy induction based on this.

The bulk of the paper considers the case of the ring A = Z4, the integers mod 4. This is important because of the work of Hammons, Kumar, Calderbank, Solé and Sloane in the 1990s, which “explained” why certain pairs of non-linear binary codes (the Preparata and Kerdock codes) are related by the MacWilliams transform, a result which holds between a linear code and its dual.

The key is the Gray map, a bijection between Z4 and (Z2)2. The Lee metric on Z4 is the number of “steps round the circle” between two elements: thus, the Lee distance from 1 to 3 is 2, while the Lee distance from 0 to 3 is 1. Now the Gray map is an isometry between Z4 with the Lee metric, and (Z2)2 with the Hamming metric, given by

0 → 00, 1 → 01, 2 → 11, 3 → 10.

As with the Gray map in general, each step around the “circle” of Z4 changes the Gray map image in a single coordinate. (It is this property which makes the Gray map useful in analog-to-digital conversion.)

Thus the image of a linear Z4-code is a possibly non-linear binary code but one whose Hamming weight (and distance) distribution is the same as for the linear Z4-code with which we began.

Now we conjecture the following analogue of Delsarte for this situation:

The strength of the Gray map image of a linear Z4-code S is one less than the Lee weight of the dual of S.

We cannot prove this conjecture, but it holds in many examples, and we can at least prove an inequality one way round. Moreover, the conjecture holds for codes whose duals are generated by a single element.

Posted in exposition | Tagged , , , , | 3 Comments