Asymptotic group theory, 4

Market hall

Thursday was a national holiday in Hungary, St Stephen’s Day if you are religious or traditional, Constitution Day if you are a communist. “The shrewd communists let the parliament pass the new constitution on August 20, 1949,” in the words of P-cubed, who kindly invited the foreign guests to his apartment, where we had a grandstand view of the fireworks from the Citadel hill. It was a splendid display, with the fireworks from two sites synchronized so as to mirror each other; some of them exploded in the Hungarian colours of red, white and green, and others in many other colours. A smaller display from the Castle was not so easily visible. We were also provided with delicious food and very nice palinka.

Earlier in the day, the fireworks at the conference were provided by Laci Babai, who talked about symmetry and regularity. I have heard versions of this talk before, but it is always good to hear it again, there is always something new. The main thrust is that highly regular objects cannot have too much symmetry, in a suitable asymptotic sense; rather, the regularity works against symmetry in some way.

In 1980, Laci proved his beautiful result that a primitive but not 2-transitive subgroup of the symmetric group Sn has order bounded by the exponential of the square root of n times a logarithmic factor. This is best possible apart from the logarithm, as the examples of Sv acting on 2-sets and Sv wr S2 (the automorphism groups of the line graphs of complete and complete bipartite graphs) show. His proof was much better than any previously known result, and essentially no group theory was required; it used coherent configurations and the techniques of probabilistic combinatorics.

At about the same time, it was realised that the Classification of Finite Simple Groups (announced then, but not proved for another quarter of a century) gave a substantial strengthening; not in terms of the bound as such, but one could bring the bound down to about nlog n, or even nlog log n, by allowing longer and less well-defined lists of exceptions. Laci’s ambition is to prove as much as possible of this strengthening by methods not dependent on CFSG, and recently he and others have had some remarkable successes.

I will just mention one here; he gave us the proof of this in detail. Given a strongly regular graph on n vertices which is not trivial (the disjoint union of complete graphs, or the complement) or the line graph of a complete or complete bipartite graph or the complement of this, then the automorphism group of the graph contains no large alternating groups as sections (and hence, if primitive, then its order is subexponential, by the result of the BCP paper). The beautiful proof goes by the following steps (I skip several details):

  • Using “elementary number theory”, it is shown that if a permutation in Sn has order nα, then some power of it moves at most n/α points.
  • A theorem of Seidel asserts that a strongly regular graph with least eigenvalue −2 or greater is one of the excluded examples, or one of finitely many exceptions (which he found explicitly, but which do not affect the asymptotic argument).
  • Any other strongly regular graph has least eigenvalue −3 or smaller; this allows spectral techniques to show that the graph is in a weak sense pseudo-random, and the support of an automorphism cannot be too small.
  • Combining this with the first step shows that orders of automorphisms are not too large, and hence the degrees of alternating groups appearing as sections are bounded by about (log n)2/(log log n).

Another theme of the day was the work of Sasha Borovik and Şükrü Yalçinkaya on a black box recognition algorithm for the group PSL(2,q), where q is a large prime power. It is important to be able to find a unipotent element, but the probability of finding one by random search is about 1/q, which is too small; so great cleverness in the use of involutions is required. From this point, one embeds PSL(2,q) into PGL(2,q), which is isomorphic to SO(3,q), and so acts on the projective plane over the field of q elements. The plane can be constructed directly from the group (points correspond to involutions and unipotent subgroups, as do lines), and then the field can be constructed by coordinatisation of the projective plane. I was familiar with the last step, which is classical projective geometry; I worked this out for myself when I wrote my lecture notes on Projective and Polar Spaces. Indeed, in my report on computer-assisted finite geometry, which I wrote for John Cannon in 1988, I speculated that computers could carry out this coordinatisation, but I have never seen it done in practice before now!

Advertisements

About Peter Cameron

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

One Response to Asymptotic group theory, 4

  1. Jon Awbrey says:

    I remember that paper … I was into everything computer-aided in those days … well, still am in a general way … inquiry driven systems … automated research tools …

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