Document Open Access Logo

A Systematic Study of Isomorphism Invariants of Finite Groups via the Weisfeiler-Leman Dimension

Authors Jendrik Brachter, Pascal Schweitzer

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.27.pdf
  • Filesize: 0.64 MB
  • 14 pages

Document Identifiers

Author Details

Jendrik Brachter
  • TU Darmstadt, Germany
Pascal Schweitzer
  • TU Darmstadt, Germany

Funding

The research leading to these results has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (EngageS: grant agreement No. 820148) and from the German Research Foundation DFG (SFB-TRR 195 "Symbolic Tools in Mathematics and their Application").

Cite AsGet BibTex

Jendrik Brachter and Pascal Schweitzer. A Systematic Study of Isomorphism Invariants of Finite Groups via the Weisfeiler-Leman Dimension. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ESA.2022.27

Abstract

We investigate the relationship between various isomorphism invariants for finite groups. Specifically, we use the Weisfeiler-Leman dimension (WL) to characterize, compare and quantify the effectiveness and complexity of invariants for group isomorphism. It turns out that a surprising number of invariants and characteristic subgroups that are classic to group theory can be detected and identified by a low dimensional Weisfeiler-Leman algorithm. These include the center, the inner automorphism group, the commutator subgroup and the derived series, the abelian radical, the solvable radical, the Fitting group and π-radicals. A low dimensional WL-algorithm additionally determines the isomorphism type of the socle as well as the factors in the derives series and the upper and lower central series. We also analyze the behavior of the WL-algorithm for group extensions and prove that a low dimensional WL-algorithm determines the isomorphism types of the composition factors of a group. Finally we develop a new tool to define a canonical maximal central decomposition for groups. This allows us to show that the Weisfeiler-Leman dimension of a group is at most one larger than the dimensions of its direct indecomposable factors. In other words the Weisfeiler-Leman dimension increases by at most 1 when taking direct products.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity theory and logic
  • Mathematics of computing → Combinatorial algorithms
Keywords
  • group isomorphism problem
  • Weisfeiler-Leman algorithms
  • group invariants
  • direct product decompositions

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Alireza Abdollahi, Saieed Akbari, and Hamid R. Maimani. Non-commuting graph of a group. J. Algebra, 298(2):468-492, April 2006. URL: https://doi.org/10.1016/j.jalgebra.2006.02.015.
  2. Vikraman Arvind, Frank Fuhlbrück, Johannes Köbler, and Oleg Verbitsky. On Weisfeiler-Leman invariance: Subgraph counts and related graph properties. J. Comput. Syst. Sci., 113:42-59, 2020. URL: https://doi.org/10.1016/j.jcss.2020.04.003.
  3. Hans Ulrich Besche and Bettina Eick. Construction of finite groups. J. Symb. Comput., 27(4):387-404, 1999. URL: https://doi.org/10.1006/jsco.1998.0258.
  4. Jendrik Brachter and Pascal Schweitzer. On the Weisfeiler-Leman dimension of finite groups. In Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS '20, pages 287-300, New York, NY, USA, 2020. Association for Computing Machinery. URL: https://doi.org/10.1145/3373718.3394786.
  5. Jendrik Brachter and Pascal Schweitzer. On the Weisfeiler-Leman dimension of finite groups. CoRR, abs/2003.13745, 2020. arXiv. URL: http://arxiv.org/abs/2003.13745.
  6. Peter A. Brooksbank, Joshua A. Grochow, Yinan Li, Youming Qiao, and James B. Wilson. Incorporating Weisfeiler-Leman into algorithms for group isomorphism. CoRR, abs/1905.02518, 2019. URL: http://arxiv.org/abs/1905.02518.
  7. Arthur Cayley. On the theory of groups, as depending on the symbolic equation θⁿ = 1. The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science, 7(42):40-47, 1854. URL: https://doi.org/10.1080/14786445408647421.
  8. Mun See Chang and Christopher Jefferson. Disjoint direct product decompositions of permutation groups. J. Symb. Comput., 108:1-16, 2022. URL: https://doi.org/10.1016/j.jsc.2021.04.003.
  9. Francesca Dalla Volta and Andrea Lucchini. Generation of almost simple groups. J. Algebra, 178(1):194-223, 1995. URL: https://doi.org/10.1006/jabr.1995.1345.
  10. Bireswar Das and Shivdutt Sharma. Nearly linear time isomorphism algorithms for some nonabelian group classes. In René van Bevern and Gregory Kucherov, editors, Computer Science - Theory and Applications - 14th International Computer Science Symposium in Russia, CSR 2019, Novosibirsk, Russia, July 1-5, 2019, Proceedings, volume 11532 of Lecture Notes in Computer Science, pages 80-92. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-19955-5_8.
  11. Heiko Dietrich and James B. Wilson. Polynomial-time isomorphism testing of groups of most finite orders. CoRR, abs/1806.08872, 2018. arXiv. URL: http://arxiv.org/abs/1806.08872.
  12. Bettina Eick and Max Horn. The construction of finite solvable groups revisited. J. Algebra, 408:166-182, 2014. URL: https://doi.org/10.1016/j.jalgebra.2013.09.028.
  13. Bettina Eick, Max Horn, and Alexander Hulpke. Constructing groups of `small' order: Recent results and open problems. In Gebhard Böckle, Wolfram Decker, and Gunter Malle, editors, Algorithmic and Experimental Methods in Algebra, Geometry, and Number Theory, pages 199-211. Springer International Publishing, Cham, 2017. URL: https://doi.org/10.1007/978-3-319-70566-8_8.
  14. The GAP Group. GAP - Groups, Algorithms, and Programming, Version 4.11.1, 2021. URL: https://www.gap-system.org.
  15. Joshua A. Grochow and Youming Qiao. On the complexity of isomorphism problems for tensors, groups, and polynomials I: tensor isomorphism-completeness. In James R. Lee, editor, 12th Innovations in Theoretical Computer Science Conference, ITCS 2021, January 6-8, 2021, Virtual Conference, volume 185 of LIPIcs, pages 31:1-31:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021. URL: https://doi.org/10.4230/LIPIcs.ITCS.2021.31.
  16. Marshall Hall. The Theory of Groups. AMS Chelsea Publishing Series. AMS Chelsea Pub., 1999. URL: https://books.google.de/books?id=oyxnWF9ssI8C.
  17. Neil Immerman. Relational queries computable in polynomial time. Inf. Control., 68(1-3):86-104, 1986. URL: https://doi.org/10.1016/S0019-9958(86)80029-8.
  18. Telikepalli Kavitha. Linear time algorithms for abelian group isomorphism and related problems. J. Comput. Syst. Sci., 73(6):986-996, 2007. URL: https://doi.org/10.1016/j.jcss.2007.03.013.
  19. Neeraj Kayal and Timur Nezhmetdinov. Factoring groups efficiently. In Susanne Albers, Alberto Marchetti-Spaccamela, Yossi Matias, Sotiris E. Nikoletseas, and Wolfgang Thomas, editors, Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009, Proceedings, Part I, volume 5555 of Lecture Notes in Computer Science, pages 585-596. Springer, 2009. URL: https://doi.org/10.1007/978-3-642-02927-1_49.
  20. Sandra Kiefer. Power and limits of the Weisfeiler-Leman algorithm. PhD thesis, RWTH Aachen University, 2020. Google Scholar
  21. Eugene M. Luks. Group isomorphism with fixed subnormal chains. CoRR, abs/1511.00151, 2015. URL: http://arxiv.org/abs/1511.00151.
  22. Eamonn A. O'Brien. The p-group generation algorithm. J. Symb. Comput., 9(5/6):677-698, 1990. URL: https://doi.org/10.1016/S0747-7171(08)80082-X.
  23. David J. Rosenbaum. Bidirectional collision detection and faster deterministic isomorphism testing. CoRR, abs/1304.3935, 2013. arXiv. URL: http://arxiv.org/abs/1304.3935.
  24. David J. Rosenbaum. Breaking the n^log n barrier for solvable-group isomorphism. In Sanjeev Khanna, editor, Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2013, New Orleans, Louisiana, USA, January 6-8, 2013, pages 1054-1073. SIAM, 2013. URL: https://doi.org/10.1137/1.9781611973105.76.
  25. Michael J. Smith. Computing automorphisms of finite soluble groups. PhD thesis, Australian National University, 1995. Google Scholar
  26. Moshe Y. Vardi. The complexity of relational query languages (extended abstract). In Harry R. Lewis, Barbara B. Simons, Walter A. Burkhard, and Lawrence H. Landweber, editors, Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA, pages 137-146. ACM, 1982. URL: https://doi.org/10.1145/800070.802186.
  27. A. V. Vasil’ev, M. A. Grechkoseeva, and V. D. Mazurov. Characterization of the finite simple groups by spectrum and order. Algebra and Logic, 48:385-409, 2009. URL: https://doi.org/10.1007/s10469-009-9074-9.
  28. James B. Wilson. Finding direct product decompositions in polynomial time. CoRR, abs/1005.0548, 2010. arXiv. URL: http://arxiv.org/abs/1005.0548.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact