The geometry of diagonal groups

Bailey, R.; Cameron, Peter; Praeger, Cheryl; Schneider, Csaba

doi:10.1090/tran/8507

The geometry of diagonal groups
HTML articles powered by AMS MathViewer

by R. A. Bailey, Peter J. Cameron, Cheryl E. Praeger and Csaba Schneider PDF

Trans. Amer. Math. Soc. 375 (2022), 5259-5311 Request permission

Abstract:

Diagonal groups are one of the classes of finite primitive permutation groups occurring in the conclusion of the O’Nan–Scott theorem. Several of the other classes have been described as the automorphism groups of geometric or combinatorial structures such as affine spaces or Cartesian decompositions, but such structures for diagonal groups have not been studied in general.

The main purpose of this paper is to describe and characterise such structures, which we call diagonal semilattices. Unlike the diagonal groups in the O’Nan–Scott theorem, which are defined over finite characteristically simple groups, our construction works over arbitrary groups, finite or infinite.

A diagonal semilattice depends on a dimension $m$ and a group $T$. For $m=2$, it is a Latin square, the Cayley table of $T$, though in fact any Latin square satisfies our combinatorial axioms. However, for $m \geqslant3$, the group $T$ emerges naturally and uniquely from the axioms. (The situation somewhat resembles projective geometry, where projective planes exist in great profusion but higher-dimensional structures are coordinatised by an algebraic object, a division ring.)

A diagonal semilattice is contained in the partition lattice on a set $\Omega$, and we provide an introduction to the calculus of partitions. Many of the concepts and constructions come from experimental design in statistics.

We also determine when a diagonal group can be primitive, or quasiprimitive (these conditions turn out to be equivalent for diagonal groups).

Associated with the diagonal semilattice is a graph, the diagonal graph, which has the same automorphism group as the diagonal semilattice except in four small cases with $m\leqslant 3$. The class of diagonal graphs includes some well-known families, Latin-square graphs and folded cubes, and is potentially of interest. We obtain partial results on the chromatic number of a diagonal graph, and mention an application to the synchronization property of permutation groups.

References

A. A. Albert, Quasigroups. I, Trans. Amer. Math. Soc. 54 (1943), 507–519. MR 9962, DOI 10.1090/S0002-9947-1943-0009962-7
João Araújo, Peter J. Cameron, and Benjamin Steinberg, Between primitive and 2-transitive: synchronization and its friends, EMS Surv. Math. Sci. 4 (2017), no. 2, 101–184. MR 3725240, DOI 10.4171/EMSS/4-2-1
Michael Aschbacher, Finite group theory, Cambridge Studies in Advanced Mathematics, vol. 10, Cambridge University Press, Cambridge, 1986. MR 895134
Michael Aschbacher, Overgroups of primitive groups. II, J. Algebra 322 (2009), no. 5, 1586–1626. MR 2543625, DOI 10.1016/j.jalgebra.2009.04.044
M. Aschbacher and L. Scott, Maximal subgroups of finite groups, J. Algebra 92 (1985), no. 1, 44–80. MR 772471, DOI 10.1016/0021-8693(85)90145-0
R. A. Bailey, Factorial design and abelian groups, Linear Algebra Appl. 70 (1985), 349–368. MR 808552, DOI 10.1016/0024-3795(85)90064-3
R. A. Bailey, Orthogonal partitions in designed experiments, Des. Codes Cryptogr. 8 (1996), no. 1-2, 45–77. Special issue dedicated to Hanfried Lenz. MR 1393974, DOI 10.1007/BF00130568
R. A. Bailey, Association schemes, Cambridge Studies in Advanced Mathematics, vol. 84, Cambridge University Press, Cambridge, 2004. Designed experiments, algebra and combinatorics. MR 2047311, DOI 10.1017/CBO9780511610882
R. A. Bailey, Design of comparative experiments, Cambridge Series in Statistical and Probabilistic Mathematics, vol. 25, Cambridge University Press, Cambridge, 2008. MR 2422352, DOI 10.1017/CBO9780511611483
R. A. Bailey, Relations among partitions, Surveys in combinatorics 2017, London Math. Soc. Lecture Note Ser., vol. 440, Cambridge Univ. Press, Cambridge, 2017, pp. 1–86. MR 3728105
R. A. Bailey, Peter J. Cameron, Michael Kinyon and Cheryl E. Praeger, Diagonal groups and arcs over groups, Designs, Codes, and Cryptography (2021). DOI 10.1007/s10623-021-00907-2
R. A. Bailey, Cheryl E. Praeger, C. A. Rowley, and T. P. Speed, Generalized wreath products of permutation groups, Proc. London Math. Soc. (3) 47 (1983), no. 1, 69–82. MR 698928, DOI 10.1112/plms/s3-47.1.69
W. W. Rouse Ball, Mathematical Recreations and Essays, The Macmillan Company, New York, 1947. Revised by H. S. M. Coxeter. MR 0019629
Gerhard Behrendt, Equivalence systems with finitely many relations, Monatsh. Math. 103 (1987), no. 2, 77–83. MR 881713, DOI 10.1007/BF01630677
R. C. Bose, Strongly regular graphs, partial geometries and partially balanced designs, Pacific J. Math. 13 (1963), 389–419. MR 157909
H. Brandt, Über eine Verallgemeinerung des Gruppenbegriffes, Math. Ann. 96 (1927), no. 1, 360–366 (German). MR 1512323, DOI 10.1007/BF01209171
John N. Bray, Qi Cai, Peter J. Cameron, Pablo Spiga, and Hua Zhang, The Hall-Paige conjecture, and synchronization for affine and diagonal groups, J. Algebra 545 (2020), 27–42. MR 4044687, DOI 10.1016/j.jalgebra.2019.02.025
Marcus Brazil, Jacinta Covington, Tim Penttila, Cheryl E. Praeger, and Alan R. Woods, Maximal subgroups of infinite symmetric groups, Proc. London Math. Soc. (3) 68 (1994), no. 1, 77–111. MR 1243836, DOI 10.1112/plms/s3-68.1.77
Andries E. Brouwer, The Shrikhande graph, https://www.win.tue.nl/~aeb/graphs/Shrikhande.html (accessed 21 June 2020).
A. E. Brouwer, A. M. Cohen, and A. Neumaier, Distance-regular graphs, Ergebnisse der Mathematik und ihrer Grenzgebiete (3) [Results in Mathematics and Related Areas (3)], vol. 18, Springer-Verlag, Berlin, 1989. MR 1002568, DOI 10.1007/978-3-642-74341-2
R. H. Bruck, Finite nets. II. Uniqueness and imbedding, Pacific J. Math. 13 (1963), 421–457. MR 154824
A. A. Bruen, J. A. Thas, and A. Blokhuis, On M.D.S. codes, arcs in $\textrm {PG}(n,q)$ with $q$ even, and a solution of three fundamental problems of B. Segre, Invent. Math. 92 (1988), no. 3, 441–459. MR 939470, DOI 10.1007/BF01393742
Peter J. Cameron, Combinatorics: topics, techniques, algorithms, Cambridge University Press, Cambridge, 1994. MR 1311922
Peter J. Cameron, Random strongly regular graphs?, Discrete Math. 273 (2003), no. 1-3, 103–114. EuroComb’01 (Barcelona). MR 2025944, DOI 10.1016/S0012-365X(03)00231-0
P. J. Cameron, Strongly regular graphs, in Topics in algebraic graph theory (eds. L. W. Beineke and R. J. Wilson), Cambridge University Press, Cambridge, 2004, pp. 203–221.
Peter J. Cameron, Asymmetric Latin squares, Steiner triple systems, and edge-parallelisms, Notes from ca. 1980, https://cameroncounts.files.wordpress.com/2015/05/asymmetric.pdf (accessed 19 July 2020).
Tullio Ceccherini-Silberstein, Fabio Scarabotti, and Filippo Tolli, Representation theory and harmonic analysis of wreath products of finite groups, London Mathematical Society Lecture Note Series, vol. 410, Cambridge University Press, Cambridge, 2014. MR 3202374
Ching-Shui Cheng and Pi-Wen Tsai, Multistratum fractional factorial designs, Statist. Sinica 21 (2011), no. 3, 1001–1021. MR 2817010, DOI 10.5705/ss.2009.287
Charles J. Colbourn, Orthogonal arrays of index more than one, Section II.4 in The CRC Handbook of Combinatorial Designs (eds. Charles J. Colbourn and Jeffrey Dinitz), CRC Press, Boca Raton, 1996, pp. 172–178.
Jacinta Covington, Dugald Macpherson, and Alan Mekler, Some maximal subgroups of infinite symmetric groups, Quart. J. Math. Oxford Ser. (2) 47 (1996), no. 187, 297–311. MR 1412557, DOI 10.1093/qmath/47.3.297
J. Dénes and A. D. Keedwell, Latin squares and their applications, Academic Press, New York-London, 1974. MR 0351850
Diane Donovan, Sheila Oates-Williams, and Cheryl E. Praeger, On the distance between distinct group Latin squares, J. Combin. Des. 5 (1997), no. 4, 235–248. MR 1451283, DOI 10.1002/(SICI)1520-6610(1997)5:4<235::AID-JCD1>3.0.CO;2-G
Steven T. Dougherty and Theresa A. Szczepanski, Latin $k$-hypercubes, Australas. J. Combin. 40 (2008), 145–160. MR 2381422
V. Duquenne, What can lattices do for experimental designs?, Math. Social Sci. 11 (1986), no. 3, 243–281. MR 842403, DOI 10.1016/0165-4896(86)90028-4
G. P. Egoryčev, Proof of the van der Waerden conjecture for permanents, Akademiya Nauk SSSR (in Russian), 22 (6), (1981), 65–71, 225
Anthony B. Evans, The admissibility of sporadic simple groups, J. Algebra 321 (2009), no. 1, 105–116. MR 2469351, DOI 10.1016/j.jalgebra.2008.09.028
D. I. Falikman, Proof of the van der Waerden conjecture on the permanent of a doubly stochastic matrix, Mat. Zametki 29 (1981), no. 6, 931–938, 957 (Russian). MR 625097
R. A. Fisher, A system of confounding for factors with more than two alternatives, giving completely orthogonal cubes and higher powers, Ann. Eugenics 12 (1945), 283–290. MR 13113
M. Frolov, Recherches sur les permutations carrées, J. Math. Spéc. (3) 4 (1890), 8–11.
Luis Goddyn, Kevin Halasz, and E. S. Mahmoodian, The chromatic number of finite group Cayley tables, Electron. J. Combin. 26 (2019), no. 1, Paper No. 1.36, 15. MR 3934367, DOI 10.37236/7874
Hansraj Gupta, On permutation cubes and Latin cubes, Indian J. Pure Appl. Math. 5 (1974), no. 11, 1003–1021. MR 469787
Marshall Hall and L. J. Paige, Complete mappings of finite groups, Pacific J. Math. 5 (1955), 541–549. MR 79589
Richard Hammack, Wilfried Imrich, and Sandi Klavžar, Handbook of product graphs, 2nd ed., Discrete Mathematics and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2011. With a foreword by Peter Winkler. MR 2817074
Camille Jordan, Traité des substitutions et des équations algébriques, Les Grands Classiques Gauthier-Villars. [Gauthier-Villars Great Classics], Éditions Jacques Gabay, Sceaux, 1989 (French). Reprint of the 1870 original. MR 1188877
A. Donald Keedwell and József Dénes, Latin squares and their applications, 2nd ed., Elsevier/North-Holland, Amsterdam, 2015. With a foreword to the previous edition by Paul Erdös. MR 3495977
K. Kishen, On Latin and hyper-Graeco-Latin cubes and hyper-cubes, Curr. Sci. 11 (1942), 98–99.
K. Kishen, On the construction of latin and hyper-graeco-latin cubes and hypercubes, J. Indian Soc. Agric. Statist. 2 (1949), 20–48. MR 34743
L. G. Kovács, Primitive permutation groups of simple diagonal type, Israel J. Math. 63 (1988), no. 1, 119–127. MR 959051, DOI 10.1007/BF02765024
L. G. Kovács, Wreath decompositions of finite permutation groups, Bull. Austral. Math. Soc. 40 (1989), no. 2, 255–279. MR 1012834, DOI 10.1017/S0004972700004366
Charles F. Laywine, Gary L. Mullen, and Geoff Whittle, $d$-dimensional hypercubes and the Euler and MacNeish conjectures, Monatsh. Math. 119 (1995), no. 3, 223–238. MR 1320681, DOI 10.1007/BF01293673
Martin W. Liebeck, The classification of finite simple Moufang loops, Math. Proc. Cambridge Philos. Soc. 102 (1987), no. 1, 33–47. MR 886433, DOI 10.1017/S0305004100067025
Martin W. Liebeck, Cheryl E. Praeger, and Jan Saxl, A classification of the maximal subgroups of the finite alternating and symmetric groups, J. Algebra 111 (1987), no. 2, 365–383. MR 916173, DOI 10.1016/0021-8693(87)90223-7
C. Devon Lin, Rahul Mukerjee, and Boxin Tang, Construction of orthogonal and nearly orthogonal Latin hypercubes, Biometrika 96 (2009), no. 1, 243–247. MR 2482150, DOI 10.1093/biomet/asn064
H. D. Macpherson and Peter M. Neumann, Subgroups of infinite symmetric groups, J. London Math. Soc. (2) 42 (1990), no. 1, 64–84. MR 1078175, DOI 10.1112/jlms/s2-42.1.64
H. D. Macpherson and Cheryl E. Praeger, Maximal subgroups of infinite symmetric groups, J. London Math. Soc. (2) 42 (1990), no. 1, 85–92. MR 1078176, DOI 10.1112/jlms/s2-42.1.85
Brendan D. McKay and Ian M. Wanless, On the number of Latin squares, Ann. Comb. 9 (2005), no. 3, 335–344. MR 2176596, DOI 10.1007/s00026-005-0261-7
Brendan D. McKay and Ian M. Wanless, A census of small Latin hypercubes, SIAM J. Discrete Math. 22 (2008), no. 2, 719–736. MR 2399374, DOI 10.1137/070693874
D. H. McLain, A characteristically-simple group, Proc. Cambridge Philos. Soc. 50 (1954), 641–642. MR 64045
Mahamendige Jayama Lalani Mendis and Ian M. Wanless, Autoparatopisms of quasigroups and Latin squares, J. Combin. Des. 25 (2017), no. 2, 51–74. MR 3592323, DOI 10.1002/jcd.21515
Seyed Morteza Mirafzal and Meysam Ziaee, A note on the automorphism group of the Hamming graph, Trans. Comb. 10 (2021), no. 2, 129–136. MR 4230851, DOI 10.22108/TOC.2021.127225.1817
Gary L. Mullen and Robert E. Weber, Latin cubes of order $\leq 5$, Discrete Math. 32 (1980), no. 3, 291–297. MR 593977, DOI 10.1016/0012-365X(80)90267-8
J. A. Nelder, The analysis of randomized experiments with orthogonal block structure. I. Block structure and the null analysis of variance, Proc. Roy. Soc. London Ser. A 283 (1965), 147–162. MR 176576, DOI 10.1098/rspa.1965.0012
Peter M. Neumann, An enumeration theorem for finite groups, Quart. J. Math. Oxford Ser. (2) 20 (1969), 395–401. MR 254134, DOI 10.1093/qmath/20.1.395
Peter M. Neumann, Charles C. Sims, and James Wiegold, Counterexamples to a theorem of Cauchy, J. London Math. Soc. 43 (1968), 234. MR 237625, DOI 10.1112/jlms/s1-43.1.234
L. J. Paige, Complete mappings of finite groups, Pacific J. Math. 1 (1951), 111–116. MR 43080
Lowell J. Paige, A class of simple Moufang loops, Proc. Amer. Math. Soc. 7 (1956), 471–482. MR 79596, DOI 10.1090/S0002-9939-1956-0079596-1
Charles Payan, On the chromatic number of cube-like graphs, Discrete Math. 103 (1992), no. 3, 271–277. MR 1171780, DOI 10.1016/0012-365X(92)90319-B
K. T. Phelps, Automorphism-free Latin square graphs, Discrete Math. 31 (1980), no. 2, 193–200. MR 583219, DOI 10.1016/0012-365X(80)90036-9
Cheryl E. Praeger and Csaba Schneider, Factorisations of characteristically simple groups, J. Algebra 255 (2002), no. 1, 198–220. MR 1935043, DOI 10.1016/S0021-8693(02)00111-4
Cheryl E. Praeger and Csaba Schneider, The contribution of L. G. Kovács to the theory of permutation groups, J. Aust. Math. Soc. 102 (2017), no. 1, 20–33. MR 3597018, DOI 10.1017/S1446788715000385
Cheryl E. Praeger and Csaba Schneider, Permutation groups and Cartesian decompositions, London Mathematical Society Lecture Note Series, vol. 449, Cambridge University Press, Cambridge, 2018. MR 3791829, DOI 10.1017/9781139194006
Cheryl E. Praeger and Csaba Schneider, Group factorisations, uniform automorphisms, and permutation groups of simple diagonal type, Israel J. Math. 228 (2018), no. 2, 1001–1023. MR 3874866, DOI 10.1007/s11856-018-1790-1
D. A. Preece, Bibliography of designs for experiments in three dimensions, Austral. J. Statist. 17 (1975), no. 1, 51–55. MR 388691
D. A. Preece, Non-orthogonal Graeco-Latin designs, Combinatorial mathematics, IV (Proc. Fourth Australian Conf., Univ. Adelaide, Adelaide, 1975) Lecture Notes in Math., Vol. 560, Springer, Berlin, 1976, pp. 7–26. MR 0432475
D. A. Preece, Latin squares, Latin cubes, Latin rectangles, etc., Encyclopedia of Statistical Sciences 4 (1983), 504–510. (eds. S. Kotz and N. L. Johnson).
D. A. Preece, Factorial experimentation in second-order Latin cubes, J. App. Stat. 16 (1989), 19–24.
D. A. Preece, S. C. Pearce, and J. R. Kerr, Orthogonal designs for three-dimensional experiments, Biometrika 60 (1973), 349–358. MR 323041, DOI 10.1093/biomet/60.2.349
Dana Randall, Decomposition methods and sampling circuits in the Cartesian lattice, Mathematical foundations of computer science, 2001 (Mariánské Láznĕ), Lecture Notes in Comput. Sci., vol. 2136, Springer, Berlin, 2001, pp. 74–86. MR 1907002, DOI 10.1007/3-540-44683-4_{8}
Derek J. S. Robinson, A course in the theory of groups, 2nd ed., Graduate Texts in Mathematics, vol. 80, Springer-Verlag, New York, 1996. MR 1357169, DOI 10.1007/978-1-4419-8594-1
Gert Sabidussi, Graph multiplication, Math. Z. 72 (1959/60), 446–457. MR 209177, DOI 10.1007/BF01162967
P. N. Saxena, On the Latin cubes of the second order and the fourth replication of the three-dimensional or cubic lattice designs, J. Indian Soc. Agric. Statist. 12 (1960), 100–140. MR 125714
Leonard L. Scott, Representations in characteristic $p$, The Santa Cruz Conference on Finite Groups (Univ. California, Santa Cruz, Calif., 1979) Proc. Sympos. Pure Math., vol. 37, Amer. Math. Soc., Providence, R.I., 1980, pp. 319–331. MR 604599
Victor Shcherbacov, Elements of quasigroup theory and applications, Monographs and Research Notes in Mathematics, CRC Press, Boca Raton, FL, 2017. MR 3644366, DOI 10.1201/9781315120058
S. S. Shrikhande, The uniqueness of the $L_{2}$ association scheme, Ann. Math. Statist. 30 (1959), 781–798. MR 110166, DOI 10.1214/aoms/1177706207
Michio Suzuki, Structure of a group and the structure of its lattice of subgroups, Ergebnisse der Mathematik und ihrer Grenzgebiete, (N.F.), Heft 10, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1956. MR 0083487
Boxin Tang, Orthogonal array-based Latin hypercubes, J. Amer. Statist. Assoc. 88 (1993), no. 424, 1392–1397. MR 1245375
Thomas Neil Throckmorton, STRUCTURES OF CLASSIFICATION DATA, ProQuest LLC, Ann Arbor, MI, 1961. Thesis (Ph.D.)–Iowa State University. MR 2613237
Tue Tjur, Analysis of variance models in orthogonal designs, Internat. Statist. Rev. 52 (1984), no. 1, 33–81 (English, with French summary). With discussion by R. A. Bailey, T. P. Speed and H. P. Wynn, and a reply by the author. MR 967202, DOI 10.2307/1403242
Tue Tjur, Analysis of variance and design of experiments, Scand. J. Statist. 18 (1991), no. 4, 273–322. With a discussion by Rolf Sundberg and Inge Helland and a rejoinder by the author. MR 1157785
Oswald Veblen and John Wesley Young, A Set of Assumptions for Projective Geometry, Amer. J. Math. 30 (1908), no. 4, 347–380. MR 1506049, DOI 10.2307/2369956
V. G. Vizing, The cartesian product of graphs, Vyčisl. Sistemy No. 9 (1963), 30–43 (Russian). MR 0209178
Ian M. Wanless, Latin squares with transitive autotopism group, http://users.monash.edu.au/~iwanless/data/autotopisms/transitive/index.html (accessed July 2020).
Stewart Wilcox, Reduction of the Hall-Paige conjecture to sporadic simple groups, J. Algebra 321 (2009), no. 5, 1407–1428. MR 2494397, DOI 10.1016/j.jalgebra.2008.11.033
George Zyskind, On structure, relation, $\Sigma$, and expectation of mean squares, Sankhyā Ser. A 24 (1962), 115–148. MR 144428