Polynomial-time complexity for instances of the endomorphism problem in free groups

POLYNOMIAL-TIME COMPLEXITY FOR INSTANCES OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS LAURA CIOBANU Abstract. We say the endomorphism problem is solvable for an element Win a free group Fif it can be decided effectively whether, given Uin F, there is an endomorphism φof Fsending Wto U. This work analyzes an approach due to C. Edmunds and improved by C. Sims. Here we prove that the approach provides an efficient algorithm for solving the endomorphism problem when Wis a twogenerator word. We show that when Wis a two-generator word this algorithm solves the problem in time polynomial in the length of U. This result gives a polynomial-time algorithm for solving, in free groups, two-variable equations in which all the variables occur on one side of the equality and all the constants on the other side. 1. Introduction The endomorphism problem is solvable for an element Win a free group Fif it can be decided effectively whether, given Uin F, there is an endomorphism φof Fsending Wto U. For an arbitrary group Gthe corresponding problem is undecidable. For example, if Gis free nilpotent of countable rank and nilpotence class at least 9, then the problem is undecidable [15]. In free groups the endomorphism problem is equivalent to solving an equation in which all the variables occur on one side of the equality and all the constants on the other side. Makanin showed that the endomorphism problem is always solvable in free groups by providing an algorithm for finding solutions to arbitrary equations [7]. Razborov has then generalized Makanin’s result to systems of equations in free groups [14]. However, Makanin’s use of very difficult group theoretical techniques makes this approach impractical. Additional evidence of the impracticability comes from the fact that the time complexity for Makanin’s algorithm is not primitive recursive [10]. Therefore our goal has been to provide practical alternatives to Makanin’s method. The starting point for this work is an approach due to C. Edmunds [1],[2] that has been improved and made algorithmically formal by C. Sims [3]. While here we consider the approach for an infinitely generated free group 1 2 LAURA CIOBANU F, Edmunds has proved [6] that solving the endomorphism problem for a word Win Fis equivalent to solving the problem in a finitely generated free group with the same number of generators as the word W. It has been shown that the Edmunds approach solves the endomorphism problem when Wbelongs to some restricted classes of words, such as quadratic words, examples of which are products of commutators. However, it has been unclear whether this approach solves the problem for any other type of words. That is, it has been unclear whether one can obtain an answer to this decision problem after performing only a finite number of the steps suggested by the Edmunds-Sims method. Here we prove that the Edmunds-Sims approach provides an algorithm in the case when Wis a two-generator word. For Wa two-generator word, we modify the existing procedures and find that after a finite number of steps we are guaranteed to obtain an answer to our decision problem. Moreover, we show that this now established algorithm runs in time polynomial in the length of U, if Wis a two-generator word. We intend to treat the case when Wis a word on an arbitrary number of generators in a future paper, but in this case the complexity appears to be not polynomial. The main idea of Edmunds’ approach is to define a subset DWfor each Win Fwhich forms a ‘basis’ for the set of endomorphic images of Win the sense of Theorem 1. In order to state the theorem we define the following. Given two cyclically reduced words Vand V′in Fwe say that V′is a proper image of Vif there exists an endomorphism φwith φ(V) = V′that sends every generator xin Vto a non-identity element of Fand no cancellations occur in φ(V). We say V′is a proper cyclic image of Vif some cyclic permutation of V′is a proper image of V. Theorem 1 (Edmunds [2]).A cyclically reduced word Uis an endomorphic image of Wif and only if Uis a proper cyclic image of some W′∈DW. In [3] Sims constructs a set CWsimilar to DWin that it satisfies Theorem 1. The set CWhas the advantage that it is a subset of DWin which most of the duplicate and less relevant words of DWare eliminated. The exact description of the algorithm used to generate the set CWcan be found in Section 4. Checking for proper and cyclic images is a polynomial-time operation. Thus the solvability and efficiency of the endomorphism problem for Wdepends heavily on the tractability of the set CW. For most words Wthe set CWis infinite and has a very complicated structure. In this paper we analyze the set CWfor two-generator words W. The fact that CWis infinite suggests that the program does not terminate. However, we are able to find upper bounds on the number of words in CWthat need to be generated before obtaining the solution. One useful representation of the set CWis as a tree with the nodes representing the words in the set CW ON THE COMPLEXITY OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS 3 and the edges representing the endomorphisms that connect the words, as we describe in Section 5. One can then associate to each node coordinates that represent the number of occurences of each generator in the word. In Sections 7, 8 and 9 we show that when Wis a two-generated word, this tree can be partitioned into finitely many subtrees whose coordinates have a ‘nice’ behavior. We call these subtrees almost perfect trees. We concentrate most of the technical results that show this behavior in Section 8. The proofs rely on the analysis of automorphisms in the free group on two generators. The key ingredient in computing the complexity of the endomorphism problem is the following theorem. Theorem 2. Let Wbe a two-generator word. The number of words in CWthat are generated before finding the last word of length at most nis quadratic in n, i.e. it is smaller than cn2, where cis a constant depending on the length of W. By Theorem 1, in order to determine whether Uis an endomorphic image of a word Wit is sufficient to check whether there exists W′in CWsuch that Uis a proper cyclic image of W′. As the length of a proper image of a word is at least as long as the length of the word, we only need to perform the check for the words W′in CWof length at most the length of U. The above results show that one only needs to check a quadratic number of words when Wis a two-generator word, and since all the other operations used in the implementation of the algorithm require polynomial time and amount of space, the endomorphism problem for two-generator words is polynomial in the length of U. We give more details on the complexity in Section 10. 2. Other results on the endomorphism problem in free groups Efficient solutions to the endomorphism problem in free groups have been known for a while in a few cases. Let Fand Mbe the free group and free monoid, respectively, on the generating set A={a,b,...}(more precisely, A±is the generating set for M). We think of the elements of Mas words in A±, and we think of the elements of Fas equivalence classes of words under free equivalence. We denote by [U] the equivalence class containing the word U. If W=akand Ua cyclically reduced word in F, where kis a positive integer, then [U] is an endomorphic image of [W] if and only if Uis of the form vk, for some word vin M. If W= [a, b] we have the following result by Wicks. Proposition 1 (Wicks [18]).Let Ube a cyclically reduced word and let W= [a, b]. Then [U]is an endomorphic image of [W]if and only if some 4 LAURA CIOBANU cyclic permutation of Uis of the form c d f c−1d−1f−1,for some c, d, f ∈ M. In [17] P. Schupp shows that the endomorphism problem is solvable for a two-generator word W. Computationally, Schupp’s approach is exponential in the length of U. The endomorphism problem in free groups is equivalent to solving a certain type of equation. We have already mentioned the seminal work of Makanin and Razborov which provides algorithms for solving systems of arbitrary equations in the free group. As their algorithm is difficult and impractical, much work has been done to find different approaches to deal with equations in free groups. Particular attention has been devoted to quadratic equations, which are now well understood. Results in this direction have been obtained by Edmunds, Comerford [5], Lyndon [11], Mal’cev [12], Schupp [16], Grigorchuk [8], Kurchanov and many others. 3. Preliminaries Let us fix a countably infinite set X={a,b,c,...}and let X−1be a set of formal inverses for the elements of X, that is, X−1={a−1, b−1, c−1,...}. Let X±=X∪X−1. Elements of Xwill be called generators and elements of X±will be called letters. For x∈Xset (x−1)−1=x. A finite string of letters is called a word. We define the inverse of a word U=x1. . . xnto be U−1=x−1 n...x−1 1. The length of Uwill be denoted by |U|. For a word W, a string of consecutive letters in Wforms a subword of W. A word Wis freely reduced if it contains no subword of the form xx−1 with xin X∪X−1and Wis cyclically reduced if all cyclic permutations of Ware freely reduced. The empty word will be denoted by e. Let Mbe the free monoid with basis X±and let Fbe the free group generated by X. The elements of Fare equivalence classes of words under free equivalence. We denote by [U] the equivalence class containing the word U. (For simplicity, in the Introduction we have denoted the elements of Fby Uinstead of [U], and we have blurred the distinction between words, that is, elements of M, and elements of F.) We will often consider cyclic words in the free group. A cyclic word is the equivalence class of a given cyclically reduced word under all cyclic permutations. Let Ube a cyclic word. A generator xoccurs in Uif xor x−1is in U. Let (x)Ube the number of occurences of xand x−1in U. More generally, for a word Vwe say that Voccurs in Uif there exists a word U′ that is a cyclic permutation of Usuch that Vor V−1is a consecutive string of letters in U′. Let (V)Udenote the number of occurences of the subwords Vand V−1in U. Let {V}Ube the number of occurences of subword Vin the cyclic word U. Thus (V)U={V}U+{V−1}U. ON THE COMPLEXITY OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS 5 We define a syllable of a cyclic word Uwith |U| ≥ 2 to be any subword (or its inverse) of length 2 in U. Every letter in the word is thus a member of exactly two syllables. Let xbe a letter. We define an x-segment to be any maximal subword in xonly. Example. Let Ube aaba−1a−1a−1b. Then its syllables are aa, ab, ba−1, a−1b, ba and its segments are aa,a−1a−1a−1, and b. The word a3is not considered to be a segment of U. We shall often use monoid endomorphisms ψof M. All such endomorphisms will be assumed to be compatible with the inverse map of M. That is, ψ(U−1) = ψ(U)−1for all elements Uof M. We will also use monoid automorphisms of M. These correspond to the permutations on the letters that are compatible with the inverse map. Definition. Given two cyclically reduced words Vand V′we say that V′ is a proper image of Vif: (1) there exists an endomorphism φ:M7−→ Mwith φ(V) = V′and (2) φsends every generator xin Vto a non-identity element. Definition. Given two cyclically reduced words Vand V′in Mwe say that V′is a proper cyclic image of Vif some cyclic permutation of V′is a proper image of V. Example. The word V=acacdac−1a−1da is a proper image of U= aaba−1bvia the endomorphism that sends ato ac and bto da. On the other hand, one can easily check that word U′=aaaba−1bb is not a proper image of U. The proper (cyclic) image relation between words is a transitive relation. The following definition is motivated by the fact that one can often find a simpler equivalent form for the words involved in the endomorphism problem. Definition. A cyclic word Uis redundant if there are distinct letters x and ysuch that y6=x−1, both xand yoccur in U, and all occurrences of x, x−1, y and y−1in Uare in subwords xy or y−1x−1. A word that is not redundant is irredundant. Example. The cyclic word U=cabcac−1b−1ab is redundant, as the only occurences of band care in subwords of the form bc or c−1b−1. If we let U′=abab−1ab, the cyclic word obtained from Uby deleting c, then Uand U′are endomorphic images of each other. Thus deciding whether some word Vis an endomorphic image of Ucan be reduced to deciding whether Vis an endomorphic image of U′. This is why when we 6 LAURA CIOBANU consider the endomorphism problem for a word Wwe can assume Wis irredundant. Let us fix a linear order on X±, say a < a−1< b < b−1< . . . . We will compare words using the corresponding length-plus-lexicographic ordering on words, which is a well-ordering on M. Definition. For a word Wlet Wbe the first word in the orbit of Aut(M) containing Wand let c Wbe the first word in the set of words obtained from Wby applying automorphisms of Mand cyclic permutations. Algorithms for determining whether a word Vis a proper image of a word U, and for computing Wand c Wwill be described in the Appendix. Although so far we have defined the free monoids and groups to be infinitely generated, in reality we work with words on a finite number of generators, which makes it possible to decide the size of the input. Thus in all procedures we make the assumption that the number of generators in the free group is bounded. Under this assumption the computation of Wand c W, as well as the proper (cyclic) image algorithms run in a time polynomial in the length of the words involved. 4. Description of Sims’ Approach For each word Win F, Edmunds [2] defines a subset DWof Fwhich forms, in the sense of Theorem 1, a ‘basis’ for the set of endomorphic images of W. In [3] Sims constructs a set CWsimilar to DWin that it satisfies Proposition 2. Proposition 2 (Sims [3]).Let Wand Ube words with Ucyclically reduced. Then [U]is an endomorphic image of [W]if and only if Uis a proper cyclic image of some element of CW. The set CWhas the advantage that it is a subset of DWin which much of the duplication of DWis eliminated. For example, no element of CWis a proper cyclic image of any other element, while this is allowed in DW. Since deciding whether a word is a proper cyclic image of another word is a relatively straightforward procedure, the solvability of the endomorphism problem for Wdepends on the tractability of the set CW. Before constructing CW, we define certain endomorphisms of Mintroduced by Edmunds that mimic free reduction. Definition. 1) Let Ube a cyclic word and let xand ybe letters such that xy (or y−1x−1) is a subword of U. Let zbe a letter not in U. If x6=ywe ON THE COMPLEXITY OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS 7 define the replacement endomorphism ρx,y,z :M7→ Mwhich acts as: ρx,y,z(x) = xz, ρx,y,z(y) = z−1y, ρx,y,z(t) = t, where tis any letter in Usuch that t6∈ {x, y, x−1, y−1}. If xx (or x−1x−1) is a subword of Uwe define the replacement endomorphism ρx,x,z :M7→ Mwhich acts as: ρx,x,z(x) = zxz−1, ρx,x,z(t) = t, where tis any generator in Usuch that t6∈ {x, x−1}. While each replacement endomorphism depends on a particular word, the choice of zis arbitrary, and in particular \ ρx,y,z(U) is independent of this choice. 2) For any subset Aof generators we define the annihilation endomorphism τA:M7→ Mto be the endomorphism that sends all generators xin Ato the identity and fixes the rest of the generators. The endomorphism τ∅is simply the identity map. We will modify slightly the previous notation for the annihilation endomorphisms. We will denote τ{x1,x2}by τx1,x2, and τ∅by τe, i.e. we enumerate the elements of the set rather than write down the set, unless the set is ∅. We say ρx,y,z is admissible for a cyclic word Uif xy is a subword of U and zdoes not occur in U. We say τxis admissible for word Uif xoccurs in U. A sequence of ρ’s and τ’s such as φn, φn−1,...,φ1is admissible for U if each φiis admissible for φi−1φi−2...φ1(U), where 1 ≤i≤n. We now present the approach suggested by C. Sims in [3]. We define the sets that are the key elements in the approach. 4.1. The set LUand KV.For a cyclic word U, let LUbe the set of irredundant words c Wthat result from all the possible chains of admissible transformations Uρx,y,z −−−−→ cyclic −−−−−−→ reduction VτA −−→ cyclic −−−−−−→ reduction W b −→ c W(1) applied to U, where xis not necessarily different from yand Ais a set of generators that occur in V. The word Vis the cyclic reduction of ρx,y,z(U) and the word Wis the cyclic reduction of τA(V). Notice that since the final operation is b, any choice of generator znot in Uis allowed in ρx,y,z. We can also describe LUin a slightly different way. For a word V, let KVbe the set of irredundant words Mobtainable by choosing a subset A of the generators occuring in V, letting Wbe the cyclic reduction of τA(V), 8 LAURA CIOBANU and setting M=c W. The set LUis then equal to the union of the sets KV, where V=ρx,y,z(U) for any admissible ρx,y,z. Let us assume Wis irredundant. We will give the formal description of the algorithm used to generate the set CWas found in [3], but since the details of the algorithm are rather technical, we first present the main idea: •Let Cbe the empty set; •Place the word Win C, and construct the set LWby applying sequences of replacement and annihilation endomorphisms to Was in (1); •Add each irredundant word Uin LWto the set Cand construct the sets LUstarting with the word Uof minimal length; •Repeat previous step for each word in Cwhile constantly removing words that are proper cyclic images of words already in C. The set CWis the set of elements added to Cand never removed. 4.2. Formalization of CW.Here we describe the algorithm used to obtain the set CWin more detail. The procedure starts by placing KWin a set Q. Let Cbe the set of words Vin Qsuch that Vis not a proper cyclic image of some element of Q− {V}. Assign Qto C. As long as the set Qdoes not become empty, execute commands (1) & (2): (1) Choose an element V∈Qof minimal length and delete it from Q; (2) For all Uin LV, check whether Uis a proper cyclic image of some element of C. If it is, do not add it to C. Otherwise delete from Cand Q all words that are proper cyclic images of Uand add Uto both Cand Q. As before, CWis the set of elements added to Cduring the above procedure and never removed. The procedure may not terminate, but if CWis finite, then the procedure terminates and returns CW. Note that if at any point in the procedure there are two words V1and V2 such that each is a proper cyclic image of the other then there is no danger that they would both be removed from Qsince c V1=c V2.The equality c V1=c V2can be established by the following argument. We have |V1|=|V2|as a consequence of the fact that the proper image of some word Vhas length greater than or equal to the length of the V. This implies that every generator in V1is sent to a generator in V2, and vice versa, and therefore the number of generators that appear in V1is equal to the number of generators that appear in V2. Thus if φis the endomorphism that sends V1to V2, then φproduces a bijective correspondence (compatible with the inverse map) between the generators that appear in V1and the generators that appear in V2. This gives c V1=c V2. ON THE COMPLEXITY OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS 9 It is fairly easy to show that the set CWis a subset of DW. The proof of Proposition 2 is more involved and can be found in [4], Proposition 2.2. Notice, however, that one of the implications in the proposition is easy to establish. If Uis a proper cyclic image of a word Vin CW, then clearly [U] is an endomorphic image of [W], since [V] is obtained from [W] by a series of endomorphisms. 5. Properties of the set CW 5.1. Description of the set CWas a tree. The set Ccan be viewed as a tree with nodes representing the words (from now on ‘word’ and ‘node’ will be used interchangeably while describing the tree) in the set Cand the edges representing the maps that connect the words. The root of the tree is the word Wand the grandchildren of every node Uform the set LU. Let TCbe the tree that corresponds to the set C, as in Figure 1. W U ρx,x,z ρx,y,z ρy,x,z ρy,y,z LW LU τ τ τ τ τ ττ τττ ττe τe τeτe τxτx,y ρ ρ ρ Figure 1. The tree TC 16 LAURA CIOBANU To establish the bijection between the sets Cand C′we need the following lemma, which shows that there exists a bijective correspondence between the sets Land L′. Lemma 5. Let Uand U′be two-generator words in aand bsuch that U=c U′.Then there exists a bijective map hbetween the sets LUand L′ U′ such that V= [ h(V)for all Vin LU. Proof. Let ψbe an automorphism that sends Uto U′. Since we consider two-generator words in aand bthere are eight such possible automorphisms, as far as actions on aand b. One can associate to each replacement endomorphism ρx,y,z applied to Ureplacement endomorphism ρψ(x),ψ(y),z applied to U′, where x, y ∈ {a, a−1, b, b−1}. Then \ ρx,y,z(U) = \ ρψ(x),ψ(y),z(U′) and we let h( \ ρx,y,z(U)) = ρψ(x),ψ(y),z(U′). For example, if ψ(a) = aand ψ(b) = b−1then \ ρa,b,c(U) = \ ρa,b−1,c(U′). There is a similar correspondence between the annihilation endomorphisms applied in LUand L′ U′. We associate to \ τt(ρx,y,z(U)) in LUthe word τψ(t)(ρψ(x),ψ(y),z(U′)) in LU′, where t∈ {a, b}. To conclude the proof of Theorem 3, we show that if a word Uis the proper cyclic image of a word Vthen f(U) is the proper cyclic image of f(V). We use the fact that [ f(U) = Uand [ f(V) = V. The word f(U) is a proper cyclic image of Usince binterchanges the letters in f(U), Uis a proper cyclic image of Vby assumption, and Vis a proper cyclic of f(V) because of the boperation. Thus f(U) is a proper cyclic image of f(V). Therefore the restriction of the map fto the set Cis a bijection between Cand C′. We then want to keep track of all the possible two-generator words in L′ U, and the transformations that generate them. These transformations result from composing a replacement and an annihilation map, followed by a permutation on the generators. The permutation is given by φas defined in (3). We get the following four transformations. (i) The first transformation comes from τa◦ρa,b,c =a→c b→c−1b. We then apply φ=c→a b→b, and we get θa,b,a :a→a b→a−1b (ii) The second transformation comes from τb◦ρa,b,c =a→ac b→c−1. We then apply φ=c→a a→band we get θa,b,b :a→ba b→a−1 (iii) The third transformation comes from τa◦ρa,b−1,c =a→c b→bc. We then apply φ=c→a b→band we get θa,b−1,a :a→a b→ba (iv) The fourth transformation comes from τb◦ρa,b−1,c =a→ac b→c. We then apply φ=c→a a→band we get θa,b−1,b :a→ba b→a ON THE COMPLEXITY OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS17 Notice that applying ρa,a,c and τaor τbwill generate a one-generator word, so we will not include it in the above list of transformations. The following lemmas show that there is duplication when applying replacements to the two-generator words produced by the four above transformations. The next lemma shows that after transformation θa,b,a, only transformations θa,b,a and θa,b,b can be applied without causing duplication. Lemma 6. For a two-generator word Uin aand b, the word ρa,b−1,c(θa,b,a(U)) is a proper cyclic image of ρa,b,c(U). Proof. The transformation ρa−1,b,c−1◦θa,b,a is defined as a→ca b→a−1b. If we let σbe the automorphism that interchanges aand c, then notice that σ◦ρa,b,c is also defined as a→ca b→a−1b. So ρa−1,b,c−1(θa,b,a(U)) = σ(ρa,b,c(U)). By Lemma 4 ρa,b−1,c and ρa−1,b,c±1produce the same words up to monoid automorphisms, so ρa,b−1,c(θa,b,a(U)) is a proper image of ρa,b,c(U) via the automorphism σ. The next lemmas show that after transformations θa,b,b,θa,b−1,a and θa,b−1,b only θa,b−1,a and θa,b−1,b can be applied without causing duplication. Lemma 7. For a two-generator word Uin aand b, the word ρa,b,c(θa,b,b(U)) is a proper cyclic image of ρa,b,c(U). Proof. By Lemma 4, ρa,b,c(U) is the same word, up to monoid automorphisms, as ρb,a,c(U). The transformation ρb,a,c ◦θa,b,b is defined as a→ba b→a−1c. If we let σbe the monoid automorphism that sends ato b,bto cand cto athen we get that σ◦ρb,a,c ◦θa,b,b is defined as a→ac b→c−1b, which is the same as ρa,b,c. Thus ρa,b,c(θa,b,b(U)) is a proper cyclic image of ρa,b,c(U).  Lemma 8. For a two-generator word Uin aand b, the words ρa,b,c(θa,b−1,a(U)) and ρa,b,c(θa,b−1,b(U)) are proper cyclic images of ρa,b−1,c(U). Proof. The transformation ρb,a,c−1◦θa,b−1,a is defined as a→ca b→ba. If we let σbe the monoid automorphism that interchanges aand cthen σ◦ρb,a,c−1◦θa,b−1,a is defined as a→ac b→bc, which is equivalent to ρa,b−1,c(U). Thus ρa,b,c(θa,b−1,a(U)) is a proper cyclic image of ρa,b−1,c(U). The transformation ρb,a,c−1◦θa,b−1,b is defined as a→ba b→ca. If we let ψbe the monoid automorpshism that sends ato c,cto band bto awe get that ψ◦ρb,a,c−1◦θa,b−1,b is defined as a→ac b→bc, which is the same as ρa,b−1,c. Thus ρa,b,c(θa,b−1,b(U)) is a proper cyclic image of ρa,b−1,c(U).  6.3. Tree representation of the two-generator words in C′.Let Wbe a two-generator word in aand b. The set CWcontains three-generator words in {a±1, b±1, c±1}, two-generator words in {a±1, b±1}and one one-generator 18 LAURA CIOBANU word (see section 4.1). As pointed out before, we are mostly interested in the two-generator words in C. In particular, we want to find the lengths of these words. For this purpose we will consider the set C′instead of C, because in the set C′all the transformations determine exactly where each generator goes, while in Cthe boperation varies for each word. We strip the set C′of all the three-generator and one-generator words and we get a tree composed only of two-generator words. Call this tree TW. This tree is not a subtree of TC′, since although the nodes are a subset of the nodes in TC′, the edges corresponding to transformations between words are different. In TWthe edges represent the transformations θa,b,a,θa,b,b, θa,b−1,a and θa,b−1,b (drawn in this order from left to right for the nodes where the transformations are applied) that send two-generator words to two-generator words. w ... θa,b,a θa,b,a θa,b,b θa,b,b θa,b−1,a θa,b−1,a θa,b−1,a θa,b−1,a θa,b−1,b θa,b−1,b θa,b−1,b θa,b−1,b Figure 2. The tree TW The only possible transformations between the words are as in Figure 2. For example, the only transformations θa,b,a appear on the leftmost edges, and the only transformations θa,b,b appear on edges leaving nodes obtained from transformation θa,b,a, since the replacement endomorphism ρa,b,c±1 (and therefore θa,b,a and θa,b,b) is not needed anywhere else by Lemma 8. 7. Overview of TWfor a two-generator word W In this section we describe the main steps involved in finding the complexity of the set CW. Our approach relies on analyzing the structure of the tree TW. In the next section we provide all the technical results needed to show the dynamics of word length in TW. Recall that in order to find the complexity of the algorithm we need to find how many words have been ON THE COMPLEXITY OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS19 generated before finding the last one of a certain length n. We do this in two steps, first by approximating the number of words of length min the tree TW, and second, by finding bounds on the length of the words generated before finding the last word of length n. As far as the first step is concerned, we show that the number of words of length min TWis linear in m. Since all the words in TWare automorphic images of each other, we were guaranteed a quadratic upper bound by a conjecture of Shpilrain and Myasnikov [13] proved by B.Khan [9]. Their statement is the following. Theorem 4 ([13], [9]).Let ube a word in the free group F2on two generators. Assume that the length of uis irreducible by any automorphism of F2, which in particular implies that uis cyclically reduced. Then the number of automorphic images of uthat have the same length as udoes, is bounded by the polynomial 8|u|2−40|u|, for large enough |u|. In order to be able to describe the tree TWin greater detail, we analyze how the transformations θa,b,a,θa,b,b,θa,b−1,a and θa,b−1,b affect the length of the two-generator words. This tree contains only two-generator words. For any node min the tree TWwe will call (a)mand (b)mthe coordinates of m. We say that two nodes mand phave the same coordinates if (a)m= (a)p and (b)m= (b)p. Note that the length of word mis (a)m+ (b)m. We can predict changes in the coordinates based on the maps that connect the parent to the children nodes. Lemma 9. Let mbe a node in the tree TWand let m1and m2be its children. If m1and m2have been obtained from mby applying transformations θa,b,a and θa,b,b, respectively, and (ab)mis the number of times syllable ab appears in m, then we get the following relations: (a)m1= (a)m+ (b)m−2(ab)m,(b)m1= (b)m,(6) (a)m2= (a)m+ (b)m−2(ab)m,(b)m2= (a)m.(7) Proof. Recall that transformation θa,b,a is given by a→a b→a−1b. Thus the a’s in m1come from both a’s and b’s in m, while the b’s in m1can only come from b’s in m. Every occurence of ab in mwill produce a syllable aa−1in θa,b,a(m) which gets cancelled when cyclically reducing θa,b,a(m) to form m1. Transformation θa,b,b is given by a→ba b→a−1. Thus the a’s in m2come from both a’s and b’s in m, while the b’s in m2can only come from a’s in m. Every occurence of ab in mwill produce a syllable aa−1in θa,b,b(m) which gets cancelled when cyclically reducing θa,b,b(m) to form m2. 20 LAURA CIOBANU Lemma 10. Let mbe a node in the tree TWand let m1and m2be its children. If m1and m2have been obtained from mby applying transformations θa,b−1,a and θa,b−1,b, respectively, and (ab−1)mis the number of times syllable ab−1appears in m, then we get (a)m1= (a)m+ (b)m−2(ab−1)m,(b)m1= (b)m,(8) (a)m2= (a)m+ (b)m−2(ab−1)m,(b)m2= (a)m.(9) Proof. Analogous to previous lemma.  The above relations show that in order to determine the length of words in C′we need to find out how the numbers of syllables ab and ab−1change when we apply the four transformations. For example, it will be shown that when θa,b,a is applied repeatedly to some word U, the number of syllables ab in the images of Udecreases until it reaches a minimum. If the minimum is equal to zero, then we don’t apply θa,b,a anymore, so the existence of syllable ab is critical for the transformation θa,b,a applied to U. This is why we call syllable ab the critical syllable of word Ufor transformations θa,b,a and θa,b,b. The syllable ab−1is the critical syllable of some word Vfor transformations θa,b−1,a and θa,b−1,b, if these transformations are applied to V. For a two-generator cyclic word Uin generators a, b and some transformation Tlet minT(xy, U) be the minimum number of times syllable xy occurs in Tn(U), where nis any positive integer and x, y ∈ {a±1, b±1}. That is, minT(xy, U) = min n≥1((xy)Tn(U)) If for a word Vwe have (xy)V= minT(xy, V ), call Vcritical with respect to Tand critical with respect to the syllable xy. Example. Let U=a2bab−1ab−1and let T=θa,b−1,a. Then minT(ab−1, U) = 1 since T(U) = a2bab−1b−1and one can check that (ab−1)Tn(U)= 1 for any n≥1. Notice that once we have iterated a transformation Tenough times for some word Uand have obtained minT(xy, U), where xy is some subword of U, then we can get a recursive relation for the coordinates of all further iterates of U. That is, for nlarge enough, we can accurately describe the growth of |Tn(U)|.It turns out that there exists a class of special subtrees in TWwhich we call ‘almost perfect trees’ and we define below. We show that for all the nodes in such a subtree the number of critical syllables with respect to the corresponding transformations can be completely described. The advantage of knowing the number of critical syllables is that we can ON THE COMPLEXITY OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS21 then accurately predict the coordinates and lengths of the nodes in the subtree. In general, let the binary subtree of TWrooted at some node wbe Tw. Let Lbw(the left branch starting at w) be the infinite path starting at w on which each node is the left child of the previous node. As before, we use the convention that for every node the left child is produced by θx,y,a and the right child is produced by θx,y,b, where x=aand y=bor y=b−1. For example, LbWconsists of the nodes obtained by applying θi a,b,a to W, where i≥0. Definition. (1) We call Twperfect if the number of critical syllables with respect to the corresponding transformations is the same in the entire subtree. That is, for any two nodes uand vin Tw, if xy is the critical syllable with respect to the transformations θx,y,a and θx,y,b applied at u and zt is the critical syllable with respect to the transformations θz,t,a and θz,t,b applied at vthen we have (xy)u= (zt)v, where {xy, zt} ⊆ {ab, ab−1}. (2) We call Twalmost perfect if: (a) for any two nodes uand vin Lbwwith xy as critical syllable we have (xy)u= (xy)v, where xy =ab or xy =ab−1and (b) for any two nodes uand vin Tw\Lbw, (ab−1)u= (ab−1)v. K K L K L L L K L L L L L L L K L Figure 3. An almost perfect tree For example, in the tree in Figure 3 let each node contain the number of critical syllables with respect to the transformations leaving that word. Then the tree in the figure is an almost perfect tree, and a perfect tree would have K=L. The great advantage of an almost perfect tree is that in such a tree no two different nodes have the same coordinates (see Theorem 5). We will 22 LAURA CIOBANU show this by establishing a series of inequalities between the coordinates of nodes in an almost perfect tree. This property leads to the fact that in an almost perfect tree the number of nodes of length nis linear in n. Finally, in Section 9, we show that the tree TCis made up of a finite number of maximal almost perfect trees and a finite number of additional nodes, and we give bounds on these numbers in terms of the length of W(see Theorem 6). This helps us characterize the number of words of a certain length in the set CW, thus leading to the final goal of finding the complexity of the endomorphism problem algorithm for two-generator words. We achieve this goal by analyzing the set C′ W, and then translating the results into statements about the set CW. 8. Technical Lemmas In this section we provide the results that will help determine the structure of the tree TW. We establish these results by analyzing the words and transformations in TW. One can view the four θtransformations as automorphisms in the free groups on two generators. As such, we can easily compute their inverses: θ−1 a,b,a :a→a b→ab,θ−1 a,b,b :a→b−1 b→ab ,θ−1 a,b−1,a :a→a b→ba−1, θ−1 a,b−1,b :a→b b→ab−1. Throughout this section we will be interested in finding out the origin of a subword via a specific automorphism. We will often use the following lemma. Lemma 11. Let Ube a reduced two-generator word of the form U= U1U′U2, where U1,U2and U′are non-empty subwords. Let φ−1be one of the four above automorphisms, that is, φ=θa,b,a,θa,b,a,θa,b−1,a or θa,b−1,b, and let Vbe the reduced word equal to φ−1(U). Then φ−1(U′)appears in Ventirely, except perhaps for the first or last letter in φ−1(U′). Proof. We will prove the stronger result that in φ−1(U) the length of the maximal subwords that get cancelled when forming Vis at most 1. That is, we cannot find words of the type xyy−1x−1inside φ−1(U), where xand yare letters with x6=y−1. Assume that xyy−1x−1does occur. It is easy to see that we cannot have x=y. Since Uis a reduced word, yand y−1must be part of the images of different, non-inverse, letters in U. Therefore, without lack of generality, we can assume that xy =φ−1(b). That implies y−1=φ−1(a) or y−1=φ−1(a−1), which means x−1is the beginning of the image of some letter in the group under φ−1. By a quick inspection, we notice that cannot be the case.  The following two lemmas give characterizations of minT(xy, U), where T=θa,b,a,θa,b−1,a or θa,b−1,b, and xy is the critical syllable for T. ON THE COMPLEXITY OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS23 Lemma 12. For a two-generator cyclic word Uin aand b, minθa,x,a (ax, U) = X n≥1 (x−1anx)U, where x=bor x=b−1.This minimum occurs in θq a,x,a(U), where qis a positive integer such that no subwords of the type (xamx)±1are present in θq a,x,a(U), for any positive integer m. Proof. Recall that transformation θa,x,a is a→a x→a−1x, when x=bor x=b−1. Notice that the number of ax’s in Ucannot increase when we apply θa,x,a. This happens because any syllable ax in θa,x,a(U) can only come from a subword akxin U, where k≥2.We have to analyze the subwords of Uthat contain (ax)±1. Clearly (ax)U=X n≥1 (x−1anx)U+X m≥1 (xamx)U. Since θl a,x,a(x−1anx) = x−1anxand θl a,x,a(xamx) = xam−lx, for all positive integers m,n, and l, we get that if q= max m≥1{(xamx)U6= 0}, then X m≥1 (xamx)θq a,x,a(U)= 0 and (ax)θq a,x,a(U)=X n≥1 (x−1anx)U. A consequence of Lemma 12 is that if a cyclic word Vsatisfies the relation (ax)V= minθa,x,a (ax, V ), then Vis of the form an1xm1. . . ankxmk, where miand niare nonzero integers, and mi−1,ni,micannot all three have the same sign, for i= 1,...,k and m0=mk. The corresponding result for θa,b−1,b is more complicated, since the transformation θa,b−1,b produces more mixing of the two letters aand b. Lemma 13. For a two-generator cyclic word U,minθa,b−1,b (ab−1, U)is reached in θk a,b−1,b(U), where kis such that no subwords of the form (b−1ab−1)±1,(a−1ba−1)±1, or (a−1b2a−1)±1appear in θk a,b−1,b(U). Proof. Recall that transformation θa,b−1,b is a→ba b→a. If we think of the word Uas a sequence of positive and negative subwords (a negative subword consists of a−1’s and b−1’s, while a positive subword consists of a’s and b’s only), then the number of transitions from a positive subword to a negative subword is equal to the number of (ab−1)±1. Thus the number of (ab−1)±1 decreases only when a positive or negative subword disappears entirely. We will determine which positive subwords have the potential to vanish under transformation θa,b−1,b. The same argument is valid for negative subwords. Let pbe a positive subword in U. As noted before, the transition from pto a negative segment is made by a subword of the type (ab−1)±1. When we apply θa,b−1,b, we get |θa,b−1,b(p)|= 2(a)p+ (b)p−1 since there is only 24 LAURA CIOBANU one cancellation due to (ab−1)±1. In particular we have (a)θa,b−1,b(p)= (a)p+ (b)p−1,(b)θa,b−1,b(p)= (a)p.(10) Thus |θa,b−1,b(p)| ≥ |p|. So if (a)p>1 then the length of the positive subword increases. We need to analyze on the cases (a)p= 0 and (a)p= 1. If (a)p= 0 then p=bnfor some positive integer n. We have θa,b−1,b(a−1bna−1) = b−1an−1b−1, so if n > 2, by (10) the transformation θa,b−1,b will increase the length of the a-segment in b−1an−1b−1. Thus only p=band p=b2can vanish under θa,b−1,b. If (a)p=1 and (b)p=mfor some positive integer m, we get (a)θa,b−1,b(p)= (b)pand (b)θa,b−1,b(p)= 1. Thus if n≥1, by (10) we have |θa,b−1,b(p)| ≥ |p| and therefore only p=acan vanish under θa,b−1,b. Now take into account the letters that can preceed and follow a positive subword. We get that the number of ab−1’s in Ucan decrease when applying θa,b−1,b only if (a−1ba−1)±1, (a−1b2a−1)±1or (b−1ab−1)±1are subwords of U. We do not need to analyze minθa,b,b (ab, U) since transformation θa,b,b is never applied twice consecutively, as can be most clearly seen from Figure 2. The following lemmas provide examples of nodes in TWwhich are the roots of almost perfect trees. We start by displaying candidates for perfect trees. Lemma 14. Let wbe a node in TW\LbWsuch that wcontains no (b−1anb−1)±1or (a−1bna−1)±1, where nis any positive integer. Then the tree Twrooted at wis a perfect tree. Proof. We show that if for a node uin TW\LbWwe have (b−1anb−1)u= (a−1bna−1)u= 0 (11) for any positive integer n, then its children have the same property. That is, if u1=θa,b−1,a(u) and u2=θa,b−1,b(u) are u’s children, then (b−1anb−1)ui= (a−1bna−1)ui= 0,where i= 1,2.(12) When obtaining u1, the map θa,b−1,a can produce b−1anb−1only from b−1an+1b−1since θ−1 a,b−1,a(b−1anb−1) = ab−1an+1b−1, and a−1bna−1from a−1(ba−1)nsince θ−1 a,b−1,a(a−1bna−1) = a−1(ba−1)na−1, and these subwords are not allowed in u. When obtaining u2, the map θa,b−1,b can produce b−1anb−1only from a−1bn+1a−1since θ−1 a,b−1,b(b−1anb−1) = ba−1bn+1a−1, and a−1bna−1from b−1(ab−1)nsince θ−1 a,b−1,b(a−1bna−1) = b−1(ab−1)nb−1, and these subwords are not allowed in u. ON THE COMPLEXITY OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS25 By Lemmas 12 and 13 for any node uwith property (11) the number of critical syllables ab−1in ucannot decrease when we apply transformations θa,b−1,a and θa,b−1,b. This fact applied to the node w, together with the iteration of equalities (12), shows that the number of critical syllables throughout the tree Twis constant. That is, Twis a perfect tree.  Lemma 15. Let wθa,b,a be the word on the leftmost branch of the tree TW for which minθa,b,a (ab, W )has been reached. Let w∗=θa,b,a(wθa,b,a ). Then w∗contains no b±mwith m≥2and the tree Tw∗rooted at w∗is almost perfect. Proof. By hypothesis, the words wa,b,a and w∗are both critical with respect to ab, so the number of syllables ab in w∗cannot be decreased by applying θa,b,a. Therefore the number of critical syllables ab in each node in Lbw∗is constant and equal to minθa,b,a (ab, W ). Let the nodes in Lbw∗be wi, i ≥0, where w∗=w0and let the right child of each wibe ui=θa,b,b(wi) (Figure 5). We get (bm)w∗= 0 for m≥2 because θ−1 a,b,a(bm) = (ba)m, so the only way to obtain bmin w∗is from subwords of the type bab in wθa,b,a . This is not possible since wθa,b,a is a critical word with respect to θa,b,a, and by Lemma 12 subword bab is not allowed in wθa,b,a . Claim. For i≥0, we have (b−1anb−1)ui= (a−1bna−1)ui= 0, where n is any positive integer. We have θ−1 a,b,b(b−1anb−1) = b−1a−1b−(n+1)a−1, and θ−1 a,b,b(a−1bma−1) = b(ab)mb, but (bab)wi= 0 since all wiare critical with respect to ab. Also (b±m)wi= 0, where m≥2 by the same argument as for w∗. Thus we have proved the claim. By Lemma 14, our claim implies that the tree Tuirooted at uiis perfect for any i≥0. One can check that θa,b,b(ab−1a−1) = ab−1, and there is no other way of obtaining ab−1when applying θa,b,b. Notice that the structure of any node in Lbw∗is of the form an1bm1...ankbmk, where the miand ni are integers, mi=±1, and mi−1,ni,micannot all three have the same sign. Moreover, all nodes in Lbw∗have the same kand the same mi’s. For any two nodes in Lbw∗the signs of the ni’s in the two nodes are the same. Since the structure of wlis the same as that of wjfor any l, j, we get (ab−1)ul= (ab−1)uj. This also shows that the tree Tw∗is almost perfect.  Lemma 16. Let wbe a node in TW\LbWfor which minθa,b−1,a (ab−1, w) = (ab−1)w. Let w∗=θa,b−1,a(w). Then (bm)w∗= 0 for m≥2and the tree Tw∗rooted at w∗is almost perfect. 32 LAURA CIOBANU number of times syllable ab appears in mthen we get the following relations: |m1|= (a)m1+ (b)m1= (a)m+ 2(b)m−2(ab)m, |m2|= (a)m2+ (b)m2= 2(a)m+ (b)m−2(ab)m, so |m| − |m1|= 2(ab)m−(b)mand |m| − |m2|= 2(ab)m−(a)m,(14) which implies |m| − |m1|<2(ab)mand |m| − |m2|<2(ab)m.(15) When the transformations involved are θa,b−1,a and θa,b−1,b we get |m| − |m1|= 2(ab−1)m−(b)mand |m| − |m2|= 2(ab−1)m−(a)m(16) which implies |m| − |m1|<2(ab−1)mand |m| − |m2|<2(ab−1)m.(17) By Lemma 12 the number of critical syllables when we apply the same transformation can only decrease. That is, for a two-generator word Uif we apply transformation θa,b,a, then the number of ab’s in θa,b,a(U) is smaller than or equal to (ab)U. The same inequality is valid for the number of ab−1’s when we apply θa,b−1,a or θa,b−1,b. Thus there exist bounds, which we make precise in the next paragraph, for both (ab)mand (ab−1)m, where mis any node in the tree TWwith ab or ab−1as the critical syllable. As in Theorem 6 and in the entire section, we use the notation illustrated in Figure 5. Each of the finite number of nodes in LbWbetween Wand w∗, the critical word with respect to θa,b,a, is denoted by W=w0,w1,..., wp=w∗. The right children of the wi’s, where 0 ≤i≤p, are denoted by u0=θa,b,b(w0), u1=θa,b,b(w1), ...,up=θa,b,b(wp). Node W=w0might have two additional children: θa,b−1,a(W) and θa,b−1,b(W). For some node min one of the binary trees Tuirooted at uiwe have (ab−1)m≤(ab−1)ui, where 0 ≤i≤p. For min LbW, the left branch of TW, or min the almost perfect tree rooted at wp,ab is the critical syllable and the upper bound on (ab)mis (ab)W. Let k1= (ab)W,and k2= max 0≤i≤p((ab−1)ui). Then the number of critical syllables for any node min TWis smaller than max(k1, k2) and the inequalities (15) and (17) imply that the length of a parent is at most 2k1or 2k2larger than the length of the child. By Lemma 20, if vqis in Tui, then the length of the path from vqto uiis less than |ui|, which implies that the length of the path between vqand Wis at most |ui|+i, where 0 ≤i≤p. Since the length of the path between vq and vr=Wis at most max i(|ui|+i), we get that |vj|< n +cfor q < j < r, where c= 2 max(k1, k2) max 0≤i≤p(|ui|+i). We conclude this proof by providing bounds for cin terms of |W|. For any two-generator word the number of times syllable ab can appear is at ON THE COMPLEXITY OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS33 θa,b−1,a θa,b−1,a θa,b−1,a θa,b−1,b θa,b−1,b θa,b−1,b θa,b,a θa,b,a θa,b,a θa,b,b θa,b,b θa,b,b w0 w1 w2 w3 u0 u1 u2 Figure 5. Tree TW most half the length of the word. Thus k1= (ab)W≤|W| 2.By Lemma 15 (ab−1)ui≤(ab−1a−1)wi, and clearly (ab−1a−1)wi≤(ab)wi. Since (ab)wi≤ (ab)W, we also get that k2≤|W| 2. Finding bounds on max 0≤i≤p(|ui|+i) is more tedious. Since wiis ui’s parent we can use formula 7 and we get |ui|=|wi|+ (a)wi−2(ab)wi,and the fact that wi−1is wi’s parent provides |wi|=|wi−1|+ (b)wi−1−2(ab)wi.Using the above formula for all 0 ≤i≤p and the fact that (b)w0= (b)w1=··· = (b)wpgives |wi|=|w0|+i(b)w0− 2((ab)w0+···+ (ab)i−1),so |ui|+i=|wi|+ (a)wi−2(ab)wi+i= 2|wi| − (b)wi−2(ab)wi+i = 2(|W|+i(b)W−2((ab)w0+···+ (ab)wi−1)−(b)W−2(ab)wi+i. Now we use the inequalities (ab)wi≥1, (b)W<|W| 2and p < |W|and we get |ui|+i < 2|W|+|W|2,which gives c < W 2(2|W|+|W|2) = |W|2+|W|3 2. 9. Main results Throughout this section we use the tree like structure we have assigned to the set C′ W. Recall that TWis the two-generator word tree corresponding to the set C′ Was described in Section 6.3. We show that the tree TWis made up of a finite number of maximal almost perfect trees and a finite number of additional nodes, and we give bounds on these numbers in terms of the length of W. We start by showing that in an almost perfect tree no 34 LAURA CIOBANU two different nodes can have the same coordinates. This will lead to the fact that the number of nodes of a certain length nin an almost perfect tree is linear in n. Theorem 5. Let Twbe an almost perfect tree of type one or two with (a)w>(b)w>2k, where kis the number of critical syllables in w. Then no two different nodes in Twhave the same coordinates. Proof. Let us note that our assumption that (a)w>(b)w>2kis not restricting the number of almost perfect trees that we can consider. By Lemma 19 the inequalities (13) become strict inequalities in essentially all the cases. Let p′and q′be nodes in Tw, and let pand qbe their respective parents. We will use double induction on the distance from p′to w, and q′to w. Suppose neither p′nor q′is equal to w. If p′and q′have been obtained by applying the same transformations (both by θa,b−1,a or both by θa,b−1,b), then pand qhave the same coordinates by formulas (8) and (9). Hence p=q, which implies that p′=q′. (See Figure 6.) ... q u2 p q’ p’ θa,b,a θa,b,a θa,b,a θa,b,b θa,b,b θa,b,b θa,b−1,a θa,b−1,a θa,b−1,a θa,b−1,a θa,b−1,b θa,b−1,b θa,b−1,b θa,b−1,b w0 w1 w2 w3 u0 u1 Figure 6. Tree Tw If p′and q′have been obtained by applying different transformations, then we get (a)p= (b)qand (a)q= (b)pwhich contradicts the inequalities (a)p>(b)p>2land (a)q>(b)q>2lof Lemma 19. ON THE COMPLEXITY OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS35 Now assume p′=w0. But then q′has different coordinates from p′ since on any path from wto a node in the tree the coordinates are strictly increasing.  Theorem 5 is the first step in characterizing the number of words of a certain length in the set CW. We now give bounds on the number of maximal almost perfect trees in TWand on the number of nodes in TW that do not belong to any almost perfect trees. Proposition 5. Let wbe a node in TW\LbW. Then the tree Twrooted at wconsists of a finite number cwof nodes together with at most cwalmost perfect trees, where cwis a number that depends on the length of w. Proof. We have to show that a tree with edges corresponding to transformations θa,b−1,a and θa,b−1,b only can be written as the union of a finte number of nodes and a finite number of almost perfect trees. Recall from Lemmas 12, 13 and 16 that a tree in which only transformations θa,b−1,a and θa,b−1,b are allowed is almost perfect when the root contains no subwords of the form (b−1anb−1)±1and (a−1bma−1)±1, where n≥1 and m≥2. Notice that any node in an almost perfect tree is itself the root of an almost perfect tree. Now choose a word vin Twwhich is not the root of an almost perfect tree, and therefore does not belong to any almost perfect tree. By Corollary 1 word vmust contain a subword of the form (b−1anb−1)±1or (a−1bma−1)±1, where n≥1 and m≥2. Consider a maximal alternating subword of vthat contains (b−1anb−1)±1or (a−1bma−1)±1, call it s, and trace the preimages sv=s,...,swof sin the words on the path from vto winside Tw. That is, if uis the parent of vin the tree Tw, let sube one of the possible preimages in uof the subword s, and we iterate this notation. Lemma 21 shows that any word vwhich is not the root of an almost perfect tree in Twis at most |w|steps away from w. In fact, if λwis the sum of the length of all maximal alternating subwords in w, then the number of steps is less than λw−|s|. The length of the path between wand vdepends on the kind of transformations that connect the nodes in this path. For example, if s=b−1anb−1and all transformations on the edges in the path between vand ware θa,b−1,a, then the length of the preimage increases by one at each step. This happens because θ−1 a,b−1,a(b−1anb−1) = ab−1an+1b−1. On the other hand, if s=a−1bma−1and all the transformations connecting vto ware θa,b−1,b, then the length of the preimage increases by at least mat each step and thus there are fewer nodes on this path than in the previous case. Let cwbe the number of nodes in Twthat are the roots of maximal almost perfect trees. By maximal almost perfect subtrees we mean trees 36 LAURA CIOBANU that do not belong to any bigger almost perfect trees. Since there are 2n nodes at height or level nin a binary tree, we get that there are at most 2λw<2|w|almost perfect trees. This shows that cw<2|w|,and in fact cw is often much smaller since some paths are shorter than |w|as noticed in the previous paragraph. We can also find a bound on the number of nodes in Twthat do not belong to any almost perfect tree. These are among the nodes of height at most λw−1. Since Twis a binary tree there are at most 2λwsuch nodes, we can use the bound cwfor there nodes as well as for the number of maximal almost perfect trees. This concludes the proof of Proposition 5.  Theorem 6. The tree TWconsists of a finite number of nodes together with at most |W|2|W|maximal almost perfect trees. Proof. In order to exhibit the almost perfect subtrees we need to display the nodes that can be the potential roots for such subtrees. By Lemma 12 we get a critical word with respect to θa,b,a when we apply this transformation to W repeatedly. Call this critical word wθa,b,a . By Lemma 15, the tree rooted at w∗=θa,b,a(wθa,b,a ) is almost perfect. Denote each of the finite number of nodes in LbWbetween Wand w∗by W= w0,w1,...,wp=w∗and denote their right children by u0=θa,b,b(w0), u1=θa,b,b(w1), ...,up=θa,b,b(wp) as in Section 3.5, and illustrated by Figure 5. Node W=w0might have two additional children: θa,b−1,a(W) and θa,b−1,b(W). By Proposition 5, for every 0 ≤i≤pthe tree rooted at uiconsists of a finite number of nodes together with a finite number of almost perfect trees. In particular, the tree TWconsists of the nodes on LbW(lying between W and w∗), the nodes in the Tuithat do not belong to any almost perfect tree, and cu1+cu2+···+cupalmost perfect trees. We now give a bound for cu1+cu2+···+cupin terms of |W|. Recall that pis the number of times we need to apply transformation θa,b,a to W in order to get a critical word with respect to θa,b,a. That is, pis such that θp a,b,a(W) contains no bamb, where m > 0. By Lemma 12 we get that pis equal to the length of the a-segment in the largest subword of type bakbin W, where k > 0. Recall that λuiis the sum of the lengths of all maximal alternating subwords in ui, where 0 ≤i≤p. By Proposition 5 we have cui<2λui. We claim that λui<|W|for each i. We show this by using the fact that θ−1 a,b,b(b−1anb−1) = b−1a−1b−(n+1)a−1, and θ−1 a,b,b(a−1bma−1) = b(ab)mb. Thus λuidepends on the number of words of type a−1b−(n+1)a−1and b(ab)mbin wi. By Lemma 12 such words can only come from subwords of type bakbor bak1bak2...bin W, so λuiis smaller than the total length of ON THE COMPLEXITY OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS37 all subwords of type bakbin W, where k, ki>0. In particular, λui<|W|. This shows that cui<2|W|for each 0 ≤i≤p, so the number of almost perfect trees in TWis less than p2|W|, and since p < |W|we get a bound of |W|2|W|for the number of maximal almost perfect trees. By Proposition 5 the number of nodes in TWnot belonging to any almost perfect tree is also bounded by |W|2|W|, since the number of such nodes in any of the trees Tuiis bounded by cui, for all 0 ≤i≤p. Theorem 7. The number of words in C′ Wof length nis linear in n. Proof. Let αbe the number of maximal almost perfect trees in TWand let βbe the number of nodes not belonging to any almost perfect tree. We first prove that the number of two-generator words in C′of length nis linear in n. A two-generator word uin aand bhas length nif and only if (a)u+(b)u= n, so in order to find all the two-generator words of length nwe need to determine the number of pairs ((a)u,(b)u) for which (a)u+ (b)u=n. For any positive integer nthere are n−1 pairs (x, y) of positive integers such that x+y=n. By Theorem 5 in an almost perfect subtree no two nodes have the same coordinates. The above fact combined with Theorem 5 shows that there can be at most nwords of length nin an infinite almost perfect tree. Thus Theorem 6 shows that there can be at most αn +βnodes of length nin TW. Now let us introduce the three-generator words into the picture. Notice that for every two-generator word uin the set C′the set L′ uwill contain at most two words that are three-generator words, one produced by ρa,a,c and one produced by ρa,b−1,c (see Proposition 3). In fact ρa,a,c will produce mostly redundant words because a node in an almost perfect tree contains no b±m, where m≥2. Let us assume that uis a node in an almost perfect tree with number of critical syllables ab−1equal to l. Recall that this means the number of critical syllables for any node in the almost perfect tree is the same and equal to l. Then the length of ρa,b−1,c(u) is 2((a)u+ (b)u)−2l= 2|u| − 2l. Thus the number of three-generator words of length nin the almost perfect subtree corresponds to the number of two-generator words of length n+2l 2 in that subtree. We have shown that the number of two-generator words of length n+2l 2is less than nfor n > 2lin any almost perfect subtree, since the number of nodes of length kis less than kin any almost perfect subtree. Therefore the number of three-generator words in C′is less than αn +βfor nsufficiently large.  Corollary 3. The number of words in C′ Wof length smaller than or equal to nis quadratic in n. 38 LAURA CIOBANU Proof. Follows immediately from Theorem 7.  Here we present the main theorem, which states that the number of words in C′ Wthat are generated before finding the last word of length nis quadratic in n. This result helps to completely determine the complexity of the endomorphism for two-generator words. Theorem 8. The number of words in C′ Wthat are generated before finding the last word of length nis quadratic in n, i.e. it is smaller than γn2, where γis a constant depending on the length of W. Proof. We start with some word v∈C′ Wof length nand we want to count all the words produced by our algorithm before vhas been produced. Notice that while three-generator words are being produced, they do not generate any further words, so we first count only the two-generator words produced before v. Let Stvbe the finite subtree of TWcontaining all the two-generator words produced before v. Stvis a subtree since at any point in the algorithm a two-generator word is produced by its parent. Recursively, this means that there is a path from any node in Stvto W. It is connected since we consider the set C′and we do not remove proper cyclic images other than the ones already removed in order to get TW, as explained in Section 4.2. We count the number of nodes in Stvby finding upper bounds on their length. Since Stvconsists of portions of almost perfect trees and a finite number of nodes that do not belong to any almost perfect tree, knowing upper bounds on the length of the words will give us the number of nodes in the almost perfect trees. Let us assume that vbelongs to L′ v1, where v1is a two-generator word in C′ W. If vis a three-generator word, then clearly |v1|< n, so we have to count all the two-generator words that have been produced before v1. We can therefore assume that vis a two-generator word of length n, where as before v∈L′ v1. First consider all the terminal nodes in Stv, that is, the nodes of degree one. Let xbe a terminal node. We use the property of the Edmunds-Sims algorithm that given two words in C′, the shorter one is chosen to produce the corresponding Lset first. Let ybe the parent of x, that is, xis in L′ y. We find bounds on |y|and in general, on the length of all non-terminal vertices. Let v=v0, v1, . . . , vr=Wbe the nodes on the path from vto W, where ris a positive integer. If xwas created by the algorithm after viand before vi+1 for some positive integer i, then |y|<|vi|. For every terminal node x′∈Stvthere exist two consecutive nodes vjand vj+1 on the path from vto Wsuch that x′was generated by the algorithm after vjand before vj+1. So if x′∈L′ y′then we get |y′| ≤ |vj|. Thus the length of each non-terminal node is bounded by the length of some node on this path. ON THE COMPLEXITY OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS39 By Lemma 21 all the non-terminal vertices in Stvthat belong to almost perfect subtrees must be words of length smaller than N=n+c. Since by Corollary 3 there are only a quadratic number of words of length smaller than or equal to N, we get that there exists a constant γ′such that there are at most γ′n2non-terminal vertices in Stv. Counting the terminal vertices and the non terminal degree one vertices that have been produced before vadds only at most 2γ′n2to get the total number of two-generator words that have been produced before v. The number of three-generator words produced is at most double the number of two-generator words, and therefore we get a bound of 5γ′n2on the number of words produced before finding the last word of length n. Let γ= 5γ′and we get the statement of the theorem.  Although all our results are about the set C′ W, they are valid for the set CWsince the set CWcontains words of the same length and in the same orbit of Aut(M) as the words in C′ W. In particular, we have the following corollaries. Corollary 4. The number of words in CWof length nis linear in n. Corollary 5. The number of words in CWof length smaller than or equal to nis quadratic in n. Corollary 6. The number of words in CWthat are generated before finding the last word of length nis quadratic in n, i.e. it is smaller than γn2, where γis a constant depending on the length of W. 10. Conclusion Recall that in order to determine whether an element [U] of Fis an endomorphic image of an element [W], it is sufficient to check whether there exists W′in CWsuch that Uis a proper cyclic image of W′. As the length of a proper image of a word is longer than or equal to the length of the word, we only need to perform the check for the words W′in CWof length at most the length of U. The results from the previous section show that one only needs to check a quadratic number of words when Wis a two-generator word, and since all the other operations used in the implementation of the algorithm (see the Appendix) use polynomial time and amount of space, the endomorphism problem for two-generator words is polynomial in the length of U. The following argument produces an estimate for the degree of the polynomial in |U|. A key ingredient of such an estimate is the complexity of the procedure that determines whether a word Vis a proper cyclic image of a word V′. One can find details about this procedure in the Appendix. 40 LAURA CIOBANU Here we need the fact that the time is O(|V|m+1), where mis the number of generators that appear in V′. Let us choose a word W′in CWwith |W′|=n, where nis some integer smaller than or equal to |U|. By the definition of CW, before adding the word W′to the set Cone needs to make sure W′is not a proper cyclic image of any of the words already in CW. However, our results depend only on a constant number of local checks for proper cyclic images in consecutive Lsets (consecutive in the sense that we consider LVand LV′, where V′ is in LV). Each check takes at most O(n4) time, since all words in CW have at most 3 generators. Since we perform a constant number of such checks, we get a complexity of O(n4) for the number of operations needed to decide whether W′should be added to the set CW. By Theorem 7 there are O(n) words of length nin CW. Thus the time it takes to check for all words of length nwhether they should be added to CWis O(n5). All other operations involved in producing the set CWrequire less time than checking for proper images and will therefore not change the degree of the polynomial. The total time for producing the words in CWthat have length smaller than or equal to |U|comes from the summation of the number of operations required for producing the words of length n, where nruns from 0 to |U|. Since we obtained a time of O(n5) for handling all the words of length n, the complexity for handling all words of length smaller than or equal to |U|in the set CWwill be O(|U|6). Notice that in implementing a program that produces the set C′ Wwe do not need to generate the words we proved are (locally) proper images. In this approach we can completely avoid the checks for proper images, and therefore the complexity will be better. Finally, for every word W′in CWor C′ Wwith |W′| ≤ |U|we need to check whether Uis a proper cyclic image of W′. This takes O(|U|4) time for each W′because the number of generators in CWor C′ Wis at most three. As pointed out in the proof of the main result, words of length greater than |U|are generated before producing the last word of length |U|. While the operations involved in producing these words increase the running time, they also do not modify the degree of the polynomial because we do not need to check whether Uis a proper image of any of these words. By Corollary 3 there are about O(|U|2) words in CWor C′ Wof length smaller than or equal to |U|, so checking whether Uis a proper image of any of the words in CWor C′ Wwill take O(|U|6). The running time for producing the relevant portion of the set CWor C′ Wand the running time for checking whether Uis a proper image of words in CWor C′ Wtogether give a complexity of O(|U|6) for checking whether Uis an endomorphic image of W. ON THE COMPLEXITY OF THE ENDOMORPHISM PROBLEM IN FREE GROUPS41 As far as the constants involved in the complexity are concerned, Theorem 6 provides the high bound of |W|2|W|on the number of almost perfect trees in the composition of the set C′ W. This translates into a rather impractical complexity constant for our algorithm. However, we would like to note that in most examples we looked at this constant has turned out to be much lower, of the order of |W|. We can avoid the above exponential constant in our final complexity calculation if we use the result of Khan (Theorem 4), which gives us an O(n2) bound on the number of words of length nin an automorphic orbit of a cyclically reduced word of length n. Since all two-generator words in C′ Ware cyclically reduced automorphic images of W, this gives a O(|U|3) bound on the number of words in CWor C′ Wof length smaller than or equal to |U|, with a numerical constant. Taking this into account, we obtain a final complexity bound of O(|U|7) for our algorithm, with a small constant. Appendix Implementation of the procedures This appendix provides a description of the basic algorithms on words that are being used in the implementation of the Edmunds-Sims approach. A similar account of the procedures can be found in [3], section 4. We also give a rough estimate of the computational complexity of these algorithms. Although the free group and monoid are infinitely generated, the estimate of the running time for all procedures assumes that we handle words on the first million generators in Xonly, which can be represented by fixed precision signed integers. First element in orbit. Let Mbe the free monoid with basis X±and let Fbe the free group generated by X. We fix a linear order on X±, say a1< a−1 1< a2< a−1 2< . . . , and we compare words using the corresponding length-plus-lexicographic ordering, which is a well-ordering on M. Given a word V, we can find the first element Vin the orbit of Aut(M) containing Vwith the following procedure. Let V=v1v2...vr, where all vi are in X±. Our goal is to assign to each vian element aj, where aj∈X±. Let fbe the assignment map. Initially no value of fhas been defined. •For istarting with i= 1 check whether f(vi) has been defined. Let j equal the number of generators in {f(v1),...,f(vi−1)}. •If an assignment has already been made, then store f(vi) in ziand process vi+1. •If not, then assign vito aj+1, that is, let f(vi) = aj+1 and f(v−1 i) = a−1 j+1, and store f(vi) in zi.