Compressed primitivity problem in free groups

2026/07/23 by Ilya Kapovich
#math.GR #math.GT

paper · pdf

Abstract

For a fixed integer r≥ 2, we prove that the compressed primitivity problem in the free group F_r=F(x₁,…,x_r) is decidable in non-deterministic polynomial time. That is, for a straight-line program \mathcal A over \x₁,…,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 \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≥ 2, automorphic minimality of the conjugacy class of a compressed word in F_r is decidable in deterministic polynomial time.

Related

• Compressed words and automorphisms in fully residually free groups
• Polynomial-time word problems
• The fully compressed subgroup membership problem
• Groups with ALOGTIME-hard word problems and PSPACE-complete compressed word problems
• The compressed word problem in relatively hyperbolic groups