Document Open Access Logo

The Isomorphism Problem for Plain Groups Is in Σ₃^{𝖯}

Authors Heiko Dietrich , Murray Elder , Adam Piggott , Youming Qiao , Armin Weiß

PDF
Thumbnail PDF

File

LIPIcs.STACS.2022.26.pdf
  • Filesize: 0.78 MB
  • 14 pages

Document Identifiers

Author Details

Heiko Dietrich
  • Monash University, Clayton, Australia
Murray Elder
  • University of Technology Sydney, Ultimo, Australia
Adam Piggott
  • Australian National University, Canberra, Australia
Youming Qiao
  • University of Technology Sydney, Ultimo, Australia
Armin Weiß
  • Universität Stuttgart, Germany

Funding

  • Dietrich, Heiko: Supported by Australian Research Council grant DP190100317.
  • Elder, Murray: Supported by Australian Research Council grant DP210100271.
  • Piggott, Adam: Supported by Australian Research Council grant DP210100271.
  • Qiao, Youming: Supported by Australian Research Council grant DP200100950.

Acknowledgements

We wish to thank the reviewers for their helpful comments and corrections.

Cite AsGet BibTex

Heiko Dietrich, Murray Elder, Adam Piggott, Youming Qiao, and Armin Weiß. The Isomorphism Problem for Plain Groups Is in Σ₃^{𝖯}. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 26:1-26:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.STACS.2022.26

Abstract

Testing isomorphism of infinite groups is a classical topic, but from the complexity theory viewpoint, few results are known. Sénizergues and the fifth author (ICALP2018) proved that the isomorphism problem for virtually free groups is decidable in PSPACE when the input is given in terms of so-called virtually free presentations. Here we consider the isomorphism problem for the class of plain groups, that is, groups that are isomorphic to a free product of finitely many finite groups and finitely many copies of the infinite cyclic group. Every plain group is naturally and efficiently presented via an inverse-closed finite convergent length-reducing rewriting system. We prove that the isomorphism problem for plain groups given in this form lies in the polynomial time hierarchy, more precisely, in Σ₃^𝖯. This result is achieved by combining new geometric and algebraic characterisations of groups presented by inverse-closed finite convergent length-reducing rewriting systems developed in recent work of the second and third authors (2021) with classical finite group isomorphism results of Babai and Szemerédi (1984).

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
  • Theory of computation → Rewrite systems
  • Mathematics of computing → Discrete mathematics
  • Theory of computation → Computability
Keywords
  • plain group
  • isomorphism problem
  • polynomial hierarchy
  • Σ₃^{𝖯} complexity class
  • inverse-closed finite convergent length-reducing rewriting system

Metrics

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

References

  1. Sanjeev Arora and Boaz Barak. Computational complexity. Cambridge University Press, Cambridge, 2009. A modern approach. URL: https://doi.org/10.1017/CBO9780511804090.
  2. László Babai. Local expansion of vertex-transitive graphs and random generation in finite groups. In Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, STOC '91, pages 164-174, New York, NY, USA, 1991. Association for Computing Machinery. URL: https://doi.org/10.1145/103418.103440.
  3. László Babai and Endre Szemeredi. On the complexity of matrix group problems I. In 25th Annual Symposium on Foundations of Computer Science, 1984., pages 229-240, 1984. URL: https://doi.org/10.1109/SFCS.1984.715919.
  4. Ronald V. Book and Friedrich Otto. String-rewriting systems. Texts and Monographs in Computer Science. Springer-Verlag, New York, 1993. URL: https://doi.org/10.1007/978-1-4613-9771-7.
  5. François Dahmani and Daniel Groves. The isomorphism problem for toral relatively hyperbolic groups. Publ. Math. Inst. Hautes Études Sci., 107:211-290, 2008. URL: https://doi.org/10.1007/s10240-008-0014-3.
  6. François Dahmani and Vincent Guirardel. The isomorphism problem for all hyperbolic groups. Geom. Funct. Anal., 21(2):223-300, 2011. URL: https://doi.org/10.1007/s00039-011-0120-0.
  7. Max Dehn. Papers on group theory and topology. Springer-Verlag, New York, 1987. Translated from the German and with introductions and an appendix by John Stillwell, With an appendix by Otto Schreier. URL: https://doi.org/10.1007/978-1-4612-4668-8.
  8. Volker Diekert. Some remarks on presentations by finite Church-Rosser Thue systems. In STACS 87 (Passau, 1987), volume 247 of Lecture Notes in Comput. Sci., pages 272-285. Springer, Berlin, 1987. URL: https://doi.org/10.1007/BFb0039612.
  9. Heiko Dietrich and James B. Wilson. Group isomorphism is nearly-linear time for most orders, 2021. Accepted for FOCS 2021. URL: http://arxiv.org/abs/2011.03133.
  10. Andy Eisenberg and Adam Piggott. Gilman’s conjecture. J. Algebra, 517:167-185, 2019. URL: https://doi.org/10.1016/j.jalgebra.2018.09.022.
  11. Murray Elder and Adam Piggott. On groups presented by inverse-closed finite convergent length-reducing rewriting systems, 2021. URL: http://arxiv.org/abs/2106.03445.
  12. Murray Elder and Adam Piggott. Rewriting systems, plain groups, and geodetic graphs. Theoretical Computer Science, 903:134-144, 2022. URL: https://doi.org/10.1016/j.tcs.2021.12.022.
  13. V. Felsch and J. Neubüser. On a programme for the determination of the automorphism group of a finite group. In Pergamon J. Leech, editor, Computational Problems in Abstract Algebra (Proceedings of a Conference on Computational Problems in Algebra, Oxford, 1967), pages 59-60, Oxford, 1970. Google Scholar
  14. Robert H. Gilman, Susan Hermiller, Derek F. Holt, and Sarah Rees. A characterisation of virtually free groups. Arch. Math. (Basel), 89(4):289-295, 2007. URL: https://doi.org/10.1007/s00013-007-2206-3.
  15. Mikhail Gromov. Hyperbolic groups. In Essays in group theory, volume 8 of Math. Sci. Res. Inst. Publ., pages 75-263. Springer, New York, 1987. URL: https://doi.org/10.1007/978-1-4613-9586-7_3.
  16. Robert H. Haring-Smith. Groups and simple languages. Trans. Amer. Math. Soc., 279(1):337-356, 1983. URL: https://doi.org/10.2307/1999388.
  17. Ravindran Kannan and Achim Bachem. Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM J. Comput., 8(4):499-507, 1979. URL: https://doi.org/10.1137/0208040.
  18. Abraham Karrass, Alfred Pietrowski, and Donald Solitar. Finite and infinite cyclic extensions of free groups. Journal of the Australian Mathematical Society, 16(4):458-466, 1973. URL: https://doi.org/10.1017/S1446788700015445.
  19. Sava Krstić. Actions of finite groups on graphs and related automorphisms of free groups. J. Algebra, 124(1):119-138, 1989. URL: https://doi.org/10.1016/0021-8693(89)90154-3.
  20. Roger C. Lyndon and Paul E. Schupp. Combinatorial group theory. Classics in Mathematics. Springer-Verlag, Berlin, 2001. Reprint of the 1977 edition. URL: https://doi.org/10.1007/978-3-642-61896-3.
  21. Klaus Madlener and Friedrich Otto. Groups presented by certain classes of finite length-reducing string-rewriting systems. In Rewriting techniques and applications (Bordeaux, 1987), volume 256 of Lecture Notes in Comput. Sci., pages 133-144. Springer, Berlin, 1987. URL: https://doi.org/10.5555/30432.30444.
  22. Gary L. Miller. On the n^log n isomorphism technique (a preliminary report). In STOC, pages 51-58, New York, NY, USA, 1978. ACM. URL: https://doi.org/10.1145/800133.804331.
  23. David E. Muller and Paul E. Schupp. The theory of ends, pushdown automata, and second-order logic. Theoret. Comput. Sci., 37(1):51-75, 1985. URL: https://doi.org/10.1016/0304-3975(85)90087-8.
  24. Paliath Narendran and Friedrich Otto. Elements of finite order for finite weight-reducing and confluent Thue systems. Acta Inform., 25(5):573-591, 1988. Google Scholar
  25. Morris Newman. The Smith normal form. In Proceedings of the Fifth Conference of the International Linear Algebra Society (Atlanta, GA, 1995), volume 254, pages 367-381, 1997. URL: https://doi.org/10.1016/S0024-3795(96)00163-2.
  26. Eliyahu Rips and Zlil Sela. Canonical representatives and equations in hyperbolic groups. Invent. Math., 120(3):489-512, 1995. URL: https://doi.org/10.1007/BF01241140.
  27. Zlil Sela. The isomorphism problem for hyperbolic groups. I. Ann. of Math. (2), 141(2):217-283, 1995. URL: https://doi.org/10.2307/2118520.
  28. Géraud Sénizergues. An effective version of Stallings' theorem in the case of context-free groups. In Automata, languages and programming (Lund, 1993), volume 700 of Lecture Notes in Comput. Sci., pages 478-495. Springer, Berlin, 1993. URL: https://doi.org/10.1007/3-540-56939-1_96.
  29. Géraud Sénizergues. On the finite subgroups of a context-free group. In Geometric and computational perspectives on infinite groups (Minneapolis, MN and New Brunswick, NJ, 1994), volume 25 of DIMACS Ser. Discrete Math. Theoret. Comput. Sci., pages 201-212. Amer. Math. Soc., Providence, RI, 1996. URL: https://doi.org/10.1007/s002360050045.
  30. Géraud Sénizergues and Armin Weiß. The isomorphism problem for finite extensions of free groups is in PSPACE. In 45th International Colloquium on Automata, Languages, and Programming, volume 107 of LIPIcs. Leibniz Int. Proc. Inform., pages Art. No. 139, 14. Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2018. Google Scholar
  31. Ákos Seress. Permutation group algorithms, volume 152 of Cambridge Tracts in Mathematics. Cambridge University Press, Cambridge, 2003. URL: https://doi.org/10.1017/CBO9780511546549.
  32. Larry J. Stockmeyer. The polynomial-time hierarchy. Theoret. Comput. Sci., 3(1):1-22 (1977), 1976. URL: https://doi.org/10.1016/0304-3975(76)90061-X.
  33. Arne Storjohann. Near optimal algorithms for computing smith normal forms of integer matrices. In Proceedings of the 1996 International Symposium on Symbolic and Algebraic Computation, ISSAC '96, pages 267-274, New York, NY, USA, 1996. Association for Computing Machinery. URL: https://doi.org/10.1145/236869.237084.
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