Graphs on groups, 12

One thing I have learned from the project is that the most interesting question about graphs defined on groups is this: given two types of graph defined on a group G, what is the class of groups for which the two graphs are equal? Answering this question has already thrown up some famous and important classes of groups, as I discussed earlier, including Dedekind groups, 2-Engel groups, EPPO or CP groups, and groups with all Sylow subgroups cyclic or generalised quaternion.

Now I am happy to report on another instance, where it is not so much the class of groups which is important as the group-theoretic methods used to obtain the result. The authors are Saul Freedman, Andrea Lucchini, Daniele Nemmi, and Colva Roney-Dougal. I’m grateful to them for keeping me in the loop with this project.

The story begins with the generating graph of a group, in which two elements are joined by an edge if together they generate the group. This has been of very great importance since its introduction by Breuer, Guralnick and Kantor, especially in connection with the probability that two random elements generate the group. But it is not much use for groups which cannot be generated by two elements!

Andrea Lucchini proposed using a different graph which does not have this defect. Call two elements x and y of the group G independent if there is no minimal (with respect to inclusion) generating set for G containing both of them. The independence graph of G has vertex set G; its edges are the independent pairs.

There is an obvious obstruction to being joined in this graph; namely, being joined in the power graph. If, say, y is a power of x, then no minimal generating set can contain both, since if they both lie in a generating set then deleting y results in a smaller generating set. So the independence graph is a subgraph of the complement of the power graph.

Lucchini says that a group G has the independence property if the independence graph is equal to the complement of the power graph. Now the theorem which has been proved by these four authors gives a complete classification of groups with the independence property; all are supersoluble.

The bulk of the proof concerns a hypothetical insoluble group with the independence property. Four pages of argument reduce this to the case of an almost simple group, and then thirteen pages of very detailed analysis of the finite simple groups and their automorphism groups (including special consideration of the 8-dimensional orthogonal groups of type + over fields of orders 2, 3 and 5) shows that none of these can occur. Even after all this, and it is known that the group must be supersoluble, it requires another five pages to complete the classification.

The key result about almost simple groups, important in its own right and almost certainly having further applications, is the following. Any non-abelian finite simple group S contains two non-commuting elements s and x such that, in any almost simple group G with socle S, the element x lies in every maximal subgroup containing s. In most cases the element x can be chosen to normalise the subgroup generated by s. But this gives only the barest indication of the level of detail required.

The paper also contains a similar but much easier result, which was actually proved at my suggestion. The rank of a finite group is the minimum number of generators, and two elements are rank-independent if they are contained in a generating set whose cardinality is equal to the rank. The rank-independence graph has two elements adjacent if they are rank-independent. Now the obvious obstruction to adjacency in this graph is adjacency in the enhaced power graph. (For suppose that x and y are joined in the enhanced power graph; this means that there is an element z such that both x and y are powers of z. Now if such a pair is contained in a generating set S, then we may remove x and y and insert z instead to obtain a strictly smaller generating set.

Call a group G rank-perfect if the rank-independence graph is the complement of the enhanced power graph. The paper also shows that rank-perfect groups are supersoluble, and gives a complete classification of them; the entire argument takes just over two pages.

Answering a question always opens many more. For most groups, there is a “gap” between the complement of the power graph amd the independence graph, or between the complement of the enhanced power graph and the rank-independence graph. What can be said about these difference graphs? For example, which vertices are isolated, or joined to all others? When are these graphs connected?

Also, what is the relation between the independence graph and the enhanced power graph, or the commuting graph? And what is the relation between the rank-independence graph and the commuting graph? I mean, for which groups is the intersection of one of these pairs the null graph, and for which groups is the union the complete graph? Other questions of the same sort can also be asked.

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

Graphs on groups, 11

A brief interlude to describe another recent preprint, and as in the preceding post I will concentrate on one result in the paper.

I don’t know why it happens, but in this project one of the most interesting graph parameters turns out to be the clique number. I have talked in an earlier post about the fact that the clique number of the power graph of a group G is the largest clique number of a cyclic subgroup, and the clique number of the cyclic group of order n is at most three times φ(n) where φ is Euler’s totient (in fact the limit superior of the ratio is 2.6481017597…).

The graph of concern here is the condensed version of a conjugacy supergraph, as defined in the preceding post. Recall that the commuting graph of a group has two vertices joined if they commute (that is, generate an abelian group). Replacing “abelian” by “nilpotent” or “soluble” here gives the nilpotency or solubility graph. Now the conjugacy super-solubility graph has x and y joined if there are conjugates u and v of x and y respectively such that u and v generate a soluble group. To condense it, we shrink each conjugacy class to a single vertex, and discard the identity. So the vertices are the non-trivial conjugacy classes, two classes joined if they contain elements generating a soluble group.

The analogous graphs for “abelian” or “nilpotent” were investigated by Herzog, Longobardi and Maj and by Mohammadian and Erfanian respectively, under the names “CCC graph” and “NCC graph” respectively, so the one considered here is the SCC graph (soluble conjugacy class graph). The investigation of the soluble case was begun by Parthajit Bhowal and Rajat Kanti Nath, who invited first me and then Benjamin Sambale to join the project.

The result I want to advertise is the following.

Theorem: Given a positive integer d, there are only finitely many finite groups whose SCC graph has clique number d. In particular, the only finite groups whose SCC graph is triangle-free are the cyclic groups of orders 1, 2 and 3 and the dihedral group of order 6.

This theorem does depend on the Classification of the Finite Simple Groups. I will say just a few words about the proof.

First, if G is soluble, then its SCC graph is complete, and so the result follows from the theorem of Landau in 1903 asserting that there are only finitely many groups with a given number of conjugacy classes. (Our theorem could be regarded as a strengthening of Landau’s.)

If G contains an element g whose order is the product of two primes p and q, then g, gp and gq define a triangle in the SCC graph. So if the graph is triangle-free, then every element of G has prime power order; G is a CP group, or EPPO group, as in the preceding post. Completing the proof involves a little digging into the structure of these groups, using properties of simple groups from the ATLAS of finite groups.

The general theorem in the insoluble case involves several reductions, and some knowledge about groups of Lie type; I will simply refer to version 2 of the paper, shortly to appear on the arXiv. We don’t have a good upper bound for the order of a group whose SCC graph has given clique number; the case of clique number 3 might be an interesting problem to tackle. For clique number 3 we meet insoluble groups; for example, the SCC graph of the alternating group A5 has four vertices (one class of elements of order 2, one of order 3, and two of order 5); the involutions are joined to all the other classes, and the two classes of order 5 to one another.

In the spirit of yesterday’s post, here are two questions we can’t answer:

  • For which groups do the SCC and NCC graphs coincide?
  • For which groups is the expanded SCC graph equal to the solubility graph?

It is possible that the answers might be “nilpotent groups” and “soluble groups” respectively.

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

Graphs on groups, 10

The lesson of this post and the next in the series is that the most interesting questions (to me, anyway) are not about the girth of the deep commuting graph but instead about the classes of groups G defined by either of the following two conditions:

  • two different types of graph defined on G are equal, or are approximately equal in some way;
  • one type of graph defined on G belongs to a restricted class (for example, perfect graphs, cographs, threshold graphs).

This post concerns an extension of the hierarchy of graphs on a group into a second dimension, which gives more scope to ask such questions. The results are contained in two papers on the arXiv, 2112.02395 and 2112.02613 (a revised and improved version of the second will be posted shortly).

I will restrict attention here to three types of graph defined on a group:

  • the power graph: two elements joined if one is a power of the other;
  • the enhanced power graph: two elements joined if both are powers of a third element;
  • the commuting graph: two elements joined if they commute.

It is commonly done with these graphs to delete elements of the group joined to all others, but I will not do this, for reasons which will become clear.

The new element is to take also an equivalence relation on the group. The ones I will describe here are

  • equality;
  • conjugacy;
  • same order.

The starting point was the talk by Lavanya Selvaganesh in the research discussion at CUSAT, although very similar ideas had also been considered by other people.

So, if A is a type of graph on groups, and B is an equivalence relation, we define the B superA graph on G by the rule that x and y if there are elements u and v which are B-equivalent to x and y equivalently and are adjacent in the graph A. So, for example, we can talk about the “order superpower graph”, which was Lavanya’s subject.

We make a convention that two elements which are B-equivalent are joined in the B superA graph. This is not forced but is in a sense natural (since arguably the definitions of the graphs would give a loop at each vertex, from which this convention would follow).

This gives us nine graphs to play with, though it turns out that two of them (the order superenhanced power graph and the order supercommuting graph) are always equal (though the other eight are in general distinct). A subsidiary problem which we didn’t solve but which should not be two hard is to find a group on which all eight graphs are distinct.

As I said, I am interested in the class of groups for which two of these graphs coincide. It was already known that the power graph is equal to the enhanced power graph if and only if all elements of G have prime power order (these are the so-called EPPO groups or CP groups); and that the enhanced power graph is equal to the commuting graph if and only if all the Sylow subgroups of G are cyclic or generalized quaternion. In each case, all such groups are known, though the classifications are not trivial.

I will discuss two new cases where interesting and previously-studied classes of groups arise. In the second case, I learned something from this, which may be new to you also.

A Dedekind group is a finite group in which all subgroups are normal. Dedekind proved in 1897 that such a group is either abelian, or of the form Q×E×F, where Q is the quaternion group of order 8, E is an elementary abelian 2-group, and F is an abelian group of odd order.

Theorem: For a finite group G, the following are equivalent:

  • the power graph of G is equal to the conjugacy superpower graph;
  • the enhanced power graph of G is equal to the conjugacy superenhanced power graph;
  • G is a Dedekind group.

A 2-Engel group is a group which satisfies the 2-Engel identity [[x,y],y] = 1, where [x,y] denotes the commutator x−1y−1xy. Thus every nilpotent group of class 2 is 2-Engel, and Hopkins and Levi independently showed that a 2-Engel group is nilpotent of class 3 (yes, that is the Levi whose name is attached to the Levi graph); both inclusions are strict.

I didn’t know prior to this work that G is a 2-Engel group if and only if every centraliser in G is a normal subgroup. This is proved in a post by Korhonen on StackExchange, using a result of Kappe.

Theorem: The commuting graph of G is equal to the conjugacy supercommuting graph if and only if G is a 2-Engel group.

There is much more to say about these graphs, for some of which I refer you to the papers. In particular, each supergraph has a “condensed” version where the vertices are the B-equivalence classes rather than elements; I used the “expanded” version in order to be able to compare the graphs. But that will do for now. The moral of this story, if it has one, is that this project is turning up interesting group theory.

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

Happy new year

Happy new year, everyone. Although I can’t see the end of the Covid tunnel yet, I do hope that for all of us the new year brings better times.

One big change for me in the coming year is that, from the beginning of March, I will only be working 25% time. (Of course, it probably doesn’t mean I will be doing any less, but it might mean I have a bit more time for the things that I want to be doing.) In parallel, this years presentation of the Advanced Combinatorics module in St Andrews will be the last in the current form. From next academic year, this module will only be lectured every second year; it will alternate with a new module on Set Theory and Logic. So it will be no longer feasible to have three syllabuses on Advanced Combinatorics which rotate; I will have to take the best bits and combine them into one.

Also, and perhaps incidentally, I reach my three-quarter century next month. (This a milestone which is significant only because it is three times the product of the numbers of fingers on my hands.)

There are a couple of significant new developments about graphs defined on groups, which I hope to tell you about in the near future. These are partly due to the fact that a couple of group theorists have picked up the topic. So there may be yet more news soon.

Posted in Uncategorized | Tagged | 2 Comments

Two pointers

As you know, this is where I take out my frustrations by having a good grumble about life, the universe, and everything. Yesterday, in a meeting, we learned of two developments coming to the academic world. In neither case is it an unmixed blessing. I should add that this is in no way a grumble against my colleagues, who foresightedly and openmindedly have told us about what is heading our way so that we can be prepared.

The first, and mostly harmless, concerns publication of research data. No longer will it be enough to say “Contact the author for the data/programs used in this paper”; the data must be available at a specific link published in the paper. It is even claimed that such statements will still be required in papers with no data at all, such as pure mathematics papers.

I do not know whether this is being forced on the humanities as well as the sciences, or whether it is just an anomaly of mathematics being misclassified as a science. In any case, I hope that someone can provide us with some boilerplate text for the purpose. (One of my colleagues suggested something along the lines “No data were hurt in the research underlying this pure mathematics”.)

But how do you publish “no data”? If mathematics is founded on set theory, a file containing the empty set symbol might do the job (an empty file might be problematic). But perhaps the bureaucrats might be happier with a spreadsheet with no entries.

Journals already require publication of funding information; many specify a conflict of interest statement; some need an ethical approval statement. I fear that in future a pure mathematics publication will resemble a beautiful work of art in a standard frame designed by a committee.

The second, more serious because it addresses a real problem, concerns accessibility of lecture notes. Now this doesn’t mean, as you might first think, that we will have to dumb down our lecture notes to make them accessible to creatures of restricted intelligence. Instead, it seems that there is a PDF reader program which reads aloud the contents of a PDF file for disabled students. (No, I am not talking about a lecturer!) It seems that PDF documents produced via LaTeX are not well handled by this piece of software, and so we are to blame and must suffer.

I have spent a lot of time during my career trying to make lecture notes as clear and beautiful as possible. I have always taken the view of conventional typographers, that typesetting is a window through which you see the beautiful scenery, and the best typesetting is the one which provides the most unobtrusive window pane. Now we are told that the programs to fix this problem (the best of which is called “bookdown”, if I caught the name right) seriously degrade the LaTeX typesetting in the interests of accessibility. So the majority of students will be penalised to help the minority. Is this good? This is a moral question I can’t judge.

With a bit less than twice the work, one could produce two files, one a carefully crafted LaTeX file, the other a reader-friendly file. The downside would be maintenance; changes would have to be made in two places, and the files could very easily get out of sync.

Let me interpolate two speculations here; I have no evidence for either of these.

First, it seems highly likely that this PDF reader is optimized for files produced by Word, as a hangover of the Microsoft hegemony. If this so, then we are being punished for using a better product than Microsoft can produce.

Second, this measure (entirely arbitrary, if my first speculation is correct) will delight the bureaucrats. Here is a measure, a number produced by computer and hence completely objective, of our concern for handicapped students. How long until it is incorporated into staff appraisals and disciplinary measures?

Now I have a suggestion here. The great computer scientist Donald Knuth, in the days before the term “web” became synonymous with “internet” in the public mind, devised a system for producing programs and documentation together, which he called Web. A Web document could be fed to two preprocessors called Tangle and Weave, though I don’t remember which was which. One of them produced as output a Pascal program (Knuth’s preferred language at the time; I believe there is a C version of Web now). The other output a TeX document which consisted of the program with documentation. Knuth published two major programs, TeX and METAFONT, in this form as books.

Surely we could have a much simpler system here. An input file (which would superficially resemble LaTeX, to ease the learning curve) could be processed in two ways: the output of one would be a reader-friendly PDF, or means to produce one, such as a bookdown file; the other would be a non-crippled LaTeX file. Both could be made available to students, and maintenance would only need to be done in one place.

Ultimately, like Hamlet, I know where the exit door is, and I know it is not locked. When my previous university brought in draconian rules for staff performance and appraisal, including restrictions on seminar attendance, I decided that rather than stay and fight I would retire and live on my pension; and so I would be doing, had not St Andrews come to the rescue with the offer of a half-time position. I still have the option of retiring and living on my pension. But I am in such a good, friendly and supportive department that I don’t expect this to become necessary, and I would take that door only with great reluctance.

Posted in Uncategorized | Tagged , | 14 Comments

Graphs on groups, 9

We continue to make progress with the graphs on groups project, but this post attempts to step back and look at the whole thing.

What use is all this?

Once, after I talked at a departmental colloquium at the University of Southern California, after my talk someone asked “What use is all this?” My view is that the fact that it is fun is reason enough to do it. But people like funders may want more than that as an answer. So let me make some comments.

To group theorists

A group theorist is likely to ask: What do I learn about a group from these graphs? So I will address that first.

The subject began with the seminal paper of Brauer and Fowler in 1955, in which they showed that there are only finitely many finite simple groups having a given group as the centralizer of an involution. Of course, it wasn’t then known that a non-abelian finite simple group must contain an involution; at the time, this was “Burnside’s conjecture”, and was proved by Feit and Thompson in the next decade. After Brauer–Fowler and Feit–Thompson, it was clear that characterizing simple groups by the centralizer of an involution would be an important ingredient in any eventual classification; and so indeed it turned out.

Brauer and Fowler used the reduced commuting graph (the commuting graph with the identity removed). I think the word “graph” does not occur in their paper, but the make use of the graph distance. Essentially they showed that the distance between two involutions in this graph is rather small.

Maybe the next contribution was that of Gruenberg and Kegel, who defined the prime graph of a finite group (now called the Gruenberg–Kegel graph: the vertices are the prime divisors of the group order, two vertices p and q joined if there is an element of order pq in the group. They gave a powerful structure theorem for groups whose GK graph is disconnected. Moreover, this was a tool in studying the decomposition of the augmentation ideal of the integral group ring.

I will return to this question later.

Another thing of interest to group theorists is that questions about the graphs often give rise to challenging problems about the groups. Here are three examples.

  1. The following three properties of a finite group G are equivalent:
    • G is an EPPO group (all elements have prime power order);
    • the Gruenberg–Kegel graph of G has no edges;
    • the power graph and enhanced power graph of G coincide.
    So we have the problem of classifying these groups.
  2. Other questions about when two of these graphs coincide give rise to other group-theoretic classification problems, some of which are worth a look. Examples include minimal non-abelian, non-nilpotent, or non-solvable groups, 2-Engel groups, and Dedekind groups.

To graph theorists

By contrast, graph theorists are not going to learn anything about general graphs by studying graphs derived from groups. However, there is a different motivation, cited by Kelarev and Quinn when they introduced the power graph in around 2000: Do groups give us examples of graphs with interesting properties, for example, graphs which will be good as networks (so good connectivity and expansion properties)?

In looking for a good network, there is a tension between having many edges (which will make the network more expensive to construct) and having good connectivity (too few edges work against this). I don’t know any definitive result. But when I was involved in writing a survey paper on power graphs of groups, as an experiment I looked at an example, the Mathieu group M11, the smallest sporadic simple group. This group has order 7920, so we start with a graph with 7920 vertices. But simple reductions (first “twin reduction”, identifying vertices with the same open or closed neighbourhood, then discarding “peripheral” parts of the graph) results in a rather beautiful graph: a bipartite graph on 165+220 vertices, which is semiregular (valencies 4 and 3 in the two parts), has diameter and girth 10, and has automorphism group M11. I have not examined this graph further, and have not done a thorough search to see if it has been found before, but finding something as nice as this in the first place I looked seemed a good omen.

To other mathematicians

I can offer here, as a carrot, the fact that this research has thrown up a number of interesting diophantine problems in number theory.

For one example among many, the power graph and enhanced power graph of a group have the same clique number if and only if the largest order of an element of the group is a prime power. I do not expect that much can be said about this class of groups. But let us look at one example, the groups PGL(2,q) for prime powers q. The largest order of an element in this group is q+1. So the power graph and enhanced power graph have the same clique number if and only if either

  • q is a power of 2, and q+1 is a Fermat prime or 9; or
  • q is a Mersenne prime, and q+1 is a power of 2.

(The first bullet point here conceals the use of the solution to Catalan’s equation, prime powers differing by 1.)

Other number-theoretic problems are thrown up by other questions. But here is one which is unrelated.

A clique in the power graph of G is contained in a cyclic subgroup of G. So the clique number of the power graph of G is equal to the largest clique number of a cyclic subgroup of G. (This is not the same as the clique number of the largest cyclic subgroup.) Now the clique number of a cyclic group of order n is a number-theoretic function f which is defined by the recurrence f = 1, and for n > 1, f(n) = φ(n)+f(n/p), where p is the smallest prime divisor of n, and φ is Euler’s totient. It follows that f(n)<3φ(n) for all n. But we could ask:

  • Is the lim sup of the ratios f(n)/φ(n) rational, algebraic, or transcendental?
  • What other limit points does the set of these ratios have?

To young researchers

Finite group theory is a very technical area, often somewhat off-putting to outsiders. But graph theory is vast and sprawling with many easy ways in.

So, not surprisingly, the field of graphs on groups offers many problems where mathematicians starting out can work profitably.

For example, there are many graphs defined on groups: power graph, enhanced power graph, deep commuting graph, commuting graph, nilpotence graph, solubility graph, non-generating graph. In a paper in preparation, we are going to extend this hierarchy into a second dimension. And there are many graph properties and parameters: connectedness, diameter, girth, clique number, chromatic number, independence number, clique cover number, matching number, domination number (strong or weak), Eulerian, Hamiltonian, pancyclic, and lots more.

So choose a type of graph on a group, and a property or parameter; chances are reasonably good that this will not previously have been investigated. See what you can do!

There are other areas of algebra where similar graphs arise, and where similar questions can be asked. One of these is zero-divisor graphs of rings (that is, commutative rings with identity).

Some of my favourite problems

Since we have a hierarchy, which is being extended into a second dimension, one very natural thing is to compare two graphs in the hierarchy. Most questions about the original hierarchy have been solved, and interesting graph classes arise. But there will soon be more such questions.

Also, even if these problems have been solved, they can be generalized in the following way. Take two adjacent graphs in the hierarchy, call them A and B; and take a monotone graph parameter p, one which cannot decrease when an edge is added (or one which cannot increase, if you prefer): many parameters are monotone. Now ask: For which groups G does p(A(G)) = p(B(G))? Two small examples: the clique numbers of the power graph and enhanced power graph of G are equal if and only if the largest order of an element of G is a prime power; and the matching numbers of these two graphs are equal for all G (even though we cannot write down a formula for them in every case).

Another problem area concerns universality. Given a graph type A, can every finite graph be embedded as induced subgraph in A(G) for some group G? If not, can you identify the class of graphs which can be so embedded? And in the other direction, given a subgroup-closed class of graphs, can you identify the class of groups G for which A(G) belongs to that class?

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

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 , , | 3 Comments