## Surprising fun fact

I have just found a proof of the following. Usual caveat: nobody else has read the proof yet, and I have not carefully checked it.

Let G be a finite group. The finite group H will be called an inverse Frattini group of G if G is isomorphic to the Frattini subgroup of H. As the climax of a series of papers going back to Gaschütz, Bettina Eick proved a beautiful theorem: G has an inverse Frattini group if and only if the inner automorphism group of G is contained in the Frattini subgroup of the automorphism group of G.

Now here is my new fact.

For a positive integer n, the following are equivalent:

• every group of order n has an inverse Frattini group;
• every group of order n is abelian.

It is certainly not true that a group has an inverse Frattini group if and only if it is abelian!

Part of the proof involves showing that, for every prime number p and positive integer m ≥ 3, there is a group of order pm which has no inverse Frattini group. This is true, but computational evidence suggests that much more is true; I conjecture that the proportion of groups of order pm with no inverse Frattini group tends to 1 as m tends to infinity, for fixed p. Here are the proportions for p = 2, m = 3,…,8: 0.4, 0.5, 0.62745…, 0.74906…, 0.87715…, 0.96213….

Posted in doing mathematics | | 2 Comments

## Integrals of groups revisited

After my trip to Florence in February, I wrote about the work I did there with Carlo Casolo and Francesco Matucci.

After Carlo’s untimely death the following month, we were left with many pages of notes from him about the work he had done on the problem during my visit and subsequently.

Our job, then, was to distil these notes into a paper and publish it in his memory.

It has taken a while to do this, but the resulting paper has just appeared on the arXiv. I won’t go through it blow by blow, but I would like to draw attention to two things about it, one major and the other rather smaller.

Let me remind you that we use the term “integral of a group G” to mean a group H whose derived group (generated by all commutators) is isomorphic to G. Every abelian group is integrable, but we were concerned in our first paper with the smallest integral of a given abelian group. In particular, if G is an infinite abelian group, does it have an integral in which it has finite index?

Carlo had put a lot of effort into this question, and had come up with, not a complete solution, but something close to it, at least in the case of a countable torsion abelian group. Unfortunately, his argument depended quite heavily on an “obvious” result from linear algebra. We had trouble with this, and spent a long time trying to come up with a proof. In the end, trying to track down where the proof attempts failed, I came up with a counterexample. Then, of course, the failure of this lemma brought down a lot of the beautiful arguments that followed from it.

I think that much of what Carlo did will prove to be correct, but a different approach needs to be found. So we simply took out everything depending on the lemma. (The paper is still a very solid 40 pages without this material.)

So I will state a very special case of this analysis. A proof of this would hopefully open the door to restoring much of the rest. I state it as a conjecture, though it was a corollary of a big theorem in Carlo’s notes.

Conjecture Let G be a countable group which is a direct product of finite cyclic groups. Then G has finite index in some integral if and only if the number of even positive integers n for which the cyclic group of order n occurs with multiplicity 1 in the product is finite.

The other matter is the solution of one of the problems in our earlier paper by Efthymios Sofos, from Glasgow. We had characterised the set of positive integers n for which every finite group of order n is integrable, and asked for the asymptotics of the number of such n up to x, for any x. It turns out that the leading asymptotics of this number is the same as for various similar-looking sets, “every group of order n is cyclic” (this was done by Paul Erdős in 1948), “every group of order n is abelian”, or “every group of order n is nilpotent”. The answer is

e−γ x/log log log x,

where γ is the Euler–Mascheroni constant.

There is much more in the paper; take a look.

## Moonlighting

In the last week of August, I attended for the first time a virtual conference. This was the 2020 Ural Workshop on Group Theory and Combinatorics, organised by Natalia Maslova at the Ural Federal University in Yekaterinburg and her colleagues. The conference was held as a Zoom meeting, and ran with only one hitch. As fate would have it, it was Natalia’s talk that was disrupted by a technological failure, so she started ten minutes late and had to talk fast. My co-author and St Andrews student Liam Stott was talking in the other parallel session immediately afterwards, so I switched as quickly as I could, only to find that the chair of that session had started him early (I assume the previous speaker hadn’t shown up), and he was three-quarters of the way through his talk already. Fortunately I knew what he was talking about!

Yekaterinburg is four hours ahead of St Andrews, so we had a week of very early rising; we had lunch at 10am, and were finished for the day (in both senses) by 2pm most days.

There were some very enjoyable talks, and as usual I can only mention a few. Cheryl Praeger talked about totally 2-closed finite groups. A permutation group G is 2-closed if every permutation preserving all the G-orbits on ordered pairs belongs to G. Cheryl and her colleagues call an abstract group 2-closed if every faithful transitive permutation representation of it is 2-closed. These groups were first studied by Abdollahi and Arezoomand, who found all nilpotent examples; with Tracey they subsequently found all soluble examples. Now this team augmented by Cheryl has considered insoluble groups. At first they found none, but they found that in fact six of the 26 sporadic simple groups (the first, third and fourth Janko groups, Lyons group, Thompson group, and Monster) are totally 2-closed. Work continues.

We had a couple of plenary talks about axial algebras; Sergey Shpectorov and Alexey Staroletov explained what these things (generalised from the Griess algebra for the Monster) are, and what the current status of their study is.

Greenberg’s Theorem states that any finite or countable group can be realised as the automorphism group of a Riemann surface, compact if and only if the group is finite. Gareth Jones talked about this. The proof, he says, is very complicated. He gave a new and much simpler proof; it did less than Greenberg’s Theorem in that it only works for finitely generated groups, but more in that the Riemann surface constructed is a complex algebraic curve over an algebraic number field.

Misha Volkov gave a beautiful talk about synchronizing automata. He began with the basic stuff around the Černý conjecture, which I have discussed before, but added a couple of things which were new to me: a YouTube video of a finite automaton taking randomly oriented plastic bottles on a conveyor belt in a factory and turning them upright; and the historical fact that the polynomial-time algorithm for testing synchronization was in the PhD thesis of Chinese mathematician Chung Laung Liu (also transliterated as Jiong Lang Liu), two years before the Černý conjecture was announced. Then he turned to new results, and showed that, with only tiny changes (allowing the automaton to have no transition for some state-symbol pair, or restricting the inputs from arbitrary words to words in a regular language) the synchronization problem can jump up from polynomial to PSPACE-complete!

Alexander Perepechko gave a remarkable talk, connecting the Thompson group T, the Farey series, automorphism groups of some affine algebraic surfaces, and Markov triples, solutions in natural numbers to the Diophantine equation x2+y2+z2 = 3xyz. (There is a long-standing conjecture that a natural number occurs at most once as the greatest element in some such triple. The sequence of such numbers begins 1, 2, 5, 13, 29, 34, 89, …. I will not attempt to explain further.)

Rosemary became the fourth author of the “diagonal structures” quartet to talk about that work, which I discussed here. She concentrated on the heart of the proof, the first place in the work where the remarkable appearance of algebraic structure (a group) from combinatorial (a Latin cube with a mild extra hypothesis) appears. Without actually describing how the hard proof goes, she explained the context and ideas clearly. I think this ranks among my best work; and all I did, apart from the induction proof of which Latin cubes form the base, was to insist to my co-authors that a result like this might just be possible, and we should go after it.

One of my early heroes in group theory was Helmut Wielandt; his book on permutation groups was my first reading as a graduate student. Danila Revin gave us a Wielandt-inspired talk. Wielandt had asked, in Tübingen lectures in the winter of 1963-4, about maximal X-subgroups of a group G, where X is a complete class of finite groups (closed under subgroups, quotients and extensions). Let kX(G) be the number of conjugacy classes of maximal X-subgroups of G, Wielandt said that the reduction X-theorem holds for the pair (G,N) if kX(G/N) =  kX(G), and holds for a group A if it holds for (G,N) whenever G/N is isomorphic to A. Wielandt asked for all A, and then all pairs (G,N), for which this is true; this is the problem which Danila and his co-authors have now solved.

(I hope Danila will forgive me an anecdote here. At an Oberwolfach meeting in the 1970s, one of the speakers told us a theorem which took more than a page to state. Wielandt remarked that you shouldn’t prove theorems that take more than a page to state. Yet the solution to his own problem took nearly ten pages to state. I think this is inevitable, and simply teaches us that finite group theory is more complicated than we might have expected, and certainly more complicated than Michael Atiyah expected. Indeed, in the very next talk, Chris Parker told us about work he and his colleagues have done on subgroups analogous to minimal parabolic subgroups in arbitrary groups. This is intended as a contribution to revising the Classification of Finite Simple Groups, and they hoped to show that with an appropriate list of properties only minimal parabolics in groups of Lie type and a few other configurations could arise; they obtained the full list and were rather dismayed by its length, which would make the applications they had in mind very difficult.)

Among other fun facts, I learned that the graph consisting of a triangle with a pendant vertex is called the paw in Yekaterinburg, but is the balalaika in Novosibirsk.

On the last day of the seven-day meeting, we had two talks on dual Seidel switching, by Vladislav Kabanov and Elena Konstantinova, who were using it and a more general operation to construct new Deza graphs and integral graphs.

After a problem session, the conference ended by a virtual tour of Yekaterinburg (or Sverdlovsk, as it was in Soviet times), covering the history, architecture and economics, and illustrated by photographs and historical documents; the tour guide was Vladislav’s daughter.

Life was made more difficult and stressful for me because I was doing something which would have been completely impossible in pre-COVID times: I spent some time moonlighting from the Urals conference to attend ALGOS (ALgebras, Graphs and Ordered Sets) in Nancy, France, a meeting to celebrate the 75th birthday of Maurice Pouzet, which I didn’t want to miss. Many friends from a different side of my mathematical interests were there; as well as Maurice himself, Stéphan Thomassé, Nicolas Thiéry, Robert Woodrow, Norbert Sauer, and many others.

The three hours’ time difference between Yekaterinburg and Nancy meant that there was not too much overlap between the two meetings, so although I missed most of the contributed talks in Nancy, I heard most of the plenaries.

Stéphan Thomassé talked about twin-width, a new graph parameter with very nice properties. Given a graph, you can identify vertices which are twins (same neighbours) or nearly twins; in the latter case, there are bad edges joined to only one of the two vertices; the twin-width is the maximum valency of the graph of bad edges. Bounded twin-width implies bounded treewidth (for example) but not conversely; a grid has twin-width 4. Graphs with bounded twin-width form a small class (at most exponentially many of them), and, remarkably, it is conjectured that a converse also holds.

Jarik Nešetřil and Honza Hubička talked about EPPA and big Ramsey degrees respectively; I had heard these nice talks in Prague at the MCW, but it was very nice to hear them again.

Norbert Sauer talked about indivisibility properties for permutation groups of countable degree. I might say something about this later if I can get my head around it, but this may take some time. In particular, Norbert attributed a lemma and an example to me, in such a way that I was not entirely sure what it was that I was supposed to have proved! (My fault, not his – it was the end of a long day!)

Nicolas Thiéry gave a very nice talk on the profile of a countable relational structure (the function counting isomorphism types of n-element induced substructures), something to which Maurice Pouzet (and I) have given much attention, and on which there has recently been a lot of progress. (I discussed some of this progress here, but there has been more progress since.) In particular, structures whose growth is polynomially bounded are now understood, due to Justine Falque’s work, and for primitive permutation groups there is a gap from the all-1 sequence up to growth 2n/p(n), where p is a polynomial, thanks to Pierre Simon and Sam Braunfeld.

Unfortunately the conference was running on BigBlueButton, some conference-enabling software which I had not encountered before but which is apparently popular in France. I am afraid that it was simply not up to the job. The second day of the conference saw some talks and sessions abandoned, because speakers could not connect; I could sometimes not see the slides at all, and the sound quality was terrible. I discovered that one is recommended to use Chrome rather than Firefox, and indeed it did work a little better for me, but not free of problems. On this showing I would not recommend this system to anyone.

In particular, a beautiful talk by Joris van der Hoeven was mostly lost for me. I couldn’t see the slides. Joris’ explanations were perfectly clear, even without the visuals, but sometimes I lost his voice as well. The talk was about the connections between different infinite systems: ordinals, Hardy fields, and surreal numbers. In better circumstances I would have really enjoyed the talk.

I hasten to add that the problems were completely ouside the control of Miguel Couceiro, the organiser, and marred what would have been a beautiful meeting.

## A problem

I seem to have too many balls in the air at the moment. So let me drop one here. Any thoughts very welcome.

A k-hypergraph consists of a set X of vertices and a collection of k-element subsets called edges. It is k-partite if there is a partition of the vertices into k parts so that every edge is a transversal to this partition, which I will call a k-partition.

Clearly there is a tension between edges and k-partitions; you would expect that more k-partitions would imply fewer edges. In one special case this is true. The existence of a second k-partition implies the existence of two vertices x,y which lie in the same part of one of the k-partitions and different parts of the other; then no edge can contain x and y.

My conjecture is very specific:

Suppose that the k-hypergraph on n vertices has at least kr k-partitions, for some positive integer r. Then there is a k-partite k-hypergraph H1 on n−r vertices which has at least as many edges as H.

The hypotheses are not pulled out of the air. Adding an isolated vertex v to a k-partite k-hypergraph multiplies the number of k-partitions by k, since v can be added to any one of the parts. So the conjecture is true if the hypergraph has r isolated vertices.

The conjecture is true if k = 2. For a connected bipartite graph has a unique bipartition; so a graph with 2r bipartitions has at least r connected components, and a simple calculation gives the result.

Posted in doing mathematics | Tagged | 4 Comments

## Communication

If you have been trying to contact me by email at QMUL recently, please try my St Andrews address instead.

Inevitably, I suppose, technology tends to fail in the middle of a pandemic. Both QMUL and St Andrews use Outlook for email. While the St Andrews version continues to work fine, the QMUL version has gone into a sulk and does nothing. I get a page looking like it has been written in unadorned HTML with a very large font size; none of the links work, and no new mail has shown up for a week. The problem occurs on both the laptops I have access to now, and in both Firefox and Chrome, so I doubt that the trouble is at my end. I have put in a trouble ticket and wait for a response.

Of course, this has only been one of a rash of problems in the last couple of weeks. Just before I went to Prague for the Midsummer Combinatorics Workshop, my new Dell laptop started giving trouble. Mail and web pages would fail to download. At first I assumed it was a problem with the wi-fi. But when various other difficulties started happening, like failing to shut down properly, and failing to read USB drives, and then failing to work even when connected via an ethernet cable, it appeared to be more serious. Fortunately I was in Prague, where Honza Hubička took it as a challenge to get it working. The problem turned out to be way outside my competence, and I am not even sure I can describe it properly. On the Dell, it seems, everything connects to the USB rather than directly to the CPU; at some point Linux was upgraded, but the upgrade was incompatible with the USB driver in the Dell. So Honza was able to fix it by going back to an earlier version of Linux.

At almost exactly the same time, my fairly new compact camera broke. This seemed to be a mechanical problem: if you touch the zoom control, it seizes up and goes into a sulk, demanding to be turned off. So back to my old camera, which had no direct communication with the computer, so I have to take out the memory card and read that. Now I had a gadget which connects a card to a USB port, but I lost it before Christmas (I left it behind after giving a seminar at Imperial College). So what to do? Eventually I took both cameras to Prague, used the old one to take photographs, put the card into the new one, and transferred the pictures.

I didn’t take my ancient Acer laptop to Prague; it is big and heavy compared to the Dell. But soon after my return, it developed a problem of its own: the battery refused to charge, and was running down at an alarming rate. Fortunately this had happened once before. The fix is just to leave it for a couple of days, after which it behaves itself again.

My third (and preferred) laptop, by Entroware, is (sad to say) in London, and unavailable to me until I am brave enough to travel south.

Posted in Uncategorized | Tagged , , , , | 4 Comments

## Puzzle solution

Thank you, Honza, spot on.

In 1964, Richard Rado published a construction of a universal graph, a countable graph which embeds every finite or countable graph as an induced subgraph. His graph turns out to be an explicit example of the Erdős–Rényi “random graph”.

The construction goes like this. (Here we are being logicians, so 0 is a natural number.) Any finite subset S of the natural numbers can be represented as a single number, the sum of the powers 2s for sS. To reverse the construction, take a number n, write it in base 2 (as a sum of powers of 2), and take the set of exponents which occur. (In this way the natural numbers form a model for hereditarily finite set theory, that is, Zermelo–Fraenkel set theory with the negation of the axiom of infinity, so that all sets are finite.

Let S(n) be the finite set corresponding to the number n.

Now the construction of the graph goes like this. Take two numbers n and m. One is smaller than the other; without loss, m < n. Now we join m to n if (and only if) m belongs to the set S(n).

What do we learn from this representation? Maybe not much, since the graph is most usually recognised by its properties. But here is one thing we learn. The graph is homogeneous, that is, any isomorphism between finite subgraphs extends to an automorphism of the graph. Using Rado’s representation, we see that the automorphism can be chosen to be a primitive recursive function (though, unfortunately, this does not mean that there is a simple representation for it: if you think it should, try to find a simple representation for an automorphism which interchanges vertices 0 and 1.)

In 1971, Ward Henson constructed a family of graphs with similar properties. The Henson graph Hn has the properties that it is homogeneous, it contains no copy of the complete graph on n vertices, and it is universal for finite or countable graphs containing no Kn. Later, Lachlan and Woodrow showed that, up to complementation, these graphs and Rado’s are the only “non-trivial” countable homogeneous graphs.

For simplicity I will stick to the case n = 3 here.

Henson found H3 inside Rado’s graph R, by a simple construction. Consider the set of natural numbers n such that n is not the largest vertex of a triangle in R. This is done by taking the natural numbers in turn, and including n in our set if and only if S(n) contains no edge of the graph; that is, for no i and j in S(n) does it happen that i is in S(j). Thus, the vertex set can be found iteratively; this is the set which was given in the puzzle.

Now this is a simple enough construction. If we had a simple formula for the vertex set, then we would have a simple explicit presentation of H3: the vertices would be given by the formula, and the edges would be defined exactly as in Rado’s graph.

But a simple formula of this sort is still lacking …

## A puzzle

What is the sequence that begins like this?

0, 1, 2, 4, 5, 8, 12, 16, 17, 18, 24, 32, 34, 40, 48, 50, 56, 64, 65, 72, 80, 81, 88, 96, 104, 112, 120, 128, 136, 144, 152, 160, 168, 176, 184, 192, 200

Hint: it is connected with Rado’s explicit description of the Erdős–Rényi countable random graph. There is another clue in the tag.

Posted in doing mathematics | Tagged | 1 Comment

## Peter Sarnak’s Hardy Lecture

Yesterday, Peter Sarnak gave the London Mathematical Society’s 2020 Hardy Lecture (remotely). He talked about gaps in the spectra of connected cubic graphs. It was a talk properly described as a tour de force, applying to the problem ideas from algebraic geometry (Weil’s proof of the Riemann conjecture for curves over finite fields), probability (Benjamini–Schramm measure), and fractal geometry (the Julia set of a real quadratic), among many other things.

I won’t attempt to describe more than the first few ideas in the talk. I think it was filmed, and a video will no doubt appear at some point; I do urge you to watch it.

Let X be the set of all finite connected cubic graphs (graphs of valency 3). We are interested in spectral questions; the spectrum of a member of X is the set (or multiset) of eigenvalues of its adjacency matrix. Since the graphs are regular, the adjacency spectrum is a simple transform of the Laplacian spectrum. It is well known that the eigenvalues of such a graph are all real, and lie in the interval [−3,3]; the value 3 is always a simple eigenvalue, and −3 is an eigenvalue if and only if the graph is bipartite.

A subinterval I of [−3,3] is a gap if there exist arbitrarily large graphs in X with no eigenvalues in this interval; it is maximal if there is no strictly larger interval which is a gap.

The first gap is (2√2,3), due to Alon and Boppana; the maximality of this gap depends on the existence of Ramanujan graphs, shown in the 1980s by Margulis and by Lubotzky, Phillips and Sarnak. As the name suggests, the construction of such graphs uses a substantial amount of number theory related to work of Ramanujan. The speaker told us that he had been rash enough to state that the construction would not be possible without number theory; but he was proved wrong (and taught to be more cautious) when a group of physicists found a construction using Lee–Yang theory in statistical mechanics.

I was so impressed with the Lubotzky–Phillips–Sarnak paper when it came out that I gave a seminar talk to the pure mathematicians at Queen Mary expounding it.

Then Peter Sarnak mentioned two other potential gaps, interest in which had come from real applications: gaps at −3, important in the theory of waveguides; and gaps at 0, important in the Hückel theory of fullerenes (molecules made of carbon atoms forming polyhedra with only pentagonal and hexagonal faces, like the football (which chemists call the buckyball). I will just repeat some of what he said about the first of these two.

He and Alicia Kollár (and others) have shown the remarkable result that [−3,−2) is a maximal gap. He associates the name of Alan Hoffman with this gap. The name is entirely appropriate. Hoffman did a lot of work on graphs with least eigenvalue −2, but in the end it was Jean-Marie Goethals, Jaap Seidel, Ernie Shult and I who proved the theorem he had been trying to prove, giving a virtually complete description of such graphs. I have described our result here; Peter Sarnak was kind enough to describe the paper as “beautiful”, and I don’t mind shining in reflected glory for a moment.

So here is the path from our theorem to the gap described above; the details were not given in the lecture.

We showed that, with finitely many exceptions (all realised in the exceptional root system E8), all connected graphs with smallest eigenvalue −2 (or greater) are what Hoffman called generalised line graphs. Fortunately I don’t have to tell you what these are, since it is an easy exercise to show that if a generalised line graph is regular, then it is either a line graph or a cocktail party (n couples attend a cocktail party, and each person talks to everyone except his/her partner). Moreover, if a line graph is regular, then it is the line graph of either a regular graph or a semiregular bipartite graph.

The cocktail party graph has valency 2n−2, which is even; so is not possible in our situation. The line graph of a regular graph of valency k has valency 2k−2, which is also even. The line graph of a semiregular bipartite graph with valencies k and l has valency k+l−2. So in our situation we only have to consider line graphs of semiregular bipartite graphs where the valencies in the two bipartite blocks are 2 and 3.

Now such a graph is obtained from a smaller graph Y in X (namely, the induced subgraph of the distance-2 graph on the set of vertices of valency 3) by inserting a vertex in each edge. So its line graph is built from Y by replacing each vertex of Y by a triangle, or sewing in triangles.

We conclude that, with finitely many exceptions, any graph in X with no eigenvalues in [−3,−2) is obtained from a graph in X by sewing in triangles. Moreover, such graphs are line graphs of graphs with more edges than vertices, and so really do have −2 as an eigenvalue; so the gap is maximal.

## National Windrush Day

Today is National Windrush Day. I’d like to put on record (for what it’s worth) my wholehearted support and sympathy for the Windrush generation.

Although I have never suffered the ill-treatment meted out to some of the Windrush generation by the Home Office, I feel close enough to them to have some appreciation. I arrived in the UK by ship from a Commonwealth country in 1968, and was given indefinite leave to remain in 1971. The only proof I have for this is a smudged stamp in an expired passport. On one occasion I was told by an immigration officer that I had no right to stay in the UK, and that he could exclude me with no right of appeal.

According to today’s news, the government, having received a report on the Windrush generation, have responded by setting up yet another inquiry. Will anything change?

## Jan Saxl

This morning brought the news that Jan Saxl died on Saturday.

Jan arrived in Britain in the early autumn of 1968, as did I: a very significant time for Czechoslovakia. (I spent six weeks in Earls Court, in London, before term started in Oxford; the first I knew about events was when I went to see a Soviet exhibition in Holland Park and found the exhibition hall surrounded by demonstrators.)

He is my mathematical brother, a student of Peter Neumann, taking his DPhil just two years after I did. (I have a vague memory that I was nominally his supervisor for a very short time while Peter Neumann was away, but I may be confusing him with David Cooper.) We collaborated on four papers; the best-known is the proof of the Sims conjecture, joint also with Cheryl Praeger and Gary Seitz.

Of course he had many collaborations with other mathematicians, especially Martin Liebeck and Cheryl Praeger, and produced some work of very great significance to the finite group theory community and more widely.

Jan was a good friend. When I directed a six-month programme on Combinatorics and Statistical Mechanics at the Isaac Newton Institute in 2008, he arranged for me to have a visiting fellowship, with a flat in Rose Crescent (up the stairs above the famous Gardenia) and lunches and dinners with the College fellows; the small price I had to pay was to give “three or four lectures” to the maths students in the College, which of course I was delighted to do.

Jan is someone who touched many people deeply. The world seems a greyer place without him. I hardly know what to say.

Posted in Uncategorized | | 5 Comments