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\}$?
1

$\begingroup$ Maybe it would be better to call it "factoring" in the Heisenberg group? $\endgroup$ – Izaak Meckler Jul 18 '17 at 7:01

1$\begingroup$ 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. $\endgroup$ – YCor Jul 18 '17 at 7:01

$\begingroup$ How is that? Do you have a counterexample? $\endgroup$ – stackExchangeUser Jul 18 '17 at 7:03

2$\begingroup$ It's an exercise you can solve. $\endgroup$ – YCor Jul 18 '17 at 7:03

2$\begingroup$ 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. $\endgroup$ – Derek Holt Jul 18 '17 at 7:42