Id: arxiv/2607.21499 Url: https://arxiv.org/abs/2607.21499 Tags: math.GR, math.GT Score: 0 Title: Compressed primitivity problem in free groups Domain: math.GR Source: arxiv Authors: Ilya Kapovich Reviews: 0 Subject: math.GR Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-23 Page: https://delphi.science/r/arxiv/2607.21499 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…