Decidability of membership problems for flat rational subsets of $\mathrm{GL}(2,\mathbb{Q})$ and singular matrices
Preprint
Abstract
We consider membership problems for rational sets in matrix semigroups. For a semigroup $M$, the rational sets $\mathrm{Rat}(M)$ are defined as sets accepted by NFA whose transitions are labeled by elements of $M$. The membership problem asks whether $g\in R$, where $g\in M$ and $R\in \mathrm{Rat}(M)$. In this work, we introduce the notion of flat rational sets: if $M$ is a semigroup and $N$ is its subsemigroup, then 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\in \mathrm{Rat}(N)$ and $g_i\in M$. We show 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. It is possible that the above result cannot be pushed any further due to the following dichotomy: 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$ or $G$ contains an extension of the Baumslag-Solitar group of infinite index. In the first case, the membership problem for rational subsets of $G$ is decidable. However, in the second case, the decidability of the membership problem has been open for many years. The latter fact has been the driving force to focus on the class of flat rational sets. It appears as a natural restriction that allowed us to prove new decidability results for $2\times 2$ matrices with rational entries. For example, we prove that the membership problem is decidable in exponential time for flat rational subsets of $\mathrm{GL}(2,\mathbb{Q})$ over $\mathrm{GL}(2,\mathbb{Z})$ but becomes decidable in doubly exponential time if we extend $\mathrm{GL}(2,\mathbb{Z})$ by matrices with determinant greater than $1$. We also show doubly exponential time bound for the membership problem for flat rational subsets that include singular matrices.
Keywords
All Related Versions
This publication has 20 references indexed in Scilit:
- Closure properties of knapsack semilinear groupsJournal of Algebra, 2022
- Geometric Group Theory2018
- The freeness problem over matrix semigroups and bounded languagesInformation and Computation, 2014
- The submonoid and rational subset membership problems for graph groupsJournal of Algebra, 2008
- Dedekind Finite Rings and a Theorem of KaplanskyCommunications in Algebra, 2003
- On the rational subsets of the free groupActa Informatica, 1996
- Rational sets in commutative monoidsJournal of Algebra, 1969
- THE OCCURRENCE PROBLEM FOR FREE PRODUCTS OF GROUPSMathematics of the USSR-Sbornik, 1968
- A practical method for enumerating cosets of a finite abstract groupProceedings of the Edinburgh Mathematical Society, 1936
- Die Untergruppen der freien GruppenAbhandlungen aus dem Mathematischen Seminar der Universitat Hamburg, 1927