Norm of elements in discrete Heisenberg group

Question

The discrete Heisenberg group (https://en.wikipedia.org/wiki/Heisenberg_group#Discrete_Heisenberg_group) is generated by
$ x=\begin{pmatrix} 1 & 1 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1\\ \end{pmatrix},\ \ y=\begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 1\\ 0 & 0 & 1\\ \end{pmatrix} $

Let $s = s_1 \cdot s_2 \cdots s_n$ with $s_i \in \{x,y\}$. Is $|s|_1$ or $|s|_{\infty}$ (or another matrix norm if you prefer) polynomially in $n$ bounded above?

Answer 1

Let $M(i,j,k)$ denote the matrix $\left(\begin{array}{ccc}1&i&k\\0&1&j\\0&0&1\end{array}\right)$, for $i,j,k \in {\mathbb Z}$. Then $G = \{M(i,j,k):i,j,k \in {\mathbb Z}\}$.

You can check that $M(i,j,k)x^{\pm 1} = M(i\pm 1,j,k)$ and $M(i,j,k)y^{\pm 1} = M(i,j\pm 1,k\pm i)$.

Using that, it is easy to show by induction that for a word of length $n$ over $x^{\pm 1}$, $y^{\pm 1}$, we have $|i|,|j| \le n$, and $|k| \le n^2$. (In fact I think you get $|k| \le (n/2)^2$.)