Document Open Access Logo

On the Identity Problem for the Special Linear Group and the Heisenberg Group

Authors Sang-Ki Ko, Reino Niskanen, Igor Potapov

PDF
Thumbnail PDF

File

LIPIcs.ICALP.2018.132.pdf
  • Filesize: 0.52 MB
  • 15 pages

Document Identifiers

Author Details

Sang-Ki Ko
  • Korea Electronics Technology Institute, South Korea
Reino Niskanen
  • Department of Computer Science, University of Liverpool, UK
Igor Potapov
  • Department of Computer Science, University of Liverpool, UK

Funding

This work was supported by EPSRC grant "Reachability problems for words, matrices and maps" (EP/M00077X/1).

Cite AsGet BibTex

Sang-Ki Ko, Reino Niskanen, and Igor Potapov. On the Identity Problem for the Special Linear Group and the Heisenberg Group. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 132:1-132:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
https://doi.org/10.4230/LIPIcs.ICALP.2018.132

Abstract

We study the identity problem for matrices, i.e., whether the identity matrix is in a semigroup generated by a given set of generators. In particular we consider the identity problem for the special linear group following recent NP-completeness result for SL(2,Z) and the undecidability for SL(4,Z) generated by 48 matrices. First we show that there is no embedding from pairs of words into 3 x3 integer matrices with determinant one, i.e., into SL{(3,Z)} extending previously known result that there is no embedding into C^{2 x 2}. Apart from theoretical importance of the result it can be seen as a strong evidence that the computational problems in SL{(3,Z)} are decidable. The result excludes the most natural possibility of encoding the Post correspondence problem into SL{(3,Z)}, where the matrix products extended by the right multiplication correspond to the Turing machine simulation. Then we show that the identity problem is decidable in polynomial time for an important subgroup of SL(3,Z), the Heisenberg group H(3,Z). Furthermore, we extend the decidability result for H(n,Q) in any dimension n. Finally we are tightening the gap on decidability question for this long standing open problem by improving the undecidability result for the identity problem in SL{(4,Z)} substantially reducing the bound on the size of the generator set from 48 to 8 by developing a novel reduction technique.

Subject Classification

ACM Subject Classification
  • Theory of computation → Models of computation
  • Computing methodologies → Symbolic and algebraic algorithms
  • Theory of computation → Program verification
Keywords
  • matrix semigroup
  • identity problem
  • special linear group
  • Heisenberg group
  • decidability

Metrics

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

Related Versions

References

  1. Andrei M. Akimenkov. Subgroups of the braid group B₄. Mathematical notes of the Academy of Sciences of the USSR, 50(6):1211-1218, 1991. URL: http://dx.doi.org/10.1007/BF01158260.
  2. László Babai, Robert Beals, Jin-yi Cai, Gábor Ivanyos, and Eugene M. Luks. Multiplicative equations over commuting matrices. In Proceedings of SODA 1996, pages 498-507. SIAM, 1996. URL: http://dl.acm.org/citation.cfm?id=313852.314109.
  3. Paul Bell, Vesa Halava, Tero Harju, Juhani Karhumäki, and Igor Potapov. Matrix equations and Hilbert’s Tenth Problem. International Journal of Algebra and Computation, 18(08):1231-1241, dec 2008. URL: http://dx.doi.org/10.1142/s0218196708004925.
  4. Paul C. Bell, Mika Hirvensalo, and Igor Potapov. The identity problem for matrix semigroups in SL(2,ℤ) is NP-complete. In Proceedings of SODA 2017, pages 187-206. SIAM, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.13.
  5. Paul C. Bell and Igor Potapov. Reachability problems in quaternion matrix and rotation semigroups. Information and Computation, 206(11):1353-1361, 2008. URL: http://dx.doi.org/10.1016/j.ic.2008.06.004.
  6. Paul C. Bell and Igor Potapov. On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups. International Journal of Foundations of Computer Science, 21(6):963-978, 2010. URL: http://dx.doi.org/10.1142/S0129054110007660.
  7. Vladimir N. Bezverkhnii and Irina V. Dobrynina. Undecidability of the conjugacy problem for subgroups in the colored braid group R₅. Matematicheskie Zametki, 65(1):15-22, 1999. URL: http://dx.doi.org/10.1007/BF02675004.
  8. Jean-Camille Birget and Stuart W. Margolis. Two-letter group codes that preserve aperiodicity of inverse finite automata. Semigroup Forum, 76:159-168, 2008. URL: http://dx.doi.org/10.1007/s00233-007-9024-6.
  9. Kenneth R. Blaney and Andrey Nikolaev. A PTIME solution to the restricted conjugacy problem in generalized Heisenberg groups. Groups Complexity Cryptology, 8(1):69-74, 2016. URL: http://dx.doi.org/10.1515/gcc-2016-0003.
  10. Vincent D. Blondel and Alexandre Megretski, editors. Unsolved problems in mathematical systems and control theory. Princeton University Press, 2004. Google Scholar
  11. Jean-Luc Brylinski. Loop spaces, characteristic classes, and geometric quantization. Birkhäuser, 1993. Google Scholar
  12. Julien Cassaigne, Tero Harju, and Juhani Karhumäki. On the undecidability of freeness of matrix semigroups. International Journal of Algebra and Computation, 9(03n04):295-305, 1999. URL: http://dx.doi.org/10.1142/S0218196799000199.
  13. Émilie Charlier and Juha Honkala. The freeness problem over matrix semigroups and bounded languages. Information and Computation, 237:243-256, 2014. URL: http://dx.doi.org/10.1016/j.ic.2014.03.001.
  14. Christian Choffrut. A remark on the representation of trace monoids. Semigroup Forum, 40(1):143-152, 1990. URL: http://dx.doi.org/10.1007/bf02573262.
  15. Christian Choffrut and Juhani Karhumäki. Some decision problems on integer matrices. RAIRO - Theoretical Informatics and Applications, 39(1):125-131, 2005. URL: http://dx.doi.org/10.1051/ita:2005007.
  16. Ventsislav Chonev, Joël Ouaknine, and James Worrell. The orbit problem in higher dimensions. In Proceedings of STOC 2013, pages 941-950. ACM, 2013. URL: http://dx.doi.org/10.1145/2488608.2488728.
  17. Ventsislav Chonev, Joël Ouaknine, and James Worrell. On the complexity of the orbit problem. Journal of the ACM, 63(3):23:1-23:18, 2016. URL: http://dx.doi.org/10.1145/2857050.
  18. Marston Conder, Edmund Robertson, and Peter Williams. Presentations for 3-dimensional special linear groups over integer rings. Proceedings of the American Mathematical Society, 115(1):19-26, 1992. URL: http://dx.doi.org/10.2307/2159559.
  19. Marston D. E. Conder. Some unexpected consequences of symmetry computations. In SIGMAP 2014, volume 159 of PROMS, pages 71-79. Springer, 2016. URL: http://dx.doi.org/10.1007/978-3-319-30451-9_3.
  20. Jintai Ding, Alexei Miasnikov, and Alexander Ushakov. A linear attack on a key exchange protocol using extensions of matrix semigroups. IACR Cryptology ePrint Archive, 2015:18, 2015. Google Scholar
  21. Esther Galby, Joël Ouaknine, and James Worrell. On matrix powering in low dimensions. In Proceedings of STACS 2015, volume 30 of LIPIcs, pages 329-340, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.329.
  22. Razvan Gelca and Alejandro Uribe. From classical theta functions to topological quantum field theory. In The influence of Solomon Lefschetz in geometry and topology, volume 621 of Contemprorary Mathematics, pages 35-68. American Mathematical Society, 2014. URL: http://dx.doi.org/10.1090/conm/621.
  23. Yuri Gurevich and Paul Schupp. Membership problem for the modular group. SIAM Journal of Computing, 37(2):425-459, 2007. URL: http://dx.doi.org/10.1137/050643295.
  24. Vesa Halava, Tero Harju, and Mika Hirvensalo. Undecidability bounds for integer matrices using Claus instances. International Journal of Foundations of Computer Science, 18(5):931-948, 2007. URL: http://dx.doi.org/10.1142/S0129054107005066.
  25. Juha Honkala. A Kraft-McMillan inequality for free semigroups of upper-triangular matrices. Information and Computation, 239:216-221, 2014. URL: http://dx.doi.org/10.1016/j.ic.2014.09.002.
  26. Juha Honkala. Products of matrices and recursively enumerable sets. Journal of Computer and System Sciences, 81(2):468-472, 2015. URL: http://dx.doi.org/10.1016/j.jcss.2014.10.004.
  27. Sang-Ki Ko, Reino Niskanen, and Igor Potapov. On the identity problem for the special linear group and the Heisenberg group. CoRR, abs/1706.04166, 2017. URL: https://arxiv.org/abs/1706.04166, URL: http://arxiv.org/abs/1706.04166.
  28. Daniel König, Markus Lohrey, and Georg Zetzsche. Knapsack and subset sum problems in nilpotent, polycyclic, and co-context-free groups. Algebra and Computer Science, 677:138-153, 2016. URL: http://dx.doi.org/10.1090/conm/677/13625.
  29. Bertram Kostant. Quantization and unitary representations. In Lectures in Modern Analysis and Applications III, pages 87-208. Springer, 1970. URL: http://dx.doi.org/10.1007/BFb0079068.
  30. Alexei Lisitsa and Igor Potapov. Membership and reachability problems for row-monomial transformations. In Proceedings of MFCS 2004, volume 3153 of LNCS, pages 623-634. Springer, 2004. URL: http://dx.doi.org/10.1007/978-3-540-28629-5_48.
  31. Roger C. Lyndon and Paul E. Schupp. Combinatorial group theory. Springer, 1977. URL: http://dx.doi.org/10.1007/978-3-642-61896-3.
  32. Andrei A. Markov. On certain insoluble problems concerning matrices. Doklady Akademii Nauk SSSR, 57(6):539-542, 1947. Google Scholar
  33. Alexei Mishchenko and Alexander Treier. Knapsack problem for nilpotent groups. Groups Complexity Cryptology, 9(1):87-98, 2017. URL: http://dx.doi.org/10.1515/gcc-2017-0006.
  34. Turlough Neary. Undecidability in binary tag systems and the Post correspondence problem for five pairs of words. In Proceedings of STACS 2015, volume 30 of LIPIcs, pages 649-661. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. URL: http://dx.doi.org/10.4230/LIPIcs.STACS.2015.649.
  35. Joël Ouaknine, João Sousa Pinto, and James Worrell. On termination of integer linear loops. In Proceedings of SODA 2015, pages 957-969. SIAM, 2015. URL: http://dx.doi.org/10.1137/1.9781611973730.65.
  36. Joël Ouaknine and James Worrell. On the positivity problem for simple linear recurrence sequences. In Proceedings of ICALP 2014, volume 8573 of LNCS, pages 318-329. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43951-7_27.
  37. Joël Ouaknine and James Worrell. Ultimate positivity is decidable for simple linear recurrence sequences. In Proceedings of ICALP 2014, volume 8573 of LNCS, pages 330-341. Springer, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43951-7_28.
  38. Christos H. Papadimitriou. On the complexity of integer programming. Journal of the ACM, 28(4):765-768, 1981. URL: http://dx.doi.org/10.1145/322276.322287.
  39. Michael S. Paterson. Unsolvability in 3 x 3 matrices. Studies in Applied Mathematics, 49(1):105, 1970. URL: http://dx.doi.org/10.1002/sapm1970491105.
  40. Igor Potapov. Composition problems for braids. In Proceedings of FSTTCS 2013, volume 24 of LIPIcs, pages 175-187. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2013. URL: http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2013.175.
  41. Igor Potapov and Pavel Semukhin. Decidability of the membership problem for 2×2 integer matrices. In Proceedings of SODA 2017, pages 170-186. SIAM, 2017. URL: http://dx.doi.org/10.1137/1.9781611974782.12.
  42. Igor Potapov and Pavel Semukhin. Membership problem in GL(2,ℤ) extended by singular matrices. In Proceedings of MFCS 2017, LIPIcs, pages 44:1-44:13. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2017.44.
  43. Alexander Schrijver. Theory of Linear and Integer Programming. Wiley, 1998. Google Scholar
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