1
$\begingroup$

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

$\endgroup$
  • $\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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.