An apology

What would life be like if I could remember all the things I ever knew?

Yesterday I was led to something I posted here twelve years ago. This was based on a talk to the London Algebra Colloquium by Mark Wildon.

He told us about results he had proved using Jordan’s theorem – this is the theorem of Jordan which gave me my fifteen minutes of fame when Jean-Pierre Serre talked about it at Queen Mary – on the existence of derangements in finite transitive permutation groups. Mark applied this to show the following, though he didn’t phrase it in these terms.

The conjugacy supercommuting graph on a group G is the graph whose vertex set is G, with an edge from x to y if there are conjugates of x and y which commute. Mark’s theorem asserted that an element of G is joined to all others if and only if it belongs to the centre of G. As a corollary, the graph is complete if and only if G is abelian.

These results form parts of theorems 4 and 5 in my paper with G. Arunkumar, Rajat Kanti Nath, and Lavanya Selvaganesh on “Super graphs on groups”, described here and now published in Graphs and Combinatorics. Our proof is the same as Mark’s.

We apologise to Mark for not attributing the result to him, and are happy to do so now.

Posted in doing mathematics | Tagged , , | 4 Comments

A week in Florida

Deerfield Beach sign

The week before last I was at the Deerfield Beach Resort in Florida, about halfway between Miami and Donald Trump’s place. My children could not believe it when I told them (I am not very good at holidays). Of course they guessed that it was not a holiday but a mathematics conference; in fact, in honour of the 70th birthday of Daniela Nikolova.

Unfortunately Daniela had to spend the entire conference in a wheelchair, having slipped and broken an ankle getting out of the jacuzzi on the pre-conference cruise. So we all wished her a speedy recovery; I do hope this happens.

It seemed important for speakers to remember when they first met Daniela. I am not sure of this. The first I can recall is Groups St Andrews in 2005, but there may have been earlier occasions which I have forgotten. A remarkable thing about the meeting was the number of pairs of participants who met for the first time at a Groups St Andrews meeting. It might be interesting to construct the graph …

The talks were a very mixed bag. There was a day for “Women in mathematics”, chaired by a man; and a day for “Young researchers in mathematics” bookended by two researchers who were no longer young. I won’t give a blow-by-blow account; I will just single out a few of my favourite talks. The first was by David Burrell. The count of groups of order 1024 announced in the year 2000 was incorrect; when he re-did the computations, he got a different number. At first he assumed he had made a mistake, and checked his calculations carefully. So eventually he contacted Eamonn O’Brien, a safe pair of hands if ever there were one. Eamonn was able to locate the mistake, apparently a simple transcription error in the tabulation of the results. It is not clear if it was human or computer error, though it looks like the former. Anyway, the correct number of groups of order 1024 is 49,487,367,289.

Gareth Jones told us about the Bateman–Horn conjecture. This is a conjecture in number theory but would have a number of important spin-offs in group theory, including the statement that there are infinitely many insoluble (and so 2-transitive) permutation groups of prime degree other than symmetric and alternating groups. The conjecture goes as follows. Suppose that you have a finite number of integer polynomials satisfying the three conditions

  • each polynomial is irreducible;
  • each polynomial has positive leading coeffiient;
  • the product of the polynomials is not identically zero modulo any prime.

Under these conditions, Schinzel conjectured that there are infinitely many values of the argument for which all the polynomials take prime values. Bateman and Horn gave a considerable refinement of this conjecture, actually giving a formula for the conjectured asymptotics, a little complicated to state here but computable in particular cases. This conjecture applies to the twin primes conjecture (take the polynomials t and t+2), the Sophie Germain primes conjecture (take t and 2t+1), and the existence of infinitely many groups PSL(2,p) of prime degree (take t and t2+t+1). It applies in several other cases including my recent work with Pallabi Manna and Ranjit Mehatari: it would imply infinitely many simple groups whose power graph is a cograph. Gareth and his co-authors have shown that the Bateman–Horn conjecture predicts things like this with remarkable accuracy.

Delaram Kahrobaei (someone I first met at Groups St Andrews in 2013) speculated about whether graph groups would provide a post-quantum encryption system, that is, a trapdoor one-way function where the hard problem is hard even on a quantum computer, should one be built. (A graph group , aka a right-angled Artin group, is defined by a graph Γ generators for the group are vertices of Γ and the only relations are that adjacent vertices commute.)

Carmine Monetta, in addition to running the conference website and the computer facilities for speakers, spoke about the non-abelian tensor square of a group. This is a concept which I have met before, since it comes up in the work Bojan Kuzma and I did on the deep commuting graph of a group.

Artefact

Mike Kagan was there with his family. He gave us the artefact shown in the picture, saying that it seemed to him that it might be Egyptian. In fact I was able to recognise it. In 2004 I went to Iran and was privileged to be able to visit Persepolis with a University car and driver from Shiraz. Here is one of the pictures I took then. Can you spot him?

Persepolis

We were taken on several excursions: to the Loxahatchee Wildlife Refuge, where the signs mentioned alligators and snakes but we saw a family of deer quite close up and some ducks that sounded like pigs; to the Jupiter campus of Florida Atlantic University, where we saw among other things the Max Planck Institute for Neuroscience, the only MPI in North America. We skipped the dolphin trip so as to get on with our joint work with Mike Kagan.

Back home, I had what has become an unfamiliar sensation: jet lag!

Posted in events | Tagged , , , , , , , , , | 7 Comments

Cambridge

This is in a sense a follow-up to my earlier post here, describing how the 6-month programme at the Isaac Newton Institute had come to a premature end because of the covid pandemic.

The time I spent in Cambridge then (early January to mid-March) was a very good time for me. With Rosemary Bailey, Michael Giudici and Gordon Royle, I finished a paper on the subgroup of a transitive permutation group generated by derangements, which was published in the Journal of Algebra. More significantly, I worked with Rosemary, Cheryl Praeger and Csaba Schneider on the geometry of diagonal groups. This was intended as a continuation of the work by Cheryl and Csaba on the geometry of wreath products, published as a book in the LMS Lecture Note series. At the end of our time in Cambridge, we had almost completed a “synthetic” approach to the geometry, and agreed on how to write it up. But in the last couple of days, I had a vision of what the “axiomatic” version should say, although I doubted my ability to prove it. Nevertheless, stuck at home in St Andrews by the lockdown, Rosemary and I were able to prove the result I had in mind. Instead of putting a group in at the start, we were able to make it emerge naturally from purely combinatorial axioms, just as a division ring does in the axiomatic theory of projective planes. The paper has just been published in the Transactions of the American Mathematical Society, and I consider it one of my best.

Now that lockdown restrictions have been lifted, the INI offered the organisers a 3-month period from May to July this year, so I returned to Cambridge for this. However, things did not work so well. Instead of two programmes running, with the possibility of real interactions between the two sets of participants, there were four programmes, two of which were mostly stuck in a building not at all suitable for intensive mathematical research in the back of Churchill College. The organisers found me a share in a large office at the INI, but when I was there I had fewer chances of interacting with other participants. So I divided my time between three places (the third being a flat in Benians Court which had decent wi-fi; it was very tempting just to work there).

I did get a lot of work done during this period. But unlike the first period, it was not with other participants in the programme, but mostly with co-authors on the Graphs on Groups project, mostly in India; also with Marina in St Andrews who was on an undergraduate research internship.

Of course, because of Rosemary’s continuing difficulties after her fall, I had to arrange for her to be in Cambridge with me. Taking her out for walks around the streets, I became very aware of some of the drawbacks of Cambridge. Cyclists there are allowed to ride on the pavement beside the road in many places, while elsewhere they just do it anyway without permission. Often there is little warning to pedestrians about this. (On the stretch along Madingley Road from Storey’s Way to Lady Margaret Road, there was just one sign declaring it a dual-use path, cunningly hidden in the trees and bushes where I was not aware of it for the first month.) Not one in ten Cambridge cyclists seem to have come across a really useful invention, the bicycle bell, which can be used to warn pedestrians of their approach. Many are staring at their phones, heedless of pedestrians. Twice I saw, right outside our flat, a cyclist come off his bike at considerable speed; if this had happened while Rosemary was hobbling along with her stick, the consequences could have been very serious. I was also spooked by the Madingley Road/Lady Margaret Road junction, where there is no part of the traffic light cycle which is safe for pedestrians, and the car which is going to run into you is probably coming from behind. I had to brave this junction many times because the nearest food shop is in the centre of Cambridge, quite a distance from the flat.

The only time the programme came alive was during the last week and a bit. On Friday of the penultimate week there was a memorial day for Jan Saxl, though the location was not well publicised. Then in the last week, we had a closing workshop with some very lovely talks. These included

  • Tim Burness on “Base 2 permutation groups and applications” – a strange and brave idea by Jan Saxl, since I would have thought that classifying groups with base size greater than 2 would have been an easier task.
  • Scott Harper on “Invariable generation and totally deranged elements of simple groups”. Every finite simple group has a pair g, h of elements which invariably generate it, meaning that you can replace each of them by an arbitrary conjugate and still have a generating set. There is no conjugate pair which invariably generate, since this would imply that a single element generates the group; but Garzoni asked whether there was a pair in the same conjugacy class in Aut(S), for a simple group S, which invariably generate. Scott showed that this does happen, and moreover gave a complete classification of this situation.
  • Persi Diaconis on “Double coset random walks on groups” showed us how some classical random walks (starting with contingency tables) can be realised as walks on the double cosets of finite groups, and how the character theory of the group can be used to analyse these.
  • Alex Lubotzky on “Good locally testable codes”. The third time I have heard this, but each time it sinks in a bit further. The idea is very simple. Cayley graphs are either left or right: the connection set multiply elements on one side, so that multiplying on the other side gives an automorphism. They combine these two methods by having a left and a right connection set, to give a 2-dimensional Cayley complex with cells (g,lg,gr,lgr) where l comes from the left connection set and r from the right.

The conference honoured Michael Aschbacher and Robert Guralnick, neither of whom was present; both spoke remotely by Zoom. I am getting old and grumpy, and beginning to think that despite all the emissions Zoom talks save, they are not really a substitute for the real thing. But best wishes to both.

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

The enhanced power graph is weakly perfect

Earlier this year, I posed a combinatorial problem, a solution to which would imply that, for any finite group G, the enhanced power graph of G is weakly perfect, that is, has clique number equal to chromatic number.

Recall that the vertices of the graph are elements of G, two vertices joined if they generate a cyclic group. It is easy to see that any clique in this graph is contained in a cyclic subgroup, so the maximum size of a clique is the maximal order of an element of G. That the chromatic number of this graph takes the same value would follow if, for any natural number n, we could find subsets A1,…,An such that the cardinality of Ai is φ(i) (Euler’s totient) and, if gcd(i,j) ≤ n then Ai and Aj are disjoint.

I spent more time than I care to remember trying various sophisticated ways to make this construction, and inflicted the problem on several other people too. But as readers of this blog will remember, an unnamed correspondent came up with a simple direct construction that can be described in a line or two and takes only a little longer to prove correct.

The correspondent turned out to be Veronica Phan, who tells me she is a medical student in Ho Chi Minh City who does mathematics as a hobby. I think there is a lesson here for us!

We wrote this up and the paper is now on the arXiv: https://arxiv.org/abs/2207.07156

Posted in doing mathematics | Tagged , , , | 19 Comments

More on the 3p paper

I wrote here about Peter Neumann’s paper on primitive permutation groups of degree 3p, where p is a prime number.

Well, summer is almost over, but my undergraduate research intern Marina Anagnostopoulou-Merkouri and I have done our work and produced our paper, which is a combination of new combinatorial results about association schemes with prescribed eigenvalue multiplicities, a historical note on the context of the original paper, and a tribute to Peter. The paper is on the arXiv, here.

In the course of doing this work, Marina found several misprints in my re-typed version of the 3p paper. I have corrected these and posted a new version on the arXiv, here.

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

Student meetings

Lots of things have happened and not been noted, sorry. I will try to catch up a bit over the next few weeks.

In the past few weeks I have spoken at two student-organised conferences. First, in July, was the Postgraduate Group Theory Conference. It was held over three days, at three different venues in London (City, Kings and Imperial), the first time this has been done, I think. I was unable to attend the first two days, since I was recovering from a mild brush with covid, but on the final day I went along to Imperial for the event.

Then this week I was in Edinburgh for GEARS, the Glasgow and Edinburgh Algebra Research Seminar, held in the Bayes Centre.

No prizes for guessing what I talked about in these meetings. And I am not going to give you a blow-by-blow account. I will just mention one talk from the Edinburgh meeting, by William Bevington. He was talking about a result, I think by Andreas Blass, asserting that there is a cohomology theory which “detects” the failure of the Axiom of Choice.

Maybe this is not so surprising. The Axiom of Choice states that every partition has a section, while vanishing cohomology means that every cocycle is a coboundary, not such a different idea. So all you have to do is to build a cohomology theory without topology, by using discrete spaces.

But it did lead us to wonder whether various properties of non-AC universes would be reflected in the cohomology arising in this case.

Two final remarks. First you need the Axiom of Choice to prove that there is a group structure defined on any set. (Proof: Exercise!) Second, as William remarked, of equivalents of the Axiom of Choice, the Axiom itself is obviously true, the Well-Ordering Principle obviously false, and Zorn’s Lemma, well, who knows?

I very much enjoy student-organised meetings. They have a real buzz of excitement to them that just doesn’t happen at most meetings.

Posted in events | Tagged , | 2 Comments

BCC29 at Lancaster

Last week we celebrated the 29th British Combinatorial Conference in Lancaster, face to face. (As a side observation, this was by far the largest social gathering I have been at since the start of the pandemic; I found it both unfamiliar and exhausting, through no fault of the organisers.)

The BCC has made a couple of judgment calls recently which have fortunately worked out well. Last year, Max Gadouleau and his team decided in advance to run the conference entirely on-line, and to make it the best on-line conference ever. This year, Tony Nixon and his team insisted from the start that it would be a live meeting. Both these proved to be right.

The meeting for me was memorable, and nostalgic. At the business meeting, I stood down as chair of the committee after thirty years. This was in large part because looking after Rosemary on top of everything else has made the last year or two difficult and exhausting, and I don’t think I have done the job very well. But I am very fortunate to be able to hand over the chair to Julia Wolf, with Robert Johnson as secretary and Simon Blackburn as treasurer, and with the committee in a good financial position (due, paradoxically, to the pandemic: we were unable to spend money on our usual support of meetings). So all the best to them in the future.

Rather than try to give a summary, I will concentrate on one topic which, for me, was the highlight: several talks around the Hall–Paige conjecture.

To begin, here is a little background. Let G be a finite group. The Cayley table of G is the square array with rows and columns indexed by G, with the entry in row x and column y being the product xy. It is a Latin square: that is, every element of G occurs once in each row and once in each column.

A transversal of a Latin square L of order n is a set of n cells, one in each row, one in each column, and one containing each symbol. A partition of the cells into transversals is called an orthogonal mate of L, since if we choose n new symbols and associate one with each part of the partition, putting it in the cells in that part, we obtain a Latin square orthogonal to L.

A complete mapping on G is a bijection φ from G to itself with the property that the map ψ defined by ψ(x) = xφ(x) is also a bijection.

The commutator subgroup (or derived group) of G is the subgroup generated by all commutators x−1y−1xy, for all x,y in G. It is the set of elements mapped to the identity in any homomorphism from G to an abelian group.

For a prime p, a Sylow p-subgroup of G is a subgroup whose order is a power of p and whose index is coprime to p. By Sylow’s Theorem, Sylow subgroups always exist, and any two are conjugate, and hence isomorphic.

With that background, I can state the Hall–Paige conjecture. It states that the following five conditions for a finite group G are all equivalent:

  • The Cayley table of G has a transversal.
  • The Cayley table of G has an orthogonal mate.
  • G has a complete mapping.
  • The product of the elements of G (in any order) belongs to the commutator subgroup.
  • The Sylow 2-subgroups of G are either trivial (this means that G has odd order) or not cyclic.

The equivalence of the first three conditions is straightforward. I will illustrate with one of the implications. Suppose that G has a complete mapping φ. Then the set of cells in row x and column φ(x) for all x is a transversal, since the column numbers and the symbols ψ(x) each comprise the set G with no repetitions.

The equivalence of the fourth and fifth conditions is almost as simple, if you know Burnside’s Transfer Theorem, a result in group theory more than a century old.

Hall and Paige proved that any of the first three conditions implies either of the last two. The conjecture, thus, asserts that the reverse implication also holds.

As a side note, I observed that the combinatorialists in Lancaster who spoke about this only used the first and fourth of the above conditions. This was a little strange, since firstly the existence of an orthogonal mate is superficially stronger than that of a transversal, and in more general situations these conditions are no longer equivalent, so that establishing the second would be a bigger result; and secondly, the fifth condition seems so obviously easier to work with than the fourth.

Anyway, Hall and Paige proved some cases of the reverse implication. Then no substantial progress happened until 2009. In that year,

  • Stuart Wilcox reduced the problem to the case where the group G is a non-abelian simple group, and settled it for the groups of Lie type except for the Tits group (the alternating groups had already been done by Hall and Paige);
  • Tony Evans did the Tits group and 25 of the sporadic groups;
  • John Bray knocked off the final sporadic group, the fourth Janko group.

The work of Wilcox and Evans was published in the Journal of Algebra that year. Bray’s work languished as folklore until 2020. I needed the result to prove that groups of simple diagonal type with more than two factors in their socle are non-synchronizing, so I persuaded John to write it up and include it in the paper I was writing.

In the last two years, there have been two dramatic developments in the story: two new “proofs” of the conjecture. (The quotes are because, if my understanding of the proofs is correct, each proves the result only for “sufficiently large” groups, and it may be that “sufficiently large” is too large for us to finish the proof by examining “small” cases.) Each proof gives a very substantial strengthening of the conjecture.

Last year, Sean Eberhard, Freddie Manners and Rudi Mrazović posted on the arXiv a paper in which they used analytic number theory to obtain an estimate for the number of transversals of the Cayley table of a group. Their estimate shows that the number is positive for sufficiently large groups.

This year, Alp Müyesser and Alexey Pokrovskiy posted on the arXiv a proof of a generalization of the Hall–Paige conjecture for large groups (concerning the existence of complete mappings on large subsets of the group), using methods of probabilistic combinatorics.

Now three of these five spoke at the BCC. Alexey gave a plenary talk on “Rainbow subgraphs and their applications”. His paper in the conference book covered this topic in generality, but in his talk he focused on the Hall–Paige application, and explained in detail what goes on in that proof.

Alp Müyesser talked about how he and Pokrovskiy have used the probabilistic methods to solve a problem of Evans for sufficiently large groups. A group is called harmonious if its elements can be arranged in a cyclic sequence g0, g1, …, gn−1 such that products of consecutive pairs of terms are all distinct, and so also make up the whole group without repetition. It is easy to see that the Hall–Paige conditions are necessary. But there is another obstruction: elementary abelian 2-groups. (In such a group, the identity is never the product of two distinct elements). They have proved that, with these exceptions, and if the group is sufficiently large, then such an arrangement can be found.

Freddie Manners spoke in the minisymposium on additive combinatorics. Kwan has proved that almost all Latin squares have transversals; Manners was able to adapt the methods used for Hall–Paige, together with a notion of quasirandomness for Latin squares based on one by Tim Gowers for groups, to give a new proof and to count the number of transversals asymptotically, extending his earlier work with Eberhard and Mrazović.

A related highlight is one I was forced to miss, since I was speaking in a different minisymposium at the time. Richard Montgomery, in the extremel combinatorics symposium, talked about his proof of the Ryser and Brualdi conjectures, stating that a Latin square of order n always has a partial transversal of size n−1, and indeed has a transversal if n is odd. (Stein’s name is also attached to these conjectures, but I am not sure of exactly who conjectured what.)

Some final observations and problems.

  • The relationship between transversals and orthogonal mates for Cayley tables of groups fails for general Latin squares, but finding estimates for the number of orthogonal mates under suitable conditions may be worth a look. Additionally, it should allow the number-theoretic proof to be parlayed into an estimate for the number of orthogonal mates of a Cayley table.
  • Since I have read in detail at least one part of the group-theoretic proof of Hall–Paige, I have been left with the feeling that transversals are very easy to find and prolific. Is it possible to extract estimates from the group-theoretic proof?
  • Gowers’ notion of quasirandomness for groups involves the degrees of the non-principal irreducible characters of the group being large. Now there is a character theory of quasigroups (algebraic structures whose Cayley table is an arbitrary Latin square) developed mainly by Jonathan Smith. Now for almost all quasigroups, the character degrees are 1 and n−1. This suggests a possible different approach to quasirandomness for Latin squares.
Posted in events, exposition, open problems | Tagged , , , , , , , , , , , | 5 Comments

Why I’d like to see this solved

I am aware that quite a number of people have been captivated by the problem I posed. So here is the motivation for it, with some additional remarks and commennts. First, to repeat the problem:

Problem: Let n be a positive integer. Show that there exist subsets A1, A2, … An of {1,2,…n} with the properties

  • |Ai| = φ(i) for i = 1,2,…,n;
  • if lcm(i,j) ≤ n, then Ai and Aj are pairwise disjoint, where lcm denotes the least common multiple.

This arises in the “graphs on groups” project. The enhanced power graph of a finite group G is the graph whose vertices are the elements of G, two vertices joined if they generate a cyclic group. Now it is easy to see that any complete subgraph of the enhanced power graph of G is contained in a cyclic subgroup of G. So the first part of the following theorem is clear.

Theorem:

  • The clique number of the enhanced power graph of G is equal to the largest order of an element of G.
  • If the answer to the problem is affirmative, then the chromatic number of the enhanced power graph is also equal to the largest order of an element of G; in other words, this graph is weakly perfect.

We prove the second part by making use to a supposed solution to the problem. We let n be the largest order of an element of G, and use the elements 1,2,…n as colours. We will assign the elements of the set Ai as colours for the elements of order i. If two elements of the same order i are joined, they generate the same cyclic group; this cyclic group has φ(i) generators, and so we have enough colours to give them all different colours. Elements of order i in a different cyclic subgroup are not joined to these ones, and so we can re-use the same colours for them. Now, if two elements of different orders i and j are joined, they lie in a cyclic group whose order is the least common multiplie of i and j; this lcm is at most n, so the colour sets Ai are disjoint. Thus we have a proper colouring with n colours. (The chromatic number cannot be smaller since there is a clique of size n.)

We have proved a little more. For any value of n for which the problem has a positive solution, the enhanced power graph of a group whose largest element order is that value of n is weakly perfect. So you will have to go quite far to look for a counterexample.

You might wonder whether we could get the conclusion of the theorem more easily. After all, for most groups, the set of element orders is not the first n natural numbers. Indeed, we could ask:

Problem: Determine the finite groups in which the set of element orders is {1,2,…,n} for some n; in particular, determine the n which can occur.

There can only be finitely many such values of n. This can be seen by considering the Gruenberg–Kegel graph, whose vertices are the prime divisors of the group order, two vertices p and q joined if the group contains an element of order pq. Now it is known that the GK graph of a finite group has at most six connected components. But for a group satisfying our conditions, any prime in the interval (n/2,n] is an isolated vertex of the graph. Modern strengthenings of Bertrand’s postulate show that the number of primes in this interval grows with n.

Indeed, the hypothesis of this question determines the GK graph: the vertices are the primes up to n, two vertices joined if their product does not exceed n.

One could also ask this question for infinite torsion groups. I don’t know what happens for these.

However, this may not help us very much. Of several approaches I tried to solve the problem, the one I found most promising included the observation that there is no difficulty about choosing the sets Ai for i > n/2; for the only sets Aj we have to avoid correspond to divisors j of i, and there are enough points available to do this. (Similarly, the sets Ai for i < √n are not a problem; they must be pairwise disjoint, but there are enough points for all of them. It is the block in the middle where the problem lies.)

So omitting some primes greater than n/2 will not make the problem easier.

We see, incidentally, that groups with the property that the maximal order of an element coincides with the exponent (so that the orders are just the divisors of n) will not be a problem. Indeed, for any finite group G, there is an integer k such that Gk has this property. But I can’t find a way to exploit this observation.

Posted in doing mathematics | Tagged , , | 3 Comments

A request

In 1956, Helmut Wielandt proved that a primitive permutation group whose degree is twice a prime p is doubly transitive, unless p has the form 2a2+2a+1, in which case the group has rank 3, and its subdegrees are a(2a+1) and (a+1)(2a+1). The only examples known to Wielandt at the time were the symmetric and alternating groups of degree 5 acting on the 2-element subsets of {1,…,5}. Now, using the Classification of Finite Simple Groups, we know that there are no others.

Wielandt’s proof falls into two parts. First it is shown that such a group has rank 3 and the permutation character is the sum of irreducible characters of degrees 1, p−1 and p. The second part of the proof starts from this decomposition and finds the form for p and the subdegrees.

As noted above, the theorem Wielandt published is now superseded. However, the second part of his proof gives a combinatorial result, using neither the primality of p nor the existence of a primitive permutation group. It is a theorem about strongly regular graphs: these are regular graphs (so the all-1 vector is an eigenvector of the adjacency matrix whose eigenvalue is the valency), with the property that on the space orthogonal to the all-1 vector the adjacency matrix has just two eigenvalues. The result is stated as Theorem 2.20 in my book with Jack van Lint. It says:

Theorem Suppose that a strongly regular graph on 2n vertices has the property that the restriction of the adjacency matrix to the space orthogonal to the all-1 vector has eigenvalue multiplicities n−1 and n. Then, up to complementation, either

  • the graph is the disjoint union of n complete graphs of size 2; or
  • the parameters are those given by Wielandt, for some integer a.

There are a number of examples of the second case beyond those of degree 10 (the line graph of K5 and its complement the Petersen graph; for example, the strongly regular graphs on 26 vertices with valency 10.

Now my question is this:

Question Who first noticed that Wielandt’s argument gave this more general result?

The reference given above is the earliest one I know, but it seems unlikely that we were the first to see this.

Posted in history | Tagged , , | Leave a comment

I’d like to see this solved

Here is a problem that I would really like to see solved. I have spent quite a bit of time on it myself, and have suggested it to a few other people, but it still resists all attacks, though it looks relatively simple.

As background, recall Euler’s totient function φ, defined for positive integers n by the rule that φ(n) is the number of integers in the interval from 0 to n−1 which are coprime to n. The one fact I need is that, if you sum φ(d) over the divisors d of n, the result is n. This is because φ(d) is the number of integers x in the interval from 0 to n−1 for which the greatest common divisor of x and n is n/d; and for every integer in this interval, gcd(n,x) is some divisor of n.

Now here is the problem.

Problem: Let n be a positive integer. Show that there exist subsets A1, A2, … An of {1,2,…n} with the properties

  • |Ai| = φ(i) for i = 1,2,…,n;
  • if lcm(i,j) ≤ n, then Ai and Aj are pairwise disjoint, where lcm denotes the least common multiple.

The conditions of the problem require, in particular, that the sets Ai for which i divides n should be pairwise disjoint; but by our earlier remark, there are just enough points to permit this.

I have tried several different attacks, which I won’t detail here; I don’t want to lead you into a blind alley. But I will make one remark.

One obvious construction to try is the greedy algorithm. Choose the sets A1, A2, …, in turn. When choosing Ai, we must avoid points lying in any Aj with j ≤ i and lcm(i,j) ≤ n; continue through the natural numbers until φ(i) points have been chosen. We win if no number greater than n needs to be chosen. This is very simple to implement computationally. It has been checked up to n = 1000 and succeeds in all cases.

I certainly feel that if the greedy algorithm succeeds in solving a problem, that problem should be easy!

Posted in doing mathematics, open problems | 9 Comments