Compressed primitivity problem in free groups

Abstract

For a fixed integer $r\ge 2$, we prove that the \emph{compressed primitivity problem} in the free group $F_r=F(x_1,\dots,x_r)$ is decidable in non-deterministic polynomial time. That is, for a \emph{straight-line program} $\mathcal A$ over $\{x_1,\dots,x_r\}^{\pm1}$ representing an element $g\in F_r$, the problem of deciding whether $g$ is primitive in $F_r$ belongs to $\mathsf{NP}$, with input measured by the size of $\mathcal A$. For $r=2$, we prove that this problem is decidable in deterministic polynomial time. We also show that, in every fixed rank $r\ge 2$, automorphic minimality of the conjugacy class of a compressed word in $F_r$ is decidable in deterministic polynomial time.