We consider membership problems in matrix semigroups. Using symbolic algorithms on words and finite automata, we prove various new decidability results for 2×2 matrices over ℚ. For that, we introduce the concept of flat rational sets: if M is a monoid and N is a submonoid, then flat rational sets of M over N are finite unions of the form L0g1L1⋯gtLt where all Li are rational subsets of N and gi ∈ M. We give quite general sufficient conditions under which flat rational sets form an effective relative Boolean algebra. As a corollary, we obtain that the emptiness problem for Boolean combinations of flat rational subsets of GL2(ℚ) over GL2(ℤ) is decidable (in singly exponential time). It is possible that such a strong decidability result cannot be pushed any further for groups sitting between GL2(ℤ) and GL2(ℚ).
We also show a dichotomy for non-trivial group extension of GL2(ℤ) in GL2(ℚ): if G is a f.g. group such that GL2(ℤ) < G ≤ GL2(ℚ), then either G ≅ GL2(ℤ) × ℤk, for some k ≥ 1, or G contains an extension of the Baumslag-Solitar group BS(1,q), with q ≥ 2, of infinite index. In the first case of the dichotomy the membership problem for G is decidable but the equality problem for rational subsets of G is undecidable. In the second case, decidability of the membership problem for rational subsets in G is open.
Our result improves various natural decidability results for 2×2 matrices with rational entries, and it also supports them with concrete complexity bounds for the first time.
My talk is based on a joint work with Igor Potapov and Pavel Semukhin (Liverpool, UK).
This video was produced by Newcastle University, Australia, as part of the Symmetries in Newcastle seminar series.
