An ABC conjecture proved

Not THE famous ABC conjecture, but a conjecture of mine with Mohammed Aljohani and John Bamberg.

A simple counting argument shows that, in any vertex-transitive graph, the product of the clique number and the independence number is at most the number of vertices.

This has extra significance because non-trivial examples meeting the bound are the obstructions to a permutation group property which we call separation arising in the theory of synchronizing automata.

This puts strong restrictions on separating permutation groups, which we assume must be transitive:

  • they must be primitive (else the disjoinot union of complete graphs on the blocks has product of clique and independence number equal to number of vertices);
  • they must be basic (else they preserve a Hamming graph, which has this property);
  • and so on …

An interesting test case is formed by the symmetric groups Sn acting on the set of k-subsets of {1,…n}. (Without loss of generality we may assume that kn/2.) Any graph admitting this group is defined by a subset L of {0,…k−1}, with two k-sets joined if their intersection has size in L.

Our conjecture asserted that there is a function F such that, if n ≥ F(k) and this graph attains the bound (clique number times independence number equals number of vertices), then (up to complementation) L = {0,…,t−1} for some t; a maximum clique is the set of blocks of a Steiner system S(t,k,n), and a maximum independence set is of Erdős–Ko–Rado type, all k-sets containing a fixed t-set.

This has now been proved in an arXiv preprint by Danila Cherkashin and Yakov Shubin (in his email to me, Danila attributed the proof to Yakov). The proof is remarkably short, based on the celebrated Deza–Erdős–Frankl theorem.

This result then plugs in to the famous theorem of Peter Keevash which says that there is a function G such that, if n ≥ G(k,t), the required Steiner system exists if and only if the well-known divisibility conditions for it are satisfied.

So, asymptotically, a good answer to the question of which groups of this type are separating.

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

Rules for retirement

I am now retired, and nearly 80. My brain does not work at the same clock speed that it used to, and I am no longer paid for things which were part of the job sucuh as refereeing, conference attendance and collaboration.

On the other hand, I have seen a big upsurge in the number of such requests. So for my own sanity, I have had to make some rules. These are not hard-and-fast rules; they are guidelines which can be overruled by special circumstances.

Refereeing and reviewing

Incidentally, people used to say “refereeing”; now more and more it is “reviewing”, which suggests to me going over something you have seen before. Does anyone know why?

I no longer have funds for page charges, so I feel no obligation to referee papers for commercial journals which have such charges. Also, as I said, I can no longer count refereeing as part of the job for which I am paid. So I feel entitled to turn down refereeing requests.

On the other hand, since I strongly support diamond open access journals, I will continue refereeing for these.

Also, my rule can be overridden by a request involving a commemorative or memorial issue for a friend.

Incidentally, I think there are cases where editors could take more responsibility. I was recently asked to referee a paper whose title began with a piece of notation which was only defined for the first time in the paper. This breaks two rules I learned long ago: a title should communicate what the paper is about; and a title should not begin with notation. The editor should have rejected the paper straight away. The author showed no respect to readers and consequently had earned no respect.

Conferences

There are so many interesting conferences these days. But I am coming to realise that there are beautiful parts of the world, such as Patagonia or Vietnam, which I am never going to see. I very much dislike airports which make me extremely nervous, and flying is becoming more difficult and dangerous. So I am trying to cut down on long-distance travel and only attend relatively nearby conferences.

On the other hand, we now have the facility for on-line or hybrid conferences, and I am quite happy with that.

However, the drawback with an on-line talk is that you get very little audience feedback and usually you have no idea who you are talking to. So I have decided to set a fee for on-line conference talks. You should send me, in advance of the talk, one or a few nice pictures of your university, town, or district, so that I can have some picture in my mind of where my talk is.

Collaboration

Collaboration is the life-blood of mathematics research. Over my career, it has enormously increased, so that single-author papers are now comparatively rare. This is a wonderful development. I intend to continue collaborating, to the best of my ability. But I am in the position of having a huge volume of collaborators at present. So, reluctantly, I have to introduce a rule.

If you send me a paper that you want me to collaborate on, please don’t start the file with hundreds of lines inputting various, probably incompatible, packages and personal macros. They may make your life easier, but they make mine more difficult, since I have to keep going back to see what these macros actually do. For one example, my LaTeX-aware editor understands “\begin{enumerate}” and “\end{enumerate}”, but if for your own convenience you redefine these as, say, “\be” and “\ee”, my editor no longer recognises them, and distractingly marks things are errors.

On the other hand, I am happy with transparent macros such as defining “\Aut” to mean “\mathop{\mathrm{Aut}}\nolimits”.

This is at its most extreme in editing a book with contributions from several authors. In one case I had to deal with, loading different authors’ packages in one author caused one to be overwritten by the other so that it had the wrong effect, and in the other order caused an error which simply stopped the compilation.

Please keep it simple!

I used to spend a long time trying to make my preprints look as good as possible. When I realised that all this work was wasted if the paper was published in a journal with its own style file, I decided that the less explicit formatting I did myself, the better.

Finally, to my many valued collaborators: I beg your patience, please bear with me. I will try to get to our joint work when I can.

Posted in Uncategorized | Tagged , , , | 4 Comments

Three easy proofs of Pythagoras’ Theorem

Take a right-angled triangle with hypotenuse c and the other two sides a and b. Pythagoras’ Theorem tells us that c2 = a2+b2.

Triangle

Let the area of the triangle be A. We know that A = ab/2 (since an a×b rectangle is cut into two such triangles by a diagonal).

Here are three simple proofs, not in the least original. All use the same diagram, constructed as follows. Take a square with side a+b. At each corner, measure a distance a along the side in the clockwise direction and b along the side in the anticlockwise direction. Complete these two segments to a rectangle, and draw the diagonal not containing the corner where you began.

Squares

You will see, in addition to the original square, a tilted square with side c, and an inner small square with side ab.

First proof: The outer square is made up of the tilted square and four copies of the triangle. So (a+b)2 = c2+4A, which on simplifying gives c2 = a2+b2.

Second proof: The tilted sqiare is made up of the inner sauqre and four copies of the triangle. So c2 = (ab)2+4A, which on simplifying gives c2 = a2+b2.

Third proof: These two proofs are in a sense dual to each other, so here is a “self-dual” proof, with the added advantage that it is not necessary to know the value of A. The area of the tilted triangle is the average of the areas of the inner and outer squares, since the difference in either direction is four triangles. So c2 = ½[(a+b)2+(ab)2], which on simplifying gives c2 = a2+b2.
These simple proofs of a not-so-simple theorem call for a couple of philosophical remarks.

  • Why three proofs, when one is sufficient to establish the result? Not all of us are perfect logicians; and for the rest of us, three proofs are more convincing than one. “What I tell you three times is true”, as the Bellman said.
  • As with any proof using a diagram, certain things are obvious from the diagram but a formal proof lies rather deeper. For example, why do congruent triangles have the same area? This depends on the fact that Euclidean transformations (translations, rotations, reflections, etc.) preserve area; so, eventually, it is a question of group theory amd measure theory.
Posted in Uncategorized | Tagged , , | 6 Comments

A real-world problem

Imagine you are in the following situation.

You are the foreign minister of your country. You are in New York for a meeting of the General Assembly of the United Nations.

A powerful enemy has been deploying troops on the borders of your country. The “experts” say that there are no plans to invade you, this is just to put pressure on you (invasion would be contrary to the United Nations charter), but if they did invade, your country would last only a few days.

But you know, or suspect, that the enemy leader’s goal is that your country will cease to exist, and that its land, people, resources and culture will become part of his empire. Also, he will have no qualms about spilling his people’s blood to achieve this.

The day before you are due to address the General Assembly, US intelligence tells you that the invasion will occur within the next 48 hours.

You know that words can matter, and that if you do not choose the right words, the consequences will be the deaths of some of your citizens (both soldiers and civilians) and possibly the disappearance of your country. It is very important that when you speak to the delegates of thhe 193 nations on earth, you persuade them not to turn away but to engage.

What do you say?

If you want to know what the Foreign Minister actually said, you should get hold of a copy of the new book Words of Defiance by Bjorn Berge, published by Biteback Publishing of London.

On second thoughts, I will repeat that sentence without the conditional.

You should get hold of a copy of the new book Words of Defiance by Bjorn Berge, published by Biteback Publishing of London.

Posted in Uncategorized | Tagged , | Leave a comment

Deep isoclinism

Graphs and groups, in my view, are two subjects engaged in a wide-ranging dialogue at present. Graphs can be used to describe interesting classes of groups, and groups to construct interesting graphs.

But I am delighted that recently, in a paper published last year in the International Journal of Group Theory, a new concept in group theory has come up, based on a paper on a particular graph defined on groups, the so-called “deep commuting graph”.

The deep commuting graph saw the light in my paper with Bojan Kuzma in the Journal of Graph Theory. Two vertices are joined if their inverse images in any central extension of the group commute. (A central extension of G is a group H with a central subgroup Z such that H/Z is isomorphic to G.) The deep commuting graph is contained in the commuting graph (as a spanning subgraph) and contains the enhanced power graph.

Central to its study is the notion of isoclinism of groups, invented by Philip Hall. Two groups are isoclinic if their commutator structures are isomorphic, in a certain sense. Commutation, the map taking (x,y) to x−1y−1xy, is a map from G×G to G. But multiplying its arguments by central elements doesn’t change the value, and it maps into the derived subgroup G‘ generated by all commutators. So it can be thought of as a map from (G/Z(G))2 to G‘. Then an isoclinism from G to H is a pair of isomorphisms from G/Z(G) to H/Z(H) and from G‘ to H‘ which “intertwine” the commutation maps in the obvious way.

For example, the dihedral and quaternion groups of order 8 are isoclinic. The central quotients are the Klein group of order 4, and the derived groups the cyclic group of order 2.

As an exercise, show that isoclinic groups of the same order have isomorphic commuting graphs. (The commuting graph is a sort of “kernel” of the commutation map.)

Bojan and I found that many rather esoteric parts of group theory get involved in the study: the Schur and Bogomolov multipliers, Schur covers, and so on.

Anyway, to the business in hand: Bahram Arvin, Behrouz Edalatzadeh and Ali Reza Salemkar introduce a new concept, which they call “deep isoclinism”. Roughly speaking, it bears the same relation to the deep commuting graph as isoclinism does to the commuting graph.

Two groups are deeply isoclinic if they have Schur covers which are isoclinic. Facts about Schur covers demonstrate that this notion is independent of the choice of Schur covers in the definition. (Similarly, the definition of the deep commuting graph can be simplified: it is the projection of the commuting graph in a Schur cover, and again the definition is independent of the choice of Schur cover.)

The notion differs curiously from ordinary isoclinism in being much more stringent. Two abelian groups of the same order are deep isoclinic if and only if they are isomorphic. Also, a group is deep isoclinic to the trivial group if and only if it is cyclic. Isoclinism and deep isoclinism coincide for a pair of groups if and only if the Bogomolov multiplier of each is equal to its Schur multiplier.

Just as isoclinic groups of the same order have isomorphic commuting graphs, so deep isoclinic groups of the same order have isomorphic deep commuting graphs. The converse of the first assertion is false (examples of order 64 were found by Eamonn O’Brien), but for the second assertion it is not known if it holds or not.

It also gave me great pleasure that the International Journal of Group Theory is back on-line, though of course we don’t know whether this will continue, given the state of the war. Check it out at ijgt.ui.ac.ir. Check it out: it is diamond open access, you can read everything!

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

The Latin square

A few years ago, R. A. Fisher (who has been derscribed as “the greatest Darwinist since Darwin”, and as “the founder of modern statistics”) fell victim to one of the waves created by the Black Lives Matter campaign, and a window commemorating him in his Cambridge college was removed (undoubtedly without due process: just two days elapsed between the proposal and the fait accompli). I wrote about this, and there were quite a few comments: see here.

Now I don’t have to defend Fisher any more, since A.W.F. Edwards has done it so much better in a book, The Latin Square, published by Cam Rivers Publishing last year. (The title was given because the window illustrated a Latin square which occurs on the dust-jacket of Fisher’s book The Design of Experiments.)

The book is a collection of essays written by Edwards at various times both before and after this incident. He does a good job of dispelling the misunderstandings, sharp practice and simple lies which fed the campaign to discredit Fisher.

Because of its origin, the book is somewhat repetitive. I will be briefer and just refer to the book. I say a few words about three allegations against Fisher.

1. Fisher was a racist. It is hard to see how this could be true, given that on his death the Indian Statistical Institute closed for a day as a mark of respect.

Fisher’s view, in his words:

Mankind as a whole certainly constitutes a single family, and it is an old ideal and certainly not a dead one to treat all mankind as our brethren.

Briefly, how did the allegation arise? Possibly because he objected to one statement in a UNESCO report on race in 1951:

Available scientific knowledge provides no basis for believing that the groups of mankind differ in their innate capacity for intellectual and emotional development.

As Edwards points out, this is a “null hypothesis”, a concept invented by Fisher, who was clear about the fact that a null hypothesis can never be proved but may be disproved by further research. In Fisher’s time the best verdict on it was probably “unproved”, but advances in genetics have surely disproved it now (despite the protestations of people like Stephen Jay Gould). Edwards also explains how its failure can come about simply as a result of genetic drift, without need for selection pressure. Needless to say, this statement can fall but does not take away our responsibility to treat all of the human family without prejudice.

2. Fisher was a eugenicist, in the disagreeable sense of the term in the USA and Germany. Again refuted by Fisher’s expressed view:

… anything so big as eugenic aims must be controlled by the personal choice of individuals acquainted with their own individual needs and circumstances …

Fisher was in favour of child allowances, to encourage “clever” people to have more children: not given by the State, but funded by contributions rather as occupational pensions are now. Ironically, it was William Beveridge, a fellow member of the Eugenic Society, who introduced state-funded child benefit. Imagine the storm if they were done away with now!

The source of the trouble may the phrase “elimination of defectives”, but for Fisher this means “defective genes”, not “defective individuals”, and he hoped it could be done by a combination of genetic counselling and voluntary sterilisation, although in one of his papers (misunderstood by historians) he proved that this would be a slow process.

3. Fisher’s interest in statistics and genetics was driven by his enthusiasm for eugenics. This is simply false, and in my view the real disgrace here is that historians could make this accusation without looking at either Fisher’s publications or his biography. Edwards remarked that after his degree he had the choice of a permanent position in Pearson’s laboratory or a temporary position at Rothamsted Experimental Station; he chose the latter.

I will end with two remarks arising from comments on my previous post on Fisher.

First, a good point in the other direction which needs to be addressed. As one correspondent pointed out, how would I feel if I were of a diffent “race” and had to eat every day in a hall illuminated by a Latin square constructed by a racist? Even if Fisher were not a racist (as seems to be the case), as long as he is perceived as a racist this point still has validity. But in that case, the blame falls not on Fisher but on those people who created and pushed the myth. Now myths can be very powerful; and if they are supported by Fellows of the Royal Society and former Regius Professors of History, it takes a certain amount of courage not to be affected by them.

Second, I have to reveal my own prejudices. Another commenter quoted extensively from Lancelot Hogben. I do not warm to Hogben. I was given one of his books as a school prize, and although it was a maths book I found it absolutely unreadable. Later I encountered G. H. Hardy’s account of his views (in A Mathematician’s Apology), which were that the only mathematics worth doing is useful mathematics (which according to Hardy’s view meant roughly school mathematics). Unnnervingly close to the views that Stalin’s thugs took of people like Egorov, Luzin, Cebotarev, and Bronstejn. And, incidentally, the flashpoint between Fisher and Hogben was likely to have been politics: Hogben was on the left.

Posted in books | Tagged , , | Leave a comment

ICM in Philadelphia

The latest newsletter from the International Mathematical Union urges mathematicians to attend this year’s ICM in Philadelphia. It will help our beleaguered collleagues in the USA by showing support, and the organisers guarantee our personal safety.

Well, I will not be there. But after moral pressure like that, I feel called on to justify my decision. So here goes.

  1. I believe I do a certain amount already to support mathematicians in difficult situations. If I thought that anyone would actually be helped by my presence in Philadelphia, I would do my best to go. But I don’t think that is the case.
  2. As to personal safety, the last time I was in the USA, I saw that the conductor on the train wore a gun in a holster on his hip. Later I mentioned this to an American acquaintance, who said, “That is to shoot fare dodgers”. I think he may have been joking.
  3. I have been to one ICM before. I found the standard of the talks almost uniformly poor: more on the lines of “Here’s how clever I am” rather than trying to explain things to mathematicians in other fields. The honorable exception was Vaughan Jones. This was the ICM when Ed Witten got a Fields medal, and during his talk Jones explained to us what Witten got the award for. I won’t write it here, but if you are having a coffee or beer with me sometime you can ask and I will tell you.
  4. The other positive thing about that ICM was meeting Persi Diaconis for the first time. I would have liked to have met him again and spent more time with him, but in the immense crush of people it was impossible to find anyone you were looking for.
  5. I am now retired, and have nobody whom I can ask for financial support. In any case, I expect that air fares and other costs will be much higher by then, as a result of the Israeli/American war.
  6. And last, how else can I make a token show of disapproval of the President of the United States?

Those reasons are in no particuclar order, and there are others; but I think probably the third and fifth are the ones that weighed most heavily.

Posted in Uncategorized | Tagged , | 2 Comments

Eugene Plotkin

I believe Eugene Plotkin has died. I read this on the AGTA website but I have no details.

I met him for the first and only time at Daniela Nikolova’s birthday conference in Deerfield Beach, Florida, four years ago. We got on very well. Outside of mathematics, one of his hobbies is finding beautiful “works of art” in natural stones; he sent me some of the extraordinary videos he had produced.

Posted in Uncategorized | Tagged , , | 1 Comment

Digraphs on groups

I have spent a lot of time recently thinking about graphs on groups. To recall the rules: the vertex set must be the group (in general, but not here, I allow an automorphism-invariant subset or the quotient by an automorphism-invariant equivalence relation); the graph must be defined in terms of the group structure with no arbitrary choices; so the automorphism group of the group acts as automorphisms of the graph.

There are many many examples of graphs on groups. (Some examples: power graph, enhanced power graph, intersection power graph, commuting graph, deep commuting graph, generating graph, nilpotency graph, solubility graph, …).

However, I have only three examples of directed graphs defined on groups. I would be very interested to have more; let me know your thoughts.

From any directed graph we can obtain an undirected graph, by replacing single or double arcs by undirected edges.

In this post, I will describe the examples (the power digraph, endomorphism digraph, and Engel digraph), and then describe their very different behaviour in two areas (recovering the directions from the undirected graph, and universality).

The three digraphs

First, chronologically, is the power digraph, defined by Kelarev and Quinn in 2000. There is an arc xy if y is a power of x.

Second, the endomorphism digraph: there is an arc xy if there is an endomorphism of the group mappping x to y.See arXiv 2511.15602.

And third, the Engel digraph: there is an arc xy if [y,x,x,…x]=1, where the left-normed iterated commutator has first element y and then, say, k elements x; I will say the pair (x,y) has depth k if this holds. (The order of the arc indicates that I think of commutation by x as an operator applied repeatedly to y. See arXiv 2408.03789.

I observe in arXiv 2602.00712 that the definitions of the first two digraphs can be extended to arbitrary algebras (in the sense of universal algebra). The third seems specific to groups.

Reconstructing directions

I explained how to get a graph from a digraph by ignoring directions. Can you go back? One of my first results on the power graph was to give the answer “yes, up to isomorphism” in the case of the power graph. Bubboloni and Pinzauti gave an algorithm for this reconstruction.

Here is a problem I have posed several times, though I don;t think I have written it down. Suppose we apply the algorithm of Bubboloni and Pinzauti to an arbitrary graph. There are three possibilities, each of which seems interesting.

  • The algorithm always succeeds. Thus, it produces some kind of distinguished orientation for any graph.
  • The algorithm fails if the input graph is not the power graph of a group. In this case, we have a recognition algorithm for power graphs.
  • The algorithm sometimes succeeds and sometimes fails. In this case we have a potentially interesting class of graphs, those for which it succeeds, which we might call “pseudo-power graphs”.

In the case of the endomorphism graph, there are simple examples to show that reconstruction fails. For example, let p be an odd prime, and consider that two groups of order p3 and exponent p. The undirected graphs are both complete, but the directed graphs are quite different.

The Engel graphs are perhaps the most interesting. Reconstruction is not true in general, but failure is quite rare. There are only two group orders below 100 for which non-isomorphic Engel digraphs give rise to isomorphic Engel graphs, namely 54 and 96. The situation is certainly not understood!

Universality

A class of digraphs is universal if every finite digraph can be embedded as an induced sub-digraph in some digraph in the class.

Neither power digraphs nor endomorphism digraphs form universal classes; the reasons are the same in both cases. THese digraphs are transitive (as relations); that is, if xy and yz, then xz.

As far as I know, the question whether they are universal for transitive digraphs (partial preorders) is still open.

Things are different for the Engel digraphs, which do indeed form a universal class. Indeed, a much stronger result is true. Above I defined the depth of a pair (x,y) to be the least k such that commuting y with x k times gives the identity; I will say the depth is infinite if you nevver get the identity.

Now consider a finite digraph with positive integers on the arcs. Can it be embedded in an Engel digraph in such a way that, if xy is an arc with label k, then the pair (x,y) has depth k, while if there is no arc then the depth is infinite?

There is one small obstruction. Saying that (x,y) has depth 1 simply means that x commutes with y, so it implies that (y,x) also has depth 1; so given an arc with label 1, it is necessary that the converse arc also exists and has label 1.

Now our theorem says that this is the only obstruction: labelled Engel digraphs are universal for labelled digraphs satisfying this condition.

Conclusion

I mentioned a couple of problems already. Here is another.

The power digraph and endomorphism digraph are both transitive relations. I wrote earlier about the groups for which they coincide (just cyclic groups). But now one could ask: For which groups is the Engel digraph transitive? For which of these (if any) does it coincide with the power digraph, or with the endomorphism digraph?

Posted in doing mathematics, exposition, open problems | Tagged , , , , | 3 Comments

Positive news about AI

I have been, and remain, sceptical about AI. At best, it is saiad to be good at writing programs, and finding specific facts; but it has a tendency to lie, to invent, and to tell you what it thinks you want to hear, so you have to check very carefully everything it tells you.

But I was sent a manuscript by Donald Knuth where he claims that Anthropic’s robot Claude (named after Claude Shannon, the pioneer in information theory) has gone some way to revise his previously sceptical opinion. Claude managed to solve a problem Knuth had been working on for several weeks, and in the process it documented all its attempts including its wrong turns.

THe problem was to find a decomposition of the cartesian product of three directed cycles into three Hamiltonian cycles. In other words, we take the directed graph whose vertex set is all triples (x,y,z) of elements of the integers mod n, where (x,y,z) sends arcs to (x+1.y,z). (x,y+1,z) and (x,y,z+1) (with addition mod n), and the task is to partition the 3n3 arcs into three sets, each of which is a directed cycle visiting all vertices. You might like to try it for yourself. (To be clear: Claude “solved” the problem for odd n; the case of even n is still open. I will explain the quotes around the word “solved” later.)

To be sure, this is not the Riemann hypothesis, or even a Clay problem; to my untutored eye, it looks like a problem you might give to a new graduate student. And Claude’s “solution” was a Python program which was able to produce the required decomposition for any value of n up to 101; it still required Knuth to extract an algorithm from the program and then prove that it did the job for any n. So Claude has not yet passed the Birch test devised by Yang He and his colleagues.

I won’t describe the whole adventure in detail, since Knuth has done it so much better and more knowledgeably. Look here for the latest information.

What really struck me is that the five-page document is much closer in spirit to Knuth’s mathematical novel Surreal Numbers, where two young students on a beach somewhere unearth a tablet with the rules for generating John Conway’s surreal numbers and work out the theory, complete with false starts and recoveries. It is interesting that Claude finds a promising line of attack and seems a bit reluctant to abandon it even when it doesn’t work, hoping that tinkering with it will produce the desired result.

It seems that Claude had to be reminded often to document its work, despite having been given clear instructions at the start of the exercise to do so.


Finally, Claude failed miserably to solve the problem for even n. It is known that there is no solution for n=2, but thought that solutions exist for all larger n.

Posted in doing mathematics, Uncategorized | Tagged , , , , | 3 Comments