Asymptotic group theory, 1

Budapest bird

The conference opened with a talk by Yoav Segev on his construction, with Eliahu Rips and Katrin Tent, of infinite non-split sharply 2-transitive groups.

A permutation group is sharply 2-transitive if any pair of distinct elements of the domain can be mapped to any other such pair by a unique element of the group. All such finite groups are known, and indeed it is easy to prove that such a finite group is “split”, that is, has a transitive abelian normal subgroup (and hence is the one-dimensional affine group over a finite nearfield – all finite nearfields were determined by Zassenhaus in the 1930s). It is a long-standing open problem whether there exist non-split infinite sharply 2-transitive groups.

Sharply 2-transitive groups give rise to a special low-rank class of independence algebras, a topic that Csaba Szabó and I worked on during my first visit to Budapest more than 22 years ago (at a time when the third Macdonalds had only just opened in Budapest). So it was very interesting to me to hear about this new construction.

The construction is remarkably easy. Yoav took us through the entire thing, apart from some calculations with normal forms in HNN extensions and free products. But the examples seem to be very diverse. In fact they show that any group whatever can be embedded as a subgroup in a sharply 2-transitive group.

In a sharply 2-transitive group, any two points are interchanged by a unique element, which is an involution; all involutions are conjugate, and so all fix the same number of points, which is either 0 or 1. Their construction deals with the former case (which they call “characteristic 2”). It can be formulated in group-theoretic terms. The final result G is a group with a subgroup A having the properties that any two conjugates of A intersect in the identity, that there are only two AA double cosets in G, and that A contains no involutions. (A is the point stabiliser.) So start with any pair G0, A0 having the first and third properties; if there are more than two double cosets, add a new generator to unify two of them. This may create new double cosets, but “in the limit” (repeating the construction enough times) the tortoise catches up with the hare and all the double cosets outside A are pulled into one. Now to get the announced result, we can take G0 to be any group and A0 to be the trivial group.

Balázs Szegedy gave us a very interesting talk on how nilpotent groups force themselves into additive combinatorics (e.g. Szemerédi’s theorem on arithmetic progressions in dense sets of integers) whether we like it or not. Roth proved the theorem for 3-term arithmetic progressions using Fourier analysis; a similar proof of Szemerédi’s theorem involves “higher order Fourier analysis”. Balázs has axiomatised the appropriate objects (which he calls nilspaces) in terms of “cubes”. The axioms are simple enough but the objects captured include nilmanifolds. I cannot really do justice to the talk in a single paragraph; but the claim is that shadows of these objects already appear in Szemerédi’s proof (although it appears to be just complicated combinatorics).

The day ended with Evgeny Vdovin talking about the conjecture that, if a transitive finite permutation group with no soluble normal subgroup has the property that the point stabiliser is soluble, then the group has a base of bounded size (that is, there is a set of points of bounded size whose pointwise stabiliser is the identity). The bound has been variously conjectured to be 7 or 5. This is almost certain to be true. Evgeny’s method shows the importance of choosing the right induction hypothesis. He works down a specially chosen composition series for the group, but the induction hypothesis “there is a base of size k cannot be made to work (there are counterexmples). Instead, he has to take the hypothesis “there are at least 5 regular orbits on k-tuples”. Why 5? I don’t know, but it seems to work!

Posted in events, exposition | Tagged , , , , | Leave a comment

In Budapest

Budapest Castle

I am back in Budapest, my fifth visit to this lovely city, but the first for thirteen years.

We are celebrating the 60th birthday of Péter Pál Pálfy, or P3, with a conference on Asymptotic Group Theory, of which more later.

Last night there was such a huge storm that the hotel lost its internet connection, so there will be some delay while I sort out the backlog. (Also, the traffic lights across the busy Múzeum korut stopped working, which made getting home last night more difficult than it should have been.)

Posted in events | Tagged , | Leave a comment

Donald Preece Memorial Day

Registration for the Donald Preece Memorial Day closes on Monday August 17. Please to to this link to register.

Posted in events | Tagged | 2 Comments


Last night, we walked out of our front door; five minutes up the path to Pipeland Hill brought us to a dark spot above the city lights. I lay down in the field and looked at the stars appearing as the daylight faded.

It was the time of the maximum in the Perseids meteor shower. Not a dramatic display, but I saw three brilliant meteors in half an hour; a satellite, possibly the International Space Station, passed across, as did a plane leaving a very clear vapour trail. Altogether an uplifting experience.

And one not possible in London. (I did once watch a lunar eclipse from Parliament Hill on Hampstead Heath, among a noisy and friendly crowd; but the lights are inescapable.)

This led me to ask myself a stupid question. Why do the Perseids happen at the same time every year? It can’t be that a cloud of debris floats there in space waiting for the earth to pass through it once a year: the fact that the radiant is in a fixed direction indicates that the debris is moving faster than the earth. I was going to pose the question here in the knowledge that someone would be able to give me the answer; but on the BBC website I found a diagram that suggested a solution. The debris is actually distributed over the whole orbit of the comet (Swift–Tuttle) which produced it, circulating round the orbit like a ring around the Sun; the orbit is more or less fixed even though the debris moves fast.

But this raises further questions. The comet (which has an orbital period of just 133 years) must have been shedding debris for a considerable time for it to have become distributed over the entire orbit like this. What is the mechanism for this? I would naively expect the debris to move with the comet, or, if expelled from the comet at high speed, to move in a whole range of orbits.

Posted in Uncategorized | Tagged , , | Leave a comment

Alex through the looking glass

A few years ago now, I wrote about the launch of Alex’s Adventures in Numberland, a maths book for the general public by Alex Bellos.

This year, I have read the follow-up, Alex through the Looking Glass, which I got in a much more low-key fashion: in the station bookshop in Guildford.

It is a very sure-footed performance, and better focussed than its predecessor (in the same way that Lewis Carroll’s second Alice book is, with its framing device of a chess game). Most of the book is about numbers and geometry: favourite numbers, Benford’s and Zipf’s laws, triangles, conics, and circles, exponential growth and decay, negative and imaginary numbers, calculus, foundations, and a very nice final chapter on cellular automata including the description of the first self-reproducing Game of Life configuration to be discovered, Andrew Wade’s Gemini.

Something I learned that I didn’t know before. Two numbers are written on separate pieces of paper which are placed face down on a table. You are allowed to look at one, and then you must say whether it is larger or smaller than the other. There is a strategy which gives you a better than even chance of winning! Seems impossible? Answer at the end. (The small print: the two numbers are real numbers and are unequal.)

And here is something Alex missed. On page 138 he explains clearly the “rule of 72”, which says, in essence, that a sum of money at x percent compound interest will double in approximatelly 72/x years. (I learned this rule with 70 in place of 72.) Then on page 148 he remarks that because the logarithm of 2 is 0.693, we have 2x = e0.693x. But he doesn’t connect these two facts, which show that the correct rule is a “rule of 69.3”, so that the one I learned was slightly more accurate than Alex’s.

Here is another unremarked connection. The pattern produced by the cellular automaton using “rule 90” is described as the Sierpinski triangle, which in a sense is correct (it is discrete, but by re-scaling as it grows we can produce a sequence of figures which converge to Sierpinski’s triangle). But this pattern is something else too: it is Pascal’s triangle mod 2 (live and dead cells corresponding to odd and even entries).

And here is the solution to the puzzle earlier. Choose a random number. (I don’t care how you do it as long as every non-empty interval has positive probability of occurring.) If x is greater than the number on the paper you looked at, you guess that the other number is also greater; if it is less, you guess that the other number is as well. Now, if in reality x is smaller than either of the numbers, or greater than either, then you have a 50% chance of being right; but if x lies between the two, you will definitely be correct, so you have improved your odds.

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

Some famous graphics

I couldn’t resist passing this on. Take a look at this data visualization infographic, or in plain language, reproduction of eleven famous graphics. These include Anaximander’s world map of 550BC; the Catalan Atlas of 1375; John Snow’s map of cholera deaths in London in 1854; Florence Nightingale’s polar charts of about the same time; and Charles Joseph Minard’s version of Napoleon’s march on Russia.

Posted in geography | Tagged , , | Leave a comment

Ernie Shult

Ernie Shult died last month. I just heard the news, from Corneliu Hoffman’s mailing list.

I first met Ernie at a “microconference” on permutation groups organised in Oxford by Peter Neumann in the early 1970s when I was just starting out. Many of the gods of finite group theory were there: Shult, Leonard Scott, Charles Sims, I don’t remember the whole list. Ernie was one of the nicest people I knew, and I will end with a story from that meeting.

There was one of Shult’s theorems that I knew well at the time, the Graph Extension Theorem. This gave a sufficient condition for the automorphism group of a vertex-transitive graph to be the stabiliser of a point in a doubly transitive group. I would like to remember Ernie by tracing some of the secret history of this theorem.

Shult himself applied it to give a characterisation of the symplectic and orthogonal groups over GF(2). This led, via a generalisation by Jaap Seidel, to the very influential Buekenhout–Shult Theorem, which gave a simple test to recognise the geometries of all the classical groups, and was used for this in the Classification of Finite Simple Groups. But I want to trace a different thread.

The Graph Extension Theorem was closely related to Graham Higman’s concept of a regular two-graph, a collection of triples satisfying a cocycle condition. To explain the connection in highbrow language: because of vanishing cohomology, a cocyle is necessarily a coboundary, in this case of a graph, which is the graph in Shult’s theorem.

A little later, John McDermott came to Oxford to give a seminar. He, like me, began as a finite group theorist; he was talking about infinite permutation groups, and specifically highly homogeneous groups, groups which act transitively on the set of k-element subsets of their domain for all k, which fail to be k-transitive (transitive on ordered k-tuples) for some k. The standard examples are linear orders such as the rational or real numbers.

John saw that you could obtain a larger group by preserving or reversing the linear order: this group is 2-transitive (but not 3-transitive). The main part of his talk was the construction of further examples of 2-transitive groups. He showed that linear orders like the rational or real numbers satisfy the hypotheses of an “oriented” version of Shult’s Graph Extension Theorem (which he proved), and thus are point stabilisers in 2-transitive groups.

Shult’s original construction is related to Higman’s regular two-graphs, which are sets of triples (or, said otherwise, relations which say “yes” or “no” to every unordered triple). Analogously, McDermott’s construction should be related to “oriented triples”, which give a cyclic orientation to every unordered triple. The obvious gadget which does this is a circular order. So it turned out that McDermott had constructed the circular order obtained from a linear order.

Once I noticed this, it was simple to observe that you could preserve or reverse the circular order (obtaining a 3-transitive group), and I was able to prove that these were all the possibilities.

Later, when I learned about the random graph, I realised that it too satisfied Shult’s hypotheses (in their original form), and so its automorphism group has a transitive extension. This led to Simon Thomas’ classification of the reducts of the random graph.

A fine body of theory to have grown out of quite a short paper (which, by the way, was published in a conference proceedings – research assessors please note!)

Back to the miniconference. At a certain point there was a party in my house. The only thing I remember from this party is that at a certain point, Ernie Shult and Leonard Scott were discussing me. Ernie said that I was a very gentle person, but Leonard disagreed, saying that I had a core of toughness (I don’t remember the precise word he used). It is not for me to judge who was right, but how characteristic of Ernie to see the good in someone.

Posted in Uncategorized | Tagged , , , , , , , , , , | 2 Comments