Short, Highly Imprimitive Words Yield Hyperbolic One-Relator Groups

Abstract

We give experimental support for a conjecture of Louder and Wilton saying that words of imprimitivity rank greater than two yield hyperbolic one-relator groups.

KEYWORDS:

• One-relator group
• hyperbolic group
• imprimitivity rank

2020 MATHEMATICS SUBJECT CLASSIFICATION:

• 20F67
• 20-08
• 20F10
• 20F05
• 20F65

1 Introduction

An element in a free group is primitive if it is an element of some basis, or free generating set. Failure of primitivity can be quantified: define the imprimitivity rank of an element to be the minimal rank of a subgroup containing it as an imprimitive element, if such a subgroup exists, or infinite otherwise. An element has imprimitivity rank 0 if and only if it is trivial, 1 if and only if it is a proper power, and $\infty$ if and only if it is a primitive element. In these cases the quotient of the free group by the subgroup normally generated by the element is a hyperbolic group, either a free group, in the first and third cases, or a one-relator group with torsion, which is hyperbolic by the B. B. Newman spelling theorem [27], in the second case. Nonelementary torsion-free two-generator one-relator groups have relators of imprimitivity rank 2. There are many nonhyperbolic groups of this form, such as ${\mathbb{Z}}^2=〈a,b|ab{a}^{-1}{b}^{-1}〉$, the Baumslag-Solitar groups $BS(m,n)=〈a,b|a{b}^m{a}^{-1}{b}^{-n}〉$, the torus knot groups $〈a,b|a^p=b^q〉$ for $\left|p\right|,\left|q\right|>1$, and the groups considered by Gardam and Woodhouse [10]. Louder and Wilton [24, Theorem 1.4] show that two-generated subgroups of a higher imprimitivity rank one-relator group are free. Thus, they have no Baumslag-Solitar subgroups. It is a long-standing open question whether groups of Type F with no Baumslag-Solitar subgroups must be hyperbolic. One-relator groups are Type F, so Louder and Wilton conjecture [24, Conjecture 1.6] that a one-relator group is hyperbolic if its defining relator does not have imprimitivity rank equal to 2.

We offer experimental support for their conjecture. Fix a basis for a free group, so that a group element can be uniquely represented as a freely reduced word, a product of basis elements and their inverses, of a well-defined length.

Theorem 1.1.

Let w be a word in ${\mathbb{F}}_r$ of length L and imprimivity rank not equal to 2. Then ${\mathbb{F}}_r/〈\mathrm{}〈w〉\mathrm{}〉$ is hyperbolic if $r\le 4$ and $L\le 17$.

These results are achieved computationally, by a combination of efficient enumeration of representatives and brute force¹. Details are in Section 4.

We also observe that a well-known result about hyperbolicity of one-relator groups is consistent with the conjecture. In these results $|w{|}_a$ denotes the total number of occurrences of a and $a^{-1}$ in w, where w is freely reduced and a is an element of the chosen basis.

Proposition 1.2.

Every word satisfying one of the nonhyperbolicity criteria of Ivanov and Schupp [17, Theorems 3 & 4] (see Theorem 3.1 and Theorem 3.2) has imprimitivity rank 2.

The proposition is proven in Section 3. As a consequence, we have:

Corollary 1.3.

Let w be a cyclically reduced word in ${\mathbb{F}}_r$ of imprimitivity rank not equal to 2 such that $0<|w{|}_a<4$ for some basis element a. Then ${\mathbb{F}}_r/〈\mathrm{}〈w〉\mathrm{}〉$ is hyperbolic.

Corollary 1.4.

Let w be cyclically reduced word in ${\mathbb{F}}_r$ of length less than 4r and imprimitivity rank not equal to 2 such that every generator or its inverse occurs in w. Then ${\mathbb{F}}_r/〈\mathrm{}〈w〉\mathrm{}〉$ is hyperbolic.

Combining these results with our experimental results, we have:

Corollary 1.5.

Let w be a word in ${\mathbb{F}}_r$ of length at most 17 and imprimitivity rank not equal to 2. Then ${\mathbb{F}}_r/〈\mathrm{}〈w〉\mathrm{}〉$ is hyperbolic.

Proof.

${\mathbb{F}}_r/〈\mathrm{}〈w〉\mathrm{}〉$ is hyperbolic when the imprimitivity rank of w is 0, 1, or $\infty$, so suppose it is finite and at least 3. Up to replacing w by an element in the same automorphic orbit, we may, without increasing the length of w, assume that it is cyclically reduced and that there is s such that taking the first s basis elements and the last r – s basis elements gives a splitting ${\mathbb{F}}_r={\mathbb{F}}_s*{\mathbb{F}}_{r-s}$ where the ${\mathbb{F}}_s$ factor is the smallest free factor containing w. Since w is imprimitive in ${\mathbb{F}}_r$, it is imprimitive in ${\mathbb{F}}_s$, so s is an upper bound on imprimitivity rank, which implies $s\ge 3$. Furthermore, since ${\mathbb{F}}_s$ is the smallest free factor containing w, all of the generators of ${\mathbb{F}}_s$ or their inverses occur in w. Since ${\mathbb{F}}_r/〈\mathrm{}〈w〉\mathrm{}〉\cong ({\mathbb{F}}_s/〈\mathrm{}〈w〉\mathrm{}〉)*{\mathbb{F}}_{r-s}$ is hyperbolic if and only if ${\mathbb{F}}_s/〈\mathrm{}〈w〉\mathrm{}〉$ is, we conclude by applying Theorem 1.1 or Corollary 1.4 to ${\mathbb{F}}_s/〈\mathrm{}〈w〉\mathrm{}〉$, according to whether s < 5 or $s\ge 5$, respectively. □

1.1 Additional conjectures

In checking the hyperbolicity conjecture, we enumerated the $\text{Aut}({\mathbb{F}}_4)$ orbits of cyclic subgroups of ${\mathbb{F}}_4$ that have a representative that can be generated by a word of length at most 16. We also computed imprimitivity ranks for these words. Armed with this data, we can test other questions involving imprimitivity rank. We check two additional conjectures and find that they are consistent with the data up to length 16. The first of these concerns uniqueness of the subgroup in the definition of imprimitivity rank, see Proposition 4.2. The second concerns the relationship between imprimitivity rank and stable commutator length, see Proposition 4.4.

2 Preliminaries

Fix a free group ${\mathbb{F}}_r$ with basis $X=(x_1,\dots ,x_r)$. Let $X^{\pm }:=\{x_1,\dots ,x_r\}\cup \{x_1^{-1},\dots ,x_r^{-1}\}$. Write $f\sim g$ if f and g are conjugate. The word length of f with respect to X is denoted $\left|f\right|$, and the word length of the cyclic reduction of f with respect to X, the cylic length of f, is denoted $\left|\right|f\left|\right|$.

We use $\cong$ to denote an isomorphism between groups and also for the equivalence of group elements via an isomorphism.

For our purposes, a finitely presented group is hyperbolic if there exists a linear function δ such that if w is a freely reduced word of length n in the generators or their inverses that represents the identity element of the group then it is possible to express w as the free reduction of a product of at most $\delta (n)$ conjugates of relators or their inverses. It turns out that while the precise function δ depends on the choice of finite presentation, its linearity does not, so being hyperbolic is a group property and not merely a property of a presentation. More on hyperbolic groups can be found in any textbook on Geometric Group Theory.

Imprimitivity rank was introduced by Puder² [30].

Stallings [31] gave a way to conveniently represent subgroups of a free group in terms of labeled graphs. We follows the treatment given by Kapovich and Myasnikov [18]: A Stallings graph is a based, directed, connected, X-labeled graph $(\Gamma ,o)$ that is folded and core with respect to o. The free group ${\pi }_1(\Gamma ,o)$ is identified with a subgroup of ${\mathbb{F}}_r$ via the labeling, and, in fact, Stallings graphs are in bijection with subgroups of ${\mathbb{F}}_r$. See Kapovich and Myasnikov [18] for details.

The group W_I of Whitehead automorphisms of the first kind are automorphic extensions of maps defined on X by $x_i\mapsto x_{\sigma (i)}^{{ϵ}_i}$ for $1\le i\le r$, where $\sigma \in \text{Sym}(r)$ and ${ϵ}_i=\pm 1$.

The set W_II of Whitehead automorphisms of the second kind are automorphic extensions of maps defined on $X^{\pm }$ as follows. Given an element $x\in X^{\pm }$ and a subset $Z\subset X^{\pm }\setminus \{x,x^{-1}\}$ take the map that fixes x and $x^{-1}$ and for $y\in X^{\pm }\setminus \{x,x^{-1}\}$ does$$y\mapsto \{\begin{array}{cc}y\hfill & \mathrm{}\text{if}\mathrm{}y,y^{-1}\notin Z,\hfill \\ xy\hfill & \mathrm{}\text{if}\mathrm{}y\in Z\mathrm{}\text{and}\mathrm{}{y}^{-1}\notin Z,\hfill \\ y{x}^{-1}\hfill & \mathrm{}\text{if}\mathrm{}y\notin Z\mathrm{}\text{and}\mathrm{}{y}^{-1}\in Z,\hfill \\ xy{x}^{-1}\hfill & \mathrm{}\text{if}\mathrm{}y,y^{-1}\in Z.\hfill \end{array}$$

Together the Whitehead automorphisms generate $\text{Aut}({\mathbb{F}}_r)$. Moreover, Whitehead [32] proves two stronger facts:

• Call a word $w\in {\mathbb{F}}_r$ Whitehead minimal if there does not exist a Whitehead automorphism α such that $\left|\right|\alpha (w)\left|\right|<\left|w\right|$. An element has minimal length in its $\text{Aut}({\mathbb{F}}_r)$ orbit if and only if it is Whitehead minimal.

• Define the Whitehead level—L graph to be the graph whose vertices are Whitehead minimal words of length L, where w and v are connected by an edge if there exists a Whitehead automorphism α such that v is the cyclic reduction of $\alpha (w)$. Then the partition of vertices by connected component in the Whitehead level—L graph is the same as the partition by $\text{Aut}({\mathbb{F}}_r)$ orbits.

Combining these two facts gives Whitehead’s Algorithm for determining if two words are in the same $\text{Aut}({\mathbb{F}}_r)$ orbit: they are if and only if their Whitehead minimal representatives have the same length, say L, and are contained in the same component of the Whitehead level–L graph. In particular, a word represents a primitive element if and only if it Whitehead reduces to a word of length 1.

A basic algorithm for enumerating words of a fixed length L in a given ordered finite alphabet $a_0<a_1<a_2<\cdots <a_n$ is via an odometer. Given a word of length L in the alphabet, we inductively construct a new word as follows. Incrementing at place k means that if the kth letter of the current word is a_m for m < n then we replace it by $a_{m+1}$ and take the resulting word. If m = n and k > 1, then we increment at place k – 1 and replace letters to the right of the $(k-1)$–st place by a₀. If m = n and k = 1 then the odometer is said to rollover to $a_0^L$. The odometer algorithm is to start with $a_0^L$, and increment on the Lth (right-most) place. Repeat until the odometer rolls over and then stop.

We will be interested in enumerating freely reduced words in a free group with a given basis. The alphabet will consist of the chosen basis elements and their inverses, with some order imposed upon them. Since we are interested in freely reduced words we modify the induction step so that we increment as many times as necessary until the resulting word is freely reduced.

3 The Ivanov-Schupp criteria

Theorem 3.1

([17, Theorem 3]). Let w be a freely and cyclically reduced word in ${\mathbb{F}}_r$ and suppose that for some basis element a, the total number of occurrences of a and $a^{-1},|w{|}_a$, satisfies $0<|w{|}_a<4$. The group ${\mathbb{F}}_r/〈\mathrm{}〈w〉\mathrm{}〉$ is not hyperbolic if and only if one of the following holds up to cyclic permutation and taking inverses:

1. $|w{|}_a=2$, w = auav and $u{v}^{-1}$ is a proper power in ${\mathbb{F}}_r$.

2. $|w{|}_a=2,w=au{a}^{-1}v$ and either u and v are conjugate to powers of the same word in ${\mathbb{F}}_r$ or u and v are both proper powers in ${\mathbb{F}}_r$.

3. $|w{|}_a=3$, w = atauav and $u{t}^{-1}=z^m,v{t}^{-1}=z^n$ where z is not a proper power, such that one of the following holds:

   1. $\min (|m|,|n|)=0$ and $\max (|m|,|n|)>1$.

   2. $\min (|m|,|n|)>0$ and $\left|m\right|=\left|n\right|\ne 1$.

   3. $\min (|m|,|n|)>0$ and $m=-n$.

   4. $\min (|m|,|n|)>0$ and $m=2n$ (or $n=2m$).

4. $|w{|}_a=3,w=\mathit{atau}{a}^{-1}v$ and $t^{-1}ut=z^m,v=z^n$ where z is not a proper power and either $\left|m\right|=\left|n\right|$ or $m=-2n$ (or $n=-2m$).

Theorem 3.2

([17, Theorem 4 (3)]). Let $w=a{u}_{1}a{u}_{2}a{u}_{3}a{u}_4$ be a freely and cyclically reduced word in ${\mathbb{F}}_r$, such that $|w{|}_a=4$ and the subwords u_i are pairwise different. Then the group ${\mathbb{F}}_r/〈\mathrm{}〈w〉\mathrm{}〉$ is not hyperbolic if and only if for some $i\in \{1,\dots ,4\}$ the following holds (with subscripts modulo 4):$$u_i{u}_{i+1}^{-1}{u}_{i+2}{u}_{i+3}^{-1}=1.$$

We check that nonhyperbolicity in these theorems implies imprimitivity rank 2:

Proof of Proposition 1.2.

Suppose w is of one of the forms in Theorem 3.1 and Theorem 3.2 so that ${\mathbb{F}}_r/〈\mathrm{}〈w〉\mathrm{}〉$ is not hyperbolic. For each case we exhibit a connected, based, rank 2 core graph with edges labeled by words in ${\mathbb{F}}_r$ in which (a conjugate of) w labels a imprimitive element of the fundamental group. By subdividing edges we can arrange that edges are labeled by basis elements. The graphs are not necessarily folded, but from the hypothesis in Theorem 3.1 and Theorem 3.2 that the only occurrences of $a^{\pm 1}$ are the explicit ones, it follows that in all of our examples folding will be a homotopy equivalence, so these graphs really do represent rank 2 subgroups.

In each of the figures the larger dot marks the base vertex, the triangular arrows mark a choice of edges in a maximal subtree, and the edges with the single and double arrows mark edges whose unique completion through the maximal subtree to a based loop represent generators α and β, respectively, of the fundamental group of the graph.

It turns out that, except where noted, when we rewrite a conjugate of w in terms of α and β the result is Whitehead minimal, so we can tell that it is imprimitive by observing that it does not have length 1.

First, let $|w{|}_a=2$ and w = auav such that $u{v}^{-1}=x^n$ with n > 1. Then $w\sim {(va)}^2{x}^n\cong {\alpha }^2{\beta }^n$ is imprimitive in Figure 1(a).

Fig. 1 Graphs for $|w{|}_a=2$ in the proof of Proposition 1.2.

Now assume that $|w{|}_a=2,w=au{a}^{-1}v$ and $u=s_1^{-1}{x}^m{s}_1$ and $v=s_2^{-1}{x}^n{s}_2$. Note that $\min (|m|,|n|)>0$, since otherwise w fails to be either freely or cyclically reduced, so $w\cong \alpha {\beta }^m{\alpha }^{-1}{\beta }^n$ is imprimitive in Figure 1(b). If $u=u_0^m$ and $v=v_0^n$ with $\min (m,n)>1$ then $w\cong {\alpha }^m{\beta }^n$ is imprimitive in Figure 1(c).

Let now $|w{|}_a=3$, w = atauav with $u{t}^{-1}=z^m$ and $v{t}^{-1}=z^n$, where z is not a proper power and m, n satisfy one of the conditions (3a)–(3d) in Theorem 3.1.

Suppose in case (3a) we have m = 0 and n > 1, other variations of this case being similar. Then $w\sim {(ta)}^3{z}^n\cong {\alpha }^3{\beta }^n$ is imprimitive in Figure 2(a).

Fig. 2 Graphs for $|w{|}_a=3$ in the proof of Proposition 1.2.

In case (3c), $w\sim {(ta)}^2{z}^{m}ta{z}^{-m}\cong {\alpha }^2\beta \alpha {\beta }^{-1}$ is imprimitive in Figure 2(b).

In the subcase m = n of case (3b) that is not covered by case (3c), we may assume m > 1 by replacing z with $z^{-1}$, if necessary. Then $w\sim {(ta)}^2{z}^{m}ta{z}^m\cong {\alpha }^2{\beta }^m\alpha {\beta }^m$ in Figure 2(a). This word admits a Whitehead reduction ${\alpha }^{-1}\mapsto \beta {\alpha }^{-1}$, which sends the w–loop to $\alpha {\beta }^{-1}\alpha {\beta }^{2(m-1)}$. Since m > 1, this word is Whitehead minimal, so the w–loop is imprimitive.

In case (3d) assume $n=2m$, the other case being similar. Then $w\sim {(ta)}^2{z}^{m}ta{z}^{2m}\cong {\alpha }^2\beta \alpha {\beta }^2$ in Figure 2(b). This word admits a Whitehead reduction $\beta \mapsto {\alpha }^{-1}\beta$ sending it to a Baumslag-Solitar word, so the w–loop is imprimitive.

Next, consider the case $|w{|}_a=3,w=\mathit{atau}{a}^{-1}v$ and $t^{-1}ut=z^m,v=z^n$ where z is not a proper power. Again we can assume that $\left|m\right|,\left|n\right|>0$ since otherwise $|w{|}_a$ would be less than 3. Then $w={(at)}^2{z}^m{(at)}^{-1}{z}^n$. Consider Figure 2(c). If $\left|m\right|=\left|n\right|$ then $w\cong {\alpha }^2\beta {\alpha }^{-1}{\beta }^{\pm 1}$. If $n=-2m$ then $w\cong {\alpha }^2\beta {\alpha }^{-1}{\beta }^{-2}$. In all three cases w is imprimitive. If $m=-2n$ then $w\cong {\alpha }^2{\beta }^2{\alpha }^{-1}{\beta }^{-1}$ is imprimitive in the graph obtained from Figure 2(c) by relabeling the β edge with $z^{-n}$.

Finally, let $w=a{u}_{1}a{u}_{2}a{u}_{3}a{u}_4$ be as in Theorem 3.2. We may assume that $u_1{u}_2^{-1}{u}_3{u}_4^{-1}=1$, so $w=a{u}_{1}a{u}_{2}a{u}_{3}a{u}_1{u}_2^{-1}{u}_3\cong \alpha \beta \alpha {\beta }^{-1}$ is imprimitive in Figure 3. □

Fig. 3 A graph for $|w{|}_a=4$ in the proof of Proposition 1.2.

4 The experiments

To prove Theorem 1.1, the idea is to enumerate words of each length in the given free group, compute their imprimitivity ranks, and for those of imprimitivity rank not equal to two, test to see if the resulting one-relator presentation is a hyperbolic group.

4.1 Enumerating words/groups

For $w\in {\mathbb{F}}_r$, an automorphism $\alpha \in \text{Aut}({\mathbb{F}}_r)$ induces an isomorphism between ${\mathbb{F}}_r/〈\mathrm{}〈w〉\mathrm{}〉$ and ${\mathbb{F}}_r/〈\mathrm{}〈\alpha {(w)}^{\pm 1}〉\mathrm{}〉$. Call these the “obvious” isomorphisms between one-relator groups. To enumerate isomorphism types of one-relator groups it suffices to enumerate one generator of one representative of each automorphic orbit of cyclic subgroup. There is a canonical choice of such an element: we choose the one that is shortlex minimal with respect to the integer lexicographic order; that is, if $(a_1,\dots ,a_r)$ is our fixed ordered basis for ${\mathbb{F}}_r$, we declare $a_r^{-1}<a_{r-1}^{-1}<\dots <a_1^{-1}<a_1<\dots <a_r$ and extend to a shortlex ordering on reduced words. There are examples of McCool and Pietrowski [25] that show that not all isomorphisms between one-relator groups are obvious, so our enumeration has some redundancies at the level of isomorphism type of one-relator groups. However, work of Kapovich and Schupp [19] and Kapovich et al. [20], says that there is a generic set of one-relator groups for which the only isomorphisms are the obvious ones, so the redundancies are rare, in a specific quantifiable sense.

A naive algorithm for enumerating representatives of length L is to simply construct the Whitehead level–L graph. Additionally, since we are interested in cyclic subgroups and not just elements, we connect every vertex v to the vertex $v^{-1}$. Then choose the shortlex minimal word in each component.

We speed this algorithm up as follows. Permutation of generators and inversion of generators and conjugation by a generator are in $\text{Aut}({\mathbb{F}}_r)$. Define the PCI class of a word to be those words that can be reached from it by a finite chain of Permutation of generators, Cyclic permutation, or Inversion of generators. Similarly, the PCI ${}^{\pm }$ class is those words that can be reached by the above operations plus replacing an element by its inverse. Define a word to be SLPCI ${}^{(\pm )}$ minimal if it is ShortLex minimal in its PCI${}^{(\pm )}$ class. Notice that if we start with a cyclically reduced word then none of the above operations change the length of the word.

Lemma 4.1.

$\text{Aut}({\mathbb{F}}_r)$ equivalence classes of cyclic subgroup such that the minimal generator length of a representative has length L are in bijection with connected components of the length–L SLPCI ${}^{\pm }$ graph: the graph whose vertices are freely and cyclically reduced words of ${\mathbb{F}}_r$ of length L that are both Whitehead and SLPCI${}^{\pm }$ minimal, and where two vertices u and v are connected by an edge if there exists an element $\alpha \in W_{II}$ such that v is the SLPCI${}^{\pm }$ minimal representative of $\alpha (u)$.

Khan [21] used a similar construction, without inversion, to study the complexity of Whitehead’s Algorithm in the special case r = 2.

Proof.

Whitehead’s result shows that the partition by components of the Whitehead level graph is the same as the partition by $\text{Aut}({\mathbb{F}}_r)$–orbits. It is clear from the definitions that two words in the same component of the length–L SLPCI${}^{\pm }$ graph are in the same component of the Whitehead level–L graph. We show the opposite. The essential observation is that the group W_I acts by conjugation on the set W_II.

Elements that differ by an element of W_I are in the same PCI class, so suppose $\alpha \in W_{II}$ and $\alpha (u_1)=u_2$ where $u_i=a_i{v}_i{a}_i^{-1}$ with v_i cyclically reduced, and suppose ${\sigma }_i(v_i^{{ϵ}_i})=w_i$ is the SLPCI${}^{\pm }$ minimal representative of v_i, where ${\sigma }_i\in W_I$ and ${ϵ}_i\in \pm 1$. Let $\alpha \prime :={\sigma }_1°\alpha °{\sigma }_1^{-1}$. Since $\alpha \prime$ is a W_I conjugate of an element of W_II, $\alpha \prime \in W_{II}$. Thus $\alpha \prime \in W_{II}$ takes w₁ to $\alpha \prime (w_1)\sim {\sigma }_1(u_2^{{ϵ}_1})$, which is in the same PCI${}^{\pm }$ class as u₂ (apply ${\sigma }_2°{\sigma }_1^{-1}$, conjugate, and invert, if necessary), so w₂ is the SLPCI${}^{\pm }$ minimal representative of $\alpha \prime (w_1)$. □

The lemma says we can run the naive algorithm but instead of enumerating all words of a fixed length, it’s enough to enumerate SLPCI${}^{\pm }$ minimal ones. This is a benefit because SLPCI${}^{\pm }$ minimality is falsifiable by a subword: if w is a word that contains a prefix p and a (cyclic) subword v of equal length such that there is a W_I automorphism that takes v or $v^{-1}$ to a word that lexicographically precedes p, then w is not SLPCI${}^{\pm }$ minimal. We modify the standard odometer algorithm for enumerating words of a fixed length by checking in the induction step for such subwords v. If we find such a subword then we increment the odometer at the rightmost position of v. This potentially allows us to skip over large ranges of words that do not contain any SLPCI${}^{\pm }$ minimal words.

Consider the following example: suppose we have the ordering $B<A<a<b$ for the rank 2 free group $〈a,b〉$, where capitalization denotes inversion. Suppose we are enumerating length 10 words, and we are given a word of the form $\mathit{BAA}*******$. Notice the prefix BA and the subword AA. There is a W_I automorphism sending AA to BB, which precedes BA lexicographically, so no word of the form $\mathit{BAA}*******$ is SLPCI${}^{\pm }$ minimal, and to get the next candidate we increment at the third position, the right-most position of the subword AA, to get the next candidate word. Thus we skip over the 7³ possible freely reduced words of the form $\mathit{BAA}*******$. Similarly, no word that begins with BA and contains equal consecutive letters is SLPCI${}^{\pm }$ minimal. We include the possibility that v is a cyclic subword, meaning that it may wrap from the end of w around to the beginning. So words of the form $BA******B$ are not SLPCI${}^{\pm }$ minimal, because they contain BB as a cyclic subword. In the case the “right-most position” of the subword should be interpreted in terms of the original word, so the right-most position of a wrapped subword is the last letter of the original word. Thus, when the problematic subword v wraps, incrementing on its right-most position does not skip over any words. However, it is still convenient that such a subword falsifies SLPCI${}^{\pm }$ minimality for us.

As the wordlength grows and exponential growth in the free group builds up steam, it is impractical to hold the entire SLPCI${}^{\pm }$ graph in memory. Instead, for each SLPCI${}^{\pm }$ and Whitehead minimal word w we start constructing its graph component as described in Lemma 4.1. If in this construction we encounter a shortlex predecessor then we throw w away and proceed to the next candidate. If no such element occurs, then w is minimal in its component. This procedure would be most effective if the SLPCI${}^{\pm }$ graph consists of many small components, and if in each component it is easy to verify whether or not a given word is the shortlex minimal one. Unfortunately, for the latter case, there do exist examples of components with shortlex local minima. For example, here is a component of the graph in rank 2 at length 9 (Capitalization indicates inversion, and the base ordering is $B<A<a<b$.) that contains a word $w:=\mathit{BBABBAAbA}$ that is a shortlex local minimum but not the global minimum in its component:$$\mathit{BBABBAAbA}-\mathit{BBABAbAbA}-\mathit{BBBABBAAA}.$$

The edges in this example are determined as follows: Apply the W_II automorphism $A\mapsto bA,b\mapsto b$ to BBABBAAbA to get BABAbAbbA. It turns out that the SLPCI${}^{\pm }$ representative for this word is in the SLPCI class of its inverse, which is aBBaBabab. There is only one matching consecutive pair, so cyclically permute to put that in the front of the word, and then apply the W_I automorphism $a\mapsto A,b\mapsto b$ to get BBABAbAbA. This is the middle vertex of the graph. To get from the middle to the right-hand vertex apply the W_II automorphism $a\mapsto ba,b\mapsto b$ and cyclically permute.

So, to verify that w is not the global minimum in its component we have to construct the entire component. That is easy in this example because the component is small. It turns out that most components are small. Figure 4 shows the observed number of components of each size in rank 3 at length 15. In this example 99% of the components have size at most 14.

Fig. 4 Number of connected components of the SLPCI${}^{\pm }$ graph by size in rank 3 at length 15.

For all³ $11\le L\le 15$ the component frequency plot looks much like Figure 4, with most values clustered left and one prominent spectrum at multiples of $\frac{1}{2}({(L-7)}^2+11(L-7)+30)$, with a unique largest component of size $\frac{L-7}{2}({(L-7)}^2+11(L-7)+30)$ represented by $C^{L-8}B\mathit{CACaBAA}$.

Myasnikov and Shpilrain [26] proved that components of the Whitehead level–L graph in rank r = 2 have size bounded by a polynomial of degree $2r-2$ in L, see also [7, 21], and conjectured that this should be true in higher ranks (see the conjecture and discussion following [26, Corollary 1.2]). The conjecture has been proven in some cases with additional technical hypotheses [22, 23]. Myasnikov and Shpilrain also, citing experimental evidence, give a specific quartic polynomial for rank 3 bounding the size of the largest component, and a representative of that component. Their representative is in the same $\text{Aut}({\mathbb{F}}_3)$–orbit as $C^{L-8}B\mathit{CACaBAA}$.

We enumerated $\text{Aut}({\mathbb{F}}_r)$ equivalence classes of cyclic subgroup up to length 16 for $r\le 4$. Table 1 shows the resulting number of representatives of each length. Lists of these representatives can be found at: https://www.mat.univie.ac.at/∼cashen/orgcensus/

Table 1 The number of length L $\text{Aut}({\mathbb{F}}_r)$ equivalence classes of cyclic subgroup not contained in a proper free factor of ${\mathbb{F}}_r$, for $L\le 16$.

L	${\mathbb{F}}_1$	${\mathbb{F}}_2$	${\mathbb{F}}_3$	${\mathbb{F}}_4$
1	1	0	0	0
2	1	0	0	0
3	1	0	0	0
4	1	2	0	0
5	1	3	0	0
6	1	8	1	0
7	1	12	5	0
8	1	34	18	2
9	1	71	98	5
10	1	217	522	35
11	1	515	3,124	315
12	1	1,423	16,866	7,106
13	1	3,834	96,086	93,460
14	1	11,816	582,844	1,124,764
15	1	33,321	3,481,458	11,679,597
16	1	95,440	19,514,686	109,264,221

Our tools for working with free groups and enumerating equivalence classes are extensions of those developed with Manning for [5].

4.2 Computing imprimitivity rank

We compute imprimitivity rank by inductively building Stallings graphs Γ representing finite rank subgroups H of ${\mathbb{F}}_r$ containing w as an imprimitive word. Since we are interested in minimal rank subgroups containing w, we may assume that the loop labeled by w traverses every edge of Γ. Furthermore, since we are interested in subgroups containing w as an imprimitive element, we may assume w traverses every edge at least twice. In particular, Γ can contain at most $\lfloor |w{|}_a/2\rfloor$ edges labeled a for each basis element a. These constraints cut down on the number of possible graphs Γ.

To be more specific about the inductive construction: we start with a base vertex. The word w must label a loop in the finished Stallings graph, so there must be an outgoing edge at the base vertex labeled with the first letter of w. There are two choices: we could make the edge a loop or we could introduce a new vertex and have the edge not be a loop. Say that there are the two “candidate graphs for the length 1 prefix.”

Now suppose we have some number of candidate graphs for the length n prefix for $n<\left|w\right|-1$. By construction, for each candidate, the length n prefix of w labels a path in the graph starting at the base vertex and ending at some other vertex v. If v already has an outgoing edge labeled by the $(n+1)$–st letter of w then there is nothing to do, pass this graph on to be a candidate for the length n + 1 prefix. If not, consider all possible ways of introducing such an edge that would result in a folded graph. This could mean introducing an edge that connects to a new vertex, or introducing an edge that connects to an existing vertex that does not already have an incoming edge with the same label. Any of the resulting graphs that also satisfy the edge counting constraints of the first paragraph are passed on to be candidates for the length n + 1 prefix.

Next, consider the candidates for the length $\left|w\right|-1$ prefix. For each such graph the length $\left|w\right|-1$ prefix of w labels a path from the base vertex to some vertex v. Now there is no choice, the final edge must lead back to the base vertex so that w labels a loop. Let us say that the last letter of w is a. If there is already an outgoing edge at v labeled a that leads to the base vertex then pass this graph on to be a candidate for w. If there is no outgoing edge at v labeled a and no incoming edge labeled a at the base vertex, and if there are less than $\lfloor |w{|}_a/2\rfloor$ edges labeled a in the graph, then add a new edge labeled a from v to the base vertex, and pass the resulting graph on to be a candidate for w.

Finally, we have some number of graphs that are “the candidates for w”. By construction, each of these is a folded based graph in which w labels a based loop. It is a based core graph because w was freely reduced, and the w–loop traverses every edge. Furthermore, every Stallings graph satisfying the edge counting constraints and containing a based loop labeled w that traverses every edge will appear in the list of candidates. Each such graph defines a subgroup of the free group containing w. For each of these, we choose a basis, write w in terms of that basis, and then check using Whitehead’s Algorithm if w is primitive in this subgroup. Discard any candidates in which w is primitive. The minimal rank of the remaining candidates is the imprimitivity rank of w. In principle there could be multiple candidates realizing the imprimitivity rank.

Louder and Wilton define w–subgroups to be those minimal rank subgroups containing w as an imprimitive element that are maximal with respect to inclusion among all such subgroups. They prove that a word w of imprimitivity rank 2 has a unique w-subgroup. On the other hand, elements of imprimitivity rank r in ${\mathbb{F}}_r$ obviously have a unique w–subgroup, the group ${\mathbb{F}}_r$ itself. For intermediate imprimitivity ranks the uniqueness of w-subgroups is an open question. We observe that all elements in our enumeration have unique w-subgroups:

Proposition 4.2.

If $w\in {\mathbb{F}}_4$ has imprimitivity rank 3 and length at most 16 then it has a unique w–subgroup.

Table 2 shows the observed number of equivalence classes of cyclic subgroups of given imprimitivity rank at word lengths 14-16.

Table 2 The number of length L $\text{Aut}({\mathbb{F}}_r)$ equivalence classes of cyclic subgroup not contained in a proper free factor, by rank and imprimitivity rank, for $14\le L\le 16$.

L = 14	irank	${\mathbb{F}}_1$	${\mathbb{F}}_2$	${\mathbb{F}}_3$	${\mathbb{F}}_4$
	1	1	12	5	0
	2	0	11804	364	6
	3	0	0	582475	321
	4	0	0	0	1124437
L = 15
	1	1	3	0	0
	2	0	33318	258	7
	3	0	0	3481200	1055
	4	0	0	0	11678535
L = 16
	1	1	34	18	2
	2	0	95406	2765	111
	3	0	0	19511903	11023
	4	0	0	0	109253085

Algorithms in this section can be found in imprimitivity_rank.py of github:cashenchris/freegroups.

4.3 Verifying hyperbolicity

Given an imprimitive, Whitehead minimal word $w\in {\mathbb{F}}_r$ that is not a proper power, we check (non)hyperbolicity of $G:={\mathbb{F}}_r/〈\mathrm{}〈w〉\mathrm{}〉$ using the following tests:

1. Check if the presentation is cyclically pinched, that is, if it can be written as a product of two finite rank free groups amalgamated over a cyclic subgroup. This is true if a cyclic permutation of w can be written as a product uv such that u and v are nontrivial words with no generators of ${\mathbb{F}}_r$ in common. In this case, G is nonhyperbolic if u and v are both proper powers, and hyperbolic otherwise.⁴ If not cyclically pinched, then

2. check if w satisfies the hypotheses of Ivanov and Schupp [17, Theorem 3 or 4], and if so, whether G is hyperbolic or not. If Ivanov-Schupp does not apply, then

3. check if w satisfies one of the small cancelation conditions C(7), $C(5)-T(4),C(4)-T(5)$, or $C(3)-T(7)$, in which case G is hyperbolic via results of Gersten and Short [11]. Otherwise,

4. check if w satisfies the $C\prime (1/4)-T\prime$ hyperbolicity condition of Blufstein and Minian [2]. If not,

5. check hyperbolicity of G with GAP. Finally, if that fails, then

6. verify hyperbolicity of G with kbmag.

The algorithm can be found in geometryofonerelatorgroups.py of:

github:cashenchris/onerelatorgroups

We remark that the above checks cannot certify a counterexample to the Louder-Wilton conjecture, since the only checks that can conclusively return “nonhyperbolic” are (1) and (2). It is easy to verify that the nonhyperbolic cyclically pinched case implies imprimitivity rank 2, and we checked this for the Ivanov-Schupp case in Proposition 1.2. Thus, the worst that could happen is that we encounter a word with high imprimitivity rank whose hyperbolicity we are unable to decide with the above tools. We did not encounter any such words. In principle, if ${\mathbb{F}}_r/〈\mathrm{}〈w〉\mathrm{}〉$ is hyperbolic, this will be verified by kbmag [15], given enough time and computing resources, but it will run forever in the nonhyperbolic case. Even in our experiments kbmag took up to several minutes to succeed, making it unsuitable for checking hundreds of millions of examples. Checks (1)–(5) are faster, but sometimes inconclusive.

Items (1)–(4) we implemented ourselves.

In item (5) we used the function IsHyperbolic (with parameter $\epsilon =1/100$) of the GAP [9] package walrus [29] which is based on an algorithm of Holt et al. [16]. The function tries to verify that the RSym curvature distribution scheme defined in [16] succeeds on every van Kampen diagram over the presentation defined by w. This step is crucial, since although small cancelation words are generic, there are still far too many words that evade checks (1)–(4) to feasibly check with kbmag. Step (5) is based on the second author’s investigation of the application of RSym and its variants to hyperbolicity of one-relator groups [14]. (Another recent application of RSym, to a different class of groups, was conducted by Chalk [6].)

The implementation of IsHyperbolic in the version of walrus we used does not capture the full power of the algorithms described in [16]:

• IsHyperbolic quits and answers inconclusively if it encounters certain potential bad van Kampen diagrams, but sometimes it can be checked by hand that such a diagram does not really exist.

• The RSym algorithm in [16] takes a depth parameter d. Success for any d implies hyperbolicity. IsHyperbolic only implements d = 1.

• [16] also defines an enhanced version of RSym called $\mathit{RSy}{m}^{+}$ that is not implemented.

The second author showed by hand that the enhanced version of RSym often succeeds when IsHyperbolic is inconclusive. For example:

Theorem 4.3

([14, Theorem 5.6]). If $w\in {\mathbb{F}}_3$ has imprimitivity rank 3 and length at most 12 then $\mathit{RSy}{m}^{+}$ succeeds at depth 2.

We considered implementing an enhanced RSym algorithm, but it turned out in our experiments that Checks (1)-(5) caught enough words that kbmag could finish off the rest in a reasonable amount of time.

After our experiments had finished and the first version of the article was in preparation, an improvement of [2] appeared [3]. It would be interesting to know if this could improve our results, in particular if the new techniques can catch hyperbolic examples that walrus misses.

4.4 Word length 17 and beyond

We have described the experiments up to length 16. To extend Theorem 1.1 to length 17 we altered the algorithm. It turns out that hyperbolicity checks (1)–(5) are fast compared to computing equivalence classes and imprimitivity ranks. Also, the imprimitivity rank computation can be short-circuited to give a faster decision of whether the imprimitivity rank is greater than 2. For length 17 we enumerated SLPCI${}^{\pm }$ and Whitehead minimal words and checked for hyperbolicity using checks (1)-(5) first. If some check answered ‘hyperbolic’ we moved on to the next candidate. Otherwise, we checked if the imprimitivity rank was equal to 2. If so, we moved on to the next candidate. In the remaining cases where hyperbolicity was inconclusive and imprimitivity rank was greater than 2, then we proceeded to check if the word was the the shortlex minimal generator of a cyclic subgroup in its $\text{Aut}({\mathbb{F}}_r)$ equivalence class, and if so verified hyperbolicity with kbmag.

This still took $\sim \mathrm{}4$ years of CPU time. The problem is completely parallelizable over the words of fixed length in a free group, so conceivably our programs could be run on a larger cluster to extend the results to length 18 or 19, if there were any particular reason to expect that a counterexample would be revealed at these lengths. We did have a reason to push as far as length 17: in rank 3 at length at most 12, kbmag is not necessary—checks (1)-(5) always succeed in verifying hyperbolicity. We conjectured, and verified, that the same phenomenon would repeat in rank 4—checks (1)-(5) suffice up to length 16, but beginning with length 17 additional complexity appears that requires kbmag. This leaves us with the question of whether in rank r all words of high imprimitivity rank and length at most 4r can be verified hyperbolic using only checks (1)-(5), or, similarly to Theorem 4.3, using some enhancement of RSym? If so, this would improve Corollary 1.4.

4.5 Stable commutator length

The commutator length (cl) of an element in the commutator subgroup of a group is the minimal number of factors in the expression of that element as a product of commutators. The stable commutator length (scl) is $\text{scl}(w):=\underset{n\to \infty }{\lim }\text{cl}(w^n)/n$. Heuer [13, Conjecture 6.3.2] conjectures a generalization of the Duncan-Howie scl-gap theorem [8] saying that $\text{scl}\ge (\text{irank}-1)/2$. We confirm Heuer’s conjecture on our dataset:

Proposition 4.4.

For all nontrivial w in the commutator subgroup of ${\mathbb{F}}_4$ with $\left|w\right|\le 16$, we have $\text{scl}(w)\ge (\text{irank}(w)-1)/2$.

We computed stable commutator lengths with scallop [4]. The results are shown in Figure 5.

Fig. 5 The number of $\text{Aut}({\mathbb{F}}_4)$ equivalence classes of cyclic subgroups of length at most 16 by stable commutator length and imprimitivity rank.

Acknowledgments

We thank Henry Wilton for his comments on an earlier draft, in particular for the suggestion to check Heuer’s conjecture.

Declaration of Interest

No potential conflict of interest was reported by the author(s).

Funding

The first author is supported by the Austrian Science Fund (FWF): P 30487-N35.

Notes

1 We ran 12 x 4 core Intel Core i5-4670S @ 3.10GHz for two months.

2 The terminology is imperfect. Puder and, following him, Louder and Wilton, use the term “primitivity rank.” The motivation is that Puder’s work shows that as this number increases, the words “behave more and more like primitive words,” in a specific quantifiable sense. We use ‘imprimitivity rank’ because it is the smallest rank of a subgroup for which the word becomes imprimitive upon inclusion into that subgroup. Compare, for instance, to the “primitivity index” of Gupta and Kapovich [12], which is the smallest index of a subgroup for which the element becomes primitive upon lifting to that subgroup.

3 The formula for the size of the component containing $C^{L-8}B\mathit{CACaBAA}$ has been confirmed up to L = 25, but we have not computed the full component frequency distribution for L > 15.

4 This is well known. If both u and v are proper powers it is easy to produce a ${\mathbb{Z}}^2$ subgroup, so the group is not hyperbolic. If at least one of them is not a proper power then hyperbolicity can be verified by the combination theorem [1].