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 the conjugacy class of a compressed word in $F_r$ is decidable in deterministic polynomial time.
Let $F_m=F(a_1,\dots,a_m)$ with $m\ge 2$, and fix $q\ge 1$. For every fixed $0<\lambda<1$, we prove that a $q$-tuple $\mathbf W_n$ of independent uniformly random cyclically reduced words of length $n$ is \emph{$\lambda$-stable} with probability converging to $1$ exponentially fast. Namely, for every $\Phi\in Aut(F_m)$, the tuple $\Phi(\mathbf W_n)$, after cyclic reduction and symmetrization, satisfies the $C'(\lambda)$ small cancellation condition. Combining generic $\lambda$-stability with Greendlinger normal-closure rigidity and with previous results of Kapovich-Schupp-Shpilrain on generic Nielsen uniqueness and generic Whitehead rigidity we establish, for any fixed $m\ge 2, q\ge 1$, isomorphism rigidity for generic $m$-generator $q$-relator groups. Thus we show that two such generic groups $\langle a_1,\dots, a_m| r_1,\dots, r_q\rangle$ and $\langle a_1,\dots, a_m| s_1,\dots, s_q\rangle$ are isomorphic if and only if, after possibly permuting and inverting the generators $a_1,\dots, a_m$, the relator tuples $(r_1,\dots, r_q)$ and $(s_1,\dots, s_q)$ are the same, up to reordering, cyclic permutations and inverting the relators. Among the applications, we obtain a quadratic-time algorithm that generically solves the isomorphism problem for $m$-generator $q$-relator groups, and show that the number of isomorphism types represented by $m$-generator $q$-relator presentations with cyclically reduced relators of length $n$ is asymptotic to \[ \frac{(2m-1)^{qn}}{2^{m+q}m!\,q!\,n^q}. \] The proof of generic $\lambda$-stability relies on the use of geodesic currents and on our deterministic sufficient criterion for a $q$-tuple $\mathbb W$ in $F_m$ to be $\lambda$-stable in terms of the components of $\mathbb W$ being sufficiently projectively close to filling currents.
Ilya Kapovich· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
