# The Identity Problem in the special affine group of $\mathbb{Z}^{2}$

Ruiwen Dong  University of Oxford
Oxford, United Kingdom
<EMAIL_ADDRESS>
###### Abstract

We consider semigroup algorithmic problems in the Special Affine group
$\mathsf{SA}(2,\mathbb{Z})=\mathbb{Z}^{2}\rtimes\mathsf{SL}(2,\mathbb{Z})$,
which is the group of affine transformations of the lattice $\mathbb{Z}^{2}$
that preserve orientation. Our paper focuses on two decision problems
introduced by Choffrut and Karhumäki (2005): the _Identity Problem_ (does a
semigroup contain a neutral element?) and the _Group Problem_ (is a semigroup
a group?) for finitely generated sub-semigroups of
$\mathsf{SA}(2,\mathbb{Z})$. We show that both problems are decidable and NP-
complete. Since
$\mathsf{SL}(2,\mathbb{Z})\leq\mathsf{SA}(2,\mathbb{Z})\leq\mathsf{SL}(3,\mathbb{Z})$,
our result extends that of Bell, Hirvensalo and Potapov (SODA 2017) on the NP-
completeness of both problems in $\mathsf{SL}(2,\mathbb{Z})$, and contributes
a first step towards the open problems in $\mathsf{SL}(3,\mathbb{Z})$.

###### Index Terms:

matrix semigroup, special affine group, Identity Problem, Group Problem.

##  I Introduction

### Algorithmic problems in matrix semigroups

The computational theory of matrix groups and semigroups is one of the oldest
and most well-developed parts of computational algebra. The area plays an
essential role in analysing system dynamics, and has numerous applications in
automata theory, program analysis, and interactive proof systems [1, 2, 3, 4,
5]. The earliest studied algorithmic problems for groups and semigroups are
the _Semigroup Membership_ and the _Group Membership_ problems, introduced
respectively by Markov [6] and Mikhailova [7] in the 1940s and 1960s. For both
problems, we work in a fixed matrix group $G$. The input is a finite set of
matrices $\mathcal{G}=\\{A_{1},\ldots,A_{K}\\}$ in $G$ and a target matrix
$A\in G$. Denote by $\langle\mathcal{G}\rangle$ the semigroup generated by
$\mathcal{G}$, and by $\langle\mathcal{G}\rangle_{grp}$ the group generated by
$\mathcal{G}$.

  1. i.

(Semigroup Membership) decide whether $\langle\mathcal{G}\rangle$ contains
$A$.

  2. ii.

(Group Membership) decide whether $\langle\mathcal{G}\rangle_{grp}$ contains
$A$.

Both problems are undecidable in general matrix groups by classical results of
Markov and Mikhailova [6, 7]. In this paper, we consider the _Identity
Problem_ and the _Group Problem_ , introduced by Choffrut and Karhumäki [3] in
2005. These two decision problems concern the _structure_ of semigroups rather
than their _membership_. Fix a matrix group $G$, the input for both problems
is a finite set of matrices $\mathcal{G}=\\{A_{1},\ldots,A_{K}\\}$ in $G$.

  1. iii.

(Identity Problem) decide whether $\langle\mathcal{G}\rangle$ contains the
neutral element $I$ of $G$.

  2. iv.

(Group Problem) decide whether $\langle\mathcal{G}\rangle$ is a group.

Apart from their obvious use in determining structural properties of a
semigroup111For example, given a decision procedure for the Group Problem, one
can compute a generating set for the _group of units_ (set of of invertible
elements) of a finitely generated semigroup $\langle\mathcal{G}\rangle$ [8].,
the Identity Problem and the Group Problem are closely related to222In fact,
decidability of Semigroup Membership subsumes decidability of the Identity
Problem and the Group Problem. the more difficult Semigroup Membership
problem. Usually, the solution to the Identity Problem is the most essential
special case on the way to building an algorithm for the Semigroup Membership
problem. We also point out that there are significantly more available
algorithms for groups then there are for semigroups, therefore performing
preliminary checks using the Group Problem can help decide Semigroup
Membership in many special cases (see Section VI).

All four algorithmic problems remain undecidable even for matrices of small
dimensions. The _Special Linear group_ of dimension $n$, denoted by
$\mathsf{SL}(n,\mathbb{Z})$, is defined as the group of $n\times n$ integer
matrices with determinant one. Mikhailova famously showed undecidability of
the Group Membership problem (and hence also Semigroup Membership) in
$\mathsf{SL}(4,\mathbb{Z})$ [7]. Later, Bell and Potapov showed undecidability
of the Identity Problem and the Group Problem in $\mathsf{SL}(4,\mathbb{Z})$
[9]. Both undecidability results stem from the fact that
$\mathsf{SL}(4,\mathbb{Z})$ contains as a subgroup a direct product of two
non-abelian free groups. In dimension two, the Semigroup Membership problem in
$\mathsf{SL}(2,\mathbb{Z})$ was shown to be decidable in EXPSPACE by Choffrut
and Karhumäki [3]; Group Membership was shown to be in PTIME by Lohrey [10];
the Identity Problem and the Group Problem were shown to be NP-complete by
Bell, Hirvensalo and Potapov [11]. It remains an intricate open problem
whether any of these four algorithmic problems is decidable in
$\mathsf{SL}(3,\mathbb{Z})$. Nevertheless, Ko, Niskanen and Potapov [12]
recently showed that $\mathsf{SL}(3,\mathbb{Z})$ cannot embed pairs of words
over an alphabet of size two, suggesting that all four problems in
$\mathsf{SL}(3,\mathbb{Z})$ might be decidable. The following table I
summarizes the state of art as well as our result, the group
$\mathsf{SA}(2,\mathbb{Z})$ will be introduced in the next subsection.

|  Semigrp Mem. |  Group Mem. |  Identity & Grp Prb.
---|---|---|---
$\mathsf{SL}(2,\mathbb{Z})$ |  EXPSPACE [3] |  PTIME [10] |  NP-complete [11]
$\mathsf{SA}(2,\mathbb{Z})$ |  ? |  Decidable [13] |  NP-complete∗
$\mathsf{SL}(3,\mathbb{Z})$ |  ? |  ? |  ?
$\mathsf{SL}(4,\mathbb{Z})$ |  Undec. [7] |  Undec. [7] |  Undec. [9]
TABLE I:  * = Our result.

### The Special Affine group $\mathsf{SA}(2,\mathbb{Z})$

In this paper we focus on an intermediate group between
$\mathsf{SL}(2,\mathbb{Z})$ and $\mathsf{SL}(3,\mathbb{Z})$: the _Special
Affine group_ $\mathsf{SA}(2,\mathbb{Z})$. This affine analogue of
$\mathsf{SL}(2,\mathbb{Z})$ is defined as the group of affine transformations
of $\mathbb{Z}^{2}$ that preserve orientation. Written as matrices, elements
of $\mathsf{SA}(2,\mathbb{Z})$ are $3\times 3$ integer matrices of the
following form.

$\mathsf{SA}(2,\mathbb{Z})\coloneqq\left\\{\begin{pmatrix}A&\boldsymbol{a}\\\
0&1\\\
\end{pmatrix}\;\middle|\;A\in\mathsf{SL}(2,\mathbb{Z}),\boldsymbol{a}\in\mathbb{Z}^{2}\right\\}.$

To be precise, elements of $\mathsf{SA}(2,\mathbb{Z})$ are represented using
matrices with _binary encoded_ entries. We denote by $(A,\boldsymbol{a})$ the
element $\begin{pmatrix}A&\boldsymbol{a}\\\ 0&1\\\ \end{pmatrix}$, then the
neutral element of $\mathsf{SA}(2,\mathbb{Z})$ is $(I,\boldsymbol{0})$;
multiplication in $\mathsf{SA}(2,\mathbb{Z})$ is given by

$(A,\boldsymbol{a})\cdot(B,\boldsymbol{b})=(AB,A\boldsymbol{b}+\boldsymbol{a}).$

Naturally, $\mathsf{SA}(2,\mathbb{Z})$ has a subgroup
$\\{(A,\boldsymbol{0})\mid A\in\mathsf{SL}(2,\mathbb{Z})\\}$
$\cong\mathsf{SL}(2,\mathbb{Z})$.

Special Affine groups are important in the context of many fundamental
problems, such as Lie groups [14], polyhedral geometry [15], dynamical systems
[16], quadrics [17], computer vision [18, 19] and gauge theory [20]. Apart
from the intrinsic interest to study $\mathsf{SA}(2,\mathbb{Z})$, we also
point out that the Special Affine group has tight connections to various
reachability problems. Some of the central questions in automated verification
include reachability problems in _Affine Vector Addition Systems_ and _Affine
Vector Addition Systems with states (Affine VASS)_ over the integers [21].
While both problems as well as many of their variations have been shown to be
decidable in dimension one and undecidable for dimension three [22, 23], few
results are known for dimension two. Since the study of these reachability
problems in dimension two necessitates the study of sub-semigroups of
$\mathsf{SA}(2,\mathbb{Z})$, the techniques introduced in our paper may
provide insights into these open problems.

Currently, among the four algorithmic problems introduced in the beginning,
the only known result in $\mathsf{SA}(2,\mathbb{Z})$ is decidability of the
Group Membership problem. This can be deduced from the recent work of Delgado
[13], who showed decidability of the Group Membership problem in the
semidirect product $\mathbb{Z}^{m}\rtimes F$, where $F$ is a free group.
Delgado’s result relies on a generalization of the Stalling automata, and can
therefore be extended to the case where $F$ is _virtually free_. This can then
be applied to
$\mathsf{SA}(2,\mathbb{Z})=\mathbb{Z}^{2}\rtimes\mathsf{SL}(2,\mathbb{Z})$,
since $\mathsf{SL}(2,\mathbb{Z})$ is virtually free.

In this paper, we step further by considering sub-semigroups of
$\mathsf{SA}(2,\mathbb{Z})$. We show decidability and NP-completeness of the
Identity Problem and the Group Problem in $\mathsf{SA}(2,\mathbb{Z})$. This
extends the NP-completeness result of Bell et al. for the Identity Problem and
the Group Problem in $\mathsf{SL}(2,\mathbb{Z})$, and contributes a first step
towards solving problems in $\mathsf{SL}(3,\mathbb{Z})$.

The NP-hard lower bounds in $\mathsf{SA}(2,\mathbb{Z})$ directly follows from
its embedding of the subgroup $\mathsf{SL}(2,\mathbb{Z})$. In order to prove
decidability and the NP upper bounds, our main idea is the following. Given a
finitely generated sub-semigroup $\langle\mathcal{G}\rangle$ of
$\mathsf{SA}(2,\mathbb{Z})$, we show that we can without loss of generality
suppose its image under the natural projection
$p\colon\mathsf{SA}(2,\mathbb{Z})\rightarrow\mathsf{SL}(2,\mathbb{Z})$ to be a
group, using a classic result for $\mathsf{SL}(2,\mathbb{Z})$. If
$p(\langle\mathcal{G}\rangle)$ is a group, we then invoke an effective version
of the _Tits alternative_ , which shows that either
$p(\langle\mathcal{G}\rangle)$ contains a non-abelian free subgroup, or it is
virtually solvable. In the first case we show that $\langle\mathcal{G}\rangle$
is always a group, while in the second case we further simplify the problem by
identifying six subcases for $p(\langle\mathcal{G}\rangle)$. Our proof
combines two viewpoints: a group theoretic viewpoint of
$\mathsf{SL}(2,\mathbb{Z})$ as a virtually free group, and a geometric
viewpoint of $\mathsf{SA}(2,\mathbb{Z})$ as elements acting on the lattice
$\mathbb{Z}^{2}$.

Beyond the Identity Problem and the Group Problem, we will discuss some
obstacles to generalizing our results to the Semigroup Membership problem in
$\mathsf{SA}(2,\mathbb{Z})$. Our results actually show that Semigroup
Membership in $\mathsf{SA}(2,\mathbb{Z})$ is decidable in many cases under
additional constraints. We identify one of the remaining difficult cases,
namely when $\langle\mathcal{G}\rangle$ is isomorphic to a sub-semigroup of
the semidirect product $\mathbb{Z}[\lambda]\rtimes_{\lambda}\mathbb{Z}$, where
$\lambda$ is a quadratic integer. The Semigroup Membership problem in
$\mathbb{Z}[\lambda]\rtimes_{\lambda}\mathbb{Z}$ remains open. However, the
group $\mathbb{Z}[\lambda]\rtimes_{\lambda}\mathbb{Z}$ bears certain
similarities to the _Baumslag-Solitar group_
$\mathsf{BS}(1,q)\coloneqq\mathbb{Z}[\frac{1}{q}]\rtimes_{q}\mathbb{Z}$; and a
recent result by Cadilhac, Chistikov and Zetzsche [24] showed decidability of
the _rational subset membership problem_ 333The rational subset membership
problem subsumes the Semigroup Membership problem. in $\mathsf{BS}(1,q)$ by
considering rational languages of _base- $q$ expansions_. Despite some visible
difficulties, it would be interesting in the future to adapt this approach to
study the Semigroup Membership problem in
$\mathbb{Z}[\lambda]\rtimes_{\lambda}\mathbb{Z}$, namely by considering
rational languages of _base- $\lambda$ expansions_ [25], where $\lambda$ is an
algebraic integer.

##  II Preliminaries

### Words, semigroups and groups

Let $G$ be an arbitrary group. Let $\mathcal{A}=\\{a_{1},\ldots,a_{K}\\}$ be a
set of elements in $G$. Considering $\mathcal{A}$ as an alphabet, denote by
$\mathcal{A}^{*}$ the set of words over $\mathcal{A}$. For an arbitrary word
$w=a_{i_{1}}a_{i_{2}}\cdots a_{i_{m}}\in\mathcal{A}^{*}$, by multiplying
consecutively the elements appearing in $w$, we can evaluate $w$ as an element
$\pi(w)$ in $G$. We say that the word $w$ _represents_ the element $\pi(w)$.
The semigroup $\langle\mathcal{A}\rangle$ generated by $\mathcal{A}$ is hence
the set of elements in $G$ that are represented by _non-empty_ words in
$\mathcal{A}^{*}$.

A word $w$ over the alphabet $\mathcal{A}$ is called _full-image_ if every
letter in $\mathcal{A}$ has at least one occurrence in $w$.

######  Lemma 1.

Let $\mathcal{A}=\\{a_{1},\ldots,a_{K}\\}$ be a set of elements in a group
$G$. Consider the following conditions:

  1. (i)

The neutral element $I$ of $G$ is represented by a full-image word over
$\mathcal{A}$.

  2. (ii)

The semigroup $\langle\mathcal{A}\rangle$ is a group.

  3. (iii)

Every element $A\in\langle\mathcal{A}\rangle$ is represented by a full-image
word over $\mathcal{A}$.

Then $(i)\Longleftrightarrow(ii)$, and $(ii)\Longrightarrow(iii)$.

Let
$\mathcal{G}=\\{(A_{1},\boldsymbol{a}_{1}),\ldots,(A_{K},\boldsymbol{a}_{K})\\}$
be a set of elements in $\mathsf{SA}(2,\mathbb{Z})$. Suppose that an element
$A\in\langle A_{1},\ldots,A_{K}\rangle$ in $\mathsf{SL}(2,\mathbb{Z})$ is
represented by a full-image word $w$ in the alphabet
$\\{A_{1},\ldots,A_{K}\\}$. Then replacing each letter $A_{i}$ in $w$ by
$(A_{i},\boldsymbol{a}_{i})$, we obtain a product
$(A,\boldsymbol{a})\in\mathsf{SA}(2,\mathbb{Z})$ for some
$\boldsymbol{a}\in\mathbb{Z}^{2}$, represented by a full-image word over
$\mathcal{G}$.

The following observation shows that decidability of the Group Problem implies
decidability of the Identity Problem.

######  Lemma 2 ([9]).

Given a subset $\mathcal{A}$ of a group $G$, the semigroup
$\langle\mathcal{A}\rangle$ contains the neutral element $I$ if and only if
there exists a non-empty subset $\mathcal{H}\subseteq\mathcal{A}$ such that
$\langle\mathcal{H}\rangle$ is a group.

### Linear algebra

For an arbitrary matrix $A\in\mathsf{SL}(2,\mathbb{Z})$, an _invariant
subspace_ of $A$ is a $\mathbb{C}$-linear subspace $V$ of $\mathbb{C}^{2}$
such that $AV=V$. If the eigenvalues of $A$ are reals, then one can suppose
that the invariant spaces of $A$ are subspaces of $\mathbb{R}^{2}$. Denote by
$\operatorname{Lat}(A)$ the set of _dimension one_ invariant subspaces of $A$.
It is easy to see that if $A\notin\\{I,-I\\}$, then $\operatorname{Lat}(A)$
has one or two elements.

Two matrices $A$ and $B$ are called _conjugates_ over a field $\mathbb{K}$ if
$P^{-1}AP=B$ for some matrix $P$ with entries in $\mathbb{K}$. This is denoted
as $A\overset{\mathbb{K}}{\sim}B$. Two matrices
$A,B\in\mathsf{SL}(2,\mathbb{Z})$ are called _simultaneously triangularizable_
if there exists a complex matrix $P$ such that $P^{-1}AP$ and $P^{-1}BP$ are
both upper-triangular. It is easy to see that if
$\operatorname{Lat}(A)\cap\operatorname{Lat}(B)\neq\emptyset$, then $A$ and
$B$ are simultaneously triangularizable.

### Group theory

For a general reference on group theory, see [26].

######  Definition 3.

A group $G$ is called _solvable_ if its _derived series_

$G=G^{(0)}\trianglerighteq G^{(1)}\trianglerighteq
G^{(2)}\trianglerighteq\cdots,$

where $G^{(i+1)}$ is the commutator subgroup444The commutator subgroup of a
group $H$ is the subgroup generated by the elements $ghg^{-1}h^{-1}$ where
$g,h\in H$. of $G^{(i)}$, eventually reaches the trivial group.

Every subgroup of a solvable group is solvable [26, Proposition 13.91].
Abelian groups are obviously solvable. For any field $\mathbb{K}$ and integer
$n$, denote by $\mathsf{T}(n,\mathbb{K})$ the group of $n\times n$ invertible
upper-triangular matrices with entries in $\mathbb{K}$. Then
$\mathsf{T}(n,\mathbb{K})$ is a solvable group [27]. In particular, if two
matrices $A,B\in\mathsf{SL}(2,\mathbb{Z})$ are simultaneously
triangularizable, then the group $G$ they generate is isomorphic to a subgroup
of $\mathsf{T}(2,\mathbb{C})$; thus $G$ is solvable.

Given an alphabet $\Sigma$, define the corresponding group alphabet
$\Sigma^{\pm}\coloneqq\Sigma\cup\\{a^{-1}\mid a\in\Sigma\\}$, where $a^{-1}$
is a new symbol. There is a natural involution $(\cdot)^{-1}$ over
$\left(\Sigma^{\pm}\right)^{*}$ defined by $(a^{-1})^{-1}$ and $(a_{1}\cdots
a_{m})^{-1}=a_{m}^{-1}\cdots a_{1}^{-1}$. A word over the alphabet is called
_reduced_ if it does not contain consecutive letters $aa^{-1}$ or $a^{-1}a$.
For a word $w$ over the alphabet $\Sigma^{\pm}$, define
$\operatorname{red}(w)$ to be the reduced word obtained by iteratively
replacing consecutive letters $aa^{-1}$ and $a^{-1}a$ with the empty string.
The _free group_ $F(\Sigma)$ over $\Sigma$ is then defined as the set of
reduced words over the alphabet $\Sigma^{\pm}$, where multiplication is given
by $v\cdot w=\operatorname{red}(vw)$, and inversion is given by the involution
$(\cdot)^{-1}$. A group is called _free_ if it is a free group over some
alphabet. The free group $F(\Sigma)$ is abelian if and only if the cardinality
of $\Sigma$ is zero or one, in which case $F(\Sigma)$ is trivial or isomorphic
to the infinite cyclic group $\mathbb{Z}$.

######  Theorem 4 (Nielsen–Schreier [28, Chapter I, Theorem 5]).

Every subgroup of a free group is free.

Given an arbitrary group $G$ with neutral element $I$. An element $T\in G$ is
called _torsion_ if $T\neq I$ and $T^{m}=I$ for some $m>1$. A group is called
_torsion-free_ if it does not contain a torsion element. In particular, a free
group is torsion-free.

A group is called _virtually solvable_ if it admits a finite index subgroup
that is solvable. Similarly, a group is called _virtually free_ if it admits a
finite index subgroup that is free. The following is a classic result.

######  Theorem 5 ([29]).

The group $\mathsf{SL}(2,\mathbb{Z})$ is virtually free. Moreover, it contains
a finite index free subgroup $F(\\{S,T\\})$ over two generators.

Based on this fact, Bell et al. showed the following complexity result.

######  Theorem 6 ([11]).

The Identity Problem and the Group Problem in $\mathsf{SL}(2,\mathbb{Z})$ are
NP-complete.

Here, the input elements in $\mathsf{SL}(2,\mathbb{Z})$ are represented using
matrices with binary encoded entries.

### Classification of elements in $\mathsf{SL}(2,\mathbb{Z})$

Let $A=\begin{pmatrix}a&b\\\ c&d\\\ \end{pmatrix}$ be a matrix in
$\mathsf{SL}(2,\mathbb{Z})$. The characteristic polynomial of $A$ is
$f(X)=X^{2}-(a+d)X+(ad-bc)=X^{2}-(a+d)X+1$. Consider the five following cases.

  1. (i)

$a+d=0$.

In this case, $A\overset{\mathbb{Q}(i)}{\sim}\begin{pmatrix}i&0\\\ 0&-i\\\
\end{pmatrix}$, the eigenvalues of $A$ are $i$ and $-i$. We have $A^{4}=I$, so
$A$ is a torsion element.

  2. (ii)

$|a+d|=1$.

In this case, $A\overset{\mathbb{Q}(\omega)}{\sim}\begin{pmatrix}\omega&0\\\
0&\omega^{-1}\\\ \end{pmatrix}$, where $\omega=\frac{1+\sqrt{3}i}{2}$ or
$\frac{-1+\sqrt{3}i}{2}$. In both cases, we have $A^{6}=I$, so $A$ is a
torsion element.

  3. (iii)

$a+d=2$.

In this case, either $A=I$, or
$A\overset{\mathbb{Q}}{\sim}\begin{pmatrix}1&1\\\ 0&1\\\ \end{pmatrix}$. In
the second situation, we call $A$ a _shear_. The only eigenvalue of $A$ is 1.
If $A$ is a shear, then $\operatorname{Lat}(A)$ has exactly one element. See
Figure 2 for an illustration.

  4. (iv)

$a+d=-2$.

In this case, either $A=-I$, or
$A\overset{\mathbb{Q}}{\sim}\begin{pmatrix}-1&1\\\ 0&-1\\\ \end{pmatrix}$. In
the second situation, we call $A$ a _twisted inversion_. In particular, if $A$
is a twisted inversion, then $(A+I)^{2}=0$, and $A^{2}$ is a shear, and
$\operatorname{Lat}(A)$ has exactly one element.

  5. (v)

$|a+d|\geq 3$.

In this case, $A\overset{\mathbb{R}}{\sim}\begin{pmatrix}\lambda&0\\\
0&\lambda^{-1}\\\ \end{pmatrix}$, where $\lambda$ is the root of $f(X)$ such
that $|\lambda|\geq 1$. Furthermore, $\lambda$ is real. In this case, we call
$A$ a _scale_. If $\lambda>0$, we call $A$ a _positive scale_ ; if
$\lambda<0$, we call $A$ an _inverting scale_. In both cases,
$\operatorname{Lat}(A)$ has two elements, one element is the invariant space
corresponding to the eigenvalue $\lambda$, and is called the _stretching
direction_ ; the other element is the invariant space corresponding to the
eigenvalue $\lambda^{-1}$, and is called the _compressing direction_. See
Figure 2 for an illustration.

Figure 1: Illustration for a (positive) scale.

Figure 2: Illustration for a shear.

##  III Overview of decision procedures

In this section we give an overview of the decision procedures for the
Identity Problem and the Group Problem in $\mathsf{SA}(2,\mathbb{Z})$. We
state two propositions (Propositions 9 and 10) regarding the structure of sub-
semigroups of $\mathsf{SA}(2,\mathbb{Z})$. Assuming these propositions, we
prove NP-completeness of the Identity Problem and the Group Problem in
$\mathsf{SA}(2,\mathbb{Z})$. The proofs of propositions 9 and 10 are delayed
until Section IV and V.

We now first focus on solving the Group Problem, because by Lemma 2,
decidability of the Group Problem will imply decidability of the Identity
Problem. Fix a set
$\mathcal{G}\coloneqq\\{(A_{1},\boldsymbol{a}_{1}),\ldots,(A_{K},\boldsymbol{a}_{K})\\}$
of elements in $\mathsf{SA}(2,\mathbb{Z})$. The following lemma shows that, if
the semigroup $G\coloneqq\langle A_{1},\ldots,A_{K}\rangle$ is not a group,
then $\langle\mathcal{G}\rangle$ is also not a group. Therefore, to decide
whether $\langle\mathcal{G}\rangle$ is a group, we can focus on the case where
$G$ is a group.

######  Lemma 7.

Let
$\mathcal{G}\coloneqq\\{(A_{1},\boldsymbol{a}_{1}),\ldots,(A_{K},\boldsymbol{a}_{K})\\}$
be a set of elements of $\mathsf{SA}(2,\mathbb{Z})$. If the semigroup
$G\coloneqq\langle A_{1},\ldots,A_{K}\rangle$ is not a group, then the
semigroup $\langle\mathcal{G}\rangle$ is also not a group.

###### Proof.

If $\langle\mathcal{G}\rangle$ is a group, then
$(A_{i}^{-1},-A_{i}^{-1}\boldsymbol{a}_{i})=(A_{i},\boldsymbol{a}_{i})^{-1}\in\langle\mathcal{G}\rangle$
for all $i$. Therefore, $A_{i}^{-1}\in\langle A_{1},\ldots,A_{K}\rangle$ for
all $i$. Thus $\langle A_{1},\ldots,A_{K}\rangle$ is a group. ∎

Suppose now that $G$ is a group. The key idea of solving the Group Problem is
the following dichotomy known as the _Tits alternative_.

######  Theorem 8 (Tits alternative [30, Theorem 1], effective version [27,
Theorem 1.1]).

For any $n$, given a finitely generated subgroup $G$ of
$\mathsf{SL}(n,\mathbb{Z})$, exactly one of the following is true:

  1. (i)

$G$ contains a non-abelian free subgroup.

  2. (ii)

$G$ is virtually solvable.

Furthermore, given a set of generators of $G$, it is decidable in PTIME which
of the two cases is true.

In case of $G$ containing a non-abelian free subgroup, we will prove the
following Proposition 9, which shows that the semigroup
$\langle\mathcal{G}\rangle$ must be a group.

######  Proposition 9.

Let
$\mathcal{G}=\\{(A_{1},\boldsymbol{a}_{1}),\ldots,(A_{K},\boldsymbol{a}_{K})\\}$
be a set of elements of $\mathsf{SA}(2,\mathbb{Z})$, such that the semigroup
$G\coloneqq\langle A_{1},\ldots,A_{K}\rangle$ is a group. If $G$ contains a
non-abelian free subgroup, then $\langle\mathcal{G}\rangle$ is a group.

The proof of Proposition 9 is highly non-trivial and will be given in Section
IV. The proof is mainly geometric - it consists of analysing the action of
$\mathsf{SA}(2,\mathbb{Z})$ on the lattice $\mathbb{Z}^{2}$.

In case of $G$ being virtually solvable, we will prove the following
Proposition 10 which refines the Tits alternative. In particular, it shows
that virtually solvable subgroups of $\mathsf{SL}(2,\mathbb{Z})$ have
relatively simple structure: it is either trivial, or it contains a torsion
element, or it is infinite cyclic.

######  Proposition 10.

Let
$\mathcal{G}=\\{(A_{1},\boldsymbol{a}_{1}),\ldots,(A_{K},\boldsymbol{a}_{K})\\}$
be a set of elements of $\mathsf{SA}(2,\mathbb{Z})$, such that the semigroup
$G\coloneqq\langle A_{1},\ldots,A_{K}\rangle$ is a group. If $G$ is virtually
solvable, then exactly one of the following six conditions holds:

  1. (i)

$G$ is the trivial group.

  2. (ii)

$G$ contains a torsion element.

  3. (iii)

$G=\langle A\rangle_{grp}$, where $A$ is a twisted inversion.

  4. (iv)

$G=\langle A\rangle_{grp}$, where $A$ is a shear.

  5. (v)

$G=\langle A\rangle_{grp}$, where $A$ is an inverting scale.

  6. (vi)

$G=\langle A\rangle_{grp}$, where $A$ is a positive scale.

Furthermore, in cases (ii), (iii) and (v), the semigroup
$\langle\mathcal{G}\rangle$ is a group. Overall, it is decidable in PTIME
whether $\langle\mathcal{G}\rangle$ is a group.

Proposition 10 will be proved in Section V. The proof will be mainly algebraic
- it consists of analysing the structure of sub-semigroups of a virtually
solvable group. Lemma 7-Proposition 10 yield the decidability of the Group
Problem (and consequently, the Identity Problem) in
$\mathsf{SA}(2,\mathbb{Z})$. An overview of the procedure is given in
Algorithm 1. The justification of each step is given in parentheses with
reference to the corresponding lemmas or propositions.

######  Theorem 11.

The Group Problem and the Identity Problem in $\mathsf{SA}(2,\mathbb{Z})$ are
NP-complete.

###### Proof.

The NP-hard lower bounds come from the NP-completeness of both problems in the
subgroup $\mathsf{SL}(2,\mathbb{Z})\cong\\{(A,\boldsymbol{0})\mid
A\in\mathsf{SL}(2,\mathbb{Z})\\}\leq\mathsf{SA}(2,\mathbb{Z})$ (see Theorem
6).

To show decidability and the NP upper bounds, we first solve the Group
Problem. Let
$\mathcal{G}=\\{(A_{1},\boldsymbol{a}_{1}),\ldots,(A_{K},\boldsymbol{a}_{K})\\}$
be a set in $\mathsf{SA}(2,\mathbb{Z})$. As a first step, we can check whether
$\langle A_{1},\ldots,A_{K}\rangle$ is a group in NP (Theorem 6). If $\langle
A_{1},\ldots,A_{K}\rangle$ is not a group, then $\langle\mathcal{G}\rangle$ is
not a group by Lemma 7.

Suppose now that $\langle A_{1},\ldots,A_{K}\rangle$ is a group. As the second
step, we check in PTIME whether $\langle A_{1},\ldots,A_{K}\rangle$ contains a
non-abelian free subgroup using Theorem 8. If $\langle
A_{1},\ldots,A_{K}\rangle$ contains a non-abelian free subgroup, then the
Group Problem has a positive answer by Proposition 9. Otherwise, $\langle
A_{1},\ldots,A_{K}\rangle$ is virtually solvable, and we can decide the Group
Problem in PTIME using Proposition 10. In total, the Group Problem for
$\mathcal{G}$ can be decided in NP.

Next we solve the Identity Problem. Note that by Lemma 2,
$I\in\langle\mathcal{G}\rangle$ if and only if there exists a non-empty subset
$\mathcal{H}$ of $\mathcal{G}$ such that the semigroup
$\langle\mathcal{H}\rangle$ is a group. Therefore, it suffices to guess a non-
empty subset $\mathcal{H}$ of $\mathcal{G}$, and check whether
$\langle\mathcal{H}\rangle$ is a group. This can be done in NP using the above
procedure of the Group Problem. ∎

Algorithm 1 Deciding the Group Problem for a subset of
$\mathsf{SA}(2,\mathbb{Z})$.

Input:

A subset
$\mathcal{G}=\\{(A_{1},\boldsymbol{a}_{1}),\ldots,(A_{K},\boldsymbol{a}_{K})\\}$
of $\mathsf{SA}(2,\mathbb{Z})$.

Output:

True or False.

  1. 1.

Decide whether the semigroup $\langle A_{1},\ldots,A_{K}\rangle$ is a group by
Theorem 6. If not a group, return False. (Lemma 7)

  2. 2.

Let $G\coloneqq\langle
A_{1},\ldots,A_{K}\rangle\leq\mathsf{SL}(2,\mathbb{Z})$, decide for $G$ which
case of Theorem 8 is true.

  3. 3.

If $G$ contains a non-abelian free subgroup, return True. (Proposition 9)

  4. 4.

If $G$ is virtually free, decide which case of Proposition 10 is true using
Lemma 16.

    1. (i)

If $G$ is trivial, decide whether $n_{1}\boldsymbol{a}_{1}+\cdots
n_{K}\boldsymbol{a}_{K}=\boldsymbol{0}$ has a solution over
$\mathbb{Z}_{>0}^{K}$. If yes, return True, otherwise return False.
(Proposition 17)

    2. (ii)

If $G$ contains a torsion element, return True. (Proposition 18)

    3. (iii)

If $G=\langle A\rangle_{grp}$, where $A$ is a twisted inversion, return True.
(Proposition 19)

    4. (iv)

If $G=\langle A\rangle_{grp}$, where $A$ is a shear, compute the set
$\varphi(\mathcal{G})$ defined by Equation (6). Decide whether
$\langle\varphi(\mathcal{G})\rangle$ is a group by Theorem 20. If yes, return
True; if not, return False. (Corollary 21)

    5. (v)

If $G=\langle A\rangle_{grp}$, where $A$ is a inverting scale, return True.
(Proposition 22)

    6. (vi)

If $G=\langle A\rangle_{grp}$, where $A$ is a positive scale, compute the set
$\mathcal{S}$ defined by Equation (8). Decide whether the condition in
Proposition 26 is satisfied for $\mathcal{S}$. If yes, return True; if not,
return False. (Corollary 27)

##  IV Non abelian free subgroup

In this section we prove Proposition 9. Omitted proofs of technical results
can be found in the appendix of the full version of this paper. Let $A$ be a
scale with $\operatorname{Lat}(A)=\\{V,W\\}$. Since $V,W$ are distinct one
dimensional subspaces of $\mathbb{R}^{2}$, every element
$\boldsymbol{x}\in\mathbb{R}^{2}$ can be written uniquely as
$\boldsymbol{x}=\boldsymbol{x}_{V}+\boldsymbol{x}_{W}$, where
$\boldsymbol{x}_{V}\in V,\boldsymbol{x}_{W}\in W$. We will adopt this notation
in the following lemma. For an element $\boldsymbol{y}\in\mathbb{R}^{2}$,
$\boldsymbol{y}_{V},\boldsymbol{y}_{W}$ are defined similarly.

######  Lemma 12.

Let $(A,\boldsymbol{a}),(B,\boldsymbol{b})$ be elements of
$\mathsf{SA}(2,\mathbb{Z})$ such that
$(A,\boldsymbol{a})\cdot(B,\boldsymbol{b})=(I,\boldsymbol{x})$ for some
$\boldsymbol{x}\in\mathbb{Z}^{2}$. Suppose $A$ is a scale; denote by $V,W$ the
elements of $\operatorname{Lat}(A)$, and suppose $\boldsymbol{x}\notin V\cup
W$. Let $\boldsymbol{v}$ be any non-zero vector in the subspace $V$.

Then for every $\varepsilon>0$, there exists a word
$w\in\\{(A,\boldsymbol{a}),(B,\boldsymbol{b})\\}^{*}$, such that
$(A,\boldsymbol{a})\cdot w\cdot(B,\boldsymbol{b})=(I,\boldsymbol{y})$, where
$\boldsymbol{y}\in\mathbb{Z}^{2}$ satisfies

$1-\frac{|\boldsymbol{v}^{\top}\boldsymbol{y}|}{|\boldsymbol{v}||\boldsymbol{y}|}<\varepsilon,\quad\boldsymbol{y}_{V}^{\top}\boldsymbol{x}_{V}>0,\quad\boldsymbol{y}_{W}^{\top}\boldsymbol{x}_{W}>0.$
(1)

In other words, the angle $\theta$ between $\boldsymbol{y}$ and $V$ satisfies
$1-\cos\theta<\varepsilon$. Also, $\boldsymbol{y}$ and $\boldsymbol{x}$ lie in
same cone out of the four cut by $V$ and $W$. See Figure 4 for an
illustration.

Figure 3: Illustration for Lemma 12.

Figure 4: Illustration for Lemma 13.

The idea of proving Lemma 12 is to use the word
$w=(A,\boldsymbol{a})^{m}(B,\boldsymbol{b})^{m}$ or
$w=(B,\boldsymbol{b})^{m}(A,\boldsymbol{a})^{m}$ for large enough $m$,
according to whether $V$ is a stretching or compressing direction. A similar
lemma can be proved for shears:

######  Lemma 13.

Let $(A,\boldsymbol{a}),(B,\boldsymbol{b})$ be elements of
$\mathsf{SA}(2,\mathbb{Z})$ such that
$(A,\boldsymbol{a})\cdot(B,\boldsymbol{b})=(I,\boldsymbol{x})$ for some
$\boldsymbol{x}\in\mathbb{Z}^{2}$. Suppose $A$ is a shear,
$\operatorname{Lat}(A)=\\{V\\}$, and $\boldsymbol{x}\notin V$. Let
$\boldsymbol{v}$ be any non-zero vector in the subspace $V$.

Then for every $\varepsilon>0$, there exists a word
$w\in\\{(A,\boldsymbol{a}),(B,\boldsymbol{b})\\}^{*}$, such that
$(A,\boldsymbol{a})\cdot w\cdot(B,\boldsymbol{b})=(I,\boldsymbol{y})$, where
$\boldsymbol{y}\in\mathbb{Z}^{2}$ satisfies

$1-\frac{\boldsymbol{v}^{\top}\boldsymbol{y}}{|\boldsymbol{v}||\boldsymbol{y}|}<\varepsilon$
(2)

and $\boldsymbol{y}$ and $\boldsymbol{x}$ lie in same halfspace cut by $V$. In
other words, the angle $\theta$ between $\boldsymbol{y}$ and $\boldsymbol{v}$
satisfies $1-\cos\theta<\varepsilon$. See Figure 4 for an illustration.

We now prove Proposition 9. See 9

###### Proof.

Suppose that the group $\langle A_{1},\ldots,A_{K}\rangle$ contains a non-
abelian free subgroup, in particular, it contains a subgroup isomorphic to the
free group $F_{2}$ of two generators. Let $A,B$ be elements of $\langle
A_{1},\ldots,A_{K}\rangle$ that generate a free group. Since $A,B$ are non-
torsion, they are twisted inversions, scales, or shears. Hence,
$A^{2},B^{2}\in\langle A_{1},\ldots,A_{K}\rangle$ are positive scales or
shears. Since $A$ and $B$ generate a free group, $A^{2}$ and $B^{2}$ also
generate a free group. Therefore, we can replace $A,B$ by $A^{2},B^{2}$, and
without loss of generality suppose $A$ and $B$ to be positive scales or
shears.

Since $\langle A_{1},\ldots,A_{K}\rangle$ is a group, $A$ and $B$ can be
represented by full-image words over the alphabet $\\{A_{1},\ldots,A_{K}\\}$
due to Lemma 1. Hence, let $(A,\boldsymbol{a})$ and $(B,\boldsymbol{b})$ be
elements in $\langle\mathcal{G}\rangle$ represented by full-image words.

Note that $A,B$ are not simultaneously triangularizable, otherwise the group
they generate is isomorphic to a subgroup of the group of upper-triangular
matrices over complex numbers, which is solvable [27]. This contradicts that
fact that $A,B$ generate a non-abelian free group (see Theorem 8). Therefore,
$\operatorname{Lat}(A)\cap\operatorname{Lat}(B)=\emptyset$. There are three
cases to consider:

  1. 1.

Both $A$ and $B$ are positive scales.

  2. 2.

One of $A$ and $B$ is a shear.

  3. 3.

Both $A$ and $B$ are shears.

Case 1. Both $A$ and $B$ are positive scales. Denote $Y=A^{-1}B^{-1}\in\langle
A_{1},\ldots,A_{K}\rangle$, we have $AYB=I$. Let
$\boldsymbol{y}\in\mathbb{Z}^{2}$ be such that
$(Y,\boldsymbol{y})\in\langle\mathcal{G}\rangle$, and let
$\boldsymbol{x}\in\mathbb{Z}^{2}$ be such that
$(A,\boldsymbol{a})(Y,\boldsymbol{y})(B,\boldsymbol{b})=(I,\boldsymbol{x})$.
If $\boldsymbol{x}=\boldsymbol{0}$, then $(I,\boldsymbol{0})$ can be
represented as a full-image word over $\mathcal{G}$, since
$(A,\boldsymbol{a})$ can. In this case, $\langle\mathcal{G}\rangle$ is a group
by Lemma 1. Otherwise, there are two subcases. Starting from any one-dimension
subspace $S$, rotate $S$ counter-clockwise and consider its sequence of
encounters with $\operatorname{Lat}(A)$ and $\operatorname{Lat}(B)$ before
finishing a full cycle. Either the sequence of encounters is a cyclic
permutation of
$(\operatorname{Lat}(A),\operatorname{Lat}(A),\operatorname{Lat}(B),\operatorname{Lat}(B))$,
or it is a cyclic permutation of
$(\operatorname{Lat}(A),\operatorname{Lat}(B),\operatorname{Lat}(A),\operatorname{Lat}(B))$.

  1. (i)

First consider the case of $(\operatorname{Lat}(A)$, $\operatorname{Lat}(A)$,
$\operatorname{Lat}(B)$, $\operatorname{Lat}(B))$. An illustration for the
proof of this case is shown in Figure 6. Denote by $V_{A},W_{A},V_{B},W_{B}$
be these subspaces in this order. Since $\boldsymbol{x}\neq\boldsymbol{0}$,
either $\boldsymbol{x}\notin V_{A}\cup W_{A}$, or $\boldsymbol{x}\notin
V_{B}\cup W_{B}$. Without loss of generality suppose $\boldsymbol{x}\notin
V_{B}\cup W_{B}$.

Let $c$ be the maximum of the cosines of angles between all pairs of subspaces
in $V_{A},W_{A},V_{B},W_{B}$. Let $0<\varepsilon<(1-|c|)/2$. Apply Lemma 12 to
$\varepsilon$, to the elements
$(A^{\prime},\boldsymbol{a}^{\prime})\coloneqq(A,\boldsymbol{a})(Y,\boldsymbol{y})$
and $(B,\boldsymbol{b})$, and to the subspaces $V_{B},W_{B}$ of
$\operatorname{Lat}(B)=\operatorname{Lat}(A^{\prime})$. (Note that
$A^{\prime}=B^{-1}$, so
$\operatorname{Lat}(A^{\prime})=\operatorname{Lat}(B)$.) Since
$(A^{\prime},\boldsymbol{a}^{\prime})(B,\boldsymbol{b})=(A,\boldsymbol{a})(Y,\boldsymbol{y})(B,\boldsymbol{b})=(I,\boldsymbol{x})$,
Lemma 12 shows there exists an element $w\in\langle\mathcal{G}\rangle$ such
that $(A^{\prime},\boldsymbol{a}^{\prime})\cdot
w\cdot(B,\boldsymbol{b})=(I,\boldsymbol{x}_{1})$, with

$1-\frac{|\boldsymbol{v}_{B}^{\top}\boldsymbol{x}_{1}|}{|\boldsymbol{v}_{B}||\boldsymbol{x}_{1}|}<\varepsilon,\;\left(\boldsymbol{x}_{1}\right)_{V_{B}}^{\top}\boldsymbol{x}_{V_{B}}>0,\;\left(\boldsymbol{x}_{1}\right)_{W_{B}}^{\top}\boldsymbol{x}_{W_{B}}>0.$
(3)

where $\boldsymbol{v}_{B},\boldsymbol{w}_{B}$ are a non-zero vectors in
$V_{B},W_{B}$. In other words, when $\varepsilon$ is sufficiently small, the
angle between $\boldsymbol{x}_{1}$ and $V_{B}$ is also sufficiently small.
Also, $\boldsymbol{x}_{1}$ and $\boldsymbol{x}$ lie in same cone out of the
four cut by $V_{B}$ and $W_{B}$. This gives us an element
$(Y_{1},\boldsymbol{y}_{1})\coloneqq(Y,\boldsymbol{y})\cdot w$ such that
$(A,\boldsymbol{a})(Y_{1},\boldsymbol{y}_{1})(B,\boldsymbol{b})=(I,\boldsymbol{x}_{1})$
with $\boldsymbol{x}_{1}$ satisfying (3), see Figure 6.

Next, apply Lemma 12 to $\varepsilon$, to the elements $(A,\boldsymbol{a})$
and
$(B^{\prime},\boldsymbol{b}^{\prime})\coloneqq(Y_{1},\boldsymbol{y}_{1})(B,\boldsymbol{b})$
of $\mathsf{SA}(2,\mathbb{Z})$, and to the subspaces $V_{A},W_{A}$ in
$\operatorname{Lat}(A)$. Same as above, we obtain an element
$(Y_{2},\boldsymbol{y}_{2})$ such that
$(A,\boldsymbol{a})(Y_{2},\boldsymbol{y}_{2})(B,\boldsymbol{b})=(I,\boldsymbol{x}_{2})$
with $\boldsymbol{x}_{2}$ satisfying

$1-\frac{|\boldsymbol{v}_{A}^{\top}\boldsymbol{x}_{2}|}{|\boldsymbol{v}_{A}||\boldsymbol{x}_{2}|}<\varepsilon,\;\left(\boldsymbol{x}_{1}\right)_{V_{A}}^{\top}\boldsymbol{x}_{V_{A}}>0,\;\left(\boldsymbol{x}_{1}\right)_{W_{A}}^{\top}\boldsymbol{x}_{W_{A}}>0.$
(4)

In other words, when $\varepsilon$ is sufficiently small, the angle between
$\boldsymbol{x}_{2}$ and $V_{A}$ is also sufficiently small. Hence, one can
take $\varepsilon$ such that $\boldsymbol{x}_{2}$ and $-\boldsymbol{x}_{1}$
lie in the same cone out of the four cut by $V_{B}$ and $W_{B}$. Furthermore,
$\boldsymbol{x}_{2}$ and $\boldsymbol{x}_{1}$ lie in same cone out of the four
cut by $V_{A}$ and $W_{A}$.

We follow this pattern and apply Lemma 12 again on
$(A^{\prime},\boldsymbol{a}^{\prime})\coloneqq(A,\boldsymbol{a})(Y_{2},\boldsymbol{y}_{2})$
and $(B,\boldsymbol{b})$, and to the subspaces $V_{B},W_{B}$. This yields an
element $(Y_{3},\boldsymbol{y}_{3})$ such that
$(A,\boldsymbol{a})(Y_{3},\boldsymbol{y}_{3})(B,\boldsymbol{b})=(I,\boldsymbol{x}_{3})$
with $\boldsymbol{x}_{3}$ very close to $V_{B}$, but lie in the same cone cut
by $V_{B}$ and $W_{B}$ as $\boldsymbol{x}_{2}$.

Finally we apply Lemma 12 again on $(A,\boldsymbol{a})$ and
$(B^{\prime},\boldsymbol{b}^{\prime})\coloneqq(Y_{3},\boldsymbol{y}_{3})(B,\boldsymbol{b})$,
and to the subspaces $V_{A},W_{A}$. This yields $(Y_{4},\boldsymbol{y}_{4})$
such that
$(A,\boldsymbol{a})(Y_{4},\boldsymbol{y}_{4})(B,\boldsymbol{b})=(I,\boldsymbol{x}_{4})$
with $\boldsymbol{x}_{4}$ very close to $V_{A}$, but lie in the same cone cut
by $V_{A}$ and $W_{A}$ as $\boldsymbol{x}_{3}$.

When $\varepsilon$ is small enough, the angles of the vectors
$\boldsymbol{x}_{1},\boldsymbol{x}_{2},\boldsymbol{x}_{3},\boldsymbol{x}_{4}$
are sufficiently close to $V_{B},V_{A},V_{B},V_{A}$, with opposing directions.
Hence, they generate $\mathbb{Q}^{2}$ as a $\mathbb{Q}_{\geq 0}$-cone. In
other words, there exist _positive_ integers $n_{1},n_{2},n_{3},n_{4}$ such
that
$n_{1}\boldsymbol{x}_{1}+n_{2}\boldsymbol{x}_{2}+n_{3}\boldsymbol{x}_{3}+n_{4}\boldsymbol{x}_{4}=\boldsymbol{0}$.
Therefore,

$(I,\boldsymbol{x}_{1})^{n_{1}}(I,\boldsymbol{x}_{2})^{n_{2}}(I,\boldsymbol{x}_{3})^{n_{3}}(I,\boldsymbol{x}_{4})^{n_{4}}=(I,\boldsymbol{0}).$

Since the element $(A,\boldsymbol{a})$ can be represented as a full-image word
over $\mathcal{G}$, the elements $(I,\boldsymbol{x}_{1})$ and hence
$(I,\boldsymbol{0})$ can be represented by full-image words as well.
Therefore, $\langle\mathcal{G}\rangle$ is a group.

Figure 5: Illustration for case 1(a).

Figure 6: Illustration for case 1(b).

Figure 7: Illustration for case 2.

Figure 8: Illustration for case 3.

  2. (ii)

Next consider the case $(\operatorname{Lat}(A)$, $\operatorname{Lat}(B)$,
$\operatorname{Lat}(A)$, $\operatorname{Lat}(B))$. Denote by
$V_{A},V_{B},W_{A},W_{B}$ be these subspaces in this order. Without loss of
generality suppose $\boldsymbol{x}\notin V_{B}\cup W_{B}$. The strategy is
exactly the same as the previous case, see Figure 6. However, in the present
case, we need to apply Lemma 12 for a total of six times, where $V$ will be
the subspaces $V_{B},W_{A},W_{B},V_{A},V_{B},W_{A}$ respectively.

In this way, we obtain $(I,\boldsymbol{x}_{1})$, $(I,\boldsymbol{x}_{2})$,
$(I,\boldsymbol{x}_{3})$, $(I,\boldsymbol{x}_{4})$, $(I,\boldsymbol{x}_{5})$,
$(I,\boldsymbol{x}_{6})$ with $\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{6}$
generating $\mathbb{Q}^{2}$ as a $\mathbb{Q}_{\geq 0}$-cone. Hence, there
exist positive integers $n_{1},\ldots,n_{6}$ such that

$(I,\boldsymbol{x}_{1})^{n_{1}}\cdots(I,\boldsymbol{x}_{6})^{n_{6}}=(I,\boldsymbol{0}).$

Similarly, since the element $(A,\boldsymbol{a})$ can be represented as a
full-image word over $\mathcal{G}$, $\langle\mathcal{G}\rangle$ is a group.

This concludes case 1.

Case 2. One of $A$ and $B$ is a shear. The approach is similar to case 1(a),
but we have to apply Lemma 12 and Lemma 13 alternately. See Figure 8 for an
illustration.

Without loss of generality, let $A$ be the shear and $B$ be the positive
scale. Starting from any one-dimension subspace $S$, rotate $S$ counter-
clockwise and consider its sequence of encounters with $\operatorname{Lat}(A)$
and $\operatorname{Lat}(B)$ before finishing a full cycle. The sequence of
encounters must a cyclic permutation of
$(\operatorname{Lat}(A),\operatorname{Lat}(B),\operatorname{Lat}(B))$. Denote
by $V_{A},V_{B},W_{B}$ be these subspaces in this order. Without loss of
generality suppose $\boldsymbol{x}\notin V_{B}\cup W_{B}$, the case where
$\boldsymbol{x}\notin V_{A}$ is analogous.

For a small enough $\varepsilon$, apply Lemma 12 to $\boldsymbol{x}$ to obtain
$\boldsymbol{x}_{1}$ that is sufficiently close to $V_{B}$; then apply Lemma
13 to $\boldsymbol{x}_{1}$ to obtain $\boldsymbol{x}_{2}$ that is sufficiently
close to $V_{A}$; then apply Lemma 12 to $\boldsymbol{x}_{2}$ to obtain
$\boldsymbol{x}_{3}$ that is sufficiently close to $W_{B}$; finally, apply
Lemma 13 to $\boldsymbol{x}_{3}$ to obtain $\boldsymbol{x}_{4}$ that is
sufficiently close to $V_{A}$. In this way, we obtain
$(I,\boldsymbol{x}_{1}),(I,\boldsymbol{x}_{2}),(I,\boldsymbol{x}_{3}),(I,\boldsymbol{x}_{4})$
with $\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{4}$ generating
$\mathbb{Q}^{2}$ as a $\mathbb{Q}_{\geq 0}$-cone. Hence, there exist positive
integers $n_{1},\ldots,n_{4}$ such that

$(I,\boldsymbol{x}_{1})^{n_{1}}\cdots(I,\boldsymbol{x}_{4})^{n_{4}}=(I,\boldsymbol{0}).$

Since the element $(A,\boldsymbol{a})$ can be represented as a full-image word
over $\mathcal{G}$, $\langle\mathcal{G}\rangle$ is a group.

Case 3. Both $A$ and $B$ are shears. The approach is similar to case 1(a), but
we have to apply Lemma 13 only. See Figure 8 for an illustration.

Denote by $V_{A},V_{B}$ respectively the elements of $\operatorname{Lat}(A)$
and $\operatorname{Lat}(B)$. Without loss of generality suppose
$\boldsymbol{x}\notin V_{B}$, the case where $\boldsymbol{x}\notin V_{A}$ is
analogous. For a small enough $\varepsilon$, apply Lemma 13 to
$\boldsymbol{x}$ to obtain $\boldsymbol{x}_{1}$ that is sufficiently close to
$V_{B}$; then apply Lemma 13 again to $\boldsymbol{x}_{1}$ to obtain
$\boldsymbol{x}_{2}$ that is sufficiently close to $V_{A}$; then apply Lemma
13 to $\boldsymbol{x}_{2}$ to obtain $\boldsymbol{x}_{3}$ that is sufficiently
close to $V_{B}$; finally, apply Lemma 13 to $\boldsymbol{x}_{3}$ to obtain
$\boldsymbol{x}_{4}$ that is sufficiently close to $V_{A}$. In this way, we
obtain
$(I,\boldsymbol{x}_{1}),(I,\boldsymbol{x}_{2}),(I,\boldsymbol{x}_{3}),(I,\boldsymbol{x}_{4})$
with $\boldsymbol{x}_{1},\ldots,\boldsymbol{x}_{4}$ generating
$\mathbb{Q}^{2}$ as a $\mathbb{Q}_{\geq 0}$-cone. Hence, there exist positive
integers $n_{1},\ldots,n_{4}$ such that

$(I,\boldsymbol{x}_{1})^{n_{1}}\cdots(I,\boldsymbol{x}_{4})^{n_{4}}=(I,\boldsymbol{0}).$

Since the element $(A,\boldsymbol{a})$ can be represented as a full-image word
over $\mathcal{G}$, $\langle\mathcal{G}\rangle$ is a group. ∎

##  V Virtual solvability

In this section we prove Proposition 10. As in the statement of the
proposition, we fix a set
$\mathcal{G}=\\{(A_{1},\boldsymbol{a}_{1}),\ldots,(A_{K},\boldsymbol{a}_{K})\\}$
of elements in $\mathsf{SA}(2,\mathbb{Z})$, such that $G\coloneqq\langle
A_{1},\ldots,A_{K}\rangle$ is a virtually solvable group.

######  Lemma 14.

Let $G$ be a virtually solvable subgroup of $\mathsf{SL}(2,\mathbb{Z})$. Then
$G$ is either finite, or it contains a finite index subgroup $H$ isomorphic to
$\mathbb{Z}$.

###### Proof.

By Theorem 5, let $F\leq\mathsf{SL}(2,\mathbb{Z})$ be a free subgroup over two
generators, such that the index $[\mathsf{SL}(2,\mathbb{Z}):F]$ is finite.
Then $[G:F\cap G]\leq[\mathsf{SL}(2,\mathbb{Z}):F]$, so the group $H\coloneqq
F\cap G$ is of finite index in $G$. But $H$ is a subgroup of the free group
$F$, so it must be free by Theorem 4. Hence, $H$ is a subgroup of the
virtually solvable group $G$, so $H$ is virtually solvable. Since
$H\leq\mathsf{SL}(2,\mathbb{Z})$ is virtually solvable and free, it must be
abelian by Theorem 8. Therefore $H\cong\mathbb{Z}$ or $H=\\{I\\}$, in the
second case, $G$ is finite. ∎

######  Lemma 15.

Let $G\leq\mathsf{SL}(2,\mathbb{Z})$ be a group which contains a finite index
subgroup $H$ isomorphic to $\mathbb{Z}$. Then either $G$ contains a torsion
element, or it is also isomorphic to $\mathbb{Z}$.

###### Proof.

Suppose $G$ torsion-free. Since $G$ is virtually free and torsion-free, by
[31, Theorem B], it is free. Hence either $G\cong\mathbb{Z}$, or $G$ is a non-
abelian free group. But a non-abelian free group is not virtually solvable
(Theorem 8), so it cannot contain a finite index subgroup $H$ isomorphic to
$\mathbb{Z}$. Therefore, we must have $G\cong\mathbb{Z}$. ∎

By Lemma 14 and 15, we can already prove the first part of Proposition 10. In
particular, by Lemma 14, $G$ is finite or contains a finite index subgroup
isomorphic to $\mathbb{Z}$. If $G$ is finite, then either it is trivial or it
contains a torsion element. If $G$ contains a finite index subgroup isomorphic
to $\mathbb{Z}$, then by Lemma 15, either it contains a torsion element, or it
is isomorphic to $\mathbb{Z}$. Therefore, we have proved that exactly one of
the following holds.

  1. (1)

$G$ is the trivial group.

  2. (2)

$G$ contains a torsion element.

  3. (3)

$G$ is isomorphic to $\mathbb{Z}$.

In case (3), the generator of $G$ is either a twisted inversion, a shear, an
inverting scale, or a positive scale. This corresponds to the cases (iii)-(vi)
of Proposition 10. We have thus proved the first part of Proposition 10. The
following lemma shows that one can decide which of the six cases in
Proposition 10 is true.

######  Lemma 16.

Let $A_{1},\ldots,A_{K}$ be matrices in $\mathsf{SL}(2,\mathbb{Z})$. The
following can be done in PTIME:

  1. (i)

decide whether the _group_ $G\coloneqq\langle A_{1},\ldots,A_{K}\rangle_{grp}$
is trivial.

  2. (ii)

decide whether $G$ is isomorphic to $\mathbb{Z}$.

  3. (iii)

compute a generator $A$ of $G$ in case $G\cong\mathbb{Z}$.

###### Proof.

(i). $G$ is trivial if and only if $A_{i}=I$ for all $i$.

(ii). First we check whether $G$ is abelian, this is done simply by checking
whether $A_{i}A_{j}=A_{j}A_{i}$ for all $1\leq i,j\leq K$. If $G$ is not
abelian, then it is not isomorphic to $\mathbb{Z}$.

Suppose $G$ is abelian. Then the group homomorphism

$\displaystyle\varphi\colon\mathbb{Z}^{K}$ $\displaystyle\longrightarrow G$
$\displaystyle(n_{1},\ldots,n_{K})$ $\displaystyle\longmapsto
A_{1}^{n_{1}}\cdots A_{K}^{n_{K}}$

is surjective. By a classic result of Babai et al. [32], the kernel

$\Lambda\coloneqq\ker(\varphi)=\\{(n_{1},\ldots,n_{K})\mid A_{1}^{n_{1}}\cdots
A_{K}^{n_{K}}=I\\}$

is a lattice of $\mathbb{Z}^{K}$, and a $\mathbb{Z}$-basis of $\Lambda$ is
computable in PTIME.

Let $\boldsymbol{\ell}_{1},\ldots,\boldsymbol{\ell}_{m}$ be a
$\mathbb{Z}$-basis of $\Lambda$. Define

$\overline{\Lambda}\coloneqq\left\\{\boldsymbol{n}\in\mathbb{Z}^{K}\;\middle|\;\boldsymbol{n}=q_{1}\boldsymbol{\ell}_{1}+\cdots+q_{m}\boldsymbol{\ell}_{m},\;\right.\\\
\left.\text{ where }q_{1},\ldots,q_{m}\in\mathbb{Q}\right\\}$

the lattice of integer points in the $\mathbb{Q}$-linear space spanned by
$\Lambda$. A basis of $\overline{\Lambda}$ is effectively computable in PTIME
using the _Hermite Normal Form_ [33]. It is then decidable in PTIME whether
$\overline{\Lambda}=\Lambda$, again using the Hermite Normal Form.

We claim that $G$ is torsion-free if and only if $\overline{\Lambda}=\Lambda$.
Indeed, let $T=A_{1}^{n_{1}}\cdots A_{K}^{n_{K}}$ be a torsion element of $G$,
then $T^{m}=I$ for some $m>1$. Therefore $A_{1}^{mn_{1}}\cdots
A_{K}^{mn_{K}}=I$, so $(mn_{1},\ldots,mn_{K})\in\Lambda$. This shows
$(n_{1},\ldots,n_{K})\in\overline{\Lambda}$. But $T\neq I$, so
$(n_{1},\ldots,n_{K})\notin\Lambda$. Hence, $T=A_{1}^{n_{1}}\cdots
A_{K}^{n_{K}}$ is a torsion element if and only if
$(n_{1},\ldots,n_{K})\in\overline{\Lambda}\setminus\Lambda$.

This proves the claim. Therefore it is decidable in PTIME whether $G$ contains
a torsion element. By Lemma 15, it is decidable in PTIME whether
$G\cong\mathbb{Z}$.

(iii). If $G$ is isomorphic to $\mathbb{Z}$, then the quotient group
$\mathbb{Z}^{K}/\Lambda\cong G\cong\mathbb{Z}$. Using Hermite Normal Form, one
can in PTIME compute an element
$\boldsymbol{x}=(x_{1},\ldots,x_{K})\in\mathbb{Z}^{K}$ such that
$\boldsymbol{x}\mathbb{Z}+\Lambda=\mathbb{Z}^{K}$. Then
$\boldsymbol{x}+\Lambda$ generates $\mathbb{Z}^{K}/\Lambda$. Therefore
$A\coloneqq\varphi(\boldsymbol{x})=A_{1}^{x_{1}}\cdots A_{K}^{n_{K}}$
generates $G$. ∎

Recall $G\coloneqq\langle A_{1},\ldots,A_{K}\rangle$. We now proceed to prove
the PTIME decidability claim of Proposition 10 for all six cases.

###  $G$ is trivial

In this case,
$\mathcal{G}=\\{(I,\boldsymbol{a}_{1}),\cdots,(I,\boldsymbol{a}_{K})\\}$.

######  Proposition 17.

Let $\mathcal{G}=\\{(I,\boldsymbol{a}_{1}),\cdots,(I,\boldsymbol{a}_{K})\\}$.
Then $\langle\mathcal{G}\rangle$ is a group if and only if the equation

$n_{1}\boldsymbol{a}_{1}+n_{2}\boldsymbol{a}_{2}+\cdots
n_{K}\boldsymbol{a}_{K}=\boldsymbol{0}$ (5)

has a solution $(n_{1},\ldots,n_{K})\in\mathbb{Z}_{>0}^{K}$. In particular,
this is decidable in PTIME.

###### Proof.

Note that the matrices in $\mathcal{G}$ commute. Therefore by the equivalence
of (i) and (ii) in Lemma 1, $\langle\mathcal{G}\rangle$ is a group if and only
if Equation (5) has a solution $(n_{1},\ldots,n_{K})\in\mathbb{Z}_{>0}^{K}$.

By the homogeneity of Equation (5), it has a solution in $\mathbb{Z}_{>0}^{K}$
if and only if it has a solution in $\mathbb{Q}_{>0}^{K}$. This is decidable
in PTIME by linear programming. ∎

###  $G$ contains a torsion element

We show that $\langle\mathcal{G}\rangle$ is always a group in case $G$
contains a torsion element.

######  Proposition 18.

Let
$\mathcal{G}\coloneqq\\{(A_{1},\boldsymbol{a}_{1}),\ldots,(A_{K},\boldsymbol{a}_{K})\\}$
be a set of elements of $\mathsf{SA}(2,\mathbb{Z})$. If the semigroup $\langle
A_{1},\ldots,A_{K}\rangle$ is a group containing a torsion element, then
$\langle\mathcal{G}\rangle$ is a group.

###### Proof.

Suppose $\langle A_{1},\ldots,A_{K}\rangle$ contains a torsion element $T$.
Let $m>0$ be such that $T^{m}=I$. Let $\boldsymbol{t}\in\mathbb{Z}^{2}$ be a
vector such that $(T,\boldsymbol{t})$ is an element in
$\langle\mathcal{G}\rangle$ represented by a full-image word (such a word
exists by Lemma 1). Then

$(T,\boldsymbol{t})^{m}=(T^{m},(I+T+\cdots+T^{m-1})\boldsymbol{t})\\\
=(I,(I-T)^{-1}(I-T^{m})\boldsymbol{t})=(I,\boldsymbol{0}).$

Here, $I-T$ is invertible because $T\in\mathsf{SL}(2,\mathbb{Z})$ is torsion,
so the eigenvalues of $T$ are all different from one (see the classification
of element of $\mathsf{SL}(2,\mathbb{Z})$ in Section II). We conclude that
$(I,\boldsymbol{0})$ can be represented by a full-image word over the alphabet
$\mathcal{G}$. Hence, $\langle\mathcal{G}\rangle$ is a group by Lemma 1. ∎

In the next four cases, $G$ is isomorphic to $\mathbb{Z}$. Let $A$ be a
generator of $G$. The _Jordan Normal Form_ of $A$ can be computed in PTIME
[34]. Consequently, one can decide whether $A$ is a twisted inversion, a shear
or a scale.

###  $G$ is generated by a twisted inversion $A$

We show that if $A$ is a twisted inversion, then $\langle\mathcal{G}\rangle$
is always a group.

######  Proposition 19.

If the generator $A$ of the group $\langle A_{1},\ldots,A_{K}\rangle$ is a
twisted inversion, then $\langle\mathcal{G}\rangle$ is a group.

###### Proof.

Since $\langle A_{1},\ldots,A_{K}\rangle$ is isomorphic to $\mathbb{Z}$, we
have $A,A^{-1}\in\langle A_{1},\ldots,A_{K}\rangle$. Since $\langle
A_{1},\ldots,A_{K}\rangle$ is a group, let $(A,\boldsymbol{a})$ and
$(A^{-1},\boldsymbol{b})$ be elements of $\langle\mathcal{G}\rangle$
represented by full-image words over $\mathcal{G}$.

We claim that

$(A,\boldsymbol{a})^{2}\cdot(A^{-1},\boldsymbol{b})^{3}\cdot(A,\boldsymbol{a})^{2}\cdot(A^{-1},\boldsymbol{b})=(I,\boldsymbol{0}).$

By direct computation,
$(A,\boldsymbol{a})^{2}\cdot(A^{-1},\boldsymbol{b})^{3}\cdot(A,\boldsymbol{a})^{2}\cdot(A^{-1},\boldsymbol{b})=(I,A^{-1}(A+I)^{2}\boldsymbol{a}+(A+I)^{2}\boldsymbol{b}).$
But since $A$ is a twisted inversion, we have $(A+I)^{2}=0$. Therefore,
$(A,\boldsymbol{a})^{2}\cdot(A^{-1},\boldsymbol{b})^{3}\cdot(A,\boldsymbol{a})^{2}\cdot(A^{-1},\boldsymbol{b})=(I,\boldsymbol{0})$.
We conclude that $(I,\boldsymbol{0})$ can be represented as a full-image word
over $\mathcal{G}$. Hence, $\langle\mathcal{G}\rangle$ is a group. ∎

###  $G$ is generated by a shear $A$

If $A$ is a shear, the main idea in this case is that the semigroup generated
by $\mathcal{G}$ can be embedded as a sub-semigroup of the _Heisenberg group_
:

$\operatorname{H}_{3}(\mathbb{Q})\coloneqq\left\\{\begin{pmatrix}1&a&b\\\
0&1&c\\\ 0&0&1\\\ \end{pmatrix}\;\middle|\;a,b,c\in\mathbb{Q}\right\\}.$

Since $A$ is a shear, it is triangularizable over $\mathbb{Q}$. Since
$A_{1},\ldots,A_{K}$ all commute, they all have the same eigenvalue one, and
are simultaneously triangularizable. Let $P$ be a matrix (with entries in
$\mathbb{Q}$) such that $P^{-1}A_{i}P$ are all of the form
$\begin{pmatrix}1&\lambda_{i}\\\ 0&1\\\ \end{pmatrix}$ with
$\lambda_{i}\in\mathbb{Q}$. Hence, we have the following conjugation:

$\begin{pmatrix}P^{-1}&0\\\ 0&1\\\
\end{pmatrix}\begin{pmatrix}A_{i}&\boldsymbol{a}_{i}\\\ 0&1\\\
\end{pmatrix}\begin{pmatrix}P&0\\\ 0&1\\\ \end{pmatrix}\\\
=\begin{pmatrix}P^{-1}A_{i}P&P^{-1}\boldsymbol{a}_{i}\\\ 0&1\\\
\end{pmatrix}\in\operatorname{H}_{3}(\mathbb{Q}).$

This shows that the map

$\varphi:\mathcal{G}\rightarrow\operatorname{H}_{3}(\mathbb{Q}),\quad(A_{i},\boldsymbol{a}_{i})\mapsto\begin{pmatrix}P^{-1}A_{i}P&P^{-1}\boldsymbol{a}_{i}\\\
0&1\\\ \end{pmatrix}$ (6)

extends to an injective semigroup homomorphism from
$\langle\mathcal{G}\rangle$ to $\operatorname{H}_{3}(\mathbb{Q})$. Therefore,
$\langle\mathcal{G}\rangle$ is a group if and only if
$\langle\varphi(\mathcal{G})\rangle$ is a group. This is decidable by the
following theorem.

######  Theorem 20 ([8]).

The Group Problem in $\operatorname{H}_{3}(\mathbb{Q})$ is decidable in PTIME.

By this result, we immediately obtain:

######  Corollary 21.

If the generator $A$ of the group $\langle A_{1},\ldots,A_{K}\rangle$ is a
shear, then the Group Problem for $\langle\mathcal{G}\rangle$ is equivalent to
the Group Problem for $\langle\varphi(\mathcal{G})\rangle$, which is decidable
in PTIME.

###  $G$ is generated by an inverting scale $A$

We show that if $A$ is an inverting scale, then $\langle\mathcal{G}\rangle$ is
a group.

######  Proposition 22.

If the generator $A$ of the group $\langle A_{1},\ldots,A_{K}\rangle$ is an
inverting scale, then $\langle\mathcal{G}\rangle$ is a group.

###  $G$ is generated by a positive scale $A$

This is the most technical case in our paper. We show that if $A$ is a
positive scale, then we can decide whether $\langle\mathcal{G}\rangle$ is a
group in PTIME. Let
$P=(\boldsymbol{x}_{V},\boldsymbol{x}_{W})\in\mathsf{SL}(2,\mathbb{R})$ be a
change of basis matrix such that $P^{-1}AP=A^{\prime}$, where $A^{\prime}$ is
diagonal and can be written as

$A^{\prime}=\begin{pmatrix}\lambda&0\\\ 0&\lambda^{-1}\\\ \end{pmatrix},$

where $\lambda>1$. For $i=1,\ldots,K$, let $A^{\prime}_{i}\coloneqq
P^{-1}A_{i}P$ and $\boldsymbol{a}^{\prime}_{i}\coloneqq
P^{-1}\boldsymbol{a}_{i}$, with

$A^{\prime}_{i}=\begin{pmatrix}\lambda^{z_{i}}&0\\\ 0&\lambda^{-z_{i}}\\\
\end{pmatrix},\quad\boldsymbol{a}^{\prime}_{i}=(a_{i},b_{i})^{\top}.$

These are the forms of $A_{i}$ and $\boldsymbol{a}_{i}$ under the new basis
$(\boldsymbol{x}_{V},\boldsymbol{x}_{W})$. In particular we have
$A\boldsymbol{x}_{V}=\lambda\boldsymbol{x}_{V},A\boldsymbol{x}_{W}=\lambda^{-1}\boldsymbol{x}_{W}$.

Define the sets

$\displaystyle J_{+}\coloneqq\\{i\mid z_{i}>0\\},\;J_{-}\coloneqq\\{i\mid
z_{i}<0\\},\;J_{0}\coloneqq\\{i\mid z_{i}=0\\}.$

Then $J_{+}\cup J_{-}\cup J_{0}=\\{1,\ldots,K\\}$. For all $i$, denote

$\displaystyle n_{i}\coloneqq\begin{cases}|z_{i}|\quad&z_{i}\neq 0\\\
1\quad&z_{i}=0.\end{cases}$

Since $\langle A_{1},\ldots,A_{K}\rangle$ is isomorphic to $\mathbb{Z}$, we
have $J_{+}\neq\emptyset,J_{-}\neq\emptyset$.

Divide the set $\mathbb{R}^{2}$ into nine parts:

$\displaystyle\mathcal{R}_{++}\coloneqq\\{(x,y)\mid x>0,y>0\\},$
$\displaystyle\mathcal{R}_{+0}\coloneqq\\{(x,y)\mid x>0,y=0\\},$
$\displaystyle\mathcal{R}_{+-}\coloneqq\\{(x,y)\mid x>0,y<0\\},$
$\displaystyle\mathcal{R}_{0+}\coloneqq\\{(x,y)\mid x=0,y>0\\},$
$\displaystyle\mathcal{R}_{00}\coloneqq\\{(x,y)\mid x=0,y=0\\},$
$\displaystyle\mathcal{R}_{0-}\coloneqq\\{(x,y)\mid x=0,y<0\\},$
$\displaystyle\mathcal{R}_{-+}\coloneqq\\{(x,y)\mid x<0,y>0\\},$
$\displaystyle\mathcal{R}_{-0}\coloneqq\\{(x,y)\mid x<0,y=0\\},$
$\displaystyle\mathcal{R}_{--}\coloneqq\\{(x,y)\mid x<0,y<0\\}.$

Each part is called a _cell_. See Figure 10.

Figure 9: Cells.

Figure 10: Illustration for Lemma 23.

For an element $\boldsymbol{x}\in\mathbb{R}^{2}$, denote by
$\operatorname{Cell}(\boldsymbol{x})$ the cell which it belongs to. In other
words, writing $\boldsymbol{x}=(x_{1},x_{2})^{\top}$, then

$\operatorname{Cell}(\boldsymbol{x})=\\{(r_{1}x_{1},r_{2}x_{2})^{\top}\mid
r_{1},r_{2}\in\mathbb{R}_{>0}\\}.$ (7)

In particular, $\boldsymbol{x}$ and ${A^{\prime}}^{z}\boldsymbol{x}$ are in
the same cell for all integers $z$.

For each tuple $(i,j)\in J_{+}\times J_{-}$, define the vector

$\boldsymbol{d}_{ij}\coloneqq(d_{ija},d_{ijb})^{\top}\in\mathbb{R}^{2}$

where

$d_{ija}\coloneqq-\frac{a_{i}}{1-\lambda^{n_{i}}}+\frac{a_{j}}{1-\lambda^{-n_{j}}},\;\;d_{ijb}\coloneqq\frac{b_{i}}{1-\lambda^{n_{i}}}-\frac{b_{j}}{1-\lambda^{-n_{j}}}.$

For each element $k\in J_{0}$, define the vector

$\boldsymbol{e}_{k}\coloneqq\left(a_{k},b_{k}\right)^{\top}\in\mathbb{R}^{2}.$

Denote by $\mathcal{G}^{\prime}$ the new alphabet
$\\{(A^{\prime}_{1},\boldsymbol{a}^{\prime}_{1}),\ldots,(A^{\prime}_{K},\boldsymbol{a}^{\prime}_{K})\\}$.

######  Lemma 23.

Let $(i,j)$ be a pair in $J_{+}\times J_{-}$ and
$(x,y)^{\top}\in\mathbb{R}^{2}$ be a vector in
$\operatorname{Cell}(\boldsymbol{d}_{ij})$. If $\lambda>1$, then there exist
elements $(I,\boldsymbol{v})$ and $(I,\boldsymbol{w})$ in
$\langle\mathcal{G}^{\prime}\rangle$, where the vector $(x,y)^{\top}$ can be
written as $r_{1}\boldsymbol{v}+r_{2}\boldsymbol{w}$ for some
$r_{1},r_{2}\in\mathbb{R}_{>0}$. Furthermore, $(I,\boldsymbol{v})$ and
$(I,\boldsymbol{w})$ are represented by words over the alphabet
$\mathcal{G}^{\prime}$, such that the letters
$(A^{\prime}_{i},\boldsymbol{a}^{\prime}_{i})$ and
$(A^{\prime}_{j},\boldsymbol{a}^{\prime}_{j})$ both occur. See Figure 10 for
an illustration.

###### Proof.

For any $p\in\mathbb{Z}_{>0}$, denote

$\displaystyle(I,\boldsymbol{v}_{p})$
$\displaystyle\coloneqq({A^{\prime}_{i}},\boldsymbol{a}^{\prime}_{i})^{pn_{j}}({A^{\prime}_{j}},\boldsymbol{a}^{\prime}_{j})^{pn_{i}},$
$\displaystyle(I,\boldsymbol{w}_{p})$
$\displaystyle\coloneqq({A^{\prime}_{j}},\boldsymbol{a}^{\prime}_{j})^{pn_{i}}({A^{\prime}_{i}},\boldsymbol{a}^{\prime}_{i})^{pn_{j}}.$

By direct computation, we have

$\displaystyle\boldsymbol{v}_{p}$
$\displaystyle=(1-\lambda^{-pn_{i}n_{j}})\cdot\left(\lambda^{pn_{i}n_{j}}d_{ija},d_{ijb}\right)^{\top},$
$\displaystyle\boldsymbol{w}_{p}$
$\displaystyle=(1-\lambda^{-pn_{i}n_{j}})\cdot\left(d_{ija},\lambda^{pn_{i}n_{j}}d_{ijb}\right)^{\top}.$

Since $\lambda>1$, we have $1-\lambda^{-pn_{i}n_{j}}>0$.

If $\operatorname{Cell}(\boldsymbol{d}_{ij})$ is of dimension one or zero,
then either $d_{ija}=0$ or $d_{ijb}=0$. In both cases,
$(x,y)^{\top},\boldsymbol{v}_{p},\boldsymbol{w}_{p}$ are linearly dependant
and have the same direction, so $(x,y)^{\top}$ is in the $\mathbb{R}_{\geq
0}$-cone generated by $\boldsymbol{v}_{p}$ and $\boldsymbol{v}_{q}$.

If $\operatorname{Cell}(\boldsymbol{d}_{ij})$ is of dimension two, then
$d_{ija}\neq 0$ and $d_{ijb}\neq 0$. Let $p$ be large enough so that
$\frac{\lambda^{pn_{i}n_{j}}d_{ija}}{d_{ijb}}>\frac{x}{y}>\frac{d_{ija}}{\lambda^{pn_{i}n_{j}}d_{ijb}}$.
Then $(x,y)^{\top}$ can be written as
$r_{1}\boldsymbol{v}_{p}+r_{2}\boldsymbol{w}_{p}$ for some
$r_{1},r_{2}\in\mathbb{R}_{>0}$. ∎

A similar lemma can be shown for $\operatorname{Cell}(\boldsymbol{e}_{k})$.

######  Lemma 24.

Let $(i,j)$ be a pair in $J_{+}\times J_{-}$, and $k$ be an element in
$J_{0}$, and $(x,y)^{\top}\in\mathbb{R}^{2}$ be a vector in
$\operatorname{Cell}(\boldsymbol{e}_{k})$. If $\lambda>1$, then there exist
elements $(I,\boldsymbol{v})$ and $(I,\boldsymbol{w})$ in
$\langle\mathcal{G}^{\prime}\rangle$, such that the vector $(x,y)^{\top}$ can
be written as $r_{1}\boldsymbol{v}+r_{2}\boldsymbol{w}$ for some
$r_{1},r_{2}\in\mathbb{R}_{>0}$. Furthermore, $(I,\boldsymbol{v})$ and
$(I,\boldsymbol{w})$ are represented as words over the alphabet
$\mathcal{G}^{\prime}$, such that the letter
$(A^{\prime}_{k},\boldsymbol{a}^{\prime}_{k})$ occurs.

Define the _radical_ $\widehat{(A^{\prime}_{i},\boldsymbol{a}^{\prime}_{i})}$
of $(A^{\prime}_{i},\boldsymbol{a}^{\prime}_{i})$ as

$\widehat{(A^{\prime}_{i},\boldsymbol{a}^{\prime}_{i})}\coloneqq\left(\begin{pmatrix}\lambda&0\\\
0&\lambda^{-1}\\\
\end{pmatrix},\begin{pmatrix}a_{i}\cdot\frac{1-\lambda}{1-\lambda^{n_{i}}}\\\
b_{i}\cdot\frac{1-\lambda^{-1}}{1-\lambda^{-{n_{i}}}}\\\
\end{pmatrix}\right).$

if $z_{i}=n_{i}>0$, and

$\widehat{(A^{\prime}_{i},\boldsymbol{a}^{\prime}_{i})}\coloneqq\left(\begin{pmatrix}\lambda^{-1}&0\\\
0&\lambda\\\
\end{pmatrix},\begin{pmatrix}a_{i}\cdot\frac{1-\lambda^{-1}}{1-\lambda^{-n_{i}}}\\\
b_{i}\cdot\frac{1-\lambda}{1-\lambda^{n_{i}}}\\\ \end{pmatrix}\right).$

if $z_{i}=-n_{i}<0$, and

$\widehat{(A^{\prime}_{i},\boldsymbol{a}^{\prime}_{i})}\coloneqq(A^{\prime}_{i},\boldsymbol{a}^{\prime}_{i})$

if $z_{i}=0$. By direct computation, we have
$\widehat{(A^{\prime}_{i},\boldsymbol{a}^{\prime}_{i})}^{n_{i}}=(A^{\prime}_{i},\boldsymbol{a}^{\prime}_{i})$
in all cases.

Define the alphabet

$\widehat{\mathcal{G}}\coloneqq\\{\widehat{(A^{\prime}_{1},\boldsymbol{a}^{\prime}_{1})},\ldots,\widehat{(A^{\prime}_{K},\boldsymbol{a}^{\prime}_{K})}\\}.$

Define the following union of cells:

$\mathcal{S}\coloneqq\left(\bigcup_{i\in J_{+},j\in
J_{-}}\operatorname{Cell}(\boldsymbol{d}_{ij})\right)\bigcup\left(\bigcup_{k\in
J_{0}}\operatorname{Cell}(\boldsymbol{e}_{k})\right).$ (8)

######  Lemma 25.

Let $w\coloneqq(C_{1},\boldsymbol{c}_{1})\cdots(C_{M},\boldsymbol{c}_{M})$ be
a full-image word over the alphabet $\widehat{\mathcal{G}}$, such that
$(C_{1},\boldsymbol{c}_{1})\cdots(C_{M},\boldsymbol{c}_{M})=(I,\boldsymbol{x})$.
Then there exists a finite non-empty set of vectors
$\\{\boldsymbol{s}_{1},\ldots,\boldsymbol{s}_{m}\\}\subseteq\mathcal{S}$ such
that the following conditions are satisfied:

  1. (i)

$r_{1}\boldsymbol{s}_{1}+\cdots+r_{m}\boldsymbol{s}_{m}=\boldsymbol{x}$ for
some strictly positive reals $r_{1},\ldots,r_{m}$.

  2. (ii)

For each $i\in J_{+}$, there exist $j\in J_{-}$ and $\ell\leq m$, such that
$\boldsymbol{s}_{\ell}\in\operatorname{Cell}(\boldsymbol{d}_{ij})$.

  3. (iii)

For each $j\in J_{-}$, there exist $i\in J_{+}$ and $\ell\leq m$, such that
$\boldsymbol{s}_{\ell}\in\operatorname{Cell}(\boldsymbol{d}_{ij})$.

  4. (iv)

For each $k\in J_{0}$, there exist $\ell\leq m$ such that
$\boldsymbol{s}_{\ell}\in\operatorname{Cell}(\boldsymbol{e}_{k})$.

######  Proposition 26.

The semigroup $\langle\mathcal{G}\rangle$ is a group if and only if there
exists a finite set of vectors
$\\{\boldsymbol{s}_{1},\ldots,\boldsymbol{s}_{m}\\}\subseteq\mathcal{S}$ that
satisfies the four conditions (i)-(iv) in Lemma 25.

###### Proof.

First suppose there exist a finite set of vectors
$\\{\boldsymbol{s}_{1},\ldots,\boldsymbol{s}_{m}\\}\subseteq\mathcal{S}$
satisfying (i)-(iv), we want to find a full-image word $w$ over the alphabet
$\mathcal{G}$, representing $(I,\boldsymbol{0})$.

For an arbitrary $t$, if $\boldsymbol{s}_{t}$ is an element of
$\operatorname{Cell}(\boldsymbol{d}_{ij})$, then by Lemma 23, there exist
$(I,\boldsymbol{v}),(I,\boldsymbol{w})\in\langle\mathcal{G}^{\prime}\rangle$
such that $\boldsymbol{s}_{t}=r_{1}\boldsymbol{v}+r_{2}\boldsymbol{w}$ for
some $r_{1},r_{2}>0$. Also, the letters
$(A^{\prime}_{i},\boldsymbol{a}^{\prime}_{i})$ and
$(A^{\prime}_{j},\boldsymbol{a}^{\prime}_{j})$ appear in some words
representing $(I,\boldsymbol{v})$ and $(I,\boldsymbol{w})$. If
$\boldsymbol{s}_{t}$ is an element of
$\operatorname{Cell}(\boldsymbol{e}_{k})$, then by Lemma 24, there exist
$(I,\boldsymbol{v}),(I,\boldsymbol{w})\in\langle\mathcal{G}^{\prime}\rangle$
such that $\boldsymbol{s}_{t}=r_{1}\boldsymbol{v}+r_{2}\boldsymbol{w}$ for
some $r_{1},r_{2}>0$. Also, the letter
$(A^{\prime}_{k},\boldsymbol{a}^{\prime}_{k})$ appears in some words
representing $(I,\boldsymbol{v})$ and $(I,\boldsymbol{w})$.

Therefore, $\boldsymbol{s}_{t}$ can always be written as a strictly positive
linear combination of vectors $\boldsymbol{v}$ with
$(I,\boldsymbol{v})\in\langle\mathcal{G}^{\prime}\rangle$. Hence, by condition
(i), there exist strictly positive reals $r_{1},\ldots,r_{M}$ such that
$r_{1}\boldsymbol{v}^{\prime}_{1}+\cdots+r_{M}\boldsymbol{v}^{\prime}_{M}=\boldsymbol{0}$,
where $(I,\boldsymbol{v}^{\prime}_{t})\in\langle\mathcal{G}^{\prime}\rangle$
for all $t$. Furthermore, conditions (ii), (iii) and (iv) show that every
letter $(A^{\prime}_{i},\boldsymbol{a}^{\prime}_{i})$ in
$\mathcal{G}^{\prime}$ appears at least once in a word representing
$(I,\boldsymbol{v}^{\prime}_{t})$ for some $t$.

Changing back to the original basis, this shows that
$r_{1}\boldsymbol{v}_{1}+\cdots+r_{M}\boldsymbol{v}_{M}=\boldsymbol{0}$, where
$(I,\boldsymbol{v}_{i})\in\langle\mathcal{G}\rangle$ for all $i$. Since the
entries of $\boldsymbol{v}_{i}$ are all integers, there exist strictly
positive _integers_ $t_{1},\ldots,t_{M}$, such that
$t_{1}\boldsymbol{v}_{1}+\cdots+t_{M}\boldsymbol{v}_{M}=\boldsymbol{0}$. Hence

$(I,\boldsymbol{v}_{1})^{t_{1}}\cdots(I,\boldsymbol{v}_{M})^{t_{M}}=(I,\boldsymbol{0}).$

Every letter $(A_{i},\boldsymbol{a}_{i})$ in $\mathcal{G}$ appears at least
once in a word representing $(I,\boldsymbol{v}_{t})$ for some $t$. Therefore,
$(I,\boldsymbol{0})$ can be represented as a full-image word. This shows that
$\langle\mathcal{G}\rangle$ is a group by Lemma 1.

Next, suppose $\langle\mathcal{G}\rangle$ is a group, we show that there
exists a $\mathbb{R}_{>0}$-linear combination of elements in $\mathcal{S}$
equal to $\boldsymbol{0}$, that satisfies the conditions (ii), (iii) and (iv).

By Lemma 1, there exists a full-image word
$w\coloneqq(B^{\prime}_{1},\boldsymbol{b}^{\prime}_{1})\cdots(B^{\prime}_{m},\boldsymbol{b}^{\prime}_{m})$
over the alphabet $\mathcal{G}^{\prime}$, representing $(I,\boldsymbol{0})$.
Replacing each letter $(B^{\prime}_{i},\boldsymbol{b}^{\prime}_{i})$ in $w$
with $n_{i}$ consecutive letters
$\widehat{(B^{\prime}_{i},\boldsymbol{b}^{\prime}_{i})}$, we obtain a full-
image word

$\hat{w}=(C_{1},\boldsymbol{c}_{1})\cdots(C_{M},\boldsymbol{c}_{M})$

over the alphabet $\widehat{\mathcal{G}}$, representing $(I,\boldsymbol{0})$,
satisfying the conditions (ii), (iii) and (iv).

Then by Lemma 25, the vector $\boldsymbol{0}$ can be written as a
$\mathbb{R}_{>0}$-linear combination of a finite number of elements in
$\mathcal{S}$, satisfying the conditions (ii), (iii) and (iv). ∎

######  Corollary 27.

If the generator $A$ of the group $\langle A_{1},\ldots,A_{K}\rangle$ is a
positive scale, it is the decidable in PTIME whether
$\langle\mathcal{G}\rangle$ is a group.

###### Proof.

Since $\langle A_{1},\ldots,A_{K}\rangle\cong\mathbb{Z}$, we have
$J_{+}\neq\emptyset,J_{-}\neq\emptyset$. Given $\mathcal{S}$ as a set of
cells, it is decidable whether there exist a finite non-empty set of vectors
$\\{\boldsymbol{s}_{1},\ldots,\boldsymbol{s}_{m}\\}\subseteq\mathcal{S}$
satisfying conditions (ii), (iii) and (iv), as well as strictly positive reals
$r_{1},\ldots,r_{m}$ such that
$r_{1}\boldsymbol{s}_{1}+\cdots+r_{m}\boldsymbol{s}_{m}=\boldsymbol{0}$.
Indeed, this is true if and only if the largest linear subspace $\mathcal{L}$
of the $\mathbb{R}_{\geq 0}$-cone $\langle\mathcal{S}\rangle_{\mathbb{R}_{\geq
0}}$ generated by $\mathcal{S}$ contains some cell
$\operatorname{Cell}(\boldsymbol{d}_{i*})$ for all $i\in J_{+}$, some cell
$\operatorname{Cell}(\boldsymbol{d}_{*j})$ for all $j\in J_{-}$, and some cell
$\operatorname{Cell}(\boldsymbol{e}_{k})$ for all $k\in J_{0}$. This is
decidable in linear time since the number of cells is finite.

Given the input set $\mathcal{G}$, we can compute the set of cells in
$\mathcal{S}$ in PTIME. Therefore, by Proposition 26, it is decidable in PTIME
whether $\langle\mathcal{G}\rangle$ is a group. ∎

We can now prove the main result of this section.

See 10

###### Proof.

Division into six cases has already been proved by Lemma 14 and 15 as well as
the discussion that follows. In cases (ii), (iii) and (v), Proposition 18, 19
and 22 show that $\langle\mathcal{G}\rangle$ is a group. We now show PTIME
decidability.

First, we decide in PTIME which of the six cases is true for $G$, using Lemma
16. In cases (ii), (iii) and (v), the Group Problem for
$\langle\mathcal{G}\rangle$ has positive answer. In cases (i), (iv) and (vi),
Proposition 17, Corollary 21 and Corollary 27 show the desired PTIME
decidability result. ∎

##  VI Extensions and obstacles to Semigroup Membership

In previous sections we showed decidability and NP-completeness of the
Identity Problem and the Group Problem in $\mathsf{SA}(2,\mathbb{Z})$. In this
section we discuss possible extensions of our result and obstacles to solving
the Semigroup Membership problem in $\mathsf{SA}(2,\mathbb{Z})$.

Let
$\mathcal{G}\coloneqq\\{(A_{1},\boldsymbol{a}_{1}),\ldots,(A_{K},\boldsymbol{a}_{K})\\}$
be a set of elements of $\mathsf{SA}(2,\mathbb{Z})$. This first obvious
obstacle for deciding Semigroup Membership for $\langle\mathcal{G}\rangle$ is
that we can no longer suppose $G\coloneqq\langle A_{1},\ldots,A_{K}\rangle$ to
be a group, which we could do for the Identity Problem and the Group Problem.
However, if we restrict the target element to be of the form
$(I,\boldsymbol{a})$, that is, if we want to deciding whether
$(I,\boldsymbol{a})\in\langle\mathcal{G}\rangle$, then we can still suppose
$G$ to be a group.

Indeed, if $G$ is not a group, then at least one of the $A_{i}$ is not
invertible in $G$. Therefore, a word over $\mathcal{G}$ representing
$(I,\boldsymbol{a})$ cannot contain the letter $(A_{i},\boldsymbol{a}_{i})$.
We can thus delete $(A_{i},\boldsymbol{a}_{i})$ from the alphabet
$\mathcal{G}$ without changing whether
$(I,\boldsymbol{a})\in\langle\mathcal{G}\rangle$. One can repeat this process
until $G$ becomes a group.

Under the additional assumption that $G$ is a group, we can decide Semigroup
Membership for $\langle\mathcal{G}\rangle$ in all except one cases. Recall
Theorem 8, if $G$ contains a non-abelian free subgroup, then
$\langle\mathcal{G}\rangle$ is a group by Proposition 9. Hence Semigroup
Membership reduces to Group Membership, and is decidable by the result of
Delgado [13]. If $G$ is virtually solvable, then consider the six cases in
Proposition 10. Case (ii), (iii) and (v) are easy since
$\langle\mathcal{G}\rangle$ becomes a group. In case (i), deciding whether
$(I,\boldsymbol{a})\in\langle\mathcal{G}\rangle$ reduces to solving the linear
equation $n_{1}\boldsymbol{a}_{1}+n_{2}\boldsymbol{a}_{2}+\cdots
n_{K}\boldsymbol{a}_{K}=\boldsymbol{a}$ for
$(n_{1},\ldots,n_{K})\in\mathbb{Z}_{\geq 0}^{K}\setminus\\{\boldsymbol{0}\\}$,
and is decidable by integer programming. In case (iv), Semigroup Membership
for $\langle\mathcal{G}\rangle$ reduces to Semigroup Membership in the
Heisenberg group $\operatorname{H}_{3}(\mathbb{Q})$, which is decidable by the
result of Colcombet et al. [35]. Only case (vi) remains unsolved.

We now show that solving the Semigroup Membership problem in case (vi) is
equivalent to solving the Semigroup Membership problem in the group
$\mathbb{Z}[\lambda]\rtimes_{\lambda}\mathbb{Z}$. Given $\lambda>1$ that
satisfies a quadratic equation $\lambda^{2}-a\lambda+1=0$ for some $a\geq 3$,
we define the following semidirect product:

$\mathbb{Z}[\lambda]\rtimes_{\lambda}\mathbb{Z}\coloneqq\left\\{\begin{pmatrix}\lambda^{k}&x\\\
0&1\\\
\end{pmatrix}\;\middle|\;k\in\mathbb{Z},x\in\mathbb{Z}[\lambda]\right\\}.$

Here, $\mathbb{Z}[\lambda]$ is the ring generated by $1$ and $\lambda$. There
exist an embedding of $\mathbb{Z}[\lambda]\rtimes_{\lambda}\mathbb{Z}$ as a
subgroup of $\mathsf{SA}(2,\mathbb{Z})$ in the following way. For a given
$\lambda$ satisfying $\lambda^{2}-a\lambda+1=0$, define the matrix
$A_{\lambda}\coloneqq\begin{pmatrix}0&-1\\\ 1&a\\\ \end{pmatrix}$ in
$\mathsf{SL}(2,\mathbb{Z})$. Since $\lambda$ is a quadratic integer, every
element $x\in\mathbb{Z}[\lambda]$ can be written uniquely as $x=x_{1}+\lambda
x_{\lambda}$ for some $x_{1},x_{\lambda}\in\mathbb{Z}$. Define the map

$\displaystyle\phi\colon\mathbb{Z}[\lambda]\rtimes_{\lambda}\mathbb{Z}$
$\displaystyle\longrightarrow\mathsf{SA}(2,\mathbb{Z})$
$\displaystyle\begin{pmatrix}\lambda^{k}&x\\\ 0&1\\\ \end{pmatrix}$
$\displaystyle\longmapsto\left(A_{\lambda}^{k},(x_{1},x_{\lambda})^{\top}\right).$

It is easy to verify that $\phi$ is an injective group homomorphism.
Furthermore, the image under $\phi$ of a sub-semigroup555We suppose that the
upper-left entries of elements of the semigroup contain both positive and
negative exponents of $\lambda$, otherwise deciding Semigroup Membership is
easy. of $\mathbb{Z}[\lambda]\rtimes_{\lambda}\mathbb{Z}$ satisfies case (vi)
of Proposition 10. Therefore, solving the hard case of the Semigroup
Membership problem in $\mathsf{SA}(2,\mathbb{Z})$ necessitates solving the
Semigroup Membership problem in
$\mathbb{Z}[\lambda]\rtimes_{\lambda}\mathbb{Z}$.

On the other hand, given any positive scale $A\in\mathsf{SL}(2,\mathbb{Z})$
with eigenvalue $\lambda>1$, one can find a change of basis matrix
$P\in\mathsf{SL}(2,\mathbb{Z})$ such that $P^{-1}AP=A_{\lambda}$ (see [36]).
Therefore, any (finitely generated) semigroup $\langle\mathcal{G}\rangle$
satisfying case (vi) of Proposition 10 must be conjugate666The conjugation is
realized by the change-of-basis matrix $\operatorname{diag}(P,1).$ to a
(finitely generated) sub-semigroup of
$\phi(\mathbb{Z}[\lambda]\rtimes_{\lambda}\mathbb{Z})\leq\mathsf{SA}(2,\mathbb{Z})$.
Hence, solving Semigroup Membership in
$\mathbb{Z}[\lambda]\rtimes_{\lambda}\mathbb{Z}$ is sufficient for solving
Semigroup Membership in the case (vi) of Proposition 10.

Although the Semigroup Membership problem in
$\mathbb{Z}[\lambda]\rtimes_{\lambda}\mathbb{Z}$ remains an open problem, the
group bears certain similarities to the better studied _Baumslag-Solitar
group_ $\mathsf{BS}(1,q)$:

$\mathsf{BS}(1,q)\coloneqq\mathbb{Z}[\frac{1}{q}]\rtimes_{q}\mathbb{Z}=\left\\{\begin{pmatrix}q^{k}&x\\\
0&1\\\
\end{pmatrix}\;\middle|\;k\in\mathbb{Z},x\in\mathbb{Z}[\frac{1}{q}]\right\\}.$

Here, $q\geq 2$ is an integer. A recent result by Cadilhac, Chistikov and
Zetzsche [24] showed decidability of the _rational subset membership problem_
in $\mathsf{BS}(1,q)$ by considering rational languages of _base- $q$
expansions_. This result subsumes decidability of the Semigroup Membership
problem in $\mathsf{BS}(1,q)$. Therefore, it would be interesting to adapt
this approach to study Semigroup Membership in
$\mathbb{Z}[\lambda]\rtimes_{\lambda}\mathbb{Z}$ by considering rational
languages of _base- $\lambda$ expansions_ [25], where $\lambda$ is an
algebraic integer. Nevertheless, adaptation of the previous result to a non-
integer base of numeration poses various additional difficulties that we have
not been able to surmount.

## Acknowledgment

The author acknowledges support from UKRI Frontier Research Grant
EP/X033813/1.

## References

  * [1] R. Beals and L. Babai, “Las vegas algorithms for matrix groups,” in _Proceedings of 1993 IEEE 34th Annual Foundations of Computer Science_. IEEE, 1993, pp. 427–436.
  * [2] V. D. Blondel, E. Jeandel, P. Koiran, and N. Portier, “Decidable and undecidable problems about quantum automata,” _SIAM Journal on Computing_ , vol. 34, no. 6, pp. 1464–1473, 2005.
  * [3] C. Choffrut and J. Karhumäki, “Some decision problems on integer matrices,” _RAIRO-Theoretical Informatics and Applications-Informatique Théorique et Applications_ , vol. 39, no. 1, pp. 125–131, 2005.
  * [4] H. Derksen, E. Jeandel, and P. Koiran, “Quantum automata and algebraic groups,” _Journal of Symbolic Computation_ , vol. 39, no. 3-4, pp. 357–371, 2005.
  * [5] E. Hrushovski, J. Ouaknine, A. Pouly, and J. Worrell, “Polynomial invariants for affine programs,” in _Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science_ , 2018, pp. 530–539.
  * [6] A. Markov, “On certain insoluble problems concerning matrices,” _Doklady Akad. Nauk SSSR_ , vol. 57, no. 6, pp. 539–542, 1947.
  * [7] K. A. Mikhailova, “The occurrence problem for direct products of groups,” _Matematicheskii Sbornik_ , vol. 112, no. 2, pp. 241–251, 1966.
  * [8] R. Dong, “On the Identity Problem and the Group Problem in nilpotent groups,” _arXiv preprint arXiv:2208.02164_ , 2022, submitted.
  * [9] P. C. Bell and I. Potapov, “On the undecidability of the identity correspondence problem and its applications for word and matrix semigroups,” _International Journal of Foundations of Computer Science_ , vol. 21, no. 06, pp. 963–978, 2010.
  * [10] M. Lohrey, “Subgroup membership in gl (2, z),” in _38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)_. Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021.
  * [11] P. C. Bell, M. Hirvensalo, and I. Potapov, “The identity problem for matrix semigroups in SL2(Z) is NP-complete,” in _Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms_. SIAM, 2017, pp. 187–206.
  * [12] S. Ko, R. Niskanen, and I. Potapov, “On the identity problem for the special linear group and the heisenberg group,” in _45th International Colloquium on Automata, Languages, and Programming, ICALP 2018_ , ser. LIPIcs, I. Chatzigiannakis, C. Kaklamanis, D. Marx, and D. Sannella, Eds., vol. 107. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, pp. 132:1–132:15.
  * [13] J. Delgado Rodríguez, “Extensions of free groups: algebraic, geometric, and algorithmic aspects,” Ph.D. dissertation, Universitat Politècnica de Catalunya, 2017.
  * [14] J. A. Wolf, “The affine group of a Lie group,” in _Proc. Amer. Math. Soc._ , vol. 14, 1963, pp. 352–353.
  * [15] D. Mundici, “Invariant measure under the affine group over,” _Combinatorics, Probability and Computing_ , vol. 23, no. 2, pp. 248–268, 2014.
  * [16] L. M. Cabrer and D. Mundici, “Classifying orbits of the affine group over the integers,” _Ergodic Theory and Dynamical Systems_ , vol. 37, no. 2, pp. 440–453, 2017.
  * [17] A. R. Tarrida, _Affine Maps, Euclidean Motions and Quadrics_. Springer, 2011.
  * [18] L. A. Giefer, J. Clemens, and K. Schill, “Extended object tracking on the affine group aff (2),” in _2020 IEEE 23rd International Conference on Information Fusion (FUSION)_. IEEE, 2020, pp. 1–8.
  * [19] J. Kwon and F. C. Park, “Visual tracking via particle filtering on the affine group,” _The International Journal of Robotics Research_ , vol. 29, no. 2-3, pp. 198–217, 2010.
  * [20] L. F. Alday and Y. Tachikawa, “Affine SL(2) conformal blocks from 4d gauge theories,” _Letters in Mathematical Physics_ , vol. 94, no. 1, pp. 87–114, 2010.
  * [21] M. Raskin, F. Mazowiecki, C. Haase, and M. Blondin, “Affine extensions of integer vector addition systems with states,” _Logical Methods in Computer Science_ , vol. 17, 2021.
  * [22] A. Finkel, S. Göller, and C. Haase, “Reachability in register machines with polynomial updates,” in _International Symposium on Mathematical Foundations of Computer Science_. Springer, 2013, pp. 409–420.
  * [23] S.-K. Ko, R. Niskanen, and I. Potapov, “Reachability problems in nondeterministic polynomial maps on the integers,” in _International Conference on Developments in Language Theory_. Springer, 2018, pp. 465–477.
  * [24] M. Cadilhac, D. Chistikov, and G. Zetzsche, “Rational subsets of baumslag-solitar groups,” in _47th International Colloquium on Automata, Languages, and Programming, ICALP 2020_ , ser. LIPIcs, A. Czumaj, A. Dawar, and E. Merelli, Eds., vol. 168. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020, pp. 116:1–116:16.
  * [25] F. Blanchard, “-expansions and symbolic dynamics,” _Theoretical Computer Science_ , vol. 65, no. 2, pp. 131–141, 1989.
  * [26] C. Druţu and M. Kapovich, _Geometric group theory_. American Mathematical Soc., 2018, vol. 63.
  * [27] R. Beals, “Algorithms for matrix groups and the tits alternative,” _Journal of computer and system sciences_ , vol. 58, no. 2, pp. 260–279, 1999\.
  * [28] J.-P. Serre, _Trees_. Springer Science & Business Media, 2002.
  * [29] M. Newman, “The structure of some subgroups of the modular group,” _Illinois Journal of Mathematics_ , vol. 6, no. 3, pp. 480–487, 1962.
  * [30] J. Tits, “Free subgroups in linear groups,” _Journal of Algebra_ , vol. 20, no. 2, pp. 250–270, 1972.
  * [31] R. G. Swan, “Groups of cohomological dimension one,” _Journal of Algebra_ , vol. 12, no. 4, pp. 585–610, 1969.
  * [32] L. Babai, R. Beals, J.-y. Cai, G. Ivanyos, and E. M. Luks, “Multiplicative equations over commuting matrices,” in _Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms_ , 1996, pp. 498–507.
  * [33] M. Bremner, _Lattice basis reduction_. CRC Press New York, 2011.
  * [34] M. Giesbrecht, “Nearly optimal algorithms for canonical matrix forms,” _SIAM Journal on Computing_ , vol. 24, no. 5, pp. 948–969, 1995.
  * [35] T. Colcombet, J. Ouaknine, P. Semukhin, and J. Worrell, “On reachability problems for low-dimensional matrix semigroups,” in _46th International Colloquium on Automata, Languages, and Programming, ICALP 2019_ , ser. LIPIcs, C. Baier, I. Chatzigiannakis, P. Flocchini, and S. Leonardi, Eds., vol. 132. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019, pp. 44:1–44:15.
  * [36] J. T. Campbell and E. C. Trouy, “When are two elements of GL(2,Z) similar?” _Linear Algebra and its Applications_ , vol. 157, pp. 175–184, 1991.

## Omitted proofs

See 1

###### Proof.

$(i)\Longrightarrow(ii)$. Let $w\in\mathcal{A}^{*}$ be a full-image word with
$\pi(w)=I$. Then for every $i$, the word $w$ can be written as
$w=va_{i}v^{\prime}$, so
$a_{i}^{-1}=\pi(v^{\prime})\pi(v)\in\langle\mathcal{A}\rangle$. Therefore, the
semigroup $\langle\mathcal{A}\rangle$ contains all the inverse $a_{i}^{-1}$,
and is thus a group.

$(ii)\Longrightarrow(iii)$. If $\langle\mathcal{A}\rangle$ is a group, then
for all $i$, the inverse $a_{i}^{-1}$ can be written as $\pi(w_{i})$ for some
word $w_{i}\in\mathcal{A}^{*}$. Then for any element
$A\in\langle\mathcal{A}\rangle$, represented by some word
$w_{A}\in\mathcal{A}^{*}$, the word $w\coloneqq
w_{A}a_{1}w_{1}a_{2}w_{2}\cdots a_{K}w_{K}$ is a full-image word with
$\pi(w)=\pi(w_{A})\pi(a_{1}w_{1})\cdots\pi(a_{K}w_{K})=A$.

$(ii)\Longrightarrow(i)$. If $\langle\mathcal{A}\rangle$ is a group, then
$I\in\langle\mathcal{A}\rangle$, so by $(ii)\Longrightarrow(iii)$, $I$ can be
represented by a full-image word. ∎

See 12

###### Proof.

Since $(A,\boldsymbol{a})\cdot(B,\boldsymbol{b})=(I,\boldsymbol{x})$, we have
$B=A^{-1}$ and $\boldsymbol{x}=A\boldsymbol{b}+\boldsymbol{a}$.

Let $\lambda$ be the eigenvalue of $A$ associated to the invariant subspace
$V$, then $\lambda^{-1}$ is the eigenvalue associated to the invariant
subspace $W$. Then we have
$A^{n}\boldsymbol{x}=\lambda^{n}\boldsymbol{x}_{V}+\lambda^{-n}\boldsymbol{x}_{W}$
for every integer $n$.

Consider two cases.

  1. 1.

If $V$ is a stretching direction. In this case, $|\lambda|>1$. Let $m>0$ be a
positive integer, and let
$w\coloneqq(A,\boldsymbol{a})^{m-1}(B,\boldsymbol{b})^{m-1}$. Consider the
product

$\displaystyle(A,\boldsymbol{a})\cdot w\cdot(B,\boldsymbol{b})$
$\displaystyle=$ $\displaystyle(A,\boldsymbol{a})^{m}(B,\boldsymbol{b})^{m}$
$\displaystyle=$
$\displaystyle(I,(I+A+\cdots+A^{(m-1)})(A\boldsymbol{b}+\boldsymbol{a}))$
$\displaystyle=$ $\displaystyle(I,(I+A+\cdots+A^{(m-1)})\boldsymbol{x})$
$\displaystyle=$
$\displaystyle(I,\sum_{i=0}^{m-1}\lambda^{i}\boldsymbol{x}_{V}+\sum_{i=0}^{m-1}\lambda^{-i}\boldsymbol{x}_{W})$

Let
$\boldsymbol{y}\coloneqq\sum_{i=0}^{m-1}\lambda^{i}\boldsymbol{x}_{V}+\sum_{i=0}^{m-1}\lambda^{-i}\boldsymbol{x}_{W}$,
then $\boldsymbol{y}_{V}=\sum_{i=0}^{m-1}\lambda^{i}\boldsymbol{x}_{V}$,
$\boldsymbol{y}_{W}=\sum_{i=0}^{m-1}\lambda^{-i}\boldsymbol{x}_{W}$. Since
$\boldsymbol{x}\notin V\cup W$, we have
$\boldsymbol{x}_{V}\neq\boldsymbol{0},\boldsymbol{x}_{W}\neq\boldsymbol{0}$.
When $m$ is odd, we have $\sum_{i=0}^{m-1}\lambda^{i}>0$,
$\sum_{i=0}^{m-1}\lambda^{-i}>0$, so
$\boldsymbol{y}_{V}^{\top}\boldsymbol{x}_{V}>0$ and
$\boldsymbol{y}_{W}^{\top}\boldsymbol{x}_{W}>0$.

We then show that when $m$ tends towards infinity,
$\frac{|\boldsymbol{v}^{\top}\boldsymbol{y}|}{|\boldsymbol{v}||\boldsymbol{y}|}$
will tend to one. Indeed,

$\displaystyle\frac{|\boldsymbol{v}^{\top}\boldsymbol{y}|}{|\boldsymbol{v}||\boldsymbol{y}|}=$
$\displaystyle\frac{\left|\sum_{i=0}^{m-1}\lambda^{i}\boldsymbol{v}^{\top}\boldsymbol{x}_{V}+\sum_{i=0}^{m-1}\lambda^{-i}\boldsymbol{v}^{\top}\boldsymbol{x}_{W}\right|}{|\boldsymbol{v}|\left|\sum_{i=0}^{m-1}\lambda^{i}\boldsymbol{x}_{V}+\sum_{i=0}^{m-1}\lambda^{-i}\boldsymbol{x}_{W}\right|}$
$\displaystyle\geq$
$\displaystyle\frac{|\boldsymbol{v}|\left|\sum_{i=0}^{m-1}\lambda^{i}\boldsymbol{x}_{V}\right|}{|\boldsymbol{v}|\left|\sum_{i=0}^{m-1}\lambda^{i}\boldsymbol{x}_{V}+\sum_{i=0}^{m-1}\lambda^{-i}\boldsymbol{x}_{W}\right|}$
$\displaystyle-\frac{\left|\sum_{i=0}^{m-1}\lambda^{-i}\boldsymbol{v}^{\top}\boldsymbol{x}_{W}\right|}{|\boldsymbol{v}|\left|\sum_{i=0}^{m-1}\lambda^{i}\boldsymbol{x}_{V}+\sum_{i=0}^{m-1}\lambda^{-i}\boldsymbol{x}_{W}\right|}$
$\displaystyle=$
$\displaystyle\frac{|\boldsymbol{v}|\left|\boldsymbol{x}_{V}\right|}{|\boldsymbol{v}|\left|\boldsymbol{x}_{V}+\lambda^{1-m}\boldsymbol{x}_{W}\right|}$
$\displaystyle-\frac{\left|\boldsymbol{v}^{\top}\boldsymbol{x}_{W}\right|}{|\boldsymbol{v}|\left|\lambda^{m-1}\boldsymbol{x}_{V}+\boldsymbol{x}_{W}\right|}$

When $m\rightarrow\infty$, this expression tends towards $1-0=1$. This is
because $|\lambda|>1$ and
$\boldsymbol{v}\neq\boldsymbol{0},\boldsymbol{x}_{V}\neq\boldsymbol{0}$.
Hence, for a large enough odd integer $m$, we have

$1-\frac{|\boldsymbol{v}^{\top}\boldsymbol{y}|}{|\boldsymbol{v}||\boldsymbol{y}|}<\varepsilon,\quad\boldsymbol{y}_{V}^{\top}\boldsymbol{x}_{V}>0,\quad\boldsymbol{y}_{W}^{\top}\boldsymbol{x}_{W}>0.$

  2. 2.

If $V$ is a compressing direction. In this case, $|\lambda|<1$. Let $m>0$ be a
positive integer, and let
$w\coloneqq(B,\boldsymbol{b})^{m}(A,\boldsymbol{a})^{m}$. Consider the product

$\displaystyle(A,\boldsymbol{a})\cdot w\cdot(B,\boldsymbol{b})$
$\displaystyle=$
$\displaystyle(A,\boldsymbol{a})(B,\boldsymbol{b})(B,\boldsymbol{b})^{m-1}(A,\boldsymbol{a})^{m-1}(A,\boldsymbol{a})(B,\boldsymbol{b})$
$\displaystyle=$
$\displaystyle(I,(2I+A^{-1}+\cdots+A^{-(m-1)})(A\boldsymbol{b}+\boldsymbol{a}))$
$\displaystyle=$
$\displaystyle(I,(2I+A^{-1}+\cdots+A^{-(m-1)})\boldsymbol{x})$
$\displaystyle=$
$\displaystyle(I,\left(1+\sum_{i=0}^{m-1}\lambda^{-i}\right)\boldsymbol{x}_{V}+\left(1+\sum_{i=0}^{m-1}\lambda^{i}\right)\boldsymbol{x}_{W})$

Let
$\boldsymbol{y}\coloneqq\left(1+\sum_{i=0}^{m-1}\lambda^{-i}\right)\boldsymbol{x}_{V}+\left(1+\sum_{i=0}^{m-1}\lambda^{i}\right)\boldsymbol{x}_{W})$,
then
$\boldsymbol{y}_{V}=\left(1+\sum_{i=0}^{m-1}\lambda^{-i}\right)\boldsymbol{x}_{V}$,
$\boldsymbol{y}_{W}=\left(1+\sum_{i=0}^{m-1}\lambda^{i}\right)\boldsymbol{x}_{W}$.
Since $\boldsymbol{x}\notin V\cup W$, we have
$\boldsymbol{x}_{V}\neq\boldsymbol{0}$ and
$\boldsymbol{x}_{W}\neq\boldsymbol{0}$. When $m$ is odd, we have
$\sum_{i=0}^{m-1}\lambda^{i}>0$, $\sum_{i=0}^{m-1}\lambda^{-i}>0$, so
$\boldsymbol{y}_{V}^{\top}\boldsymbol{x}_{V}>0,\boldsymbol{y}_{W}^{\top}\boldsymbol{x}_{W}>0$.

We then show that when $m$ tends towards infinity,
$\frac{|\boldsymbol{v}^{\top}\boldsymbol{y}|}{|\boldsymbol{v}||\boldsymbol{y}|}$
will tend to one. Indeed,

$\displaystyle\frac{|\boldsymbol{v}^{\top}\boldsymbol{y}|}{|\boldsymbol{v}||\boldsymbol{y}|}$
$\displaystyle=$
$\displaystyle\frac{\left[\left(1+\sum_{i=0}^{m-1}\lambda^{-i}\right)\boldsymbol{v}^{\top}\boldsymbol{x}_{V}+\left(1+\sum_{i=0}^{m-1}\lambda^{i}\right)\boldsymbol{v}^{\top}\boldsymbol{x}_{W}\right|}{|\boldsymbol{v}|\left|\left(1+\sum_{i=0}^{m-1}\lambda^{-i}\right)\boldsymbol{x}_{V}+\left(1+\sum_{i=0}^{m-1}\lambda^{i}\right)\boldsymbol{x}_{W}\right|}$
$\displaystyle\geq$
$\displaystyle\frac{|\boldsymbol{v}|\left|\boldsymbol{x}_{V}\right|}{|\boldsymbol{v}|\left|\boldsymbol{x}_{V}+\frac{1+\sum_{i=0}^{m-1}\lambda^{i}}{1+\sum_{i=0}^{m-1}\lambda^{-i}}\boldsymbol{x}_{W}\right|}$
$\displaystyle-\frac{\left|\boldsymbol{v}^{\top}\boldsymbol{x}_{W}\right|}{|\boldsymbol{v}|\left|\frac{1+\sum_{i=0}^{m-1}\lambda^{-i}}{1+\sum_{i=0}^{m-1}\lambda^{i}}\boldsymbol{x}_{V}+\boldsymbol{x}_{W}\right|}$

When $m\rightarrow\infty$, this expression tends towards $1-0=1$. This is
because $|\lambda|<1$ and
$\boldsymbol{v}\neq\boldsymbol{0},\boldsymbol{x}_{V}\neq\boldsymbol{0}$, so

$\lim_{m\rightarrow\infty}\frac{1+\sum_{i=0}^{m-1}\lambda^{i}}{1+\sum_{i=0}^{m-1}\lambda^{-i}}=0.$

Hence, for a large enough odd integer $m$, we have

$1-\frac{|\boldsymbol{v}^{\top}\boldsymbol{y}|}{|\boldsymbol{v}||\boldsymbol{y}|}<\varepsilon,\quad\boldsymbol{y}_{V}^{\top}\boldsymbol{x}_{V}>0,\quad\boldsymbol{y}_{W}^{\top}\boldsymbol{x}_{W}>0.$

Combining the two cases yields the desired result. ∎

See 13

###### Proof.

Since $(A,\boldsymbol{a})\cdot(B,\boldsymbol{b})=(I,\boldsymbol{x})$, we have
$B=A^{-1}$ and $\boldsymbol{x}=A\boldsymbol{b}+\boldsymbol{a}$.

Let $W$ be the orthogonal space of $V$, and $\boldsymbol{w}$ be a non-zero
vector in $W$. Under the basis $\\{\boldsymbol{v},\boldsymbol{w}\\}$, the
matrix $A$ has the form $\begin{pmatrix}1&\mu\\\ 0&1\\\ \end{pmatrix}$, where
$\mu\neq 0$. Then for every integer $n$, we have
$A^{n}\boldsymbol{x}=\boldsymbol{x}+n\mu c\boldsymbol{v}$, where $c$ is a
scalar such that $c\boldsymbol{w}=\boldsymbol{x}_{W}$. Since
$\boldsymbol{x}\notin V$, we have $\boldsymbol{x}_{W}\neq\boldsymbol{0}$, so
$c\neq 0$. Consider two cases.

  1. 1.

If $\mu c>0$. Let $m>0$ be a positive integer, and let
$w\coloneqq(A,\boldsymbol{a})^{m-1}(B,\boldsymbol{b})^{m-1}$. Consider the
product

$\displaystyle(A,\boldsymbol{a})\cdot w\cdot(B,\boldsymbol{b})$
$\displaystyle=\;$ $\displaystyle(A,\boldsymbol{a})^{m}(B,\boldsymbol{b})^{m}$
$\displaystyle=\;$
$\displaystyle\left(I,(I+A+\cdots+A^{(m-1)})(A\boldsymbol{b}+\boldsymbol{a})\right)$
$\displaystyle=\;$
$\displaystyle\left(I,(I+A+\cdots+A^{(m-1)})\boldsymbol{x}\right)$
$\displaystyle=\;$ $\displaystyle\left(I,m\boldsymbol{x}+\frac{m(m-1)}{2}\mu
c\boldsymbol{v}\right).$

Let $\boldsymbol{y}\coloneqq m\boldsymbol{x}+\frac{m(m-1)}{2}\mu
c\boldsymbol{v}$, then $\boldsymbol{y}$ and $\boldsymbol{x}$ lie in same
halfspace cut by $V$.

We then show that when $m$ tends towards infinity,
$\frac{\boldsymbol{v}^{\top}\boldsymbol{y}}{|\boldsymbol{v}||\boldsymbol{y}|}$
will tend to one. Indeed,

$\displaystyle\frac{\boldsymbol{v}^{\top}\boldsymbol{y}}{|\boldsymbol{v}||\boldsymbol{y}|}=\;$
$\displaystyle\frac{m\boldsymbol{v}^{\top}\boldsymbol{x}+\frac{m(m-1)}{2}\mu
c\boldsymbol{v}^{\top}\boldsymbol{v}}{|\boldsymbol{v}|\left|m\boldsymbol{x}+\frac{m(m-1)}{2}\mu
c\boldsymbol{v}\right|}$ $\displaystyle=\;$
$\displaystyle\frac{\boldsymbol{v}^{\top}\boldsymbol{x}}{|\boldsymbol{v}|\left|\boldsymbol{x}+\frac{(m-1)}{2}\mu
c\boldsymbol{v}\right|}+\frac{\frac{(m-1)}{2}\mu
c|\boldsymbol{v}|}{\left|\boldsymbol{x}+\frac{(m-1)}{2}\mu
c\boldsymbol{v}\right|}.$

When $m\rightarrow\infty$, this expression tends towards $0+1=1$, because $\mu
c>0$ and $\boldsymbol{v}\neq\boldsymbol{0}$. Hence, for a large enough odd
integer $m$, we have
$1-\frac{\boldsymbol{v}^{\top}\boldsymbol{y}}{|\boldsymbol{v}||\boldsymbol{y}|}<\varepsilon.$

  2. 2.

If $\mu c<0$. Let $m>0$ be a positive integer, and let
$w\coloneqq(B,\boldsymbol{b})^{m}(A,\boldsymbol{a})^{m}$. Consider the product

$\displaystyle(A,\boldsymbol{a})\cdot w\cdot(B,\boldsymbol{b})$
$\displaystyle=\;$
$\displaystyle(A,\boldsymbol{a})(B,\boldsymbol{b})(B,\boldsymbol{b})^{m-1}(A,\boldsymbol{a})^{m-1}(A,\boldsymbol{a})(B,\boldsymbol{b})$
$\displaystyle=\;$
$\displaystyle\left(I,(2I+A^{-1}+\cdots+A^{-(m-1)})(A\boldsymbol{b}+\boldsymbol{a})\right)$
$\displaystyle=\;$
$\displaystyle\left(I,(2I+A^{-1}+\cdots+A^{-(m-1)})\boldsymbol{x}\right)$
$\displaystyle=\;$
$\displaystyle\left(I,(m+1)\boldsymbol{x}-\frac{m(m-1)}{2}\mu
c\boldsymbol{v}\right).$

Let $\boldsymbol{y}\coloneqq(m+1)\boldsymbol{x}-\frac{m(m-1)}{2}\mu
c\boldsymbol{v}$, then $\boldsymbol{y}$ and $\boldsymbol{x}$ lie in same
halfspace cut by $V$.

We then show that when $m$ tends towards infinity,
$\frac{\boldsymbol{v}^{\top}\boldsymbol{y}}{|\boldsymbol{v}||\boldsymbol{y}|}$
will tend to one. Indeed,

$\displaystyle\frac{\boldsymbol{v}^{\top}\boldsymbol{y}}{|\boldsymbol{v}||\boldsymbol{y}|}=\;$
$\displaystyle\frac{(m+1)\boldsymbol{v}^{\top}\boldsymbol{x}-\frac{m(m-1)}{2}\mu
c\boldsymbol{v}^{\top}\boldsymbol{v}}{|\boldsymbol{v}|\left|(m+1)\boldsymbol{x}-\frac{m(m-1)}{2}\mu
c\boldsymbol{v}\right|}$ $\displaystyle=\;$
$\displaystyle\frac{\boldsymbol{v}^{\top}\boldsymbol{x}}{|\boldsymbol{v}|\left|\boldsymbol{x}-\frac{m(m-1)}{2(m+1)}\mu
c\boldsymbol{v}\right|}+\frac{-\frac{m(m-1)}{2(m+1)}\mu
c|\boldsymbol{v}|}{\left|\boldsymbol{x}-\frac{m(m-1)}{2(m+1)}\mu
c\boldsymbol{v}\right|}.$

When $m\rightarrow\infty$, this expression tends towards $0+1=1$, because $\mu
c<0$ and $\boldsymbol{v}\neq\boldsymbol{0}$. Hence, for a large enough odd
integer $m$, we have
$1-\frac{\boldsymbol{v}^{\top}\boldsymbol{y}}{|\boldsymbol{v}||\boldsymbol{y}|}<\varepsilon.$

∎

See 22

###### Proof.

Since $\langle A_{1},\ldots,A_{K}\rangle$ is a group, we have
$A,A^{-1}\in\langle A_{1},\ldots,A_{K}\rangle$. Since $\langle
A_{1},\ldots,A_{K}\rangle$ is a group, let
$(A,a_{+}\boldsymbol{x}_{V}+b_{+}\boldsymbol{x}_{W})$ and
$(A^{-1},a_{-}\boldsymbol{x}_{V}+b_{-}\boldsymbol{x}_{W})$ be elements of
$\langle\mathcal{G}\rangle$ represented by full-image words.

Then for any $m>0$, the elements

$(I,\boldsymbol{v}_{m})\coloneqq(A,a_{+}\boldsymbol{x}_{V}+b_{+}\boldsymbol{x}_{W})^{m}\cdot(A^{-1},a_{-}\boldsymbol{x}_{V}+b_{-}\boldsymbol{x}_{W})^{m}\\\
=\left(I,\left(\frac{a_{+}}{1-\lambda}-\frac{a_{-}}{1-\lambda^{-1}}\right)(1-\lambda^{m})\boldsymbol{x}_{V}\right.\\\
+\left.\left(\frac{b_{+}}{1-\lambda^{-1}}-\frac{b_{-}}{1-\lambda}\right)(1-\lambda^{-m})\boldsymbol{x}_{W}\right)$

and

$(I,\boldsymbol{w}_{m})\coloneqq(A^{-1},a_{-}\boldsymbol{x}_{V}+b_{-}\boldsymbol{x}_{W})^{m}\cdot(A,a_{+}\boldsymbol{x}_{V}+b_{+}\boldsymbol{x}_{W})^{m}\\\
=\left(I,\left(\frac{a_{+}}{1-\lambda}-\frac{a_{-}}{1-\lambda^{-1}}\right)(\lambda^{-m}-1)\boldsymbol{x}_{V}\right.\\\
+\left.\left(\frac{b_{+}}{1-\lambda^{-1}}-\frac{b_{-}}{1-\lambda}\right)(\lambda^{m}-1)\boldsymbol{x}_{W}\right)$

are in $\langle\mathcal{G}\rangle$.

Consider four cases:

  1. 1.

$\frac{a_{+}}{1-\lambda}-\frac{a_{-}}{1-\lambda^{-1}}=\frac{b_{+}}{1-\lambda^{-1}}-\frac{b_{-}}{1-\lambda}=0$.
In this case we have directly $\boldsymbol{v}_{m}=\boldsymbol{0}$ for all $m$.
So $(I,\boldsymbol{0})$ can be represented by a full-image word.

  2. 2.

$\frac{a_{+}}{1-\lambda}-\frac{a_{-}}{1-\lambda^{-1}}=0$, but
$\frac{b_{+}}{1-\lambda^{-1}}-\frac{b_{-}}{1-\lambda}\neq 0$. When $m$ is
even, $\boldsymbol{w}_{m}$ is a positive multiple of $\boldsymbol{x}_{W}$, and
when $n$ is odd, $\boldsymbol{w}_{n}$ is a negative multiple of
$\boldsymbol{x}_{W}$. Therefore, there exists positive real numbers
$r_{1},r_{2}$ such that $r_{1}\boldsymbol{w}_{m}+r_{2}\boldsymbol{w}_{n}=0$.
Since $\boldsymbol{w}_{m},\boldsymbol{w}_{n}$ have integer entries, there even
exist positive _integers_ $n_{1},n_{2}$ such that
$n_{1}\boldsymbol{w}_{m}+n_{2}\boldsymbol{w}_{n}=0$. Therefore
$(I,\boldsymbol{0})=(I,\boldsymbol{w}_{m})^{n_{1}}(I,\boldsymbol{w}_{n})^{n_{2}}$
can be represented by a full-image word.

  3. 3.

$\frac{b_{+}}{1-\lambda^{-1}}-\frac{b_{-}}{1-\lambda}=0$, but
$\frac{a_{+}}{1-\lambda}-\frac{a_{-}}{1-\lambda^{-1}}\neq 0$. This case is
exactly the symmetry of the previous case.

  4. 4.

Both $\frac{a_{+}}{1-\lambda}-\frac{a_{-}}{1-\lambda^{-1}}$ and
$\frac{b_{+}}{1-\lambda^{-1}}-\frac{b_{-}}{1-\lambda}$ are non-zero. In this
case, consider the vectors $\boldsymbol{v}_{2m}$, $\boldsymbol{v}_{2m+1}$,
$\boldsymbol{w}_{2m}$, $\boldsymbol{w}_{2m+1}$ when $m$ tends to infinity.
Since $\lambda<-1$, we have
$\lim_{m\rightarrow\infty}(1-\lambda^{2m})=-\infty$,
$\lim_{m\rightarrow\infty}(1-\lambda^{2m+1})=+\infty$,
$\lim_{m\rightarrow\infty}(1-\lambda^{-2m})=1$,
$\lim_{m\rightarrow\infty}(1-\lambda^{-2m-1})=1$. Therefore, the _direction_
of $\boldsymbol{v}_{2m}$ tends towards $-\boldsymbol{x}_{V}$, the direction of
$\boldsymbol{v}_{2m+1}$ tends towards $\boldsymbol{x}_{V}$, the direction of
$\boldsymbol{w}_{2m}$ tends towards $\boldsymbol{x}_{W}$, the direction of
$\boldsymbol{w}_{2m+1}$ tends towards $-\boldsymbol{x}_{W}$. Hence, when $m$
is large enough, the four vectors $\boldsymbol{v}_{2m}$,
$\boldsymbol{v}_{2m+1}$, $\boldsymbol{w}_{2m}$, $\boldsymbol{w}_{2m+1}$ in
$\mathbb{Z}^{2}$ generate $\mathbb{Q}^{2}$ as a $\mathbb{Q}_{\geq 0}$-cone.
Hence, there exist positive integers $t_{1},\ldots,t_{4}$ such that

$(I,\boldsymbol{v}_{2m})^{t_{1}}\cdots(I,\boldsymbol{w}_{2m+1})^{t_{4}}=(I,\boldsymbol{0}).$

Therefore $(I,\boldsymbol{0})$ can be represented by a full-image word.

In all cases, $(I,\boldsymbol{0})$ can be represented by a full-image word, so
$\langle\mathcal{G}\rangle$ is a group. ∎

See 24

###### Proof.

For any $p\in\mathbb{Z}_{\geq 0}$, $q\in\mathbb{Z}_{>0}$, denote

$(I,\boldsymbol{v}_{pq})\coloneqq{A^{\prime}_{i}}^{pn_{j}}{A^{\prime}_{k}}^{q}{A^{\prime}_{j}}^{pn_{i}},\quad(I,\boldsymbol{w}_{pq})\coloneqq{A^{\prime}_{j}}^{pn_{i}}{A^{\prime}_{k}}^{q}{A^{\prime}_{i}}^{pn_{j}},$

Obviously, the letter $(A^{\prime}_{k},\boldsymbol{a}^{\prime}_{k})$ occurs in
both words. By direct computation, we have

$\boldsymbol{v}_{pq}=(1-\lambda^{-pn_{i}n_{j}})\cdot\left(\lambda^{pn_{i}n_{j}}d_{ija},d_{ijb}\right)^{\top}\\\
+(\lambda^{pn_{i}n_{j}}qa_{k},\lambda^{-pn_{i}n_{j}}qb_{k})^{\top},$
$\boldsymbol{w}_{pq}=(1-\lambda^{-pn_{i}n_{j}})\cdot\left(d_{ija},\lambda^{pn_{i}n_{j}}d_{ijb}\right)^{\top}\\\
+q\cdot(\lambda^{-pn_{i}n_{j}}a_{k},\lambda^{pn_{i}n_{j}}b_{k})^{\top}.$

Since $\lambda>1$, we have $1-\lambda^{-pn_{i}n_{j}}>0$.

If $\operatorname{Cell}(\boldsymbol{e}_{k})$ has dimension one or zero, then
take $p=0$ and the statement is trivial. Suppose that
$\operatorname{Cell}(\boldsymbol{e}_{k})$ has dimension two, then we have
$d_{ija}\neq 0$ and $d_{ijb}\neq 0$. Fix a large enough $p$ so that
$\frac{\lambda^{pn_{i}n_{j}}a_{k}}{\lambda^{-pn_{i}n_{j}}b_{k}}>\frac{x}{y}>\frac{\lambda^{-pn_{i}n_{j}}a_{k}}{\lambda^{pn_{i}n_{j}}b_{k}}$.
Then $(x,y)^{\top}$ can be written as
$r_{1}(\lambda^{-pn_{i}n_{j}}a_{k},\lambda^{pn_{i}n_{j}}b_{k})^{\top}+r_{2}(\lambda^{-pn_{i}n_{j}}a_{k},\lambda^{pn_{i}n_{j}}b_{k})$
for some $r_{1},r_{2}\in\mathbb{R}_{>0}$. When $q$ tends towards infinity, the
direction of the vectors $\boldsymbol{v}_{pq},\boldsymbol{w}_{pq}$ tends
respectively to
$(\lambda^{-pn_{i}n_{j}}a_{k},\lambda^{pn_{i}n_{j}}b_{k})^{\top}$ and
$(\lambda^{-pn_{i}n_{j}}a_{k},\lambda^{pn_{i}n_{j}}b_{k})$. Therefore, for
large enough $q$, the vector $(x,y)^{\top}$ can be written as
$r^{\prime}_{1}\boldsymbol{v}_{pq}+r^{\prime}_{2}\boldsymbol{w}_{pq}$ for some
$r^{\prime}_{1},r^{\prime}_{2}\in\mathbb{R}_{>0}$. ∎

See 25

###### Proof.

We call a vector of the form
$r_{1}\boldsymbol{s}_{1}+\cdots+r_{m}\boldsymbol{s}_{m},r_{i}\in\mathbb{R}_{>0},\boldsymbol{s}_{i}\in\mathcal{S}$,
an _$\mathbb{R}_{ >0}$-linear combination_ of elements in $\mathcal{S}$. For
$i=1,\ldots,M$, write

$(C_{i},\boldsymbol{c}_{i})=\left(\begin{pmatrix}\lambda^{t_{i}}&0\\\
0&\lambda^{-t_{i}}\\\ \end{pmatrix},\begin{pmatrix}c_{i}\\\ d_{i}\\\
\end{pmatrix}\right),$

where $t_{i}\in\\{-1,0,1\\}$. We show that if
$(C_{1},\boldsymbol{c}_{1})\cdots(C_{M},\boldsymbol{c}_{M})=(I,\boldsymbol{x})$
then $\boldsymbol{x}$ can be written as an $\mathbb{R}_{>0}$-linear
combination of elements in $\mathcal{S}$. We use induction on $M$. When $M=1$,
$(C_{1},\boldsymbol{c}_{1})=(I,\boldsymbol{e}_{k})$ for some $k\in J_{0}$, and
the statement is obvious. When $M\geq 2$, distinguish the following three
cases.

  1. 1.

If $t_{1}t_{M}=1$. Suppose $t_{1}=t_{M}=1$, the case where $t_{1}=t_{M}=-1$
can be done analogously.

Since $t_{1}=1>0$ and $t_{1}+\cdots+t_{M-1}=-1<0$, there must exist $1<i<M-1$
such that $t_{1}+\cdots+t_{i}=0$. By induction hypothesis,

$\displaystyle(C_{1},\boldsymbol{c}_{1})\cdots(C_{i},\boldsymbol{c}_{i})=(I,\boldsymbol{y}),$
$\displaystyle(C_{i+1},\boldsymbol{c}_{i+1})\cdots(C_{M},\boldsymbol{c}_{M})=(I,\boldsymbol{y}^{\prime}),$

where $\boldsymbol{y}$ and $\boldsymbol{y}^{\prime}$ can be written as a
$\mathbb{R}_{>0}$-linear combination of elements in $\mathcal{S}$. Therefore
$\boldsymbol{x}=\boldsymbol{y}+\boldsymbol{y}^{\prime}$ also satisfies this
claim.

  2. 2.

If $t_{1}t_{M}=-1$. In this case, $C_{2}\cdots C_{M-1}=C_{1}C_{2}\cdots C_{M}$
$=I$. Define
$w^{\prime}\coloneqq(C_{2},\boldsymbol{c}_{2})\cdots(C_{M-1},\boldsymbol{c}_{M-1})$.
Then the product of $w^{\prime}$ is of the form $(I,\boldsymbol{x}^{\prime})$,
where $\boldsymbol{x}^{\prime}$ is either $\boldsymbol{0}$ (when $w^{\prime}$
is empty), or $\boldsymbol{x}^{\prime}$ is a $\mathbb{R}_{>0}$-combination of
elements in $\mathcal{S}$ by the induction hypothesis. Hence

$\displaystyle\;(C_{1},\boldsymbol{c}_{1})\cdots(C_{M},\boldsymbol{c}_{M})$
$\displaystyle=$
$\displaystyle\;(C_{1},\boldsymbol{c}_{1})\cdot(I,\boldsymbol{x}^{\prime})\cdot(C_{M},\boldsymbol{c}_{M})$
$\displaystyle=$
$\displaystyle\;(I,\boldsymbol{c}_{1}+C_{1}\boldsymbol{c}_{M}+C_{1}\boldsymbol{x}^{\prime}).$

We claim that
$\boldsymbol{c}_{1}+C_{1}\boldsymbol{c}_{M}\in\operatorname{Cell}(\boldsymbol{d}_{ij})$.
First suppose $t_{1}=1,t_{M}=-1$. Let $i\in J_{+},j\in J_{-}$ be indices such
that
$\widehat{(A^{\prime}_{i},\boldsymbol{a}^{\prime}_{i})}=(C_{1},\boldsymbol{c}_{1})$
and
$\widehat{(A^{\prime}_{j},\boldsymbol{a}^{\prime}_{j})}=(C_{M},\boldsymbol{c}_{M})$,
then

$\displaystyle\boldsymbol{c}_{1}+C_{1}\boldsymbol{c}_{M}=$
$\displaystyle\left(a_{j}\cdot\frac{\lambda-1}{1-\lambda^{-n_{j}}}+a_{i}\cdot\frac{1-\lambda}{1-\lambda^{n_{i}}},\right.$
$\displaystyle\quad\quad\left.b_{j}\cdot\frac{\lambda^{-1}-1}{1-\lambda^{n_{j}}}+b_{i}\cdot\frac{1-\lambda^{-1}}{1-\lambda^{-n_{i}}}\right)$
$\displaystyle=$
$\displaystyle\left((\lambda-1)d_{ija},(1-\lambda^{-1})d_{ijb}\right)$
$\displaystyle\in$ $\displaystyle\operatorname{Cell}(\boldsymbol{d}_{ij}).$

Next suppose $t_{1}=-1,t_{M}=1$. Let $i\in J_{+},j\in J_{-}$ be indices such
that
$\widehat{(A^{\prime}_{j},\boldsymbol{a}^{\prime}_{j})}=(C_{1},\boldsymbol{c}_{1})$
and
$\widehat{(A^{\prime}_{i},\boldsymbol{a}^{\prime}_{i})}=(C_{M},\boldsymbol{c}_{M})$,
then

$\displaystyle\boldsymbol{c}_{1}+C_{1}\boldsymbol{c}_{M}=$
$\displaystyle\left(a_{i}\cdot\frac{\lambda^{-1}-1}{1-\lambda^{n_{i}}}+a_{j}\cdot\frac{1-\lambda^{-1}}{1-\lambda^{-n_{j}}},\right.$
$\displaystyle\quad\quad\left.b_{i}\cdot\frac{\lambda-1}{1-\lambda^{-n_{i}}}+b_{j}\cdot\frac{1-\lambda}{1-\lambda^{n_{j}}}\right)$
$\displaystyle=$
$\displaystyle\left((1-\lambda^{-1})d_{ija},(\lambda-1)d_{ijb}\right)$
$\displaystyle\in$ $\displaystyle\operatorname{Cell}(\boldsymbol{d}_{ij}).$

Hence, in both cases,
$\boldsymbol{c}_{1}+C_{1}\boldsymbol{c}_{M}\in\operatorname{Cell}(\boldsymbol{d}_{ij})\subseteq\mathcal{S}$.
We then show that
$\boldsymbol{c}_{1}+C_{1}\boldsymbol{c}_{M}+C_{1}\boldsymbol{x}^{\prime}$ is a
$\mathbb{R}_{>0}$-combination of elements in $\mathcal{S}$. Since
$\boldsymbol{x}^{\prime}$ is either zero or a $\mathbb{R}_{>0}$-combination of
elements in $\mathcal{S}$, write
$\boldsymbol{x}^{\prime}=\sum_{i=1}^{m}r_{i}\boldsymbol{s}_{i}$, where
$r_{i}>0,\boldsymbol{s}_{i}\in\mathcal{S}$. Then
$C_{1}\boldsymbol{x}^{\prime}=\sum_{i=1}^{m}r_{i}C_{1}\boldsymbol{s}_{i}$ is
still a $\mathbb{R}_{>0}$-combination of elements in $\mathcal{S}$ by the
definition (7). Hence,
$\boldsymbol{c}_{1}+C_{1}\boldsymbol{c}_{M}+C_{1}\boldsymbol{x}^{\prime}$ is a
$\mathbb{R}_{>0}$-combination of elements in $\mathcal{S}$.

  3. 3.

If $t_{1}t_{M}=0$. Suppose $t_{1}=0$, the case where $t_{M}=0$ can be done
analogously.

By induction hypothesis,

$(C_{1},\boldsymbol{c}_{1})=(I,\boldsymbol{y}),\quad(C_{2},\boldsymbol{c}_{2})\cdots(C_{M},\boldsymbol{c}_{M})=(I,\boldsymbol{y}^{\prime}),$

where $\boldsymbol{y}$ and $\boldsymbol{y}^{\prime}$ can be written as a
$\mathbb{R}_{>0}$-linear combination of elements in $\mathcal{S}$. Therefore
$\boldsymbol{x}=\boldsymbol{y}+\boldsymbol{y}^{\prime}$ also satisfies this
claim.

Therefore we have found an $\mathbb{R}_{>0}$-linear combination that satisfies
(i). The following can be easily seen from the above induction procedure: if
for some $i\in J_{+}$ the letter
$\widehat{(A^{\prime}_{i},\boldsymbol{a}^{\prime}_{i})}$ appears in $w$, then
the $\mathbb{R}_{>0}$-linear combination contains a vector
$\boldsymbol{s}_{\ell}$ in the cell $\operatorname{Cell}(\boldsymbol{d}_{ij})$
for some $j\in J_{-}$. Since $w$ is full-image, the condition (ii) in the
statement of the Lemma must hold. Similarly, the conditions (iii) and (iv)
must also hold. ∎