A rant

When the Great Helmsman died in 1976, Jung Chang was able to put on a convincing display of abandoned grief. But afterwards, she decided to think through Mao’s philosophy, and how he had been able to exert such control. She decided that he had been a “restless fight promoter”, who understood and exploited the ugly side of human instincts such as envy and resentment, and used them together with the ignorance of his followers to eliminate possible challengers.

The Chairman might have been interested to know that this process has now been automated. The Internet and the World Wide Web, inventions which huge potential for good, can be exploited in much the same way. Start a rumour on social media, and there will be people who believe it without checking, and are ready to take up aggressive stances for the cause.

Take BLM, for example. This is absolutely necessary and vitally important; our society is shamefully riven with racism, and black people find themselves on the end of it on a daily basis. So the movement has become a vital force for change.

But it can be used for more sinister motives. Cancel culture has a good side; it is surely wrong that someone who made a fortune trading other humans with scant respect for their lives should be memorialised, even if he donated some of this fortune to the good of his city.

But this is a convenient weapon for taking down your enemies, even if they are not here to speak for themselves. It would be a shame if the whole movement were to be tainted by such activity.

This brings me to my real topic, the statistician and geneticist R. A. Fisher.

Earlier this year, Fisher was denounced as a racist by a historian, who was so on top of her subject that she could actually claim that Fisher invented Latin squares. The movement was taken up by others, the walls of Gonville and Caius College in Cambridge were defaced, and the governing body of the College yielded to popular pressure and removed the stained glass window in their dining hall in which Fisher is commemorated by a Latin square. (I will say more about this in a moment.) In any case, I am a member of the College, having been admitted during my tenure of a G. C. Steward fellowship there in 2008, so I feel entitled to put my head above the parapet.

The complaint against Fisher is that be belonged to (and was for a time the president of) the University of Cambridge Eugenics Society. This proves he was a racist, right? Well no, actually, if you look a little closer.

Eugenics was in its origin a plan to use genetic information to “improve” the human stock, as humans have been doing to other life forms for many millennia. If you have ever had genetic counselling, or have employed embryo testing, then you could be said to be making use of eugenics.

Of course, what constitutes an improvement is not entirely clear, and a lot hinges on the interpretation of this. There is no doubt that, in the first half of the twentieth century, eugenics meant different things to different people. In Germany and the USA, it was enmeshed with racism from quite early on. (Read about David Starr Jordan, the founding president of Stanford, to see the extent to which this was true.)

But in Britain, as always, class was the most important determining factor; the Eugenic Society was mainly populated by people from the middle classes who were uneasy about the rise of the lower classes. It encouraged the middle classes to have more children. The wider attitude persisted. In a book of commentary on the Sokal hoax, published by the editors of Lingua Franca, the Introduction gives a brief account of the field of Cultural Studies, and we read, “The discipline’s first institutional incarnation was the Centre for Contemporary Cultural Studies, a postgraduate research institute established in 1964 at the University of Birmingham in England. […] American cultural studies is often said to be characterized by a movement away from the Birmingham school’s emphasis on social class towards other aspects of identity, such as race and gender […]”.

For Fisher, a particular point at issue was intelligence. He regarded himself (correctly) as intelligent, and so (more dubiously) felt it his duty to have many children himself. He was not a person who found it easy to change his opinions or admit his mistakes. But he did leave the Eugenics Society. I have no hard evidence for this, but I suspect there were two reasons: first, his own research in genetics and that of others was showing that “things were not so simple”; and second, when the society appeared to be moving from discussion to action, he felt he could not be part of it.

As hinted above, nobody regarded Fisher as an easy-going or pleasant colleage. But that is not the same as being a racist; students from Africa and India, Jewish refugees from Nazi Germany, seem to feel affection for him and what he contributed to the discipline and to their careers. (Read Walter Bodmer’s account here.) And that he was a great scientist there is no doubt. Sticking to statistics (since I know little about genetics), his principles for experimental design and analysis, notably his insistence on randomization, replication, and blocking, have enormously improved the accuracy of experimental results, which have given us better agricultural practices (and so more food to feed the world) and better drugs (because of randomized clinical trials). It would not be easy to count the number of lives saved as a result.

So I will not be removing Fisher’s inequality from my teaching material any time soon.

On Latin squares: The window in Caius was based on the cover of his book The Design of Experiments. It appeared on every one of the many editions the book went through. Nobody knows where it came from. It seems it does not occur anywhere in Fisher’s works, and it has been suggested that someone at the publisher, who knew what a Latin square is, sat down and produced one essentially at random. This is reinforced by the fact that on the cover of one edition (the sixth, I think), it was printed upside down.

And if you don’t know who did invent Latin squares, Wikipedia has this to say: “The Korean mathematician Choi Seok-jeong was the first to publish an example of Latin squares of order nine, in order to construct a magic square in 1700, predating Leonhard Euler by 67 years.” (Euler was also constructing magic squares when he came up with the idea.)

In conclusion, a remark. If you visit St Andrews, walk along Lade Braes. You will find that a number of citizens of the town are commemorated by trees, marked with plaques at ground level. The plaques are quite unobtrusive, and hopefully not upsetting to anyone who found that person’s views offensive. Also, one presumes that by the time the trees die, those who remember the person commemorated will also have gone, so the fame will be no more permanent than it should be. Moreover, if some future movement demanded that such monuments would fall, and people showed up to chop down a tree and throw it into the river, it should not be hard to recognise them as vandals. This is a solution that might be more widely adopted …

Posted in Uncategorized | Tagged , | Leave a comment

Graphs defined on groups

Apologies; I have been so busy lately that very little has got written up. Let me try to remedy this with a quick tour through some recent mathematical developments.

As some of my posts have hinted, one topic I have been much involved with is graphs defined on groups, typically things like the commuting graph, generating graph, and power graph. This came about for a couple reasons, both emanating from India. First, Angsuman Das at the Presidency University in Kolkata asked me to speak at an International Conference on Algebraic Graph Theory and Applications on this topic. While I understand the main part of Algebraic Graph Theory to concern study of eigenvalues and automorphism groups of graphs, I know that there are a number of people in India and elsewhere who are interested in these specific topics. I was asked to give a 90-minute expository talk. So I had a bit of reading up to do.

At about the same time I had an email from Ranjit Mehatari in Rourkela enclosing a preprint of some recent research and asking for suggestions on new research topics. As I have discussed, this led to some new ideas about questions of the general form: for which groups G does the power graph of G have certain specified properties? You can read the resulting preprint on the arXiv, but here are two particular questions which seem of interest.

  1. The power graph of a finite group (two vertices joined if one is a power of the other) is always a perfect graph. What about the enhanced power graph (two vertices joined if they generate a cyclic group) or the commuting graph (two vertices joined if they generate an abelian group)? For which groups is each of these a perfect graph? This has not been much studied, and is I think of interest.
  2. For which groups G is the power graph of G a cograph (that is, does not contain the 4-vertex path as induced subgraph)? We know the answer for nilpotent groups, but the general case is open.

While preparing my talk for Kolkata, I was struck by the fact that the Gruenberg–Kegel graph of a finite group carries a lot of information about several of these graphs. This graph has as vertex set the set of prime divisors of the group order, with an edge from p to q if and only if the group contains an element of order pq. So it is very much smaller than the graphs defined on the group! Now:

  1. For groups with trivial centre, the commuting graph is connected if and only if the GK graph is connected.
  2. The power graph is equal to the enhanced power graph if and only if the GK graph is a null graph (that is, has no edges).
  3. There is a necessary condition, and a sufficient condition, for the power graph of G to be a cograph, both phrased in terms of the structure of the GK graph – but there is no necessary and sufficient condition depending only on the GK graph.

While thinking about the second of the above, I wrote to Natalia Maslova to ask if she had a list of groups with this property. She was able to work it out, and we hope to make all this available shortly.

But in the meantime we turned our attention to another problem about the GK graph. We were able to show the following. There is a function F with the property that, given a finite graph Γ, if the number of groups with GK graph isomorphic to Γ is greater than F(n), where n is the number of vertices, then it is infinite. Moreover, F is bounded by a polynomial (of degree 7 in our proof, though no doubt some improvements could be made). The paper has just gone on the arXiv.

A chance remark from Natalia in this connection led me in a completely different direction, which I have been working out with Bojan Kuzma. We have defined a new graph which lies between the enhanced power graph and the commuting graph. We call it the deep commuting graph. The definition looks a bit abstruse. It depends on the notion of a Schur cover of G, a group H with a subgroup Z such that H/Z is isomorphic to G, and Z is contained in both the centre and the derived group of H; moreover, H should be as large as possible subject to this. Now we say that x and y are joined in the new graph if and only if their inverse images in H commute. (Since Z is central in H, this condition does not depend on the choice of coset representatives of Z.)

A given group can have several different Schur covers, but they cannot be too different; the subgroups Z are all isomorphic (this is the Schur multiplier of G); and the graphs defined on G by the above procedure are all isomorphic. However, a frustrating open problem remains. We do not know whether the graphs on G defined by different Schur covers are all equal (that is, have the same edge sets), even though they must be isomorphic, and must lie between the enhanced power graph and the commuting graph.

We also have necessary and sufficient conditions for our new graph to be equal to either the enhanced power graph or the commuting graph. Equality in the latter case holds if and only if the Schur multiplier is equal to the Bogomolov multiplier: this is a lesser-known group-theoretic construction which arose first in studying rationality questions in invariant theory. A paper should be on the arXiv shortly.

And finally for this post, St Andrews PhD student Saul Freedman (of whom I am second supervisor) has been looking further up the hierarchy. If G is non-abelian or not 2-generated, the commuting graph is a spanning subgraph of the non-generating graph, in which x and y are joined if together they do not generate the whole group. The edge set of this graph is the union of complete graphs on the maximal subgroups of G. Saul has been looking at the difference between this and the commuting graph, which we call by the less than snappy (but descriptive) title non-commuting non-generating graphx and y are joined if they don’t commute but don’t generate the group. He has very strong results on various properties of this graph, especially its connectedness (apart from the identity); the answer for nilpotent groups is particularly complete and a paper is on the arXiv.

In addition, Saul used rather similar techniques to study the intersection graph of a group G, whose vertices are the non-trivial proper subgroups of G, two subgroups joined if they have non-trivial intersection. It was known to be connected, but for simple groups the best upper bound for the diameter was 28. Saul has reduced this to the best possible value, namely 5.

The value 5 is realised by the Baby Monster and by some unitary groups. The diameter of the intersection graph of a simple unitary group is 3, 4 or 5, and all values occur; we do not currently know which groups have which diameters.

Posted in doing mathematics, exposition | Tagged , , , , , , , , | Leave a comment

A paradox, and where it led

What is the difference between a contradiction and a paradox?

A contradiction is a dead end, a sign that the road leads nowhere and you should turn back and take the other road. A paradox, however, is an invitation to think creatively about the situation; you stand to gain a lot.

So here are a couple of paradoxes. The first I only realised recently, but it will be relevant to my story later. Here are two views of Aristotle, both of which have been very influential in Western thought.

  • We observe that in the world, every effect has a cause. Aristotle thought that this created a backward chain of causes, which could not go on for ever, and therefore there must be a First Cause or Prime Mover somewhere outside our universe to set the whole thing into motion.
  • Though Aristotle denied the existence of actual infinity, he was happy with potential infinity (such as the passage from one natural number to the next in induction); also, he believed that human souls have an immortal part.

I have always regarded the first argument as unworthy of a philosopher. I see no problem with infinite backward chains of causation in principle; even if we deny them, it by no means follows that there can be only one First Cause. Why not many?

But there is an asymmetry between the two parts. If there is a Prime Mover to start everything off, why not a Prime Eater at the end, like the eagle in Carlos Castaneda’s philosophy? Doron Zeilberger claims that there is a largest natural number, and it is impossible to refute that.

But there is a place where mathematicians have embraced that asymmetry (look away now, Doron); that is in set theory, where everything is built from the empty set but there is no end to how far the sets go.

But before following that, it is time for the second paradox. One of the “portals” of first-order model theory is the Löwenheim–Skolem theorem, which says that if a first-order theory in a countable language has an infinite model, then it has a countable model. Now, the Zermelo–Fraenkel axioms for set theory are first-order in a countable language (with a single binary relation symbol ∈ for membership). So, if they are consistent (as most mathematicians would assume, although Gödel showed us that they cannot prove their own consistency), then there is a countable model of ZF.

The paradox, the famous Skolem paradox, arises because there is a theorem of ZF asserting the existence of uncountable sets.

I discussed the resolution of the paradox in my book Sets, Logic and Categories, and am not intending to repeat that here. Rather, this is to discuss the properties of countable models.

The membership relation is not symmetric, so it defines a directed graph structure on the universe of the model. But it has the remarkable property that if we ignore the directions, and consider the undirected graph, it is isomorphic to the Erdős–Rényi random graph (also known as the Rado graph). I have discussed this graph in a series of posts beginning here. I have known this for so long that I cannot remember when I first learned it.

The proof is very simple. Clearly it relies on the axioms of ZF, but not many of them are actually used. Apart from the Empty Set, Union and Pairing axioms (which are needed to guarantee that there is something), only one axiom is used, the Axiom of Foundation. So, for example, the Axiom of Choice is not used; the Axiom of Infinity is not used. This has historical significance. There is a standard model of hereditarily finite set theory (in which every set is finite, as are all its subsets, and so on): the sets are natural numbers, and x is in y if and only if 2x occurs in the base 2 expansion of y. If we undirect this relation, we obtain precisely Rado’s original definition of his graph.

The Axiom of Foundation is the one I alluded to above, which destroys the symmetry of up and down in set theory. Its statement is somewhat technical, but it has the effect of forbidding infinite descending chains under the membership relation (although this is not a theorem of first-order ZF, but rather a metatheorem). It can be proved in ZF (using the Axiom of Foundation) that there are no finite cycles under the membership relation; in particular, no set can be a member of itself; and there do not exist two sets, each a member of the other.

So I wondered what sort of graphs would arise if we negate the Axiom of Foundation, for example by replacing it by some version of the Anti-Foundation Axiom proposed by Peter Aczel. The resulting theory is known as ZFA. This is discussed in detail in the book Vicious Circles by John Barwise and Lawrence Moss, who give a number of applications of the theory.

Some fairly large number of years ago, I tried to interest a PhD student in this problem, but the student did not take it up. Then, much more recently, Bea Adam-Day, a St Andrews student doing the undergraduate Masters degree, got interested in the question. I hope I am doing justice to Bea when I say that a combination of the beauty of the ideas around the random graph and the excitement of proving new mathematical results together seduced her into continuing her studies; she is now a PhD student at the University of Leeds.

We proved several results. One is the fact that, if you keep loops and double edges but delete single edges from the digraph, you get the “random loopy graph” (the random graph with loops at a random set of vertices); whereas other reducts are more complicated and do not have countably categorical theories. I discussed the results here.

After a long and complicated story, the paper was finally published on-line yesterday; you can read it here (it is open access).

But happily the story goes on. There were several questions we were unable to answer. At Leeds, Bea has got her fellow students John Howe, Rosario Mennuni interested in the question, and they have a paper on the arXiv.

Posted in doing mathematics, exposition | Tagged , , | Leave a comment

Between Fermat and Mersenne

The following problem came up in something I was doing recently. I have no idea how difficult it is – it looks hard to me – but I would be glad to hear from anyone who knows more than I do.

As is well known, a Mersenne prime is one of the form 2n−1, and a Fermat prime is one of the form 2n+1. In each case, only finitely many examples are known, but it is thought that there may be infinitely many Mersenne primes but only finitely many Fermat primes.

If we relax “prime” to “prime power”, we get Catalan’s equation, which only gives us one new solution: 23+1 = 32.

But what I want is the following. For which positive integers n is it the case that each of 2n−1 and 2n+1 is the product of at most two distinct primes?

It happens that, in many small cases, if one of these numbers is prime, the other is a product of two primes; but this may be just the law of small numbers. But there are other cases. For example,

211−1 = 23×89,   211+1 = 3×683.

As usual, thoughts welcome.

Posted in open problems | Tagged , , | 15 Comments

Perfectness of the power graph

The power graph of a group is the graph whose vertices are the group elements (sometimes the identity is excluded but it doesn’t matter here), in which x and y are joined if one is a power of the other.

A finite graph is perfect if every induced subgraph has clique number equal to chromatic number. This is a well-studied class of graphs.

Theorem The power graph of a finite group is perfect.

In fact, much more is true. The result holds in any power-associative magma, that is, set with a binary operation in which powers of any element satisfy the associative law, and in particular, in any semigroup. Moreover, finiteness is not necessary, if we adopt the convention that an infinite graph is perfect if every finite induced subgraph is perfect.

The proof is not hard, but contains a small subtlety, so I will give it in full here.

A binary relation → is a partial preorder if it is reflexive and transitive. One of the first pieces of mathematics you might do when looking at binary relations is the analysis of partial preorders. Define a relation ≡ by the rule that x ≡ y if x → y and y → x. Then ≡ is an equivalence relation. Now define a relation on the set of equivalence classes by the rule that [x] ≤ [y] if u → v for some (and hence every) u∈[x] and v∈[y]. Then ≤ is a partial order on the set of equivalence classes.

Conversely, given an equivalence relation and a partial order on the set of equivalence classes, we can reconstruct uniquely the partial preorder on the original set.

As a paranthetical remark, this can be expressed in the language of species by saying that partial preorders are obtained from partial orders by substituting sets.

The comparability graph of a partial preorder → is the undirected graph in which distinct points x and y are joined if either x → y or y → x.

Now let G be a group. (As before, a power-associative magma would suffice.) We define the directed power graph on G by the rule that x → y if y is a power of x. Since x1 = x and (xm)n = xmn, this is a partial preorder whose comparability graph is the power graph of G.

So the general result from which all follows is:

Theorem The comparability graph of a partial preorder is perfect.

First we observe that the class of comparability graphs of partial preorders is closed under taking induced subgraphs, so it suffices to prove that such a graph has chromatic number equal to clique number.

Here is the proof. In the case of a partial order, this is the easy part of Dilworth’s Theorem, and is proved as follows. Take a finite partial order. Then a clique in the comparability graph is a chain in the order. Let k be the maximal size of a chain. We need to find a k-colouring of the graph. So take the set of minimal elements in the partial order. They are pairwise incomparable, so we can give them the first colour. Then remove these elements and proceed inductively. We only need k colours since the obstruction to this would be a chain of length greater than k.

To go from partial orders to partial preorders, it is convenient to use the weak perfect graph theorem, proved by Lovász:

Theorem The complement of a perfect graph is perfect.

So let Γ be the complement of the comparability graph of a partial preorder → on x. The equivalence classes of the relation ≡ are sets of vertices which pairwise have the same neighbours, and in particular are not joined in Γ. Factor out ≡; that is, shrink each equivalence class to a single vertex (there is no anbiguity about the adjacency relation in the reduced graph). This is the complement of the comparability graph of the partial order ≤, and so is perfect. Suppose that its clique number and chromatic number are equal to k.

I claim that we can blow up each vertex of the reduced graph to an equivalence class and reconstruct Γ without changing the clique number and chromatic number. Consider the process of “cloning” a single vertex v, creating a new vertex v* with the same neighbours as v. Since v and v* are nonadjacent, we do not create a larger clique; and since they have the same neighbours, we can give v* the same colour as v. A number of steps of this kind finish the proof.

The argument can be done without going via the complement, but is rather messier since the “blowing-up” process does not preserve clique and chromatic numbers in the original graph.

I will conclude with an open problem. There are two other graphs that are similarly defined on a group G (I will restrict to groups here, since I have no idea what is possible in more general cases):

  • the enhanced power graph, in which x and y are joined if they are both powers of an element z;
  • the commuting graph, in which x and y are joined if xy = yx.

The power graph is a spanning subgraph of the enhanced power graph, which is itself a spanning subgraph of the commuting graph.

Neither of these two graphs is perfect in general. For the commuting graph, take the symmetric group of degree 5, and consider the five transpositions (1,2), (3,4), (5,1), (2,3), (4,5). The induced subgraph is a 5-cycle, which has clique number 2 and chromatic number 3. For the enhanced power graph, replace transpositions by cycles of pairwise coprime length (in a larger symmetric group) with the same intersection pattern, noting that elements of coprime orders in a group commute if and only if they are both powers of a single element, their product.)

Problem For which groups is the enhanced power graph perfect? For which groups is the commuting graph perfect?

In my paper with Ghodratallah Aalipour, Saieed Akbari, Reza Nikandish and Farzad Shaveisi, we determined the groups in which either the enhanced power graph or the commuting graph is equal to the power graph; they obviously satisfy the condition. What other groups can occur?

Posted in doing mathematics, exposition | Tagged , , , , | 1 Comment

Permanence of open access publication

Both email accounts I use have rather zealous spam filters, and from time to time I have to check what they have filtered out. (An excuse for slow response to email?) The last time I looked I found a copy of the International Mathematical Union’s Bulletin. Included in it, along with the sad news of Vaughan Jones’ death, I found a discussion and link to a paper on the arXiv documenting the authors’ research on the disappearance of open access journals over the last two decades.

Back in pre-Internet days, libraries subscribed to journals, and you could go to the library and read a back issue (except that, if it was very old, you might have to order it from the stacks). Sometimes, scandalously, the library would pulp its old journals on the grounds that it could no longer afford the cost of storing them. But there was also the option of Inter-Library Loan: if your library didn’t hold the journal issue you were after, you could order it from another library (at a small charge, which the University would pay).

Now all is different. The existence of the Internet encourages small groups to start up journals. Usually these are run by volunteers. (Even the big publishers get the editorial and refereeing work done by volunteers, so this is not such a big difference.) Also, they are free, both to authors and to readers: “diamond open access”.

So the study in question, by Mikael Laakso, Lisa Matthias and Najko Jahn, asked what happens if you need to refer to a paper in one of these open access journals and find that the journal is no longer in operation. This might happen for many reasons: someone dies, retires or loses interest; something similar happens to an organisation; a change in technology has made the papers unreadable or unfindable; and so on. Your local library will not have hard copy, and maybe Google is unable to find the paper from the incomplete information you hold.

Clearly this is a serious problem.

One of the first organisations to address this problem had the acronym LOCKSS (“Lots Of Copies Keep Stuff Safe”). Now there are several others, all operating a little differently. The idea is that publishers agree that they can keep copies of the papers; if the copyright lapses for any reason, they can make their copies freely available. But of course this costs money. Small groups of volunteers running a journal may not be able to afford the cost; and, in any case, they are more focussed on getting papers published than on their long-term security.

By various ingenious methods, including using the Wayback Machine (which provides snapshots of the internet in former times), Google searches, and information from friends and colleagues, they were able to identify 176 open access journals that have disappeared in the last two decades. The dataset is here. They point to the urgency of the problem and encourage use of the data for further research. According to the IMU, two of the 176 journals are in mathematics. (I have not checked this.)

Actually I think there are wider issues.

First, a policy issue. It seems reasonable to assume, though I have no data on this, that open access journals are more likely to disappear than subscription journals. While the papers are behind a paywall, they are a source of income for the publisher, who is thus likely to ensure their continued existence. They may be less inclined to support something which brings them no further income. On the other hand, funders are putting very strong pressure on us (for good reason) to publish in open access journals. Our research is publicly funded, so the results arguably belong to the public, who should have free access to them.

Second, not every document worth preserving is published in a journal, open access or otherwise. The pressure of research assessment is forcing us to submit our papers to higher-prestige journals (since our administrators find it easier to judge their quality by looking at the journal impact factor). Thus, even good papers get rejected, and after a couple of rejections the author may get discouraged and the paper languish unseen. Nowadays we are likely to put the preprint on the arXiv, but many of us have various papers from earlier times which may still be of interest, either on personal web pages or in our filing cabinets.

I have many such files. A few of them have seen the light of day, mostly on the arXiv, such as this one, a paper I wrote in around 1980 showing that most Latin squares and Steiner triple systems have trivial automorphism group (I was scooped by Laci Babai but later he encouraged me to make my version public); this one, on some group invariants related to permutation bases; this one with Sam Tarzi, on the outer automorphism group of the automorphism group of the random m-coloured countable complete graph (no, that is not a typo). As well I have several other papers on the arXiv which were never published because they were rejected by journals, such as this and this. And elsewhere there is this essay I wrote for John Cannon when he was developing Magma.

Posted in publishing | Tagged , , , | 2 Comments

Combinatorial Theory

I learned yesterday of a new free and open-access journal, Combinatorial Theory, owned by its editorial board. There is a temporary web page here, on which the editorial board (including some familiar names) is listed. This journal joins a list headed by the Electronic Journal of Combinatorics (more than a quarter of a century old), and including also the Australasian Journal of Combinatorics and Algebraic Combinatorics, along with many in other fields.

More information can be found on the FPSAC website here. This is a letter from Victor Reiner announcing that the new journal is to be regarded as the successor of the Elsevier publication Journal of Combinatorial Theory (A). Since I am in favour of free open-access journals owned by the editorial board, I welcome the new journal. On the other hand, I don’t want to disparage JCT(A), but merely note that the last couple of papers I published there have had almost no citations (9 and 6 respectively, according to Google Scholar which is not prone to undercounting).

Paying page charges (sorry, APCs) to major publishers with large profit margins has always seemed to me uncomfortably close to vanity publishing, where authors desperate to see their work in print are prepared to pay unscrupulous publishers. Of course, it is very difficult to occupy the high moral ground now, when publishers offer universities package deals including open-access publishing (but you can be sure that somebody is paying them, money which might be better spent supporting young scholars starting out).

Posted in publishing | Tagged , , | 3 Comments

The Fitting subgroup

I have talked a bit about the Frattini subgroup. Time for its big brother.

The definition of the Fitting subgroup F(G) of a finite group G is the unique maximal normal nilpotent subgroup of G. As such, of course, it contains the Frattini subgroup Φ(G). (I showed here the Frattini argument used to prove its nilpotence.)

But wait a minute, that definition makes no sense until you have proved that the object in question exists. I learned this proof as a student; I can remember that it seemed to me to be more complicated than you would expect, but I cannot remember how it went.

So here is a simple proof, using nothing more than Sylow’s theorem. Since Sylow’s theorem is the most important theorem about finite groups, this is entirely fitting.

We need also the fact that a finite group is nilpotent if and only if it has a unique Sylow p-subgroup for each prime p. This is the same property I used for the Frattini subgroup. You can, if you wish, use it as a definition of nilpotence for finite groups. In the end you don’t escape the work, since this won’t do for infinite groups, so you have to come to terms with central series. But it will do as a working definition here.

The key lemma is the following:

If A and B are normal nilpotent subgroups of G, then AB is a normal nilpotent subgroup of G.

Given this, it is clear that the product of all the normal nilpotent subgroups is the required unique maximal one.

So let A and B be as given. It is elementary that AB is a normal subgroup of G. Also, |AB| = |A|.|B|/|AB|.

Choose a prime p, and let R be a Sylow p-subgroup of AB. By Sylow’s theorem, R is contained in a Sylow p-subgroup P of A, and in a Sylow p-subgroup Q of B. Moreover, PQ = R, since there is no larger p-subgroup in AB.

Now P is the unique Sylow p-subgroup of A, and so is characteristic in A, and thus normal in G. Similarly Q is normal in G. So PQ is a normal subgroup of G, and its order is |P|.|Q|/|PQ|. Comparing the equations for |AB| and |PQ|, we see that the latter is the p-part of the former; so PQ is a normal (and hence unique) Sylow p-subgroup of AB.

Since this holds for all primes p, AB is nilpotent.

Posted in exposition | Tagged , , , | 3 Comments

Groups and graphs

Two new preprints have appeared on the arXiv (2008.09291 and 2009.02884), about which I would like to say something. One is by Saul Freedman, the other by him and two co-authors (his PhD supervisors).

The intersection graph of a group G is the graph whose vertices are the proper non-trivial subgroups of G, two vertices joined if they have non-trivial intersection. (Here, as usual, the trivial subgroup of any group is the subgroup whose only element is the identity of the group. For obvious reasons we exclude the cyclic groups of prime order.) The history of this graph is explained in the preprint on the arXiv. It was defined by Csákány and Pollák in 1964; they determined the non-simple groups for which it is disconnected, and proved that if it is connected (for non-simple G), then its diameter is at most 4.

What about simple groups?

In 2010, Shen proved that the the intersection graph is connected and asked for an upper bound on the diameter. In the same year Herzog, Longobardi and Maj gave a bound of 64. This was reduced to 28 by Ma in 2016. Meanwhile Shasavari and Khosravi gave a lower boud of 3.

Now Saul has reduced the upper bound to 5; shown that this is best possible (the intersection graph of the Baby Monster has diameter 5, the distance 5 realised by two subgroups of order 47), and shown moreover that any other simple group whose intersection graph has diameter 5 must be a simple unitary group of odd prime degree. There exist unitary groups where the diameter is 5, and others where it is 4; we do not currenly have a complete classification.

So let me interpolate a question here which is relevant to this and may be interesting to finite geometers. The classical unital U(q), for a prime power q, has q3+1 points, and the unitary group PGU(3,q) acts on it 2-transitively. This group has a cyclic subgroup of order q2q+1, which acts with q+1 regular orbits. Is the following true? If O is one of these orbits, and g is any element of PGU(3,q), then O and Og have non-empty intersection.

The other paper turns to territory more familiar to me. Consider the following graphs whose vertices are the non-identity elements of a group G:

  • the power graph, with x joined to y if one is a power of the other;
  • the enhanced power graph, with x joined to y if both are powers of an element z;
  • the commuting graph, with x joined to y if xy = yx;
  • the non-generating graph, with x joined to y if x and y do not generate G;
  • the complete graph, with all pairs adjacent.

Each graph is a spanning subgraph of the following one, except possibly for the third and fourth, for which this holds if G is non-abelian.

When can it happen that two consecutive graphs on this list coincide? For the first and second, and for the second and third, this question was answered in a paper I wrote with Ghodratollah Aalipour, Saieed Akbari, Reza Nikandish, and Farzad Shaveisi in 2017, using classical results of Frobenius, Burnside, Zassenhaus, and Gruenberg and Kegel, among others. For non-abelian G, the third and fourth are equal if and only if G is minimal non-abelian (all proper subgroups abelian); these groups were classified back in 1903 by Miller and Moreno. The last pair are equal if and only if G cannot be generated by two elements.

The next question one might ask about this hierarchy (assuming G non-abelian) is whether successive differences are connected, and what can be said about the diameter of connected components. For the last pair, the difference is the generating graph of the group, in which two vertices are joined if together they generate the group. This graph has received a lot of attention, not least from Scott Harper (a St Andrews graduate); a recent theorem of his with Tim Burness and Robert Guralnick shows that if G is finite and all proper quotients of G are cyclic, then the generating graph has diameter 2 (arXiv 2006.01421).

The next difference is the so-called non-generating, non-commuting graph; this is the graph considered in Saul’s other preprint. I won’t describe here the results (which chiefly concern connectedness and diameter in the case where G is nilpotent, though there is much more in Saul’s thesis), since I want to add some further comments to the general set-up.

Firstly, after examining connectedness and diameter, one could ask questions such as Hamiltonicity, clique size, chromatic number, domination number, and so forth. However, for the first two “difference graphs”, even the question of connectedness is open. (The connectedness of the commuting graph has been much studied, but this is the edge-union of the first three of the difference graphs.)

A second comment is that, if G is non-abelian and 2-generated, then we have partitioned the complete graph on the non-identity elements of G into (at most) five parts. What happens if we run the Weisfeiler–Leman algorithm on this partition, to find the coarsest coherent configuration refining it?

For the final comment, note that in the enhanced power graph, two vertices are joined if and only if they generate a cyclic group; in the commuting graph, if and only if they generate an abelian group; and in the non-generating graph, if and only if they generate a proper subgroup. This inevitably suggests many further graphs, defined by imposing an appropriate condition on the subgroup generated by the two elements, either intrinsic (e.g. nilpotent or soluble) or with relation to the whole group. This opens a large number of problems. Are any of them interesting? Perhaps the best way to find out is to study them and see!

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

On the Frattini subgroup

I wrote earlier about the Frattini subgroup of a group. It can be defined in either of two ways (as the set of non-generators of a group, the elements which can be dropped from any generating set containing them; or as the intersection of all the maximal subgroups), and the proof that it is nilpotent is a good illustration of the Frattini argument.

As you will see from the preceding post, I have been thinking about the Frattini subgroup recently. What I propose to do here is to tell you something about it which I don’t recall meeting when I was a student (and so perhaps you didn’t either), and also to throw some light on two other things: how research is done, and how mathematics was written a century ago.

In the course of what I was doing, I began to wonder whether the Frattini subgroup of the direct product G×H is the direct product of the Frattini subgroups of G and H. GAP confirmed that this was so in a couple of examples. In the past, I would have had to go to the library and look through books, and probably lug huge volumes of Mathematical Reviews down from the shelves. Now I can’t go to the library, but I do have the internet. So I googled the question. I found a fairly recent paper determining exactly when this holds, for arbitrary (possibly infinite) direct products of arbitrary (possibly infinite) groups. In the bibliography was a paper by G. A. Miller from 1915 which, it was claimed, proved the result for finite direct products of finite groups.

The paper was in the Transactions of the American Mathematical Society, long enough ago that it is freely available, so I downloaded a copy. It is only seven pages long, but does not contain a single theorem; it just consists of text, with a few important points italicised. A quick glance didn’t lead me to the theorem quoted, although he deals with the Frattini subgroup of a Sylow subgroup of the symmetric group, so has to handle direct products.

This is how mathematics was done in those days. I think the change in style was not too abrupt; in Burnside’s book, he often rambles on for several pages, but at least he states a theorem at the end of his ramblings. I think that today we would not allow our students to write like that, and journals would not accept our papers if we did it ourselves.

So I had to prove it for myself, to be sure it was right. I will also explain why finiteness of the groups is needed.

I will use the definition as intersection of maximal subgroups, though Miller uses the other definition of the Frattini subgroup.

Consider G×H. If A is a maximal subgroup of G, then A×H is a maximal subgroup of G×H; the intersection of all these is Φ(GH. Similarly the other way around. So certainly Φ(G)×Φ(H) is an intersection of some maximal subgroups, so contains Φ(G×H). We have to show that intersecting this with other maximal subgroups does not make it any smaller.

So we have to think about arbitrary maximal subgroups of a direct product G×H. In fact, it is known (I did learn this as a student) that all subgroups of the direct product are produced in the following way. Let A and C be subgroups of G, with A a normal subgroup of C; and similarly B and D in H. Suppose that the factor groups C/A and D/B are isomorphic; let α be an isomorphism between them. Now consider the set of all pairs (g,h) in G×H such that gC, hD, and (Ag)α = Bh. This is a subgroup, and every subgroup has this form.

It is easy to see that, in order for the subgroup in the previous paragraph to be maximal, we have to have C = G, D = H, and the isomorphic quotients G/A and H/B simple.

Now we can see why the formula for the Frattini subgroup of a direct product can fail for infinite groups. Let G be an infinite simple group which has no maximal subgroups. Then Φ(G) = G. But G×G has a diagonal subgroup consisting of all (g,gα) for gG, which is maximal; so Φ(G×G) is not equal to G×G.

But the Frattini subgroup of a finite simple group G is trivial; for every finite group has a maximal subgroup, so its Frattini subgroup is proper, and it is normal, so is trivial if G is simple.

Thus, for a maximal subgroup of the type we are considering, A contains Φ(G) and B contains Φ(H), so our maximal subgroup contains Φ(G)×Φ(H), as required.

Posted in doing mathematics, exposition | Tagged , , | 4 Comments