Disjoint direct product decompositions of permutation groups. (English) Zbl 1542.20007
Summary: Let \(H\leq S_n\) be an intransitive group with orbits \(\Omega_1,\Omega_2,\dots,\Omega_k\). Then certainly \(H\) is a subdirect product of the direct product of its projections onto each orbit, \(H |_{\Omega_1}\times H |_{\Omega_2}\times\dots\times H|_{\Omega_k}\). Here we provide a polynomial time algorithm for computing the finest partition \(P\) of the \(H\)-orbits such that \(H=\prod_{c\in P}H|_c\) and we demonstrate its usefulness in some applications.
MathOverflow Questions:
An algorithm to decompose a directly indecomposable permutation group into a wreath productGenerating set of permutation group such that generators do not ”contain” other group elements
MSC:
| 20B05 | General theory for finite permutation groups |
| 20B35 | Subgroups of symmetric groups |
| 20-08 | Computational methods for problems pertaining to group theory |
Keywords:
permutation group; computation; direct product; subdirect product; decomposition; computer algebra systemReferences:
| [1] | Bauer, K.; Sen, D.; Zvengrowski, P., A generalized Goursat lemma, Tatra Mt. Math. Publ., 64, 1-19 (2015) · Zbl 1396.20027 |
| [2] | Donaldson, A. F.; Miller, A., Exact and approximate strategies for symmetry reduction in model checking, (FM 2006: Formal Methods (2006)), 541-556 |
| [3] | Donaldson, A. F.; Miller, A., On the constructive orbit problem, Ann. Math. Artif. Intell., 57, 1, 1-35 (2009) · Zbl 1205.68220 |
| [4] | GAP, GAP - groups, algorithms, and programming, version 4.11.0, the GAP group (2020) |
| [5] | Gent, I. P.; Petrie, K. E.; Puget, J.-F., Chapter 10 - symmetry in constraint programming, (Rossi, F.; van Beek, P.; Walsh, T., Handbook of Constraint Programming. Handbook of Constraint Programming, Foundations of Artificial Intelligence, vol. 2 (2006), Elsevier), 329-376 · Zbl 1175.90011 |
| [6] | Goursat, E., Sur les substitutions orthogonales et les divisions régulières de l’espace, Ann. Sci. Éc. Norm. Supér. (3), 6, 9-102 (1889) · JFM 21.0530.01 |
| [7] | Grayland, A., Automated static symmetry breaking in constraint satisfaction problems (2011), University of St. Andrews, Ph.D. thesis |
| [8] | Grayland, A.; Jefferson, C.; Miguel, I.; Roney-Dougal, C. M., Minimal ordering constraints for some families of variable symmetries, Ann. Math. Artif. Intell., 57, 1, 75-102 (2009) · Zbl 1205.68375 |
| [9] | Holt, D. F.; Eick, B.; O’Brien, E. A., Handbook of Computational Group Theory, Discrete Mathematics and Its Applications (Boca Raton) (2005), Chapman & Hall/CRC: Chapman & Hall/CRC Boca Raton, FL · Zbl 1091.20001 |
| [10] | Hulpke, A., TransGrp (Nov. 2017), Transitive groups library, Version 2.0.2, GAP package |
| [11] | Hungerford, T. W., Algebra (1974), Holt, Rinehart and Winston, Inc.: Holt, Rinehart and Winston, Inc. New York-Montreal, Que.-London · Zbl 0293.12001 |
| [12] | Kayal, N.; Nezhmetdinov, T., Factoring groups efficiently, (Automata, Languages and Programming. Part I. Automata, Languages and Programming. Part I, Lecture Notes in Comput. Sci., vol. 5555 (2009), Springer: Springer Berlin), 585-596 · Zbl 1248.68250 |
| [13] | McKay, B. D.; Piperno, A., Practical graph isomorphism, II, J. Symb. Comput., 60, 94-112 (2014) · Zbl 1394.05079 |
| [14] | Praeger, C. E.; Schneider, C., Permutation Groups and Cartesian Decompositions, London Mathematical Society Lecture Note Series, vol. 449 (2018), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1428.20002 |
| [15] | Schmidt, R., Subgroup Lattices of Groups, De Gruyter Expositions in Mathematics, vol. 14 (1994), Walter de Gruyter & Co.: Walter de Gruyter & Co. Berlin · Zbl 0843.20003 |
| [16] | Seress, A., Permutation Group Algorithms, Cambridge Tracts in Mathematics, vol. 152 (2003), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1028.20002 |
| [17] | Sims, C. C., Computational methods in the study of permutation groups, (Computational Problems in Abstract Algebra, Proc. Conf.. Computational Problems in Abstract Algebra, Proc. Conf., Oxford, 1967 (1970), Pergamon: Pergamon Oxford), 169-183 · Zbl 0215.10002 |
| [18] | Sims, C. C., Computation with permutation groups, (Proceedings of the Second ACM Symposium on Symbolic and Algebraic Manipulation. SYMSAC ’71 (1971), Association for Computing Machinery: Association for Computing Machinery New York, NY, USA), 23-28 · Zbl 0449.20002 |
| [19] | Wilson, J. B., Existence, algorithms, and asymptotics of direct product decompositions, I, Groups Complex. Cryptol., 4, 1, 33-72 (2012) · Zbl 1277.20022 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
