Pedro Silva
email: pvsilva@fc.up.pt

Pascal Weil
email: pascal.weil@labri.fr

On finite-index extensions of subgroups of free groups *

Keywords: free groups, subgroups, finite-index extensions MSC: 20E05

We study the lattice of finite-index extensions of a given finitely generated subgroup H of a free group F . This lattice is finite and we give a combinatorial characterization of its greatest element, which is the commensurator of H. This characterization leads to a fast algorithm to compute the commensurator, which is based on a standard algorithm from automata theory. We also give a sub-exponential and super-polynomial upper bound for the number of finite-index extensions of H, and we give a language-theoretic characterization of the lattice of finite-index subgroups of H. Finally, we give a polynomial time algorithm to compute the malnormal closure of H.

This paper is part of the study of the lattice of finitely generated subgroups of a free group of finite rank F . Like most of the recent work on this topic, our paper makes crucial use of the graphical representation of the subgroups of F introduced in the seminal papers of Serre (1977 [8]) and Stallings (1983 [11]). This representation not only makes it easier to form an intuition and to prove properties of subgroups of F , but it also provides a convenient framework to efficiently solve algorithmic problems and compute invariants concerning these subgroups.

The particular object of study in this paper is the lattice of extensions of a given finitely generated subgroup H of F , and more specifically the sublattice of finite-index extensions of H. In this paper, all groups are subgroups of a fixed free group, and the notion of extension must be understood in this context.

It is elementary to verify that H has only finitely many finite-index extensions, and it is known that if K and L are finite-index extensions of H, then the subgroup they generate, namely K, L , has finite index over H as well (Greenberg's theorem, see [START_REF] Stallings | The topology of graphs[END_REF]). Therefore H has a maximum finite-index extension H fi , which is effectively constructible, and the finite-index extensions of H form a full convex sublattice of the lattice of subgroups of F .

This paper contains a detailed discussion of the lattice of finite-index extensions of H. Our main contributions are the following.

We show that the maximum finite-index extension H fi of H is the commensurator of H, and we give a combinatorial (graph-theoretic) characterization of H fi . This characterization leads to efficient algorithms to compute all finiteindex extensions of H, and to compute H fi -the latter in time O(n log n). We also give a rather tight upper bound on the number of finite-index extensions of H: there are at most O( √ n n 1 2 log 2 n ) such extensions, where n is the number of vertices in the graphical representation of H. Note that this upper bound is sub-exponential but super-polynomial.

The consideration of the subgroups of the form H fi , which have no proper finite-index extensions, leads us to the dual study of the lattice of finite-index subgroups of a given subgroup, and we give a combinatorial (language-theoretic) characterization of each such lattice.

Finally, we use our better understanding of the lattice of extensions of a subgroup of F , to give a polynomial time algorithm to compute the malnormal closure of a given subgroup.

As we already indicated, we use in a fundamental way the graphical representation of finitely generated subgroups of F , including a detailed study of the different steps of the computation of this representation (given a set of generators for the subgroup H), whose study was at the heart of an earlier paper by the authors [START_REF] Silva | On an algorithm to decide whether a free group is a free factor of another[END_REF]. It is particularly interesting to see that language-theoretic results and arguments play an important role in this paper: that is, we sometimes consider the graphical representation of a subgroup not just as an edge-labeled graph, but as a finite state automaton. Such considerations are present in almost all the results of this paper, but they become crucial at a rather unexpected juncture: the design of an efficient algorithm to compute the maximal finiteindex extension H fi of H. Indeed, the very low complexity we achieve is due to the possibility of using a standard automata-theoretic algorithm, namely the computation of the minimal automaton of a regular language.

Section 1 summarizes a number of well-known facts about free groups and the representation of their finitely generated subgroups, which will be used freely in the sequel (see [START_REF] Stallings | The topology of graphs[END_REF][START_REF] Weil | Computing closures of finitely generated subgroups of the free group[END_REF][START_REF] Kapovich | Stallings foldings and subgroups of free groups[END_REF][START_REF] Miasnikov | Algebraic extensions in free groups[END_REF][START_REF] Silva | On an algorithm to decide whether a free group is a free factor of another[END_REF] for more details). Section 2 is the heart of the paper: it starts with a technical study of the different steps of the algorithm to compute the graphical representation of a given subgroup, and a description of those steps which preserve finite-index (Section 2.2). These technical results are then used to characterize the maximal finite-index extension H fi (Section 2.3), to relate the computation of H fi and the minimization of certain finite-state automata (Section 2.4), to evaluate the maximal number of finite-index extensions of a given subgroup (Section 2.5), and to describe an invariant of the lattice of finite-index subgroups of a given subgroup (Section 2.6).

Finally, we apply the same ideas in Section 3, to study the malnormal closure of a subgroup, and to show that it can be computed in polynomial time.

Subgroups of free groups and Stallings graphs

Let F be a finitely generated free group and let A = {a 1 , . . . , a r } be a fixed basis of F . Let Ā = {ā 1 , . . . , ār } be a disjoint copy of A and let à = A ∪ Ā: as usual, we extend the map a → ā from the set A to all words by letting ā = a if a ∈ A and ua = āū if a ∈ à and u ∈ à * . As usual again, the elements of F are identified with the reduced words over the alphabet Ã, that is, the words that do not contain a sequence of the form aā (a ∈ Ã). If u ∈ à * is an arbitrary word, we denote by red(u) the corresponding reduced word, that is, the word obtained from u by repeatedly deleting all sequences of the form aā (a ∈ Ã).

A reduced word u ∈ F is cyclically reduced if u cannot be written as u = avā with a ∈ Ã and v ∈ F . Every reduced word u can be factored in a unique way in the form u = xyx, with y cyclically reduced.

If H is a subgroup of F , an extension of H is any subgroup G containing H and we write H ≤ G. If H is finitely generated, we also write H ≤ fg G. If H has finite index in G, we say that G is a finite-index extension of H and we write H ≤ fi G. Finally, we write H ≤ ff G if H is a free factor of G.

The graphical representation of a subgroup

It is well known (since Serre's and Stalling's fundamental work [START_REF] Serre | Arbres, amalgames[END_REF][START_REF] Stallings | The topology of graphs[END_REF]) that every finitely generated subgroup H ≤ fg F admits a unique graphical representation of the form A(H) = (Γ(H), 1), where Γ(H) is a finite directed graph with Alabeled edges and 1 is a designated vertex of Γ(H), subject to the combinatorial conditions below. Here, a graph is a pair (V, E) where V is the set of vertices and E ⊆ V ×A×V is the set of edges; the in-degree (resp. out-degree) of a vertex v ∈ V is the number of edges in E of the form (v ′ , a, v) (resp. (v, a, v ′ )); and the degree of v is the sum of its in-and out-degree. Every pair A(H) satisfies the following:

-the (underlying undirected) graph is connected; -for each a ∈ A, every vertex is the source (resp. the target) of at most one a-labeled edge;

-and every vertex, except possibly 1, has degree at least 2.

Moreover, every pair (Γ, 1) with these properties is said to be admissible, and it is the representation of a finitely generated subgroup of F . In addition, given a finite set of generators of H, the representation of H is effectively computable.

We refer the reader to [START_REF] Stallings | The topology of graphs[END_REF][START_REF] Kapovich | Stallings foldings and subgroups of free groups[END_REF][START_REF] Miasnikov | Algebraic extensions in free groups[END_REF][START_REF] Weil | Computing closures of finitely generated subgroups of the free group[END_REF][START_REF] Silva | On an algorithm to decide whether a free group is a free factor of another[END_REF] for some of the literature on this construction and its many applications, and to Section 2.1 below on the construction of A(H).

We sometimes like to view the A-labeled graph Γ(H) as a transition system over the alphabet Ã: if p, q are vertices of Γ(H), a ∈ A and (p, a, q) is an edge of Γ(H), we say that a labels a path from p to q and ā labels a path from q to p, written p a -→ q and q ā -→ p. If u ∈ Ã * is a word (reduced or not) and u = va (a ∈ Ã), we say that p u -→ q (u labels a path from p to q) if p v -→ p ′ a -→ q for some vertex p ′ . In particular, a reduced word is in H if and only if it labels a loop at vertex 1. Moreover, if we have a path p u -→ q, then we also have a path

p red(u) -→ q.
If H ≤ fg G ≤ fg F , then there is a homomorphism from A(H) into A(G), that is, a map ϕ from the vertex set of Γ(H) to the vertex set of Γ(G) such that ϕ(1) = 1 and

-if p a -→ q in Γ(H) (p, q vertices, a ∈ Ã), then ϕ(p) a -→ ϕ(q) in Γ(G).
It is not difficult to verify that this morphism, if it exists, is unique, and we denote it by ϕ G H . It is well known (see [START_REF] Serre | Arbres, amalgames[END_REF][START_REF] Stallings | The topology of graphs[END_REF][START_REF] Kapovich | Stallings foldings and subgroups of free groups[END_REF][START_REF] Miasnikov | Algebraic extensions in free groups[END_REF]) that if ϕ G H is one-to-one, then H ≤ ff G.

Finally, we say that the homomorphism

ϕ G H is a cover, if it satisfies -if p, q are vertices of Γ(H), a ∈ Ã and ϕ G H (p) a -→ ϕ G H (q) in Γ(G), then p a -→ q ′ in Γ(H) for some vertex q ′ such that ϕ G H (q ′ ) = ϕ G H (q).
In that case, all sets of the form (ϕ G H ) -1 (q) (q a vertex of Γ(G)) have the same cardinality. Covers have the following property, which we will use freely in the sequel. Lemma 1.1 If ϕ: A(H) → A(G) is a cover, p is a vertex of A(H) and u ∈ F labels a loop of A(G) at ϕ(p), then red(u m ) labels a loop of A(H) at p for some integer m > 1.

Covers, cyclically reduced subgroups and finite-index extensions

Let us say that H is cyclically reduced (with respect to the basis A) if every vertex of Γ(H) has degree at least equal to 2. If H is not cyclically reduced, then the designated vertex 1 of Γ(H) has degree 1 and Γ(H) consists of two parts: tail(Γ(H)), which contains the designated vertex 1 and all degree 2 vertices that can be connected to vertex 1 through other degree 2 vertices; and the rest of Γ(H), which is called the core of Γ(H), written cc(Γ(H)). We let t H (1) be the shortest word which labels a path from 1 to a vertex in cc(Γ(H)) and let τ H (1) be the vertex of cc(Γ(H)) thus reached (if H is cyclically reduced, then t H (1) is the empty word and τ H (1) = 1). We write t(1) and τ (1) if the subgroup H is clear from the context. The tail and the core of Γ(H) have intrinsic characterizations. The characterization of the core is well-known (see [START_REF] Stallings | The topology of graphs[END_REF]Exercise 7.3(a)]) and that of the tail is an elementary consequence.

Remark 1.2 Let H ≤ fg F and let p be a vertex of Γ(H). Then p is a vertex of cc(Γ(H)) if and only if some cyclically reduced word u labels a path from p to p.

⊓ ⊔

Proof. By definition, if H is not cyclically reduced, then tail(Γ(H)) consists of a single path from vertex 1 to vertex t(1) (excluding the latter vertex): it is therefore elementary to verify that no non-empty cyclically reduced word labels a loop at a vertex in tail(Γ(H)).

Let now p be a vertex in cc(Γ(H)): then p has degree at least 2, and if it has degree exactly 2, then neither of the two edges adjacent to it leads to a vertex in tail(Γ(H)). Therefore, one can find distinct letters a, a ′ ∈ Ã such that p a -→ q and p a ′ -→ q ′ , with q and q ′ in cc(Γ(H)) as well. Iterating this reasoning, one can show that there exist arbitrarily long paths within cc(Γ(H)), starting from p and labeled by reduced words of the form au and a ′ u ′ . Since Γ(H) is finite, vertices are repeated along these paths, and we consider the earliest such repetition after the initial p. If p itself is the first repeated vertex along the path labeled au, we have a loop p au -→ p such that au is cyclically reduced, and we are done. The situation is similar if p is the first repeated vertex along the path labeled a ′ u ′ . Otherwise, let r and r ′ be the first repeated vertices along the two paths. Then r = p, r ′ = p, and cc(Γ(H)) has paths of the form

p au -→ r, p a ′ u ′ -→ r ′ , r v -→ r and r ′ v ′ -→ r ′ such that auvūā, a ′ u ′ v ′ ū′ ā′ are reduced.
Then the word auvūāa ′ u ′ v ′ ū′ ā′ is cyclically reduced, and it labels a loop at p in Γ(H). This concludes the proof.

⊓ ⊔

Remark 1.3 Let H ≤ fg F . Then t(1)
is the maximum common prefix of the non-trivial elements of H.

⊓ ⊔

Proof. Since every non-trivial element of H is the label of a loop at 1 in Γ(H), it is clear that t(1) is a common prefix to all these words. By Remark 1.2, there exists a cyclically reduced word u labeling a loop at τ (1). Then both t(1)ut(1) and t(1)ūt(1) are reduced words in H, and their maximum common prefix is t(1). This concludes the proof.

⊓ ⊔

We can now state the following extension of the classical characterization of finite-index extensions of cyclically reduced subgroups in terms of covers.

Proposition 1.4 Let H ≤ fg G ≤ fg F . Then t G (1) is a prefix of t(H). More- over, H ≤ fi G if and only if t H (1) = t G (1) and the restriction of ϕ G H is a cover from (cc(Γ(H)), τ H (1)) onto (cc(Γ(G)), τ G (1)). If that is the case, the index of H in G is the common cardinality of the subsets ϕ G H -1 (q) (q a vertex of cc(Γ(G))). Proof. Let ϕ = ϕ G H .
If u is cyclically reduced and labels a loop at a vertex p of cc(Γ(H)), then u labels a loop at ϕ(p) in Γ(G), and that vertex is in the core of Γ(G) by Fact 1.2. It follows that t H (1) labels a path from the origin in Γ(G) to a vertex in cc(Γ(G)). In particular, t G (1) is a prefix of t H [START_REF] Baumslag | Malnormality is decidable in free groups[END_REF].

If t G (1) is a proper prefix of t H (1), we have t H (1) = t G (1)at for some a ∈ Ã and t ∈ F . Since τ G (1) is in cc(Γ(G)), there exist a cyclically reduced word of the form bu, with first letter b = a, which labels a loop at τ G (1) in cc(Γ(G)). Then the words t G (1)(bu) n t G (1) are all reduced, and the cosets Ht G (1)(bu) n t G (1) are all in G. Moreover, these cosets are pairwise disjoint since H contains no reduced word of the form t G (1)(bu [START_REF] Baumslag | Malnormality is decidable in free groups[END_REF]. It follows immediately that ϕ maps core vertices to core vertices and tail vertices to tail vertices.

) d t G (1), d = 0. Thus, if H ≤ fi G, then t H (1) = t G
Let us now assume that Γ(H) and Γ(G) have the same tails, and let us denote by t(1) the word t H (1) = t G [START_REF] Baumslag | Malnormality is decidable in free groups[END_REF]. Then H ′ = t(1)Ht( 1) and G ′ = t(1)Gt( 1) are cyclically reduced, and H ≤ fi G if and only if H ′ ≤ fi G ′ . Thus we may now assume that G and H are cyclically reduced. If ϕ is not a cover, there exists a vertex p of Γ(H) such that Γ(G) has a loop at ϕ(p) labeled by a cyclically reduced word bu (b ∈ Ã) and Γ(H) has no b-labeled edge out of p. Let v label a path from 1 to p in Γ(H) (and hence in Γ(G)). By the same reasoning as above, the cosets Hv(bu) n v are pairwise distinct, and contained in G. Thus, if H ≤ fi G, then ϕ is a cover.

The converse is verified as follows: if ϕ is a cover, let u 1 , . . . , u d be reduced words labeling paths in Γ(H) from 1 to the elements 1 = p 1 , . . . , p d of ϕ -1 (1). If g ∈ G, then g labels a loop at 1 in Γ(G), and since ϕ is a cover, g labels a path in Γ(H) from 1 to p i for some i. Therefore g ∈ Hu i : thus G is the union of finitely many H-cosets.

⊓ ⊔ Corollary 1.5 The extensions, and the finite-index subgroups of a cyclically reduced subgroup are cyclically reduced as well.

2 Finite-index extensions of a subgroup H

It follows from the characterization of finite-index extensions by covers, that if H ≤ fi G, then ϕ G H is onto 1 . Therefore H has only a finite number of finiteindex extensions, and that number can be bounded above by the number of binary relations on Γ(H): if that graph has n vertices, then H has at most 2 n 2 finite-index extensions. We give a better upper bound in Section 2.5.

Moreover, the collection of finite-index extensions of H is effectively computable. In addition, it is elementary to use these graphical representations to show that the join of two finite-index extensions of H is again a finite-index extension (see Stalling's proof of Greenberg's theorem [START_REF] Stallings | The topology of graphs[END_REF]). It follows that if H ≤ fg F , then H admits an effectively computable maximum finite-index extension H fi . The results of Section 2.4 below yield an efficient algorithm to compute the set of finite-index extensions of a given subgroup H, and its maximum finite-index extension H fi .

Remark 2.1 We just observed that every finitely generated subgroup of F has a finite number of finite-index extensions. However, it usually has infinitely many finite-index subgroups. More precisely, every non-trivial subgroup H ≤ fg F admits a finite-index subgroup of index r for each r ≥ 1. Indeed, let A(H) = (Γ(H), 1) and let Q be the vertex set of Γ(H). Define Γ r be the A-labeled graph with vertex set Q × {1, . . . , r} and with the following edge set: for each edge (p, a, q) of Γ(H), there is an edge ((p, i), a, (q, i + 1)) for each 1 ≤ i < r and an edge ((p, r), a, (q, 1)). Then Γ r is an admissible graph, the map π: (p, i) → p defines a cover from Γ r to Γ(H), and if H r is the subgroup represented by (Γ r , (1, 1)), then H r has index r in H. ⊓ ⊔

i-steps and finite-index extensions

Let H ≤ G be finitely generated subgroups of F and let g 1 , . . . , g n be reduced words such that G = H, g 1 , . . . , g n . Let G 0 = H and let

G i = G i-1 , g i (1 ≤ i ≤ n).
We may of course assume that

g i ∈ G i-1 , so G i-1 = G i . Then A(G i ) is obtained from A(G i-1
) by, first, adding sufficiently many new vertices and edges to create a new path from vertex 1 to itself, labeled by g i ; and second, by reducing2 the resulting graph, that is, repeatedly identifying vertices p and p ′ such that q a -→ p and q a -→ p ′ for some vertex q and some letter a ∈ Ã, see for instance [START_REF] Stallings | The topology of graphs[END_REF][START_REF] Weil | Computing closures of finitely generated subgroups of the free group[END_REF][START_REF] Kapovich | Stallings foldings and subgroups of free groups[END_REF][START_REF] Silva | On an algorithm to decide whether a free group is a free factor of another[END_REF]. Depending on the length of prefixes of g i and ḡi that can be read from vertex 1 in Γ(G i-1 ), this procedure amounts to one of the two following moves:

-a reduced expansion, or re-step (we write

A(G i-1 ) -→ (p,w,q) re A(G i ))
, that is, we add a new path labeled by a factor w of g i , from some vertex p to some vertex q of Γ(G i-1 ) in such a way that the resulting graph is admissible (needs no reduction);

-or an i-step (we write

A(G i-1 ) -→ p=q i A(G i ))
, that is, we identify a pair of vertices (p, q) of Γ(G i-1 ), and we reduce the resulting graph.

Remark 2.2 Let us comment on these steps, with reference to Stallings's algorithm [START_REF] Stallings | The topology of graphs[END_REF]. If H = g 1 , . . . , g n , Stallings produces A(H) by reducing (folding) a bouquet of n circles, labeled g 1 , . . . , g n respectively. For our purpose, we decompose this operation in n steps, adding one generator at a time and producing successively the A( h 1 , . . . , h i ) (1 ≤ i ≤ n). Each of these steps is either an re-step or an i-step.

⊓ ⊔

We refer the readers to [10, Section 2] for a detailed analysis of these moves and we record the following observation.

Lemma 2.3 Let G, H ≤ fg F . If H ≤ fi G, then only i-steps are involved in the transformation from Γ(H) to Γ(G). Proof. Let H = G 0 ≤ G 1 ≤ . . . ≤ G n = G be as in the above discussion. Note that H ≤ fi G if and only if G i-1 ≤ fi G i for each 1 ≤ i ≤ n. If A(G i-1 ) -→ re A(G i ), then the homomorphism ϕ Gi Gi-1 is one-to-one, so G i-1 ≤ ff G i and in particular, G i is not a finite-index extension of G i-1 . ⊓ ⊔
2.2 Which i-steps yield finite-index extensions?

If p is a vertex of cc(Γ(H)), we let L p (H) be the language accepted by cc(Γ(H)), seen as a finite state automaton with initial state p and all states final: that is, the set of (possibly non-reduced) words in à * that label a path in cc(Γ(H)) starting at vertex p. Let then L p (H) be the set of reduced words in L p (H)which is also the set of all red(u) (u ∈ L p (H)), and also the set of prefixes of words in the subgroup represented by the pair (cc(Γ(H)), p). Let us first record the following elementary remark.

Remark 2.4 If p u -→ q is a path in cc(Γ(H)), then L q (H) = {red(ūx) | x ∈ L p (H)}. ⊓ ⊔
We now refine the result of Lemma 2.3.

Proposition 2.5 Let H ≤ fg F and let p, q be distinct vertices in Γ(H). Let G be the subgroup of F such that A(H) -→ p=q i A(G). Then H ≤ fi G if and only if p, q are in cc(Γ(H)) and L p (H) = L q (H), if and only if p, q are in cc(Γ(H)) and L p (H) = L q (H).

Proof. Let us first assume that H ≤ fi G and let ϕ = ϕ G H . By Proposition 1.4, ϕ is a bijection from tail(H) onto tail(G) and, since ϕ(p) = ϕ(q), the vertices p and q must both be in cc(Γ(H)).

If p, q ∈ cc(Γ(H)) and L p (H) = L q (H), we consider (without loss of generality) a word u ∈ L p (H) \ L q (H), with minimum length, say u = va with a ∈ Ã. By definition, there exist paths p v -→ p ′ a -→ p ′′ and q v -→ q ′ , but no path q ′ a -→ q ′′ in cc(Γ(H)). Observe that A(H) -→ p ′ =q ′ i A(G). If there is a path q ′ a -→ q ′′ in Γ(H), then we also have A(H) -→ p ′′ =q ′′ i A(G) and since p ′′ ∈ cc(Γ(H)) and q ′′ ∈ tail(Γ(H)), we conclude to a contradiction by Proposition 1.4. We now assume that there is no path q ′ a -→ q ′′ in Γ(H). We claim that there exists w ∈ F such that aw is cyclically reduced and p ′ aw -→ q ′ in cc(Γ(H)). Let indeed p ′′ z -→ q ′ be a path of minimal length in cc(Γ(H)) (there exists one by connectedness). Since p ′′ ∈ cc(Γ(H)), there exists a path p ′′ b -→ r for some b ∈ Ã, b = ā, and as in the proof of Remark 1.2, there exists a reduced word of the form bt labeling a loop at p ′′ . Let w = red(btz): then we have a path p ′′ w -→ q ′ . By minimality of the length of z, t b is not a prefix of z, so w starts with letter b, and hence aw is reduced. In fact, aw is cyclically reduced since there is no path q ′ a -→ q ′′ . Let 1 t -→ q ′ be a path in Γ(H). Then red(taw t) ∈ G, and hence there exists m > 1 such that red(t(aw) m t) ∈ H. Again, since there is no path q ′ a -→ q ′′ , the word ta is reduced. By replacing m by a sufficiently large multiple, we find that ta is a prefix of red(t(aw) m t), and hence that ta labels a path from 1 in Γ(H): this contradicts the absence of a path q ′ a -→ q ′′ . Thus we have proved that, if H ≤ fi G, then p, q ∈ cc(Γ(H)) and L p (H) = L q (H). The latter condition immediately implies that L p (H) = L q (H). We now assume that p, q ∈ cc(Γ(H)) and L p (H) = L q (H), and we show that H ≤ fi G. We first establish a technical fact.

Lemma 2.6 Let r i zi -→ s i+1 (z i ∈ F , 0 ≤ i ≤ k) be paths in cc(Γ(H)), such that r i , s i ∈ {p, q} for each 1 ≤ i ≤ k. Then there exists a path r 0 red(z0•••z k ) -→ t in cc(Γ(H)).
Proof. The proof is by induction on k, and is trivial for k = 0. If k > 0, then there is a path r 1

red(z1•••z k ) -→ t in cc(Γ(H)). Since L p (H) = L q (H), there is also a path s 1 red(z1•••z k )
-→ t ′ for some t ′ ∈ cc(Γ(H)), and therefore a path r 0

red(z0•••z k ) -→ t ′ as required. ⊓ ⊔
We want to show that G has finitely many H-cosets. Let u ∈ G: then u labels a loop at 1 in Γ(G). Let B be the automaton obtained from Γ(H) by identifying vertices p and q, but without performing any reduction. Then Γ(G) is the result of the reduction of B. In particular (say, in view of [START_REF] Silva | On an algorithm to decide whether a free group is a free factor of another[END_REF]Fact 1.4]), u = red(v) for some word v ∈ Ã * labeling a loop at 1 in B. By definition of B, the word v factors as v = v 0 • • • v k , in such a way that Γ(H) has paths of the form 1

v0 -→ s 1 , r i vi -→ s i+1 (1 ≤ i < k) and r k v k
-→ 1, and the vertices r 1 , s 1 , • • • , r k , s k are all equal to p or q. As observed in Section 1, Γ(H) also has paths

1 red(v0) -→ s 1 , r i red(vi) -→ s i+1 (1 ≤ i < k) and r k red(v k ) -→ 1.
In particular, we have red(v 0 ) = t(1)w 0 and red(v k ) = w k t(1) for some w 0 , w k ∈ F , and there are paths 1 t(1)

-→ τ (1) w0 -→ s 1 and r k w k -→ τ (1) t(1)
-→ 1. Note that the paths τ (1)

w0 -→ s 1 , r i red(vi) -→ s i+1 (1 ≤ i < k) and r k w k -→ τ (1)
are set entirely within cc(Γ(H)), since no reduced word-labeled path between vertices in cc(Γ(H)) can visit a vertex in tail(Γ(H)).

By Lemma 2.6, there exists a path τ (1) 1)), so u ∈ H red(t(1) h t(1)). Since h was chosen to be a geodesic in cc(Γ(H)), it can take only finitely many values, and this completes the proof that G has finitely many H-cosets.

red(w0v1•••v k-1 w k ) -→ t for some vertex t in cc(Γ(H)). Let h be a shortest-length word such that t h -→ τ (1) in cc(Γ(H)). Then z = t(1) red(w 0 v 1 • • • v k-1 w k ) h t(1) labels a loop at vertex 1 in Γ(H), so red(z) ∈ H. By construction, we have u = red(t(1)w 0 v 1 • • • v k-1 w k t(

⊓ ⊔

Proof. In view of Corollary 2.9, A(H fi ) is obtained from A(H) by identifying all pairs of vertices p, q of cc(Γ(H)) such that L p (H) = L q (H), and then by reducing the resulting graph B. If p a -→ r and q a -→ s (a ∈ Ã) are paths in cc(Γ(H)) and if L p (H) = L q (H), then L r (H) = L s (H) by Remark 2.4. Thus B is already reduced, which concludes the proof of the first statement.

The fact that Comm(H) is a subgroup and a finite-index extension of H is proved, for instance, in [START_REF] Kapovich | Stallings foldings and subgroups of free groups[END_REF]Prop. 8.9]. Conversely, suppose that H ≤ fi G and g ∈ G. Since conjugation by g is an automorphism of G, we have H g ≤ fi G. Now the intersection of finite-index subgroups, again has finite index, so H ∩H g ≤ fi G and hence H ∩ H g ≤ fi H and H ∩ H g ≤ fi H g . Thus g ∈ Comm F (H), which concludes the proof.

⊓ ⊔

Computing finite-index extensions

Recall the notion of minimization of a deterministic finite-state automaton (see [START_REF] Kozen | Automata and Computability[END_REF] for instance). Let B = (Q, i, E, T ) be such an automaton, over the alphabet B, with Q the finite set of states, i ∈ Q the initial state, E ⊆ Q × B × Q the set of transitions and T ⊆ Q the set of accepting states, and let L be the language accepted by B, that is, the set of words in B * that label a path from p to a state in T . Then the minimal automaton of L is obtained by identifying the pairs of states (p, q) such that the automata (Q, p, E, T ) and (Q, q, E, T ) accept the same language.

In our situation, the alphabet is à and L p (H) is the language accepted by the automaton B p , whose states and transitions are given by cc(Γ(H)), with initial state p and all states final. Therefore Corollary 2.9 and Theorem 2.10 show that the identification of two vertices p, q ∈ cc(Γ(H)) yields a finite-index extension if and only if p and q are identified when minimizing B τ (1) . Moreover, cc(Γ(H fi )) is given by the states and transitions of the minimal automaton of L τ (1) (H).

The classical Hopcroft algorithm (see [START_REF] Kozen | Automata and Computability[END_REF]) minimizes an n-state automaton in time O(n log n), so we have the following result. Proposition 2.11 Let H ≤ fg F , and let n be the number of vertices of Γ(H).

• cc(Γ(H fi )) is obtained by minimizing the automaton given by the vertices and edges of cc(Γ(H)), with all states final (the initial state does not matter in that situation).

• One can compute Γ(H fi ) in time O(n log n).

• One can decide in time O(n log n) whether identifying a given set of pairs of vertices of Γ(H) will produce a finite-index extension of H.

Remark 2.12 It may be that for the particular automata at hand (over a symmetrized alphabet, with all states final), the complexity of Hopcroft's algorithm might be better than O(n log n), even linear. It has also been observed that in many instances, Myhill's automata minimization algorithm exhibits a better performance than Hopcroft's, in spite of a O(n 2 ) worst-case complexity. Brzozowski's algorithm [START_REF] Brzozowski | Canonical regular expressions and minimal state graphs for definite events[END_REF] also performs remarkably well in practice [START_REF] Champarnaud | Canonical derivatives, partial derivatives and finite automaton constructions[END_REF]. ⊓ ⊔

Counting finite-index extensions

Recall that, if Γ is an A-labeled graph, the product Γ × A Γ (also called the fiber product, or the pull-back, of two copies of Γ) is the A-labeled graph whose vertex set is the set of pairs (p, q) of vertices of Γ and whose edges are the triples ((p, q), a, (p ′ , q ′ )) such that (p, a, q) and (p ′ , a, q ′ ) are edges of Γ. This graph is not admissible, nor even connected in general (the vertices of the form (p, p) form a connected component that is isomorphic to Γ). Note that there is a u-labeled path in Γ × A Γ from (p, q) to (p ′ , q ′ ), if and only if Γ has paths p u -→ p ′ and q u -→ q ′ . If p, q are vertices of cc(Γ(H)), we let p ∼ q if and only if L p (H) = L q (H).

Proposition 2.13 Let H ≤ fg F . • The relation ∼ is a union of connected components of cc(Γ(H))× A cc(Γ(H)).
• Let p, q be vertices of cc(Γ(H)). Then p ∼ q if and only if the first and the second component projections, from the connected component of (p, q) in cc(Γ(H)) × A cc(Γ(H)) to cc(Γ(H)) are both covers.

Proof. The first statement follows directly from Remark 2.4, which shows that if p ∼ q and there is a path (p, q) u -→(p ′ , q ′ ), then p ′ ∼ q ′ . Let us now assume that p ∼ q and let us show that the first component projection is a cover from the connected component of (p, q) onto cc(Γ(H)). Let (r, s) be a vertex in that connected component: then there exists u ∈ F such that p u -→ r and q u -→ s. Let r a -→ r ′ (a ∈ Ã) be an edge in Γ(H). Then ua ∈ L p (H), so ua ∈ L q (H), and hence (since Γ(H) × A Γ(H) is deterministic), there exists an a-labeled path s a -→ s ′ . Therefore there exists an a-labeled path (r, s) a -→(r ′ , s ′ ). Thus the first component projection is a cover. The proof concerning the second component projection is identical.

Conversely, suppose that the first and the second component projections, from the connected component of (p, q) in cc(Γ(H)) × A cc(Γ(H)) to cc(Γ(H)) are covers, and let u ∈ L p (H). Then cc(Γ(H)) has a path p u -→ r. It is an elementary property of covers that this path can be lifted to a path in cc(Γ(H)) × A cc(Γ(H)), of the form (p, q) u -→(r, s). The second component projection of that path yields a path q u -→ s in cc(Γ(H)), and hence u ∈ L q (H). ⊓ ⊔ Let f (n) be the maximal number of finite-index extensions of a subgroup H ≤ fg F such that Γ(H) has at most n vertices. By Proposition 2.13, every pair (p, q) such that p ∼ q is in the connected component of a pair of the form (1, r) for some r > 1. Moreover, this connected component has elements of the form (i, j) for all 1 ≤ i ≤ n, so the graph resulting from the identification of 1 and r (or from p and q) has at most n/2 vertices. Thus f (1) = 1 and f (n) ≤ n f (⌊n/2⌋) for all n ≥ 2. It follows that f (n) ≤ n

s d,k = m d,k m d,d = ℓ d,k ℓ d,d = (2 k -1)(2 k -2)(2 k -4) • • • (2 k -2 d-1 ) (2 d -1)(2 d -2)(2 d -4) • • • (2 d -2 d-1
) .

Finally, the number of subspaces of Z k 2 is equal to k d=0 s d,k , with s 0,k = 1. We observe that for each 0

≤ i < d < k, 2 k -2 i 2 d -2 i > 2 k-d , so that s d,k > 2 (k-d)d . By considering d = ⌊ k 2 ⌋, we find that s d,k > 2 k 2 /4
. Finally, we note that Γ(H) is the Cayley graph of Z k 2 with respect to the basis e 1 , . . . , e d (a graph known as the dimension k hypercube), so that Γ(H) has n = 2 k vertices. As a result, H has more than n 1 4 log 2 n finite-index extensions. ⊓ ⊔

The lattice of finite-index subgroups of G

Let us call fi-maximal a subgroup G ≤ fg F which has no proper finite-index extension, that is (in view of Theorem 2.10), such that G = Comm F (G). If G is fi-maximal, let FIS(G) be the set of all finite-index subgroups of G, that is, the set of subgroups H ≤ fg F such that H fi = G. Note that distinct fi-maximal subgroups yield disjoint lattices of finite-index subgroups.

Remark 2.16 Let G ≤ fg F be non-trivial and fi-maximal. Then FIS(G) forms a convex sublattice of the lattice of subgroups of F , with greatest element G. This sublattice is always infinite (see Remark 2.1) and without a least element. ⊓ ⊔ Lemma 2.8 provides us with an invariant for every sublattice of the form FIS(G) (with G fi-maximal).

Proposition 2.17 Let H, K ≤ fg F . Then H fi = K fi if and only if t H (1) = t K (1) and L τ (1) (H) = L τ (1) (K), if and only if t H (1) = t K (1) and L τ (1) (H) = L τ (1) (K).
(4.5) if t is not the empty word, then t = t ′ a for a letter a ∈ Ã such that ā ∈ L.

Proof. Conditions (1) and ( 2) are equivalent by Proposition 2.17. Proposition 2.11 shows that (1) implies (3'), which in turn implies (3). Let us now assume that (3) holds and let Γ be the A-labeled graph induced by the states and transitions of the minimal automaton of L. The extra condition given shows that every vertex of Γ is visited by a loop labeled by a cyclically reduced word. It follows that, if G is the subgroup whose graphical representation is A(G) = (Γ, q 0 ), with q 0 the initial state, then G is cyclically reduced, L = L q0 (G). The condition on the word t shows that Condition (1) holds with H = G t . Condition (3) easily implies Condition (4). Let us now assume that Condition (4) holds. By [9, Theorem 4.1], Properties (4.2) and (4.3) show that L is accepted by an i-automaton. Property (4.1) shows that all states of that automaton are final, and Property (4.4) shows that, for each state p, there exist transitions (p, a, q) and (p, b, r) for at least two distinct letters a, b ∈ Ã. Thus Condition (4) implies Condition (3), which concludes the proof.

⊓ ⊔ 3 Malnormal closure A subgroup H of F is malnormal if H g ∩ H = 1 for each g ∈ H.
Malnormality was proved decidable in [START_REF] Baumslag | Malnormality is decidable in free groups[END_REF], and a simple decision algorithm was given in [START_REF] Kapovich | Stallings foldings and subgroups of free groups[END_REF], based on the following characterization [START_REF] Kapovich | Stallings foldings and subgroups of free groups[END_REF][START_REF] Jitsukawa | Malnormal subgroups of free groups[END_REF].

= q ∈ cc(Γ(H)), L p (H) ∩ L q (H) is finite.
This yields directly an O(n 2 log n) decision algorithm, where n is the number of vertices of cc(Γ(H)). It also yields the following corollary.

Corollary 3.2 Let H ≤ fg F . If H is malnormal, then H is fi-maximal, that is, H has no proper finite-index extension.
Proof. By Corollary 2.9, if H is not fi-maximal, then there exist vertices p = q in cc(Γ(H)) such that L p (H) = L q (H), and hence such that L p (H) ∩ L q (H) = L p (H) is infinite. In particular, H is not malnormal.

⊓ ⊔

It is shown in [START_REF] Miasnikov | Algebraic extensions in free groups[END_REF]Prop. 4.5] that for every finitely generated subgroup H ≤ fg F , there exists a least malnormal extension H mal , called the malnormal closure of H, that H mal is finitely generated and effectively computable, and that the rank of H mal is less than or equal to the rank of H [7, Corol. 4.14]. In fact, [START_REF] Miasnikov | Algebraic extensions in free groups[END_REF] shows that Γ(H mal ) is obtained from Γ(H) by a series of i-steps. The algorithm computing H mal then consists in computing all the quotients of Γ(H) and verifying, for each of them, whether it represents a malnormal subgroup. We now give a much better, polynomial-time algorithm. Theorem 3.3 Let H ≤ fg F n . The malnormal closure of H is computed by repeatedly applying the following construction: in Γ(H), identify all pairs (p, q) of distinct vertices in cc(Γ(H)), such that L p (H) ∩ L q (H) is infinite and reduce the resulting graph.

Proof. Let H 0 = H and let H i+1 be the subgroup of F such that Γ(H i+1 ) is obtained from Γ(H i ) by, first identifying all pairs p, q of vertices of cc(Γ(H i )) such that L p (H i ) ∩ L q (H i ) is infinite, and then reducing the resulting graph. Since Γ(H i+1 ) has less vertices than Γ(H i ), this defines a finite sequence of subgroups

H = H 0 < H 1 < . . . < H k ,
where k ≥ 0 and H k is malnormal. We want to show that H k is the least malnormal extension of H.

Let K be any malnormal subgroup of F such that H ≤ K. By Takahasi's theorem (see for instance [START_REF] Miasnikov | Algebraic extensions in free groups[END_REF]), there exists a subgroup G such that H ≤ G ≤ K such that G is obtained from H by a sequence of i-steps, and K is obtained from G by a sequence of re-steps (this fact can also be deduced from [10, Prop.

2.6]).

Let p, q ∈ cc(Γ(H)) such that L p (H) ∩ L q (H) is infinite. It is elementary to

verify that L p (H) ⊆ L ϕ G H (p) (G) ⊆ L ϕ K G (ϕ G H (p)) (K). In particular, ϕ K G (ϕ G H (p)) ∩ ϕ K G (ϕ G H (q)
) is infinite. Since K is malnormal, it follows from Proposition 3.1 that ϕ K G (ϕ G H (p)) = ϕ K G (ϕ G H (q)). But ϕ K G is one-to-one by definition, so we have ϕ G H (p) = ϕ G H (q). It follows that G is obtained from H 1 by a sequence of i-steps, and in particular, H 1 ≤ G ≤ K. Iterating this reasoning, we find that H k ≤ K, which concludes the proof. This part of the algorithm is iterated k times, to compute Γ(H k ) = Γ(H mal ), and we have k < n since the number of vertices of the Γ(H i ) forms a properly decreasing sequence. This concludes the proof.

⊓ ⊔

⊓ ⊔ Corollary 3 . 4

 34 Let H ≤ F . If Γ(H) has n vertices, then one can compute Γ(H mal ) in time O(n 3 log n).Proof. According to the algorithm given in Proposition 3.3, we first need to compute the connected components of cc(Γ(H)) × A cc(Γ(H)) -done in time O(n 2 log n) -, identifying which are trees and which are not -done in time O(n 2 ) -, identifying the vertices of cc(Γ(H)) involved in a non-diagonal connected component and reducing the resulting graph to obtain Γ(H 1 ) -which is done in time O(n log n). Thus Γ(H 1 ) is computed from Γ(H 0 ) in time O(n 2 log n).

  Proposition 2.14 Let H ≤ fg F . If cc(Γ(H)) has n vertices, then H has at most n Example 2.15 By means of lower bound, we consider the following example. Let e 1 , . . . , e k be the canonical basis of the vector space Z k 2 , let ϕ be the morphism from the free group F over A = {a 1 , . . . , a k } into the additive group Z k 2 , mapping a i to e i , and let H = ker ϕ. Then H is normal and finite-index, so all its extensions have finite index and they are in bijection with the set of quotients of Z k 2 , hence with the set of subgroups of Z k 2 , or equivalently with the set of subspaces of Z k 2 . Let ℓ d,k be the number of linearly independent d-tuples inZ k 2 (d ≥ 1). Then ℓ 1,k = 2 k -1. If d ≥ 2, a d-tuple (x 1 , . . . , x d ) is linearly independent if and only if (x 1 , . . . , x d-1) is linearly independent and x d does not belong to the subspace generated by x 1 , . . . , x d-1 , so that ℓd,k = ℓ d-1,k (2 k -2 d-1). Now the set of cardinality d linearly independent subsets has m d,k = ℓ d,k /d! elements, and the number of dimension d subspaces of Z k 2 is

	1 2 (1+log 2 n) finite-index extensions.
	1 2 (1+log 2 n) .

The converse is not true, see[START_REF] Miasnikov | Algebraic extensions in free groups[END_REF] for a detailed study of the extensions H ≤ fg G such that ϕ G H is onto.

This reduction operation is the iteration of Stallings's folding operation[START_REF] Stallings | The topology of graphs[END_REF]; our terminology emphasizes the fact that this is a generalization of the reduction of a word (the iterated process of deleting factors of the form aā, a ∈ Ã).

Acknowledgements

The authors thank A. Martino and E. Ventura for their help in the computation in Example 2.15. They also are indebted to the anonymous referee whose careful reading helped improve this paper.

* The first author acknowledges support from Project ASA (PTDC/MAT/65481/2006) and C.M.U.P., financed by F.C.T. (Portugal) through the programmes POCTI and POSI, with national and European Community structural funds. Both authors acknowledge support from ESF project AutoMathA.

We note the following consequence of this proof.

Corollary 2.7 Let H ≤ fg F and let p, q ∈ cc(Γ(H)). Then L p (H) = L q (H) if and only if L p (H) = L q (H).

The lattice of finite-index extensions of H

We further refine Proposition 2.5 as follows: we consider an extension H ≤ fi G and a pair (r, s) of vertices of Γ(H), whose identification yields a finiteindex extension of H. Then we show that identifying the vertices of Γ(G) corresponding to r and s, also yields a finite-index extension of G.

Conversely, suppose that ϕ(p)

⊓ ⊔

Together with Proposition 2.5, Lemma 2.8 immediately implies the following statements.

Corollary 2.9 Let H ≤ fg F .

H ≤ fi G if and only if A(G) is obtained from A(H

) by identifying some pairs of vertices (p, q) in cc(Γ(H)) such that L p (H) = L q (H), and then reducing the resulting graph.

The identification of all pairs of vertices (p, q) such that L p (H) = L q (H) yields the minimum quotient of A(H) and hence the maximum finite-index extension H fi of H. In addition, we find that H fi is exactly the commensurator of H (the set Comm F (H) of all elements g ∈ F such that H ∩ H g has finite index in both H and H g ), a fact that can also be deduced from [START_REF] Kapovich | Stallings foldings and subgroups of free groups[END_REF]Lemma 8.7].

Theorem 2.10 Let H ≤ fg F and let H fi be its maximum finite-index extension.

1. A(H fi ) is obtained from A(H) by identifying all pairs of vertices p, q of cc(Γ(H)) such that L p (H) = L q (H). No reduction is necessary.

2.

Proof. If H fi = K fi , then H, K ≤ fi H fi , and Proposition 1.4 and Lemma 2.8 show directly that t

We now prove the converse. More precisely, we show that if H and K are fi-maximal, t H (1) = t K (1) and L τ (1) (H) = L τ (1) (K), then H = K. First we note that A(H tH(1) ) = (cc(Γ(H)), τ (1)) and in particular, H tH(1) is cyclically reduced and fi-maximal. Thus, it suffices to prove the expected result (namely, that H = K) under the hypothesis that H and K are cyclically reduced.

By Remark 2.4, the set of all L p (H) (p ∈ Γ(H)) coincides with the set

It also follows from the same fact that, again if H is fi-maximal, there is an edge (p, a, q) in Γ(H) if and only if L q (H) = {red(āx) | x ∈ L p (H)}. Thus, the cyclically reduced fi-maximal subgroup H is entirely determined by the set L 1 (H). This concludes the proof.

⊓ ⊔

The pairs (t, L) that are equal to (t(1), L τ (1) (G)) for some subgroup G ≤ fg F are characterized as follows. Recall that an i-automaton [START_REF] Silva | On free inverse monoid languages[END_REF] is a deterministic automaton (Q, i, E, T ) over the alphabet à such that, (p, a, q) ∈ E if and only if (q, ā, p) ∈ E for all vertices p, q and a ∈ A. The automata B p discussed in Section 2.4 are i-automata. Proposition 2.18 Let t ∈ F and let L ⊆ à * be a rational language. The following conditions are equivalent.

(1) There exists a subgroup H ≤ fg F such that t = t(1) and L = L τ (1) (H).

(2) There exists a fi-maximal subgroup H ≤ fg F such that t = t(1) and L = L τ (1) (H).

(3) L is accepted by an i-automaton with all states accepting and such that, for each state p, there exist transitions (p, a, q) and (p, b, r) for at least two distinct letters a, b ∈ Ã. In addition, if t is not the empty word, then t = t ′ a for a letter a ∈ Ã such that ā ∈ L.

(3') The minimal automaton of L is an i-automaton with all states accepting and such that, for each state p, there exist transitions (p, a, q) and (p, b, r) for at least two distinct letters a, b ∈ Ã. In addition, if t is not the empty word, then t = t ′ a for a letter a ∈ Ã such that ā ∈ L.

(4) t and L satisfy the following conditions: