Computing area in group presentations

Timothy Riley

Published 2016-06-28Version 1

The width of a word $w$ representing an element in a free group $F(a,b)$ was defined by Jiang to be the minimal $N$ such that $w$ freely equals a product of $N$ conjugates of powers of $a$ and $b$. In 1991 Grigorchuk and Kurchanov gave an algorithm computing $N$ and asked whether it could be done in polynomial time. We use dynamic programming answer this affirmatively. The width of $w$ can be reinterpreted as its area with respect to the presentation $\langle a, b \mid a^k, b^k; \ k \in \mathbb{N} \rangle$ of the trivial group. We also give a polynomial time algorithm finding the areas of words in the group presentation $\langle a, b \mid a, b \rangle$. These problems have connections to computing the minimal number of fixed points in the homotopy class of a continuous self-map of a compact surface, RNA folding, and the design of liquid crystals.