An asymptotic for the Hall-Paige conjecture

Asymptotic enumeration (05A16) Orthogonal arrays, Latin squares, Room squares (05B15) Arithmetic and combinatorial problems involving abstract finite groups (20D60)

Abstract: Hall and Paige conjectured in 1955 that a finite group

G

has a complete mapping if and only if its Sylow

2

-subgroups are trivial or noncyclic. This conjecture was proved in 2009 by Wilcox, Evans, and Bray using the classification of finite simple groups and extensive computer algebra. Using a completely different approach motivated by the circle method from analytic number theory, we prove that the number of complete mappings of any group

G

of order

n

satisfying the Hall--Paige condition is

(e^{- 1 / 2} + o (1)), | G^{e} x t a b |, n!^{2} / n^{n}

.

Review text

In this article, the authors give an asymptotic formula for the number of complete mappings possessed by a group satisfying the Hall-Paige condition. Given a finite group \(G\), a bijection \(\phi :G\rightarrow G\) is complete if the mapping \(g\rightarrow g\phi (g)\) is also a bijection. Complete mappings are important in the theory of Latin squares: For example, a Latin square based on a group \(G\) has an orthogonal mate if and only if \(G\) possesses a complete mapping. \textit{M. Hall} and \textit{L. J. Paige} [Pac. J. Math. 5, 541--549 (1955; Zbl 0066.27703)] showed that if \(G\) possesses a complete mapping, then \(\prod _{x\in G} x \in G'\), where \(G'\) is the commutator subgroup of \(G\). They also showed that this latter condition, known as the Hall-Paige condition, is equivalent to the condition that any \(2\)-Sylow subgroup of \(G\) is either trivial or noncyclic. (An interesting corollary is that Euler's conjecture on Latin squares of order \(4n+2\) holds for group-based Latin squares.) Hall and Paige [loc. cit.] conjectured the converse is true. This conjecture, which became known as the Hall-Paige conjecture, was eventually resolved in 2009 by Evans, Wilcox, and Bray (see [\textit{A. B. Evans}, J. Algebra 321, No. 1, 105--116 (2009; Zbl 1166.20012)] and [\textit{S. Wilcox}, J. Algebra 321, No. 5, 1407--1428 (2009; Zbl 1172.20024)]) by reducing the problem to simple groups followed by an arduous systematic elimination of possible minimal counterexamples. A full discussion can be found in [\textit{A. B. Evans}, Orthogonal Latin squares based on groups. Cham: Springer (2018; Zbl 1404.05002)]. The authors' results suggest another, largely different approach to proving the Hall-Paige conjecture. Using a method motivated by the circle method of analytic number theory, the authors show that if \(G\) is a group of order \(n\) satisfying the Hall-Paige condition, then the number of complete mappings of \(G\) is \[ (e^{-1/2}+o(1))|G^{\mathrm{ab}}| n!^2/n^n, \] where \(G^{\mathrm{ab}}=G/G'\). This count implies the Hall-Paige conjecture for sufficiently large groups, leaving relatively few simple groups to check. The asymptotic count of complete mappings is a corollary of the following result on permutation configurations proved by the authors: Let \(G\) be a group of order \(n\) and let \(f:\{1,\dots ,n\}\rightarrow G\) be a function such that \[ \prod_{i=1}^n f(i)=\prod_{x\in G} (\mathrm{mod}\ G'). \] Then the number of solutions to \(\pi_1\pi_2\pi_3=f\) with \(\pi_1,\pi_2,\pi_3:\{1,\dots ,n\}\rightarrow G\) bijections is \[ [\exp(-\mathrm{coll}(f)/n^2)+o(1)]|G^{\mathrm{ab}}| n!^3/n^n, \] where \(\mathrm{coll}(f)\) is the number of collisions in \(f\).

Recommendations

Cites work

Cited in

(18)

This page was built for publication: An asymptotic for the Hall-Paige conjecture

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2671901)