I have just spent a very wet week in Novi Sad at the fourth Novi Sad Algebraic Conference. Wet both in the sense of the large amount of rain that fell (most afternoons brought lightning, thunder and a heavy downpour) but also the volume of water heading down the Danube. (On the last half-day of the conference, the weather turned lovely, to show us what we had missed.)
Many thanks to Igor Dolinka and his team for putting on such a splendid show.
“Algebra” means many different things, and each algebra conference has its own way of specialising. Here, there was a lot of semigroup theory, and a lot of universal algebra. I was here mostly to learn, particularly about semigroup theory.
Novi Sad (Neoplanta, “New plantation”), the capital of Vojvodina province in Serbia, is a town of about 350000 people on the river Danube. It is a town with very many restaurants, some of the best of them specialising in fish from the river (carp, catfish, etc.) It was founded in 1694 opposite the fortress of Petrovaradin, which stands in a commanding position overlooking the river.
It is perhaps most famous for the Exit music festival; the town was full of posters for Fatboy Slim, Bloc Party, Snoop Dogg, and other acts appearing at the festival next month.
One of the big developments in universal algebra recently has been the recognition of the role that polymorphisms can play in the constraint satisfaction problem. Inevitably there was a lot of discussion of this, but clones of polymorphisms, and clones for their own sake, have become central objects in universal algebra. (I heard a lot about clones in the early 1980s, but they seemed to go out of fashion for a while.)
A clone is a collection of functions on a set A of all possible arities (that is, functions from An to A for all positive integers n) with the two properties
- it is closed under composition: that is, if the n-ary function
g and n m-ary functions f1,…fn belong to the clone, then so does the m-ary function g(f1,…fn).
- It contains all projections pn,i for i ≤ n, where pn,i is the n-ary function given by pn,i(x1,…xn) = xi.
Given a relational structure (with any number of relations) on a set X, a polymorphism of the structure is an n-ary function f which is a homomorphism from Xn to X. This means that, given any r-ary relation R, and any r×n array of elements of X each of whose columns satisfies the relation R, the r elements obtained by applying f to the rows of the array also satisfy R.
Now the polymorphisms of a relational structure form a clone, the polymorphism clone of the structure. Conversely, given a clone, we can consider the set of all relations invariant under the functions of the clone. This is the duality.
This is how I see clones in relation to things I am interested in.
- The symmetric group on a set X is contained in the transformation monoid on X; it consists precisely of the invertible elements.
- The transformation monoid on X is contained in the clone of functions on X; it consists of the functions of arity 1. (The identity element is the projection p11.)
More generally, if we have a relational structure on X, then its automorphism group is contained in its endomorphism monoid, which is itself contained in its clone of polymorphisms.
A lot of activity reported at the meeting involved extending results about permutation groups (such as Sierpiński rank – about which more later – and the Bergman property) to transformation semigroups, and work has begun extending them further to clones.
There was a feast of good talks at the meeting. With difficulty I will restrict myself to discussing just four.
Ben Steinberg’s talk was a real highlight, making an unexpected connection. A little background:
- A variety of algebras is a set defined by identities. An example of an identity is the commutative law xy = yx.
- A quasi-variety of algebras is a set defined by quasi-identities, statements asserting that if a finite connection of equations hold then some other equation must hold. An example is the cancellation law: xy=xz ⇒ y=z.
- A band is a semigroup (structure with associative law) in which all the elements are idempotents (satisfying x2 = x). It is normal if it satisfies the identity xyzx = xzyx.
According to Ben, normal bands are the simplest semigroups. In particular, every quasi-variety of normal bands is finitely based (determined by finitely many quasi-identities) and has a polynomial-time membership test. Note that the first property implies the second.
Ben told us that the most important semigroup is the three-element semigroup whose elements are called 0, +, −, and whose operation is given by 0·x = x, +·x = +, −·x = − for any choice of x. It is a band, but not a normal band. He called this the “flop-flip” semigroup since its dual arose in the theory of flip-flops. The flop-flip generates the variety of left-regular bands (satisfying xyx = xy).
Ben’s theorem asserted that the quasi-variety generated by the flop-flip is not finitely based, but membership can still be tested in polynomial time. The reason is that the number of quasi-identities you need to check to see whether a given semigroup S lies in the quasi-variety grows (linearly) with the size of S.
The bridgehead to the other area is formed by the following interpretation of the flop-flip. Its three elements 0, +, − correspond to the origin on the real line and the two half-lines. The operation is obtained as follows: to work out xy, stand in region x and move a short distance towards y.
A hyperplane arrangement consists of a finite number (say r) of hyperplanes through the origin in Euclidean space. Without loss of generality, their intersection is just the origin. (Think of a bunch of lines through the origin in the plane, or the coordinate planes in three dimensions.) The chambers are the connected components of what remains when the hyperplanes are removed; the faces consist of these together with smaller-dimensional regions (so, with lines in the plane, faces are chambers, half-lines, and the origin).
Jacques Tits defined a semigroup structure on the faces of a hyperplane arrangement, which is very important for the geometry and representation theory of the arrangement. The elements of the semigroup are the faces; to work out xy, you stand in region x and move a short distance towards y. So the flop-flip just corresponds to the unique hyperplane arrangement in one dimension (the hyperplane is the origin).
To analyse this, choose a starting chamber. Now for each hyperplane, associate a value to every point in space, with is 0 if the point is on the hyperplane, + if it is on the same side as the starting chamber, and − if it is on the opposite side. Then each face is represented by a r-tuple of elements of the flop-flip (remember that r is the number of hyperplanes). It is easily checked that the composition works correctly; so the Tits semigroup is a subsemigroup of Lr, where L is the flop-flip. So any such semigroup lies in the quasi-variety generated by L.
Now nice geometric arguments can be used to analyse the situation and prove the theorem.
The Sierpiński rank of an infinite algebra S is the least number d such that any countable subset of S is contained in a d-generator subalgebra (if such a number exists). It is so-called because Sierpiński showed that the rank of the transformation semigroup on an infinite set is 2; in other words, given a countable sequence of functions, we can find two functions such that all of them can be expressed in terms of these two by composition.
James gave many new results on this concept, but the gem was a proof of Sierpiński’s theorem, with a new trick due to James Hyde.
We will just deal with transformations of a countable set; since it doesn’t matter which set we use, we will take the set to be the set of all eventually constant sequences of natural numbers. Call it X. I write maps on the right, and compose left-to-right.
So let f1, f2, … be functions on X. (Note that there is no function f0.) Define maps a, b, c on X to map (x0,x1,…) to the following (eventually constant) sequences:
- a : (0,x0,x1,…) [insert 0 at the front of the sequence]
- b : (x0+1,x1,…) [add 1 to the first term]
- c : (x1,x2,…)fx0 [delete the first term and apply the function indexed by this term]
Now a simple calculation shows that fn = abnc. This shows that the three functions a, b, c suffice to generate the fs, so the Sierpiński rank is at most 3.
Now comes the trick. Set f0 = b. Then b = f0 = ac, so actually the functions a and c suffice!
Maja and Christian Pech
Maja and Christian Pech gave two consecutive short talks, the second following on from the first, so it was like a single longer talk. It was rather similar to James’ talk, and unsurprisingly the name of Sierpiński also came up.
The relative rank of an algebraic structure S in a larger structure T is the number of generators that have to be added to S to generate T. Higgins, Howie and Ruškuc showed that the relative rank of the symmetric group in the full transformation monoid on an infinite set is 2.
Maja’s first result was a condition for the relative rank of the endomorphism monoid of a homogeneous structure in its polymorphism clone to be 1. This condition is satisfied by the random graph, by a result of Bonato and Delić.
Then there was a condition for the relative rank of the polymorphism clone over the semigroup of embeddings to be at most 2, expressed in terms of the age of the homogeneous structure; as well as the amalgamation property (Fraïssé’s condition), we require the homo-amalgamation property and the amalgamation extension property. Moreover, the two added functions can be taken to be one unary and one binary.
It was a particular pleasure to see the HAP arising here, since it is the condition for homomorphism-homogeneity, a concept that Jarik Nešetřil and I devised a few years ago. A referee of our paper remarked that it was not the most significant paper that either of us had written; but I think that one of its seeds is finding its place in the sun of Novi Sad and growing into a beautiful plant!
Things people said
Often a speaker will make an off-the-cuff comment which can provide good insights to the listeners. Here are some I noted down. Usually these are paraphrases rather than exact words, which I was not quick enough to record.
From Anand Pillay:
- Model theory could have become part of set theory, and it could have become part of recursion theory, but it didn’t.
- Stable theories are the most perfect theories.
- Omega-categoricity is a branch of permutation group theory.
From Bob Gray:
- Groups are not like life; whatever you do, you can undo. But semigroups are more like life; you can’t always get back to where you were.
From Victoria Gould:
- When you’re in a variety, things are so much nicer: you take a homomorphic image and you don’t fall out.
Arkady Tsurkov used “the principle of the empty set” at one point.
A couple of talks led me to reflect that, in normal English, “similarity” is a relation, but many mathematicians use it to mean a function.
The spirit of Douglas Adams was hovering around. Mark Kambites mentioned “somebody else’s problem”; James Mitchell pointed out that that the Sierpiński rank of the endomorphism semigroup of surjective functions on a set of cardinality ℵ5 is 42; and, most impressively, Michael Pinsker announced a talk on the fact that there are 42 retracts of the ordered random graph, but between this and the actual conference, he and his co-authors realised that they had miscounted, and there are really only 41 retracts … so we have to wait another ten million years to find out what the ultimate question is!
At the conference dinner, James Hyde reminded me of the problem of the prisoners and the boxes. I hope to discuss this in a forthcoming post on the symmetric group (that’s a hint!), but you might like to think about it before then. I think the problem is due to Peter Winkler; if you are really impatient, see here.
The names of 100 prisoners are placed in 100 wooden boxes, one name to a box, and the boxes are lined up on a table in a room. One by one, the prisoners are led into the room; each may look in at most 50 boxes, but must leave the room exactly as he found it and is permitted no further communication with the others.
The prisoners have a chance to plot their strategy in advance, and they are going to need it, because unless every single prisoner finds his own name all will subsequently be executed.
Find a strategy for them which which has probability of success exceeding 30%.