Decidability of membership problems for $2\times 2$ matrices over $\mathbb{Q}$

Abstract: My talk is based on a joint work with Igor Potapov and Pavel Semukhin (Liverpool, UK). We consider membership problems in matrix semigroups. Using symbolic algorithms on words and finite automata, we prove various new decidability results for $2\times 2$ matrices over $\mathbb{Q}$. For that, we introduce the concept of flat rational sets: if $M$ is a monoid and $N$ is a submonoid, then \emph{flat rational sets of $M$ over $N$} are finite unions of the form $L_0g_1L_1 \cdots g_t L_t$ where all $L_i$'s are rational subsets of $N$ and $g_i\in 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 $\mathrm{GL}(2,\mathbb{Q})$ over $\mathrm{GL}(2,\mathbb{Z})$ is decidable (in singly exponential time). It is possible that such a strong decidability result cannot be pushed any further for groups sitting between $\mathrm{GL}(2,\mathbb{Z})$ and $\mathrm{GL}(2,\mathbb{Q})$.

We also show a dichotomy for nontrivial group extension of $\mathrm{GL}(2,\mathbb{Z})$ in $\mathrm{GL}(2,\mathbb{Q})$: if $G$ is a f.g.~group such that $\mathrm{GL}(2,\mathbb{Z}) < G \leq \mathrm{GL}(2,\mathbb{Q})$, then either $G\cong \mathrm{GL}(2,\mathbb{Z})\times \mathbb{Z}^k$, for some $k\geq 1$, or $G$ contains an extension of the Baumslag-Solitar group $\mathop\mathrm{BS}(1,q)$, with $q\geq 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 improves various natural decidability results for $2 \times 2$ matrices with rational entries, and it also supports them with concrete complexity bounds for the first time.

group theory

Audience: researchers in the discipline

Symmetry in Newcastle