Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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!

share|improve this answer
    
That's exactly what I meant by "direct". –  Jackie Mar 3 '12 at 17:10

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.