GRA workshop 2

This workshop was on “Computational and algorithmic aspects” (of groups, representations and applications, presumably). In my opinion, this was the week when the programme really took off.

There were many good talks, so as ever I shall just select a few. First, two contrasting styles to actually use the computer to solve problems.

Richard Parker gave a talk on “10 years of meataxe development”, the Meataxe being Richard’s program for decomposing modules. He described it as “a rant”; he works very close to the metal in an attempt to squeeze more speed out of the hardware. He said (and this echoed comments at our Big Data symposium a few years ago) that data movement is more expensive than actually doing the work. (So, of the three Rs, arithmetic is cheap and quick, while reading and writing are much slower and more expensive.) He claimed that programmers mostly ignore modern hardware design. Typically there are three levels of cache with very differing speeds well above RAM access, and if you don’t use them you are taking a factor of hundreds longer than you need. But things are not made easier by the lack of user-friendly assemblers for today’s very complex chips. His wish list was a scheduler, a more friendly assembler, and a solution to the synchronization problem.

At the other end was Nicolas Thiéry. He has a new PhD student, who is going to work on representation theory of semigroups. The software he needs is scattered over many different systems (GAP, Magma, Singular, many others); with some effort he can call everything he needs from Sage, but it is considerably harder than it should be because of differing formats. This is a software engineering problem.

But there was much more to Nicolas’ talk. He was much more concerned to give us insight and motivation than to write down detailed definitions. What is the difference between groups and semigroups? He explained, rather briefly, the J-classes of a semigroup, and how these might be structured round a group. Why do you want to do representation theory of semigroups? Group theory has been applied to the analysis of Markov chains by Diaconis and others; but in this imperfect world, things mightn’t be reversible, and semigroups are like groups where the operations can’t always be reversed. (His picture of a group is a perfect circle.) His example was the Tsetlin library, rephrased in more homely terms: you pull the shirt you want out of the pile, and when it is washed it is put back on top.

I took away the impression that moving from groups to semigroups is not unlike moving from ordinary to modular representation theory of finite groups: things are no longer completely reducible, and you have to deal with the radical.

There was a surprising amount of algebraic geometry; some of it I found very interesting. I’ll mention two. Mohammed Barakat talked about “Chevalley’s Theorem on constructible images made constructive”. In a topological space, a set is locally closed if it is the intersection of an open set and a closed set, and is constructible if it is a finite union of locally closed sets. Chevalley’s theorem says that the image of a rational map of affine varieties is constructible (in the Zariski topology). If this sounds hard, his simple example made it clear. We take the map between two-dimensional affine spaces taking the point (x,y) to x,xy). The image of this map is the whole plane with the Y-axis removed and the origin put back, obviously a constructible set. He has a new proof of this which produces a kind of canonical decomposition into locally closed sets, and which can be implemented on a computer, not just over a field but over rings like the integers too. There were several nice applications.

Tobias Rossman took us on an absolute roller-coaster ride connecting group theory, combinatorics, graph theory, and algebraic geometry. To cut to the chase, given a finite graph Γ, he defines a group scheme G_Γ where you have a generator for each vertex, two generators commute if the vertices are non-adjacent (I am not certain I have this right), and commutators are central (so the group is nilpotent of class at most 2). The object of interest is the number of conjugacy classes of this group, over some given field or ring. This has a zeta-function with an Euler product, and the factors are bivariate rational functions of p and p^-s. For some special graphs (a subclass of the cographs or N-free graphs), these are simple combinations of translates of the Riemann zeta function. The proof covers a huge amount of ground (as proofs in this area tend to do, in my experience).

Joanna Fawcett and Melissa Lee gave us an update on the base size 2 project: which primitive groups have a base of size 2, or perhaps easier, which ones don’t? (The base size is the minimal number of points whose pointwise stabiliser is the identity.) There is a nice graph, the Saxl graph, associated with groups of base size 2: very simply, the edges are the bases. This is conjectured to have nice properties resembling those of the generating graph of a finite simple group.

Madeleine Whybrow talked about dihedral axial algebras. It would take a while to explain this, but let’s say that the Griess algebra for the Monster is the motiviating example of an axial algebra, though others arise in Jordan algebras. There are now quite simple axioms for axial algebras, though it has taken a while to reach this point, and (the point of the talk) good computational tools to explore them. “Dihedral” just means “two generators”. One can put in values for various numbers that occur in the multiplication table of the idempotents. What has emerged is that the values that occur in the Griess algebra (1, 1/4 and 1/32), which seemed rather artificial at first, really are the sweet spot.

Finally, a lovely talk by Eilidh McKemmie on invariable generation. A group is invariably generated by a set of elements if you can replace any of them by arbitrary conjugates and still have a generating set. It is a result due to Pemantle, Peres and Rivin in one direction and Eberhard, Ford and Green in the other, that four random elements invariably generate the symmetric group S_n with probability bounded away from zero, but three random elements do not. Eilidh has proved that exactly the same holds in classical groups. (There is a slight complication here: classical groups have two parameters, and we may take them to infinity in either order or together, but I will skip over this.)

All rather exciting and exhausting!