Peer-reviewedCC BYJournal of Computational Algebra
Compressed primitivity problem in free groups
- 1Department of Mathematics and Statistics, Hunter College of CUNY, 695 Park Ave, New York, NY 10065, USA
Abstract
For a fixed integer r ≥ 2 , we prove that the compressed primitivity problem in the free group F r = F ( x 1 , … , x r ) is decidable in nondeterministic polynomial time. That is, for a straight-line program A 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 A . 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.
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
@article{kapovich2026compressed,
title = {{Compressed primitivity problem in free groups}},
author = {Ilya Kapovich},
journal = {Journal of Computational Algebra},
year = {2026},
month = oct,
doi = {10.1016/j.jaca.2026.100050},
url = {https://doi.org/10.1016/j.jaca.2026.100050},
note = {CC BY},
}
RIS
TY - JOUR
TI - Compressed primitivity problem in free groups
AU - Ilya Kapovich
PY - 2026
DA - 2026/10/30
JO - Journal of Computational Algebra
DO - 10.1016/j.jaca.2026.100050
UR - https://doi.org/10.1016/j.jaca.2026.100050
AB - For a fixed integer r ≥ 2 , we prove that the compressed primitivity problem in the free group F r = F ( x 1 , … , x r ) is decidable in nondeterministic polynomial time. That is, for a straight-line program A 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 A . 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.
SN - 2772-8277
ER -