1
$\begingroup$

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?

1 Answers 1

4

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!

  • 0
    That's exactly what I meant by "direct".2012-03-03