Proof. If \(u\) and \(v\) commute, then \(H(u,v)\) is cyclic, so \(\varphi_{u,v}\) cannot be injective. Conversely, if \(u\) and \(v\) do not commute, then \(H(u,v)\) is a non-cyclic subgroup of the free group \(F_2\) generated by two elements. Hence \(H(u,v)\) is free of rank two, and one can show that the images of \(a\) and \(b\) freely generate the image of \(\varphi_{u,v}\). Therefore \(\varphi_{u,v}\) is injective. ◻

Proof. Suppose first that \(\varphi\) is prime. Then \(\varphi\) is injective by definition. If there were a subgroup \(K\) with \(H<K<F_2\) and \(\operatorname{rk}K=2\), choose an isomorphism \(\alpha\colon F_2\to K\). Since \(H\leq K\), the map \(\beta=\alpha^{-1}\circ\varphi\colon F_2\to F_2\) is an injective endomorphism and \(\varphi=\alpha\circ\beta\). The subgroup \(K\) is proper in \(F_2\), so \(\alpha\) is not an automorphism. Also \(H<K\), so \(\beta(F_2)<F_2\), and hence \(\beta\) is not an automorphism. This contradicts primeness. Therefore no such subgroup \(K\) exists.

Conversely, suppose that \(\varphi\) is injective and that there is no subgroup \(K\) with \(H<K<F_2\) and \(\operatorname{rk}K=2\). If \(\varphi=\alpha\circ\beta\) with \(\alpha,\beta\colon F_2\to F_2\) endomorphisms and neither an automorphism, then the injectivity of \(\varphi\) implies that \(\beta\) is injective. Moreover, \(\alpha(F_2)\) contains \(H=\varphi(F_2)\), which has rank two because \(\varphi\) is injective. Hence \(\alpha(F_2)\) is non-cyclic, and therefore \(\alpha\) is injective by Lemma 1. It follows that \(H=\varphi(F_2)=\alpha(\beta(F_2))<\alpha(F_2)<F_2\). Since \(\alpha\) is injective, \(\alpha(F_2)\) is free of rank two. Thus \(\alpha(F_2)\) is a proper intermediate rank-two subgroup, contradiction. Therefore \(\varphi\) is prime. ◻

Proof. If \(H\) were contained in a proper free factor \(L\) of \(K\), then \(\operatorname{rk}L\leq 1\) because \(K\) has rank two. This is impossible since \(H\) is non-cyclic. ◻

Proof. Let \(\varphi\colon F_2\to F_2\) be injective and put \(H=\varphi(F_2)\). If \(\varphi\) is not prime, Lemma 2 gives a proper intermediate rank-two subgroup \(H<K<F_2\). Choosing an isomorphism \(\alpha\colon F_2\to K\) gives a nontrivial factorization \(\varphi=\alpha\circ(\alpha^{-1}\circ\varphi)\). Iterating this procedure corresponds to passing upward in the finite poset \(P_2(H)\), so the process terminates. Maximal chains in \(P_2(H)\) therefore give prime factorizations. Conversely, any prime factorization determines such a chain, up to the evident freedom of inserting inverse automorphisms between adjacent factors. Since \(P_2(H)\) is finite, only finitely many chains, and hence only finitely many such factorizations, occur. ◻

Proof. Using the Hanna-Neumann inequality [@Mineyev], \(\max\{\operatorname{rk}(K\cap L)-1,0\}\leq (\operatorname{rk}K-1)(\operatorname{rk}L-1)=1\), so \(\operatorname{rk}(K\cap L)\leq 2\). On the other hand, \(H\leq K\cap L\), and since \(H\) is non-cyclic, the subgroup \(K\cap L\) is non-cyclic. Hence \(\operatorname{rk}(K\cap L)=2\). ◻

Proof. The set \(P_2(G)\) is nonempty because \(F_2\in P_2(G)\), and it is finite by the preceding corollary. If \(P_2(G)=\{K_1,\dots,K_m\}\), then repeated application of the Proposition 1 shows that \(K_1\cap\cdots\cap K_m\) still has rank two and contains \(G\). It is therefore the unique minimal element of \(P_2(G)\). ◻

Proof. Finiteness and the meet formula were proved above. For the join, let \(K,L\in P_2(H)\) and set \(G=\langle K,L\rangle\). Then \(G\) is finitely generated and non-cyclic, so \(\operatorname{cl}_2(G)\) exists. It contains \(K\) and \(L\), and it is contained in every rank-two subgroup containing both. Hence it is the least upper bound of \(K\) and \(L\) in \(P_2(H)\). ◻

Proof. Let \(H=\langle b^2,\;a^{-1}b^2a\rangle\leq F(a,b)\). The folded labelled core graph of \(H\) looks as follows: \[\begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/pksnoxfg.png}\label{scejmrlu}\end{figure}\tag{1}\] The corresponding rank-two overgroups are represented by the following partitions of the vertex set \(\{0,1,2,3\}\): \[\begin{array}{cccccccccccc } T&=&0000,& A&=&0011,& B&=&0012,& C&=&0101,\\ D&=&0110,& E&=&0122,& H&=&0123.& \end{array}\] The resulting Hasse diagram is \[\begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/lvopxmqt.png}\label{dgxnrfks}\end{figure}\tag{2}\] Thus the Hasse diagram has seven elements. Taking \(x=B\), \(y=C\), and \(z=A\), we have \(x\leq z\), \(y\wedge z=H\), and hence \(x\vee(y\wedge z)=B\). On the other hand, \(x\vee y=T\), so \((x\vee y)\wedge z=A\). Therefore \(x\vee(y\wedge z)=B\neq A=(x\vee y)\wedge z\), and the modular law fails. ◻

Proof. The folded core graph of \(H_p\) consists of two directed \(a\)-cycles of length \(p\), joined by one \(b\)-edge. Since \(p\) is prime, a folded quotient of a directed \(p\)-cycle is either again a \(p\)-cycle or a single vertex with an \(a\)-loop. Moreover, if a vertex of one \(a\)-cycle is identified with a vertex of the other and neither cycle is collapsed, then folding forces the two cycles to be identified with a fixed cyclic shift. There are exactly \(p\) such diagonal identifications.

The rank-two quotients are therefore as follows: the original graph; the \(p\) diagonal quotients; two quotients in which exactly one of the two \(a\)-cycles is collapsed to an \(a\)-loop; one quotient in which both \(a\)-cycles are collapsed but the endpoints of the \(b\)-edge remain distinct; and finally the rose, hence the full group \(F(a,b)\). Altogether this yields \(1+p+2+1+1=p+5\) rank-two overgroups.

Writing \(D_0,\dots,D_{p-1}\) for the diagonal quotients, \(L\) and \(R\) for the two quotients in which exactly one \(a\)-cycle is collapsed, and \(M\) for the quotient in which both \(a\)-cycles are collapsed but the endpoints of the \(b\)-edge remain distinct, the Hasse diagram has the schematic form \[\begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/wjtymkbv.png}\label{zhcoauve}\end{figure}\tag{3}\] In particular, the chain \[H_p<L<M<F(a,b)\] has length three, and no longer chain can occur from the description above. ◻

Proof. It suffices to show that \(u\) and \(v\) do not commute, since two noncommuting elements of \(F_2\) generate a free subgroup of rank two, and hence the given two generators freely generate it.

Suppose that \(u\) and \(v\) commute. Then they lie in a common cyclic subgroup of \(F_2\). Hence their cyclic reductions are positive powers of a common cyclically reduced word, up to cyclic conjugacy and inversion. This contradicts \(L\)-cleanness. Thus \(u\) and \(v\) do not commute, and the claim follows. ◻

Proof. Let \(\bar X\) be the graph obtained from \(X\) by suppressing degree-two vertices. Since \(X\) is a core graph, every vertex of \(\bar X\) has degree at least three, except in the case of a single vertex with loop-edges. Since \(b_1(\bar X)=2\), we have \[|E(\bar X)|-|V(\bar X)|+1=2,\] and hence \(|E(\bar X)|=|V(\bar X)|+1\). Therefore \[\sum_{x\in V(\bar X)}(\deg(x)-2) = 2|E(\bar X)|-2|V(\bar X)| = 2.\] There are only three possibilities: one vertex with two loop-edges, two vertices joined by three edges, or two loop-vertices joined by a bridge. These are, respectively, the figure-eight, theta, and barbell types. ◻

Proof. Let \(y\in Y\) be the image of the basepoint of the pointed Stallings graph of \(H\). The pointed core graph \((Y,y)\) represents an intermediate subgroup \(J\) with \(H\leq J\leq K .\) Since \(H\) has rank two, \(J\) has rank at least two. Since \(Y\subseteq X\) and \(X\) has first Betti number two, \(Y\) has first Betti number at most two. Thus \(Y\) has first Betti number exactly two.

If \(Y\neq X\), then \(Y\) is a proper connected core subgraph of the connected core graph \(X\). Every component of the closure of \(X\setminus Y\) must contribute a cycle relative to \(Y\); otherwise it would be a tree attached to \(Y\) at a single vertex and would contain an edge not lying on any reduced closed path, contrary to the fact that \(X\) is a core graph. Hence adjoining \(X\setminus Y\) to \(Y\) strictly increases the first Betti number. This contradicts \(b_1(Y)=b_1(X)=2\). Therefore \(Y=X\). ◻

Proof. Choose a subpath \(I\subset e\) of length \(L\). Every traversal of \(e\) contains a traversal of \(I\), possibly with the opposite orientation. If two traversals of \(e\) have the same orientation, then the label of \(I\) occurs twice as a cyclic length-\(L\) subword among \(u\) and \(v\). If the orientations are opposite, then the same label occurs once in one of \(u,v\) and once in one of \(u^{-1},v^{-1}\). In either case there are two distinct cyclic occurrences of the same reduced word of length \(L\), contradicting \(L\)-cleanness. ◻

Proof. Put \(d=|c|\). The cyclic word \(w\) is periodic with period \(d\). Hence the length-\(L\) cyclic subword starting at a given position depends only on that position modulo \(d\).

Since \(|w|=|m|d\geq L\), length-\(L\) cyclic subwords are defined. Because \(|m|\geq 2\), the cyclic word \(w\) has at least two distinct positions in each congruence class modulo \(d\). Choose any cyclic starting position \(i\). The starting position \(i+d\), taken modulo \(|w|\), is distinct from \(i\), and by periodicity the length-\(L\) cyclic subword starting at \(i+d\) is equal to the one starting at \(i\). Thus \(w\) has two distinct cyclic occurrences of the same reduced word of length \(L\). ◻

Proof of Proposition 7. Let \(X=\Gamma(K)\). By the stem-removing reduction above, after replacing \(H\leq K\) by a common conjugate, we may assume that the basepoint of \(K\) lies in \(X\). The elements \(u\) and \(v\) then determine based closed paths in \(X\).

Let \(Y\subseteq X\) be the core of the image of the pointed Stallings graph \(\Gamma(H)\) in \(X\). By Lemma 2.6, we have \(Y=X\). Thus the based closed paths labelled by \(u\) and \(v\) fill the whole core graph \(X\).

Suppose that \(X\) has a topological edge \(e\) of length at least \(L\). We first observe that \(e\) is traversed by at least one of the cyclic reductions of \(u\) and \(v\). Indeed, if not, then every occurrence of \(e\) in the based loops labelled by \(u\) and \(v\) is contained in the initial-final cancellation of one of these loops. Since the based loops fill \(X\), this can only occur in the barbell case: the edge \(e\) is the bar, and the cyclic reductions of \(u\) and \(v\) lie in the two rank-one lobes. Let \(c_1\) and \(c_2\) be cyclically reduced generators of the rank-one subgroups represented by the two lobes. Thus, up to interchanging \(u\) and \(v\), their cyclic reductions are powers \(c_1^m\) and \(c_2^n\). By Lemma 8 and \(L\)-cleanness, the cyclic reductions of \(u\) and \(v\) have length at least \(6L\), so \(|m| = |n| = 1\). Since the bar of a barbell is a separating tree-bridge, it contributes nothing to \(\pi_1\), and \(\pi_1(X)\) is freely generated by (conjugates into a common basepoint of) the two lobe generators \(c_1\) and \(c_2\). As \(|m| = |n| = 1\), the elements \(u\) and \(v\) are conjugate to \(c_1^{\pm1}\) and \(c_2^{\pm1}\), so they generate all of \(\pi_1(X)\). Hence \(H = K\), contrary to \(H \ne K\).

Therefore \(e\) is traversed by at least one of the cyclic reductions of \(u\) and \(v\). If it is traversed at least twice in total, counting both orientations and both cyclic words, then Lemma 2.7 contradicts \(L\)-cleanness. Hence \(e\) is traversed exactly once in total by the cyclic reductions of \(u\) and \(v\).

If \(e\) is separating, then every cyclic closed path in \(X\) traverses \(e\) algebraically zero times and, in particular, an even number of times in total. Thus \(e\) cannot be traversed exactly once by the union of the two cyclic paths. Hence \(e\) is nonseparating.

Remove the interior of \(e\) from \(X\) and call the resulting connected graph \(Y=X\setminus \operatorname{int}(e)\). Since \(X\) has rank two and \(e\) is nonseparating, \(Y\) has rank one. Exactly one of the two cyclic paths, say the path labelled by \(u\), traverses \(e\) once; the other path, labelled by \(v\), is contained in \(Y\).

Let \(c\) be a cyclically reduced generator of the rank-one subgroup represented by the core of \(Y\). Since the cyclic path labelled by \(v\) is contained in a rank-one graph, its cyclic label is a power of \(c\): \(v \sim_{\mathrm{cyc}} c^m\) for some nonzero integer \(m\). If \(|m|\geq 2\), then Lemma 8 contradicts \(L\)-cleanness, because the cyclic reduction of \(v\) has length at least \(6L\). Therefore \(|m|=1\).

Let \(p\) be the initial vertex of the unique traversal of \(e\) along the cyclic path labelled by \(u\). Simultaneously conjugating \(H\) and \(K\) by the label of a path from the original basepoint to \(p\) preserves all hypotheses and the strictness of the inclusion. It replaces \(u\) and \(v\) by conjugates whose cyclic reductions are cyclically conjugate to the original ones, so \(L\)-cleanness is preserved. Thus we may rebase \(X\) at \(p\) and still denote the resulting subgroup pair by \(H\leq_{\operatorname{alg}}K\) and the resulting generators by \(u,v\).

After this rebasing, the loop representing \(u\) starts with the unique traversal of \(e\), so \(u=er\), where \(r\) is a path in \(Y\) from the terminal vertex \(q\) of \(e\) back to \(p\). Also \(p\in Y\), and since the cyclic path labelled by \(v\) is contained in \(Y\), the element \(v\) lies in \(\pi_1(Y,p)\). Because \(\pi_1(Y,p)\) has rank one and the cyclic label of \(v\) is \(c^{\pm1}\), the element \(v\) generates \(\pi_1(Y,p)\).

Choose any path \(\beta\) in \(Y\) from \(p\) to \(q\). Then \(s=e\beta^{-1}\) is the stable loop obtained by adjoining the nonseparating edge \(e\) to \(Y\), so \(\pi_1(X,p)\) is generated by \(\pi_1(Y,p)\) together with \(s\). Since \(\beta r\) is a loop in \(Y\) based at \(p\), there exists \(n\in\mathbb{Z}\) such that \(\beta r=v^n\). Hence \(u=er=(e\beta^{-1})(\beta r)=s v^n\). Therefore \(s=u v^{-n}\) lies in \(H\). Since \(v\) already generates \(\pi_1(Y,p)\), we obtain \(H=\pi_1(X,p)=K\), contrary to the assumption that \(H \not =K\).

Thus no topological edge of \(X\) has length at least \(L\). Since a rank-two core graph has at most three topological edges, we obtain \(\operatorname{vol}(K)<3L\). ◻

Proof. Let \(X=\Gamma(K)\), and suppress degree-two vertices. By the rank-two classification lemma, the resulting topological graph is a figure-eight, a theta graph, or a barbell.

Assume first that \(\bar X\) is a figure-eight with loop lengths \(a,b\). After identifying the two orientations of each loop, the weighted \(4 \times 4\) transfer matrix reduces to \[M_{a,b}(r)= \begin{pmatrix} r^a & 2r^b \\ 2r^a & r^b \end{pmatrix}.\] The critical value \(r=\rho^{-1}\) is determined by \(\det\bigl(I-M_{a,b}(r)\bigr)=0,\) that is, \((1-r^a)(1-r^b)-4r^{a+b}=0.\) If \(a=b=1\), then the core is the rose and represents \(F_2\), contrary to \(K<F_2\). Hence, after relabelling, either \(a=1,b\geq 2\), or else \(a,b\geq 2\). Since the entries of \(M_{a,b}(r)\) decrease as \(a,b\) increase, the maximal proper figure-eight case is \((a,b)=(1,2)\). In this case the critical equation is \[(1-r)(1-r^2)-4r^3=0,\] or equivalently \(1-r-r^2-3r^3=0.\) Writing \(\rho=r^{-1}\), this becomes \(\rho^3-\rho^2-\rho-3=0.\) Thus the maximal figure-eight value is \(\rho_0\) using Cardano’s formula.

If \(\bar X\) is a theta graph, then every oriented ordinary edge has at most two allowed non-backtracking successors. Hence every row sum of the non-backtracking adjacency matrix \(B_X\) is at most \(2\), so \(\rho(X)\leq 2<\rho_0.\) The same row-sum bound holds for a barbell graph, so again \(\rho(X)\leq 2<\rho_0.\)

Therefore \(\rho(\Gamma(K))\leq \rho_0\) for every proper rank-two subgroup \(K<F_2\). Equality can occur only in the figure-eight case with loop lengths \(1\) and \(2\). ◻

Proof. Let \(X=\Gamma(K)\), let \(h=h(K)\), and let \(x\in X\) be the attachment point of the stem of \(\widehat\Gamma(K)\). Let \[F_{X,x}(z)=\sum_{n\geq 1} c_n(X,x)z^n\] be the generating series for non-backtracking closed paths in \(X\) based at \(x\). By the preceding discussion, the generating series \[F_K(z)=\sum_{n\geq 1}|K\cap S_n|z^n\] for reduced words in \(K\) satisfies \[F_K(z)=z^{2h}F_{X,x}(z).\] We therefore estimate \(F_{X,x}(z)\) uniformly.

The point \(x\) is either a branch vertex of \(\bar X\) or lies in the interior of a unique topological edge. In either case there are only boundedly many possible initial partial segments leaving \(x\) and terminal partial segments returning to \(x\). Consequently there are vectors \(u_{X,x}(z),v_{X,x}(z)\in \mathbb{C}^{\Omega_X}\) whose entries are finite sums of at most uniformly many monomials in \(z\), and a function \(g_X(z)\) such that \[F_{X,x}(z)=g_X(z)+u_{X,x}(z)^\ast\bigl(I-M_X(z)\bigr)^{-1}v_{X,x}(z).\] Here \(g_X(z)\) is either a polynomial with coefficients bounded by an absolute constant, or else \(x\) lies in the interior of a topological loop of length \(\ell\) and \[g_X(z)=2\sum_{n\geq 1} z^{n\ell}=\frac{2z^\ell}{1-z^\ell}.\] Indeed, if \(x\) does not lie in the interior of a topological loop, then a based non-backtracking closed path that never reaches a branch vertex has only finitely many possibilities, and these are recorded by a polynomial. If \(x\) does lie in the interior of a topological loop of length \(\ell\), then the closed non-backtracking paths that stay entirely in that loop are exactly the nonzero windings around the loop in one of the two orientations, giving the displayed geometric series. All remaining based closed paths are obtained by choosing an initial partial segment from \(x\) to a branch vertex, following a non-backtracking itinerary of oriented topological edges, and then taking a terminal partial segment back to \(x\). This is encoded by the displayed formula.

Set \(\rho_*=\frac{9}{4},\) and \(R=\rho_*^{-1}=\frac{4}{9}.\) By Lemma 9, every proper rank-two core has spectral radius at most \(\rho_0<\rho_*\). Therefore, at \(R=4/9\), the weighted transfer matrices are uniformly inside their disk of convergence. More explicitly, for \(|z|\leq R\), the entrywise absolute value of \(M_X(z)\) is dominated by one of the finitely many maximal matrices corresponding to the three topological types: the figure-eight of lengths \((1,2)\), the theta graph of lengths \((1,1,1)\), or the barbell graph of lengths \((1,1,1)\). In the theta and barbell cases the maximal matrix has row sums at most \(2R=8/9<1\). In the figure-eight case the maximal matrix is \[\begin{pmatrix} R & 2R^2 \\ 2R & R^2 \end{pmatrix},\] whose spectral radius is strictly smaller than \(1\) because its critical value is \(\rho_0^{-1}>R\). Hence the Neumann series \[\bigl(I-M_X(z)\bigr)^{-1}=\sum_{j\geq 0} M_X(z)^j\] is uniformly bounded for all proper rank-two \(K\) and all \(|z|\leq R\). In the polynomial case \(g_X(z)\) is uniformly bounded there, and in the loop case one has \[|g_X(z)|\leq \frac{2R}{1-R}=\frac{8}{5}.\] Since each entry of \(u_{X,x}(z)\) and \(v_{X,x}(z)\) is a sum of at most uniformly many monomials \(z^d\) and \(|z|\leq R<1\), these entries are also uniformly bounded there, the generating series \(F_{X,x}(z)\) is bounded by an absolute constant on that disk, independently of \(K\).

Therefore \(F_K(z)=z^{2h}F_{X,x}(z)\) is bounded by \(C_1R^{2h}\) on \(|z|\leq R\). By Cauchy’s estimate, the coefficient of \(z^n\) in \(F_K(z)\) satisfies \[|K\cap S_n|\leq C_1 R^{2h-n}=C_1 \rho_*^{\,n-2h}.\] Since \(|S_n|=4\cdot 3^{n-1}\), we obtain \(\frac{|K\cap S_n|}{|S_n|}\leq C_0\left(\frac{3}{4}\right)^n\left(\frac{9}{4}\right)^{-2h}\). ◻

Proof. After suppressing degree-two vertices, the graph has one of three topological types: figure-eight, theta, or barbell. Hence it has at most three topological edges.

For each of the three topological types, the number of choices of the lengths of the topological edges, subject to total length at most \(m\), is bounded by \((m+1)^3\). If a topological edge has length \(\ell\), then it admits at most \(4\cdot 3^{\ell-1}\) reduced labels. Since the total length is at most \(m\) and there are at most three topological edges, the total number of labellings is at most \(A_0 3^m\) for an absolute constant \(A_0>0\). Finally, a graph with at most \(m\) unoriented edges has at most \(m+1\) vertices, so the root contributes at most \(m+1\) choices.

Multiplying these bounds and absorbing the three topological types into the constant gives \[\#\{\text{rooted folded labelled rank-two cores with at most }m \text{ edges}\} \leq A(m+1)^4 3^m\] for an absolute constant \(A>0\). ◻

Proof. If \(|u_n|_{\mathrm{cyc}}\leq n-2k\), then \(u_n\) has the form \(u_n=r z r^{-1}\), where \(r\) is reduced of length \(k\) and \(z\) is reduced, or trivial, of length \(n-2k\). Thus the number of such words is at most \[|S_k|\cdot \max\{1,|S_{n-2k}|\} \leq C_0\,3^{n-k-1}\] for an absolute constant \(C_0\). Since \(|S_n|=4\cdot 3^{n-1}\), this gives \(\mathbb{P}\bigl(|u_n|_{\mathrm{cyc}}\leq n-2k\bigr)\leq C\,3^{-k}\).

For the second claim, write \(m=n-2k\) and fix a cyclically reduced word \(c=c_1\cdots c_m\) of length \(m\). The reduced words of length \(n\) whose cyclic reduction is \(c\) are exactly the words \(r c r^{-1}\) with \(|r|=k\) for which the concatenation is reduced. If \(k=0\), there is only the word \(c\) itself. If \(k\geq 1\), the last letter of \(r\) may be any of the two letters different from \(c_1^{-1}\) and \(c_m\), and once that last letter is fixed, the preceding \(k-1\) letters of \(r\) may be chosen arbitrarily subject only to reducedness. Hence there are exactly \(2\cdot 3^{k-1}\) such words \(r\), independently of \(c\). Therefore every cyclically reduced word of length \(m\) has the same number of preimages, proving the conditional uniformity. ◻

Proof. Because the law of \(C_m\) is invariant under cyclic rotation, we may place the first starting position at \(1\). Each chosen occurrence determines an interval of \(L\) consecutive positions in the original cyclic word \(C_m\); if an occurrence is taken in \(C_m^{-1}\), we first pull it back to the corresponding interval in \(C_m\) by reversing orientation and inverting labels. The union of the two resulting intervals has size at most \(2L\), so since \(m\geq 6L\) we may cut the cyclic word at a position outside this union and regard all relevant letters as lying in a genuine linear reduced word.

First note that a uniformly distributed cyclically reduced word of length \(m\) is obtained from a uniformly distributed reduced word of length \(m\) by conditioning on the last letter not being the inverse of the first. Given the first \(m-1\) letters, the last letter has three possible values, and at most one of them is forbidden by cyclic reduction. Hence this conditioning changes probabilities by at most the factor \(3/2.\) It is therefore enough to prove an exponential bound for a uniform reduced word.

Assume first that both occurrences lie in the same orientation of the word, so we are comparing two length-\(L\) blocks in a uniform reduced word \(W\). Let \(t\) be the distance between their starting positions. If \(t\geq L\), then the two blocks are disjoint, and after revealing the first block the second must equal one prescribed reduced word of length \(L\). Thus the probability is at most \(3^{-L}\).

If \(1\leq t<L\), then equality of the two blocks is equivalent to saying that the linear segment of length \(L+t\) spanning them has period \(t\). Once the first \(t\) letters are chosen, the next \(L\) letters are forced. Hence the number of possible reduced labels for that segment is at most \(4\cdot 3^{t-1}\), whereas the total number of reduced labels of length \(L+t\) is \(4\cdot 3^{L+t-1}\). So the probability is again at most \(3^{-L}\).

It remains to consider the case where one occurrence is taken in \(W^{-1}\). View that occurrence back in \(W\) as the reverse inverse of a length-\(L\) block. If the two corresponding length-\(L\) intervals in \(W\) are disjoint, then after revealing the first block the second interval must realize one prescribed reduced word, so the probability is at most \(3^{-L}\).

Assume finally that these two intervals overlap. Let \(I\) be the minimal linear segment of \(W\) containing their union, and write \(s=|I|\). Then \(L\leq s<2L\). Equality of the original block with the inverse occurrence induces an orientation-reversing involution on the positions of \(I\). A fixed point would force a letter to equal its own inverse, which is impossible, so every orbit has size two. Hence choosing the letters on one representative from each orbit determines the whole segment \(I\). Therefore the number of reduced labels on \(I\) compatible with the overlap condition is at most \(4\cdot 3^{\lceil s/2\rceil-1}.\) Since the total number of reduced labels of length \(s\) is \(4\cdot 3^{s-1}\), the probability of this overlap event is at most \(3^{-\lfloor s/2\rfloor}\leq 3^{-L/2}.\)

Thus, for a uniform reduced word, the probability is at most \(3^{-L/2}\) in all cases. Multiplying by the conditioning factor \(3/2\) and absorbing constants proves the lemma. ◻

Proof. Let \(\widehat u_n,\widehat v_n\) be the cyclic reductions of \(u_n\) and \(v_n\). Applying the previous lemma with \(k=\left\lceil \frac{n-6L}{2}\right\rceil\) gives \[\mathbb{P}\bigl(|\widehat u_n|<6L\text{ or }|\widehat v_n|<6L\bigr) \leq A_0\,3^{-\lceil (n-6L)/2\rceil} \leq A_0\,3^{-(n-6L)/2}.\]

Now condition on \(|\widehat u_n|=m\) and \(|\widehat v_n|=\ell\), where \(m,\ell\geq 6L\). By the second part of the previous lemma, \(\widehat u_n\) and \(\widehat v_n\) are independent uniformly distributed cyclically reduced words of lengths \(m\) and \(\ell\).

It remains to estimate repeated cyclic factors of length \(L\) in \(\widehat u_n,\widehat u_n^{-1},\widehat v_n,\widehat v_n^{-1}\). There are at most \((2m+2\ell)^2\leq 16n^2\) ordered pairs of cyclic starting positions.

For two fixed distinct starting positions in the same cyclic word, the fixed cyclic block estimate gives \[\mathbb{P}\bigl(\text{the two length-}L\text{ blocks agree}\bigr) \leq A_1 3^{-L/2}.\] If the two starting positions lie in different cyclic words, then after revealing the first block, the second block must realize one prescribed reduced word of length \(L\), so the same bound holds. Finally, a block in an inverse cyclic word is obtained from a block in the original cyclic word by reversing the order and inverting the letters. Thus the same bound also applies when one or both occurrences are taken in inverse cyclic words.

Therefore \[\mathbb{P}\bigl(\text{some length-}L\text{ cyclic factor repeats} \mid |\widehat u_n|=m,\;|\widehat v_n|=\ell\bigr) \leq A_2 n^2 3^{-L/2}.\] Averaging over \(m,\ell\geq 6L\) and combining with the first estimate gives \[\mathbb{P}\bigl((u_n,v_n)\text{ is not }L\text{-clean}\bigr) \leq A_0 3^{-(n-6L)/2}+A_2 n^2 3^{-L/2}.\] This proves the claim. ◻

Proof. Put \(L=\left\lfloor\frac{n}{7}\right\rfloor.\) Let \(\mathcal{G}_n\) be the event that \((u_n,v_n)\) is \(L\)-clean. By the explicit cleanliness lemma, \[\mathbb{P}(\mathcal{G}_n^c) \leq A_0\left(3^{-(n-6L)/2}+n^2 3^{-L/2}\right).\] Since \(L\leq n/7\) and \(L\geq n/7-1\), the right-hand side is at most \(A_1 n^2 3^{-n/14}.\) On \(\mathcal{G}_n\), the pair \((u_n,v_n)\) freely generates a rank-two subgroup.

Assume that \(\mathcal{G}_n\) holds and that there exists \(H_n<K<F_2\) with \(\operatorname{rk}K=2\). Then \(H_n\leq_{\operatorname{alg}}K\) by the rank argument in Section 1. The deterministic rank-two quotient lemma therefore gives \(\operatorname{vol}(K)<3L\).

Thus, on \(\mathcal{G}_n\), non-primality implies that both \(u_n\) and \(v_n\) lie in some proper rank-two subgroup \(K<F_2\) with \(\operatorname{vol}(K)<3L\).

By the counting lemma, the number of possible rooted folded labelled rank-two cores of volume less than \(3L\) is at most \(A_2 (L+1)^4 3^{3L}.\) For each such rooted core and each integer \(h\geq 0\), there are at most \(C_0'3^h\) possible reduced stem labels of length \(h\). Hence the number of proper rank-two subgroups \(K<F_2\) with \(\operatorname{vol}(K)<3L\) and \(h(K)=h\) is at most \(A_3 (L+1)^4 3^{3L+h}.\) For each fixed such subgroup, the return estimate gives \[\mathbb{P}(u_n\in K,\;v_n\in K) \leq C_0^2 \left(\frac{3}{4}\right)^{2n}\left(\frac{9}{4}\right)^{-4h}.\]

Therefore \[\begin{align} &\mathbb{P}\bigl(\exists K<F_2:\;\operatorname{rk}K=2,\;\operatorname{vol}(K)<3L, \;u_n,v_n\in K\bigr) \\ &\qquad\leq A_4 (L+1)^4 3^{3L} \left(\frac{3}{4}\right)^{2n} \sum_{h\geq 0} 3^h\left(\frac{9}{4}\right)^{-4h}. \end{align}\] Since \(3\left(\frac{9}{4}\right)^{-4}=3\left(\frac{4}{9}\right)^4=\frac{768}{6561}<1,\) the geometric sum is bounded by an absolute constant. Hence \[\mathbb{P}\bigl(\exists K<F_2:\;\operatorname{rk}K=2,\;\operatorname{vol}(K)<3L, \;u_n,v_n\in K\bigr) \leq A_5 (L+1)^4 3^{3L}\left(\frac{3}{4}\right)^{2n}.\] Since \(L\leq n/7\), we have \(3^{3L}\left(\frac{3}{4}\right)^{2n} \leq 3^{3n/7}\left(\frac{3}{4}\right)^{2n} \leq 3^{-n/14},\) because this is equivalent to \(3^{1/2}\leq \left(\frac{4}{3}\right)^2,\) and indeed \(243<256\). Therefore \[\mathbb{P}\bigl(\exists K<F_2:\;\operatorname{rk}K=2,\;\operatorname{vol}(K)<3L, \;u_n,v_n\in K\bigr) \leq A_6 (n+1)^4 3^{-n/14}.\] Combining this with the estimate for \(\mathcal{G}_n^c\) gives \(\mathbb{P}\bigl(\varphi_{u_n,v_n}\text{ is not prime}\bigr) \leq A n^B 3^{-n/14}\) for some absolute constants \(A,B>0\).

Finally, on \(\mathcal{G}_n\), the pair \((u_n,v_n)\) freely generates \(H_n\). Hence the endomorphism with \(a\mapsto u_n\) and \(b\mapsto v_n\) is injective. By Lemma 2, absence of a proper intermediate rank-two subgroup is exactly primeness. ◻

Proof. Put \(N=\min\{r,s\},\) and \(L=\left\lfloor\frac{N}{7}\right\rfloor.\) Let \(\widehat U_r\) and \(\widehat V_s\) be the cyclic reductions of \(U_r\) and \(V_s\). Applying the cyclic cancellation lemma separately to \(U_r\) and \(V_s\) gives \[\mathbb{P}\bigl(|\widehat U_r|<6L\text{ or }|\widehat V_s|<6L\bigr) \leq A_0\left(3^{-(r-6L)/2}+3^{-(s-6L)/2}\right) \leq A_1 3^{-N/14}.\] Conditioned on \(|\widehat U_r|=m\) and \(|\widehat V_s|=\ell\), with \(m,\ell\geq 6L\), the cyclic reductions are independent uniformly distributed cyclically reduced words of lengths \(m\) and \(\ell\). The four cyclic words \(\widehat U_r,\widehat U_r^{-1},\widehat V_s,\widehat V_s^{-1}\) have at most \(2m+2\ell\leq 2(r+s)\) cyclic starting positions in total. Therefore, by the fixed cyclic block estimate, \[\begin{gather} \mathbb{P}\bigl((U_r,V_s)\text{ is not }L\text{-clean} \mid |\widehat U_r|=m,\;|\widehat V_s|=\ell\bigr) \\ \leq A_2 (r+s)^2 3^{-L/2} \leq A_3 (r+s)^2 3^{-N/14}. \end{gather}\] On the good event, the pair freely generates a rank-two subgroup. If the associated endomorphism is not prime, then both words lie in a proper rank-two subgroup \(K\) with \(\operatorname{vol}(K)<3L\), by the deterministic quotient lemma. The counting lemma and the return estimate therefore give \[\begin{align} \mathbb{P}\bigl(\exists K<F_2:\;U_r,V_s\in K,\;\operatorname{vol}(K)<3L\bigr) &\leq A_4 (L+1)^4 3^{3L} \left(\frac{3}{4}\right)^{r+s} \sum_{h\geq 0} 3^h\left(\frac{9}{4}\right)^{-4h} \\ &\leq A_5 (N+1)^4 3^{3L} \left(\frac{3}{4}\right)^{2N} \\ &\leq A_6 (N+1)^4 3^{-N/14}. \end{align}\] Combining the three estimates and using \((N+1)^4\leq (r+s)^4\) proves the claim. ◻

Proof. The cases where \(u=1\) or \(v=1\) contribute \(O(3^{-n})\), which is harmless. For \(r,s\geq 1\), condition on \(|u|=r\) and \(|v|=s\). Since \(|S_r|=4\cdot 3^{r-1}\) and \(|B_n|=2\cdot 3^n-1,\) the contribution of lengths \(r,s\) is bounded by \[C 3^{r+s-2n}\cdot A(r+s)^B3^{-\min\{r,s\}/14}.\] Assume \(r\leq s\). Then \[3^{r+s-2n}3^{-r/14} \leq 3^{r+n-2n}3^{-r/14} =3^{-n}3^{13r/14} \leq 3^{-n/14}.\] The same bound holds when \(s\leq r\). Summing over the at most \((n+1)^2\) pairs of lengths contributes only a polynomial factor, so the whole probability is at most \(A'n^{B'}3^{-n/14}\) for suitable absolute constants \(A',B'\). Renaming the constants gives the claim. ◻

Proof. Choose a proper finite-index subgroup \(L<K\). Since \(K\) has rank two, such an \(L\) exists. Because \(K\) is a finite union of right cosets of \(L\), and multiplication by a fixed coset representative changes word length by only a bounded amount, the sets \(L\cap B_n\) and \(K\cap B_n\) have the same exponential growth rate: \[\limsup_{n\to\infty}|L\cap B_n|^{1/n}=\rho(K).\]

If \(u,v\in L\) do not commute, then \(\varphi_{u,v}\) is injective by Lemma 1, and \(\langle u,v\rangle\leq L<K<F_2.\) Hence \(\varphi_{u,v}\) is not prime by Lemma 2.

It remains to note that commuting pairs in \((L\cap B_n)^2\) are negligible on the exponential scale. For each nontrivial \(u\in F_2\), the centralizer \(C_{F_2}(u)\) is cyclic, so \(|C_{F_2}(u)\cap B_n|=O(n).\) Hence the number of commuting pairs in \((L\cap B_n)^2\) is at most \(O(n)|L\cap B_n|+O(|L\cap B_n|)\), which has exponential growth rate \(\rho(K)\), whereas \((L\cap B_n)^2\) has exponential growth rate \(\rho(K)^2\). Thus the noncommuting pairs in \((L\cap B_n)^2\) have exponential growth rate \(\rho(K)^2\).

Consequently \(|\mathcal{N}_n|\geq \exp\bigl((2\log \rho(K)+o(1))n\bigr).\) Since \(|B_n\times B_n|=\exp\bigl((2\log 3+o(1))n\bigr),\) we obtain \(\delta_{\mathrm{np}}\geq \frac{\log \rho(K)}{\log 3}.\) ◻

Proof. The Stallings core of \(K\) is a figure-eight with one loop of length \(2\), labelled by \(a^2\), and one loop of length \(1\), labelled by \(b\). Let \(r=\rho^{-1}\). Recall, by symmetry, the weighted non-backtracking transfer matrix reduces to \[\begin{pmatrix} r^2 & 2r \\ 2r^2 & r \end{pmatrix}.\] The critical value is determined by the condition that this matrix have spectral radius \(1\), equivalently \((1-r^2)(1-r)-4r^3=0.\) Thus \(1-r-r^2-3r^3=0.\) Putting \(\rho=r^{-1}\), this becomes \(\rho^3-\rho^2-\rho-3=0.\) As before, Cardano’s formula gives the displayed expression for \(\rho_0\). The lower bound now follows from Proposition 9. ◻

Proof. Let \(\Gamma=\ker\bigl(F(a,b)\to (\mathbb{Z}/2\mathbb{Z})^2\bigr)\) be the kernel of the homomorphism sending \(a\) and \(b\) to the two standard generators. Then \(\Gamma\) is a proper finite-index subgroup of \(F(a,b)\), and therefore \(|\Gamma\cap B_r|=3^{r+o(r)}.\)

Put \(m=\lfloor n/2\rfloor\). For \(x\in \Gamma\cap B_m\) and \(y\in \Gamma\cap B_n\) with \([x,y]\neq 1\), consider the endomorphism \[\psi_{x,y}(a)=x^2, \qquad \psi_{x,y}(b)=y.\] Since \(|x^2|\leq 2|x|\leq n\) and \(|y|\leq n\), this gives a pair in \(B_n\times B_n\).

Let \[\varphi_{a^2,b}(a)=a^2, \qquad \varphi_{a^2,b}(b)=b,\] and let \[\alpha(a)=x, \qquad \alpha(b)=y.\] Then \(\psi_{x,y}=\alpha\circ\varphi_{a^2,b}\). Since \(a^2\) and \(b\) do not commute, Lemma 1 shows that \(\varphi_{a^2,b}\) is injective. Its image lies in the proper subgroup \(\langle a^2,b\rangle<F(a,b)\), so \(\varphi_{a^2,b}\) is not an automorphism. Since \(x\) and \(y\) do not commute, Lemma 1 also shows that \(\alpha\) is injective. Moreover \(\alpha(F(a,b))\subseteq \Gamma<F(a,b)\), so \(\alpha\) is not an automorphism. Thus \(\psi_{x,y}\) is a non-prime injective endomorphism.

It remains to count. The pairs with \(x=1\) contribute only \(3^{n+o(n)}\). For each nontrivial \(x\in \Gamma\cap B_m\), the centralizer \(C_{F_2}(x)\) is cyclic, so \(|C_{F_2}(x)\cap B_n|=O(n).\) Hence the commuting pairs in \((\Gamma\cap B_m)\times(\Gamma\cap B_n)\) are exponentially negligible, and the number of noncommuting such pairs is \(3^{m+n+o(n)}=3^{3n/2+o(n)}.\) The squaring map is injective in a free group, since free groups have unique roots. Therefore these choices give \(3^{3n/2+o(n)}\) distinct non-prime pairs in \(B_n\times B_n\).

Since \(|B_n\times B_n|=3^{2n+o(n)},\) we obtain \(\delta_{\mathrm{np}}\geq \frac{3/2}{2}=\frac{3}{4}.\) ◻

Proof. Let \(T_n=X_1+\cdots+X_n\), where the \(X_i\) are independent and satisfy \[\mathbb{P}(X_i=1)=\frac{3}{4}, \qquad \mathbb{P}(X_i=-1)=\frac{1}{4}.\] The radial process \(R_n=|w_n|\) moves up with probability \(3/4\) and down with probability \(1/4\) away from the identity, while at the identity it is forced to move up. Hence one may couple \(R_n\) and \(T_n\) so that \(R_n\geq T_n\) for all \(n\). Since \(\lambda\geq 0\), this gives \[\mathbb{E}e^{-\lambda R_n} \leq \mathbb{E}e^{-\lambda T_n} = \left(\frac{3}{4} e^{-\lambda}+\frac{1}{4} e^{\lambda}\right)^n.\] For the second assertion, use \(e^{-\lambda \min\{R_n^{(1)},R_n^{(2)}\}} \leq e^{-\lambda R_n^{(1)}}+e^{-\lambda R_n^{(2)}}.\) ◻

Proof. The simple random walk measure on \(F_2\) is invariant under every automorphism of the labelled Cayley tree fixing the identity. This automorphism group acts transitively on each sphere \(S_r\). Therefore the conditional distribution on \(S_r\) is uniform. ◻

Proof. Put \(R_i=|w_n^{(i)}|,\) for \(i=1,2\). Conditioned on \(R_1=r\) and \(R_2=s\), with \(r,s\geq 1\), the two reduced words \(w_n^{(1)}\) and \(w_n^{(2)}\) are independent and uniformly distributed on \(S_r\) and \(S_s\), respectively, by Lemma 16.

By Corollary 4, there are absolute constants \(A_0,B>0\) such that \[\begin{align} \mathbb{P}\bigl(&\varphi_{w_n^{(1)},w_n^{(2)}}\text{ is not prime} \,\big|\, R_1=r,\;R_2=s\bigr) \leq A_0 (r+s)^B 3^{-\min\{r,s\}/14}. \end{align}\] Since \(r+s\leq 2n\), averaging gives \[\begin{align} &\mathbb{P}\bigl(\varphi_{w_n^{(1)},w_n^{(2)}}\text{ is not prime},\;R_1,R_2\geq 1\bigr) \leq A_1 n^B \mathbb{E}\,3^{-\min\{R_1,R_2\}/14}. \end{align}\] Apply Lemma 15 with \(\lambda=(\log 3)/14\). Then \[\mathbb{E}\left(3^{-\min\{R_1,R_2\}/14}\right) \leq 2\left(\frac{3}{4}\,3^{-1/14}+\frac{1}{4}\,3^{1/14}\right)^n.\] The numerical inequality \(\frac{3}{4}\,3^{-1/14}+\frac{1}{4}\,3^{1/14} < 3^{-1/30}\) therefore implies \[\mathbb{P}\bigl(\varphi_{w_n^{(1)},w_n^{(2)}}\text{ is not prime},\;R_1,R_2\geq 1\bigr) \leq A_2 n^B 3^{-n/30}.\]

It remains to consider the case \(R_1=0\) or \(R_2=0\). Since \(\mathbf{1}_{\{R_i=0\}}\leq 3^{-R_i/14},\) the same exponential moment estimate gives \[\mathbb{P}(R_i=0) \leq \left(\frac{3}{4}\,3^{-1/14}+\frac{1}{4}\,3^{1/14}\right)^n \leq 3^{-n/30}.\] Thus \(\mathbb{P}(R_1=0\text{ or }R_2=0) \leq 2 \cdot 3^{-n/30}.\) Absorbing this term into the polynomial prefactor proves \(\mathbb{P}\bigl(\varphi_{w_n^{(1)},w_n^{(2)}}\text{ is not prime}\bigr) \leq A n^B 3^{-n/30}.\) This proves the theorem. ◻