# Factoring in discrete Heisenberg group $H_3(\mathbb{Z})$

Let $H_3(\mathbb{Z})$ be the discrete Heisenberg group 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}$ Suppose we have $s=s_1\cdot s_2 \cdots s_n$ with $s_i \in \{x,y\}$ and we know only $s$. Is there an efficient algorithm to compute the $s_i$ only by knowledge of $s$ and that $s_i \in \{x,y\}$?

• Maybe it would be better to call it "factoring" in the Heisenberg group? – Izaak Meckler Jul 18 '17 at 7:01
• This is not what's widely called "word problem". Second, before asking the algorithmic question, you can just ask the theoretical one: does $s$ determine the $s_i$ (i noticed you considered only positive words)? The answer is no! So it's hard to make sense of your algorithmic question. – YCor Jul 18 '17 at 7:01
• How is that? Do you have a counterexample? – stackExchangeUser Jul 18 '17 at 7:03
• It's an exercise you can solve. – YCor Jul 18 '17 at 7:03
• This should not be too difficult. The total numbers of $x$ and $y$ in the product are determined by the $(1,2)$ and $(2,3)$ entries of $s$. The $(1,3)$ entry is equal to the total number of pairs $s_i=x$, $s_j=y$ in the product with $i<j$. As YCor pointed out, the solution is not always unique, but all solutions have the same word length. – Derek Holt Jul 18 '17 at 7:42