The Hall–Paige conjecture

A Latin square of ordern is an n×n array of symbols from an alphabet of size n with the property that each symbol in the alphabet occurs once in each row or column. Two Latin squares L and M are orthogonal if, given symbols x and y from the alphabets of L and M respectively, there is a unique position (i,j) in the array such that Lij = x and Mij = y.

orthogonal Latin squares

The figure shows two orthogonal Latin squares, the first using the Latin alphabet {A,B,C,D}, the second the Greek alphabet {α,β,γ,δ}, superimposed in the same array. Motivated by this, a pair of orthogonal Latin squares is often called a Graeco-Latin square. Indeed, Euler first defined Graeco-Latin squares (as a technique for constructing magic squares), and then Latin squares, whose name is a back-formation.

A Latin square orthogonal to a given square L is called an orthogonal mate of L.

A source of Latin squares familiar to algebraists consists of Cayley tables of groups. The Cayley table of G is the array whose rows and columns are indexed by the elements of G, with (g,h) entry gh. (Sometimes it is more convenient to take the entry to be (gh)−1; the square obtained is equivalent to the original under a permutation of the symbols of the alphabet.)

So a very natural question is: For which groups G does the Cayley table have an orthogonal mate? This question was considered by Marshall Hall Jr and Lowell J. Paige in 1955. They proved that, if the Cayley table of G has an orthogonal mate, then the Sylow 2-subgroups of G must be either trivial (that is, G has odd order) or non-cyclic. They also conjectured that these conditions are sufficient for existence of an orthogonal mate for the Cayley table of G, and proved this for some groups, including the alternating groups.

A different language is sometimes used here. A complete mapping of G is a bijective function φ from G to itself such that the function ψ given by ψ(g) = gφ(g) is also bijective. If φ is a complete mapping on G, then the Cayley table of G has an orthogonal mate, whose (g,h) entry is gψ(h). (Given x,y in G, we need to find g,h in G such that gh = x and gψ(h) = y; this requires φ(h) = x−1y, from which h and hence g is uniquely determined.) Conversely, the existence of an orthogonal mate implies that of a complete mapping.

In 2009, there was significant progress on the conjecture, in two papers in the Journal of Algebra. Stewart Wilcox, in J. Algebra 321 (2009), 1407–1428, showed that the truth of the conjecture for all groups would follow from its proof for finite simple groups. (Burnside’s Transfer Theorem shows thath a finite simple group, other than the cyclic group of order 2, cannot have cyclic Sylow 2-subgroups, so what is required is to show that all such groups have complete mappings. This is elementary for cyclic groups of odd prime order, so we have to deal with the non-abelian simple groups.) He showed that it holds for all simple groups of Lie type, with one exception, the Tits group (the derived group of 2F4(2)) have complete mappings. Anthony Evans, in J. Algebra 321 (2009), 105–116, handled the Tits group, and also all of the sporadic groups except the Janko group J4. The final sporadic simple group was dealt with by John Bray, but his result remained unpublished.

Now of course it is not entirely satisfactory when the last step in the proof of a long-standing conjecture remains unpublished …

In the meantime, work on synchronization found a use for the truth of the Hall–Paige conjecture. I have described synchronization before, indeed more than once; it is a small obsession of mine now. So here is a very brief summary of all that I need.

  • A permutation group G is called synchronizing if, for any map t on the domain which is not a permutation, the semigroup generated by G and t contains a map of rank 1, that is, mapping the entire domain onto a single point.
  • A permutation group is non-synchronizing if and only if it is contained in the automorphism group of a graph, neither complete nor null, whose clique number and chromatic number are equal.
  • A synchronizing group is primitive, and a 2-transitive group is synchronizing.

So, to test whether G is synchronizing or not, we may assume that G is primitive (this means that it preserves no non-trivial equivalence relation). Primitive groups are described by the O’Nan–Scott Theorem, of which I require here just a simple version: Any primitive permutation group G satisfies one of the following:

  • G preserves a Cartesian structure, which means that it is contained in a wreath product with product action;
  • G is of affine, diagonal, or almost simple type.

The first type are not synchronizing. For such a group preserves a Hamming graph, whose vertices are all the m-tuples over an alphabet of size q, two tuples being adjacent if they agree in all but one coordinate. Such a graph contains cliques of size q (fix all but one coordinate and let the last coordinate take all possible values). It also has a colouring with q colours: take the alphabet to be an abelian group Q, and colour an m-tuple with the product of its entries in Q.

So synchronizing groups must be affine, diagonal or almost simple.

I will not here describe in detail what diagonal groups look like; here are some properties of the “three-factor” diagonal groups. Take a non-abelian finite simple group T. The group in question has minimal normal subgroup consisting of the direct product of three copies of T. To this we can adjoin automorphisms of T (acting simultaneously on the three copies) together with permutations of the three coordinates. This group acts on the set of cells of the Cayley table of G (which we take in the modified form with (g,h) entry (gh)−1, in other words, the unique k such that ghk = 1). The equation ghk = 1 is preserved by cyclic permutation of the three group elements. Now T3 acts to preserve these triples. An element t of the first factor acts by right multiplication on g and by left multiplication (by t−1) on h; the other two factors are similar but with the group elements permuted.

This group action preserves the Latin square graph associated with the Cayley table. This graph, defined for any Latin square, has as vertices the cells of the square, with two vertices adjacent if they lie in the same row, or lie in the same column, or contain the same symbol.

Now the clique number of the Latin square graph from a Latin square L of order n is n if n > 2 (a clique consisting of a row, or a column, or a symbol). The chromatic number thus cannot be less than n, and it is not hard to see that it is equal to n if and only if L has an orthogonal mate. (Use the symbols in the orthogonal mate as colours.) Thus, the Hall–Paige conjecture implies that the three-factor diagonal group built from a non-abelian finite simple group is non-synchronizing.

Encouraged by this, I was able to find a proof that diagonal groups with more than two factors are non-synchronizing. The proof for even numbers of factors is elementary, but for odd numbers of factors it uses the Hall–Paige conjecture in a similar manner to the above. The same conclusion was obtained by Pablo Spiga.

With this in hand, I managed to persuade John Bray that the time was right for him to dig out the files of his calculations and publish them. In fact, he did a lot more; he re-did the calculations, and put in several checks on their correctness (enabling different “minimal proofs” to be given). Moreover, he contributed these files to a joint paper proving the result above about synchronization, together with a weaker result covering affine groups and diagonal groups with two factors.

John’s computations are impressive. A result of Wilcox says the following. Let H be a subgroup of a group G. Suppose that H has a complete mapping. Suppose also that there are bijective mappings Φ, Ψ from the set of double cosets D = HxH of H in G such that Ψ(D) ⊆ DΦ(D) for all D. Then G has a complete mapping. To check these conditions, we have to be able to compute the collapsed adjacency matrices for all the orbital graphs for G acting on the cosets of H. (The double cosets correspond naturally to the orbital graphs for G acting on the cosets of H.)

Now the permutation representations of J4 have rather large degree. The one he uses, by conjugation on the involutions of type 2A, has degree more than a billion; so only very limited direct computation in this permutation group is possible. The most convenient representation of the group for computation is by matrices of order 112 over the field with two elements. Now since the objects we are permuting are involutions, we can look at their fixed point spaces in this 112-dimensional vector space. John is able to find a “signature” for pairs of involutions, involving four dimensions related to the pair, which distinguish all the 20 orbital graphs.

Computing all the collapsed adjacency matrices would be too big a job. But it is possible to compute those corresponding to the graphs of smallest valency. John computes three such matrices. Now the collapsed adjacency matrices span an algebra over the complex numbers; this is the image of the centraliser algebra of the permutation representation under what is sometimes called the Bose–Mesner isomorphism (in the context of permutation groups it was rediscovered by Donald Higman who notes in his paper that it had also been found by Helmut Wielandt). John verifies that the first two collapsed adjacency matrices generate an algebra of dimension 20, which thus must contain all the others (and they can easily be extracted as the matrices in the algebra having a single non-zero entry in the first row, up to scaling). The third computed matrix then can be used as a check. Now we can check from the collapsed adjacency matrices that all the orbital graphs have triangles, so the condition is satisfied with Φ and Ψ the identity map.

Another check is provided since John finds that all the double cosets apart from H itself have double coset representatives of order 3. These imply the existence of triangles (which are different from the previous in the case when the graphs are directed), verifying the condition required with Φ the identity map and Ψ(D) = D−1.

The paper is on the arXiv, here. As well as the above, it contains weaker results for affine and two-factor diagonal groups, which simplify the computational testing of these groups. For affine and two-factor diagonal groups to be non-synchronizing, it suffices to find a G-invariant graph for which the product of the clique number and independence number is equal to the number of vertices. This result were found independently by Qi Cai and Hua Zhang; so the paper ended up with five authors.

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in doing mathematics, exposition, mathematics and tagged , , , , , , , , , . Bookmark the permalink.

2 Responses to The Hall–Paige conjecture

  1. The paper has now been accepted for publication in the Charles Sims memorial issue of the Journal of Algebra. (Sims’ interests included both permutation groups and computational group theory, so the paper fits well.)

  2. Sean Eberhard says:

    I’ve been thinking a bit about the problem at the end of your paper, about whether diagonal groups with k = 2 are always non-synchronizing. It seems that the derangement graph often works, at least for small examples.

    Let T be a simple group and let G = T \rtimes (\text{Aut} T \times C_2) be the corresponding diagonal group acting on T. Suppose T acts transitively on some set \Omega. Let D\subset T be the set of all derangements in this action, and consider the Cayley graph on T generated by D. Assume that D is a characteristic subset. There is an obvious |\Omega|-colouring: colour according to the destination of any fixed \omega \in \Omega.

    The big question is whether there is an |\Omega|-clique. This is certainly the case whenever T has a regular subgroup: this settles the question for lots of small examples. Sometimes there is an |\Omega|-clique for other reasons, too. For T=A_n with its defining action, the existence of of an |\Omega|-clique is equivalent to the existence of a Latin square all of whose rows are even (I suppose these always exist, but I don’t immediately see a construction when n is twice an odd number).

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.