PreprintarXiv licencearXiv
Compressed primitivity problem in free groups
Abstract
For a fixed integer r≥ 2, we prove that the \emph{compressed primitivity problem} in the free group Fr=F(x1,…,xr) is decidable in non-deterministic polynomial time. That is, for a \emph{straight-line program} 𝒜 over {x1,…,xr}±1 representing an element g∈ Fr, the problem of deciding whether g is primitive in Fr belongs to NP, with input measured by the size of 𝒜. For r=2, we prove that this problem is decidable in deterministic polynomial time. We also show that, in every fixed rank r≥ 2, automorphic minimality of the conjugacy class of a compressed word in Fr is decidable in deterministic polynomial time.
Related
- PHP decompositions and primitivity of group rings for linear groups
- The Diophantine Problem with constraints in some free-by-cyclic groups
- An Alternative Framework for Irreducibility and Primitivity of Nonnegative Tensors
- The congruence subgroup problem for branch groups
- On the sample complexity of the generalized hidden shift problem over arbitrary finite groups
BibTeX
@misc{kapovich2026compressed,
title = {{Compressed primitivity problem in free groups}},
author = {Ilya Kapovich},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.21499},
eprint = {2607.21499},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.21499},
}
RIS
TY - UNPB
TI - Compressed primitivity problem in free groups
AU - Ilya Kapovich
PY - 2026
DA - 2026/10/14
PB - arXiv
DO - 10.48550/arxiv.2607.21499
UR - https://arxiv.org/abs/2607.21499
AB - For a fixed integer r≥ 2, we prove that the \emph{compressed primitivity problem} in the free group F_r=F(x_1,…,x_r) is decidable in non-deterministic polynomial time. That is, for a \emph{straight-line program} 𝒜 over {x_1,…,x_r}^±1 representing an element g∈ F_r, the problem of deciding whether g is primitive in F_r belongs to NP, with input measured by the size of 𝒜. For r=2, we prove that this problem is decidable in deterministic polynomial time. We also show that, in every fixed rank r≥ 2, automorphic minimality of the conjugacy class of a compressed word in F_r is decidable in deterministic polynomial time.
ER -