COP26

If I could send a message to the world leaders who will soon assemble in Glasgow, it would be, in the words of a St Andrews honorary graduate:

What’ll you do now, my blue-eyed son?
What’ll you do now, my darling young one?

You have been around the world, seen and heard the evidence (the scientific data, the fires, the floods), and met the people whose lives will be most affected; now is the time to act before we “start sinking”.

In fact this song, written nearly 60 years ago, is full of topical references to the state of our world. For example, “sad forests” (acid rain), “dead oceans” (plastic pollution), “graveyard” (Covid), “black branch” (destruction of forests), “white ladder covered with water” (sea-level rise), “guns … in the hands of young children” (civil wars in Uganda and elsewhere), “wave” (from melting icecaps? or a tsunami?), “one man starve” (famine), “song of a poet” (here it is!), “young woman whose body was burning” (the next pandemic?), “man who was wounded in love/hatred” (persecution based on sexual orientation in some countries, the burden of prejudice that so many people have to carry), and so on.

Perhaps the song should be the anthem of COP26?

Posted in Uncategorized | Tagged , | 2 Comments

Joachim Neubüser

Another sad loss, with the death of Joachim Neubüser this week.

He was the driving force behind the creation of the computer algebra system GAP. Even though I worked with John Cannon, the creator of the rival system Magma, I have always used GAP rather than Magma. That for several reasons:

  • Magma is expensive, GAP is free, and I am mean. Neubüser is supposed to have said, “Nobody charges you for using Sylow’s Theorem, so nobody should charge you to compute a Sylow subgroup.”
  • It had unlimited precision integer and rational arithmetic, which was absolutely necessary for some of the computatations I did – indeed, before I started using GAP, I had written my own unlimited precision integer routines in Pascal. Along with everything else, I use GAP as a calculator.
  • It happened that I have always had GAP expertise close at hand: Leonard Soicher at QMUL, Alexander Konovalov and a number of others at St Andrews. Indeed, Leonard wrote the GRAPE package for computing with graphs and groups, which I have made huge use of.

Related to the second point, back in 2008 I spent six months in Cambridge running a programme at the Isaac Newton Institute. Jan Saxl very kindly arranged for me to be a visiting fellow at Gonville and Caius College, which gave me the use of a flat in Rose Crescent. At the time Rosemary was recovering from cancer treatment, so it was possible to come to Cambridge and spend her time in the flat apart from short walks. She had just been on an RSS panel investigating the distastrous failure of a drug trial at Northwick Park, and had invented some better designs for first-in-human drug trials. To find out how much better than the designs then in use, she needed to do a lot of boring calculations involving finding the Moore–Penrose inverses of matrices. She needed the arithmetic to be exact, so GAP was ideal for the job; I set her up with a laptop and she could do the sums. (These designs have been published but never implemented despite their advantages: they would need to be approved by a regulator, and getting approval costs serious money; drugs companies would not pay, since this would be tantamount to admitting that their existing designs are less than perfect. So it goes.)

Neubüser was much more than just the originator of GAP: a skilled computational group theorist himself, and an inspiring teacher. Indeed, when I wrote my book on permutation groups in the late 1990s, he wrote me a long account of the trials and mis-steps in the classification of transitive subgroups of low-degree symmetric groups, and permitted me to quote it in the book (which I did).

But GAP, together with his students, make up his main legacy.

Posted in history | Tagged , , | 3 Comments

Clive Sinclair

Yesterday I read the news that Clive Sinclair has died. This brought back memories of my first encounter with personal computers nearly 40 years ago.

At the time I had a demanding job and three small children, and I was not going to get something like a Commodore PET as some of my colleagues did. Instead, I started on a Sinclair ZX Spectrum in 1982 or 1983.

The machine had a laughably small amount of memory by today’s standard: 16Kb ROM, 48Kb RAM (of which nearly 7Kb were taken up by screen memory and printer buffer, leaving only 41Kb for the user). The machine had its own version of BASIC built-in, with keywords available by a single keypress. But it used a Z80 processor, a variant of the Intel 8080, so with a list of Z80 opcodes it was possible to program it in machine code, by writing a BASIC program to put the appropriate values into memory and then call the code; it was even possible to return a value.

So I used it to prove a theorem.

Suppose that you choose a sum-free set S of natural numbers by the following random procedure. Examine the natural numbers in turn. When examining n, if it happens that n = x+y where x and y have already been put into S, then obviously n cannot be in S; otherwise, choose randomly and independently with probability 1/2 whether to put n into S or not.

This is a fascinating process with many curious properties. It is very easy to see that the probability that no odd number is ever put into S is zero. (If no odd number has so far been put into S, then the next odd number to be examined will have even chance of being put into S.) What about even numbers?

Theorem In the above process, the probability of the event that S contains no even numbers is non-zero.

In fact this probability is about 0.218.

So how does the proof go? Let pn be the probability that no even number occurs when the numbers 1,…,n have been considered; then the sequence (pn) is decreasing, and the probability p that there are no even numbers in the final set is its limit. Now there is a simple upper bound for pnp, so if we can find a value of n for which pn exceeds this bound then the theorem is proved. The value of pn for n even can be computed by finding, for all sets of odd numbers in [1,…,n], the probability of obtaining this set as the initial part of S; a simple sum over 2n/2 subsets. A slow process, but just the job for the computer. With about a day’s computation on the Spectrum I was able to find a lower bound of about 0.21759 and an upper bound of about 0.21862 for this number.

At various times since, I have thought that it would be possible to get a more accurate estimate; computers today are faster, and the algorithm is easily parallelisable (the individual terms in the sum can be computed independently). But I never got round to it.

Using this, and a similar estimate for a kind of “cross-sum”, I was able to show that, if T is a complete sum-free set modulo m (that is, it is sum-free in the integers mod m, and every element of this quotient not in T is the sum of two elements in T), then the probability that a random sum-free set is contained in the union of congruence classes given by T is positive. (The class {1} modulo 2 is the first example of such a set.) So, unlike some of my favourite examples like the random graph, this measure space contains infinitely many “natural” pieces with positive probability.

And there is more. After a hectic week visiting Neil Calkin in Atlanta, during which we changed our mind several times about whether we were proving that it was zero or positive, we showed that sum-free sets in which 2 is the only even number have positive probability (though rather small). More generally, a set which belongs to T mod m (as above) with finitely many exceptions has positive probability. So there are more such pieces.

I’t like to advertise some open problems about this space, involving the density of a sum-free set (a random variable on the space).

  • Does a sum-free set have a density with probability 1?
  • Is it true that the spectrum of densities is discrete above 1/6?
  • Does it have a continuous part below 1/6?

We think that the answers to the first two questions is “yes”, but are quite uncertain about the third.

By the end of the decade, I had moved to an Atari ST, which could store information on floppy discs. I was commuting from Oxford to London by then, and got a Tandy TRS-80 for writing on the train; I had to write a low-level program to connect it to the Atari, which involved learning about DTR and CTS and other mysteries of RS-232 to do this. By the following decade, though, all these things were obsolete and we were provided with PCs running some version of Windows, which crashed so often that as soon as I could get something better, I did.

But it was Clive Sinclair’s cheap and cheerful machine that got me into this.

Posted in doing mathematics, history, open problems | Tagged , , | Leave a comment

Graphs on groups, 8

The dark clouds seem to have lifted a bit. Perhaps now, that the last rush of conferences for a while is over, life can return to something like normality …

For me the most significant event was the last in the series of research discussions on graphs and groups, run by Vijayakumar Ambat and Aparna Lakshmanan S. in CUSAT, Kochi. The whole series was a great success. I gave the last talk, and devoted it to describing five areas, mostly involving the power graph of a group, where significant progress has resulted, usually as a result of contacts made during the RDGG meetings. In fact, almost as soon as I had given the talk, it was outdated: Swathi V V and I had answered, in a way which came as a surprise to me, one of the questions I asked in my talk. (This is described below.) Anyway, as well as getting the slides from the usual place on my St Andrews web page, you can watch videos of any or all of the talks in the discussion group. The link is https://youtube.com/playlist?list=PLemEI0kNLyjsrc95V78CQs3go-1sPS15T.

Another very nice meeting that I didn’t have the time or energy to comment on before was the 80th meeting of the Portuguese Mathematical Society. I was invited to speak, and chose a topic which I hoped would be accessible to many participants: “Conversations between graphs and groups”. I chose four areas where these two rather different parts of mathematics have interacted fruitfully. Again, the slides are in the usual place, and the professionally produced video is available from https://m.youtube.com/watch?v=OlELf0jBpPM&feature=share.

Anyway, here is a description of the new result. I have been banging on for a while about a hierarchy of graphs whose vertex set is a given group. I will only need two of them here:

  • the power graph, in which x and y are joined if and only if one is a power of the other;
  • the enhanced power graph, in which x and y are joined if they are both powers of some element z (equivalently, if the group they generate is cyclic).

Obviously any edge of the power graph is an edge of the enhanced power graph; said otherwise, the power graph is a spanning subgraph of the enhanced power graph. The two graphs coincide if and only if the group has the property that every element has prime power order. These are the so-called EPPO groups, which have been classified.

As a generalization of the classification of EPPO groups, I posed the following general problem. Let f be a graph parameter which is monotone, in the sense that adding edges to a graph doesn’t decrease its value. Then the value of f on the power graph of a group G is less than or equal to its value on the enhanced power graph. If these two graphs coincide, the values will be equal. But easy examples show that they may be equal for a wider class of groups. So I proposed the question: given a monotone graph parameter f, for which groups G do its values on the power graph and enhanced power graph coincide? This will be a wider class than the class of EPPO groups, and of course it depends on the chosen parameter.

An example of a monotone graph parameter is the matching number μ(Γ), defined to be the largest cardinality of a matching, a set of pairwise disjoint edges of the graph. Now our theorem says the following: the class of finite groups for which the power graph and enhanced power graph have equal matching number is the class of all finite groups!

Here is a hint at the proof. Take a matching M of maximum cardinalitly in the enhanced power graph of a group G. If all edges in M belong to the power graph, we are done; so suppose not. We are going to replace M by another matching of the same size, with one fewer edge not belonging to the power graph; after finitely many such steps we will be done.

Choose an edge {g,h} which is in M but is not an edge of the power graph, and (subject to this) the least common multiple of the orders of g and h is as large as possible. This lcm, call it l, is equal to the order of the cyclic group C generated by g and h. Now C has φ(l) generators, say x1,…,xφ(l), each of which is a dominating vertex of the induced subgraph on C, that is, joined to all other vertices. (Here φ is Euler’s totient.) If one of these vertices, say xi, is not covered by M, then we can replace the edge {g,h} by the edge {g,xi), which belongs to the power graph; so we can assume that there are elements y1,…yφ(l) such that, for all i, {xi,yi} is in the matching M.

Now there are three possibilities for such an edge:

  • xi; is a power of yi;
  • yi is a power of xi;
  • neither of the above.

In the first case, g and h are powers of yi, so we can replace the edges {g,h} and {xi,yi} by {g,xi} and {h,yi}, both in the power graph. In the third case, the least common multiple of the orders of xi and yi is greater than l, contradicting the choice of {g,h}.

So the second case must apply for all values of i, and the vertices y1,…yφ(l) belong to C. If any two of them, say yi and yj, are joined in the power graph, then we can do a three-way swap, replacing {g,h}, {xi,yi} and {xj,yj} by {g,xi}, {h,xj} and {yi,yj}.

So we have an independent set of size φ(l) in the cyclic group of order l. But, using elementary number theory, it can be shown that this is only possible for l ∈ {2,6}, and these cases are easily dealt with.

So, a quick question: Let φ be Euler’s function and τ the divisor function. Then φ(n) > τ(n) unless n is one of the numbers 1, 2, 3, 4, 6, 8, 10, 12, 18, 24, 30. Is this written down anywhere? (If you haven’t seen it, it is an interesting exercise.)

Posted in doing mathematics, events, open problems | Tagged , , | Leave a comment

A small problem

In connection with the research discussion about graphs and groups, I began to wonder which finite groups have the property that any two elements of the same order are conjugate. I thought about this, and got a certain distance, and then other jobs crowded it out of my thoughts.

I had become convinced that there are only three such groups, the symmetric groups of degrees 1, 2 and 3, and had got part way to a proof. In the end, not having time to go back to it, I resorted to a well-known search engine. With a little further research I came up with the answer, and with a small problem, which I want to pose.

In 1933, G. A. Miller published a paper in the Proceedings of the National Academy of Sciences of the USA on the problem. (His name is one which has come up a number of times in our researches about graphs on groups.) He showed, in brief, that in a group with this property, the derived group has index at most 2; moreover, if it has index 2, then the group is the symmetric group of degree 2 or 3. He couldn’t deal with the remaining case (though he did reduce it to considering non-abelian simple groups), and the earliest solution of the problem I found was by Patrick Fitzpatrick, in the Proceedings of the Royal Irish Academy in 1985; he used the Classification of Finite Simple Groups to show that the only such group is the trivial group. This was proved again by Walter Feit and Gary Seitz in 1988. (As a student of Peter Neumann, I know better than to say that they reproved the result – he would certainly have reproved me for saying so!)

So the problem I wish to pose is to give a proof of this simple result which does not depend on CFSG.

Posted in open problems | Tagged , , | 1 Comment

Bad times

Apologies for this. If you don’t like reading personal news, especially bad news, don’t persist. I am writing it down in the hope of putting it behind me.

Back in early April, Rosemary had a very bad fall on the Fife Coastal Path. She tumbled over a six-metre cliff into a rocky river bed, full of icy water. I was able to lift her head out of the water, but it was an hour before the ambulance and coastguard were able to get her out of the river on a scoop and into a helicopter to take her to Ninewells Hospital in Dundee. She had multiple fractures to vertebrae and pelvis as well as scalp lacerations, and her right eye had moved out of position. She was in hospital for two months. She is home now, but I am her full-time carer. I don’t mind doing this, but it eats up time and energy, and I know I am not coping well with other things; I try to get some things done but there is no way I can deal with everything that arrives.

The medics expect her to make a full recovery. She can now walk several blocks on elbow crutches, and the eye is moving back into its correct position. But the vertebrae have not yet mended, so she still has intermittent pain. Part of my job is administering painkillers four times a day. Of course I have all the cooking, cleaning, laundry, and so on, as well as helping her wash and dress herself. It will be months rather than weeks before she is recovered, so I will be on the treadmill for a while yet.

I know this is all very mild compared to what she has been through, but one of the worst things I have to deal with is the memory of watching her fall and being completely unable to help. In the first weeks after the accident it took all my mental strength to stop this scene replaying over and over. I am coming to terms with it a bit better now.

So finally an apology for the rather intermittent updating of this blog. I have been to two outstanding on-line conferences over the past couple of weeks: the British Combinatorial Conference and the Portuguese Mathematical Society’s 80th anniversary meeting. Normally I would have reported on some of the wonderful things I learned at these. But because of circumstances I had to skip many conference talks that I would have liked to attend, and have not had time or energy to write about the ones I did hear. I will just say that, at the Portuguese meeting, several plenary talks which appeared at first sight to be some way from my interests turned out to be absolutely fascinating. The BCC plenary talks have already been posted and the Portuguese talks will appear soon, I hope. When this happens I might try to point you to some of my favourites.

Posted in Uncategorized | 13 Comments

A little problem

In connection with the power graphs of unitary groups, I came across the following little number-theoretic conundrum. Can anyone solve it?

Let q be an odd power of 2 (bigger than 2). Show that (q2q+1)/3 is not a prime power unless it is a prime.

Posted in open problems | Tagged , , | 3 Comments

A new constant?

This is an appeal for help. Has anyone come across the constant 2.648102…?

Here is the background, which connects with my previous posts about graphs on groups. We are interested in the clique number of the power graph of the cyclic group of order n. The generators of the group are joined to everything else; there are φ(n) of them, where φ is Euler’s function. These must be in every maximal clique. To them, we adjoin a maximum-size clique of the subgroup of order n/p, where p is the smallest prime divisor of n. Thus the size f(n) of the largest clique satisfies the recurrence f(1) = 1, f(n) = φ(n)+f(n/p), where as above p is the smallest prime divisor of n. (This was proved by Alireza, Erfanian and Abbas in 2015.)

Now, with f defined as above, I conjecture that the ratio f(n)/φ(n) is bounded, and its lim sup is the constant 2.648102….

As you might expect, the largest values of this ratio are realised by the product of the first so many primes.

Posted in doing mathematics, open problems | Tagged , , | 8 Comments

Graphs on groups, 7

Nothing much to report, just a few connections.

My long paper has appeared on-line ahead of publication in the International Journal of Group Theory. You can get a copy here (click on PDF).

Next week, on Wednesday 12 May at 10:00 (British Summer Time, that’s 09:00 UTC), I am speaking at the QMUL day of the London Combinatorics Colloquia.

And, if you want a longer version, I am giving an 8-lecture intensive course at the London Taught Course Centre next month (tentatively 8–9 June). These courses run over a 24-hour period, from lunchtime on Tuesday to lunchtime on Wednesday. Email office@ltcc.ac.uk to register for the course.

Posted in events | Tagged , , | Leave a comment

Graphs on groups, 6

The Groups and Graphs seminar has been running well.

I find that I feel close to many people in the seminar even though most likely we have not met face to face.

So I feel concerned about the Covid wave in India in a way that I probably wouldn’t have done but for this seminar. My thoughts are with them. By comparison, we are in good shape here. I had my first Covid jab (many weeks late, and after a lot of effort, since I had been left off the list), I am staying at home, and there is very little Covid in the neighbourhood.

Please remember the people of India facing this terrible uncertainty and trouble.

Posted in events | 1 Comment