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

MSI Colloquium, where the school comes together for afternoon tea before one speaker gives an accessible talk on their subject

schedule Date & time
23 Sep 2022 | 4 - 5pm
person Speaker


Volker Diekert, University of Stuttgart
contact_support Contact

Content navigation



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})

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.





Seminar Room 1.33, Building 145, Science Road, ANU