Home » Subject » Group Theory

Hall-Paige conjecture (Solved)

Importance: High ✭✭✭
Author(s): Hall, Marshall
Paige, Lowell J.
Subject: Group Theory
Keywords: complete map
finite group
latin square
Recomm. for undergrads: no
Posted by: mdevos
on: October 21st, 2007
Solved by: Wilcox, Stewart

A complete map for a (multiplicative) group $ G $ is a bijection $ \phi : G \rightarrow G $ so that the map $ x \rightarrow x \phi (x) $ is also a bijection.

Conjecture   If $ G $ is a finite group and the Sylow 2-subgroups of $ G $ are either trivial or non-cyclic, then $ G $ has a complete map.

The motivation for this problem comes from the study of Latin Squares. Call a collection of $ k $ cells from a $ k \times k $ matrix a transversal if there is exactly one cell from each row and one from each column, and say that a transversal is latin if no two of its cells contain the same element. The multiplication table of every (finite multiplicative) group $ G $ is a latin square, and we see that $ G $ has a latin transversal if and only if it has a complete map (the cells indexed by $ g, \phi(g) $ form the transversal). If we do have such a latin transversal, then for every $ h \in G $, the map $ \phi_h : G \rightarrow G $ given by $ \phi_h(g) = \phi(g) h $ is also a latin transversal, and the collection $ \{ \phi_h : h \in G\} $ gives us $ |G| $ pairwise disjoint latin transversals in the multiplication table of $ G $. This is precisely equivalent to the existence of a latin square orthogonal to this multiplication table. Thus, the above conjecture may be restated as follows.

Conjecture  (Hall-Paige version 2)   If $ G $ is a finite group and the Sylow 2-subgroups of $ G $ are either trivial or non-cyclic, then there is a latin square orthogonal to the multiplication table of $ G $.

Next, let us show that the assumption in the conjecture on Sylow 2-subgroups is necessary, so let $ G $ be a group with nontrivial cyclic 2-Sylow subgroup $ H $. Under these assumptions, it follows from a theorem of Burnside that there exists a normal subgroup $ N $ (of odd order) so that $ G/N \cong H $. Let $ \nu : G \rightarrow G/N $ be the canonical homomorphism and let $ t $ be the unique element in $ G/N $ of order 2. Now, suppose (for a contradiction) that $ G $ has a complete map $ \phi : G \rightarrow G $ and consider the three families $ \{\nu(g)\}_{g \in G} $, $ \{\nu(\phi(g))\}_{g \in G} $, $ \{\nu(g \phi(g))\}_{g \in G} $, and their products $ a = \prod_{g \in G} \nu(g) $, $ b = \prod_{g \in G} \nu(\phi(g)) $, and $ c = \prod_{g \in G} \nu(g \phi(g)) $. For every $ g \in G $ we have $ \nu(g) \cdot \nu(\phi(g)) = \nu( g \phi(g)) $, so taking the product of all of these equations we get $ ab=c $ (since $ G/N $ is abelian, the order doesn't matter here). However, every element in $ G/N $ occurs exactly $ |N| $ times in each of these families, and it follows from this that $ a = b = c = t $, giving us a contradiction.

Hall and Paige proved their conjecture for solvable groups, and for the alternating and symmetric groups. More recently, a number of authors have studied this problem, establishing a number of partial results. Dalla Volta and Gavioli [DG3] have shown that a minimal counterexample to the conjecture is either almost simple, or it has a unique central involution and its derived subgroup is is a quasi-simple group of index 2. The following list contains a number groups for which the problem is solved.

    \item $ Sz(q) $, $ SU(3,q^2) $, $ PSU(3,q^2) $ where $ q=2^n $ and $ n>1 $ [D] \item $ PSL(2,q) $, $ PGL(n,q) $, $ GL(n,q) $ with $ q $ odd [DG1] [DG2] \item $ O(G)Q $ where $ O(G) $ is the largest normal subgroup of odd order and $ Q $ is a Frobenius complement [D] \item $ SL(2,q) $ [E2] [E3] [S] \item $ SL(n,q) $, $ PSL(n,q) $, $ GL(n,q) $, $ PGL(n,q) $ with $ q $ even and $ (n,q) \neq (2,2) $ [DG1] \item Matthieu groups and their automorphism groups [DG1]

The Hall-Paige conjecture is rather trivial for abelian groups, but Snevily has suggested an interesting conjecture concerning latin transversals in submatricies of the latin squares given by multiplication tables in abelian groups. There is a common generalization of these two conjectures highlighted below. I (M. DeVos) have no reason to suggest this conjecture other than its natural appearance, so it may well be false already for some small examples.

Conjecture   Let $ G $ be a group and let $ A,B $ be subsets of $ G $ with $ |A| = |B| = k $. Then there exists an ordering $ \{a_1,\ldots,a_k\} $ of $ A $ and $ \{b_1,\ldots,b_k\} $ of $ B $ so that the products $ a_i b_i $ are distinct unless there is a subgroup $ H \le G $ so that the Sylow 2-subgroups of $ H $ are nontrivial and cyclic, and there exist $ g,g' \in G $ so that $ A = gH $ and $ B = Hg' $.

Related problems

Snevily's conjecture

Bibliography

[W] Wilcox, Stewart, Reduction of the Hall-Paige conjecture to sporadic simple groups, J. Algebra 321 (2009), no. 5, 1407--1428. MathSciNet

[DG1] F. Dalla Volta, N. Gavioli, Complete mappings in some linear and projective groups, Arch. Math. (Basel) 61 (1993) 111--118. MathSciNet.

[DG2] F. Dalla Volta, N. Gavioli, On the admissibility of some linear and projective groups in odd characteristic, Geom. Dedicata 66 (1997) 245--254. MathSciNet.

[DG3] F. Dalla Volta, N. Gavioli, N. Minimal counterexamples to a conjecture of Hall and Paige. Arch. Math. (Basel) 77 (2001), no. 3, 209--214. MathSciNet.

[D] O. M. Di Vincenzo, On the existence of complete mappings of finite groups. Rend. Mat. 9, 7, 189--198 (1989). MathSciNet.

[E1] A.B. Evans, The existence of complete mappings of finite groups, Congr. Numer. 90 (1992) 65--75. MathSciNet.

[E2] A.B. Evans, The existence of complete mappings of $ SL(2,q) $, $ q\equiv 1\,\roman{mod}\,4 $, Finite Fields Appl. 7 (2001) 373--381. MathSciNet.

[E3] A. B. Evans, The existence of complete mappings of $ {\rm SL}(2,q) $, $ q\equiv 3 $ modulo 4. Finite Fields Appl. 11 (2005), no. 1, 151--155. MathSciNet.

*[HP] M. Hall, L. J. Paige, Complete mappings of finite groups, Pacific J. Math. 5 (1955) 541--549. MathSciNet.

[S] D. Saeli, Saeli applicazioni complete e rapporto incrementale in doppi cappi. Riv. Mat. Univ. Parma 15, 4, 11--117 (1989). MathSciNet.

[WV] M. Vaughan-Lee, I. M. Wanless, Latin squares and the Hall-Paige conjecture. Bull. London Math. Soc. 35 (2003), no. 2, 191--195. MathSciNet.


* indicates original appearance(s) of problem.
add new comment