Word length in the Discrete Heisenberg Group In the Discrete Heisenberg group, given an element of the group, is it possible to compute its shortest presentation in terms of the generators:
$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}$
?
(I mean the shortest word in $x$ and $y$ and their inverses which equals the given element)
If so, is there a direct efficient way to find it in this case?
 A: Yes it is certainly possible, and it can be done efficiently, but it is complicated! (I am not sure what you mean by "direct".) I will try and give a rough description of how to proceed. It would be an interesting programming exercise and hard to get exactly right.
Let $z = [y,x] = y^{-1}x^{-1}yx$. (This is actually the identity matrix with an extra $-1$ at the top right.) Then every element of the group can be written uniquely as $x^ly^mz^n$ with $l,m,n \in {\mathbb Z}$.
Let's first consider the case $z^n$. A word for this will have $a$ occurrences each of $x$ and $x^{-1}$ and $b$ each of $y$, $y^{-1}$ for some $a,b>0$. Note that $[x^a,y^b] = z^{-ab}$ and $[y^b,x^a] = z^{ab}$ and by suitably arranging the generators, we can get any power $z^n$ with $-ab \le n \le ab$ using such a word. So we have to choose $a,b$ to minimize $a+b$ subject to $ab \ge n$. For example, for $n=75$, the minimum possible $a+b$ is 18. For example, we could choose $a=8$, $b=10$, $z^{75} = y^{-10}x^{-8}y^5xy^5x^7$,
which is one of many possible shortest words for this element.
The general case is a bit more complicated. Let's assume $l,m \ge 0$ (the other cases are similar). Then if $0 \le n \le lm$, we are lucky, and we can do it with a word of length $l+m$, which is clearly minimal. For example, $x^3y^7z^{17} = y^5 x yx^2 y$.
So suppose that $n > lm$, so $x^l y^m z^n = y^m x^l z^{n-lm}$. If we introduce $a$ extra occurrences of $x$ and $x^{-1}$ and $b$ of $y$ and $y^{-1}$, then the highest power of $z$ that we can get is with the word $y^{m+b} x^{l+a} y^{-b}x^{-a} = y^m x^l z^{(l+a)b}$, so we want to minimize $a+b$ subject to $(l+a)b \ge n-lm$.
For example, for $g=x^5y^4z^{100}=y^4x^5z^{80}$, the minimum $a+b$ is 13 and choosing, for example, $a=4$, $b=9$, we have $g=y^4x^{-4}y^9x^8y^{-1}xy^{-8}$.
The case $n < 0$ is similar!
