TY - GEN

T1 - On the identity problem for the special linear group and the heisenberg group

AU - Ko, Sang Ki

AU - Niskanen, Reino

AU - Potapov, Igor

N1 - Publisher Copyright:
© 2018 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

PY - 2018/7/1

Y1 - 2018/7/1

N2 - 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 × 3 integer matrices with determinant one, i.e., into SL(3, Z) extending previously known result that there is no embedding into C2×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.

AB - 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 × 3 integer matrices with determinant one, i.e., into SL(3, Z) extending previously known result that there is no embedding into C2×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.

KW - Decidability

KW - Heisenberg group

KW - Identity problem

KW - Matrix semigroup

KW - Special linear group

UR - http://www.scopus.com/inward/record.url?scp=85049316349&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.ICALP.2018.132

DO - 10.4230/LIPIcs.ICALP.2018.132

M3 - Conference contribution

AN - SCOPUS:85049316349

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018

A2 - Kaklamanis, Christos

A2 - Marx, Daniel

A2 - Chatzigiannakis, Ioannis

A2 - Sannella, Donald

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018

Y2 - 9 July 2018 through 13 July 2018

ER -