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.

Disclosure

“t need to recover the exponentially long block decomposition: it performs the same shears directly on the input SLP and makes a single cyclic-length test at the end. 9. Disclosure of AI use ChatGPT was used during the preparation of this manuscript. The author independently checked and edited all mathematical arguments and takes full responsibility for the final content. Referen”

PDF page 24

Classification

Proof ideas or individual proof-step assistance

Multiplier

8

Verified

2026-08-23T19:04:22.633939Z

Structural counts