For a finite abelian group GG of order nn with ∑x∈Gx=0\sum_{x\in G}x=0 (in particular G=Z/nZG=\mathbb{Z}/n\mathbb{Z} for odd nn), the number s(G)s(G) of ordered pairs of bijections π1,π2 ⁣:{1,…,n}→G\pi_1,\pi_2\colon\{1,\dots,n\}\to G whose pointwise sum π1+π2\pi_1+\pi_2 is again a bijection is known to equal (e−1/2+o(1)) n!3/nn−1(e^{-1/2}+o(1))\,n!^3/n^{n-1}. Divided by n!n!, this count is the number of complete mappings (orthomorphisms) of GG and the number of transversals of the Cayley-table Latin square of GG; for G=Z/nZG=\mathbb{Z}/n\mathbb{Z} it is also the number of ways to place nn mutually nonattacking semiqueens (chess pieces attacking along rows, columns, and diagonals of one chosen slope only) on an n×nn\times n toroidal chessboard. The problem is to determine the error term hidden in the o(1)o(1): prove a power-saving refinement s(G)=(e−1/2+O(n−δ)) n!3/nn−1s(G)=(e^{-1/2}+O(n^{-\delta}))\,n!^3/n^{n-1} for some explicit δ>0\delta>0 (uniformly in GG, or with explicit dependence on the invariant factors of GG), or show that no power saving holds by identifying the true scale of the discrepancy, and, optionally, determine lower-order terms if an asymptotic expansion exists. All known proofs, and all later extensions (even-order groups, nonabelian groups, quasirandom Latin squares), stop at the leading constant.

Background

A complete mapping\textit{complete mapping} (also called an orthomorphism\textit{orthomorphism}) of a group GG is a bijection σ ⁣:G→G\sigma\colon G\to G such that x↦σ(x)−xx\mapsto\sigma(x)-x is also a bijection; equivalently, the addition table of GG (a Latin square, i.e. an n×nn\times n array whose rows, columns and symbol sets are each all of GG) contains a transversal\textit{transversal} — a selection of nn entries using every row, every column, and every symbol exactly once. For G=Z/nZG=\mathbb{Z}/n\mathbb{Z} the same objects describe arrangements of nn mutually nonattacking semiqueens\textit{semiqueens} on an n×nn\times n toroidal chessboard, where a semiqueen is a chess piece attacking along rows, columns, and diagonals of one chosen slope only, and 'toroidal' means the board wraps around at the edges. Writing s(G)s(G) for the number of ordered pairs of bijections π1,π2 ⁣:{1,…,n}→G\pi_1,\pi_2\colon\{1,\dots,n\}\to G with π1+π2\pi_1+\pi_2 also a bijection, one has s(G)=n!⋅(number of complete mappings of G)s(G)=n!\cdot(\text{number of complete mappings of }G), which is also n!n! times the number of transversals of the Cayley-table Latin square of GG; for G=Z/nZG=\mathbb{Z}/n\mathbb{Z} this is the transversal count of the cyclic Latin square with (i,j)(i,j) entry i+j mod ni+j \bmod n. If nn is even, s(Z/nZ)=0s(\mathbb{Z}/n\mathbb{Z})=0: the sum of all elements of Z/nZ\mathbb{Z}/n\mathbb{Z} is n/2≠0n/2\ne 0, while the sum of the values of π1+π2\pi_1+\pi_2 over all inputs is twice the sum of all elements, i.e. 00, so π1+π2\pi_1+\pi_2 cannot be a bijection; if nn is odd, s(G)>0s(G)>0, but estimating it is hard. Vardi conjectured in 1991 (in the cyclic group formulation) that c1 nn!2≤sn≤c2 nn!2c_1^{\,n} n!^2 \le s_n \le c_2^{\,n} n!^2 for constants c1>0c_1>0 and c2<1c_2<1 and all large odd nn; the upper bound was improved in stages (Cooper–Kovalenko, Kovalenko, McKay–McLeod–Wanless, Taranenko, Glebov–Luria) to c2=1/e+o(1)c_2=1/e+o(1), while the best lower bound for all odd nn (Cavenagh–Wanless, 2010) was exponentially far from it, and Wanless conjectured lim⁡n→∞(1/n)log⁡(sn/n!2)=−1\lim_{n\to\infty}(1/n)\log(s_n/n!^2)=-1. Eberhard–Manners–Mrazović (J. Eur. Math. Soc. 21 (2018) 441–463) settled both conjectures in a much stronger form: for G=Z/nZG=\mathbb{Z}/n\mathbb{Z} with nn odd, and more generally for every finite abelian group GG of odd order nn, s(G)=(e−1/2+o(1)) n!3nn−1.s(G)=(e^{-1/2}+o(1))\,\frac{n!^3}{n^{n-1}}. The constant e−1/2e^{-1/2} arises as a singular series\textit{singular series} — the total contribution of the 'major arcs' — in a version of the Hardy–Littlewood circle method (an analytic-number-theory technique that partitions frequency space into major arcs, evaluated exactly, and minor arcs, bounded) adapted to the group (Z/nZ)n(\mathbb{Z}/n\mathbb{Z})^n, with the Fourier transform of the indicator of the set of bijections controlled through an entropy partition of the dual group (its character group, i.e. the group of homomorphisms Gn→C×G^n\to\mathbb{C}^\times; the partition splits it into pieces according to the entropy of the corresponding characters). The published proof gives only the leading constant with an unspecified o(1)o(1) relative error; the authors state two limitations of the method: it was not known to extend to groups of even order having 2-torsion (nonzero elements of order 2), such as (Z/2Z)d(\mathbb{Z}/2\mathbb{Z})^d, and the analogous toroidal queens problem (counting solutions of the complexity-2 linear system π1+π2=π3\pi_1+\pi_2=\pi_3, π1−π2=π4\pi_1-\pi_2=\pi_4 in bijections; 'complexity' measures the degree of the Fourier/higher-order-Fourier data needed to control a linear system) is provably beyond pure Fourier analysis. Both limitations were subsequently addressed at the leading-order level: Eberhard (2017 preprint) proved the same formula for every finite abelian group with ∑x∈Gx=0\sum_{x\in G}x=0 (the sum is nonzero exactly when GG has a unique element of order 2, equivalently G≅Z/mZ×HG\cong\mathbb{Z}/m\mathbb{Z}\times H with mm even and ∣H∣|H| odd, and then s(G)=0s(G)=0 exactly), with a power-saving error term Od(n3−d)O_d(n^{3-d}) available only when four or more bijections are summed; Eberhard–Manners–Mrazović (Adv. Math. 2022) proved a nonabelian analogue (the Hall–Paige asymptotic: a finite group has complete mappings only if its Sylow 2-subgroups are trivial or noncyclic, and then the count is (e−1/2+o(1))∣Gab∣ n!2/nn(e^{-1/2}+o(1))|G^{\mathrm{ab}}|\,n!^2/n^n, where GabG^{\mathrm{ab}} is the abelianization, the largest abelian quotient of GG); and the toroidal queens count was determined as ((1+o(1)) ne−3)n((1+o(1))\,ne^{-3})^n for n≡±1(mod6)n\equiv\pm1\pmod 6 by Luria's entropy upper bound (2017) and the matching absorption lower bound of Bowtell–Keevash (2021). For the central three-summand count, however, no result in the literature improves on the o(1)o(1): no power-saving error term, no identified error scale, and no lower-order expansion is known for s(G)s(G), in contrast with the d≥4d\ge 4 case where power savings are available.

Problem Statement

Let GG be a finite abelian group of order nn with ∑x∈Gx=0\sum_{x\in G}x=0 (this includes G=Z/nZG=\mathbb{Z}/n\mathbb{Z} for odd nn and groups such as (Z/2Z)d(\mathbb{Z}/2\mathbb{Z})^d; for the remaining finite abelian groups — those with a unique element of order 2 — s(G)=0s(G)=0 identically), and let s(G)s(G) be the number of ordered pairs of bijections π1,π2 ⁣:{1,…,n}→G\pi_1,\pi_2\colon\{1,\dots,n\}\to G such that the pointwise sum π1+π2\pi_1+\pi_2 is also a bijection — equivalently, s(G)/n!s(G)/n! is the number of complete mappings (orthomorphisms) of GG and the number of transversals of the Cayley-table Latin square of GG (and, for G=Z/nZG=\mathbb{Z}/n\mathbb{Z}, the number of arrangements of nn mutually nonattacking semiqueens on an n×nn\times n toroidal chessboard). It is known that s(G)=(e−1/2+o(1)) n!3/nn−1s(G)=(e^{-1/2}+o(1))\,n!^3/n^{n-1} (for odd nn this is the published theorem of Eberhard–Manners–Mrazović; the even-order groups of this class are covered by Eberhard's unpublished extension). Determine the error term hidden in the o(1)o(1): prove that for some explicit δ>0\delta>0, s(G)=(e−1/2+O(n−δ))n!3/nn−1s(G)=\left(e^{-1/2}+O(n^{-\delta})\right)n!^3/n^{n-1}, either uniformly in GG or with the dependence of the constant on the invariant factors of GG (the orders of the cyclic factors in a decomposition of GG; in particular its 2-rank, the number of even-order cyclic factors) made explicit; or show that no power saving holds, by determining the true order (or oscillation scale) of the discrepancy s(G) nn−1/n!3−e−1/2s(G)\,n^{n-1}/n!^3-e^{-1/2} along subsequences of groups; optionally, in either case, determine the lower-order terms of the asymptotic if such an expansion exists. The single common objective is a first quantitative characterization of the discrepancy between s(G)s(G) and its known leading term.

References

  1. Sean Eberhard, Freddie Manners, Rudi Mrazović, 'Additive triples of bijections, or the toroidal semiqueens problem', Journal of the European Mathematical Society 21(2):441–463, 2018. DOI: 10.4171/jems/841; https://doi.org/10.4171/jems/841 (preprint arXiv:1510.05987, https://arxiv.org/abs/1510.05987)
  2. Sean Eberhard, 'More on additive triples of bijections', preprint, 2017. arXiv:1704.02407; https://arxiv.org/abs/1704.02407
  3. Sean Eberhard, Freddie Manners, Rudi Mrazović, 'An asymptotic for the Hall–Paige conjecture', Advances in Mathematics 404:108423, 2022. DOI: 10.1016/j.aim.2022.108423; https://doi.org/10.1016/j.aim.2022.108423 (preprint arXiv:2003.01798, https://arxiv.org/abs/2003.01798)
  4. Sean Eberhard, Freddie Manners, Rudi Mrazović, 'Transversals in quasirandom latin squares', Proceedings of the London Mathematical Society 127(1):84–115, 2023. DOI: 10.1112/plms.12538; https://doi.org/10.1112/plms.12538 (preprint arXiv:2209.02180, https://arxiv.org/abs/2209.02180)
  5. Candida Bowtell, Peter Keevash, 'The n-queens problem', preprint, 2021. arXiv:2109.08083; https://arxiv.org/abs/2109.08083
  6. Zur Luria, 'New bounds on the number of n-queens configurations', preprint, 2017. arXiv:1705.05225; https://arxiv.org/abs/1705.05225
  7. Michael Simkin, 'The number of n-queens configurations', Advances in Mathematics 427:109127, 2023. DOI: 10.1016/j.aim.2023.109127; https://doi.org/10.1016/j.aim.2023.109127 (preprint arXiv:2107.13460, https://arxiv.org/abs/2107.13460)
  8. Nicholas J. Cavenagh, Ian M. Wanless, 'On the number of transversals in Cayley tables of cyclic groups', Discrete Applied Mathematics 158(2):136–146, 2010. DOI: 10.1016/j.dam.2009.09.006; https://doi.org/10.1016/j.dam.2009.09.006
  9. Ian M. Wanless, 'Transversals in latin squares: a survey', in Surveys in Combinatorics 2011, London Mathematical Society Lecture Note Series 392, pp. 403–437, Cambridge University Press, 2011. DOI: 10.1017/CBO9781139004114.010; https://doi.org/10.1017/CBO9781139004114.010
  10. Ilan Vardi, 'Computational Recreations in Mathematica', Addison-Wesley, Redwood City, CA, 1991. ISBN 0-201-52989-0; https://zbmath.org/0786.11002 (zbMATH Open, Zbl 0786.11002)
  11. Bodan Arsovski, 'A proof of Snevily's conjecture', Israel Journal of Mathematics 182(1):505–508, 2011. DOI: 10.1007/s11856-011-0040-6; https://doi.org/10.1007/s11856-011-0040-6