A visit to Lisbon


Back in London after three weeks in Lisboa.

It wasn’t meant to be my research visit; I tagged along with the intention of having a holiday. But it didn’t work out like that.

We lived in student accommodation at the new university in Caparica on the south bank of the Tejo. This meant commuting to work by tram and train. The train goes on a deck below the road traffic on the famous 25 April bridge. So shortly after leaving Pragal, it goes into a tunnel (with 75 lights on each side, not all working), then suddenly emerges into the open high over the river, with stunning views of the city, Belém, and the south bank. I think it would be a long time before I got tired of that view.

CAUL, the Centro de Álgebra da Universidade de Lisboa, gave me the visitor’s desk and wi-fi access; fortunately the room was just across the corridor from the office of João Araújo and Wolfram Bentz, with whom I worked (very hard, actually). We submitted one paper, as I already mentioned, and wrote two more, which I will discuss below.

In addition, our kind hosts took us to some of the most spectacular bits of the countryside round Lisboa, including Sintra, Santarém, Maffra, Palmela, the walled town of Óbidos, and the seaside town of Nazaré which boasts some of the best surf in Europe (which we didn’t try) and an extraordinary seafood restaurant on the seafront (which we did). We also listened to fado (Fado? south of the Tejo? Impossible! But not only did it exist, but it was quite unlike what they put on for tourists in the centre of Lisboa), ate and drank very well indeed, and had just enough free time for a long walk around the city and a visit to the zoo.

I have talked about synchronization before; let me recap briefly. Let G be a permutation group on a finite set X. We say that G synchronizes a non-permutation f on X if the monoid ⟨G,f⟩ generated by G and f contains a constant function. Then the group G is synchronizing if it synchronizes every non-permutation. It is known that every synchronizing group is primitive, but not every primitive group is synchronizing.

We say that the group G is almost synchronizing if it synchronizes every map whose kernel is non-uniform. (The kernel of f is the partition of X given by the inverse images of the points in the image of f; the kernel is uniform if all parts of the partition have the same size, non-uniform otherwise.) It is easy to see that an almost synchronizing group is primitive – for an imprimitive group it is easy to find non-uniform maps which are not synchronized.

João and Wolfram had produced a sufficient condition for a group to be almost synchronizing, and while I was there we were able to weaken it to the extent that we could find infinitely many examples; we also used a paper of Godsil and Royle on cores of graphs to find infinitely many more examples. João made the bold conjecture that every primitive group is almost synchronizing. This looks very interesting but seems out of reach at present.

The other piece of work grew out of results of Levi and McFadden, who proved that, if f is a non-permutation, then the semigroup generated by all conjugates of f under the symmetric group is idempotent-generated and regular. McAlister showed that the semigroup generated by these conjugates is actually the set of all non-permutations in the semigroup generated by the symmetric group and f.

Later Levi showed that all these conjugates are actually conjugate under the alternating group, and hence the same result holds with the alternating group rather than the symmetric group. This leads to three questions: for which permutation groups G is it true that

  • for all f, the semigroup generated by the G-conjugates of f is idempotent-generated;
  • for all f, the semigroup generated by the G-conjugates of f is regular;
  • for all f, the semigroup generated by the G-conjugates of f is the set of non-permutations in ⟨G,f⟩?

The second question was solved by João, James Mitchell and Csaba Schneider (J. Algebra 2011); a generalization of that question (when we fix the rank of the map) was answered in the big paper we submitted in the first week I was there. The first question was also answered in the João, James and Csaba paper, and the corresponding generalization for maps of fixed rank is on the way (I hope I and João can finish it before the summer). Regarding the third question, we managed to crack it, with the help of James Mitchell and Max Neunhöffer at St Andrews. The answer is that, apart from the symmetric group, the alternating group, and the trivial group, the only possibilities are five specific groups of degrees 5, 6, 6, 9, 9. The reason for getting help was that a big computation is needed: there are 99 functions on a set of size 9 to check! They are responsible for two GAP packages called Citrus and Orb which together are exactly the tools required for the job.

As well as the research, I gave four talks in Lisbon. They will appear on the CAUL website at some point, I hope. They have all been discussed here in the past. If you are impatient, you can find the slides here:


About Peter Cameron

I count all the things that need to be counted.
This entry was posted in doing mathematics, exposition, synchronization and tagged , , , . Bookmark the permalink.

2 Responses to A visit to Lisbon

  1. The second paper is now on the arXiv: http://arxiv.org/abs/1205.0450, and the third is at http://arxiv.org/abs/1205.0682

  2. João Araújo pointed out to me that what I said about the contents of the big paper was not quite correct. He suggested an accurate statement, which I have incorporated in the post.

    He also provided me with the link to an astonishing video of the surf in Nazaré, which I have also incorporated.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s