{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-23","reactions":{}}