Computational algebra in Lisbon

This week I was at a very nice workshop on Computational Algebra in Lisbon. Rarely do I learn so many new things at a conference, although it was only three days in duration.

Here are some of the highlights, roughly in order of appearance.

Catarina Carvalho told us about constraint satisfaction. I have heard several times about the Feder–Vardi dichotomy conjecture, according to which a constraint satisfaction problem is either in P or NP-complete; and I have heard several times about the clone of polymorphisms of a relational structure, and how it gives information about the CSP. But I hadn’t realised how clearly that there are five relevant complexity classes, in descending order NP, P, NL (nondeterministic logspace), L, and AC0 (I don’t know what this last one is), and five 2-point restrictions of the polymorphism clone, with proved or conjectured relations between the complexity classes and the non-occurence of various combinations of these types.

Pedro Silva talked about some work he has been doing with John Rhodes and others, connecting matroids, fundamental groups of simplicial complexes, and superBoolean algebras. This deserves more than a quick sketch, and I want to return to it in more detail later.

Michael Kinyon talked about the use of automated deduction systems (in particular Prover 9) in finding and proving big theorems about three classes of loops: Moufang loops, Bruck loops, and automorphic loops. He really kindled my interest in simple automorphic loops, and I hope to return to this later as well.

Mikhail Volkov gave two stunning talks.

The first was about expanders. It was advertised as primarily about algebraic constructions of expanders, but instead he spent some time showing us in detail how bipartite graphs with good expansion properties give rise to an infinite class of linear error-correcting codes in which both the rate and the relative error-correction (number of errors corrected divided by length) are bounded away from zero.

The second was about the Černý conjecture, which I have talked about here earlier. The conjecture asserts that, if a finite deterministic automaton with n states is synchronizing, then it has a reset word of length at most (n−1)2. If true, this would be best possible; but there are very few known examples attaining the bound: one infinite family, and eight sporadic examples all with n ≤ 6. Instead of trying to prove this, he and his student Vladimir Gusev computed the shortest reset word for all automata with 8 or 9 states. As expected, they found only one meeting the bound; below this there was a gap, then a small “island” of values, then another gap, then the “mainland” below that. For example, for n = 9, there is one automaton with reset word of length 64, then 6 with reset word in the set {56,57,58}, then a gap to 52.

He explained that this reminded him of very similar behaviour in a different problem where more is known. A non-negative matrix is primitive if some power of it is strictly positive; the smallest exponent of such a power is the exponent of the matrix. Wielandt showed in 1950 that the exponent of a matrix of order n is at most (n−1)2+1; there is one matrix of this exponent, and one of exponent (n−1)2, then a gap, an island, and another gap. The coincidence is not exact, but is still very striking.

So they went on and estabished very close connections between the two problems, so that slowly synchronizing automata can be constructed from matrices with large exponent. It hasn’t led to a proof of the conjecture, but it certainly has thrown some very interesting light on it!

James Mitchell talked about his software for establishing properties (e.g. order, R-classes) of various kinds of semigroups, beginning with transformation semigroups. Before this, state-of-the-art meant computing, storing and counting all the elements of the semigroup; an obvious disadvantage, but the advantage is that it only requires that you can multiply and test equality for the semigroup elements. By contrast, group theorists have the Schreier–Sims method which can give the order, membership test, etc., of a permutation group with given generators much more efficiently, and in particular without computing all the elements. James explained how his Semigroups package for GAP borrows not only ideas but code from the Schreier–Sims algorithm for doing the same thing for semigroups, and gave us a demonstration. The method works more generally, requiring only that your generators lie in some overarching regular semigroup. So as well as transformation semigroups, they work for semigroups or matrices, partition monoids, and so on. I have wished for something like this for a long time, and now it exists!

There was other nice stuff too, but for me these were the best.

The slides of my two talks are in the usual place.

At the end of the talk, João Araújo was interviewed by a journalist about his on-line PhD courses, which I mentioned earlier. After João’s interview, the journalist talked to three of the students who had come along (one of them, Manuel Martins, had spoken at the conference about his web-based version of GAP), and then to three of the teachers (Michael, James and me), and finally another session with João.

One of my regrets is missing the conference dinner in order to fly home. I was standing in a queue for forty minutes while the other delegates were presumably tucking in, and because of various delays along the way I didn’t walk in through my front door until ten past two in the morning.


About Peter Cameron

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

Leave a Reply

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

You are commenting using your 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