# The Identity Problem in nilpotent groups of bounded class

Ruiwen Dong111Department of Computer Science, University of Oxford, Oxford,
OX1 3QD, United Kingdom, email<EMAIL_ADDRESS>
###### Abstract

Let $G$ be a unitriangular matrix group of nilpotency class at most ten. We
show that the Identity Problem (does a semigroup contain the identity matrix?)
and the Group Problem (is a semigroup a group?) are decidable in polynomial
time for finitely generated subsemigroups of $G$. Our decidability results
also hold when $G$ is an arbitrary finitely generated nilpotent group of class
at most ten. This extends earlier work of Babai et al. on commutative matrix
groups (SODA’96) and work of Bell et al. on $\mathsf{SL}(2,\mathbb{Z})$
(SODA’17). Furthermore, we formulate a sufficient condition for the
generalization of our results to nilpotent groups of class $d>10$. For every
such $d$, we exhibit an effective procedure that verifies this condition in
case it is true.

##  1 Introduction

#### Algorithmic problems in matrix semigroups.

The computational theory of groups and semigroups is one of the oldest and
most well-developed parts of computational algebra. Algorithmic problems for
matrix semigroups have been studied in computer science continuously since the
work of Markov [35] in the 1940s. The area now plays an essential role in
analysing system dynamics, and has numerous applications in automata theory,
randomized algorithms, program analysis, and interactive proof systems [1, 6,
9, 13, 16, 25]. Among the most prominent problems in this area are _Semigroup
Membership_ and _Group Membership_ , proposed respectively by Markov and
Mikhailova in the mid twentieth century. For these decision problems, we work
in a fixed matrix group $G$. The input is a finite set of matrices
$\mathcal{G}=\\{A_{1},\ldots,A_{K}\\}\subseteq G$ and a matrix $A$. 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 the classical
results of Markov and Mikhailova [35, 36]. In this paper, we consider two
closely related problems introduced by Choffrut and Karhumäki [13] in 2005:
the _Identity Problem_ and the _Group Problem_. These two decision problems
concern the _structure_ of semigroups rather than their _membership_. Given as
input a finite set of matrices $\mathcal{G}$:

  1. (iii)

(Identity Problem) decide whether $\langle\mathcal{G}\rangle$ contains the
identity matrix $I$.

  2. (iv)

(Group Problem) decide whether $\langle\mathcal{G}\rangle$ is a group, in
other words, whether
$\langle\mathcal{G}\rangle=\langle\mathcal{G}\rangle_{grp}$.

All four algorithmic problems remain undecidable for matrices in low
dimensions: for example, for matrices in the group $\mathsf{SL}(4,\mathbb{Z})$
of $4\times 4$ integer matrices of determinant one [8, 36]. The undecidability
results stem from the fact that $\mathsf{SL}(4,\mathbb{Z})$ can embed a direct
product of two non-abelian free groups. On the other hand, for matrices in
$\mathsf{SL}(2,\mathbb{Z})$, Semigroup Membership was shown to be decidable in
EXPSPACE by Choffrut and Karhumaki [13], Group Membership is in PTIME by a
result of Lohrey [32], and the Identity Problem and the Group Problem are NP-
complete by results of Bell, Hirvensalo, and Potapov [7].

The goal of this paper is to solve the Identity Problem and the Group Problem
in matrix groups with additional structures. To this end, we will consider the
more general problem of computing _invertible subsets_ , which subsumes the
Identity Problem and the Group Problem.

######  Definition 1.1.

Let $G$ be a matrix group. Given a finite set of elements
$\mathcal{G}=\\{A_{1},\ldots,A_{K}\\}\subseteq G$, the _invertible subset_ of
$\mathcal{G}$ is the set of matrices in $\mathcal{G}$ who inverse lies in
$\langle\mathcal{G}\rangle$.

######  Proposition 1.2.

Given a finite set of matrices $\mathcal{G}=\\{A_{1},\ldots,A_{K}\\}$ in a
matrix group $G$. Denote by $\mathcal{G}_{inv}$ the invertible subset of
$\mathcal{G}$.

  1. (i)

The Identity Problem for $\mathcal{G}$ has a positive answer if and only if
$\mathcal{G}_{inv}$ is non-empty.

  2. (ii)

The Group Problem for $\mathcal{G}$ has a positive answer if and only if
$\mathcal{G}_{inv}=\mathcal{G}$.

#### Nilpotent groups, unitriangular matrices, and related work.

Computation on matrix groups becomes easier in the presence of structural
restrictions such as commutativity and nilpotence. In [2], Babai et al.
famously reduced algorithmic problems in _commutative_ matrix groups to
computation on _lattices_. Thus, for commutative matrix groups, Group
Membership reduces to linear algebra over $\mathbb{Z}$, and is hence decidable
in PTIME; Semigroup Membership is equivalent to integer programming, and is
hence NP-complete; the Identity Problem and the Group Problem reduce to
solving _homogeneous_ linear Diophantine equations, and are hence in PTIME.
The work of Babai left as an open problem how these complexity results
generalize to nilpotent groups and solvable groups. In this paper we work in
the setting of nilpotent groups.

######  Definition 1.3.

Given a group $G$ and a subgroup $H$ of $G$, define the commutator $[G,H]$ to
be the group generated by the elements in $\\{ghg^{-1}h^{-1}\mid g\in G,h\in
H\\}$. The _lower central series_ of a group $G$ is the inductively defined
descending sequence of subgroups

$G=G_{1}\geq G_{2}\geq G_{3}\geq\cdots,$

in which $G_{k}=[G,G_{k-1}]$. A group $G$ is called _nilpotent_ if its lower
central series terminates with $G_{d+1}=\\{I\\}$ for some $d$. The smallest
such $d$ is called the _nilpotency class_ of $G$.

In particular, abelian groups are nilpotent of class one. Nilpotent groups are
one of the most studied classes of groups due to being the “simplest” non-
commutative groups. Much research has focused on algorithms for groups of
relatively small nilpotency classes. For finite groups, the decades-old quest
for a PTIME algorithm of the group isomorphism problem has focused on the very
difficult case of class two nilpotent groups [3, 20, 39]. For infinite groups,
a celebrated result of Grunewald and Segal [22] showed decidability of group
isomorphism for all finitely generated nilpotent groups. For membership
problems, a classic result of Kopytov showed that Group Membership is
decidable in nilpotent matrix groups [29]. On the other hand, Roman’kov [38]
recently showed that Semigroup Membership is undecidable for a class two
nilpotent matrix group. The decidability and complexity of the Identity
Problem and the Group Problem for nilpotent groups remained an intricate open
problem.

The most prominent example of nilpotent groups is the group
$\mathsf{UT}(n,\mathbb{Q})$ of $n\times n$ unitriangular rational matrices.

######  Definition 1.4.

Denote by $\mathsf{UT}(n,\mathbb{Q})$ the group of $n\times n$ upper
triangular rational matrices with ones along the diagonal:

$\mathsf{UT}(n,\mathbb{Q})\coloneqq\left\\{\begin{pmatrix}1&*&\cdots&*\\\
0&1&\cdots&*\\\ \vdots&\vdots&\ddots&\vdots\\\ 0&0&\cdots&1\\\
\end{pmatrix},\text{ where $*$ are elements of $\mathbb{Q}$ }.\right\\}$

A group $G$ is called a _unitriangular matrix group over $\mathbb{Q}$_ if it
is a subgroup of $\mathsf{UT}(n,\mathbb{Q})$ for some $n$.

The group $\mathsf{UT}(n,\mathbb{Q})$ is nilpotent of class $n-1$ [26, Example
16.1.2]. A strong motivation for studying $\mathsf{UT}(n,\mathbb{Q})$ is the
fact that every finitely generated nilpotent group is isomorphic to a subgroup
of the direct product $\mathsf{UT}(n,\mathbb{Q})\times F$ where $F$ is finite
[5, 26]. For this reason, it suffices to focus our study on unitriangular
matrix groups over $\mathbb{Q}$.

In [28], Ko, Niskanen and Potapov showed the PTIME decidability of the
Identity Problem in $\mathsf{UT}(3,\mathbb{Q})$. Later, utilising the special
structure of the first term in the _Baker-Campbell-Hausdorff (BCH) formula_ ,
Colcombet, Ouaknine, Semukhin and Worrell proved the decidability of Semigroup
Membership in $\mathsf{UT}(3,\mathbb{Q})$ by encoding it into a Parikh
automaton [14]. Recently, Dong [17] showed the PTIME decidability of the
Identity Problem in $\mathsf{UT}(4,\mathbb{Z})$. However, Dong’s result relies
on an _ad hoc_ argument from algebraic geometry, which seems unlikely to
generalize to higher dimensions. It was therefore left as an open problem
whether the Identity Problem in $\mathsf{UT}(n,\mathbb{Q})$ is decidable for
$n\geq 5$. On the undecidability side, Roman’kov [38] showed that Semigroup
Membership in $\mathsf{UT}(3,\mathbb{Q})^{k}$ (which is of nilpotency class
two) is undecidable for sufficiently large $k$. His main technique is an
embedding of the Hilbert’s tenth problem. In this paper, we generalize some of
the above decidability results to unitriangular matrix groups of arbitrary
_dimension_ , with bounded _nilpotency class_.

#### Main contribution.

The highlight of our approach is combining convex geometry and Lie algebra to
study semigroup algorithmic problems, which to the best of our knowledge is a
new method in this area. Convex geometry can be seen as the study of
subsemigroups of the _abelian_ group $\mathbb{R}^{n}$. Combined with Lie
algebra techniques, we use it to study subsemigroups of _nilpotent_ groups.
The most significant contribution of our paper includes proving several
intricate properties of the $k$-th term of the _BCH formula_ , from which our
main result follows. All but one of these properties are proven for every term
of the BCH formula, whereas the remaining one is verified term by term using
assistance from computer algebra software. The huge computational power needed
to verify this particular property is the reason why our result stops at
nilpotency class ten222Nilpotent groups of high classes have intrinsically
complicated structures. Many conjectured results on nilpotent groups and
$\mathsf{UT}(n,\mathbb{K})$ are notoriously difficult to prove, but are
verified for relatively small nilpotency classes. For example, classification
of nilpotent Lie algebras is done up to dimension seven [21], and Higman’s
conjecture [41] on the number of conjugacy classes in
$\mathsf{UT}(n,\mathbb{F}_{p})$ is verified up to $n\leq 13$. . However, we
exhibit an effective procedure that verifies this property for higher classes
in case it is true.

##  2 Main results

The main result of this paper is the following theorem.

######  Theorem 2.1.

Let $G$ be a unitriangular matrix group over $\mathbb{Q}$ with nilpotency
class at most ten. Given any finite set $\mathcal{G}\subseteq G$, the
invertible subset of $\mathcal{G}$ is computable in polynomial time.

Here, the input size is defined as the total bit length of the entries in the
matrices of $\mathcal{G}$. The proof of Theorem 2.1 will be given in Sections
4 and 5. Together with Proposition 1.2, Theorem 2.1 implies that the Identity
Problem and the Group Problem are decidable in PTIME in unitriangular matrix
groups over $\mathbb{Q}$ with nilpotency class at most ten. For example, this
result also applies to the direct product $\mathsf{UT}(11,\mathbb{K})^{m}$ for
any $m\in\mathbb{N}$ and any algebraic number field $\mathbb{K}$, since
$\mathbb{K}$ can be embedded as matrices in $\mathbb{Q}^{k\times k}$, where
$k$ is the degree of the field extension $\mathbb{K}/\mathbb{Q}$.

The following corollary extends Theorem 2.1 to arbitrary finitely generated
nilpotent groups. However, the complexity will depend on specific group
embeddings, which we do not analyse.

######  Corollary 2.2.

Let $G$ be a finitely generated nilpotent group of class at most ten, given by
a finite presentation [24, Chap. 8]. Then the Identity Problem and the Group
Problem are decidable in $G$.

##  3 Preliminaries

#### Words and linear programming.

All omitted proofs can be found in Appendix A. Given a finite set of matrix
$\mathcal{G}=\\{A_{1},\ldots,A_{K}\\}$, one can consider $\mathcal{G}$ as a
finite alphabet. Let $\mathcal{G}^{*}$ denote the set of words over
$\mathcal{G}$, and let $\mathcal{G}^{+}$ denote the set of _non-empty_ words
over $\mathcal{G}$. Given a word $w\in\mathcal{G}^{+}$, by multiplying
consecutively the matrices appearing in $w$, we can evaluate $w$ as a matrix,
which we denote by $\pi(w)$. Then the semigroup $\langle\mathcal{G}\rangle$
consists of all matrices $\pi(w)$ where $w\in\mathcal{G}^{+}$. We now define
some concepts necessary for analysing words with linear algebra.

######  Definition 3.1 (Parikh image).

Given a finite alphabet $\mathcal{G}=\\{A_{1},\ldots,A_{K}\\}$, the _Parikh
image_ of a word $w=B_{1}\cdots B_{m}$ in $\mathcal{G}^{*}$ is the vector
$\boldsymbol{\ell}=(\ell_{1},\ldots,\ell_{K})\in\mathbb{Z}_{\geq 0}^{K}$
defined by $\ell_{i}=\operatorname{card}(\\{j\mid B_{j}=A_{i}\\})$ (that is,
$\ell_{i}$ is the number of times $A_{i}$ appears in $w$). The Parikh image of
$w$ over the alphabet $\mathcal{G}$ is denoted by
$\operatorname{PI}^{\mathcal{G}}(w)$.

######  Definition 3.2 (Cones).

Let $V$ be a $\mathbb{Q}$-linear space. A subset $\mathcal{C}\subseteq V$ is
called a _$\mathbb{Q}_{\geq 0}$ -cone_ if $a\in\mathcal{C}\Longrightarrow
a\mathbb{Q}_{\geq 0}\subseteq\mathcal{C}$, and
$a,b\in\mathcal{C}\Longrightarrow a+b\in\mathcal{C}$. Given a set of vectors
$\mathcal{S}\subseteq V$, denote by
$\langle\mathcal{S}\rangle_{\mathbb{Q}_{\geq 0}}$ the _$\mathbb{Q}_{\geq 0}$
-cone generated by $\mathcal{S}$_, that is the smallest $\mathbb{Q}_{\geq
0}$-cone of $V$ containing $\mathcal{S}$. Similarly, denote by
$\langle\mathcal{S}\rangle_{\mathbb{Q}}$ the $\mathbb{Q}$-linear space
generated by $\mathcal{S}$. These notations extend to $\mathbb{R}_{\geq
0}$-cones and $\mathbb{R}$-linear spaces.

######  Definition 3.3 (Support).

A subset $\Lambda\subseteq\mathbb{Z}_{\geq 0}^{K}$ is called a
_$\mathbb{Z}_{\geq 0}$ -cone_ if $a,b\in\Lambda\Longrightarrow a+b\in\Lambda$,
and $\boldsymbol{0}\in\Lambda$. The _support_ of a vector
$\boldsymbol{\ell}=(\ell_{1},\ldots,\ell_{K})\in\mathbb{Z}_{\geq 0}^{K}$ is
defined as the set of indices where the entry of $\boldsymbol{\ell}$ is non-
zero:

$\operatorname{supp}(\boldsymbol{\ell})\coloneqq\\{i\in\\{1,\ldots,K\\}\mid\ell_{i}>0\\}.$

The _support_ of a $\mathbb{Z}_{\geq 0}$-cone $\Lambda$ is defined as the
union of supports of all vectors in $\Lambda$:

$\operatorname{supp}(\Lambda)\coloneqq\bigcup\nolimits_{\boldsymbol{\ell}\in\Lambda}\operatorname{supp}(\boldsymbol{\ell})=\\{i\mid\exists(\ell_{1},\ldots,\ell_{K})\in\Lambda,\ell_{i}>0\\}.$

Let $V$ be a $\mathbb{Q}$-linear subspace of $\mathbb{Q}^{K}$, represented as
the solution set of linear homogeneous equations. Then $\mathbb{Z}_{\geq
0}^{K}\cap V$ is a $\mathbb{Z}_{\geq 0}$-cone. In this paper, we will need to
compute the support of $\mathbb{Z}_{\geq 0}$-cones of the form
$\Lambda=\mathbb{Z}_{\geq 0}^{K}\cap V$ (namely, in Algorithm 1).

######  Lemma 3.4.

Given $V$ represented as the solution set of linear homogeneous equations, one
can compute the support of $\Lambda=\mathbb{Z}_{\geq 0}^{K}\cap V$ in
polynomial time.

#### Lie algebra.

For a general reference on Lie algebra, see [19].

######  Definition 3.5 (Lie algebra $\mathfrak{u}(n)$).

The _Lie algebra_ $\mathfrak{u}(n)$ is defined as the $\mathbb{Q}$-linear
space of $n\times n$ upper triangular rational matrices with _zeros_ on the
diagonal. There exist maps

$\log:\mathsf{UT}(n,\mathbb{Q})\rightarrow\mathfrak{u}(n),\quad
A\mapsto\sum_{k=1}^{n}\frac{(-1)^{k-1}}{k}(A-I)^{k},$

and

$\exp:\mathfrak{u}(n)\rightarrow\mathsf{UT}(n,\mathbb{Q}),\quad
X\mapsto\sum_{k=0}^{n}\frac{1}{k!}X^{k},$

which are inverse of one another. In particular, $\log I=0$ and $\exp(0)=I$.

The Lie algebra $\mathfrak{u}(n)$ is equipped with a _Lie bracket_
$[\cdot,\cdot]:\mathfrak{u}(n)\times\mathfrak{u}(n)\rightarrow\mathfrak{u}(n)$
given by $[X,Y]=XY-YX$. The Lie bracket is bilinear, anticommutative (meaning
$[X,Y]=-[Y,X]$), and it additionally satisfies the _Jacobi Identity_ :

$[X,[Y,Z]]+[Y,[Z,X]]+[Z,[X,Y]]=0\text{ for all }X,Y,Z\in\mathfrak{u}(n).$

######  Notation 3.6.

Given a set of matrices $\mathcal{G}\subseteq\mathsf{UT}(n,\mathbb{Q})$, we
denote $\log\mathcal{G}\coloneqq\\{\log A\mid A\in\mathcal{G}\\}$. It is a
subset of $\mathfrak{u}(n)$. If $G$ is a subgroup of
$\mathsf{UT}(n,\mathbb{Q})$, then $\log G$ is similarly defined by considering
$G$ as a set. Given a set of elements $\mathcal{H}\subseteq\mathfrak{u}(n)$
and an integer $k\geq 2$, define

$[\mathcal{H}]_{k}\coloneqq\big{\\{}[\ldots[[X_{1},X_{2}],X_{3}],\ldots,X_{k}]\mid
X_{1},X_{2},\ldots,X_{k}\in\mathcal{H}\big{\\}}.$

That is, $[\mathcal{H}]_{k}$ is the set of all “left bracketing” of length $k$
of elements in $\mathcal{H}$.

It is a standard result that, using bilinearity, anticommutativity and the
Jacobi identity, any $k$-iteration of Lie brackets of elements in
$\mathcal{H}$ can be written as a linear combination of elements in
$[\mathcal{H}]_{k}$. For example, for $k=4$, one can write

$\displaystyle[[X_{1},X_{2}],[X_{3},X_{4}]]=$
$\displaystyle-[[X_{2},[X_{3},X_{4}]],X_{1}]-[[[X_{3},X_{4}],X_{1}],X_{2}]\quad\text{(Jacobi
identity)}$ $\displaystyle=$
$\displaystyle\;[[[X_{3},X_{4}],X_{2}],X_{1}]-[[[X_{3},X_{4}],X_{1}],X_{2}]\quad\text{(Anticommutativity)}.$

The following lemma is a corollary of the so-called _Mal’cev correspondence_
[34]:

######  Lemma 3.7.

Let $G$ be a subgroup of $\mathsf{UT}(n,\mathbb{Q})$. If $G$ has nilpotency
class $d$, then $[\log G]_{d+1}=\\{0\\}$.

#### The Baker-Campbell-Hausdorff (BCH) formula.

######  Theorem 3.8 (Baker-Campbell-Hausdorff (BCH) formula [4, 11, 23]).

Let $G$ be a unitriangular matrix group over $\mathbb{Q}$, whose nilpotency
class is at most $d$. Let $B_{1},\ldots,B_{m}$ be elements of $G$. Then

$\log(B_{1}B_{2}\cdots B_{m})=\sum_{i=1}^{m}\log
B_{i}+\sum_{k=2}^{d}H_{k}(\log B_{1},\ldots,\log B_{m}),$ (1)

where the terms $H_{k}(\log B_{1},\ldots,\log B_{m}),k=2,3,\ldots$, can be
expressed as finite $\mathbb{Q}$-linear combinations of elements in $[\\{\log
B_{1},\ldots,\log B_{m}\\}]_{k}$.

In theory, one can compute the expressions $H_{k}$ effectively using recursion
(see, for example [12]). An explicit expression for the term $H_{k}$ was
discovered by Dynkin [31] (see Section 5). However, as $k$ grows, these
expressions quickly become very complicated. For example, here are the
explicit expressions of the first two terms.

$\displaystyle H_{2}(C_{1},\ldots,C_{m})$
$\displaystyle=\frac{1}{2}\sum_{i<j}[C_{i},C_{j}],$ $\displaystyle
H_{3}(C_{1},\ldots,C_{m})$
$\displaystyle=\sum_{i<j<k}\left(\frac{[C_{i},[C_{j},C_{k}]]}{3}+\frac{[[C_{i},C_{k}],C_{j}]}{6}\right)+\sum_{i<j}\frac{[C_{i},[C_{i},C_{j}]]+[[C_{i},C_{j}],C_{j}]}{12}.$
(2)

##  4 Polynomial time algorithm for Theorem 2.1

In this section, we exhibit the algorithm that proves the main result of this
paper (Theorem 2.1). In order to describe our algorithm, we need to introduce
the following notation. Let $\mathcal{H}$ be a finite set of elements in the
Lie algebra $\mathfrak{u}(n)$. For any $k\geq 1$, denote

$\mathfrak{L}_{\geq
k}(\mathcal{H})\coloneqq\left\langle\bigcup\nolimits_{i\geq
k}[\mathcal{H}]_{i}\right\rangle_{\mathbb{Q}}.$

That is, $\mathfrak{L}_{\geq k}(\mathcal{H})$ is the linear space spanned by
the set of all “left bracketing” of length _at least_ $k$ of elements in
$\mathcal{H}$. By Lemma 3.7, if a unitriangular matrix group $G$ has
nilpotency class $d$, then for any $\mathcal{H}\subseteq\log G$, we have
$\mathfrak{L}_{\geq d+1}(\mathcal{H})=\\{0\\}$, and $\mathfrak{L}_{\geq
k}(\mathcal{H})=\langle[\mathcal{H}]_{k}\rangle_{\mathbb{Q}}+\langle[\mathcal{H}]_{k+1}\rangle_{\mathbb{Q}}+\cdots+\langle[\mathcal{H}]_{d}\rangle_{\mathbb{Q}}$.
We have thus an ascending series of linear spaces $\\{0\\}=\mathfrak{L}_{\geq
d+1}(\mathcal{H})\subseteq\mathfrak{L}_{\geq
d}(\mathcal{H})\subseteq\cdots\subseteq\mathfrak{L}_{\geq
1}(\mathcal{H})\subseteq\mathfrak{u}(n)$, such that $[\mathfrak{L}_{\geq
i}(\mathcal{H}),\mathfrak{L}_{\geq j}(\mathcal{H})]\subseteq\mathfrak{L}_{\geq
i+j}(\mathcal{H})$.

######  Example 4.1 (label=exa:cont).

We give a concrete example to show how the subspaces $\mathfrak{L}_{\geq
k}(\mathcal{H}),k=d,\ldots,2,1,$ may look like. Let
$G=\mathsf{UT}(4,\mathbb{Q})$, so it has nilpotency class $d=3$. Consider the
Lie algebra

$\mathfrak{u}(4)=\left\\{\begin{pmatrix}0&*&*&*\\\ 0&0&*&*\\\ 0&0&0&*\\\
0&0&0&0\\\ \end{pmatrix},\text{ where $*$ are entries in
$\mathbb{Q}$}\right\\}.$

It is a $\mathbb{Q}$-linear space of dimension six. Let
$\mathcal{G}=\\{A_{1},A_{2},A_{3}\\}$, where

$A_{1}=\begin{pmatrix}1&2&-1&1\\\ 0&1&2&1\\\ 0&0&1&2\\\ 0&0&0&1\\\
\end{pmatrix},A_{2}=\begin{pmatrix}1&-1&-1&2\\\ 0&1&-1&-1\\\ 0&0&1&0\\\
0&0&0&1\\\ \end{pmatrix},A_{3}=\begin{pmatrix}1&0&3&-1\\\ 0&1&0&1\\\
0&0&1&-1\\\ 0&0&0&1\\\ \end{pmatrix}.$

Let $\mathcal{H}=\\{\log A_{1},\log A_{2},\log A_{3}\\}$. In particular,

$\log A_{1}=\begin{pmatrix}0&2&-3&\frac{11}{3}\\\ 0&0&2&-1\\\ 0&0&0&2\\\
0&0&0&0\\\ \end{pmatrix},\log
A_{2}=\begin{pmatrix}0&-1&-\frac{3}{2}&\frac{3}{2}\\\ 0&0&-1&-1\\\ 0&0&0&0\\\
0&0&0&0\\\ \end{pmatrix},\log A_{3}=\begin{pmatrix}0&0&3&\frac{1}{2}\\\
0&0&0&1\\\ 0&0&0&-1\\\ 0&0&0&0\\\ \end{pmatrix}.$ (3)

We have $[\mathcal{H}]_{4}=\\{0\\}$ by applying Lemma 3.7 with $d=3$.
Moreover,

$\displaystyle[\mathcal{H}]_{3}$ $\displaystyle=\big{\\{}[[\log A_{1},\log
A_{2}],\log A_{1}],[[\log A_{1},\log A_{2}],\log A_{2}],\ldots,[[\log
A_{3},\log A_{2}],\log A_{2}]\big{\\}},$ $\displaystyle[\mathcal{H}]_{2}$
$\displaystyle=\big{\\{}[\log A_{1},\log A_{2}],[\log A_{1},\log A_{3}],[\log
A_{2},\log A_{3}],[\log A_{2},\log A_{1}]=-[\log A_{1},\log
A_{2}],\ldots\big{\\}},$ $\displaystyle[\mathcal{H}]_{1}$
$\displaystyle=\big{\\{}\log A_{1},\log A_{2},\log A_{3}\big{\\}}.$

Then, we have $\mathfrak{L}_{\geq 4}(\mathcal{H})=\\{0\\}$,
$\mathfrak{L}_{\geq
3}(\mathcal{H})=\langle[\mathcal{H}]_{3}\rangle_{\mathbb{Q}}$,
$\mathfrak{L}_{\geq
2}(\mathcal{H})=\langle[\mathcal{H}]_{2}\rangle_{\mathbb{Q}}+\langle[\mathcal{H}]_{3}\rangle_{\mathbb{Q}}$
and $\mathfrak{L}_{\geq
1}(\mathcal{H})=\langle[\mathcal{H}]_{1}\rangle_{\mathbb{Q}}+\langle[\mathcal{H}]_{2}\rangle_{\mathbb{Q}}+\langle[\mathcal{H}]_{3}\rangle_{\mathbb{Q}}$.
By direct computation, this yields

$\mathfrak{L}_{\geq 3}(\mathcal{H})=\left\\{\begin{pmatrix}0&0&0&a\\\
0&0&0&0\\\ 0&0&0&0\\\ 0&0&0&0\\\
\end{pmatrix}\;\middle|\;a\in\mathbb{Q}\right\\},\mathfrak{L}_{\geq
2}(\mathcal{H})=\left\\{\begin{pmatrix}0&0&0&a\\\ 0&0&0&b\\\ 0&0&0&0\\\
0&0&0&0\\\ \end{pmatrix}\;\middle|\;a,b\in\mathbb{Q}\right\\},\\\
\mathfrak{L}_{\geq 1}(\mathcal{H})=\left\\{\begin{pmatrix}0&c_{1}&c_{3}&a\\\
0&0&c_{1}&b\\\ 0&0&0&c_{2}\\\ 0&0&0&0\\\
\end{pmatrix}\;\middle|\;a,b,c_{1},c_{2},c_{3}\in\mathbb{Q}\right\\}.$ (4)

Hence in this example, $\mathfrak{L}_{\geq 3}(\mathcal{H}),\mathfrak{L}_{\geq
2}(\mathcal{H}),\mathfrak{L}_{\geq 1}(\mathcal{H})$ are respectively subspaces
of $\mathfrak{u}(4)$ of dimension one, two and five.

Let $G$ be a subgroup of $\mathsf{UT}(n,\mathbb{Q})$ of nilpotency class at
most ten, and fix $\mathcal{G}=\\{A_{1},\ldots,A_{K}\\}$ to be a finite
alphabet of elements in $G$. For any vector
$\boldsymbol{\ell}=(\ell_{1},\ldots,\ell_{K})\in\mathbb{Z}_{\geq 0}^{K}$,
define

$\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}\coloneqq\\{A_{i}\mid
A_{i}\in\mathcal{G},i\in\operatorname{supp}(\boldsymbol{\ell})\\}$

as the set of matrices in $\mathcal{G}$ whose index appears in the support set
$\operatorname{supp}(\boldsymbol{\ell})$.

Recall that for a word $w\in\mathcal{G}^{+}$, the matrix $\pi(w)$ is obtained
by multiplying consecutively the matrices appearing in $w$. The key ingredient
of our algorithm is the following Theorem 4.2, which provides a criterion for
the existence of a non-empty word $w\in\mathcal{G}^{+}$ satisfying
$\log\pi(w)=0$ (equivalently, $\pi(w)=I$). In particular, this provides a
criterion for whether $I\in\langle\mathcal{G}\rangle$ (the Identity Problem),
and can be extended to the computation of invertible subsets.

######  Theorem 4.2.

Let $\mathcal{G}=\\{A_{1},\ldots,A_{K}\\}$ be a finite set of matrices in
$\mathsf{UT}(n,\mathbb{Q})$ that satisfies $[\log\mathcal{G}]_{11}=\\{0\\}$.
Given a non-zero vector
$\boldsymbol{\ell}=(\ell_{1},\ldots,\ell_{K})\in\mathbb{Z}_{\geq 0}^{K}$:

  1. (i)

If there exists a word $w\in\mathcal{G}^{+}$ with
$\operatorname{PI}^{\mathcal{G}}(w)=\boldsymbol{\ell}$ and $\log\pi(w)=0$,
then

$\sum_{i=1}^{K}\ell_{i}\log A_{i}\in\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}).$ (5)

  2. (ii)

If $\boldsymbol{\ell}$ satisfies (5), then there exists a word
$w\in\mathcal{G}^{+}$ with
$\operatorname{PI}^{\mathcal{G}}(w)\in\mathbb{Z}_{>0}\cdot\boldsymbol{\ell}$,
such that $\log\pi(w)=0$.

Part (i) of Theorem 4.2 is relatively easy to prove:

###### Proof of part (i) of Theorem 4.2.

Let $w$ be a word with $\operatorname{PI}^{\mathcal{G}}(w)=\boldsymbol{\ell}$.
Write $w=B_{1}B_{2}\cdots B_{m}$ where $B_{i}\in\mathcal{G},i=1,\ldots,m$.
Regrouping by letters, we have $\sum_{i=1}^{K}\ell_{i}\log
A_{i}=\sum_{i=1}^{m}\log B_{i}$.

If $\log\pi(w)=0$, then by the BCH formula (Theorem 3.8), we have

$\sum_{i=1}^{m}\log B_{i}+\sum_{k=2}^{n-1}H_{k}(\log B_{1},\ldots,\log
B_{m})=\log(B_{1}B_{2}\cdots B_{m})=0.$

The higher order terms $H_{k},k\geq n$ vanish because
$[\log\mathcal{G}]_{n}=\\{0\\}$ (a consequence of
$\mathcal{G}\subseteq\mathsf{UT}(n,\mathbb{Q})$). Therefore,
$\sum_{i=1}^{K}\ell_{i}\log A_{i}=\sum_{i=1}^{m}\log
B_{i}=-\sum_{k=2}^{n-1}H_{k}(\log B_{1},\ldots,\log B_{m})$.

Since the Parikh image of the word $B_{1}B_{2}\cdots B_{m}$ is
$\boldsymbol{\ell}$, the matrices $B_{i}$ all lie in the subset $\\{A_{i}\mid
i\in\operatorname{supp}(\boldsymbol{\ell})\\}$ of $\mathcal{G}$. Therefore,
$\log B_{i}\in\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}$ for
all $i$. By Theorem 3.8, for all $k\geq 2$ we have $-H_{k}(\log
B_{1},\ldots,\log B_{m})\in\big{\langle}[\\{\log B_{i}\mid
i=1,\ldots,m\\}]_{k}\big{\rangle}_{\mathbb{Q}}\subseteq\mathfrak{L}_{\geq
k}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})\subseteq\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})$. Therefore, we
have $\sum_{i=1}^{K}\ell_{i}\log A_{i}=-\sum_{k=2}^{n-1}H_{k}(\log
B_{1},\ldots,\log B_{m})\in\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}).$ ∎

Proving part (ii) of Theorem 4.2 is highly non-trivial and will be the main
focus of Section 5. We continue Example 4.1 to give an intuition of the
Condition (5) in Theorem 4.2.

######  Example 4.3 (continues=exa:cont).

Let $\mathcal{G}$ be as in Example 4.1. As an example, we show that
$\boldsymbol{\ell}=(1,2,2)$ satisfies Equation (5). When
$\boldsymbol{\ell}=(1,2,2)$, we have
$\operatorname{supp}(\boldsymbol{\ell})=\\{1,2,3\\}$, so $\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})=\mathfrak{L}_{\geq
2}(\log\mathcal{G})$ as defined in Equation (4). Therefore,

$\sum_{i=1}^{3}\ell_{i}\log A_{i}=\log A_{1}+2\log A_{2}+2\log
A_{3}=\begin{pmatrix}0&0&0&\frac{23}{3}\\\ 0&0&0&-1\\\ 0&0&0&0\\\ 0&0&0&0\\\
\end{pmatrix}\in\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}),$

where $\log A_{i},i=1,2,3,$ are given in Equation (3). Hence in this example,
$\boldsymbol{\ell}$ satisfies Equation (5).

Note that finding solutions of Equation (5) relies only on linear algebra.
Assuming Theorem 4.2, we can devise the following Algorithm 1 that computes
the invertible subset of any finite set $\mathcal{G}\subseteq G$.

Input:

A finite set of elements $\mathcal{G}=\\{A_{1},\ldots,A_{K}\\}$ in $G$.

Output:

The invertible subset $\mathcal{G}_{inv}$ of $\mathcal{G}$.

  1. Step 1

Initialization. Set $S\coloneqq\\{1,\ldots,K\\}$.

  2. Step 2

Main loop. Repeat the following

    1. (a)

Represent the $\mathbb{Q}$-linear subspace of $\mathbb{Q}^{K}$:

$V\coloneqq\left\\{(\ell_{1},\ldots,\ell_{K})\in\mathbb{Q}^{K}\middle|\sum\nolimits_{i=1}^{K}\ell_{i}\log
A_{i}\in\mathfrak{L}_{\geq 2}(\\{\log A_{i}\mid i\in S\\})\right\\}$

as the solution set of homogeneous linear equations.

    2. (b)

Define $\Lambda\coloneqq\mathbb{Z}_{\geq 0}^{K}\cap V$ and compute
$\operatorname{supp}(\Lambda)$ using Lemma 3.4.

    3. (c)

If $\operatorname{supp}(\Lambda)=S$, terminate the algorithm and return
$\mathcal{G}_{inv}=\\{A_{i}\mid i\in S\\}$.

Otherwise let $S\coloneqq\operatorname{supp}(\Lambda)$ and continue.

Algorithm 1 Computing the invertible subset of $\mathcal{G}$

###### Proof of Theorem 2.1 and proof of correctness of Algorithm 1 (assuming
Theorem 4.2).

After each iteration of Step 2, the cardinality of
$\operatorname{supp}(\Lambda)$ strictly decreases. Therefore, the algorithm
terminates after at most $K$ iterations of Step 2.

Since $G$ has nilpotency class at most ten, by Lemma 3.7, its subset
$\mathcal{G}$ satisfies $[\log\mathcal{G}]_{11}=\\{0\\}$. We start by showing
that, when the algorithm terminates, every element of $\\{A_{i}\mid i\in S\\}$
has an inverse in the semigroup $\langle\mathcal{G}\rangle$. When the
algorithm terminates at Step 2(c), we have $\operatorname{supp}(\Lambda)=S$.
By the additivity of $\Lambda$ (that is,
$\boldsymbol{a},\boldsymbol{b}\in\Lambda\implies\boldsymbol{a}+\boldsymbol{b}\in\Lambda$),
there exists a vector $\boldsymbol{\ell}=(\ell_{1},\ldots,\ell_{K})\in\Lambda$
such that
$\operatorname{supp}(\boldsymbol{\ell})=\operatorname{supp}(\Lambda)=S$. This
vector then satisfies $\sum_{i=1}^{K}\ell_{i}\log A_{i}\in\mathfrak{L}_{\geq
2}(\\{\log A_{i}\mid i\in\operatorname{supp}(\boldsymbol{\ell})\\})$ by the
definition of $V$. By Theorem 4.2(ii), this shows that there exists a non-
empty word $w$, with
$\operatorname{PI}^{\mathcal{G}}(w)\in\mathbb{Z}_{>0}\cdot\boldsymbol{\ell}$
such that $\log\pi(w)=0$ (that is, $\pi(w)=I$). For any $i\in S$, since
$\operatorname{supp}(\boldsymbol{\ell})=S$, the letter $A_{i}$ appears in the
word $w$. Write $w=w_{1}A_{i}w_{2}$; then since $\pi(w_{1}A_{i}w_{2})=I$, we
have $\pi(w_{1})A_{i}\pi(w_{2})=I$. Hence,
$A_{i}^{-1}=\pi(w_{2})\pi(w_{1})\in\langle\mathcal{G}\rangle\cup\\{I\\}$, so
$A_{i}^{-1}\in\langle\mathcal{G}\rangle$.

We then show that for every matrix $A_{i}$ invertible in
$\langle\mathcal{G}\rangle$, the index $i$ is in the set $S$ at the
termination of the algorithm. Suppose $A_{i}^{-1}$ is equal to $\pi(w)$, where
$w$ is a non-empty word. Then the product of the word $w^{\prime}=wA_{i}$ is
equal to the identity, that is, $\log\pi(w^{\prime})=0$. By Theorem 4.2(i),
the Parikh image
$\boldsymbol{\ell}=\operatorname{PI}^{\mathcal{G}}(w^{\prime})$ satisfies
$\sum_{i=1}^{K}\ell_{i}\log A_{i}\in\mathfrak{L}_{\geq 2}(\\{\log A_{i}\mid
i\in\operatorname{supp}(\boldsymbol{\ell})\\}).$

We show that $\operatorname{supp}(\boldsymbol{\ell})\subseteq S$ is an
invariant of the algorithm. At initialization, we obviously have
$\operatorname{supp}(\boldsymbol{\ell})\subseteq S$. Before each iteration of
Step 2(b), suppose we have $\operatorname{supp}(\boldsymbol{\ell})\subseteq
S$, then

$\sum_{i=1}^{K}\ell_{i}\log A_{i}\in\mathfrak{L}_{\geq 2}(\\{\log A_{i}\mid
i\in\operatorname{supp}(\boldsymbol{\ell})\\})\subseteq\mathfrak{L}_{\geq
2}(\\{\log A_{i}\mid i\in S\\}).$

Hence $\boldsymbol{\ell}\in\Lambda=\mathbb{Z}_{\geq 0}^{K}\cap V$.
Consequently,
$\operatorname{supp}(\boldsymbol{\ell})\subseteq\operatorname{supp}(\Lambda)$
at the beginning of Step 2(c), which shows that
$\operatorname{supp}(\boldsymbol{\ell})\subseteq S$ still holds after the
iteration of Step 2. This invariant shows that
$i\in\operatorname{supp}(\boldsymbol{\ell})\subseteq S$ by the end of the
algorithm. Combining with the previous implication, we conclude that by the
end of the algorithm, $S$ is exactly the set of elements in $\mathcal{G}$ with
inverse in $\langle\mathcal{G}\rangle$.

For the complexity analysis, recall that the algorithm terminates after at
most $K$ iterations of Step 2. At each iteration of Step 2(b), the support
$\operatorname{supp}(\Lambda)$ can be computed in polynomial time by Lemma
3.4. The total input size of these linear programming instances is polynomial
with respect to the total bit length of the matrix entries in $\mathcal{G}$.
Indeed, a $\mathbb{Q}$-basis of $\mathfrak{L}_{\geq 2}(\\{\log A_{i}\mid i\in
S\\})$ is simply the set $\bigcup_{10\geq k\geq 2}[\\{\log A_{i}\mid i\in
S\\}]_{k}$, whose total bit length is of polynomial size in $\mathcal{G}$.
From this, one can express $V$ as the solution set of a system of homogeneous
linear equations whose total bit length is polynomial in $\mathcal{G}$ (note
that the total bit length of $\log A_{i}$ is also polynomial in
$\mathcal{G}$). Therefore, the overall complexity of Algorithm 1 is polynomial
with respect to the input $\mathcal{G}$. ∎

##  5 Proof of Theorem 4.2(ii)

In this section we give the proof of Theorem 4.2(ii). We first give an
intuition of the proof by continuing Example 4.1. This will illustrate some of
the ideas necessary to prove the general case.

######  Example 5.1 (continues=exa:cont).

Let $\mathcal{G}$ be as in Example 4.1. Let $\boldsymbol{\ell}=(1,2,2)$. We
have already shown that $\boldsymbol{\ell}$ satisfies Equation (5), so Theorem
4.2(ii) claims that there exists a word $w\in\mathcal{G}^{+}$ with
$\operatorname{PI}^{\mathcal{G}}(w)\in\mathbb{Z}_{>0}\cdot(1,2,2)$, such that
$\log\pi(w)=0$. We illustrate here how to construct this word $w$ in two
steps. By slight abuse of notation we now write $\log A$ instead of
$\log\pi(A)$ for any word $A\in\mathcal{G}^{+}$.

Step 1. We find elements $A^{\prime}_{1},A^{\prime}_{2},A^{\prime}_{3}$ in
$\mathcal{G}^{+}$, such that $\log A^{\prime}_{1},\log A^{\prime}_{2},\log
A^{\prime}_{3}$ generate the subspace $\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})$ as a
_$\mathbb{Q}_{\geq 0}$ -cone_. The idea is to take

$A^{\prime}_{1}\coloneqq A_{1}^{t}A_{2}^{2t}A_{3}^{2t},\quad
A^{\prime}_{2}\coloneqq A_{2}^{2t}A_{3}^{2t}A_{1}^{t},\quad
A^{\prime}_{3}\coloneqq A_{2}^{2t}A_{1}^{t}A_{3}^{2t},$ (6)

for a suitable $t\in\mathbb{N}$. Apply the BCH formula (1) with
$B_{1}\coloneqq A_{1}^{t},B_{2}\coloneqq A_{2}^{2t},B_{3}\coloneqq
A_{3}^{2t}$, we obtain

$\log A^{\prime}_{1}=\log(A_{1}^{t}A_{2}^{2t}A_{3}^{2t})=\log A_{1}^{t}+\log
A_{2}^{2t}+\log A_{3}^{2t}+\sum\nolimits_{k=2}^{3}H_{k}(\log A_{1}^{t},\log
A_{2}^{2t},\log A_{3}^{2t})\\\ =t\cdot(\log A_{1}+2\log A_{2}+2\log
A_{3})+\sum\nolimits_{k=2}^{3}t^{k}\cdot H_{k}(\log A_{1},2\log A_{2},2\log
A_{3}).$ (7)

The last equality is due to $\log A^{t}=t\log A$ and because the term $H_{k}$
is a linear combination of $k$-iterations of Lie brackets.

The linear term $t\cdot(\log A_{1}+2\log A_{2}+2\log A_{3})$ in (7) falls in
the subspace $\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})$ by Condition
(5). The non-linear terms $t^{k}\cdot H_{k}(\log A_{1},2\log A_{2},2\log
A_{3}),k=2,3,$ also fall in the subspace $\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})$ by Theorem 3.8.
Therefore, we have $\log A^{\prime}_{1}\in\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})$. Similarly,
$\log A^{\prime}_{2}$ and $\log A^{\prime}_{3}$ are also in
$\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})$.

Using the exact expression (3) for the terms $H_{2}$ and $H_{3}$, we obtain
that the expressions for $\log A^{\prime}_{1},\log A^{\prime}_{2}$ and $\log
A^{\prime}_{3}$ are respectively

$\begin{pmatrix}0&0&0&\frac{4}{3}t^{3}+\frac{23}{3}t\\\ 0&0&0&2t^{2}-t\\\
0&0&0&0\\\ 0&0&0&0\\\
\end{pmatrix},\begin{pmatrix}0&0&0&-\frac{8}{3}t^{3}+2t^{2}+\frac{23}{3}t\\\
0&0&0&2t^{2}-t\\\ 0&0&0&0\\\ 0&0&0&0\\\ \end{pmatrix},\text{ and
}\begin{pmatrix}0&0&0&\frac{4}{3}t^{3}+\frac{23}{3}t\\\ 0&0&0&-2t^{2}-t\\\
0&0&0&0\\\ 0&0&0&0\\\ \end{pmatrix}.$

We then choose $t=10$. This choice is made so that $t$ is large enough for
$\log A^{\prime}_{1},\log A^{\prime}_{2},\log A^{\prime}_{3}$ to exhibit their
“asymptotic” behaviour. When $t=10$, we have

$\log A^{\prime}_{1}=\begin{pmatrix}0&0&0&1410\\\ 0&0&0&190\\\ 0&0&0&0\\\
0&0&0&0\\\ \end{pmatrix},\log A^{\prime}_{2}=\begin{pmatrix}0&0&0&-2390\\\
0&0&0&190\\\ 0&0&0&0\\\ 0&0&0&0\\\ \end{pmatrix},\log
A^{\prime}_{3}=\begin{pmatrix}0&0&0&1410\\\ 0&0&0&-210\\\ 0&0&0&0\\\
0&0&0&0\\\ \end{pmatrix}.$ (8)

Then indeed we have $\langle\log A^{\prime}_{1},\log A^{\prime}_{2},\log
A^{\prime}_{3}\rangle_{\mathbb{Q}_{\geq 0}}=\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})$, which is proved
by linear programming. Furthermore, the Parikh images are
$\operatorname{PI}^{\mathcal{G}}(A^{\prime}_{1})=\operatorname{PI}^{\mathcal{G}}(A^{\prime}_{2})=\operatorname{PI}^{\mathcal{G}}(A^{\prime}_{3})=(10,20,20)$.

Step 2. Consider the new alphabet
$\mathcal{G}^{\prime}\coloneqq\\{A^{\prime}_{1},A^{\prime}_{2},A^{\prime}_{3}\\}$.
We now find a non-empty word
$A^{\prime\prime}\in\left(\mathcal{G}^{\prime}\right)^{+}$, such that $\log
A^{\prime\prime}\in\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))=\\{0\\}$.
Directly computing from (8) yields

$117\cdot\log A^{\prime}_{1}+282\cdot\log A^{\prime}_{2}+361\cdot\log
A^{\prime}_{3}=0.$ (9)

Let
$A^{\prime\prime}\coloneqq\left(A^{\prime}_{1}\right)^{117}\cdot\left(A^{\prime}_{2}\right)^{282}\cdot\left(A^{\prime}_{3}\right)^{361}.$
By the BCH formula (1), we have $\log A^{\prime\prime}=117\cdot\log
A^{\prime}_{1}+282\cdot\log A^{\prime}_{2}+361\cdot\log A^{\prime}_{3}=0.$
This is because all the terms $H_{k},k\geq 2$ in the BCH formula are in

$\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))\subseteq\mathfrak{L}_{\geq
4}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})=\\{0\\}.$ (10)

Furthermore, the Parikh image of $A^{\prime\prime}$ is
$\operatorname{PI}^{\mathcal{G}}(A^{\prime\prime})=117\cdot\operatorname{PI}^{\mathcal{G}}(A^{\prime}_{1})+282\cdot\operatorname{PI}^{\mathcal{G}}(A^{\prime}_{2})+361\cdot\operatorname{PI}^{\mathcal{G}}(A^{\prime}_{3})=7600\cdot(1,2,2)$.
We have thus found the word $w=A^{\prime\prime}$ satisfying $\log\pi(w)=0$,
with Parikh image $7600\cdot(1,2,2)$. This concludes our example.

The following subsections aim to formalize the idea exhibited in this example
and provide a rigorous proof of Theorem 4.2(ii). Here is an overview of the
main difficulties in formalizing a proof.

  1. (i)

In Equation (6) we took a specific choice of
$A^{\prime}_{1},A^{\prime}_{2},A^{\prime}_{3}$. In the general case, we will
use a similar idea of taking $A^{\prime}_{i}$ to be words of the form
$A_{i_{1}}^{t}A_{i_{2}}^{t}\cdots A_{i_{m}}^{t}$. However, the permutations
$(i_{1},i_{2},\ldots,i_{m})$ need to be chosen carefully. We need to show that
there exist enough permutations so that the constructed elements $\log
A^{\prime}_{1},\log A^{\prime}_{2},\ldots,$ generate the linear space
$\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})$. We achieve this
by proving a deep combinatorial property of the terms $H_{k}$ (Proposition
5.2).

  2. (ii)

Furthermore, $\log A^{\prime}_{1},\log A^{\prime}_{2},\ldots,$ need to
generate $\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})$ as a _cone_. The
coefficients $(117,282,361)$ obtained in Equation (9) happen to be all
positive, but this is _a priori_ not always the case. We need to show that $0$
can always be written as a _positive_ combination of $\log A^{\prime}_{i}$.
This is proved by finding identities over the terms $H_{k}$ using computer
assistance (Proposition 5.3).

  3. (iii)

The exponent $t$ in Equation (6) needs to be chosen carefully. In fact, we may
even need to take several different $t$. Such $t$ are chosen using techniques
from convex geometry (Proposition 5.4).

  4. (iv)

In the above example the nilpotency class of $G$ is three. This is the reason
why in Step 2, Equation (10) holds, and the matrices
$A^{\prime}_{1},A^{\prime}_{2},A^{\prime}_{3}$ commute with each other. In the
general case, we deal with groups of nilpotency class up to ten. Then,
Equation (10) no longer holds. Hence, we need to repeat the above process for
more steps. In general, when $G$ has nilpotency class up to $2^{d}-1$, we need
to repeat the process for $d$ steps (Subsection 5.4).

Thus, our formal proof of Theorem 4.2(ii) relies on the three following
technical propositions. For $k\in\mathbb{Z}_{>0}$, denote by
$\operatorname{S}_{k}$ the permutation group of the set $\\{1,\ldots,k\\}$.

######  Proposition 5.2.

For every $k\geq 2$, there exists a function
$\mu_{k}\colon\operatorname{S}_{k}\rightarrow\mathbb{Z}$, such that for any
sequence of elements $C_{1},\ldots,C_{m},m\geq k,$ in the Lie algebra
$\mathfrak{u}(n)$ we have

$[\ldots[[C_{1},C_{2}],C_{3}],\ldots,C_{k}]=\sum\nolimits_{\sigma\in\operatorname{S}_{k}}\mu_{k}(\sigma)H_{k}(C_{\sigma(1)},\ldots,C_{\sigma(k)},C_{k+1},\ldots,C_{m}).$
(11)

######  Proposition 5.3.

Let $k\leq 10$ and let $\mathcal{H}\subset\mathsf{UT}(n,\mathbb{Q})$ be a
finite set of matrices for some $n\geq 2$. Then there exist a non-negative
integer $r$, positive rational numbers $\alpha_{1},\ldots,\alpha_{r}$, as well
as, for $s=1,\ldots,r$, words $\boldsymbol{j}_{s}=j_{s,1}j_{s,2}\cdots
j_{s,m_{s}}$ in the alphabet $\mathcal{I}=\\{1,2,\ldots,k+1\\}$, such that
$\operatorname{PI}^{\mathcal{I}}(\boldsymbol{j}_{s})\in\\{(1,\ldots,1),(2,\ldots,2)\\}$
and

$\sum_{\sigma\in\operatorname{S}_{k+1}}H_{k}(\log B_{\sigma(1)},\ldots,\log
B_{\sigma(k+1)})+\sum_{s=1}^{r}\alpha_{s}\sum_{\sigma\in\operatorname{S}_{k+1}}H_{k}(\log
B_{\sigma(j_{s,1})},\ldots,\log B_{\sigma(j_{s,m_{s}})})\\\
\in\mathfrak{L}_{\geq k+1}(\log\mathcal{H})+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq 2}(\log\mathcal{H}))$ (12)

for all $B_{1},\ldots,B_{k+1}\in\mathsf{UT}(n,\mathbb{Q})$ satisfying $\log
B_{i}\in\mathfrak{L}_{\geq 1}(\log\mathcal{H})$ and $\sum_{i=1}^{k+1}\log
B_{i}\in\mathfrak{L}_{\geq 2}(\log\mathcal{H})$.

######  Proposition 5.4.

Let $V$ be a finite dimensional $\mathbb{Q}$-linear space. Let $d$ be a
positive integer, $\mathcal{I}$ be a finite index set, and
$\boldsymbol{a}_{1i},\ldots,\boldsymbol{a}_{di},i\in\mathcal{I}$ be vectors in
$V$. For any $t\in\mathbb{Z}_{>0}$ and $i\in\mathcal{I}$, define

$P_{i}(t)\coloneqq
t\cdot\boldsymbol{a}_{1i}+t^{2}\cdot\boldsymbol{a}_{2i}+\cdots+t^{d}\cdot\boldsymbol{a}_{di}.$

Suppose the following two conditions hold:

  1. (i)

The $\mathbb{Q}_{\geq 0}$-cone
$\mathcal{C}_{d}\coloneqq\langle\boldsymbol{a}_{di}\mid
i\in\mathcal{I}\rangle_{\mathbb{Q}_{\geq 0}}$ is a linear space.

  2. (ii)

For $k=d-1,d-2,\ldots,1$, the inductively defined $\mathbb{Q}_{\geq 0}$-cones
$\mathcal{C}_{k}\coloneqq\langle\boldsymbol{a}_{ki}\mid
i\in\mathcal{I}\rangle_{\mathbb{Q}_{\geq 0}}+\mathcal{C}_{k+1}$ are linear
spaces.

Then the $\mathbb{Q}_{\geq 0}$-cone $\langle P_{i}(t)\mid
i\in\mathcal{I},t\in\mathbb{Z}_{>0}\rangle_{\mathbb{Q}_{\geq 0}}$ is equal to
$\mathcal{C}_{1}$.

This concludes the overview. In the following subsections we will gradually
prove these technical propositions. The intuition of Proposition 5.2 is as
follows. Theorem 3.8 showed that in the BCH formula, the terms $H_{k}(\log
B_{1},\ldots,\log B_{m})$ can be written as a linear combination of
$k$-iterated Lie brackets $[\ldots[[\log B_{i_{1}},\log B_{i_{2}}],\log
B_{i_{3}}],\ldots,\log B_{i_{k}}]$. Here, Proposition 5.2 shows that a
converse of it is true: for any $k\geq 2$, the $k$-iterated Lie bracket
$[\ldots[[\log B_{1},\log B_{2}],\log B_{3}],\ldots,\log B_{k}]$ can be
written as a linear combination of expressions in $H_{k}$.

Proposition 5.3 shows that for $k\leq 10$, one can find a linear combination
with _positive_ coefficients of the terms $H_{k}$ that lies in
$\mathfrak{L}_{\geq k+1}+\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq 2}(\cdot))$.
(Note that _a priori_ $H_{k}$ lies in $\mathfrak{L}_{\geq k}(\cdot)$.)
Proposition 5.3 is the only one among the three above propositions that is
limited by the nilpotency class. This constitutes the main obstacle to
generalizing Theorem 4.2 to higher nilpotency classes.

Finally, Proposition 5.4 concerns only convex geometry and is responsible for
finding a suitable $t$ from difficulty (iii).

###  5.1 Proof of Proposition 5.2

For a permutation $\sigma\in\operatorname{S}_{k}$, define $d(\sigma)$ to be
the number of _descents_ in $\sigma$, that is, the number of
$i\in\\{1,\ldots,k-1\\}$ such that $\sigma(i)>\sigma(i+1)$. In order to prove
Proposition 5.2, we need an explicit expression for the terms $H_{k}$. This
expression is provided by Dynkin333Dynkin originally only proved the bivariate
case of Lemma 5.5. It was later been generalized to the multivariate case
without much difficulty.:

######  Lemma 5.5 (Dynkin formula [18], [31, Proposition 3.4 and Proposition
4.2]).

We have

$H_{k}(C_{1},\ldots,C_{m})=\sum_{i_{1}+\cdots+i_{m}=k}\frac{1}{i_{1}!\ldots
i_{m}!}\varphi_{k}(\underbrace{C_{1},\ldots,C_{1}}_{i_{1}},\underbrace{C_{2},\ldots,C_{2}}_{i_{2}},\ldots,\underbrace{C_{m},\ldots,C_{m}}_{i_{m}}),$
(13)

where the indices $i_{1},\ldots,i_{m}$ are non-negative integers, and

$\varphi_{k}(X_{1},\ldots,X_{k})=\sum_{\sigma\in\operatorname{S}_{k}}\frac{(-1)^{d(\sigma)}}{k^{2}\binom{k-1}{d(\sigma)}}[\ldots[[X_{\sigma(1)},X_{\sigma(2)}],X_{\sigma(3)}],\ldots,X_{\sigma(k)}].$
(14)

Define recursively the following maps
$\mu_{k}:\operatorname{S}_{k}\rightarrow\mathbb{Z},k=2,3,\ldots$. For $k=2$,
let $\mu_{2}(\operatorname{id})=1,\mu_{2}((12))=-1$, where $\operatorname{id}$
is the constant permutation and $(12)$ is the permutation that swaps $1$ and
$2$. For $k\geq 3$, denote by $(j_{1}j_{2}\cdots j_{m})$ the cyclic
permutation that sends $j_{i}$ to $j_{i+1}$, $i=1,\ldots,m-1$, and sends
$j_{m}$ to $j_{1}$. Suppose $\mu_{k-1}$ already defined, we then define

$\displaystyle\mu_{k}(\sigma)\coloneqq\begin{cases}\mu_{k-1}(\sigma)\quad&k=\sigma(k)\\\
-\mu_{k-1}(\sigma\circ(12\cdots k))\quad&k=\sigma(1)\\\
0\quad&k=\sigma(i),i=2,\ldots,k-1.\end{cases}$ (15)

In the first two cases, the permutation $\sigma$ or $\sigma\circ(12\cdots k)$
fixes $k$, so they can be considered as elements in $\operatorname{S}_{k-1}$,
hence $\mu_{k-1}(\sigma)$ is well defined. For example, $\mu_{3}(\sigma)=1$
when $\sigma=\operatorname{id}$ or $(13)$; $\mu_{3}(\sigma)=-1$ when
$\sigma=(12)$ or $(132)$; and $\mu_{3}(\sigma)=0$ otherwise. We will show
that, for this $\mu_{k}$, the Equation (11) in Proposition 5.2 is satisfied:

See 5.2

###### Proof.

Take $\mu_{k}$ to be the function defined recursively in (15). For every
$j\geq 2$, there is a natural embedding
$f_{j}:\operatorname{S}_{j}\hookrightarrow\operatorname{S}_{j+1}$, defined by
$f_{j}(\sigma)(i)=\sigma(i),i=1,\ldots,j$, $f_{j}(\sigma)(j+1)=j+1$. It is
easy to verify that under this natural embedding, $\mu_{j}$ and $\mu_{j+1}$
are identified, that is, $\mu_{j}=\mu_{j+1}\circ f_{j}$. Therefore, we can
denote by $\mu$ the map $\cup_{k\geq
2}\operatorname{S}_{k}\rightarrow\mathbb{Z}$ as $\mu(\sigma)=\mu_{k}(\sigma)$,
where $\sigma\in\operatorname{S}_{k}$. We prove Equation (11) in three steps.

  1. (1)

First, we simplify the right hand side of Equation (11) by showing

$\sum_{\sigma\in\operatorname{S}_{k}}\mu(\sigma)H_{k}(C_{\sigma(1)},\ldots,C_{\sigma(k)},C_{k+1},\ldots,C_{m})=\sum_{\sigma\in\operatorname{S}_{k}}\mu(\sigma)\varphi_{k}(C_{\sigma(1)},\ldots,C_{\sigma(k)}),$
(16)

where $\varphi_{k}$ is defined in Lemma 5.5.

Thanks to Lemma 5.5, $H_{k}(C_{1},\ldots,C_{m})$ can be written as

$H_{k}(C_{1},\ldots,C_{m})=\\\ \sum_{1\leq j_{1}<j_{2}<\cdots<j_{k}\leq
m}\varphi_{k}(C_{j_{1}},\ldots,C_{j_{k}})+\sum_{l=2}^{k-1}\sum_{1\leq
j_{1}<j_{2}<\cdots<j_{l}\leq m}H_{kl}(C_{j_{1}},\ldots,C_{j_{l}}),$ (17)

where $H_{kl}(C_{j_{1}},\ldots,C_{j_{l}})$ is some linear combination of
elements in $[\\{C_{j_{1}},\ldots,C_{j_{l}}\\}]_{k}$. By abuse of notation,
for $\sigma\in\operatorname{S}_{k}$ and $x>k$, we define
$\sigma(x)=\sigma^{-1}(x)=x$. For any $l=2,\ldots,k-1$, we have

$\sum_{\sigma\in\operatorname{S}_{k}}\sum_{1\leq j_{1}<j_{2}<\cdots<j_{l}\leq
m}\mu(\sigma)H_{kl}(C_{\sigma(j_{1})},\ldots,C_{\sigma(j_{l})})\\\
=\sum_{\overset{t_{1},t_{2},\ldots,t_{l}\in\\{1,\ldots,m\\}}{\text{pairwise
distinct}}}H_{kl}(C_{t_{1}},\ldots,C_{t_{l}})\sum_{\overset{\sigma\in\operatorname{S}_{k}}{\sigma^{-1}(t_{1})<\cdots<\sigma^{-1}(t_{l})}}\mu(\sigma).$
(18)

We claim that, for any pairwise distinct
$t_{1},t_{2},\ldots,t_{l}\in\\{1,\ldots,m\\}$, $l<k$, we have

$\sum_{\overset{\sigma\in\operatorname{S}_{k}}{\sigma^{-1}(t_{1})<\cdots<\sigma^{-1}(t_{l})}}\mu(\sigma)=0.$
(19)

We show (19) by induction on $k$. When $k=2$, by the definition of $\mu$, (19)
holds. Suppose (19) holds for $k-1$. Denote by $c$ the cyclic permutation
$(12\cdots k)$, then by the recursive definition of $\mu$,

$\sum_{\overset{\sigma\in\operatorname{S}_{k}}{\sigma^{-1}(t_{1})<\cdots<\sigma^{-1}(t_{l})}}\mu(\sigma)=\sum_{\overset{\sigma\in\operatorname{S}_{k-1}}{\sigma^{-1}(t_{1})<\cdots<\sigma^{-1}(t_{l})}}\mu(\sigma)-\sum_{\overset{\sigma\in\operatorname{S}_{k-1}}{c\circ\sigma^{-1}(t_{1})<\cdots<c\circ\sigma^{-1}(t_{l})}}\mu(\sigma).$
(20)

Without loss of generality, suppose the sum on the left hand side is not
empty. That is, there exists at least one permutation
$\sigma\in\operatorname{S}_{k}$ such that
$\sigma^{-1}(t_{1})<\cdots<\sigma^{-1}(t_{l})$. Since
$\sigma^{-1}\in\operatorname{S}_{k}$ does not permute any $t_{j}$ with
$t_{j}>k$, the elements of $\\{t_{1},\ldots,t_{l}\\}$ which are larger than
$k$ must appear after the elements which are smaller or equal to $k$, and must
appear in increasing order. In other words, there exists some $s\geq 1$, such
that $t_{i}\leq k$ for all $i<s$, and $k<t_{s}<\cdots<t_{l}$. ($s$ could be
$l+1$, in which case $t_{i}\leq k$ for all $i=1,\ldots,l$.) Since
$\sigma\in\operatorname{S}_{k}$ does not change the value of
$t_{s},\cdots,t_{l}$, one can discard them without changing the sum. Hence, we
suppose without loss of generality $t_{1},\ldots,t_{l}\in\\{1,\ldots,k\\}$.

    1. (a)

If $t_{i}=k$ for some $i=2,\ldots,l-1$. Then no permutation
$\sigma\in\operatorname{S}_{k-1}$ can satisfy
$\sigma^{-1}(t_{1})<\sigma^{-1}(t_{i})=k<\sigma^{-1}(t_{l})$ or
$c\circ\sigma^{-1}(t_{1})<c\circ\sigma^{-1}(t_{i})=1<c\circ\sigma^{-1}(t_{l})$.
Hence, both sums on the right hand side of Equation (20) are empty. The claim
(19) follows.

    2. (b)

If $t_{1}=k$. Then no permutation $\sigma\in\operatorname{S}_{k-1}$ can
satisfy $\sigma^{-1}(t_{1})<\sigma^{-1}(t_{i})=k<\sigma^{-1}(t_{l})$, so the
first sum on the right hand side of Equation (20) is empty. As for the second
sum, because $c\circ\sigma^{-1}(t_{1})=c(k)=1$, we have
$c\circ\sigma^{-1}(t_{1})<\cdots<c\circ\sigma^{-1}(t_{l})$ if and only if
$\sigma^{-1}(t_{2})<\cdots<\sigma^{-1}(t_{l})$. Hence, using the induction
hypothesis on $t_{2},\ldots,t_{l}\in\\{1,\ldots,k\\}$ yields

$\sum_{\overset{\sigma\in\operatorname{S}_{k-1}}{c\circ\sigma^{-1}(t_{1})<\cdots<c\circ\sigma^{-1}(t_{l})}}\mu(\sigma)=\sum_{\overset{\sigma\in\operatorname{S}_{k-1}}{\sigma^{-1}(t_{2})<\cdots<\sigma^{-1}(t_{l})}}\mu(\sigma)=0.$

Therefore both sums on the right hand side of Equation (20) equal zero. The
claim (19) follows.

    3. (c)

If $t_{l}=k$. Similar to the previous case, the second sum on the right hand
side of Equation (20) is empty. As for the first sum, because
$\sigma^{-1}(t_{l})=k$, we have $\sigma^{-1}(t_{1})<\cdots<\sigma^{-1}(t_{l})$
if and only if $\sigma^{-1}(t_{1})<\cdots<\sigma^{-1}(t_{l-1})$. Hence, using
the induction hypothesis on $t_{1},\ldots,t_{l-1}\in\\{1,\ldots,k\\}$ shows
the sum is zero. The claim (19) follows.

    4. (d)

If $t_{i}\neq k$ for all $i=1,\ldots,l$. Then
$\sigma^{-1}(t_{1})<\cdots<\sigma^{-1}(t_{l})$ if and only if
$c\circ\sigma^{-1}(t_{1})<\cdots<c\circ\sigma^{-1}(t_{l})$. Hence, the two
sums on the right hand side of Equation (20) are the same. The claim (19)
follows.

Using the claim (19) on Equation (18) yields

$\sum_{\sigma\in\operatorname{S}_{k}}\sum_{1\leq j_{1}<j_{2}<\cdots<j_{l}\leq
m}\mu(\sigma)H_{kl}(C_{\sigma(j_{1})},\ldots,C_{\sigma(j_{l})})=0,$ (21)

and this combined with Equation (17) yields

$\displaystyle\sum_{\sigma\in\operatorname{S}_{k}}\mu(\sigma)H_{k}(C_{\sigma(1)},\ldots,C_{\sigma(k)},C_{k+1},\ldots,C_{m})$
$\displaystyle=$
$\displaystyle\sum_{\sigma\in\operatorname{S}_{k}}\mu(\sigma)H_{k}(C_{\sigma(1)},\ldots,C_{\sigma(m)})\quad\text{(define
$\sigma(s)=s$ for $\sigma\in\operatorname{S}_{k}$ and $s>k$)}$
$\displaystyle=$
$\displaystyle\sum_{\sigma\in\operatorname{S}_{k}}\mu(\sigma)\sum_{1\leq
j_{1}<j_{2}<\cdots<j_{k}\leq
m}\varphi_{k}(C_{\sigma(j_{1})},\ldots,C_{\sigma(j_{k})})\quad\text{(by
\eqref{eq:sumrewrite} and \eqref{eq:sumHkl})}$ $\displaystyle=$
$\displaystyle\sum_{\overset{t_{1},t_{2},\ldots,t_{k}\in\\{1,\ldots,m\\}}{\text{pairwise
distinct}}}\varphi_{k}(C_{t_{1}},\ldots,C_{t_{k}})\sum_{\overset{\sigma\in\operatorname{S}_{k}}{\sigma^{-1}(t_{1})<\cdots<\sigma^{-1}(t_{k})}}\mu(\sigma)$
$\displaystyle=$
$\displaystyle\sum_{l=0}^{k}\sum_{\overset{\overset{t_{1},t_{2},\ldots,t_{l}\in\\{1,\ldots,k\\}}{\text{pairwise
distinct,}}}{k<t_{l+1}<\cdots<t_{k}\leq
m}}\varphi_{k}(C_{t_{1}},\ldots,C_{t_{k}})\sum_{\overset{\sigma\in\operatorname{S}_{k}}{\sigma^{-1}(t_{1})<\cdots<\sigma^{-1}(t_{l})}}\mu(\sigma)$
(22)

Because Equation (19) holds for $l<k$, that is, the sum
$\sum_{\overset{\sigma\in\operatorname{S}_{k}}{\sigma^{-1}(t_{1})<\cdots<\sigma^{-1}(t_{l})}}\mu(\sigma)$
vanishes whenever $l<k$, the above expression ((1)) is equal to

$\sum_{\overset{t_{1},t_{2},\ldots,t_{k}\in\\{1,\ldots,k\\}}{\text{pairwise
distinct}}}\varphi_{k}(C_{t_{1}},\ldots,C_{t_{k}})\sum_{\overset{\sigma\in\operatorname{S}_{k}}{\sigma^{-1}(t_{1})<\cdots<\sigma^{-1}(t_{k})}}\mu(\sigma)=\sum_{\sigma\in\operatorname{S}_{k}}\mu(\sigma)\varphi_{k}(C_{\sigma(1)},\ldots,C_{\sigma(k)}).$

We have hence shown Equation (16):

$\sum_{\sigma\in\operatorname{S}_{k}}\mu(\sigma)H_{k}(C_{\sigma(1)},\ldots,C_{\sigma(k)},C_{k+1},\ldots,C_{m})=\sum_{\sigma\in\operatorname{S}_{k}}\mu(\sigma)\varphi_{k}(C_{\sigma(1)},\ldots,C_{\sigma(k)}),$

  2. (2)

The second step is to show

$\sum_{\sigma\in\operatorname{S}_{k}}\mu(\sigma)\varphi_{k}(C_{\sigma(1)},\ldots,C_{\sigma(k)})=\sum_{T\in\operatorname{S}_{k}}\frac{\mu(T)}{k}[\ldots[[C_{T(1)},C_{T(2)}],C_{T(3)}],\ldots,C_{T(k)}].$
(23)

Using the exact expression for $\varphi_{k}$ in Lemma 5.5, we have

$\displaystyle\sum_{\sigma\in\operatorname{S}_{k}}\mu(\sigma)\varphi_{k}(C_{\sigma(1)},\ldots,C_{\sigma(k)})$
$\displaystyle=$
$\displaystyle\sum_{\sigma\in\operatorname{S}_{k}}\sum_{\tau\in\operatorname{S}_{k}}\frac{(-1)^{d(\tau)}\mu(\sigma)}{k^{2}\binom{k-1}{d(\tau)}}[\ldots[[C_{\sigma\circ\tau(1)},C_{\sigma\circ\tau(2)}],C_{\sigma\circ\tau(3)}],\ldots,C_{\sigma\circ\tau(k)}]$
$\displaystyle=$
$\displaystyle\sum_{T\in\operatorname{S}_{k}}[\ldots[[C_{T(1)},C_{T(2)}],C_{T(3)}],\ldots,C_{T(k)}]\sum_{\sigma\in\operatorname{S}_{k}}\frac{(-1)^{d(\sigma^{-1}\circ
T)}\mu(\sigma)}{k^{2}\binom{k-1}{d(\sigma^{-1}\circ T)}}$ (24)

We will compute the value of
$\sum_{\sigma\in\operatorname{S}_{k}}\frac{(-1)^{d(\sigma^{-1}\circ
T)}\mu(\sigma)}{k^{2}\binom{k-1}{d(\sigma^{-1}\circ T)}}$ depending on the
permutation $T$. We show by induction on $k$ that

$\sum_{\sigma\in\operatorname{S}_{k}}\frac{(-1)^{d(\sigma^{-1}\circ
T)}\mu(\sigma)}{k^{2}\binom{k-1}{d(\sigma^{-1}\circ T)}}=\frac{\mu(T)}{k}.$
(25)

When $k=2$, by direct computation,
$\sum_{\sigma\in\operatorname{S}_{k}}\frac{(-1)^{d(\sigma^{-1}\circ
T)}\mu(\sigma)}{k^{2}\binom{k-1}{d(\sigma^{-1}\circ T)}}$ is equal to
$\frac{1}{2}$ if $T=\operatorname{id}$ and to $-\frac{1}{2}$ if $T=(12)$. This
matches the values of $\frac{\mu(T)}{k}$. If $k\geq 3$, suppose (25) proven
for $k-1$. Again denote by $c$ the cyclic permutation $(12\cdots k)$, by the
recursive definition of $\mu$ we have

$\sum_{\sigma\in\operatorname{S}_{k}}\frac{(-1)^{d(\sigma^{-1}\circ
T)}\mu(\sigma)}{k^{2}\binom{k-1}{d(\sigma^{-1}\circ
T)}}=\sum_{\sigma\in\operatorname{S}_{k-1}}\frac{(-1)^{d(\sigma^{-1}\circ
T)}\mu(\sigma)}{k^{2}\binom{k-1}{d(\sigma^{-1}\circ
T)}}-\sum_{\sigma\in\operatorname{S}_{k-1}}\frac{(-1)^{d(c\circ\sigma^{-1}\circ
T)}\mu(\sigma)}{k^{2}\binom{k-1}{d(c\circ\sigma^{-1}\circ T)}}.$ (26)

    1. (a)

If $T(i)=k$ for some $i=2,\ldots,k-1$. We claim that $d(\sigma^{-1}\circ
T)=d(c\circ\sigma^{-1}\circ T)$ for all $\sigma\in\operatorname{S}_{k-1}$. In
fact, for $\sigma\in\operatorname{S}_{k-1}$, we have $\sigma^{-1}\circ T(i)=k$
and $c\circ\sigma^{-1}\circ T(i)=1$. Therefore $\sigma^{-1}\circ
T(i)>\sigma^{-1}\circ T(i+1)$, $\sigma^{-1}\circ T(i)>\sigma^{-1}\circ
T(i-1)$, whereas $c\circ\sigma^{-1}\circ T(i)<c\circ\sigma^{-1}\circ T(i+1)$,
$c\circ\sigma^{-1}\circ T(i)<c\circ\sigma^{-1}\circ T(i-1)$. And for $j\neq
i-1,i$, we have $\sigma^{-1}\circ T(j)>\sigma^{-1}\circ T(j+1)$ if and only if
$c\circ\sigma^{-1}\circ T(j)>c\circ\sigma^{-1}\circ T(j+1)$. This shows
$d(\sigma^{-1}\circ T)=d(c\circ\sigma^{-1}\circ T)$. Hence, the two sums on
the right hand side of (26) are equal, and
$\sum_{\sigma\in\operatorname{S}_{k}}\frac{(-1)^{d(\sigma^{-1}\circ
T)}\mu(\sigma)}{k^{2}\binom{k-1}{d(\sigma^{-1}\circ T)}}=0=\frac{\mu(T)}{k}$.

    2. (b)

If $T(1)=k$. Similar to the above discussion, we can show that
$d(\sigma^{-1}\circ T)=d(c\circ\sigma^{-1}\circ T)+1$. Hence the right hand
side of (26) is equal to

$\displaystyle-\sum_{\sigma\in\operatorname{S}_{k-1}}\left(\frac{(-1)^{d(c\circ\sigma^{-1}\circ
T)}\mu(\sigma)}{k^{2}\binom{k-1}{d(c\circ\sigma^{-1}\circ
T)+1}}+\frac{(-1)^{d(c\circ\sigma^{-1}\circ
T)}\mu(\sigma)}{k^{2}\binom{k-1}{d(c\circ\sigma^{-1}\circ T)}}\right)$
$\displaystyle=$
$\displaystyle\;-\sum_{\sigma\in\operatorname{S}_{k-1}}\frac{(-1)^{d(c\circ\sigma^{-1}\circ
T)}\mu(\sigma)}{k(k-1)\binom{k-2}{d(c\circ\sigma^{-1}\circ T)}}$
$\displaystyle=$
$\displaystyle\;\frac{-(k-1)}{k}\sum_{\sigma\in\operatorname{S}_{k-1}}\frac{(-1)^{d(c\circ\sigma^{-1}\circ
T)}\mu(\sigma)}{(k-1)^{2}\binom{k-2}{d(c\circ\sigma^{-1}\circ T)}}$

We claim that $d(c\circ\sigma^{-1}\circ T)=d(\sigma^{-1}\circ T\circ c)$. This
is because $\sigma^{-1}\circ T\circ c(k-1)<\sigma^{-1}\circ T\circ c(k)=k$,
$1=c\circ\sigma^{-1}\circ T(1)<c\circ\sigma^{-1}\circ T(2)$, and
$c\circ\sigma^{-1}\circ T(i+1)>c\circ\sigma^{-1}\circ T(i)$ if and only if
$\sigma^{-1}\circ T\circ c(i)>\sigma^{-1}\circ T\circ c(i-1)$, for
$i=2,3,\ldots,k-1$. Hence,

$\displaystyle\frac{-(k-1)}{k}\sum_{\sigma\in\operatorname{S}_{k-1}}\frac{(-1)^{d(c\circ\sigma^{-1}\circ
T)}\mu(\sigma)}{(k-1)^{2}\binom{k-2}{d(c\circ\sigma^{-1}\circ T)}}$
$\displaystyle=$
$\displaystyle\;\frac{-(k-1)}{k}\sum_{\sigma^{\prime}\in\operatorname{S}_{k-1}^{c}}\frac{(-1)^{d(\sigma^{-1}\circ
T\circ c)}\mu(\sigma)}{(k-1)^{2}\binom{k-2}{d(\sigma^{-1}\circ T\circ c)}}$
$\displaystyle=$ $\displaystyle\;\frac{-(k-1)}{k}\frac{\mu(T\circ c)}{k-1}$
(by induction hypothesis) $\displaystyle=$
$\displaystyle\;\frac{(k-1)}{k}\frac{\mu(T)}{k-1}$ (by definition of $\mu$)
$\displaystyle=$ $\displaystyle\;\frac{\mu(T)}{k}.$

    3. (c)

If $T(k)=k$. Similar to the above discussion, we can show that
$d(c\circ\sigma^{-1}\circ T)=d(\sigma^{-1}\circ T)+1$. And hence the right
hand side of (26) is equal to

$\frac{(k-1)}{k}\sum_{\sigma\in\operatorname{S}_{k-1}}\frac{(-1)^{d(\sigma^{-1}\circ
T)}\mu(\sigma)}{(k-1)^{2}\binom{k-2}{d(\sigma^{-1}\circ
T)}}=\frac{(k-1)}{k}\frac{\mu(T)}{k-1}=\frac{\mu(T)}{k}$

by the induction hypothesis, where $T$ can be considered as an element in
$\operatorname{S}_{k-1}$ since it stabilizes $k$.

We have thus shown the claim (25). Putting this into Equation ((2)) shows
Equation (23):

$\sum_{\sigma\in\operatorname{S}_{k}}\mu(\sigma)\varphi_{k}(C_{\sigma(1)},\ldots,C_{\sigma(k)})=\sum_{T\in\operatorname{S}_{k}}\frac{\mu(T)}{k}[\ldots[[C_{T(1)},C_{T(2)}],C_{T(3)}],\ldots,C_{T(k)}].$

  3. (3)

The third and last step is to show444A direct way of proving Equation (27) is
to use the Dynkin-Specht-Wever theorem [18], which states that if a non-
commutative polynomial $f\in\mathbb{Q}\langle C_{1},\ldots,C_{k}\rangle$ is
_Lie_ , then one can replace all monomials $C_{i_{1}}C_{i_{2}}\cdots
C_{i_{k}}$ by $[\ldots[C_{i_{1}},C_{i_{2}}],\ldots,C_{i_{k}}]/k$ without
changing its value. Writing the right hand side of (27) as an element in
$\mathbb{Q}\langle C_{1},\ldots,C_{k}\rangle$ gives
$k\sum_{\sigma\in\operatorname{S}_{k}}\mu(\sigma)C_{\sigma(1)}C_{\sigma(2)}\cdots
C_{\sigma(k)}$ (we can check this using the definition of $\mu$), which is
equal to the left hand side by replacing the monomials
$C_{\sigma(1)}C_{\sigma(2)}\cdots C_{\sigma(k)}$ by the Lie brackets
$[\ldots[[C_{\sigma(1)},C_{\sigma(2)}],C_{\sigma(3)}],\ldots,C_{\sigma(k)}]/k$.
Nevertheless, here we will give a self-contained proof without using the
Dynkin-Specht-Wever theorem.

$\sum_{T\in\operatorname{S}_{k}}\mu(T)[\ldots[[C_{T(1)},C_{T(2)}],C_{T(3)}],\ldots,C_{T(k)}]=k[\ldots[[C_{1},C_{2}],C_{3}],\ldots,C_{k}].$
(27)

First, using induction on $k$, we will show that

$\sum_{T\in\operatorname{S}_{k}}\mu(T)[\ldots[[C_{k+1},C_{T(1)}],C_{T(2)}],\ldots,C_{T(k)}]=-[\ldots[[C_{1},C_{2}],C_{3}],\ldots,C_{k+1}].$
(28)

The case where $k=2$ is immediate. Suppose Equation (28) hold for $k-1$, then

$\sum_{T\in\operatorname{S}_{k}}\mu(T)[\ldots[[C_{k+1},C_{T(1)}],C_{T(2)}],\ldots,C_{T(k)}]\\\
=\sum_{T\in\operatorname{S}_{k-1}}\mu(T)[[\ldots[[C_{k+1},C_{T(1)}],C_{T(2)}],\ldots,C_{T(k-1)}],C_{k}]\\\
-\sum_{T\in\operatorname{S}_{k-1}}\mu(T)[\ldots[[C_{k+1},C_{k}],C_{T(1)}],\ldots,C_{T(k-1)}].$
(29)

By the induction hypothesis, the first sum on the right hand side is equal to

$-[[[\ldots[[C_{1},C_{2}],C_{3}],\ldots,C_{k-1}],C_{k+1}],C_{k}],$

and the second sum on the right hand side is equal to

$-[[\ldots[[C_{1},C_{2}],C_{3}],\ldots,C_{k-1}],[C_{k+1},C_{k}]].$

Using the Jacobi identity and the anticommutativity of Lie brackets, we have

$-[[[\ldots[[C_{1},C_{2}],C_{3}],\ldots,C_{k-1}],C_{k+1}],C_{k}]+[[\ldots[[C_{1},C_{2}],C_{3}],\ldots,C_{k-1}],[C_{k+1},C_{k}]]\\\
=-[[[\ldots[[C_{1},C_{2}],C_{3}],\ldots,C_{k-1}],C_{k}],C_{k+1}].$

Hence, Equation (29) yields

$\sum_{T\in\operatorname{S}_{k}}\mu(T)[\ldots[[C_{k+1},C_{T(1)}],C_{T(2)}],\ldots,C_{T(k)}]=-[[\ldots[[C_{1},C_{2}],C_{3}],\ldots,C_{k}],C_{k+1}],$

concluding the proof by induction for Equation (28).

Next, we will again use induction on $k$ to prove Equation (27):

$\sum_{T\in\operatorname{S}_{k}}\mu(T)[\ldots[[C_{T(1)},C_{T(2)}],C_{T(3)}],\ldots,C_{T(k)}]=k[\ldots[[C_{1},C_{2}],C_{3}],\ldots,C_{k}].$

The case of $k=2$ results from direct computation. Suppose (27) hold for
$k-1$, then

$\displaystyle\sum_{T\in\operatorname{S}_{k}}\mu(T)[\ldots[[C_{T(1)},C_{T(2)}],C_{T(3)}],\ldots,C_{T(k)}]$
$\displaystyle=$
$\displaystyle\sum_{T\in\operatorname{S}_{k-1}}\mu(T)[[\ldots[[C_{T(1)},C_{T(2)}],C_{T(3)}],\ldots,C_{T(k-1)}],C_{k}]$
$\displaystyle\quad-\sum_{T\in\operatorname{S}_{k-1}}\mu(T)[\ldots[[C_{k},C_{T(1)}],C_{T(2)}],\ldots,C_{T(k-1)}]$
$\displaystyle=$
$\displaystyle\;(k-1)[\ldots[[C_{1},C_{2}],C_{3}],\ldots,C_{k}]$
$\displaystyle\quad-\sum_{T\in\operatorname{S}_{k-1}}\mu(T)[\ldots[[C_{k},C_{T(1)}],C_{T(2)}],\ldots,C_{T(k-1)}]$
$\displaystyle\quad(\text{by induction hypothesis})$ $\displaystyle=$
$\displaystyle\;k[\ldots[[C_{1},C_{2}],C_{3}],\ldots,C_{k}]$
$\displaystyle\quad(\text{by Equation~{}\eqref{eq:indgoal2} for }k-1).$

We have thus shown Equation (27).

Combining the Equations (16), (23) and (27) obtained in the three steps gives
us

$\sum_{\sigma\in\operatorname{S}_{k}}\mu(\sigma)H_{k}(C_{\sigma(1)},\ldots,C_{\sigma(k)},C_{k+1},\ldots,C_{m})=[\ldots[[C_{1},C_{2}],C_{3}],\ldots,C_{k}].$

∎

###  5.2 Proof of Proposition 5.3

In this subsection we prove Proposition 5.3. Again, the key is understanding
the structure of the expressions for $H_{k}$. For even $k$, the following
lemma shows that the expression $H_{k}(C_{1},\ldots,C_{m})$ is
“antisymmetric”, and immediately yields Proposition 5.3.

######  Lemma 5.6.

When $k$ is even, we have

$H_{k}(C_{1},\ldots,C_{m})=-H_{k}(C_{m},\ldots,C_{1}).$

###### Proof.

Define a new variable $t$. Replacing $B_{i}$ by $\exp({tC_{i}})$ in the BCH
formula (1), we have

$\log(\exp({tC_{1}})\cdots\exp({tC_{m}}))=t\sum_{i=1}^{m}C_{i}+t^{k}\sum_{k=2}^{d-1}H_{k}(C_{1},\ldots,C_{m}).$
(30)

Now, replace $B_{i}$ by $\exp({-tC_{m+1-i}})$, $i=1,\ldots,m$, in the BCH
formula (1), we obtain

$\log(\exp({-tC_{m}})\cdots\exp({-tC_{1}}))=-t\sum_{i=1}^{m}C_{i}+(-t)^{k}\sum_{k=2}^{d-1}H_{k}(C_{m},\ldots,C_{1}).$
(31)

Since
$\log(\exp({tC_{1}})\cdots\exp({tC_{m}}))=-\log(\exp({-tC_{m}})\cdots\exp({-tC_{1}}))$,
comparing the coefficients of $t^{k}$ in (30) and (31) yields

$H_{k}(C_{1},\ldots,C_{m})=-H_{k}(C_{m},\ldots,C_{1})$

for even $k$. ∎

Next, we need the following lemmas regarding the odd terms $H_{3}$, $H_{5}$,
$H_{7}$ and $H_{9}$. These correspond to Proposition 5.3 for $k=3,5,7,9$.

######  Lemma 5.7.

Let $\mathcal{H}\subset\mathsf{UT}(n,\mathbb{Q})$ be a finite set of matrices.
Given matrices $B_{1},\ldots,B_{m}$ in $\mathsf{UT}(n,\mathbb{Q})$ such that
$\log B_{i}\in\mathfrak{L}_{\geq 1}(\log\mathcal{H})$, $i=1,\ldots,m$, and
$\sum_{i=1}^{m}\log B_{i}\in\mathfrak{L}_{\geq 2}(\log\mathcal{H})$, then

$\sum_{\sigma\in\operatorname{S}_{m}}H_{3}(\log B_{\sigma(1)},\ldots,\log
B_{\sigma(m)})\in\mathfrak{L}_{\geq 4}(\log\mathcal{H}).$

###### Proof.

Denote $C_{i}\coloneqq\log B_{i},i=1,\ldots,m$, we will show the following
identity

$\sum_{\sigma\in\operatorname{S}_{m}}H_{3}(C_{\sigma(1)},\ldots,C_{\sigma(m)})=\frac{m!}{12}\sum_{i=1}^{m}\left[C_{i},\left[C_{i},\sum_{j=1}^{m}C_{j}\right]\right].$
(32)

Write

$H_{3}(C_{\sigma(1)},\ldots,C_{\sigma(m)})=\sum_{i<j<k}H_{33}(C_{\sigma(i)},C_{\sigma(j)},C_{\sigma(k)})+\sum_{i<j}H_{32}(C_{\sigma(i)},C_{\sigma(j)}),$

where

$H_{33}(X,Y,Z)=\frac{1}{3}[X,[Y,Z]]+\frac{1}{6}[[X,Z],Y],$
$H_{32}(X,Y)=\frac{1}{12}([X,[X,Y]]+[[X,Y],Y]).$

Using the Jacobi identity, we have

$\displaystyle
H_{33}(C_{i},C_{j},C_{k})+H_{33}(C_{j},C_{k},C_{i})+H_{33}(C_{k},C_{i},C_{j})$
$\displaystyle=$
$\displaystyle\;\frac{1}{3}\left([C_{i},[C_{j},C_{k}]]+[C_{j},[C_{k},C_{i}]+[C_{k},[C_{i},C_{j}]]]\right)$
$\displaystyle+\frac{1}{6}\left([[C_{i},C_{j}],C_{k}]+[[C_{j},C_{k}],C_{i}]+[[C_{k},C_{i}],C_{j}]\right)$
$\displaystyle=$ $\displaystyle\;0$

for any $i,j,k$. Similarly,

$H_{33}(C_{k},C_{j},C_{i})+H_{33}(C_{j},C_{i},C_{k})+H_{33}(C_{i},C_{k},C_{j})=0.$

Hence,

$\displaystyle\sum_{\sigma\in\operatorname{S}_{m}}\sum_{i<j<k}H_{33}(C_{\sigma(i)},C_{\sigma(j)},C_{\sigma(k)})$
$\displaystyle=$
$\displaystyle\;\frac{m!}{6}\sum_{i<j<k}(H_{33}(C_{i},C_{j},C_{k})+H_{33}(C_{j},C_{k},C_{i})+H_{33}(C_{k},C_{i},C_{j}))$
$\displaystyle+\frac{m!}{6}\sum_{i<j<k}(H_{33}(C_{k},C_{j},C_{i})+H_{33}(C_{j},C_{i},C_{k})+H_{33}(C_{i},C_{k},C_{j}))$
$\displaystyle=$ $\displaystyle\;0.$

Whereas

$\displaystyle\sum_{\sigma\in\operatorname{S}_{m}}\sum_{i<j}H_{3,2}(C_{\sigma(i)},C_{\sigma(j)})$
$\displaystyle=$ $\displaystyle\;\frac{m!}{2}\sum_{i\neq
j}H_{3,2}(C_{i},C_{j})$ $\displaystyle=$
$\displaystyle\;\frac{m!}{2}\sum_{i\neq
j}\left(\frac{1}{12}[C_{i},[C_{i},C_{j}]]+\frac{1}{12}[[C_{i},C_{j}],C_{j}]\right)$
$\displaystyle=$
$\displaystyle\;\frac{m!}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\left(\frac{1}{12}[C_{i},[C_{i},C_{j}]]+\frac{1}{12}[[C_{i},C_{j}],C_{j}]\right)$
$\displaystyle=$
$\displaystyle\;\frac{m!}{2}\sum_{i=1}^{m}\frac{1}{12}\left[C_{i},\left[C_{i},\sum_{j=1}^{m}C_{j}\right]\right]+\frac{m!}{2}\sum_{j=1}^{m}\frac{1}{12}\left[\left[\sum_{i=1}^{m}C_{i},C_{j}\right],C_{j}\right]$
$\displaystyle=$
$\displaystyle\;\frac{m!}{12}\sum_{i=1}^{m}\left[C_{i},\left[C_{i},\sum_{j=1}^{m}C_{j}\right]\right].$

Adding up the two above expressions yields Equation (32). Since $\log
B_{i}\in\mathfrak{L}_{\geq 1}(\log\mathcal{H})$ for all $i$ and
$\sum_{i=1}^{m}\log B_{i}\in\mathfrak{L}_{\geq 2}(\log\mathcal{H})$, Equation
(32) yields

$\displaystyle\sum_{\sigma\in\operatorname{S}_{m}}H_{3}(\log
B_{\sigma(1)},\ldots,\log B_{\sigma(m)})$ $\displaystyle=$
$\displaystyle\;\frac{m!}{12}\sum_{i=1}^{m}\left[\log B_{i},\left[\log
B_{i},\sum_{j=1}^{m}\log B_{j}\right]\right]$ $\displaystyle\in$
$\displaystyle\;\frac{m!}{12}\sum_{i=1}^{m}\left[\log B_{i},\left[\log
B_{i},\mathfrak{L}_{\geq 2}(\log\mathcal{H})\right]\right]$ $\displaystyle\in$
$\displaystyle\;\mathfrak{L}_{\geq 4}(\log\mathcal{H})$

∎

The following Lemmas 5.8, 5.10 and 5.11 regarding $H_{5},H_{7},H_{9}$ are
proven using computer assistance from the software SageMath [40]. In what
follows, we give a sketch of their proof. Details of the full proof along with
the algorithm used for computer assistance are given in Section B. Links to
the code can be found in the respective proofs.

######  Lemma 5.8.

Let $\mathcal{H}\subset\mathsf{UT}(n,\mathbb{Q})$ be a finite set of matrices.
There exists a permutation $(j_{1},j_{2},\ldots,j_{12})$ of the tuple
$(1,1,2,2,\ldots,6,6)$, such that for any given set of matrices
$B_{1},\ldots,B_{6}$ in $\mathsf{UT}(n,\mathbb{Q})$ with $\log
B_{i}\in\mathfrak{L}_{\geq 1}(\log\mathcal{H})$ and $\sum_{i=1}^{6}\log
B_{i}\in\mathfrak{L}_{\geq 2}(\log\mathcal{H})$, we have

$\sum_{\sigma\in\operatorname{S}_{6}}H_{5}(\log B_{\sigma(1)},\ldots,\log
B_{\sigma(6)})+\sum_{\sigma\in\operatorname{S}_{6}}H_{5}(\log
B_{\sigma(j_{1})},\ldots,\log B_{\sigma(j_{12})})\\\ \in\mathfrak{L}_{\geq
6}(\log\mathcal{H})+\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{H})).$ (33)

Namely, we can take $(j_{1},j_{2},\ldots,j_{12})=(1,2,3,4,4,5,5,6,6,1,2,3)$.

###### Sketch of proof of Lemma 5.8.

For $x,y\in\mathfrak{u}(n)$, denote $x\sim y$ if

$x-y\in\mathfrak{L}_{\geq 6}(\log\mathcal{H})+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq 2}(\log\mathcal{H})).$

The claim (33) can be written as

$\sum_{\sigma\in\operatorname{S}_{6}}H_{5}(\log B_{\sigma(1)},\ldots,\log
B_{\sigma(6)})+\sum_{\sigma\in\operatorname{S}_{6}}H_{5}(\log
B_{\sigma(j_{1})},\ldots,\log B_{\sigma(j_{12})})\sim 0$

By the Dynkin formula (Lemma 5.5), the expressions
$\sum_{\sigma\in\operatorname{S}_{6}}H_{5}(\log B_{\sigma(1)},\ldots,\log
B_{\sigma(6)})$ and $\sum_{\sigma\in\operatorname{S}_{6}}H_{5}(\log
B_{\sigma(j_{1})},\ldots,\log B_{\sigma(j_{12})})$ can be expressed as a sum
in the form of

$\sum_{\boldsymbol{j}=(j_{1},\ldots,j_{5})\in\\{1,\ldots,6\\}^{5}}\alpha_{\boldsymbol{j}}\sum_{\sigma\in\operatorname{S}_{6}}\varphi_{5}(\log
B_{\sigma(j_{1})},\ldots,\log B_{\sigma(j_{5})}),$ (34)

where $\alpha_{\boldsymbol{j}}$ are rational numbers.

Since $\sum_{i=1}^{6}\log B_{i}\in\mathfrak{L}_{\geq 2}(\log\mathcal{H})$, for
any tuple $\boldsymbol{j}=(j_{1},\ldots,j_{5})\in\\{1,\ldots,6\\}^{5}$, the
expression $\sum_{\sigma\in\operatorname{S}_{6}}\varphi_{5}(\log
B_{\sigma(j_{1})},\ldots,\log B_{\sigma(j_{5})})$ is equivalent (under $\sim$)
to a rational multiple of
$\sum_{i\neq j}[[[[\log B_{i},\log B_{j}],\log B_{j}],\log B_{i}],\log
B_{i}]$. (See Appendix B for detailed justification.) In particular, using
computer assistance, we can compute these rational multiples and show

$\displaystyle\sum_{\sigma\in\operatorname{S}_{6}}H_{5}(\log
B_{\sigma(1)},\ldots,\log B_{\sigma(6)})$ $\displaystyle\sim\sum_{i\neq
j}[[[[\log B_{i},\log B_{j}],\log B_{j}],\log B_{i}],\log B_{i}],$
$\displaystyle\sum_{\sigma\in\operatorname{S}_{6}}H_{5}\big{(}\log
B_{\sigma(j_{1})},\ldots,\log B_{\sigma(j_{12})}\big{)}$
$\displaystyle\sim-\sum_{i\neq j}[[[[\log B_{i},\log B_{j}],\log B_{j}],\log
B_{i}],\log B_{i}].$

This yields

$\sum_{\sigma\in\operatorname{S}_{6}}H_{5}(\log B_{\sigma(1)},\ldots,\log
B_{\sigma(6)})+\sum_{\sigma\in\operatorname{S}_{6}}H_{5}(\log
B_{\sigma(j_{1})},\ldots,\log B_{\sigma(j_{12})})\sim 0.$

The code for computer assistance can be found at
https://doi.org/10.6084/m9.figshare.20124146.v1. ∎

######  Remark 5.9.

The added expression of $\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{H}))$ on the right hand side of Equation (33) is crucial for
its correctness. In fact, we can consider Equation (33) in the quotient Lie
algebra $L\coloneqq\mathfrak{L}_{\geq 1}(\log\mathcal{H})/\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq 2}(\log\mathcal{H}))$. The Lie algebra $L$ is
_metabelian_ , meaning $[[L,L],[L,L]]=0$. (Free) metabelian Lie algebras have
significantly fewer dimensions compared to (free) Lie algebras having the same
number of generators. Moreover, free metabelian Lie algebras admit a
relatively simple basis (sometimes called the _Gröbner-Shirshov basis_) [10],
making it computationally viable to find identities such as Equation (33). In
our computer assisted proofs (see Appendix B), we are using a heavily modified
version of this basis to compute Equation (33) as well as Equations (35) and
(36) in the following lemmas.

######  Lemma 5.10.

Let $\mathcal{H}\subset\mathsf{UT}(n,\mathbb{Q})$ be a finite set of matrices.
There exist positive rational numbers $\alpha_{1},\alpha_{2}$, as well as, for
$s=1,2$, permutations $(j_{s,1},j_{s,2},\ldots,j_{s,16})$ of the tuple
$(1,1,2,2,\ldots,8,8)$, such that for any given set of matrices
$B_{1},\ldots,B_{8}$ in $\mathsf{UT}(n,\mathbb{Q})$ with $\log
B_{i}\in\mathfrak{L}_{\geq 1}(\log\mathcal{H})$ and $\sum_{i=1}^{8}\log
B_{i}\in\mathfrak{L}_{\geq 2}(\log\mathcal{H})$, we have

$\sum_{\sigma\in\operatorname{S}_{8}}H_{7}(\log B_{\sigma(1)},\ldots,\log
B_{\sigma(8)})+\sum_{s=1}^{2}\alpha_{s}\sum_{\sigma\in\operatorname{S}_{8}}H_{7}(\log
B_{\sigma(j_{s,1})},\ldots,\log B_{\sigma(j_{s,16})})\\\ \in\mathfrak{L}_{\geq
8}(\log\mathcal{H})+\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{H})).$ (35)

Namely, we can take $\alpha_{1}=\frac{1}{15},\alpha_{2}=\frac{8}{15}$, and

$\displaystyle(j_{1,1},j_{1,2},\ldots,j_{1,16})$
$\displaystyle=(1,2,3,4,5,5,6,6,7,7,8,8,1,2,3,4),$
$\displaystyle(j_{2,1},j_{2,2},\ldots,j_{2,16})$
$\displaystyle=(1,2,3,4,5,4,6,7,1,2,8,3,5,6,7,8).$

###### Sketch of proof of Lemma 5.10.

Similar to Lemma 5.8, define the equivalence relation

$x\sim y\iff x-y\in\mathfrak{L}_{\geq 8}(\log\mathcal{H})+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq 2}(\log\mathcal{H})).$

By the Dynkin formula (Lemma 5.5), both the expressions
$\sum_{\sigma\in\operatorname{S}_{8}}H_{7}(\log B_{\sigma(1)},\ldots,\log
B_{\sigma(8)})$ and $\sum_{\sigma\in\operatorname{S}_{8}}H_{7}(\log
B_{\sigma(j_{1})},\ldots,\log B_{\sigma(j_{16})})$ can be expressed as a sum
in the form of

$\sum_{\boldsymbol{j}=(j_{1},\ldots,j_{7})\in\\{1,\ldots,8\\}^{7}}\alpha_{\boldsymbol{j}}\sum_{\sigma\in\operatorname{S}_{8}}\varphi_{7}(\log
B_{\sigma(j_{1})},\ldots,\log B_{\sigma(j_{7})}),$

where $\alpha_{\boldsymbol{j}}$ are rational numbers.

Denote $C_{i}\coloneqq\log B_{i},i=1,\ldots,m$. Since
$\sum_{i=1}^{8}C_{i}\in\mathfrak{L}_{\geq 2}(\log\mathcal{H})$, for any tuple
$\boldsymbol{j}=(j_{1},\ldots,j_{7})\in\\{1,\ldots,8\\}^{7}$, the expression
$\sum_{\sigma\in\operatorname{S}_{8}}\varphi_{7}(C_{\sigma(j_{1})},\ldots,C_{\sigma(j_{7})})$
is equivalent to a linear combination (with rational coefficients) of

$\displaystyle\sum_{i\neq
j}[[[[[[C_{i},C_{j}],C_{j}],C_{i}],C_{i}],C_{i}],C_{i}],$
$\displaystyle\sum_{i\neq
j}[[[[[[C_{i},C_{j}],C_{j}],C_{j}],C_{i}],C_{i}],C_{i}],$

and

$\sum_{\overset{i,j,k}{\text{
distinct}}}[[[[[[C_{i},C_{j}],C_{j}],C_{k}],C_{k}],C_{i}],C_{i}].$

(See Section B for detailed justification.) In fact, using computer
assistance, we show that

$\sum_{\sigma\in\operatorname{S}_{8}}H_{7}(\log B_{\sigma(1)},\ldots,\log
B_{\sigma(8)})\sim\frac{34}{15}\cdot\sum_{i\neq
j}[[[[[[C_{i},C_{j}],C_{j}],C_{i}],C_{i}],C_{i}],C_{i}]\\\
-\frac{34}{45}\cdot\sum_{i\neq
j}[[[[[[C_{i},C_{j}],C_{j}],C_{j}],C_{i}],C_{i}],C_{i}]+\frac{68}{15}\cdot\sum_{\overset{i,j,k}{\text{
distinct}}}[[[[[[C_{i},C_{j}],C_{j}],C_{k}],C_{k}],C_{i}],C_{i}],$
$\sum_{\sigma\in\operatorname{S}_{8}}H_{7}\big{(}\log
B_{\sigma(j_{1,1})},\ldots,\log
B_{\sigma(j_{1,16})}\big{)}\sim\frac{34}{15}\cdot\sum_{i\neq
j}[[[[[[C_{i},C_{j}],C_{j}],C_{i}],C_{i}],C_{i}],C_{i}]\\\
+\frac{238}{45}\cdot\sum_{i\neq
j}[[[[[[C_{i},C_{j}],C_{j}],C_{j}],C_{i}],C_{i}],C_{i}]-\frac{68}{5}\cdot\sum_{\overset{i,j,k}{\text{
distinct}}}[[[[[[C_{i},C_{j}],C_{j}],C_{k}],C_{k}],C_{i}],C_{i}],$

and

$\sum_{\sigma\in\operatorname{S}_{8}}H_{7}\big{(}\log
B_{\sigma(j_{2,1})},\ldots,\log
B_{\sigma(j_{2,16})}\big{)}\sim-\frac{68}{15}\cdot\sum_{i\neq
j}[[[[[[C_{i},C_{j}],C_{j}],C_{i}],C_{i}],C_{i}],C_{i}]\\\
+\frac{34}{45}\cdot\sum_{i\neq
j}[[[[[[C_{i},C_{j}],C_{j}],C_{j}],C_{i}],C_{i}],C_{i}]-\frac{34}{5}\cdot\sum_{\overset{i,j,k}{\text{
distinct}}}[[[[[[C_{i},C_{j}],C_{j}],C_{k}],C_{k}],C_{i}],C_{i}].$

This yields

$\sum_{\sigma\in\operatorname{S}_{8}}H_{7}(\log B_{\sigma(1)},\ldots,\log
B_{\sigma(8)})+\sum_{s=1}^{2}\alpha_{s}\sum_{\sigma\in\operatorname{S}_{8}}H_{7}(\log
B_{\sigma(j_{s,1})},\ldots,\log B_{\sigma(j_{s,16})})\sim 0,$

where $\alpha_{1}=\frac{1}{15},\alpha_{2}=\frac{8}{15}$. The code can be found
at https://doi.org/10.6084/m9.figshare.20124113.v1. ∎

######  Lemma 5.11.

Let $\mathcal{H}\subset\mathsf{UT}(n,\mathbb{Q})$ be a finite set of matrices.
There exist positive rational numbers $\alpha_{1},\ldots,\alpha_{6}$, as well
as, for $s=1,\ldots,6$, permutations $(j_{s,1},j_{s,2},\ldots,j_{s,20})$ of
the tuple $(1,1,2,2,\ldots,10)$, such that for any given set of matrices
$B_{1},\ldots,B_{10}$ in $\mathsf{UT}(n,\mathbb{Q})$ with $\log
B_{i}\in\mathfrak{L}_{\geq 1}(\log\mathcal{H})$ and $\sum_{i=1}^{10}\log
B_{i}\in\mathfrak{L}_{\geq 2}(\log\mathcal{H})$, we have

$\sum_{\sigma\in\operatorname{S}_{10}}H_{9}(\log B_{\sigma(1)},\ldots,\log
B_{\sigma(10)})+\sum_{s=1}^{6}\alpha_{s}\sum_{\sigma\in\operatorname{S}_{10}}H_{9}(\log
B_{\sigma(j_{s,1})},\ldots,\log B_{\sigma(j_{s,20})})\\\ \in\mathfrak{L}_{\geq
10}(\log\mathcal{H})+\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{H})).$ (36)

Namely, we can take
$\alpha_{1}=\frac{44566633}{13702661},\alpha_{2}=\frac{557040}{13702661},\alpha_{3}=\frac{205175}{3915046},\alpha_{4}=\frac{1307207}{13702661},\alpha_{5}=\frac{86275275}{27405322}$,
$\alpha_{6}=\frac{4105194}{1957523}$, and

$\displaystyle(j_{1,1},j_{1,2},\ldots,j_{1,20})$
$\displaystyle=(5,4,7,10,2,8,3,8,1,9,7,6,5,6,2,3,9,10,1,4),$
$\displaystyle(j_{2,1},j_{2,2},\ldots,j_{2,20})$
$\displaystyle=(8,3,5,7,10,6,8,2,1,10,2,4,9,1,5,9,3,6,7,4),$
$\displaystyle(j_{3,1},j_{3,2},\ldots,j_{3,20})$
$\displaystyle=(7,10,2,6,4,9,6,4,1,5,3,5,1,9,3,7,10,2,8,8),$
$\displaystyle(j_{4,1},j_{4,2},\ldots,j_{4,20})$
$\displaystyle=(10,2,2,6,7,1,9,3,9,4,8,7,8,5,5,1,4,10,6,3),$
$\displaystyle(j_{5,1},j_{5,2},\ldots,j_{5,20})$
$\displaystyle=(3,5,10,1,4,8,6,9,3,2,7,6,1,10,9,7,2,4,5,8),$
$\displaystyle(j_{6,1},j_{6,2},\ldots,j_{6,20})$
$\displaystyle=(4,7,2,10,2,1,3,5,8,1,6,9,10,7,6,8,3,5,9,4).$

###### Sketch of proof of Lemma 5.11.

Similar to Lemma 5.8, and Lemma 5.10, denote $C_{i}=\log B_{i}$ for
$i=1,\ldots,m$. Since $\sum_{i=1}^{10}C_{i}\in\mathfrak{L}_{\geq
2}(\log\mathcal{H})$, for any tuple
$\boldsymbol{j}=(j_{1},\ldots,j_{9})\in\\{1,\ldots,10\\}^{9}$, the expression
$\sum_{\sigma\in\operatorname{S}_{10}}\varphi_{9}(C_{\sigma(j_{1})},\ldots,C_{\sigma(j_{9})})$
is equivalent to a linear combination (with rational coefficient) of

$\displaystyle\sum_{i\neq
j}[[[[[[[[C_{i},C_{j}],C_{j}],C_{i}],C_{i}],C_{i}],C_{i}],C_{i}],C_{i}],$
$\displaystyle\sum_{i\neq
j}[[[[[[[[C_{i},C_{j}],C_{j}],C_{j}],C_{i}],C_{i}],C_{i}],C_{i}],C_{i}],$
$\displaystyle\sum_{i\neq
j}[[[[[[[[C_{i},C_{j}],C_{j}],C_{j}],C_{j}],C_{i}],C_{i}],C_{i}],C_{i}],$
$\displaystyle\sum_{\overset{i,j,k}{\text{
distinct}}}[[[[[[[[C_{i},C_{j}],C_{j}],C_{k}],C_{k}],C_{i}],C_{i}],C_{i}],C_{i}],$
$\displaystyle\sum_{\overset{i,j,k}{\text{
distinct}}}[[[[[[[[C_{i},C_{j}],C_{j}],C_{j}],C_{k}],C_{k}],C_{i}],C_{i}],C_{i}],$

and

$\displaystyle\sum_{\overset{i,j,k}{\text{
distinct}}}[[[[[[[[C_{i},C_{j}],C_{j}],C_{k}],C_{k}],C_{k}],C_{i}],C_{i}],C_{i}].$

Similar to the previous lemmas, the rest of the proof can be done by computer
assistance. The code can be found at
https://doi.org/10.6084/m9.figshare.20122979.v1. ∎

Combining Lemma 5.6-5.11, we obtain Proposition 5.3.

See 5.3

###### Proof.

For even $k$, Equation (12) is satisfied by Lemma 5.6 by taking $r=0$ and
pairing each permutation $\sigma$ with its _reversal_ :

$\displaystyle\sum_{\sigma\in\operatorname{S}_{k+1}}H_{k}(\log
B_{\sigma(1)},\ldots,\log B_{\sigma(k+1)})$ $\displaystyle=$
$\displaystyle\;\frac{1}{2}\left(\sum_{\sigma\in\operatorname{S}_{k+1}}H_{k}(\log
B_{\sigma(1)},\ldots,\log
B_{\sigma(k+1)})+\sum_{\sigma\in\operatorname{S}_{k+1}}H_{k}(\log
B_{\operatorname{rev}(\sigma)(1)},\ldots,\log
B_{\operatorname{rev}(\sigma)(k+1)})\right)$ $\displaystyle=$
$\displaystyle\;\frac{1}{2}\sum_{\sigma\in\operatorname{S}_{k+1}}\left(H_{k}(\log
B_{\sigma(1)},\ldots,\log B_{\sigma(k+1)})+H_{k}(\log
B_{\operatorname{rev}(\sigma)(1)},\ldots,\log
B_{\operatorname{rev}(\sigma)(k+1)})\right)$ $\displaystyle=$
$\displaystyle\;0.$

Here $\operatorname{rev}(\sigma)\in\operatorname{S}_{k+1}$ is the reversal of
$\sigma$, meaning
$\operatorname{rev}(\sigma)(i)=\sigma(k+2-i),i=1,\ldots,k+1$. For $k=3,5,7,9$,
Equation (12) is satisfied by Lemma 5.7, 5.8, 5.10 and 5.11 respectively. ∎

###  5.3 Proof of Proposition 5.4

In this subsection, we give the proof of Proposition 5.4.

See 5.4

###### Proof.

For convenience, define $\mathcal{C}_{d+1}\coloneqq\\{0\\}$. We will prove
that, for all $k=2,\ldots,d+1$, the cone $\langle P_{i}(t)\mid
i\in\mathcal{I},t\in\mathbb{Z}_{>0}\rangle_{\mathbb{Q}_{\geq
0}}+\mathcal{C}_{k}$ is equal to $\mathcal{C}_{1}$. Notice that the claim in
the proposition is the case where $k=d+1$. We use induction on $k$.

For $k=2$, since $\boldsymbol{a}_{ki}\in\mathcal{C}_{2}$ for $k\geq 2$, we
have $P_{i}(t)+\mathcal{C}_{2}=t\boldsymbol{a}_{1i}+\mathcal{C}_{2}$, so

$\langle P_{i}(t)\mid
i\in\mathcal{I},t\in\mathbb{Z}_{>0}\rangle_{\mathbb{Q}_{\geq
0}}+\mathcal{C}_{2}=\langle t\boldsymbol{a}_{1i}\mid
i\in\mathcal{I},t\in\mathbb{Z}_{>0}\rangle_{\mathbb{Q}_{\geq
0}}+\mathcal{C}_{2}\overset{\text{(ii)}}{=}\mathcal{C}_{1}.$

For the induction step, suppose now that the cone $\langle P_{i}(t)\mid
i\in\mathcal{I},t\in\mathbb{Z}_{>0}\rangle_{\mathbb{Q}_{\geq
0}}+\mathcal{C}_{k}$ is equal to $\mathcal{C}_{1}$, we want to prove that
$\langle P_{i}(t)\mid
i\in\mathcal{I},t\in\mathbb{Z}_{>0}\rangle_{\mathbb{Q}_{\geq
0}}+\mathcal{C}_{k+1}$ is equal to $\mathcal{C}_{1}$.

By the induction hypothesis, there exist indices
$i_{1},\ldots,i_{m}\in\mathcal{I}$ as well as positive integers
$t_{1},\ldots,t_{m}\in\mathbb{Z}_{>0}$, such that

$\langle P_{i_{j}}(t_{j})\mid j=1,\ldots,m\rangle_{\mathbb{Q}_{\geq
0}}+\mathcal{C}_{k}=\mathcal{C}_{1}.$

Condition (ii) of the proposition shows that there exist indices
$i^{\prime}_{1},\ldots,i^{\prime}_{m^{\prime}}\in\mathcal{I}$ such that

$\langle\boldsymbol{a}_{ki^{\prime}_{j}}\mid
j=1,\ldots,m^{\prime}\rangle_{\mathbb{Q}_{\geq
0}}+\mathcal{C}_{k+1}=\mathcal{C}_{k}.$

Hence

$\langle P_{i_{j}}(t_{j})\mid j=1,\ldots,m\rangle_{\mathbb{Q}_{\geq
0}}+\langle\boldsymbol{a}_{ki^{\prime}_{j}}\mid
j=1,\ldots,m^{\prime}\rangle_{\mathbb{Q}_{\geq
0}}+\mathcal{C}_{k+1}=\mathcal{C}_{1}.$ (37)

We show that there exists $t\in\mathbb{Z}_{>0}$ such that

$\langle P_{i_{j}}(t_{j})\mid j=1,\ldots,m\rangle_{\mathbb{Q}_{\geq
0}}+\langle P_{i^{\prime}_{j}}(t)\mid
j=1,\ldots,m^{\prime}\rangle_{\mathbb{Q}_{\geq
0}}+\mathcal{C}_{k+1}=\mathcal{C}_{1}.$

Suppose the contrary, that for every $t\in\mathbb{Z}_{>0}$,

$\langle P_{i_{j}}(t_{j})\mid j=1,\ldots,m\rangle_{\mathbb{Q}_{\geq
0}}+\langle P_{i^{\prime}_{j}}(t)\mid
j=1,\ldots,m^{\prime}\rangle_{\mathbb{Q}_{\geq
0}}+\mathcal{C}_{k+1}\subsetneq\mathcal{C}_{1}.$

For any $\mathbb{Q}_{\geq 0}$-cone $\mathcal{C}$, define the _normal cone_ of
$\mathcal{C}$ as the set of vectors $\boldsymbol{v}\in V$ such that
$\boldsymbol{v}^{\top}\boldsymbol{c}\leq 0$ for all
$\boldsymbol{c}\in\mathcal{C}$. For every $t$, take a normalized vector
$\boldsymbol{v}_{t}\in\mathcal{C}_{1}$ (meaning the norm of
$\boldsymbol{v}_{t}$ is 1) in the normal cone of $\langle P_{i_{j}}(t_{j})\mid
j=1,\ldots,m\rangle_{\mathbb{Q}_{\geq 0}}+\langle P_{i^{\prime}_{j}}(t)\mid
j=1,\ldots,m^{\prime}\rangle_{\mathbb{Q}_{\geq 0}}+\mathcal{C}_{k+1}$. That
is,

$\boldsymbol{v}_{t}^{\top}P_{i_{j}}(t_{j})\leq 0\text{ for all
}j,\quad\boldsymbol{v}_{t}^{\top}P_{i^{\prime}_{j}}(t)\leq 0\text{ for all
}j,\quad\boldsymbol{v}_{t}\perp\mathcal{C}_{k+1}.$ (38)

Such a vector must exist because $\langle P_{i_{j}}(t_{j})\mid
j=1,\ldots,m\rangle_{\mathbb{Q}_{\geq 0}}+\langle P_{i^{\prime}_{j}}(t)\mid
j=1,\ldots,m^{\prime}\rangle_{\mathbb{Q}_{\geq 0}}+\mathcal{C}_{k+1}$ is a
strict sub-cone of the linear space $\mathcal{C}_{1}$. The $\mathbb{R}$-linear
space $V_{\mathbb{R}}=V\otimes_{\mathbb{Q}}\mathbb{R}$ is finite dimensional
and hence compact. Embed $V$ into $V_{\mathbb{R}}$ canonically, then the
sequence $\\{\boldsymbol{v}_{t}\\}_{t\in\mathbb{Z}_{>0}}$ has a limit point in
$V_{\mathbb{R}}$. Denote by $\boldsymbol{v}_{lim}$ this limit point. As all
the vectors $\boldsymbol{v}_{t}$ are in $\mathcal{C}_{1}$,
$\boldsymbol{v}_{lim}$ must be in
$\mathcal{C}_{1}\otimes_{\mathbb{Q}}\mathbb{R}$. Since the inner product of
$V$ canonically extends to the inner product of $V_{\mathbb{R}}$, taking the
limit of (38), we have

$\boldsymbol{v}_{lim}^{\top}\cdot P_{i_{j}}(t_{j})\leq 0\text{ for all
}j,\quad\boldsymbol{v}_{lim}\perp\mathcal{C}_{k+1},$ (39)

and

$\displaystyle\boldsymbol{v}_{lim}^{\top}\cdot\boldsymbol{a}_{ki^{\prime}_{j}}=\;$
$\displaystyle\boldsymbol{v}_{lim}^{\top}\cdot\lim_{t\rightarrow\infty}\left(\frac{P_{i^{\prime}_{j}}(t)}{t^{k}}-t\boldsymbol{a}_{k+1,i^{\prime}_{j}}-\cdots-t^{d-k}\boldsymbol{a}_{d,i^{\prime}_{j}}\right)$
$\displaystyle=\;$
$\displaystyle\boldsymbol{v}_{lim}^{\top}\cdot\lim_{t\rightarrow\infty}\frac{P_{i^{\prime}_{j}}(t)}{t^{k}}\leq
0,\quad j=1,\ldots,m^{\prime}.$ (40)

The second equality is due to
$\boldsymbol{a}_{k+1,i^{\prime}_{j}},\ldots,\boldsymbol{a}_{d,i^{\prime}_{j}}\in\mathcal{C}_{k+1}\perp\boldsymbol{v}_{lim}$.
Hence, (39) and (5.3) show that
$\boldsymbol{v}_{lim}^{\top}\cdot\boldsymbol{v}\leq 0$ for all
$\boldsymbol{v}$ in the $\mathbb{R}_{\geq 0}$-cone

$\langle P_{i_{j}}(t_{j})\mid j=1,\ldots,m\rangle_{\mathbb{Q}_{\geq
0}}+\langle\boldsymbol{a}_{ki^{\prime}_{j}}\mid
j=1,\ldots,m^{\prime}\rangle_{\mathbb{Q}_{\geq
0}}+\mathcal{C}_{k+1}\overset{\text{Eq.}~{}\eqref{eq:aC}}{=}\mathcal{C}_{1}.$

Since $\mathcal{C}_{1}$ is a linear space, $\boldsymbol{v}_{lim}$ is non-zero
(it has norm one) and is in $\mathcal{C}_{1}\otimes_{\mathbb{Q}}\mathbb{R}$,
this yields a contradiction. We have thus shown that there exists
$t\in\mathbb{Z}_{>0}$ such that

$\langle P_{i_{j}}(t_{j})\mid j=1,\ldots,m\rangle_{\mathbb{Q}_{\geq
0}}+\langle P_{i^{\prime}_{j}}(t)\mid
j=1,\ldots,m^{\prime}\rangle_{\mathbb{Q}_{\geq
0}}+\mathcal{C}_{k+1}=\mathcal{C}_{1}.$

Since $P_{i}(t)\in\mathcal{C}_{1},i\in\mathcal{I},t\in\mathbb{Z}_{>0}$, this
means

$\langle P_{i}(t)\mid
i\in\mathcal{I},t\in\mathbb{Z}_{>0}\rangle_{\mathbb{Q}_{\geq
0}}+\mathcal{C}_{k+1}=\mathcal{C}_{1},$

concluding the induction.

Finally, take $k=d+1$. This yields $\langle P_{i}(t)\mid
i\in\mathcal{I},t\in\mathbb{Z}_{>0}\rangle_{\mathbb{Q}_{\geq
0}}=\mathcal{C}_{1}$. ∎

###  5.4 Full proof of Theorem 4.2

In this subsection, with Propositions 5.2 \- 5.4 at our disposal, we will show
the proof of Theorem 4.2. First, we need the following lemma.

######  Lemma 5.12.

Let $\mathcal{H}$ be a finite subset of the Lie algebra $\mathfrak{u}(n)$. Let
$W,V$ be linear subspaces of $\mathfrak{L}_{\geq 1}(\mathcal{H})$ such that
$W+\mathfrak{L}_{\geq 2}(V)=V$, then $\mathfrak{L}_{\geq
2}(W)=\mathfrak{L}_{\geq 2}(V)$.

###### Proof.

Since $W+\mathfrak{L}_{\geq 2}(V)=V$, we have $W\subseteq V$, and thus
$\mathfrak{L}_{\geq 2}(W)\subseteq\mathfrak{L}_{\geq 2}(V)$. Therefore, it
suffices to prove the opposite inclusion $\mathfrak{L}_{\geq
2}(W)\supseteq\mathfrak{L}_{\geq 2}(V)$.

Note that since $W,V$ are linear spaces, the sets $[V]_{k},[W]_{k}$ are also
linear spaces for all $k=1,\ldots,n$. We use induction on $k$ to show that

$[V]_{k}\subseteq[W]_{k}+\mathfrak{L}_{\geq k+1}(V).$ (41)

For $k=1$ this immediately results from the equation $W+\mathfrak{L}_{\geq
2}(V)=V$. Suppose Equation (41) hold for $k-1$. Then, take any elements $x\in
V,y\in[V]_{k-1}$, by the induction hypothesis and by $W+\mathfrak{L}_{\geq
2}(V)=V$, there exist $x^{\prime}\in W,y^{\prime}\in[W]_{k-1}$, such that
$x-x^{\prime}\in\mathfrak{L}_{\geq 2}(V),y-y^{\prime}\in\mathfrak{L}_{\geq
k}(V)$. Then,

$\displaystyle[y,x]$
$\displaystyle=[y^{\prime},x^{\prime}]+[y-y^{\prime},x^{\prime}]+[y,x-x^{\prime}]$
$\displaystyle\in[[W]_{k-1},W]+[\mathfrak{L}_{\geq
k}(V),W]+[[V]_{k-1},\mathfrak{L}_{\geq 2}(V)]$
$\displaystyle\subseteq[W]_{k}+[\mathfrak{L}_{\geq
k}(V),V]+[\mathfrak{L}_{\geq k-1}(V),\mathfrak{L}_{\geq 2}(V)]$
$\displaystyle\subseteq[W]_{k}+\mathfrak{L}_{\geq k+1}(V).$

Taking the linear span for all $x\in V,y\in[V]_{k-1}$ shows
$[V]_{k}\subseteq[W]_{k}+\mathfrak{L}_{\geq k+1}(V)$, concluding the
induction.

Now, for any $l=2,\ldots,d$, take the sum of Equation (41) for $k=l,\ldots,d$,
we have

$\mathfrak{L}_{\geq l}(V)=\sum_{k\geq l}[V]_{k}\subseteq\sum_{k\geq
l}[W]_{k}+\sum_{k\geq l}\mathfrak{L}_{\geq k+1}(V)=\mathfrak{L}_{\geq
l}(W)+\mathfrak{L}_{\geq l+1}(V).$

Therefore,

$\displaystyle\mathfrak{L}_{\geq 2}(V)$ $\displaystyle\subseteq$
$\displaystyle\;\mathfrak{L}_{\geq 2}(W)+\mathfrak{L}_{\geq 3}(V)$
$\displaystyle\subseteq$ $\displaystyle\;\mathfrak{L}_{\geq
2}(W)+\mathfrak{L}_{\geq 3}(W)+\mathfrak{L}_{\geq 4}(V)$ $\displaystyle\vdots$
$\displaystyle\subseteq$ $\displaystyle\;\mathfrak{L}_{\geq
2}(W)+\mathfrak{L}_{\geq 3}(W)+\cdots+\mathfrak{L}_{\geq n}(W)$
$\displaystyle=$ $\displaystyle\;\mathfrak{L}_{\geq 2}(W).$

This shows the inclusion $\mathfrak{L}_{\geq 2}(W)\supseteq\mathfrak{L}_{\geq
2}(V)$. ∎

Let $\mathcal{G}=\\{A_{1},\ldots,A_{K}\\}$ be a finite alphabet of elements in
$\mathsf{UT}(n,\mathbb{Q})$. For any vector
$\boldsymbol{\ell}=(\ell_{1},\ldots,\ell_{K})\in\mathbb{Z}_{\geq 0}^{K}$,
define inductively the following $\mathbb{Q}$-cones
$\mathcal{R}_{k}(\boldsymbol{\ell})$ for $k=11,10,\ldots,2$:

$\displaystyle\mathcal{R}_{11}(\boldsymbol{\ell})\coloneqq\\{0\\},$ (42)
$\displaystyle\mathcal{R}_{k}(\boldsymbol{\ell})\coloneqq\mathcal{R}_{k+1}(\boldsymbol{\ell})+\bigg{\langle}H_{k}(\log
B_{1},\ldots,\log
B_{m})\;\bigg{|}\;B_{i}\in\mathcal{G}^{*},\sum_{i=1}^{m}\operatorname{PI}^{\mathcal{G}}(B_{i})\in\\{\boldsymbol{\ell},2\boldsymbol{\ell}\\}\bigg{\rangle}_{\mathbb{Q}_{\geq
0}}.$ (43)

That is, $\mathcal{R}_{k}(\boldsymbol{\ell})$ is the $\mathbb{Q}_{\geq
0}$-cone generated by the elements $H_{j}(\log B_{1},\ldots,\log B_{m}),j\geq
k$, where $B_{1},\ldots,B_{m}$ are _words_ in $\mathcal{G}^{*}$, and the
Parikh images of $B_{i}$ sum up to $\boldsymbol{\ell}$ or
$2\boldsymbol{\ell}$. Recall the definition of

$\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}\coloneqq\\{\log
A_{i}\mid i\in\operatorname{supp}(\boldsymbol{\ell})\\}$

as the set of logarithm of matrices in $\mathcal{G}$ whose index appears in
$\operatorname{supp}(\boldsymbol{\ell})$. Combining Proposition 5.2 and 5.3,
we can show the following proposition that characterizes the cones
$\mathcal{R}_{k}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})$ up
to the quotient by $\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))$.

######  Proposition 5.13.

Let $\mathcal{G}=\\{A_{1},\ldots,A_{K}\\}$ be a finite set of matrices in
$\mathsf{UT}(n,\mathbb{Q})$ that satisfies $[\log\mathcal{G}]_{11}=\\{0\\}$.
Let $\boldsymbol{\ell}=(\ell_{1},\ldots,\ell_{K})\in\mathbb{Z}_{\geq 0}^{K}$
be a non-zero vector that satisfies $\sum_{i=1}^{K}\ell_{i}\log
A_{i}\in\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})$ as well as
$\ell_{i}\geq 10$ for all $i\in\operatorname{supp}(\boldsymbol{\ell})$.
Consider the quotient linear space $\mathfrak{u}(n)/\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))$.

For any set $\mathcal{C}\subseteq\mathfrak{u}(n)$, denote by
$\overline{\mathcal{C}}$ the subset of $\mathfrak{u}(n)/\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))$ consisting of
the equivalence classes $c+\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})),c\in\mathcal{C}$.
Then for all $k\leq 11$, the cone
$\overline{\mathcal{R}_{k}(\boldsymbol{\ell})}$ is equal to the linear space
$\overline{\mathfrak{L}_{\geq
k}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})}$.

###### Proof.

We show that the claim is true for $k=11,10,\ldots,2,$ using induction with
reverse order on $k$. For $k=11$, we have
$\overline{\mathcal{R}_{11}(\boldsymbol{\ell})}=\overline{\mathfrak{L}_{\geq
11}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})}=\\{0\\}$
because $[\log\mathcal{G}]_{11}=\\{0\\}$. Now for some $10\geq k\geq 2$,
suppose
$\overline{\mathcal{R}_{k+1}(\boldsymbol{\ell})}=\overline{\mathfrak{L}_{\geq{k+1}}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})}$
by induction hypothesis. We will show that
$\overline{\mathcal{R}_{k}(\boldsymbol{\ell})}=\overline{\mathfrak{L}_{\geq
k}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})}$.

First, we show that for any
$i_{1},i_{2},\ldots,i_{k}\in\operatorname{supp}(\boldsymbol{\ell})$, we have

$[\ldots[[\log A_{i_{1}},\log A_{i_{2}}],\log A_{i_{3}}],\ldots,\log
A_{i_{k}}]\in\mathcal{R}_{k}(\boldsymbol{\ell})+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})).$

Take a tuple of words $(B^{\prime}_{1},\ldots,B^{\prime}_{k+1})$ with
$B^{\prime}_{1}=A_{i_{1}},B^{\prime}_{2}=A_{i_{2}},\ldots,B^{\prime}_{k}=A_{i_{k}},B^{\prime}_{k+1}\in\mathcal{G}^{*}$,
such that
$\sum_{i=1}^{k+1}\operatorname{PI}^{\mathcal{G}}(B^{\prime}_{i})=\boldsymbol{\ell}$.
Such a tuple can always be found because $\boldsymbol{\ell}$ satisfies
$\ell_{i}\geq 10\geq k,i\in\operatorname{supp}(\boldsymbol{\ell})$. For this
tuple, the BCH formula gives us

$\sum_{i=1}^{k+1}\log B^{\prime}_{i}\in\sum_{i=1}^{K}\ell_{i}\log
A_{i}+\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})\subseteq\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}).$

Hence, for any $\sigma\in\operatorname{S}_{k}$, Proposition 5.3 shows that

$\displaystyle-H_{k}\left(\log B^{\prime}_{\sigma(1)},\log
B^{\prime}_{\sigma(2)},\ldots,\log B^{\prime}_{\sigma(k)},\log
B^{\prime}_{k+1}\right)$ $\displaystyle\in$
$\displaystyle\bigg{\langle}H_{k}(\log B_{1},\ldots,\log
B_{k+1})\;\bigg{|}\;B_{i}\in\mathcal{G}^{*},\sum_{i=1}^{k+1}\operatorname{PI}^{\mathcal{G}}(B_{i})=\boldsymbol{\ell}\bigg{\rangle}_{\mathbb{Q}_{\geq
0}}$ $\displaystyle\quad+\bigg{\langle}H_{k}(\log B_{1},\ldots,\log
B_{2k+2})\;\bigg{|}\;B_{i}\in\mathcal{G}^{*},\sum_{i=1}^{2k+2}\operatorname{PI}^{\mathcal{G}}(B_{i})=2\boldsymbol{\ell}\bigg{\rangle}_{\mathbb{Q}_{\geq
0}}$ $\displaystyle\quad+\mathfrak{L}_{\geq
k+1}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))$
$\displaystyle\subseteq$
$\displaystyle\;\mathcal{R}_{k}(\boldsymbol{\ell})+\mathfrak{L}_{\geq
k+1}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))$
$\displaystyle=$
$\displaystyle\;\mathcal{R}_{k}(\boldsymbol{\ell})+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})).$ (44)

The last equality come from $\overline{\mathfrak{L}_{\geq
k+1}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})}=\overline{\mathcal{R}_{k+1}(\boldsymbol{\ell})}\subseteq\overline{\mathcal{R}_{k}(\boldsymbol{\ell})}$
by the induction hypothesis.

Hence, by Proposition 5.2,

$\displaystyle[\ldots[[\log A_{i_{1}},\log A_{i_{2}}],\log
A_{i_{3}}],\ldots,\log A_{i_{k}}]$ $\displaystyle=$
$\displaystyle\;[\ldots[[\log B^{\prime}_{1},\log B^{\prime}_{2}],\log
B^{\prime}_{3}],\ldots,\log B^{\prime}_{k}]$ $\displaystyle=$
$\displaystyle\;\sum_{\sigma\in\operatorname{S}_{k}}\mu(\sigma)H_{k}(\log
B^{\prime}_{\sigma(1)},\log B^{\prime}_{\sigma(2)},\ldots,\log
B^{\prime}_{\sigma(k)},\log B^{\prime}_{k+1})$ $\displaystyle\in$
$\displaystyle\;\mathcal{R}_{k}(\boldsymbol{\ell})+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})).$

The last inclusion comes from the fact that both the expressions $H_{k}(\log
B^{\prime}_{\sigma(1)},\ldots,\log B^{\prime}_{\sigma(k)},\log
B^{\prime}_{k+1})$ and $-H_{k}(\log B^{\prime}_{\sigma(1)},\ldots,\log
B^{\prime}_{\sigma(k)},\log B^{\prime}_{k+1})$ are in the cone
$\mathcal{R}_{k}(\boldsymbol{\ell})+\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))$ (by Equation
(5.4)). Therefore for every $\sigma\in\operatorname{S}_{k}$, regardless of the
sign which $\mu(\sigma)$ takes, the summand $\mu(\sigma)H_{k}(\log
B^{\prime}_{\sigma(1)},\ldots,\log B^{\prime}_{\sigma(k)},\log
B^{\prime}_{k+1})$ is in the cone
$\mathcal{R}_{k}(\boldsymbol{\ell})+\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))$.

Therefore,
$[\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}]_{k}\subseteq\mathcal{R}_{k}(\boldsymbol{\ell})+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))$; that is,
$\overline{[\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}]_{k}}\subseteq\overline{\mathcal{R}_{k}(\boldsymbol{\ell})}$.
And since $\overline{\mathfrak{L}_{\geq
k+1}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})}\subseteq\overline{\mathcal{R}_{k+1}(\boldsymbol{\ell})}\subseteq\overline{\mathcal{R}_{k}(\boldsymbol{\ell})}$
by the induction hypothesis, we have

$\displaystyle\overline{\mathfrak{L}_{\geq
k}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})}=\overline{\left\langle[\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}]_{k}\right\rangle_{\mathbb{Q}}}+\overline{\mathfrak{L}_{\geq
k+1}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})}\subseteq\overline{\mathcal{R}_{k}(\boldsymbol{\ell})}.$
(45)

Next, take any tuple
$(B_{1},\ldots,B_{m})\in\left(\mathcal{G}^{*}\right)^{m}$,
$\sum_{i=1}^{m}\operatorname{PI}^{\mathcal{G}}(B_{i})=\boldsymbol{\ell}$ or
$2\boldsymbol{\ell}$. Note that $\log B_{i}\in\mathfrak{L}_{\geq
1}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}),i=1,\ldots,m,$ by
the BCH formula. Hence, the expression $H_{k}(\log B_{1},\ldots,\log B_{m})$
can be written as a linear combination of elements in
$\left[\mathfrak{L}_{\geq
1}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})\right]_{k}$. That
is,

$\mathcal{R}_{k}(\boldsymbol{\ell})\subseteq\left\langle\left[\mathfrak{L}_{\geq
1}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})\right]_{k}\right\rangle_{\mathbb{Q}}+\mathcal{R}_{k+1}(\boldsymbol{\ell})\\\
\subseteq\mathfrak{L}_{\geq
k}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})+\mathcal{R}_{k+1}(\boldsymbol{\ell})=\mathfrak{L}_{\geq{k+1}}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}).$
(46)

Combining (45) and (46) we have the desired equality. This concludes the
induction and thus the whole proof. ∎

We now prove Theorem 4.2. Although part (i) has already been proven when the
theorem is first stated, we will restate it for the sake of completeness.

See 4.2

###### Proof.

(i) Let $w$ be a word with
$\operatorname{PI}^{\mathcal{G}}(w)=\boldsymbol{\ell}$. Write
$w=B_{1}B_{2}\cdots B_{m}$ $B_{i}\in\mathcal{G},i=1,\ldots,m$. Regrouping by
letters, we have $\sum_{i=1}^{K}\ell_{i}\log A_{i}=\sum_{i=1}^{m}\log B_{i}$.

If $\log w=0$, then by the BCH formula, we have

$\sum_{i=1}^{m}\log B_{i}+\sum_{k=2}^{n-1}H_{k}(\log B_{1},\ldots,\log
B_{m})=\log(B_{1}B_{2}\cdots B_{m})=0.$

The higher order terms $H_{k},k\geq n$ vanish because
$[\log\mathcal{G}]_{n}=\\{0\\}$ (a consequence of
$\mathcal{G}\subseteq\mathsf{UT}(n,\mathbb{Q})$). Therefore,
$\sum_{i=1}^{K}\ell_{i}\log A_{i}=\sum_{i=1}^{m}\log
B_{i}=-\sum_{k=2}^{n-1}H_{k}(\log B_{1},\ldots,\log B_{m})$.

Since the Parikh image of the word $B_{1}\cdots B_{m}$ is $\boldsymbol{\ell}$,
the matrices $B_{i}$ all lie in the subset $\\{A_{i}\mid
i\in\operatorname{supp}(\boldsymbol{\ell})\\}$ of $\mathcal{G}$. Therefore,
$\log B_{i}\in\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}$ for
all $i$. By Theorem 3.8, for all $k\geq 2$ we have $-H_{k}(\log
B_{1},\ldots,\log B_{m})\in\big{\langle}[\\{\log B_{i}\mid
i=1,\ldots,m\\}]_{k}\big{\rangle}_{\mathbb{Q}}\subseteq\mathfrak{L}_{\geq
k}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})\subseteq\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})$. Therefore, we
have $\sum_{i=1}^{K}\ell_{i}\log A_{i}=-\sum_{k=2}^{n-1}H_{k}(\log
B_{1},\ldots,\log B_{m})\in\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}).$

(ii) Suppose condition (5) hold for the vector $\boldsymbol{\ell}$. Resonating
Example 4.1, our proof for (ii) proceeds in four steps. Now we give an
overview of each step. As the first step, we want to construct some matrices
$A^{\prime}_{1},\ldots,A^{\prime}_{K^{\prime}}\in\langle\mathcal{G}\rangle$,
such that

$\langle\log A^{\prime}_{i}\mid i=1,\ldots,K^{\prime}\rangle_{\mathbb{Q}_{\geq
0}}+\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))=\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})).$ (47)

The candidates for the matrices
$A^{\prime}_{1},\ldots,A^{\prime}_{K^{\prime}}$ are of the form
$B_{1}^{t}\cdots B_{m}^{t}$, where $m\geq 1$, $t\in\mathbb{Z}_{>0}$,
$B_{i}\in\mathcal{G}^{*},i=1,\ldots,m$ and
$\sum_{i=1}^{m}\operatorname{PI}^{\mathcal{G}}(B_{i})=\boldsymbol{\ell}$ or
$2\boldsymbol{\ell}$. The general strategy is to invoke Proposition 5.4 while
using Proposition 5.13 to guarantee that the conditions (i) and (ii) of
Proposition 5.4 are satisfied.

As the second step, we work in the new alphabet
$\mathcal{G}^{\prime}=\\{A^{\prime}_{1},\ldots,A^{\prime}_{K^{\prime}}\\}$ of
matrices found in the previous step. We want to fabricate some matrices
$A^{\prime\prime}_{1},\ldots,A^{\prime\prime}_{K^{\prime\prime}}\in\langle\mathcal{G}^{\prime}\rangle$,
such that

$\langle\log A^{\prime\prime}_{i}\mid
i=1,\ldots,K^{\prime\prime}\rangle_{\mathbb{Q}_{\geq 0}}+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})))\\\
=\mathfrak{L}_{\geq 2}\left(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})\right)+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))).$ (48)

The candidates for the matrices
$A^{\prime\prime}_{1},\ldots,A^{\prime\prime}_{K^{\prime\prime}}$ are of the
form $B_{1}^{t}\cdots B_{m}^{t}$, where
$B_{i}\in\left(\mathcal{G}^{\prime}\right)^{*},i=1,\ldots,m$. The idea is to
again invoke Proposition 5.4 and to use Proposition 5.13 for the new alphabet
$\mathcal{G}^{\prime}$ and a suitable vector $\boldsymbol{\ell}^{\prime}$.

As the third step, we work in the new alphabet
$\mathcal{G}^{\prime\prime}=\\{A^{\prime\prime}_{1},\ldots,A^{\prime\prime}_{K^{\prime\prime}}\\}$
of matrices found in the previous step. We want to fabricate some matrices
$A^{\prime\prime\prime}_{1},\ldots,A^{\prime\prime\prime}_{K^{\prime\prime\prime}}\in\langle\mathcal{G}^{\prime\prime}\rangle$,
such that

$\langle\log A^{\prime\prime\prime}_{i}\mid
i=1,\ldots,K^{\prime\prime}\rangle_{\mathbb{Q}_{\geq 0}}=\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))).$ (49)

(Note that $\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))))=\\{0\\}$.) The
candidates for
$A^{\prime\prime\prime}_{1},\ldots,A^{\prime\prime\prime}_{K^{\prime\prime\prime}}$
are of the form $B_{1}^{t}\cdots B_{m}^{t}$, where
$B_{i}\in\left(\mathcal{G}^{\prime\prime}\right)^{*},i=1,\ldots,m$. The idea
is to again invoke Proposition 5.4 and to use Proposition 5.13 for the new
alphabet $\mathcal{G}^{\prime\prime}$ and a suitable vector
$\boldsymbol{\ell}^{\prime\prime}$.

As the fourth and last step, we work in the new alphabet
$\mathcal{G}^{\prime\prime\prime}=\\{A^{\prime\prime\prime}_{1},\ldots,A^{\prime\prime\prime}_{K^{\prime\prime\prime}}\\}$
of matrices found in the previous step. We then observe that the matrices
$A^{\prime\prime\prime}_{1},\ldots,A^{\prime\prime\prime}_{K^{\prime\prime\prime}}$
commute with each other, because $\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))))=\\{0\\}$.
Hence, it is very easy to search for the desired non-empty word
$w\in\left(\mathcal{G}^{\prime\prime\prime}\right)^{*}$ with $\log w=0$.

We now give the detailed account of each step.

  1. (1)

Find matrices
$A^{\prime}_{1},\ldots,A^{\prime}_{K^{\prime}}\in\langle\mathcal{G}\rangle$
satisfying condition (47). Since the right hand side of Equation (5) is a
linear space, we can replace $\boldsymbol{\ell}$ by $10\boldsymbol{\ell}$, and
thus suppose $\boldsymbol{\ell}$ satisfy $\ell_{i}\geq
10,i\in\operatorname{supp}(\boldsymbol{\ell})$. Since $\mathbb{Z}_{>0}\cdot
10\boldsymbol{\ell}\subseteq\mathbb{Z}_{>0}\cdot\boldsymbol{\ell}$, the
resulting word $w$ will still satisfy
$\operatorname{PI}^{\mathcal{G}}(w)\in\mathbb{Z}_{>0}\cdot\boldsymbol{\ell}$.

Since $\boldsymbol{\ell}$ satisfies $\sum_{i=1}^{K}\ell_{i}\log
A_{i}\in\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})$, we are able to
use Proposition 5.13 for the vector $\boldsymbol{\ell}$. Our aim is to apply
Proposition 5.4 in the quotient space

$V\coloneqq\mathfrak{u}(n)/\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})),$

for the index set

$\mathcal{I}\coloneqq\bigg{\\{}(B_{1},\ldots,B_{m})\;\bigg{|}\;m\geq
1,B_{i}\in\mathcal{G}^{*},\sum_{i=1}^{m}\operatorname{PI}^{\mathcal{G}}(B_{i})\in\\{\boldsymbol{\ell},2\boldsymbol{\ell}\\}\bigg{\\}},$

that is, the set of tuples of words whose concatenation has Parikh image
$\boldsymbol{\ell}$ or $2\boldsymbol{\ell}$. For any element
$\boldsymbol{x}\in\mathfrak{u}(n)$, denote by
$\overline{\boldsymbol{x}}\coloneqq\boldsymbol{x}+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})$ its equivalence
class in

$V=\mathfrak{u}(n)/\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})).$

For any tuple $b=(B_{1},\ldots,B_{m})\in\mathcal{I}$, consider the vectors in
$V$:

$\displaystyle\boldsymbol{a}_{1b}$
$\displaystyle\coloneqq\overline{\sum_{i=1}^{m}\log B_{i}},$
$\displaystyle\boldsymbol{a}_{kb}$ $\displaystyle\coloneqq\overline{H_{k}(\log
B_{1},\ldots,\log B_{m})},\quad k=2,\ldots,10,$

and

$P_{b}(t)\coloneqq\overline{\log(B_{1}^{t}\cdots
B_{m}^{t})}=t\boldsymbol{a}_{1b}+\sum_{k=2}^{10}t^{k}\boldsymbol{a}_{kb},$

coming from the BCH formula for $B_{1}^{t},\ldots,B_{m}^{t}$. We now apply
Proposition 5.4 to these vectors: we need to verify that the cones
$\mathcal{C}_{k},k=10,\ldots,1$ as defined in Proposition 5.4 are indeed
linear spaces. Proposition 5.13 shows that

$\mathcal{C}_{10}=\langle\boldsymbol{a}_{{10}b}\mid
b\in\mathcal{I}\rangle_{\mathbb{Q}_{\geq
0}}=\overline{\mathcal{R}_{10}(\boldsymbol{\ell})}$

and

$\mathcal{C}_{k}=\langle\boldsymbol{a}_{kb}\mid
b\in\mathcal{I}\rangle_{\mathbb{Q}_{\geq
0}}+\mathcal{C}_{k+1}=\overline{\mathcal{R}_{k}(\boldsymbol{\ell})},\quad
k=9,\ldots,2,$

are linear subspaces of $\mathfrak{u}(n)/\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})$. Furthermore, by
the condition
$\sum_{i=1}^{K}\ell_{i}\log A_{i}\in\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})$, we have

$\boldsymbol{a}_{1b}\in\left\\{\overline{\sum_{i=1}^{K}\ell_{i}\log
A_{i}},2\cdot\overline{\sum_{i=1}^{K}\ell_{i}\log
A_{i}}\right\\}\subseteq\overline{\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})}=\overline{\mathcal{R}_{2}(\boldsymbol{\ell})}$

for all $b\in\mathcal{I}$. Hence,

$\mathcal{C}_{1}=\langle\boldsymbol{a}_{1b}\mid
b\in\mathcal{I}\rangle_{\mathbb{Q}_{\geq
0}}+\mathcal{C}_{2}=\overline{\mathcal{R}_{2}(\boldsymbol{\ell})}=\overline{\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})}$

is also a linear space. The conditions (i) and (ii) in Proposition 5.4 are
thus satisfied. We can thus apply Proposition 5.4, which yields

$\left\langle P_{b}(t)\mid b\in\mathcal{I},t\in\mathbb{Z}_{\geq
0}\right\rangle_{\mathbb{Q}_{\geq
0}}=\mathcal{C}_{1}=\overline{\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})}.$

In other words,

$\bigg{\langle}\overline{\log(B_{1}^{t}\cdots
B_{m}^{t})}\;\bigg{|}\;t\in\mathbb{Z}_{\geq 0},m\geq
1,B_{i}\in\mathcal{G}^{*},\sum_{i=1}^{m}\operatorname{PI}^{\mathcal{G}}(B_{i})\in\\{\boldsymbol{\ell},2\boldsymbol{\ell}\\}\bigg{\rangle}_{\mathbb{Q}_{\geq
0}}\\\ =\overline{\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})}.$

Since $\mathfrak{u}(n)/\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))$ is of finite
dimension, this shows that there exist $K^{\prime}>0$ tuples of words
$(B_{11},\ldots,B_{1m})$, $\ldots$, $(B_{K^{\prime}1},\ldots,B_{K^{\prime}m})$
with $\sum_{i=1}^{m}\operatorname{PI}^{\mathcal{G}}(B_{ji})=\boldsymbol{\ell}$
or $2\boldsymbol{\ell}$ for all $j\in\\{1,\ldots,K^{\prime}\\}$, as well as
positive integers $t_{1},\ldots,t_{K^{\prime}}\in\mathbb{Z}_{>0}$, such that

$\langle\log(B_{i1}^{t_{i}}\cdots B_{im}^{t_{i}})\mid
i=1,\ldots,K^{\prime}\rangle_{\mathbb{Q}_{\geq 0}}+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))\\\
=\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})).$

Hence, the matrices $A^{\prime}_{i}=B_{i1}^{t_{i}}\cdots
B_{im}^{t_{i}},i=1,\ldots,K^{\prime}$ satisfy the Equation (47). Define a new
alphabet
$\mathcal{G}^{\prime}=\\{A^{\prime}_{1},\ldots,A^{\prime}_{K^{\prime}}\\}\subseteq
G$.

  2. (2)

Find matrices
$A^{\prime\prime}_{1},\ldots,A^{\prime\prime}_{K^{\prime\prime}}\in\langle\mathcal{G}^{\prime}\rangle$
satisfying condition (48). Since the right hand side of Equation (47) is a
linear space, we have $-\log A^{\prime}_{j}\in\langle\log A^{\prime}_{i}\mid
i=1,\ldots,K^{\prime}\rangle_{\mathbb{Q}_{\geq 0}}+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))$ for
$j=1,\ldots,K^{\prime}$. Hence, there exists a non-zero vector
$\boldsymbol{\ell}^{\prime}=(\ell^{\prime}_{1},\ldots,\ell^{\prime}_{K^{\prime}})$
in $\mathbb{Z}_{\geq 0}^{K^{\prime}}$, satisfying
$\operatorname{supp}(\boldsymbol{\ell}^{\prime})=\\{1,\ldots,K^{\prime}\\}$,
$\ell^{\prime}_{i}\geq 10$ for all $i\in\\{1,\ldots,K^{\prime}\\}$, and

$\sum_{i=1}^{K^{\prime}}\ell^{\prime}_{i}\log
A^{\prime}_{i}\in\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})).$ (50)

Define
$\log\mathcal{G}^{\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime})}\coloneqq\\{\log
A^{\prime}_{i}\mid
i\in\operatorname{supp}(\boldsymbol{\ell}^{\prime})\\}=\log\mathcal{G}^{\prime}$,
because
$\operatorname{supp}(\boldsymbol{\ell}^{\prime})=\\{1,\ldots,K^{\prime}\\}$.
First, we claim that

$\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))=\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime})}).$
(51)

Indeed, Equation (47) shows that

$\left\langle\log\mathcal{G}^{\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime})}\right\rangle_{\mathbb{Q}}+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))\\\
=\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))=\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}).$

Applying Lemma 5.12 with
$W=\left\langle\log\mathcal{G}^{\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime})}\right\rangle_{\mathbb{Q}},V=\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})$ to the above
equation yields the equality (51). Consequently, we have

$\sum_{i=1}^{K^{\prime}}\ell^{\prime}_{i}\log
A^{\prime}_{i}\in\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime})})$

by (50). Apply Proposition 5.13 for the alphabet $\mathcal{G}^{\prime}$ and
the vector $\boldsymbol{\ell}^{\prime}$, then we have that, in the quotient
space

$\mathfrak{u}(n)/\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime})})),$

the equations
$\overline{\mathcal{R}_{k}(\boldsymbol{\ell}^{\prime})}=\overline{\mathfrak{L}_{\geq
k}(\log\mathcal{G}^{\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime})})},k=10,\ldots,2$,
hold. Then, applying Proposition 5.4 in the quotient linear space

$V\coloneqq\mathfrak{u}(n)/\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime})}))$

as in the previous step, we have

$\bigg{\langle}\overline{\log(B_{1}^{t}\cdots
B_{m}^{t})}\;\bigg{|}\;t\in\mathbb{Z}_{\geq 0},m\geq
1,B_{i}\in\left(\mathcal{G}^{\prime}\right)^{*},\sum_{i=1}^{m}\operatorname{PI}^{\mathcal{G}^{\prime}}(B_{i})\in\\{\boldsymbol{\ell}^{\prime},2\boldsymbol{\ell}^{\prime}\\}\bigg{\rangle}_{\mathbb{Q}_{\geq
0}}\\\ =\overline{\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime})})}.$

Hence, there exist $K^{\prime\prime}>0$ tuples of words
$(B^{\prime}_{11},\ldots,B^{\prime}_{1m})$, $\ldots$,
$(B^{\prime}_{K^{\prime\prime}1},\ldots,B^{\prime}_{K^{\prime\prime}m})$ in
$\left(\mathcal{G}^{\prime}\right)^{*}$ with
$\sum_{i=1}^{m}\operatorname{PI}^{\mathcal{G}^{\prime}}(B^{\prime}_{ji})=\boldsymbol{\ell}^{\prime}$
or $2\boldsymbol{\ell}^{\prime}$ for all $j$, as well as positive integers
$t^{\prime}_{1},\ldots,t^{\prime}_{K^{\prime\prime}}\in\mathbb{Z}_{>0}$, such
that

$\langle\log({B^{\prime}}_{i1}^{t^{\prime}_{i}}\cdots{B^{\prime}}_{im}^{t^{\prime}_{i}})\mid
i=1,\ldots,K^{\prime\prime}\rangle_{\mathbb{Q}_{\geq 0}}+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime})}))\\\
=\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime})})+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime})})).$
(52)

Substituting with $\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime})})=\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))$, Equation (52)
can be rewritten as

$\langle\log(B_{i1}^{t^{\prime}_{i}}\cdots B_{im}^{t^{\prime}_{i}})\mid
i=1,\ldots,K^{\prime\prime}\rangle_{\mathbb{Q}_{\geq 0}}+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})))\\\
=\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))).$

Hence, the matrices
$A^{\prime\prime}_{i}={B^{\prime}}_{i1}^{t^{\prime}_{i}}\cdots{B^{\prime}}_{im}^{t^{\prime}_{i}},i=1,\ldots,K^{\prime\prime}$
satisfy the Equation (48). Define the new alphabet
$\mathcal{G}^{\prime\prime}=\\{A^{\prime\prime}_{1},\ldots,A^{\prime\prime}_{K^{\prime\prime}}\\}$.

  3. (3)

Find matrices
$A^{\prime\prime\prime}_{1},\ldots,A^{\prime\prime\prime}_{K^{\prime\prime\prime}}\in\langle\mathcal{G}^{\prime\prime}\rangle$
satisfying condition (49). Similar to the previous step, one can find a vector
$\boldsymbol{\ell}^{\prime\prime}=(\ell^{\prime\prime}_{1},\ldots,\ell^{\prime\prime}_{K^{\prime\prime}})\in\mathbb{Z}_{\geq
0}^{K^{\prime\prime}}$, satisfying
$\operatorname{supp}(\boldsymbol{\ell}^{\prime\prime})=\\{1,\ldots,K^{\prime\prime}\\}$,
$\ell^{\prime\prime}_{i}\geq 10,i=1,\ldots,K^{\prime\prime}$, and

$\sum_{i=1}^{K^{\prime\prime}}\ell^{\prime\prime}_{i}\log
A^{\prime\prime}_{i}\in\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime})})).$

Define
$\log\mathcal{G}^{\prime\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime\prime})}\coloneqq\\{\log
A^{\prime\prime}_{i}\mid
i\in\operatorname{supp}(\boldsymbol{\ell}^{\prime\prime})\\}=\log\mathcal{G}^{\prime\prime}$.
As in the previous step, we have

$\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime\prime})})=\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime})})).$

Combining it with $\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime})})=\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))$, we have

$\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime\prime})})=\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))).$

Apply Proposition 5.13 for the alphabet $\mathcal{G}^{\prime\prime}$ and the
vector $\boldsymbol{\ell}^{\prime\prime}$, then we have that, in the quotient
space $\mathfrak{u}(n)/\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime\prime})}))$,
the equations
$\overline{\mathcal{R}_{k}(\boldsymbol{\ell}^{\prime\prime})}=\overline{\mathfrak{L}_{\geq
k}(\log\mathcal{G}^{\prime\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime\prime})})}$,
$k=10,\ldots,2$, hold.

Then, applying Proposition 5.4 in the quotient linear space

$V\coloneqq\mathfrak{u}(n)/\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime\prime})}))$

as in the previous steps, we have

$\bigg{\langle}\overline{\log(B_{1}^{t}\cdots
B_{m}^{t})}\;\bigg{|}\;t\in\mathbb{Z}_{\geq 0},m\geq
1,B_{i}\in\left(\mathcal{G}^{\prime}\right)^{*},\sum_{i=1}^{m}\operatorname{PI}^{\mathcal{G}^{\prime\prime}}(B_{i})\in\\{\boldsymbol{\ell}^{\prime\prime},2\boldsymbol{\ell}^{\prime\prime}\\}\bigg{\rangle}_{\mathbb{Q}_{\geq
0}}\\\ =\overline{\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime\prime})})}.$

Hence, there exist $K^{\prime\prime\prime}>0$ tuples of words
$(B^{\prime\prime}_{11},\ldots,B^{\prime\prime}_{1m})$, $\ldots$,
$(B^{\prime\prime}_{K^{\prime\prime\prime}1},\ldots,B^{\prime\prime}_{K^{\prime\prime\prime}m})$
in $\left(\mathcal{G}^{\prime\prime}\right)^{*}$ with
$\sum_{i=1}^{m}\operatorname{PI}^{\mathcal{G}^{\prime\prime}}(B^{\prime\prime}_{ji})=\boldsymbol{\ell}^{\prime\prime}$
or $2\boldsymbol{\ell}^{\prime\prime}$ for all $j$, as well as positive
integers
$t^{\prime\prime}_{1},\ldots,t^{\prime\prime}_{K^{\prime\prime\prime}}\in\mathbb{Z}_{>0}$,
such that

$\langle\log({B^{\prime\prime}}_{i1}^{t^{\prime\prime}_{i}}\cdots{B^{\prime\prime}}_{im}^{t^{\prime\prime}_{i}})\mid
i=1,\ldots,K^{\prime\prime\prime}\rangle_{\mathbb{Q}_{\geq
0}}+\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime\prime})}))\\\
=\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime\prime})})+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime\prime})})).$
(53)

Since $\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime\prime})})=\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})))$, we have

$\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime\prime}_{\operatorname{supp}(\boldsymbol{\ell}^{\prime\prime})}))\subseteq\mathfrak{L}_{\geq
16}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})=\\{0\\}.$

Thus, Equation (53) can be rewritten as

$\langle\log({B^{\prime\prime}}_{i1}^{t^{\prime\prime}_{i}}\cdots{B^{\prime\prime}}_{im}^{t^{\prime\prime}_{i}})\mid
i=1,\ldots,K^{\prime\prime\prime}\rangle_{\mathbb{Q}_{\geq
0}}=\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})}))).$

Hence, the matrices
$A^{\prime\prime\prime}_{i}={B^{\prime\prime}}_{i1}^{t^{\prime\prime}_{i}}\cdots{B^{\prime\prime}}_{im}^{t^{\prime\prime}_{i}},i=1,\ldots,K^{\prime\prime\prime}$
satisfy the Equation (49). Define the new alphabet
$\mathcal{G}^{\prime\prime\prime}=\\{A^{\prime\prime\prime}_{1},\ldots,A^{\prime\prime\prime}_{K^{\prime\prime\prime}}\\}$.

  4. (4)

Find a word $w\in\langle\mathcal{G}^{\prime\prime\prime}\rangle$ with $\log
w=0$. Since the right hand side of Equation (49) is a linear space, we have
$-\log A^{\prime\prime\prime}_{j}\in\langle\log A^{\prime\prime\prime}_{i}\mid
i=1,\ldots,K^{\prime\prime\prime}\rangle_{\mathbb{Q}_{\geq 0}}$ for
$j=1,\ldots,K^{\prime\prime\prime}$. Hence, there exists a non-zero vector
$\boldsymbol{\ell}^{\prime\prime\prime}=(\ell^{\prime\prime\prime}_{1},\ldots,\ell^{\prime\prime\prime}_{K^{\prime}})\in\mathbb{Z}_{\geq
0}^{K^{\prime\prime\prime}}$, satisfying

$\sum_{i=1}^{K^{\prime\prime\prime}}\ell^{\prime\prime\prime}_{i}\log
A^{\prime\prime\prime}_{i}=0.$

Since $\log\mathcal{G}^{\prime\prime\prime}\in\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq 2}(\mathfrak{L}_{\geq
2}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})))\subseteq\mathfrak{L}_{\geq
8}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})$, we have

$\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime\prime\prime})\subseteq\mathfrak{L}_{\geq
16}(\log\mathcal{G}_{\operatorname{supp}(\boldsymbol{\ell})})=\\{0\\}.$

Hence, by the BCH formula,

$\log({A^{\prime\prime\prime}}_{1}^{\ell^{\prime\prime\prime}_{1}}\cdots{A^{\prime\prime\prime}}_{K^{\prime\prime\prime}}^{\ell^{\prime\prime\prime}_{K^{\prime\prime\prime}}})=\sum_{i=1}^{K^{\prime\prime\prime}}\ell^{\prime\prime\prime}_{i}\log
A^{\prime\prime\prime}_{i}=0,$

because the terms $H_{k},k\geq 2$ are in $\mathfrak{L}_{\geq
2}(\log\mathcal{G}^{\prime\prime\prime})$, which vanishes. Therefore, we have
found the non-empty word
$w={A^{\prime\prime\prime}}_{1}^{\ell^{\prime\prime\prime}_{1}}\cdots{A^{\prime\prime\prime}}_{K^{\prime\prime\prime}}^{\ell^{\prime\prime\prime}_{K^{\prime\prime\prime}}}\in\left(\mathcal{G}^{\prime\prime\prime}\right)^{*}$
satisfying $\log w=0$. By replacing $A^{\prime\prime\prime}_{i}$ with their
corresponding words
${B^{\prime\prime}}_{i1}^{t^{\prime\prime}_{i}}\cdots{B^{\prime\prime}}_{im}^{t^{\prime\prime}_{i}}$
in $\left(\mathcal{G}^{\prime\prime}\right)^{*}$, then replacing
$A^{\prime\prime}_{i}$ with corresponding words in
$\left(\mathcal{G}^{\prime}\right)^{*}$, then replacing $A^{\prime}_{i}$ with
corresponding words in $\mathcal{G}^{*}$, we see that $w$ considered as a word
in $\mathcal{G}^{*}$ has Parikh image in
$\mathbb{Z}_{>0}\cdot\boldsymbol{\ell}$, because the words
$B_{i1}^{t_{i}}\cdots B_{im}^{t_{i}}$ corresponding to $A^{\prime}_{i}$ all
have Parikh image in $\mathbb{Z}_{>0}\cdot\boldsymbol{\ell}$.

∎

##  6 Conjecture for higher nilpotency class

In Sections 4 and 5, we showed that the invertible subset of any finite set
$\mathcal{G}\subseteq G$ is computable in polynomial time, where $G$ is a
subgroup of $\mathsf{UT}(n,\mathbb{Q})$ of nilpotency class at most ten. The
only obstacle for generalizing this result to higher nilpotency class is to
prove Proposition 5.3 for $k\geq 11$. If the identities (12) exist for $k\geq
11$, then they can be found with the same computer aided procedure as the one
used in the proof of Lemma 5.8-5.10 (see Section B). Following this idea,
given $k\geq 11$, we propose the following conjecture, which generalizes
Proposition 5.3:

######  Conjecture 6.1.

Let $\mathcal{H}\subset\mathsf{UT}(n,\mathbb{Q})$ be any finite set of
matrices. There exist an integer $r\geq 0$, positive rational numbers
$\alpha_{1},\ldots,\alpha_{r}$, as well as, for $s=1,\ldots,r$, words
$\boldsymbol{j}_{s}=j_{s,1}j_{s,2}\cdots j_{s,m_{s}}$ in the alphabet
$\mathcal{I}=\\{1,2,\ldots,k+1\\}$, such that
$\operatorname{PI}^{\mathcal{I}}(\boldsymbol{j}_{s})\in\mathbb{Z}_{>0}\cdot(1,1,\ldots,1)$
and

$\sum_{\sigma\in\operatorname{S}_{k+1}}H_{k}(\log B_{\sigma(1)},\ldots,\log
B_{\sigma(k+1)})+\sum_{s=1}^{r}\alpha_{s}\sum_{\sigma\in\operatorname{S}_{k+1}}H_{k}(\log
B_{\sigma(j_{s,1})},\ldots,\log B_{\sigma(j_{s,m_{s}})})\\\
\in\mathfrak{L}_{\geq k+1}(\log\mathcal{H})+\mathfrak{L}_{\geq
2}(\mathfrak{L}_{\geq 2}(\log\mathcal{H}))$ (54)

for all matrices $B_{1},\ldots,B_{k+1}$ in $\mathsf{UT}(n,\mathbb{Q})$
satisfying $\log B_{i}\in\mathfrak{L}_{\geq 1}(\log\mathcal{H})$ and
$\sum_{i=1}^{k+1}\log B_{i}\in\mathfrak{L}_{\geq 2}(\log\mathcal{H})$.

For even $k$, Conjecture 6.1 is correct by the antisymmetry of $H_{k}$ (Lemma
5.6). For $k=3$, it is correct by taking $r=0$ and using Lemma 5.7. For
$k=5,7,9$, it is verified by Lemma 5.8, 5.10, 5.11, where the words
$\boldsymbol{j}_{s},s=1,\ldots,r,$ all satisfy
$\operatorname{PI}^{\mathcal{I}}(\boldsymbol{j}_{s})=(2,2,\ldots,2)$.

For odd $k$ larger than $10$, using Algorithm 2 in Section B, we can search
for words $\boldsymbol{j}_{s}$ that potentially verify Conjecture 6.1. Namely,
starting with $q=2$, take all the words $\boldsymbol{j}_{s}$ satisfying
$\operatorname{PI}^{\mathcal{I}}(\boldsymbol{j}_{s})=(p,p,\ldots,p),2\leq
p\leq q$. Under the equivalence relation $\sim$ (defined in the proof of Lemma
5.8), we can write each expression

$h_{k}(\boldsymbol{j}_{s})\coloneqq\sum_{\sigma\in\operatorname{S}_{k+1}}H_{k}(\log
B_{\sigma(j_{s,1})},\ldots,\log B_{\sigma(j_{s,m_{s}})})$

as a linear combination of expressions $\widehat{M}(P,c)$ (see Section B)
using Algorithm 2. Then, writing
$-\sum_{\sigma\in\operatorname{S}_{k+1}}H_{k}(\log B_{\sigma(1)},\ldots,\log
B_{\sigma(k+1)})$ also as a linear combination of $\widehat{M}(P,c)$, we can
verify whether it is in the $\mathbb{Q}_{\geq 0}$-cone generated by the
elements $h_{k}(\boldsymbol{j}_{s})$. If this is the case, then there exist
positive rational numbers $\alpha_{s},s=1,2,\ldots,$ satisfying Equation (54).
If this is not the case, we can increase $q$ and repeat the above procedure.

If there exists a relation of the form (54), then the above procedure
terminates for some $q$ and returns this relation. Otherwise it does not