Silly season, 2

I received a very respectful email enclosing a paper and soliciting my comments.

I wouldn’t usually treat the sender of such an email like this, but I happened to notice that all the other addressees had names beginning pj, so I doubt that I had been carefully selected.

A glance at the attachment showed two things.

  • First, it contained two proofs that π = (14−√2)/4.
  • Second, it was not a manuscript or preprint, but a reprint from an international journal with the spuriously precise impact factor of 3.785.
Posted in publishing | Tagged , | 3 Comments

September

September

I already posted part of this picture, a signpost on the edge of the Olympic Park back in 2011. I tagged it with the last phrase of the second verse of Procol Harum’s apocalyptic song Homburg: “The signposts cease to sign”.

I decided that, instead of scrubby trees by an east London waterway, it deserved a more dramatic background, so I used a photo of the sun setting into the sea taken at St Kilda, a suburb of Melbourne, later that year.

Posted in Uncategorized | Tagged , , , | Leave a comment

Silly season gleanings

EPSRC have finally made it into Private Eye, into Pseuds Corner to be precise; the current edition quotes part of their definition of a sandpit. (The entire definition is several pages long. Thus, sample activities for the first stage, called “Interact, Create mission statement”, of the process might be “Site visits to further explore the issues. Vision setting through creative ‘cartoon strip’ workshop, followed by a night learning how to play a musical instrument … and some friendly team competition.”)

Three kings

The picture above is not friendly team competition over dinner at a sandpit, but shows the kings of Hungary, Bohemia and Poland meeting in the castle of Visegrád in 1335 to hammer out an agreement. Did the agreement include relaxing the Hungarian quota on imports of Czech beer?

Posted in Uncategorized | Tagged , , , | Leave a comment

The other St Andrews

Szentendre

Szentendre is a small town at the end of a suburban railway line from Budapest. I first visited it 22 years ago, in the winter; it was a beautiful place of artists’ studios and galleries, old Serbian churches full of icons, and wide views across an arm of the Danube to a large island.

We went back yesterday, on a summer Sunday at the end of the St Stephen’s Day long weekend, and could hardly move for tourists.

Posted in geography | Tagged , , | Leave a comment

Budapest moment

Rose and yew

The moment of the rose and the moment of the yew tree
Are of equal duration

T. S. Eliot, “Little Gidding”

This picture is of a corner of the sadly neglected gardens around the tomb of Gül Baba, the person who introduced the cultivation of roses to Budapest.

Posted in geography, history | Tagged , , , , , , | Leave a comment

Asymptotic group theory, 5

Cat and bird

Now the conference is over.

On the last morning, Marty Isaacs posed an interesting problem. Let p be a prime, and n a positive integer. Is there an infinite group in which exactly n elements are not pth powers? This was during a talk in which he told us several things about finite groups with this property, with complete proofs: notably, either such a group has order at most n2, or it is a sharply 2-transitive group of order n(n+1), where n is a power of p.

I gave the last talk of the meeting. Contrary to my usual practice, I will tell you a bit about it, for two reasons. First, this is joint work with Colva Roney-Dougal; we don’t have a preprint yet, but I regard it as public following my talk, and so worth publicising. The second reason will emerge later.

The aim of the project is to say something about generating sets for finite groups. In the case of an elementary abelian p-group, the minimal generating sets are just bases in a vector space, and the theory is so easy that we teach it to all mathematics students. By the Burnside basis theorem, arbitrary p-groups are essentially no worse. A set generates a p-group P if and only if the corresponding cosets generate P/Φ(P), an elementary abelian group (where Φ(P) is the Frattini subgroup); so we just have a vector space “blown up” by the order of the Frattini subgroup. But for arbitrary groups, things are more complicated.

One gadget which has been much studied recently is the generating graph of a group G, in which group elements x and y are joined if and only if {x,y} = G. Of course, this is the null graph unless G is 2-generated; but, by a miracle which we don’t understand, at least every finite simple group is 2-generated.

When I first learned about this, I calculated the generating graph of A5, a group whose order is equal to the age of P-cubed. I found to my astonishment that the automorphism group of the graph has order 23482733690880. But it is not a new simple group; the reason is not hard to find. Elements of order 3 or 5 which generate the same cyclic subgroup have the same neighbour set in the graph, and so can be permuted arbitrarily. There is a normal subgroup of order (2!)10(4!)6 doing this, and the quotient is just S5, the automorphism group of A5.

So we can reduce the graph by the “g-equivalence relation”, in which two vertices are equivalent if they have the same neighbours. The resulting smaller graph shares many important properties (including clique number and chromatic number) with the original one, and is likely to have a more sensible automorphism group.

We were led to another equivalence relation, the “m-equivalence relation”, in which two elements are equivalent if they lie in the same maximal subgroups of the group G. It is clear that this is a refinement of g-equivalence, but is non-trivial for any finite group. So now I can state one of our conjectures:

Conjecture: In a finite simple group (or maybe even a 2-generated almost simple group), two elements are g-equivalent if and only if they are m-equivalent.

This is false in general, even for 2-generated groups. For S4, for example, a double transposition lies in no 2-element generating set, so they are g-equivalent to the identity, but not m-equivalent: there are 14 g-equivalence classes, but 15 m-equivalence classes. The numbers of m-equivalence classes in symmetric groups form an interesting sequence, beginning 1, 2, 5, 15, 67, 362, 1479, …

However, I learned later that Budapest is not a good place for marketing generating sets; they are readily available on street corners:

Generating sets

Posted in events, exposition | Tagged , , , | 2 Comments

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!

Posted in events, exposition | Tagged , , , , | 1 Comment