Two things that should be related

Here are two things that look as if there should be a relation between them.

A graph duality

In my paper on graphs defined on groups, I invented an ad hoc duality relation between pairs of graphs.

The context is that, in a little break from his PhD work, Saul Freedman had looked at the intersection graph of a finite group G, the graph whose vertices are the non-trivial proper subgroups of G, two subgroups joined if the subgroups have non-trivial intersection. This graph was first studied by Csákány and Pollák in 1969; they showed that, for a non-simple group G, if the graph is connected, its diameter is at most&nbs[;4. For simple groups, Shen proved in 2010 that the graph is connected, and asked for a bound on its diameter. Herzog, Longobardi and Maj gave a bound of 64, reduced to 28 by Ma. Saul was able to show that the correct upper bound for simple groups is 5, and that this bound is attained only by the Baby Monster and possibly certain unitary groups.

I was thinking about graphs such as the enhanced power graph, commuting graph, and non-generating graph at the time, and when I wrote the survey I realised that there was a connection.

Let Γ₁ and Γ₂ be graphs with no isolated vertices. I say that these graphs are dual if there is a bipartite graph B with bipartition (V(Γ₁),V(Γ₂)) such that, for i = 1,2, two vertices in V(Γ_i) are joined in Γ_i if and only if they have a common neighbour in B.

Now it is straightforward to see that, if Γ₁ and Γ₂ are dual, then there is a natural bijection between their connected components, and corresponding components have diameters differing by at most 1.

Question: What other properties are shared by dual pairs of graphs?

The relevance of this is that, for a group which is not cyclic of prime order, the non-generating graph is dual to the subgroup intersection graph. (We make a bipartite graph whose vertices are the non-identity elements and non-trivial proper subgroups, with adjacency being membership. Then two non-identity elements fail to generate the group if and only if they lie in a proper subgroup; and two non-identity proper subgroups have non-trivial intersection if and only if some non-identity element lies in both.

So Saul’s result is almost equivalent to a result on the diameter of the non-generating graph of a simple group.

But there is more. We can replace the subgroup intersection graph by the (usually much smaller) maximal subgroup intersection graph, and the duality still applies. (The number of subgroups of a group can be greater than polynomial in the group order, but the number of maximal subgroups cannot. According to Wall’s conjecture, the number of maximal subgroups is strictly less than the group order. This is now known to be false, but it is known to be bounded by c|G|^3/2, and the true exponent is thought to be much lower.)

It is easy to see that the maximal subgroup intersection graph is also dual to the non-generating graph. So similar comments also apply.

There are further results of this sort. For example, if G is minimal non-abelian, then the (maximal) subgroup intersection graph is dual to the commuting graph. And so on.

This looks like it should be a potential unifying principle for results about graphs defined on groups and related graphs.

The zero-divisor graph of a poset

The research discussion on graphs and groups, run by Ambat Vijayakumar and Aparna Lakshmanan in Kochi, produced a cornucopia of ideas, results, and papers. Tamizh Chelvam told us about the zero-divisor graph of a commutative ring with identity, and then Vinayak Joshi told us about the zero-divisor graph of a poset with zero. He proposes this as a unifying principle for various graphs defined on algebraic structures.

Let P be a poset which has a unique minimal element 0. A non-zero element a of P is a zero-divisor if there exists a non-zero element b in P such that the only element below both a and b is 0. The zero-divisor graph of P has as vertices the zero-divisors, two elements a and b adjacent if they have the above relation.

Now among several examples of such graphs, we have the following:

• The annihilating ideal graph of a commutative ring with identity is defined as follows: vertices are those annihilating ideals (ideals with non-zero annihilator) I for which there exists an annihilating ideal J with IJ = 0; adjacency of I and J is defined by this relation.
• Let G be a finite group. Define a relation R on G by the rule that x and y are in the relation if y is a power of x. This is a partial preorder, that is, a reflexive and transitive relation; so the set of equivalence classes of the equivalence relation S (in which two elements are equivalent if each is a power of the other) is partially ordered by R. Extending R by an arbitrary total order on each equivalence class, we obtain a partial order on G, whose comparability graph is the power graph of G. Now take the reverse of this partial order, and introduce a new least element 0 below everything else. Two elements a and b have the property that only 0 lies below both if and only if there is no cyclic subgroup containing a and b. So the zero-divisor graph is the complement of the enhanced power graph of G.
• Angsuman Das studied component graphs of finite vector spaces with a given basis. These turn out to be the joins of zero-divisor graphs of a lattice derived from the vector space with complete graphs.
• Any graph Γ can be considered as a simplicial complex, whose elements are the empty set and the vertices and edges of the graph. We can regard this complex as a poset, and take the zero-divisor graph of it. If we adjoin the edges of Γ to this graph, we obtain a graph whose chromatic number is the total chromatic number of Γ.

A concept which includes four such different graphs as special cases is obviously a good candidate for a unifying principle. Moreover, any general results that can be proved about zero-divisor graphs of posets will contain as corollaries results about the three types of graph above.

In particular, it often happens (for example, in the second and fourth examples above) that the graph is weakly perfect, that is, has clique number equ al to chromatic number. A good start would be to prove this for posets under som e additional condition which would have these results as special cases.

Question: Can we connect the above theories of dual graphs and zero-divisor graphs of posets?

Portugal

Portugal is one of my favourite countries in the world.

In large part this is due to my colleague and friend João Araújo, who arranged for me to visit Portugal for the first time in 2008, and on all of my many visits since, has taken me on “crazy trips” over much of the country; as well as the popular tourist attractions, I have seen things that most tourists never get to.

Last year, Rosemary’s nephew and partner had a holiday in Porto and the Douro valley. They asked me for recommendations for things to see. Since we didn’t have time for much discussion over Christmas, I wrote a little brochure about some of the highlights south of the Douro for them. I sent a copy to João, who corrected some historical errors (surprisingly few, since I wrote it without recourse to guidebooks, just occasional use of Google to check spelling), and encouraged me to go public with it.

So, with that seal of approval, here it is!

Happy new year

The world has been a bit crazy for several years. Let us hope for better times. I hope to have more mathematics to tell you about soon.

A theorem on polytopes

You know what polygons and polyhedra are. How do we extend their study to higher dimensions?

There are two parts to this question. The first involves incidence geometry: vertices, edges, faces, etc. Here the generalisation is fairly straightforward. A polygon has two types of objects, a polyhedron three; so for an r-dimensional polytope, we take objects of r possible types 0,1,…r−1, with incidence relations between different types satisfying certain conditions. (For convenience we take a single object of type −1 and one of type r incident with everything.)

In a polyhedron, an edge is incident with two vertices and two faces, which are incident with one another; and every vertex or face is contained in a triple of mutually incident objects called a maximal flag. We extend this: every set of mutually incident objects is contained in a maximal flag, having one object of each type. Moreover, a next-to-maximal flag, missing just one type of object, is contained in two maximal flags. Now, if a flag misses two types of object, then the objects of these two types indident with the flag form an incidence structure which is either a polygon (if the two missing types are adjacent) ir complete (if not). For example, in a polyhedron, the edges and faces containing a vertex form a combinatorial polygon; while vertices and faces incident with a common edge are incident with one another).

There are also connectedness conditions which I will not discuss.

I will also not discuss the metric properties (involving distances, angles, etc.) which make a polygon regular, but describe a different take on regularity.

Given a maximal flag F, there are exactly r maximal flags differing from it in just one position. All these are fixed by the stabiliser of F in the group of combinatorial automorphisms. So the order of the group does not exceed the number of maximal flags. We say that the polygon is regular if equality holds, which means that the group acts transitively (and regularly) on the set of maximal flags.

In a regular polygon, there is a unique element s_i mapping F to the flag F_i differing from it in position i only; it maps F_i back to F, so its square is the identity. Connectedness implies that these r elements generate the automorphism group. Moreover, if |i−j|>1, then s_i and s_j commute. So the automorphism group of a regular polytope is what is called a string C-group, which includes an intersection condition implying that the intersection of the subgroups generated by the involutions s_i for i∈I and for i∈J is generated by those with i∈I∩J.

Thus the search for regular polytopes “reduces” to the search for representations of a group as a string C-group; and a string C-group generating a group G determines a unique regulqr polytope up to isomorphism and duality.

The simplest family of regular polytopes to describe consists of the simplices (extending the sequence triangle, tetrahedron …). In this case the r generators are the adjacent transpositions in the symmetric group S_n, with n = r+1, occurring in the representation of this group as a Coxeter group of type A_n (discovered by E. H. Moore in 1896).

Maria Elisa Fernandes and Dimitri Leemans investigated regular polytopes with automorphism group S_n. They showed that there is only one of rank n−1 for n≥5 (the simplex), and, up to duality, only one of rank n−2 for n≥7. Moreover, there are examples of every possible rank from 1 to n−1.

Over the last several years, I have collaborated in work on regular polytopes, first with Dimitri, and then with Maria Elisa, on polytopes whose group is a (transitive) proper subgroup of S_n. We showed that these can have rank at most n/2+c. (For our strugle with the alternating groups, see here.) Now, exploiting these results and the techniques used in their proofs, we have shown what I think a remarkable theorem, proving a conjecture based on the first two results in the preceding paragraph and extensions of them.

Theorem. Suppose that n≥2κ+3. Then the number (up to isomorphism and duality) of regular polytopes of rank n−κ with group S_n depends only on κ, not on n.

(Thus these numbers can be computed by just computing these polytopes of rank r with group S_n with n=2r−3.) The numbers for κ = 1,2,… are 1, 1, 7, 9, 35, 48; we are computing the next number but it is a slow process.

I won’t begin to give the proof here; the paper is over 40 pages long and depends on results from our earlier papers and much else besides. I am very grateful to my coauthors for including me in the project. You can read the paper at . I will just say that, if the inequality between degree and rank holds, we show that there is a weak point in the diagram (called a “perfect split”) where one can insert a transposition to increase both degree and rank by 1.

The road closure property

My work with João Araújo and other semigroup theorists has produced a number of permutation group properties which lie between primitivity and 2-homogeneity, especially the synchronization family. Another of these is the road closure propery, which I have discussed here before. Last week, we had a workshop to try to understand this property.

The workshop was in the Convento do Arrábida, an old Franciscan monastery in a national park on the side of a mountain overlooking the sea, just south of Lisbon (on the tongue of land which ends at Cabo Espichel). A beautiful spot, although for the first three days of the workshop there was fog, rain and strong wind, so we had to wait for the stunning views. There was nothing to do but work, and work we did.

Let G be a permutation group on Ω. The orbital graphs for G are the graphs on the vertex set Ω whose edges are the orbits of G on 2-element subsets of Ω, thus one graph for each orbit. A permutation group is transitive if it fixes no subset of Ω except for Ω and the empty set, and is primitive if in addition it fixes no partition of Ω except the partition into singletons and the partition with a single part. According to a theorem of Donald Higman, G is primitive if and only if all its orbital graphs are connected. G is 2-homogeneous if it has just a single orbit on the 2-element subsets of Ω, that is, it has just one orbital graph which is the complete graph. So a 2-homogeneous group is primitive.

We say that G has the road closure property if, for any orbit O of G on 2-sets, and any proper block of imprimitivity B for the action of G on O, the graph with edge set O\B is connected. That is, if an orbital graph for G represents a road network, and if the roads in a block B are all closed for roadworks, it is still possible to travel around the network. It is clear that the road closure property implies primitivity. Also, the complete graph (on more than two vertices) cannot be disconnected by removing a block, since if it could then it would be the union of two disconnected graphs; so a 2-homogeneous group has the road closure property.

Why would anyone invent such a strange property? It turns out that it is motivated by semigroup theory. One very important class of semigroups consists of the idempotent-generated semigroups (an idempotent is an element equal to its square). Now we consider semigroups obtained by adding a non-permutation f to the group G and generating a semigroup ⟨G,f⟩, then removing the elements of G (since the only permutation which is an idempotent is the identity). We look for properties such as idempotent-generation for this semigroup, call it S (depending on G and f). Understanding such semigroups is the first step towards understanding all transformation semigroups having G as group of units, or normalizer.

Now it can be shown, fairly easily, that for a given group G,

S contains an idempotent for any choice of f of rank 2 if and only if G is primitive.

Furthermore, with a rather longer proof,

S is idempotent-generated for any choice of f of rank 2 if and only if G has the road closure property.

(The rank of a transformation is the size of its image.)

The gap between primitivity and the road closure property is not large; most primitive groups have the RCP (as I will call it). One example where it fails is provided by the non-basic groups. A primitive group G is non-basic if it is contained in a wreath product S_q wr S_m in its product action of degree q^m. This can be said another way. The Hamming graph H(m,q) has as vertices the set of all words of length m over an alphabet of size q; two vertices are adjacent if the words differ in exactly one coordinate (in coding theory terms, they have Hamming distance 1). Now the automorphism group of the Hamming graph is the wreath product of symmetric groups mentioned above; so G is non-basic if it acts as a group of automorphisms of a Hamming graph. Now, in the Hamming graph, each edge has a direction, the number of the coordinate in which their vertices differ; the set of edges with a given direction is a block of imprimitivity, and if we remove the ith block, then we can no longer change the ith coordinate by moving along the remaining edges, so the graph is disconnected.

Now a primitive group G is basic if it is not non-basic; and the task of the road closure problem is to describe all basic primitive groups which fail to have the road closure property.

Here is an example, which ties in with our deliberations in Arrábida. Consider our old friend the Fano plane.

Let G be the group of collineations and correlations (dualities) of this plane; this is a group of order 336 isomorphic to PGL(2,7). There are two primitive actions of G, on the 21 flags (the incident point-line pairs) and on the 28 antiflags (the non-incident point-line pairs). Both actions are basic (since their degrees are not proper powers); both fail the road closure property. This can be seen by similar arguments in each case, but there is a simple way to see both.

The orbital graphs are constructed similarly: the vertices are the flags (or antiflags); two vertices are joined if they share either a point or a line. Now construct a 7×7 array whose columns are indexed by the points and rows by the lines. Then G acts on this array with two orbits, the flags and the antiflags. Now it is easy to see that that, in each orbital graph, the horizontal and vertical edges form blocks of imprimitivity; and, just as in the non-basic case, removing a block disconnects both graphs.

According to the O’Nan–Scott Theorem, basic primitive groups are of one of three types: affine, diagonal and almost simple. Pablo Spiga, one of the participants in the workshop, has a proof that all basic affine groups have the RCP. We expect the same for diagonal groups. The problem, then, should reduce to considering almost simple groups, of which PGL(2,7) gives the smallest two examples.

A program written by Leonard Soicher, another participant, examined primitive groups of degree up to 4095 (the limit of the GAP library) and found that, in all cases where the stabilizer of a block contains the socle, there are just two blocks, as in this example. But we do have examples with three blocks. I mentioned one in the previous post; Pablo has another, of degree 6000, which may well be the smallest such. We have no examples with more than three blocks.

So a reasonable goal for the road closure program would be to show that there cannot be more than three blocks, and perhaps to classify the groups which have three blocks.

We cannot yet do that. But we have shown that, apart from cases where the block stabiliser contains the socle of the group, there are two other possibilities:

• G is the symmetric or alternating group of degree m (the number of blocks), and the given action is of rather large degree (at least 2^m);
• Ω can be identified with a subset of the set of k-element subsets of {1,…,m}, and adjacent pairs of subsets meet in a constant number of points.

No examples are known for any of these cases, and we have further numerical information which hopefully will allow us to elimiate them.

But there was more.

As described above, the RCP is equivalent to the statement that, for every rank 2 map f, the semigroup S obtained by generating a semigroup with G and f and then removing G is idempotent generated. So the alternative name for the RCP is the 2-idempotent generated property, or 2-id for short. But of course we can define k-id for any k≥2, and ask for a list of such groups.

The first major step has already been taken. A permutation group G has the k-universal transversal property, or k-ut for short, if given any k-subset A and k-partition P of Ω, there is an element g of the group G which maps A to a transversal to P. This property is equivalent to the statement that the semigroup S contains an idempotent, and so is weaker than k-id. Now we have previously studied groups with k-ut; they are all known apart from some families and some sporadic groups where we have been unable to decide. So the problem is to investigate these groups and determine which (out of those which definitely or possibly have k-ut) have k-id. At the workshop, João Araújo and Wolfram Bentz made some significant progress on this question.

I should add here that, for the case of 2-id groups, we have a combinatorial property involving objects of size polynomial in n which is equivalent, namely the RCP. This is lacking for higher values of k, and it is difficult for someone like me to understand exactly what makes the semigroup S idempotent-generated. Fortunately, negative results can be obtained by making a good guess about the k-partition to test, without needing to test them all.

In conclusion, we had a week in a stunningly beautiful place. The food was absolutely outstanding; Portuguese cuisine at its best. The weather was a mixed blessing but at least kept us to the task. And the facilities were adequate, apart from rather limited access to wi-fi (this is good and bad: like the weather it took away distractions, but it also made it difficult to look up previous results). So many thanks to João for organising a memorable occasion. I should not let this post conclude without mention of Gavril Farkas, who had come because he is interested in monodromy groups of covers of surfaces; both primitivity and 2-transitivity have natural interpretations in this context, and he was looking for intermediate properties which might have similar interpretations.

A warning

I have just learned that I am losing my personal webpages at St Andrews, http://www-groups.mcs.st-andrews.ac.uk/~pjc/

I know people have found some of this material useful. I will try to make it available in some other form, though this may have to be at my own expense.

Feel free to write to the university to complain.

COBS and equitable partitions

It happens sometimes that researchers working in different fields study the same thing, give it different names, and don’t realise that there is further work on the subject somewhere else. Here is a story of such a situation, which arose indirectly from the work Rosemary and I were doing with statisticians in Covilhã, Portugal, namely Dário and Sandra Ferreira and Célia Nunes.

I begin with the statistics. We are designing an experiment to test a number of different “treatments” (fertilizers, drugs, or whatever). We have a number of experimental units available: these may be plots of land, fruit trees, human or animal subjects, etc. For brevity I will call them “plots”.

The design for the experiment is a function from the set of plots to the set of treatments, giving the treatment to be applied to each plot.

The simplest case is where the plots are all alike, apart from small random variations. In this case there is no restriction on how we choose the design function; for efficiency (meaning small variance of estimators of treatment differences) we should apply each treatment the same number of times, or if this is not possible, choose the numbers of occurrences to differ by at most one.

But in practice things may be more complicated. The plots may differ on a number of factors, each corresponding to a partition of the set of plots. For example, an agricultural experiment may use several plots on each of a number of farms in different parts of the world; plots on the same farm will be more similar than plots on different farms, and analysis of the experiment should take this into consideration. The plots are partitioned into “blocks”, one for each farm.

Indeed, there may be several such partitions. In an experiment on fruit trees, the trees in an orchard may be arranged in a rectangular array, and may have been used for an experiment last year; then the rows, columns, and earlier treatments all form significant partitions. In an experiment on animal feed, the animals may be divided into pens, a number of pens on each of several farms. In a clinical trial, the gender of the subject and the hospital at which they are treated may be relevant.

Thus we have to consider “plot structure”, usually (as above) defined by a collection of partitions of the set of plots. It is convenient of the partitions satisfy some conditions: each should have all parts of the same size; if possible, any two should be “orthogonal”, meaning that they intersect proportionally; and perhaps the set of partitions should be closed under meet and join and contain the two trivial partitions (the partition with a single part and the partition into singletons). Such a plot structure is called an orthogonal block structure, or OBS for short.

The plot structure is given; the experimenter has no control over it. All that she can control is the design function.

The result of the experiment will typically be a real number measured on each plot, that is, an element of the real vector space V of functions from the set of plots to the real numbers. In this vector space, each partition of the set of plots is represented by a subspace of V, consisting of functions which are constant on each part of the corresponding projection. There is a natural inner product on V (the characteristic functions of singletons forming an orthonormal basis), and so there is an orthogonal projection onto the space corresponding to any partition: this has the effect of averaging the function over each part of the partition.

Even if the plot structure is not completely described by partitions, it may still be the case that it gives rise to a collection of linear maps on V. For example, if the plots lie in a circle, there may be a neighbour effect, and we could consider the adjacency matrix of the cycle graph.

Statisticians introduced a helpful notion here, that of a commutative orthogonal block structure, or COBS for short. Noting that the design function allocating treatments to plots corresponds to another partition of the set of plots (where plots getting the same treatment lie in the same part), they argued that it is helpful if the orthogonal projection onto the treatment subspace commutes with the matrices arising from the plot structure. They call such a set-up a commutative orthogonal block structure, or COBS.

Now we leave statistics for a while and turn to graph theory.

Let Γ be a graph, and Δ a partition of its vertex set with parts P₁, … P_r. Then Δ is said to be equitable if there is a r×r matrix M such that, for any i,j, the number m_ij of vertices of P_j joined to a given vertex in P_i depends only on i and j, and not on the chosen vertex. Among the various consequences of this definition, I mention just one: The matrix M is the restriction of the adjacency matrix of the graph to the subspace consisting of functions constant on the parts of Δ; so this subspace is invariant under the adjacency matrix of the graph, and moreover, the minimal polynomial of the matrix M divides that of the adjacency matrix of the graph, so that its eigenvalues are among those of the adjacency matrix.

Equitable partitions occur widely in finite geometry and combinatorics; among geometrix examples, one could mention ovoids in projective spaces. Also, it is clear that the orbit partition of any group of automorphisms of the graph forms an equitable partition of its vertex set.

Once one suspects that there is a connection between COBS and equitable partitions, it soon becomes clear what theorem needs to be proved to connect them. It is the following, whose proof is straightforward once we have decided what is needed.

Theorem A partition Δ is equitable for a graph Γ if and only if the projection matrix onto the subspace of functions constant on parts of Δ commutes with the adjacency matrix of Γ.

A simple consequence of this theorem (not immediately obvious) is that, if the graph Γ is distance-regular, then an equitable partition of Γ is also equitable for the distance-i graph of Γ, for all i up to the diameter of the graph. For distance-regularity means that the distance-i graphs have adjacency matrices which are polynomials in the adjacency matrix of Γ so any matrix which commutes with the adjacency matrix of Γ commutes with the adjacency matrices of all distance-i graphs.

The work we were doing in Covilhã concerned COBS for the half-diallel, a genetic term referring to the situation where the genome of an individual comes from two parents but there is no distinction in their role. Designs for such experiments could also be applied to the situation where an experimental unit consists of a pair of individuals from a population. This might, for example, involve comparing the efficiency of various communication methods (face-to-face, telephone, video call, email, etc.). Thus a COBS for such an experiment is an equitable partition of the triangular graph, whose vertices are the 2-element subsets of the set of individuals, two vertices joined if the subsets have non-empty intersection.

My earlier foray into equitable partitions, with Rosemary Bailey, Sasha Gavrilyuk and Sergei Goryainov, involved Latin square graphs; this could be applied in the situation of an n×n array of fruit trees where last year an experiment in the form of a Latin square was done on the trees.

So how did we come to realise the connection? It happened like this. Rosemary was working on a classification of the COBS for the triangular association scheme. I noticed that what she was doing had a superficial resemblance to what she had done on equitable partitions of Latin square graphs on a plane returning from China a few years ago. As said above, once you suspect that a connection exists, it is fairly straightforward to see what it is and to prove the required theorem.

An apology

What would life be like if I could remember all the things I ever knew?

Yesterday I was led to something I posted here twelve years ago. This was based on a talk to the London Algebra Colloquium by Mark Wildon.

He told us about results he had proved using Jordan’s theorem – this is the theorem of Jordan which gave me my fifteen minutes of fame when Jean-Pierre Serre talked about it at Queen Mary – on the existence of derangements in finite transitive permutation groups. Mark applied this to show the following, though he didn’t phrase it in these terms.

The conjugacy supercommuting graph on a group G is the graph whose vertex set is G, with an edge from x to y if there are conjugates of x and y which commute. Mark’s theorem asserted that an element of G is joined to all others if and only if it belongs to the centre of G. As a corollary, the graph is complete if and only if G is abelian.

These results form parts of theorems 4 and 5 in my paper with G. Arunkumar, Rajat Kanti Nath, and Lavanya Selvaganesh on “Super graphs on groups”, described here and now published in Graphs and Combinatorics. Our proof is the same as Mark’s.

We apologise to Mark for not attributing the result to him, and are happy to do so now.

A week in Florida

The week before last I was at the Deerfield Beach Resort in Florida, about halfway between Miami and Donald Trump’s place. My children could not believe it when I told them (I am not very good at holidays). Of course they guessed that it was not a holiday but a mathematics conference; in fact, in honour of the 70th birthday of Daniela Nikolova.

Unfortunately Daniela had to spend the entire conference in a wheelchair, having slipped and broken an ankle getting out of the jacuzzi on the pre-conference cruise. So we all wished her a speedy recovery; I do hope this happens.

It seemed important for speakers to remember when they first met Daniela. I am not sure of this. The first I can recall is Groups St Andrews in 2005, but there may have been earlier occasions which I have forgotten. A remarkable thing about the meeting was the number of pairs of participants who met for the first time at a Groups St Andrews meeting. It might be interesting to construct the graph …

The talks were a very mixed bag. There was a day for “Women in mathematics”, chaired by a man; and a day for “Young researchers in mathematics” bookended by two researchers who were no longer young. I won’t give a blow-by-blow account; I will just single out a few of my favourite talks. The first was by David Burrell. The count of groups of order 1024 announced in the year 2000 was incorrect; when he re-did the computations, he got a different number. At first he assumed he had made a mistake, and checked his calculations carefully. So eventually he contacted Eamonn O’Brien, a safe pair of hands if ever there were one. Eamonn was able to locate the mistake, apparently a simple transcription error in the tabulation of the results. It is not clear if it was human or computer error, though it looks like the former. Anyway, the correct number of groups of order 1024 is 49,487,367,289.

Gareth Jones told us about the Bateman–Horn conjecture. This is a conjecture in number theory but would have a number of important spin-offs in group theory, including the statement that there are infinitely many insoluble (and so 2-transitive) permutation groups of prime degree other than symmetric and alternating groups. The conjecture goes as follows. Suppose that you have a finite number of integer polynomials satisfying the three conditions

• each polynomial is irreducible;
• each polynomial has positive leading coeffiient;
• the product of the polynomials is not identically zero modulo any prime.

Under these conditions, Schinzel conjectured that there are infinitely many values of the argument for which all the polynomials take prime values. Bateman and Horn gave a considerable refinement of this conjecture, actually giving a formula for the conjectured asymptotics, a little complicated to state here but computable in particular cases. This conjecture applies to the twin primes conjecture (take the polynomials t and t+2), the Sophie Germain primes conjecture (take t and 2t+1), and the existence of infinitely many groups PSL(2,p) of prime degree (take t and t²+t+1). It applies in several other cases including my recent work with Pallabi Manna and Ranjit Mehatari: it would imply infinitely many simple groups whose power graph is a cograph. Gareth and his co-authors have shown that the Bateman–Horn conjecture predicts things like this with remarkable accuracy.

Delaram Kahrobaei (someone I first met at Groups St Andrews in 2013) speculated about whether graph groups would provide a post-quantum encryption system, that is, a trapdoor one-way function where the hard problem is hard even on a quantum computer, should one be built. (A graph group , aka a right-angled Artin group, is defined by a graph Γ generators for the group are vertices of Γ and the only relations are that adjacent vertices commute.)

Carmine Monetta, in addition to running the conference website and the computer facilities for speakers, spoke about the non-abelian tensor square of a group. This is a concept which I have met before, since it comes up in the work Bojan Kuzma and I did on the deep commuting graph of a group.

Mike Kagan was there with his family. He gave us the artefact shown in the picture, saying that it seemed to him that it might be Egyptian. In fact I was able to recognise it. In 2004 I went to Iran and was privileged to be able to visit Persepolis with a University car and driver from Shiraz. Here is one of the pictures I took then. Can you spot him?

We were taken on several excursions: to the Loxahatchee Wildlife Refuge, where the signs mentioned alligators and snakes but we saw a family of deer quite close up and some ducks that sounded like pigs; to the Jupiter campus of Florida Atlantic University, where we saw among other things the Max Planck Institute for Neuroscience, the only MPI in North America. We skipped the dolphin trip so as to get on with our joint work with Mike Kagan.

Back home, I had what has become an unfamiliar sensation: jet lag!

Cambridge

This is in a sense a follow-up to my earlier post here, describing how the 6-month programme at the Isaac Newton Institute had come to a premature end because of the covid pandemic.

The time I spent in Cambridge then (early January to mid-March) was a very good time for me. With Rosemary Bailey, Michael Giudici and Gordon Royle, I finished a paper on the subgroup of a transitive permutation group generated by derangements, which was published in the Journal of Algebra. More significantly, I worked with Rosemary, Cheryl Praeger and Csaba Schneider on the geometry of diagonal groups. This was intended as a continuation of the work by Cheryl and Csaba on the geometry of wreath products, published as a book in the LMS Lecture Note series. At the end of our time in Cambridge, we had almost completed a “synthetic” approach to the geometry, and agreed on how to write it up. But in the last couple of days, I had a vision of what the “axiomatic” version should say, although I doubted my ability to prove it. Nevertheless, stuck at home in St Andrews by the lockdown, Rosemary and I were able to prove the result I had in mind. Instead of putting a group in at the start, we were able to make it emerge naturally from purely combinatorial axioms, just as a division ring does in the axiomatic theory of projective planes. The paper has just been published in the Transactions of the American Mathematical Society, and I consider it one of my best.

Now that lockdown restrictions have been lifted, the INI offered the organisers a 3-month period from May to July this year, so I returned to Cambridge for this. However, things did not work so well. Instead of two programmes running, with the possibility of real interactions between the two sets of participants, there were four programmes, two of which were mostly stuck in a building not at all suitable for intensive mathematical research in the back of Churchill College. The organisers found me a share in a large office at the INI, but when I was there I had fewer chances of interacting with other participants. So I divided my time between three places (the third being a flat in Benians Court which had decent wi-fi; it was very tempting just to work there).

I did get a lot of work done during this period. But unlike the first period, it was not with other participants in the programme, but mostly with co-authors on the Graphs on Groups project, mostly in India; also with Marina in St Andrews who was on an undergraduate research internship.

Of course, because of Rosemary’s continuing difficulties after her fall, I had to arrange for her to be in Cambridge with me. Taking her out for walks around the streets, I became very aware of some of the drawbacks of Cambridge. Cyclists there are allowed to ride on the pavement beside the road in many places, while elsewhere they just do it anyway without permission. Often there is little warning to pedestrians about this. (On the stretch along Madingley Road from Storey’s Way to Lady Margaret Road, there was just one sign declaring it a dual-use path, cunningly hidden in the trees and bushes where I was not aware of it for the first month.) Not one in ten Cambridge cyclists seem to have come across a really useful invention, the bicycle bell, which can be used to warn pedestrians of their approach. Many are staring at their phones, heedless of pedestrians. Twice I saw, right outside our flat, a cyclist come off his bike at considerable speed; if this had happened while Rosemary was hobbling along with her stick, the consequences could have been very serious. I was also spooked by the Madingley Road/Lady Margaret Road junction, where there is no part of the traffic light cycle which is safe for pedestrians, and the car which is going to run into you is probably coming from behind. I had to brave this junction many times because the nearest food shop is in the centre of Cambridge, quite a distance from the flat.

The only time the programme came alive was during the last week and a bit. On Friday of the penultimate week there was a memorial day for Jan Saxl, though the location was not well publicised. Then in the last week, we had a closing workshop with some very lovely talks. These included

• Tim Burness on “Base 2 permutation groups and applications” – a strange and brave idea by Jan Saxl, since I would have thought that classifying groups with base size greater than 2 would have been an easier task.
• Scott Harper on “Invariable generation and totally deranged elements of simple groups”. Every finite simple group has a pair g, h of elements which invariably generate it, meaning that you can replace each of them by an arbitrary conjugate and still have a generating set. There is no conjugate pair which invariably generate, since this would imply that a single element generates the group; but Garzoni asked whether there was a pair in the same conjugacy class in Aut(S), for a simple group S, which invariably generate. Scott showed that this does happen, and moreover gave a complete classification of this situation.
• Persi Diaconis on “Double coset random walks on groups” showed us how some classical random walks (starting with contingency tables) can be realised as walks on the double cosets of finite groups, and how the character theory of the group can be used to analyse these.
• Alex Lubotzky on “Good locally testable codes”. The third time I have heard this, but each time it sinks in a bit further. The idea is very simple. Cayley graphs are either left or right: the connection set multiply elements on one side, so that multiplying on the other side gives an automorphism. They combine these two methods by having a left and a right connection set, to give a 2-dimensional Cayley complex with cells (g,lg,gr,lgr) where l comes from the left connection set and r from the right.

The conference honoured Michael Aschbacher and Robert Guralnick, neither of whom was present; both spoke remotely by Zoom. I am getting old and grumpy, and beginning to think that despite all the emissions Zoom talks save, they are not really a substitute for the real thing. But best wishes to both.