On the Identity Problem for unipotent matrix groups of nilpotency class at most ten.

25^th May 2022, 14:00 Ashton Lecture Theatre
Ruiwen Dong
University of Oxford

Abstract

Given a finite set of matrices $\mathcal{G}$ in a unipotent matrix group $G$ over $\Q$. Suppose that the $G$ has nilpotency class at most ten, we show that the Identity Problem (whether $I$ is in the semigroup $\langle\mathcal{G}\rangle$) and the Group Problem (whether $\langle\mathcal{G}\rangle$ is a group) are decidable in polynomial time.
In particular, this shows that the Identity Problem and the Group Problem are decidable in polynomial time for finitely generated sub-semigroups of the group $UT(11, K)^n$, where $K$ is any number field. Another important implication of this result is the decidability of the Identity Problem for finitely generated sub-semigroups of finitely generated nilpotent groups of class at most ten.
The key idea in our approach is the correspondence between unipotent matrix groups and nilpotent Lie algebras. Using the Baker-Campbell-Hausdorff formula, one can convert problems in matrix groups to problems in Lie algebras. Using the linear space structure of Lie algebras, we relate semigroup problems in matrix groups to convex geometry problems in Lie algebra. The core of our work is showing some fascinating identities for the $k$-th term of the Baker-Campbell-Hausdorff formula, some of which are proven using computer assistance.
We will also formulate a conjecture with respect to a variable $k$, such that, if the conjecture is true for all $k \leq d$, then our result still holds when the unipotent matrix group $G$ has nilpotency class $d$. For every $k$, there is an effective procedure that produces a proof of this conjecture in case it is true.