domain: math info

text:
Valérie Berthé

Vincent Delecroix

Francesco Dolce

Dominique Perrin

Christophe Reutenauer

Giuseppina Rindone

Return words of linear involutions and fundamental groups

come

Introduction

A linear involution is an injective piecewise isometry defined on a pair of intervals. This generalization of the notion of interval exchange allows one to work with nonorientable foliations (see e.g. [START_REF] Danthony | Involutions linéaires et feuilletages mesurés[END_REF] and [START_REF] Boissy | Dynamics and geometry of the Rauzy-Veech induction for quadratic differentials[END_REF]Convention 2.2]). Linear involutions were introduced by Danthony and Nogueira in [START_REF] Danthony | Measured foliations on nonorientable surfaces[END_REF] and [START_REF] Danthony | Involutions linéaires et feuilletages mesurés[END_REF], generalizing interval exchanges with flip(s) [START_REF] Nogueira | Almost all interval exchange transformations with flips are nonergodic[END_REF][START_REF] Nogueira | Orbit structure of interval exchange transformations with flip[END_REF] (these are interval exchange transformations which reverse orientation in at least one interval). They extended to these transformations the notion of Rauzy induction (introduced in [START_REF] Rauzy | Échanges d'intervalles et transformations induites[END_REF]). The study of linear involutions was later developed by Boissy and Lanneau in [START_REF] Boissy | Dynamics and geometry of the Rauzy-Veech induction for quadratic differentials[END_REF] in connection with the classification of connected components of exceptional strata of meromorphic quadratic differentials. Note that there exist various generalizations of interval exchanges: let us quote, e.g., pseudogroups of isometries [START_REF] Gaboriau | Pseudogroups of isometries of R: reconstruction of free actions on R-trees[END_REF] and interval identification systems [START_REF] Skripchenko | Symmetric interval identification systems of order three[END_REF].

In the present paper, we study natural codings of linear involutions in the spirit of our previous papers on Sturmian sets [START_REF] Berstel | Bifix codes and Sturmian words[END_REF] and their generalizations as tree sets [START_REF] Berthé | Bifix codes and interval exchanges[END_REF][START_REF] Berthé | The finite index basis property[END_REF][START_REF] Berthé | Maximal bifix decoding[END_REF][START_REF] Berthé | Acyclic, connected and tree sets[END_REF]. A tree set is a factorial set of words that all satisfy a combinatorial condition expressed in terms of the possible extensions of these words within the tree set: the condition is that the extension graph of each word is a tree, with this graph describing the possible extensions of a word in 1 the language on the left and on the right. Tree sets encompass the languages of classical shifts of zero entropy like the ones generated by Sturmian words, Arnoux-Rauzy words, or else natural codings of interval exchanges. Note however that all these shifts display various behaviors in terms of spectral properties (they can be weakly mixing, or they can have pure discrete spectrum).

Tree sets have particularly interesting properties relating free groups and symbolic dynamics. In particular tree sets allow one to exhibit bases of the free group, or of subgroups of the free group. Indeed, in a uniformly recurrent tree set, the sets of return words to a given word are bases of the free group on the alphabet [START_REF] Berthé | Acyclic, connected and tree sets[END_REF]. Moreover, maximal bifix codes that are included in uniformly recurrent tree sets provide bases of subgroups of finite index of the free group [START_REF] Berthé | The finite index basis property[END_REF].

These properties thus hold for tree sets associated with regular interval exchange sets. Observe that the fact that return words are bases of the free group can either be deduced combinatorially from the property that interval exchanges yield tree sets [START_REF] Berthé | Bifix codes and interval exchanges[END_REF] or else, as we will show here, from the geometric interpretation of interval exchanges as Poincaré sections of linear flows on translation surfaces: return words provide bases of the fundamental group of the associated surface.

The natural coding of a linear involution is the set of factors of the infinite words that encode the sequences of subintervals met by the orbits of the transformation. They are defined on an alphabet A whose letters and their inverses index the intervals exchanged by the involution. A natural coding is thus a subset of the free group F A on the alphabet A. One of our motivations for working with natural involutions is that they provide a first step for extending the combinatorial study of tree sets, done in the framework of monoids, to free groups. A further motivation relies in providing a classification of free group automorphisms associated with tree sets according to the botany developed in [START_REF] Coulbois | Botany of irreducible automorphisms of free groups[END_REF] for fully irreducible outer automorphisms of the free group.

We extend to natural codings of linear involutions most of the properties proved for uniformly recurrent tree sets, and thus, for natural codings of interval exchanges. The extension is not completely immediate. If linear involutions have a geometric interpretation as Poincaré maps of measured foliations, one has to modify the definition of return words in order to make it consistent with the notion of Poincaré map of a foliation. We thus consider return words to the set {w, w -1 } and we consider a truncated version of them, that we call mixed return words. We also have to replace the basis of a subgroup by its symmetric version containing the inverses of its elements, called a symmetric basis. The free group is then obtained as the fundamental group of a compact surface in which a finite number of points are removed, and linear involutions are seen as Poincaré sections of measured foliations of the surface. The return words to a given word can be seen as different ways of choosing a section.

We prove that if a language S is the natural coding of a linear involution T without connections on the alphabet A, the following holds.

• The set of mixed return words to a given word w (recall that they are defined with respect to the set {w, w -1 }) in S is a symmetric basis of the free group on A (Theorem 6.4).

• Let G be a subgroup of finite index of the free group F A . The set of prime words in S with respect to G is a symmetric basis of G (Theorem 6.9). By prime words in S with respect to G, we mean the nonempty words in G ∩ S without a proper nonempty prefix in G ∩ S. Even if the proofs provided here concerning the algebraic properties of return words are of a topological and geometric flavor, these properties hold in a wider combinatorial context through the notion of specular set and specular groups, where the present geometric background does a priori not exist. Extensions of Theorem 6.4 and 6.9 are proved to hold in this context in [START_REF] Berthé | Specular sets[END_REF]. We also emphasize as part of our motivation the great importance of return words as a tool for symbolic dynamics and its relations with other structures. For instance, they are closely related to induction and renormalization, they allow the characterization of substitutive words [START_REF] Durand | A characterization of substitutive sequences using return words[END_REF], they provide spectral information through eigenvalues (see, e.g., [START_REF] Bufetov | On the modulus of continuity for spectral measures in substitution dynamics[END_REF]), or else, they yield so-called S-adic representations [START_REF] Durand | Linearly recurrent subshifts have a finite number of nonperiodic subshift factors[END_REF][START_REF] Durand | Corrigendum and addendum to: "Linearly recurrent subshifts have a finite number of non-periodic subshift factors[END_REF]. This paper is organized as follows. In Section 2, we recall notions concerning words, free groups and graphs. Linear involutions are defined in Section 3. We also recall that, by a result of [START_REF] Boissy | Dynamics and geometry of the Rauzy-Veech induction for quadratic differentials[END_REF], a nonorientable linear involution without connections is minimal. In Section 4, we provide the necessary geometric background on natural involutions. We focus on the symbolical properties of their natural codings in Section 5 and we introduce the notion of return word we will work with, as well as even letters and the even group. The geometric and topological proofs of the main results on return words for natural codings of linear involutions are given in Section 6.

Ackowledgement This work was supported by grants from Region Ile-de-France (project DIM RDM-IdF), and by the ANR projects Dyna3S ANR-13-BS02-0003 and Eqinocs ANR-11-BS02-004. We also warmly thank the referees for their valuable comments.

Words, free groups and laminary sets

In this section, we introduce notions concerning sets of words and free groups.

Let A be a finite nonempty alphabet and let A * be the set of all words on A. We let 1 or ε denote the empty word. A set of words is said to be factorial if it contains the factors of its elements.

The notation a -1 will be interpreted as an inverse in the free group F A on A. We also use the notation ā instead of a -1 .

A set of reduced words on the alphabet A ∪ A -1 is said to be symmetric if it contains the inverses of its elements. Let X * be the submonoid of (A ∪ A -1 ) * generated by X without reducing the products. If X is symmetric, the subgroup of F A generated by X is the set obtained by reducing the words of X * .

Definition 2.1 (Symmetric basis) If X is a basis of a subgroup H of F A , the set X ∪ X -1 is called a symmetric basis of H.
In particular, A ∪ A -1 is a symmetric basis of F A . Note that a symmetric basis X ∪ X -1 is not a basis of H but that any w ∈ H can be written uniquely w = x 1 x 2 • • • x n with x i ∈ X ∪ X -1 and x i x i+1 is not equivalent to 1 for 1 ≤ i ≤ n -1. We recall that, by Scheier's Formula, any basis of a subgroup of index d of a free group on k symbols has d(k -1) + 1 elements. Hence, if Y is a symmetric basis of a subgroup of index d in a free group on k symbols, then Card(Y ) = 2d(k -1) + 2.

The following definition follows [START_REF] Thierry Coulbois | R-trees and laminations for free groups. I. Algebraic laminations[END_REF] and [START_REF] Lopez | Lamination languages. Ergodic Theory Dynam[END_REF].

Definition 2.2 (Laminary set) A symmetric factorial set of reduced words on the alphabet A ∪ A -1 is called a laminary set on A.

A laminary set S is called semi-recurrent if for any u, w ∈ S, there is v ∈ S such that uvw ∈ S or uvw -1 ∈ S. Likewise, it is said to be uniformly semirecurrent if it is right extendable and if for any word u ∈ S there is an integer n ≥ 1 such that for any word w of length n in S, u or u -1 is a factor of w. A uniformly semi-recurrent set is semi-recurrent.

Following again the terminology of [START_REF] Thierry Coulbois | R-trees and laminations for free groups. I. Algebraic laminations[END_REF], we say that a laminary set S is orientable if there exist two factorial sets S + , S -such that S = S + ∪ S -with S + ∩ S -= {ε} and for any x ∈ S, one has x ∈ S -if and only if x -1 ∈ S + . Note that if S is a semi-recurrent orientable laminary set, then the sets S + , S - as above are unique (up to their interchange). The sets S + , S -are called the components of S. Moreover a uniformly recurrent and orientable laminary set is a union of two uniformly recurrent sets. Indeed, S + and S -are uniformly recurrent.

Linear involutions

In this section, we define linear involutions, which are a generalization of interval exchange transformations. We first give the basic definitions including generalized permutation and length data, and then discuss minimality for involutions in relation with the notion of connection.

Definition

Let A be an alphabet with k elements.

We consider two copies I × {0} and I × {1} of an open interval I of the real line and we define Î = I × {0, 1}. We call the sets I × {0} and I × {1} the two components of Î. We consider each component as an open interval.

A generalized permutation on A of type (ℓ, m), with ℓ+m = 2k, is a bijection π : {1, 2, . . . , 2k} → A ∪ A -1 . We represent it by a two line array π = π(1) π(2) . . . π(ℓ) π(ℓ + 1) . . . π(ℓ + m) .

A length data associated with (ℓ, m, π) is a nonnegative vector λ ∈ R A∪A -1

+ = R 2k
+ such that λ π(1) + . . . + λ π(ℓ) = λ π(ℓ+1) + . . . + λ π(2k) and λ a = λ a -1 for all a ∈ A.

We consider a partition of I × {0} (minus ℓ -1 points) into ℓ open intervals I π(1) , . . . , I π(ℓ) of lengths λ π(1) , . . . , λ π(ℓ) and a partition of I × {1} (minus m -1 points) into m open intervals I π(ℓ+1) , . . . , I π(ℓ+m) of lengths λ π(ℓ+1) , . . . , λ π(ℓ+m) .

Recall that 2k = ℓ + m. Let Σ be the set of 2k -2 division points separating the intervals I a for a ∈ A ∪ A -1 . The linear involution on I relative to these data is the map T = σ 2 • σ 1 defined on the set Î \ Σ, formed of Î minus 2k -2 points, and which is the composition of two involutions defined as follows.

(i) The first involution σ 1 is defined on Î \ Σ. It is such that for each a ∈ A ∪ A -1 , its restriction to I a is either a translation or a symmetry from I a onto I a -1 . Since σ 1 is an involution, its respective restrictions to I a and I a -1 are of the same nature, that is, either a translation or a symmetry. Thus, there are real numbers α a such that for any (x, δ) ∈ I a , one has σ 1 (x, δ) = (x + α a , γ) in the first case, and σ 1 (x, δ) = (-x + α a , γ) in the second case (with γ ∈ {0, 1}). (ii) The second involution exchanges the two components of Î. It is defined for (x, δ) ∈ Î by σ 2 (x, δ) = (x, 1δ). The image of z by σ 2 is called the mirror image of z. We also say that T is a linear involution on I relative to the alphabet A or that it is a k-linear involution to express the fact that the alphabet A has k elements. Let T be the 4-linear involution corresponding to the length data represented in Figure 3.1. We represent I × {0} above I × {1} with the assumption that the restriction of σ 1 to I a and I d is a symmetry while its restriction to I b , I c is a translation. We indicate on the figure the effect of the transformation T on Thus the notion of linear involution is an extension of the notion of interval exchange transformation in the following sense. Assume that ℓ = m = k, that A = {π(1), . . . , π(k)}, and that the restriction of σ 1 to each subinterval is a translation. Then, the restriction of T to I × {0} is an interval exchange (and so is its restriction to I × {1} which is the inverse of the first one). Thus, in this case, T is a pair of mutually inverse interval exchange transformations.

z T (z) T 2 (z) a b a -1 c c -1 d -1 b -1 d
It is also an extension of the notion of interval exchange with flip(s) [START_REF] Nogueira | Almost all interval exchange transformations with flips are nonergodic[END_REF][START_REF] Nogueira | Orbit structure of interval exchange transformations with flip[END_REF]. Assume again that ℓ = m = k, that A = {π(1), . . . , π(k)}, but now that the restriction of σ 1 to at least one subinterval is a symmetry. Then the restriction of T to I × {0} is an interval exchange with flip(s).

Note that we consider in this paper interval exchange transformations defined by a partition of an open interval minus finitely many points in a finite number of open intervals. The usual notion of interval exchange transformation uses a partition of a semi-interval in a finite number of semi-intervals. One recovers the usual notion of interval exchange transformation on a semi-interval by attaching to each open interval its left endpoint.

A linear involution T is a bijection from Î \ Σ onto Î \ σ 2 (Σ). Since σ 1 , σ 2 are involutions and

T = σ 2 • σ 1 , the inverse of T is T -1 = σ 1 • σ 2 .
The set of singular points of T is defined as the set Σ of division points of T and their mirror images are the singular points of T -1 . Note that these singular points z may be 'false' singularities (that is, false discontinuities), in the sense that T can have a continuous extension to an open neighborhood of z.

Two particular cases of linear involutions deserve attention.

Definition 3.2 (Nonorientable linear involution)

A linear involution T on the alphabet A relative to a generalized permutation π of type (ℓ, m) is said to be nonorientable if there are indices i, j ≤ ℓ such that π(i) = π(j) -1 (and thus indices i, j ≥ ℓ + 1 such that π(i) = π(j) -1 ). In other words, there is some a ∈ A ∪ A -1 for which I a and I a -1 belong to the same component of Î. Otherwise T is said to be orientable.

Definition 3.3 (Coherent linear involution)

A linear involution T = σ 2 • σ 1 on I relative to the alphabet A is said to be coherent if, for each a ∈ A∪A -1 , the restriction of σ 1 to I a is a translation if and only if I a and I a -1 belong to distinct components of Î.

Example 3.4

The linear involution of Example 3.1 is coherent. Let us consider now the linear involution T which is the same as in Example 3.1, but such that the restriction of σ 1 to I c is a symmetry. Thus T is not coherent. We assume that

I =]0, 1[, that λ a = λ d , that 1/4 < λ c < 1/2 and that λ a + λ b < 1/2. Let z = 1/2 + λ c (see Figure 3.2). We have then T 3 (z) = z, showing that T is not minimal. Indeed, since z ∈ I c , we have T (z) = 1 -z = 1/2 -λ c . Since T (z) ∈ I a we have T 2 (z) = (λ a + λ b )+ (λ a -1 + z) = z -λ c = 1/2. Finally, since T 2 (z) ∈ I d -1 , we obtain 1 -T 3 (z) = T 2 (z) -λ c = 1 -z and thus T 3 (z) = z. z = T 3 (z) T (z) T 2 (z) a b a -1 c c -1 d -1 b -1 d Figure 3.2: A noncoherent linear involution.
Linear involutions which are orientable and coherent correspond to interval exchange transformations, whereas orientable but noncoherent linear involutions are interval exchanges with flip(s).

Orientable linear involutions correspond to orientable laminations (see Section 4), whereas coherent linear involutions correspond to orientable surfaces. Thus coherent nonorientable involutions correspond to nonorientable laminations on orientable surfaces.

Minimality

We first recall the notion of connection and then prove that involutions without connections are essentially always minimal.

Definition 3.5 (Connection) A connection of a linear involution T is a triple (x, y, n) where x is a singularity of T -1 , y is a singularity of T , n ≥ 0 and T n x = y.
Let T be a linear involution without connections. Let

O = n≥0 T -n (Σ) and Ô = O ∪ σ 2 (O) (3.1)
be respectively the negative orbit of the singular points and its closure under mirror image. Then T is a bijection from Î \ Ô onto itself. Indeed, assume that

T (z) ∈ Ô. If T (z) ∈ O then z ∈ Ô. Next if T (z) ∈ σ 2 (O), then T (z) ∈ σ 2 (T -n (Σ)) = T n (σ 2 (Σ)) for some n ≥ 0. We cannot have n = 0 since σ 2 (Σ) is not in the image of T . Thus z ∈ T n-1 (σ 2 (Σ)) = σ 2 (T -n+1 (Σ)) ⊂ σ 2 (O).
Therefore in both cases z ∈ Ô. The converse implication is proved in the same way. Note that Î \ Ô is dense in Î, and the nonnegative orbit of any point of Î \ Ô is well-defined.

Definition 3.6 (Minimality) A linear involution T on I without connections is minimal if for any point z ∈ Î \ Ô the nonnegative orbit of z is dense in Î.
Note that when a linear involution is orientable, that is, when it is a pair of interval exchange transformations (with or without flips), the interval exchange transformations can be minimal although the linear involution is not since each component of Î is stable by the action of T . Moreover, it is shown in [START_REF] Danthony | Measured foliations on nonorientable surfaces[END_REF] that noncoherent linear involutions are almost surely not minimal.

Let X ⊂ I × {0, 1}. The return time ρ X to X is the function from I × {0, 1} to N ∪ {∞} defined on X by ρ X (x) = inf{n ≥ 1 | T n (x) ∈ X}. (3.2)
The following result is proved in [START_REF] Boissy | Dynamics and geometry of the Rauzy-Veech induction for quadratic differentials[END_REF] (Proposition 4.2) for the class of coherent involutions. The proof uses Keane's theorem proving that an interval exchange transformation without connections is minimal [START_REF] Keane | Interval exchange transformations[END_REF]. The proof of Keane's theorem also implies that for each interval of positive length, the return time to this interval is bounded. Proposition 3.7 Let T be a linear involution without connections on I. If T is nonorientable, it is minimal. Otherwise, its restriction to each component of Î is minimal. Moreover, in both cases, for each interval of positive length included in Î, the return time to this interval takes a finite number of values.

Proof. Consider the set I = Î × {0, 1} = I × {0, 1} 2 and the transformation T on I defined for (x, δ) ∈ I by

T (x, δ) = (T (x), δ) if T is a translation on a neighborhood of x (T (x), 1 -δ) otherwise.
Let T ′ be the transformation induced by T on

I ′ = I × {0, 0}. Note that if x ∈ I ′ is recurrent, that is, T n (x) ∈ I ′
for some n > 0, then the restriction of T ′ to some neighborhood of x is a translation. Indeed, there is an even number of indices i with 0 ≤ i < n such that T is a symmetry on a neighborhood of T i (x).

Let us show that T ′ is an interval exchange transformation. Let Σ be the set of singularities of T . For each z ∈ Σ, let s(z) be the minimal integer s > 0 (or

∞) such that T -s (z) ∈ I ′ . Let N = { T -s(z) (z) | z ∈ Σ with s(z) < ∞}. The set N divides I ′ into a finite number of disjoint open intervals. If J is such
an open interval, it contains, by the Poincaré Recurrence Theorem, at least one recurrent point x ∈ I ′ for T , that is such that T n (x) ∈ I ′ for some n > 0. By definition of N , all the points of J are recurrent. Moreover, as we have seen above, the restriction of T ′ to J is a translation. This shows that T ′ is an interval exchange transformation.

We can now conclude the proof. Since T has no connection, T ′ has no connection. Thus, by Keane's theorem, it is minimal. This shows that the intersection with I × {0} of the nonnegative orbit of any point in I × {0} is dense in I × {0}. A similar proof shows that the same is true for I × {1}. If T is nonorientable, the nonnegative orbit of any x ∈ I × {0} contains a point in I × {1}. Thus its nonnegative orbit is dense in Î. The same holds symmetrically for x ∈ I × {1}.

Let J be an interval of positive length included in I. By Keane's theorem, the return time to J × {0, 0} relative to T ′ takes a finite number of values. Thus the return time to J × {0} with respect to T takes also a finite number of values. A similar argument holds for an interval included in I × {1}.

Measured foliations and linear involutions

Let us now introduce a geometric and topological viewpoint on natural involutions. The main actors are measured foliations of surfaces introduced by W.P. Thurston (see [START_REF] Fathi | Travaux de Thurston sur les surfaces[END_REF] for an introduction, and see also [START_REF] Hatcher | Algebraic topology[END_REF]). They can be considered as two-dimensional extensions of linear involutions. They are defined on a compact surface X in which a finite number of points Σ ⊂ X are removed. Poincaré sections of these measured foliations are then linear involutions.

A foliation is a decomposition of a surface as a union of leaves which are 1-dimensional. As an example, the plane R 2 decomposes as a union of vertical lines. Let X be a (non-necessarily orientable) surface. A foliation on X is a covering of X by charts φ i :

X i → R 2 such that the transitions φ i • φ -1 j : φ j (X i ∩ X j ) → φ i (X i ∩ X j )
preserve vertical lines, in other words they are of the form:

φ i • φ -1 j (x, y) = (f ij (x), g ij (x, y)) with f ij (x) = ±x + c ij .
In the chart φ j , each stripe x = a matches up with the stripe x = f ij (a) in X i . Gluing all together these stripes we obtain a leaf of the foliation which is a one-dimensional manifold immersed in X. Each leaf is hence homeomorphic to the circle R/Z or the line R. The surface X decomposes as the union of these leaves.

Given a nonsingular smooth vector field, or more generally a line field, the integral curves of this field provide a foliation. In Figure 4.2 we show an example of a foliation of a surface related to this linear involution. This surface is built from a polygon where vertices are removed and edges are glued with orientation preserving isometry.

Let now X be a compact surface. A singular foliation on X is a foliation F defined on X\Σ where Σ ⊂ X is a finite set of points and such that in the neighborhood of each point of Σ the foliation is homeomorphic to the foliation of the punctured disc in C given by the line field z p (dz) 2 = I; in other words, the leaves are the branches of γ c (t) = (It + c) 1/(p/2+1) where c ∈ C is a constant (see also leaves (which are half-lines that hit 0) that we call separatrices. We say that the singularity of the foliation has angle (p + 2)π or degree p.

On the surface obtained from the polygon of Figure 4.2, one can check that the foliation has 4 singularities of degree p = -1 (or angle π).

A transverse measure on F is a measure µ defined on transverse arcs to F that is invariant under homotopy along the leaves and which is finite on compact intervals. A measured foliation is a singular foliation endowed with a transverse measure. We will see that linear involutions and measured foliations are essentially the same objects. In Figure 4.2, the natural transverse measure is simply the integral of dx along curves (where x is the natural horizontal coordinate in the plane).

A measured foliation is denoted as (X, Σ, F , µ) or (F , µ) when the space X and the set Σ are understood.

A connection of F is a finite leaf that joins two points of Σ.

Definition 4.2 Let (X, Σ, F , µ) be a measured foliation without connections. A closed segment I ⊂ X is admissible if • it is transverse to F ,
• its interior avoids Σ and both endpoints are on singular leaves,

• the leaf segments that join one endpoint to a singularity do not intersect the interior of I.

We consider admissible intervals as being oriented, that is, having a start and an end. Because of the transverse measure, there is always a prefered parametrization for segments: we always assume that parametrization of a seg-

ment γ : [0, t] → X is such that µ(γ([s, s ′ ])) = s ′ -s.
In other words, there is a unique parametrization such that µ| I is the image of the Lebesgue measure. For a transverse segment I and δ > 0 small enough, there is a neighborhood of I which is isomorphic to [0, µ(I)] × [-δ, δ], and for which the leaves of the foliation on the rectangle are the vertical segments. For a piece of leaf that crosses the segment I, it hence makes sense to say going up or going down.

We define the Poincaré map of the foliation on I × {0, 1} as follows. For a point x ∈ I, we define σ 1 (x, 0) as the point (y, i) ∈ I × {0, 1} where y is the first point of the interior of I that is crossed by following the leaf from x and going up. If we arrive from above we set i = 0 and if not we set i = 1. Next, σ 1 (x, 1) is defined similarly, but following the leaf from x by going down. The map σ 1 is not defined if the leaf encounters a singularity before returning into I. The map σ 2 is the exchange (x, 0) → (x, 1) and (x, 1) → (x, 0). The transformation T is the composition σ 2 • σ 1 . The sequence (x, 0), T (x, 0), T 2 (x, 0), . . . is by construction the sequence of intersections of the leaf from x with I. The total angle of a foliation is the sum of the angles of the singularities. Lemma 4.4 Let (X, Σ, F , µ) be a measured foliation without connections of total angle (2k -2)π. Let I be an admissible interval. Then the Poincaré map induced on I × {0, 1} is a k-linear involution without connections.

Proof. If the foliation has no connection, then each infinite half-leaf intersects I. We consider singularities for the Poincaré map, in other words the points in I that run into a singularity before going back to I. This set cuts the domain I ×{0, 1} into subintervals. As the transverse measure is preserved, the Poincaré map is an isometry restricted to each of these subintervals. It is hence a linear involution.

For each subinterval I a , let R a be the rectangle made of the union of the leaf segments that start from I a to T (I a ). On each of the two vertical boundaries of these rectangles there is exactly one singularity except for two of the extreme rectangles. It follows that there are k pairs of subintervals for the Poincaré map.

Note that if p 1 , . . . , p s are the degrees of the singularities, then the sum of the angles is (p 1 + 2)π + . . . + (p s + 2)π = (2k -2)π, and thus that p 1 + . . . + p s + 2s + 2 = 2k.

In the example of The following lemma is the converse of Lemma 4.4.

Lemma 4.5 Let T be a linear involution without connections. Then there exists a measured foliation (X, Σ, F , µ) without connections and an admissible interval I ⊂ X such that T is conjugate to the Poincaré map of the foliation F on I.

Proof. We just use the reverse procedure as in the proof of Lemma 4.4. For each subinterval I a , we consider a rectangle R a = I a × [0, 1]. The vertical boundaries of the rectangles can be glued together to give a foliation. Note that there is no need to glue the vertical sides of the rectangles by isometry since we are only interested in the transverse measure dx.

The pair (F , µ, I) of a measured foliation and an admissible interval associated with T as above is called a suspension of T .

Natural codings

We now focus on return words of linear foliations. Algebraic information on the set of return words (see Theorem 6.4 below) then will follow from the remark that a section captures the geometry of the surface (see Lemma 6.1) and that the free group is geometrically seen as the fundamental group π 1 (X\Σ).

Natural codings of linear involutions

In this section, we introduce the natural coding of a linear involution T . It is obtained by first coding the orbits under T with respect to the partition provided by the intervals I a (a ∈ A ∪ A -1 ), and then, by taking the language of the associated symbolic dynamical system.

Let T be a linear involution on I, let Î = I × {0, 1} and let Ô be the set defined by Equation (3.1). Given z ∈ Î \ Ô, the infinite natural coding of T relative to z is the infinite word Σ T (z) = a 0 a 1 . . . on the alphabet A ∪ A -1 defined by

a n = a if T n (z) ∈ I a .
We first observe that the infinite word Σ T (z) is reduced. Indeed, assume that a n = a and a n+1 = a -1 with a ∈ A ∪ A -1 . Set x = T n (z) and y = T (x) = T n+1 (z). Then x ∈ I a and y ∈ I a -1 . But y = σ 2 (u) with u = σ 1 (x). Since x ∈ I a , we have u ∈ I a -1 . This implies that y = σ 2 (u) and u belong to the same component of Î, a contradiction.

Definition 5.1 (Natural coding) Let T be a linear involution. We let L(T ) denote the set of factors of the infinite natural codings of T . We say that L(T ) is the natural coding of T .

As classically done in symbolic dynamics for codings, the set L(T ) can be easily described in terms of intervals associated with factors, obtained by refining the coding partition. Lemma 5.2 Let T be a linear involution. For a nonempty word u = a 0 a 1 • • • a m-1 on A ∪ A -1 , we define

I u = I a0 ∩ T -1 (I a1 ) ∩ . . . ∩ T -m+1 (I am-1 ).
By convention, I ε = Î. We have Let u be a factor of L(T ). By Definition 5.1, there exists a point z ∈ Î \ Ô such that u is a factor of Σ T (z). In particular, T -n (z) never belongs to the set Σ of singular points, for any nonnegative n. Hence, for any z ∈ Î \ Ô, one has z ∈ I u if and only if u is a prefix of Σ T (z).

u ∈ L(T ) ⇐⇒ I u = ∅.
If u is a factor of Σ T (z) for some z ∈ Î \ Ô, then T n (z) ∈ I u for some n ≥ 0 and thus

I u = ∅. Conversely, if I u = ∅, since I u is an open interval, it contains some z ∈ Î \ Ô. Then u is a prefix of Σ T (z) and thus u ∈ L(T ).
Observe that if T is nonorientable and without connections, then by Proposition 3.7, L(T ) is the set of factors of Σ T (z) for any z ∈ Î \ Ô, that is, the set of factors of Σ T (z) does not depend on z. Indeed, if I u = ∅, since the orbit of z is dense in Î, there is an n ≥ 0 such that T n (z) ∈ I u and thus u is a factor of Σ T (z). Proposition 5.3 Let T = σ 2 • σ 1 be a linear involution. For any nonempty word u ∈ L(T ), one has I u -1 = σ 1 T |u|-1 (I u ). Consequently the set L(T ) is closed under taking inverses. It is thus a laminary set. Proof. To prove the assertion, we use an induction on the length of u. The property holds for |u| = 1 by definition of σ 1 . Next, consider u ∈ L(T ) and a ∈ A ∪ A -1 such that ua ∈ L(T ). We assume by induction hypothesis that

I u -1 = σ 1 T |u|-1 (I u ). Since T -1 = σ 1 • σ 2 , σ 1 T |u| (I ua ) = σ 1 T |u| (I u ∩ T -|u| (I a )) = σ 1 T |u| (I u ) ∩ σ 1 (I a ) = σ 1 σ 2 σ 1 T |u|-1 (I u ) ∩ σ 1 (I a ) = σ 1 σ 2 (I u -1 ) ∩ I a -1 = I a -1 u -1
where the last equality results from

I a -1 u -1 = T -1 I u -1 ∩ I a -1 .
We easily deduce that the set L(T ) is closed under taking inverses. Furthermore it is a factorial subset of the free group F A . It is thus a laminary set.

Example 5.4 Let T be the linear involution of Example 4.1. This linear involution is one of the simplest nontrivial examples of linear involution we can think of, with respect to the size of the alphabet. By nontrivial, we mean in particular that it is without connections and nonorientable (it thus admits odd and even letters, see Example 5.8 and Example 6.11 below). This simple example illustrates how Rauzy induction can be used to understand natural codings. Recall that Rauzy induction was initially defined for interval exchanges in [START_REF] Rauzy | Échanges d'intervalles et transformations induites[END_REF] and extended to linear involutions in [START_REF] Boissy | Dynamics and geometry of the Rauzy-Veech induction for quadratic differentials[END_REF]. Recall also that induction is intimately connected with return words.

The set S = L(T ) can actually be defined directly as the set of factors of the substitution

f : a → cb -1 , b → c, c → ab -1
which extends to an automorphism of the free group F A . The natural coding of T thus bares some analogy with the language of the Fibonacci morphism a → ab, b → a (see also Example 6.8). Indeed, the Rauzy induction applied to T gives the linear involution T ′ represented in Figure 5.1 on the left. It is the transformation induced by T on the interval obtained by erasing the smallest interval on the right, namely I a -1 .

The Rauzy induction applied on T ′ is obtained by erasing the smallest interval on the right, namely I b -1 . It gives a transformation T ′′ represented in Figure 5.1 on the right.

The transformation T ′′ is the same as T up to normalization of the length of the interval, exchange of the two components and the permutation (written in cycle form) π = (a c b a -1 c -1 b -1 ) (see Figure 5.1) which sends a to c, c to b and so on.

Set S = L(T ), S ′ = L(T ′ ) and S ′′ = L(T ′′ ). Since T ′ is obtained from T by a Rauzy induction, there is an associated automorphism τ ′ of the free group such that S = Fact(τ ′ (S ′ )) (where the notation Fact( ) stands for the set of factors). One has actually τ one has

′ : a → ab -1 , b → b, c → c. Similarly, a a -1 b b -1 c c -1 a a -1 b b -1 c c -1
S ′ = Fact(τ ′′ (S ′′ )) with τ ′′ : a → a, b → bc -1 , c → c. Furthermore, S ′′ = π -1 (S). Set τ = τ ′ • τ ′′ . It is easy to verify that f = τ • π -1 . Since S = Fact(τ (S ′′ )) = Fact(τ π -1 (S)) = Fact(f (S))
, we obtain that S is the set of factors of the fixpoint of f as claimed above.

Orientability and uniform recurrence

We gather here basic properties of the language L(T ) of a linear involution. We recall that the notion of orientability for a laminary set was introduced in Section 2.

Proposition 5.5 Let T be a linear involution. If T is orientable, then L(T ) is orientable. The converse is true if T is without connections.

Proof. Let T be a linear involution and let S = L(T ). Assume that T is orientable.

Set S + = {u ∈ S | I u ⊂ I × {0}} ∪ {ε} and S -= {u ∈ S | I u ⊂ I × {1}} ∪ {ε}. Then S = S + ∪ S -.
Since T is orientable, we have u ∈ S + (resp. u ∈ S -) if and only if all letters of u are in S + (resp. in S -). This shows that S + ∩ S -= {ε}, that S + , S -are factorial, and that u ∈ S + if and only if u -1 ∈ S -. Thus S is orientable. Conversely, assume that T is nonorientable and is without connections. Let a ∈ A be such that I a , I a -1 ⊂ I × {0}. Since T is minimal by Proposition 3.7, there is some z ∈ I a and n > 0 such that T n (z) ∈ I a -1 . Thus S contains a word of the form aua -1 . This implies that S is nonorientable.

The following statement can be easily deduced from the similar statement for interval exchange transformations (see [7, p. 392]). Proposition 5.6 Let T be a linear involution without connections. If T is nonorientable, then L(T ) is uniformly recurrent. Otherwise, L(T ) is uniformly semi-recurrent.

Proof. Set S = L(T ). Let u ∈ S and let N be the maximal return time to I u (this exists by Proposition 3.7). Thus for any z ∈ Î such that the return time ρ Iu (z) is finite (see Equation (3.2)), we have ρ Iu (z) ≤ N . Let w be a word of S of length N + |u| and let z ∈ Î \ Ô be such that Σ T (z) begins with w.

If T is nonorientable, by Proposition 3.7, it is minimal. Thus there exists n > 0 such that T n (z) ∈ I u . This implies that ρ Iu (z) is finite and thus that ρ Iu (z) ≤ N . This implies in turn that u is a factor of w. We conclude that S is uniformly recurrent.

If T is orientable, then the restriction of T to each component of Î is minimal. By Proposition 5.5, S is orientable. Thus I u and I u -1 cannot be included in the same component of Î, since otherwise S would contain a word of the form uvu -1 , and S would be nonorientable. Thus I w is in the same component as I u or I u -1 , and we conclude as above that u or u -1 is a factor of w. This shows that S is uniformly semi-recurrent.

Return words and the even group

In this section, we first introduce odd and even words, and then discuss various notions of return words. Definition 5.7 (Even group) Let T be a linear involution without connections.

We say that a letter a ∈ A is even (with respect to T ) if I a and I a -1 belong to distinct components of Î and odd, otherwise.

A reduced word is said to be if it has an even number of odd letters and said to be odd, otherwise. In particular, if T is orientable, all words are even.

The even group is the subgroup of the free group F A formed by the even words.

Note that a word w is even if and only if for any z ∈ I w , the points z and T |w| (z) belong to the same component. Since σ 2 I w -1 = T |w| (I w ) according to Proposition 5.3, w is even if and only if I w and I w -1 belong to distinct components of Î. Hence a word w is even if and only if I w and T -|w| I w belong to the same component.

If T is assumed to be nonorientable, the even group is a subgroup of index 2 of F A ; it has thus rank 2 Card A -1 according to Schreier's formula.

Example 5.8 Let T be the linear involution of Example 4.1. The letter a is even and the letters b, c are odd. The even group is generated by the set Z = {a, bāc, bc, bc, bc}.

We now introduce several notions of return words. Let T be a linear involution relative to the alphabet A and let S = L(T ) be its natural coding. Recall that S is a factorial subset of the free group F A .

For a set W ⊂ S, a complete return word to W is a word of S which has a proper prefix in W and a proper suffix in W , and that has no internal factor in W . If S is uniformly recurrent (in particular, if T is nonorientable and without connections, by Proposition 5.6), the set of complete return words to W is finite for any finite set W .

We now focus on return words for two types of sets W , namely sets reduced to one word or symmetric sets of the form {w, w -1 }.

By considering the set {w}, one recovers the classical notion of return word. For any w ∈ S, a right return word to w in S is a word u such that wu is a complete return word to {w}. We denote by R S (w) the set of right return words to w in S. We define similarly left return words. Remark 5.9 Note that all elements of R S (x) are even. Indeed, if w ∈ R S (x), we have xw = vx for some v ∈ S. We assume w.l.o.g. that x is odd and that I x ⊂ I × {0}. Take z ∈ I xw . Then T |x| (z) ∈ I × {1} since x is odd. One has T |x| (z) ∈ I w . Hence I w ⊂ I × {1}. But T |w| (I w ) ⊂ T -|x| I x ⊂ I × {1} (again since x is odd). Hence T |w| (I w ) and I w belong to the same component and w is even. The other cases can be handled similarly.

For w ∈ S, we also consider complete return words to the set W = {w, w -1 } in S. We let CR S (w) denote this set and call its elements the complete return words to {w, w -1 }.

In order to provide a connection between return words and elements of a symmetric basis of the free group, we need to introduce a further notion that plays the role of usual return words in symbolic dynamics. Definition 5.10 (Mixed return words) With a complete return word u to the set {w, w -1 }, we associate a word N (u) as follows: if u has w as prefix, we erase it and if u has a suffix w -1 , we also erase it. Such a word is called a mixed return word.

The words N (u) for u complete return word to {w, w -1 } are called mixed return words. We let MR S (w) denote this set.

The convention chosen for the transformation N corresponds to the induction on I w -1 ∪ σ 2 (I w -1 ) (see Lemma 5.12 below).

Note that the two operations described above can be made in any order since w and w -1 cannot overlap. Note also that MR S (w) is symmetric and that w -1 MR S (w)w = MR S (w -1 ).

If T is orientable, then MR S (w) is equal to the union of the set of right return words to w with the set of left return words to w -1 .

Observe that any uniformly recurrent biinfinite word x whose set of factors is S can be uniquely written as a concatenation of mixed return words (see Figure 5.2). Note also that successive occurrences of w may overlap but that successive occurrences of w and w -1 cannot. The reason for introducing the notion of mixed return words (see Definition 5.10) comes from the fact that we are interested in the transformation induced on I w ∪ σ 2 (I w ), according to Section 4 (see Remark 4.3). The natural coding of a point in I w begins with w while the natural coding of a point z in σ 2 (I w ) is preceded by w -1 in the sense that the natural coding of T -|w| (z) begins with w -1 . To be more precise, the convention chosen for the transformation N corresponds to the induction on I w -1 ∪ σ 2 (I w -1 ), such as shown with the following lemma. Recall that the notation ρ X stands for the return time to X. Lemma 5.12 Let T be a linear involution withhout connections and w a nonempty word in its natural coding L(T ). Let K w = I w -1 ∪ σ 2 (I w -1 ). Then the set of mixed return words to w are exactly the prefixes of length ρ Kw (z) of the infinite natural coding of points z ∈ K w .

Proof. Let u be the prefix of length ρ Kw (z) of Σ T (z) for some z ∈ K w . Let us first recall that σ 2 (I w -1 ) = T |w| (I w ) (Proposition 5.3). Assume first that the length of u is larger than or equal to the length of w. If z ∈ I w -1 , then u starts with w -1 while if z ∈ σ 2 (I w -1 ) then wu is in L(T ). Similarly, if T |u| (z) ∈ I w -1 then uw -1 is in L(T ) while if T |u| (z) ∈ σ 2 (I w -1 ) then u ends with w. In all four possible cases, u, wu, uw -1 and wuw -1 are in L(T ).

Let

p = ε if z ∈ I w -1 , w if z ∈ σ 2 (I w -1 ), and s = w -1 if T |u| (z) ∈ I w -1 , ε if T |u| (z) ∈ σ 2 (I w -1 ).
Since I w -1 and σ 2 (I w -1 ) are included into two distinct components, there is no cancellation in the product pus. Moreover, |pus| ≥ |u| and hence pus starts and ends with an occurrence of w or w -1 . One thus has N (pus) = u and pus is a complete return word to {w, w -1 }.

Let conversely u be a mixed return word to w and let u ′ be the complete return word such that u = N (u ′ ). Write u ′ = pus. Assume first that u ′ = wu. Then wu ends with w. For any point y ∈ I u ′ , set x = T |w] (y). Then x ∈ T |w] I w = σ 2 (I w -1 ), x ∈ I u , and thus T |u| x ∈ σ 2 (I w -1 ) and ρ Kw (x) = |w|. Hence u is the prefix of length ρ Jw (x) of Σ T (x). The proof in the three other cases is similar.

We end this section by introducing a further variation around return words, adapted to subgroups of the free group (the interest of this notion will be highlighted by Theorem 6.9 below). Definition 5.13 (Prime words) Let G be a subgroup of the free group F A . Let S be a laminary set. The prime words in S with respect to G are the nonempty words in G ∩ S without a proper nonempty prefix in G ∩ S.

Example 5.14 Let T be the linear involution of Example 4.1. The set of prime words with respect to the even group is the set Z ∪ Z -1 where Z is as in Example 5.8.

Return words and fundamental group

We now interpret the notions of 'return words' we have seen so far (to a word, or with respect to a subgroup via the notion of prime words) in geometrical terms.

We consider a punctured surface (X, Σ). Fixing a base point x 0 , recall that the fundamental group π 1 (X\Σ, x 0 ) is the set of equivalence classes of loops in X\Σ based at x 0 up to homotopy. One ingredient of our main results (Theorem 6.4 and Theorem 6.9) is that with each admissible interval for the foliation (in the sense of Definition 4.2) is associated a symmetric basis of the fundamental group as we shall see below. Furthermore, the fundamental group is a free group.

Let (X, Σ, F , µ) be a measured foliation and assume that Σ is nonempty. Let I be an admissible interval and let x 0 be any point of I. By Lemma 4.4, the domain I × {0, 1} of the Poincaré map T is cut into 2k subintervals by the first return map. With each subinterval I a we associate an element of π 1 (X\Σ, x 0 ) as follows. Let x be a point in that subinterval, we consider the loop γ(x) which is the concatenation of • the segment in I that joins x 0 to x,

• the piece of leaf that joins x to x ′ = T (x),

• the segment in I that joins x ′ to x 0 . The homotopy class of γ(x) only depends on the subinterval to which x belongs. We let Γ(X, I, x 0 ) denote the set of equivalence classes of loops in π 1 (X\Σ, x 0 ) obtained by that process. The following lemma shows in particular that there are 2k classes. Lemma 6.1 Let (X, Σ, F , µ) be a measured foliation with total angle (2k -2)π. Then, if Σ is nonempty, the fundamental group of X\Σ is a free group on k generators. Moreover for any admissible interval I in X and any x 0 ∈ I, the set Γ(X, I, x 0 ) is a symmetric basis of π 1 (X\Σ, x 0 ).

Proof. Let I be an admissible interval. We consider the k loops obtained from the above construction. With an homotopy fixing x 0 , one can easily realize the loops in such way that the only common point between any two is x 0 . We let Y ⊂ X\Σ denote this set of d loops. Now we show that the punctured surface X\Σ is homotopic to Y . We may decompose the surface X\Σ into zippered rectangles as in Lemmas 4.4 and 4.5: we cut the surface along each singular leaf, from the singularities until the first time it hits the interior of I. In each rectangle there is exactly one loop passing through. It is easy to see that by a continuous deformation we can shrink each rectangle to that loop. In other words we build a homotopy to Y . Now Y is a connected sum of k loops (also called a rose) and its fundamental group is a free group of rank k generated by each curve that goes once through a loop.

Return words and bases of the free group

We now have gathered all what was needed to deduce algebraic properties of mixed return words.

Let T : I × {0, 1} → I × {0, 1} be a linear involution relative to the alphabet A and let S = L(T ). We have introduced with Definition 4.2 the notion of an admissible interval I ⊂ X with respect to a measured foliation (X, Σ, F , µ). We can formulate directly a similar definition for an open interval J ⊂ I with respect to a linear involution T defined on I as follows. Definition 6.2 (Admissible interval) Let T be a linear involution without connections defined on the interval I. The open interval J =]u, v[ with J ⊂ I is admissible with respect to T if for each of its two endpoints x = u, v, there is (i) either a singularity z of T -1 such that x = T n (z) and T k (z) / ∈ J for 0 ≤ k ≤ n, (ii) or a singularity z of T such that z = T n (x) and T k (x) / ∈ J for 0 ≤ k ≤ n.

The term 'admissible' was introduced originally by G. Rauzy [START_REF] Rauzy | Échanges d'intervalles et transformations induites[END_REF] for interval exchanges.

It is clear that if J is admissible with respect to T , then it is admissible with respect to any suspension (F , µ, I) of T . Hence, for any admissible interval of I with respect to T , the transformation induced on I is a k-linear involution without connections, according to Lemma 4.4. Furthermore, for any admissible interval of I, the Poincaré map of the foliation is the Poincaré map of the linear involution on the union I ∪ σ 2 (I).

The following result is proved in [START_REF] Dolce | Interval exchanges, admissibility and branching Rauzy induction[END_REF] for interval exchange transformations. The proof for linear involutions is the same. Recall that the intervals I w , w ∈ S, are defined in Section 5.1. Proposition 6.3 Let T be a k-linear involution without connections on I. The interval I w , seen as a subinterval of I, is admissible with respect to T .

Proof. Let T be a k-linear involution. Recall that Σ is the set of 2k -2 division points separating the intervals I a for a ∈ A ∪ A -1 . Let λ stand for the left endpoint of the interval I.

For any m ≥ 1, let

P m = {T -i (z) | z ∈ Σ, 0 ≤ i ≤ m -1} ∪ ({λ} × {0, 1}).
Since T is without connections, one has Card(P m ) = (2k -2)m + 2. Consider two points z and z ′ in Î \ Ô that belong to two different intervals of the partition by open intervals of I × {0, 1} made by the points of P m . Then the prefixes of size m of their respective infinite natural codings differ. On the other hand, the left boundary of each I w , |w| = m, is the left boundary of some T -i (I a ) for some 0 ≤ i ≤ m -1 and some a ∈ A ∪ A -1 . This proves that P m is the set of 2(k -1)m + 2 left boundaries of the intervals I w for all words w with |w| = m, and that the family (I w ) |w|=m forms a partition of I × {0, 1} (up to the points of P m ).

Let

I w =]u, v[ and w = a 0 a 1 • • • a n-1
. By construction, there exist a point z ∈ Σ ∪ {λ} and an integer 0 ≤ i ≤ n -1 such that u = T -i (z), where I an =]z, t[ for a certain t ∈ I. For any j with 0 ≤ j ≤ n -2, the point T i (z) is the left boundary of some interval I y , with |y| = m, and thus T k (z) / ∈ I w . The same reasoning applies for the right boundary v of I w .

We now can state our main result concerning return words. Theorem 6.4 Let S be the natural coding of a linear involution without connections on the alphabet A. For any w ∈ S, the set of mixed return words to w is a symmetric basis of the free group F A .

Proof of Theorem 6.4. Let T be a linear involution without connections relative to the alphabet A. By Lemma 4.5, there exist a measured foliation (X, Σ, F , µ) and an admissible interval I ⊂ X such that T is conjugate to the Poincaré map of F on I. Let w be a nonempty word of the natural coding S = L(T ). By Proposition 6.3, the subinterval I w is admissible for the linear involution T . Let x 0 be a point in I w . Recall F A stands for the free group on the alphabet A. We have a natural identification F A → π 1 (X\Σ, x 0 ) given by Lemma 6.1. Since I w is admissible, using Lemma 5.12, the same construction provides an identification of the subgroup Γ(X, I w , x 0 ) generated by the mixed return words and π 1 (X\Σ, x 0 ). This shows that the set of mixed return words is a symmetric basis of F A . Theorem 6.4 thus provides bases of the free group within a given natural coding by taking mixed return words with respect to a given factor w. Example 6.5 The set of MR S (c) in Example 5.11 provides a symmetric basis of the free group, whereas CR S (c) is not a symmetric basis of the free group.

One also deduces the following cardinality result, which is the counterpart for linear involutions of Theorem 3.6 in [START_REF] Berthé | Acyclic, connected and tree sets[END_REF], that holds for tree sets, by noticing that the set of mixed return words MR S (w) has the same cardinality as the set of complete return words CR S (w). Corollary 6.6 Let T be a linear involution without connections relative to the alphabet A. For any w ∈ L(T ), the set of complete return words to {w, w -1 } has 2 Card(A) elements.

Prime words and coverings

We now prove an analogue of Theorem 6.4 for prime words with respect to a subgroup of the free group. This will be Theorem 6.9 below. We will first consider surface coverings that are in correspondence with subgroups of π 1 (X\Σ). From this correspondence, we will obtain a proof of Theorem 6.9.

Let us first quickly recall the Galois correspondence of coverings. Let X be a compact connected surface and Σ a finite set of points. A covering of X of degree d is a compact connected surface Y with a continuous map f : Y → X such that for each x ∈ X\Σ there exists a connected neighborhood U of x such that f

-1 (U ) is a disjoint union of d open sets f -1 (U ) = U 1 ∪ U 2 ∪ . . . ∪ U d such that for each i ∈ {1, . . . , d}, f : U i → U is a homeomorphism.
In our case, we consider more generally a ramified covering with ramifications contained in Σ. For points x ∈ X\Σ we keep the same condition, but for points x ∈ we allow the preimage to be a union of m ≤ d open sets U 1 ∪ U 2 ∪ . . . U m such that f restricted to U i is of the form z → z pi for some p i ≥ 0 from the unit disc in C to itself. One can show that p 1 + p 2 + . . . + p m = d. In other words, the degree is constant if we count multiplicities.

Two coverings f : Y → X and f ′ : Y ′ → X are equivalent if there exists an homeomorphism g :

Y → Y ′ such that f = f ′ • g. If γ is a loop in Y then f (γ) is a loop in X. Hence, for any y 0 ∈ Y we get a map f * : π 1 (Y \f -1 (Σ), y 0 ) → π 1 (X\Σ, f (y 0 )). The map f * is injective and its image is of finite index in π 1 (X\Σ, f (y 0 )).
The following result establishes a Galois correspondence between coverings of finite degree of X ramified over Σ and subgroups of π 1 (X \ Σ). For a proof, see [START_REF] Hatcher | Algebraic topology[END_REF] or [START_REF] Forster | Lectures on Riemann surfaces[END_REF]. Theorem 6.7 Let X be a compact connected surface and let Σ ⊂ X be a finite set. Let Y be a covering of X of degree d. Then, the map (f : Y → X) → f * (π 1 (Y \ f -1 (Σ))) induces a bijection between equivalence classes of coverings of degree d ramified over Σ and conjugacy classes of subgroups of π 1 (X\Σ) of index d. Example 6.8 Let T be the linear involution of Example 4.1. It is without connections and nonorientable, the group of even words is thus a subgroup of index d = 2. The covering of degree 2 of its suspension associated with the group of even words is the orientation covering of the foliation.

One can see on Figure 6.1 that the obtained foliation is orientable. The result is actually a torus and its coding yields Sturmian words. Indeed, one way to obtain the orientation covering is to duplicate the alphabet and to work on (A ∪ A ′ ) ∪ (A ∪ A ′ ) -1 . With each word are associated two lifted words: the first one is obtained by replacing the positive letters by elements of A and negative letters by elements of A ′ , and the second one is obtained by replacing the positive letters by letters of (A ′ ) -1 and the negative ones by elements of A -1 . The language on (A ∪ A ′ ) ∪ (A ∪ A ′ ) -1 that is obtained in this way is orientable. As an illustration, the word c -1 ab -1 c -1 ba -1 c belongs to the natural coding The following statement show a remarkable property of the set of prime words with respect to a subgroup of finite index. Theorem 6.9 Let T be a linear involution relative to the alphabet A without connections and let S = L(T ). For any subgroup G of finite index of the free group F A , the set of prime words in S with respect to G is a symmetric basis of G.

Proof of Theorem 6.9. Let T be a linear involution on I relative to the alphabet A without connections. By Lemma 4.5, there exist a measured foliation (X, Σ, F , µ) and an admissible interval I ⊂ X such that T is conjugate to the Poincaré map of F on I. By Lemma 6.1, there is an identification F A → π 1 (X \ Σ, x 0 ) for any x 0 ∈ I.

Let G be a subgroup of F A of index d. By Theorem 6.7, there is a covering f : X → X of degree d ramified over Σ such that G is identified with π 1 ( X \f -1 (Σ)), i.e., f * (π 1 ( X \ Σ)) = G.

The preimage Ĩ of the interval I in X is made of d copies of I. We can also lift the measured foliation to X and describe the Poincaré map of this measure foliation on I. Indeed, let I = Î × Q where Q is the set of right cosets of G in F A (recall that Î = I × {0, 1}).

For a point x ∈ Î we denote by a(x) the element of A ∪ A -1 such that x ∈ I a(x) . We define T (x, Gw) = (T x, Gwa(x)).

Then T is the Poincaré map of the lift of (F , µ) to X on I. Now, consider the induced map of T on the interval Î × {G} where {G} denotes the set reduced to the coset G. For a point x ∈ Î we denote by ρ(x) the least n ≥ 1 such that T n (x, G) ∈ Î × {G}.

We fix a basepoint x0 in X and for a point x ∈ Î, we denote by γ(x) the loop from x0 to itself which passes by x, T (x), • • • , T ρ(x)-1 (x).

The natural coding of a finite orbit {x, T (x), . . . , T n-1 (x)} is defined as the word Σ

(n) T (x) = a 0 a 1 • • • a n-1 such that T i (x) ∈ I ai for 0 ≤ i < n. Thus it is the prefix of length n of the infinite natural coding Σ T (x) of T relative to x.

It is easy to verify that the map γ(x) → Σ (ρ(x)) T (x) for x ∈ Î is a bijection from Γ( X \ f -1 (Σ), Ĩ, x0 ) onto the set of prime words with respect to G which extends to an isomorphism from π 1 ( X \ Σ) onto G.

By Lemma 6.1, the set Γ(Y \ f -1 (Σ), Ĩ × {G}) is a symmetric basis of G. We thus deduce that the set of prime words with respect to G is a symmetric basis of G. Corollary 6.10 Let T be a linear involution without connections. Let w be a word of its natural coding L(T ). The set of right return words to w is a basis of the even group.

Proof. We assume w.l.o.g. that I w ⊂ I × {0}. We consider the induced map of T on I × {0}. It is an orientable linear involution without connections, that is, an interval exchange with flip(s), with intervals provided by the prime words of the even group that belong to S + , with the notation of Proposition 5.5. Furthermore, in the orientable case, the set of complete return words MR(w) is made of the right return words to w with the left return word to w -1 . The conclusion comes from the fact that prime words of the even group that are in S + are the right return words to w.

We illustrate Theorem 6.9 with the group G of even words of the 3-linear involution of Example 4.1. Recall that the covering of degree 2 of its suspension associated with G is the orientation covering of the foliation (see Example 6.8). the words of Z correspond to the returns to I × {0} while the words of Z -1 correspond to the first returns to I × {1}. Furthermore, one may check directly that the set Z = {a, ba -1 c, bc -1 , b -1 c -1 , b -1 c} is a basis of a subgroup of index 2, in agreement with Theorem 6.9.

Example 3 . 1

 31 Let A = {a, b, c, d} and π = a b a -1 c c -1 d -1 b -1 d .

Figure 3 . 1 :

 31 Figure 3.1: A linear involution. a point z located in the left part of the interval I a . The point σ 1 (z) is located in the right part of I a -1 , and the point T (z) = σ 2 σ 1 (z) is just below on the left of I b -1 . Next, the point σ 1 T (z) is located on the left part of I b and the point T 2 (z) just below.

Example 4 . 1

 41 Let T be the coherent linear involution on I =]0, 1[ represented in Figure 4.1. We choose (3 -√ 5)/2 for the length of the interval I c (or I b ). With this choice, T has no connection.

Figure 4 . 1 :

 41 Figure 4.1: The 3-linear involution of Example 4.1.

  Figure

Figure 4 . 2 :

 42 Figure 4.2:The foliation is made of vertical lines. The cutting sequence following a leaf is given by the iteration of the linear involution T (the notation follows the convention σ 1 (y i ) = x i and σ 2 (y i ) = x i+1 ).

  (a) degree p = -1, angle π (b) degree p = 1, angle 3π (c) degree p = 2, angle 4π

Figure 4 . 3 :

 43 Figure 4.3: Chart around points of Σ.

Remark 4 . 3

 43 The way the Poincaré map of the foliation works explains the notion of mixed return word (see Definition 5.10 below).

  Figure 4.2, one has s = 4, p 1 = p 2 = p 3 = p 4 = -1 and k = 3.

Proof.

  Each set I u is a (possibly empty) open interval. Indeed, this is true if u is a letter. Next, assume that I u is an open interval. Note that I au = I a ∩ T -1 (I u ). Then, for a ∈ A ∪ A -1 , we have T (I au ) = T (I a ) ∩ I u and thus T (I au ) is an open interval. Since I au ⊂ I a , T (I au ) is the image of I au by a continuous map and thus I au is also an open interval.

Figure 5 . 1 :

 51 Figure 5.1: The transforms T ′ and T ′′ of T by Rauzy induction.

Figure 5 . 2 :

 52 Figure 5.2: A uniformly recurrent infinite word factorized as an infinite product • • • rstu • • • of mixed return words to w.

Figure 6 . 1 :Figure 6 . 2 :

 6162 Figure 6.1: The orientation covering of the suspension of Figure 4.2. The choice of letters is made in order that only positive letters or negative letters appear in the coding of an orbit.

Example 6 .

 6 [START_REF] Thierry Coulbois | R-trees and laminations for free groups. I. Algebraic laminations[END_REF] Let T be as in Example 4.1 and let S = L(T ). Let G be the group of even words in F A . It is a subgroup of index 2. The set of prime words with respect to G in S is the setZ ∪ Z -1 with Z = {a, ba -1 c, bc -1 , b -1 c -1 , b -1 c}.Actually, the transformation induced by T on the set I ×{0} (the upper part of Î in Figure4.1) is the interval echange transformation represented in Figure6.3. Its upper intervals are the I z for z ∈ Z. This corresponds to the fact that

Figure 6 . 3 :

 63 Figure 6.3: The transformation induced on the upper level.