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

A problelm

Given a finite permutation group G on a set X, the permutation character π of G is the function on G mapping an element g to its number of fixed points in X. This is a character of G, the function giving the trace of a matrix representation of G (in this case, the representation by permutation matrices). So it can be decomposed into irreducible characters of G; say,

π = ∑miχi.

Now the number of orbits of G is equal to the multiplicy m0 of the trivial character χ0 in this expression (by the Orbit-Counting Lemma), while the rank of G (the number of orbits on X2) is equal to the sum of squares of the multiplicities mi.

Thus, the permutation character is the sum of the trivial character and one non-trivial irreducible if and only if G is doubly transitive. An old result asserts that the permutation character cannot have the form χ0+mχ for a non-trivial irreducible χ if m > 1.

The proof goes like this. By Jordan’s Theorem, since G is transitive, it contains an element g with no fixed points. Now the expression for π shows that χ(g) = −1/m. But any character value must be an algebraic integer, and so an integer if it is also rational, as this value is.

Now I have described before the notion of coherent configuration, a combinatorial gadget which describes (among other things) the orbits of a permutation group G on the set of ordered pairs. The relation matrices for the group orbits span an algebra (over the complex numbers) which is a direct sum of complete matrix algebras of dimensions equal to the multiplicities mi, this matrix algebra occurring with multiplicity in the regular representation equal to the degree of the character χi. For a general coherent configuration, we have a similar algebraic theory, but we do not have the group to give us these numbers.

Problem Is there a coherent configuration which “looks like” one coming from a group whose permutation character has this forbidden form, that is, the sum of a 1-dimensional algebra and a complete matrix algebra of degree greater than i?

We no longer have Jordan’s theorem to help us. I suspect that there is a simple algebraic argument which substitutes, but I cannot at the moment see how it would go. Any ideas?

Posted in open problems | Tagged , | 2 Comments

Some things get better

Amid the gloom, we went for a short walk in Dura Den, one of the most scenic parts of Fife. At the end of the den is the village of Pitscottie, with the White Chimneys café. To our pleasure and delight we found that, following the relaxation of pandemic rules, it has fully reopened, and is once again doing breakfast, including absolutely excellent smoked salmon from St Monans.

Posted in Uncategorized | Tagged , | Leave a comment

St Andrews Combinatorics Day

We are having a home-grown combinatorics day in St Andrews next Tuesday, 24 May. Here is the programme. Come along if you are nearby on the day. It will be in Lecture Theatre B in the Mathematical Institute.

  • 11-11:30 Rosemary Bailey: Diagonal structures and beyond
  • 11:40-12:10 Ashley Clayton: Combinatorial results for subdirect products
  • 12:20-12:50 James East (Western Sydney University): How many pyramids are there?
  • 12:55-1:40 Lunch (Room 1A, Mathematics Institute)
  • 1:40-2:10 Peter Cameron: Conjugacy class graphs on groups
  • 2:20-2:50 Sophie Huczynska: Constructing generalised difference families – how cyclotomy can help us
  • 3-3:30 Laura Johnson: Applications of DPDFs and EPDFs
  • 3:35- 4:00 Tea/coffee (1A)
  • 4:00-4:30 Jack Southgate: Global area rigidity of generic hypergraph frameworks
  • 4:40- 5:10 Nik Ruskuc: Counting subpowers of unary algebras

Please let Nik or Sophie know if you are coming, and in particular if you will want catering.

Posted in events | Leave a comment

John McKay

I learned only yesterday that John McKay died a month ago.

John McKay made the kind of contribution to the subject that most mathematicians can only dream of, in part because of his wide-ranging interests and keen observation. He was also a pioneer of the use of computers in mathematics: he and Graham Higman constructed two of the sporadic finite simple groups, Janko’s third group and Held’s group, in the early 1970s.

John is best known for two stunning observations.

The one with the most impact, and the easiest to state, was probably noticing that the degree of the smallest non-trivial linear representation of the Monster (which is 196883) is one less than the first non-trivial Fourier coefficient of the classical modular function. (Googling “196884=196883+1” gives 1200 hits.) It was remarked at the time that few mathematicians were familiar with both of these topics, which appear at first sight to be completely unconnected. John Conway named this monstrous moonshine, and it led to connections with vertex operator algebras and a Fields medal for Richard Borcherds.

The second big conjecture concerned the binary rotation groups (that is, the double covers of the finite rotation groups in Euclidean 3-space obtained by pulling them back to the 2-dimensional complex unitary group by the two-to-one homomorphism to the real 3-dimensional orthogonal group. Such a group has a natural 2-dimensional unitary representation χ. If we form a graph whose vertices are the irreducible representations, each vertex labelled with the degree, then the result is connected, and the sum of the labels on the neighbours of a vertex is twice the label of a vertex. Thus the graph has greatest eigenvalue 2, and is an extended Dynkin diagram of type ADE. I have described this in my series about the ADE affair.

But there is more. I am currently at a workshop at the Isaac Newton Institue on Counting conjectures and beyond in representation theory. Another observation of John McKay was at the origin of this field: he observed that, in the simple groups G he examined, if p is prime, then the number of irreducible representations of G of degree coprime to p is equal to the corresponding number for the normaliser of a Sylow p subgroup of G. The conjecture was later extended to all finite groups, and a lot of progress has been made, in particular, the conjecture is true for soluble groups. It has also taken its place among several further conjectures with a similar “local-to-global” form. However, I know much less about this, so I will say no more.

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

Peter Neumann’s 3p paper

In 1955, Helmut Wielandt published a paper proving the following theorem:

Let G be a primitive permutation group of degree 2p, where p is a prime greater than 3, which is not doubly transitive. Then p = 2a2+2a+1 for some positive integer a, and G has rank 3 and subdegrees a(2a+1) and (a+1)(2a+1).

The proof involved first showing that the permutation character decomposes into three irreducible constituents, the principal character and characters of degree p−1 and p, followed by analysis of what we would now call the coherent configuration associated with G. Wielandt was a student of Schur, and had essentially stripped away the algebraic part of the theory of Schur rings to leave a purely combinatorial object.

Indeed, the second part of Wielandt’s argument can be rewritten to show the following result (I am not sure who originally proved this, but you can find it as Theorem (2.20) in my book with Jack van Lint):

Let Γ be a strongly regular graph on 2n vertices whose eigenvalues have multiplicities 1, n−1 and n. Then, up to complementation, either Γ consists of n pairwise disjoint edges, or n = 2a2+2a+1 for some positive integer a, and Γ has valency a(2a+1).

This result is much more general; the only examples satisfying Wielandt’s hypothesis are the symmetric and alternating groups of degree 5 acting on the ten unordered pairs from 5 (we need the Classification of Finite Simple Groups to show there are no more, a tool which of course was not available to Wielandt), whereas there are many strongly regular graphs satisfying the hypotheses (after the Petersen graph of degree 10 there are several of degree 26, etc.)

But I am getting out of historical order here.

When I arrived in Oxford as a doctoral student in 1968, Peter Neumann gave me Wielandt’s book Finite Permutation Groups to read, and then gave me a copy of a typescript over 50 pages long he had just finished, proving an analogue of Wielandt’s theorem for primitive groups of degree 3p.

In the time since Wielandt’s paper, Walter Feit had proved a theorem about degrees of linear groups which greatly reduced the work required to decompose the permutation character. But the second combinatorial part is much more difficult, since there are many possible decompositions, including some in which a character has multiplicity greater than 1, and very detailed analysis is required in each case. The final result has not a single quadratic expression for p, but three different expressions, together with three exceptional values.

Leonard Scott, who has a role in this story (as he had proved similar results), kindly sent me a scan of the typescript, mine having been lost many years ago, together with scans of various items showing that he and Peter had planned a collaboration on this material which never came about. The paper remained unpublished and virtually inaccessible.

Until now.

I have just posted on the arXiv a version of the paper re-typed in LaTeX: it is 2204.06926.

This is motivated in part by the fact that this paper was written at the time when the combinatorial methods in permutation groups developed by Wielandt and Donald Higman were very similar to those used by statisticians (who, following R. C. Bose, called them association schemes) and mathematicians/computer scientists led by Boris Weisfeiler in the former Soviet Union working on graph isomorphism (who called them cellular algebras). Peter’s paper gives a very nice exposition of this theory.

The other reason is that St Andrews undergraduate Marina Anagnostopoulou-Merkouri is working on extracting purely combinatorial information from the paper, similar to the result on strongly regular graphs which derives from Wielandt’s arguments, and needs to be able to refer to the paper.

It should be said that the actual theorem proved in the paper is, like Wielandt’s, superseded by consequences of the Classification of Finite Simple Groups. For example, in the 1980s, Bill Kantor, and independently Martin Liebeck and Jan Saxl, found (in some sense) all the primitive permutation groups of odd degree, and their results show that the short list of examples in Peter Neumann’s paper is complete.

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

Peter Neumann memorial meeting

On Saturday, I was in Oxford for a memorial meeting for Peter Neumann, organised by Chris Hollings for the British Society for the History of Mathematics (of which Peter was a past president). It was a hybrid meeting, with half the attendees there in person, in a lovely little seminar room in the Queen’s College, and the others attending by Teams (with lousy sound) or YouTube (with a small delay, and no possibility to ask questions). Indeed, at one point, someone pressed the wrong button and the speaker’s recent words came booming out of the sound system.

It was an interesting and varied meeting. Three of the talks could be said to be specifically about Peter: Raymond Flood gave a tribute, Cheryl Praeger talked about his contributions to and influence on group theory, and Tony Mann spoke on working with Peter on matters related to William Burnside (including editing his collected works). I talked about Peter’s unpublished manuscript on primitive permutation groups of degree 3p written in 1969, which was the first thing (apart from Wielandt’s book) I read as his student in Oxford. (I hope to say more about this shortly.) Adrian Rice looked at Peter’s book reviews and compared them to those of Augustus De Morgan. Martin Bridson gave a short closing address.

Most of the other talks were on things that would have been interesting to Peter as a mathematician, historian, and person with wide interests: these included the evidence for ancient Egyptian mathematics, the challenges issued to John Wallis by Pierre de Fermat and their reception, the library of several thousand mathematics books collected by Charles Hutton and its eventual fate, Mary Somerville engaging with quaternions while in her 90s, a summary of algebra in the USA in the early 20th century, and how mathematics (specifically calculations related to the “problem of the points” discussed by Fermat and Pascal) influenced questions of contracts and inheritance in English and French law.

Perhaps the best line of the day, quoted by Adrian Rice, was a comment from Peter to someone who had sent him something to read, which went something like this: “Your second sentence is the longest I have read, except for some by Frobenius, who was always happy to leave the verbs until Volume 3.”

It was especially nice to see Sylvia there. She had been unsure of attending because of a contact with someone who tested positive for Covid; fortunately Sylvia herself was negative and so was able to come. We had some small business to talk about, but also the opportunity to chat.

Posted in events, history | Tagged , | 1 Comment

Taylor series

Today, XKCD, with tongue in cheek, is saying that “The Taylor series should have been canceled after the first term”.

After a flying visit to London (more about that shortly), I am reminded again that at least the second term of the Taylor series impinges on real life.

My house in London is in a courtyard entered through double gates hinged at the outside. By entering a code, you can open either a single or a double gate. The gates are rather slow to open, and of course I get impatient.

Assume for simplicity that the width of each gate is one unit of length, and that the gates open at 1 radian per unit of time. Now, if I open a single gate, then after time t, the gap for me to get through is 2 sin t/2, whose Taylor series is t+…; while if I open both gates, the gap is 2(1−cos t), whose Taylor series is t2+…

I have watched people waiting for the double gates to open wide enough for them to slip through, and grumbling about the slowness. Of course I feel a little smug!

Posted in Uncategorized | Tagged , | 4 Comments

An O’Nan-Scott note

My old friend Leonard Soicher is visiting St Andrews this week, having made a better job of retiring than I did. Today he gently took me to task for using the expression “simple diagonal type” for one of the types in the O’Nan–Scott Theorem in a manner slightly different from the official one. But there is an interesting story here, which I will tell.

The most commonly used type division in this theorem (which describes primitive permutation groups in terms of their socle) is the one by Cheryl Praeger. You can find a clear exposition of it in a post by Michael Giudici on the SymOmega blog.

Before getting to the point at issue, some preliminaries.

I like, where possible, to define permutation properties in a fairly uniform way, using the formula “A permutation group has property X if it preserves no non-trivial A-structure”. Here a trivial structure is one which is invariant under the full symmetric group on the domain. So, for example:

  • If A-structure is “subset”, the trivial subsets are the empty set and the entire domain, and so the corresponding X is “transitive”.
  • If A-structure is “partition”, the trivial partitions are the partition into singletons and the partition with a single part, and so the corresponding X is “primitive”.
  • If A-structure is “graph”, the trivial graphs are complete and null, and the corresponding X is “2-homogeneous” (or “2-set transitive”).
  • If A-structure is “digraph”, the corresponding X-structure is “2-transitive”.

A couple more in a moment. But first let me point out the problem. If the size of the domain is 2, then the only partitions are trivial ones, and so the trivial group would qualify as “primitive”. You might like to stop and think whether you want that or not.

So here are a couple more. If A-structure is “Hamming graph”, then X is what I have called “basic”; if A-structure is “graph with clique number equal to chromatic number”, then X is “synchronizing”.

So back to group theory. Let S be a group. The holomorph of S is the semidirect product of S by Aut(S), its automorphism group. If S is the additive group of a vector space over the field of p elements, for p prime, its holomorph is the affine group on this vector space. In general, Hol(S) acts as a permutation group on S, where S acts by right multiplication and its automorphism group acts in the natural way.

The case where S has trivial centre is the one relevant here. In this case, the inner automorphism group of S is isomorphic to S. Now consider the following three actions of S on itself:

  • by right multiplication: x → xs;
  • by left multiplication by the inverse: x → s−1x (the inverse is necessary to get the action working correctly);
  • by conjugation: x → s−1xs.

It is clear that a permutation group which contains two of these actions will also contain the third. So the semidirect product of S by its inner automorphism group is isomorphic to the direct product of two copies of S (one acting on the right, the other on the left). As a passing remark, the commutativity of these two actions is equivalent to the associativity of elements of S, as you will see if you write it out.

So in this case, we can define the holomorph to be the extension of S×S by the outer automorphism group Out(S) of automorphisms modulo inner automorphisms (we already have the inner automorphisms).

Now, more generally, the “full” diagonal group Diag(S,m) is generated as a group by the right multiplications, automorphisms of S (acting simultaneously on all coordinates) and permutations of the coordinates. Subgroups of such a group containing the socle Sm are sometimes just called “diagonal groups”. It was worked out a long time ago (I am not quite sure by whom) that, if S is a non-abelian simple group, then a diagonal group with socle Sm (for m > 1) is primitive if and only if the subgroup of Sym(m) permuting the coordinates is primitive. But, warning: this is primitive in the weaker sense of not preserving any non-trivial partition; so this subgroup must be either the trivial group of degree 2, or a group which is primitive in the more usual sense.

Note that the element which interchanges the two factors in the socle acts on S as the inversion map x → x−1. So the full diagonal group is obtained from the holomorph of S by adjoining the inversion map.

Now turn back to Michael Giudici’s account. He defines a group to be of type (HS) if it is contained in the holomorph of a simple group, and of type (SD) if it is as described in the preceding paragraph (with the small modification that the group permuting the factors in the socle is primitive in the usual sense).

So it appears that two primitive groups with identical socles acting in identical ways can belong to different types in this classification depending on whether or not the inversion belongs to the group. This rather conflicts with the notion that the O’Nan–Scott Theorem classifies primitive groups by their socles.

This seems less than satisfactory to me; but perhaps I have misunderstood Cheryl’s classification.

Posted in exposition | Tagged , , , , , , | 2 Comments