Transverse properties of parabolic subgroups of Garside groups
Yago Antolín Luis Paris


ℕ Div 𝒮
ev Gr Geo
ℤ ℱ Å𝒜
diam Min




Let G be a Garside group endowed with the generating set  of non-trivial simple elements, and let H be a parabolic subgroup of G.
We determine a transversal T of H in G such that each θ∈ T is of minimal length in its right-coset, H θ, for the word length with respect to .
We show that there exists a regular language L on ∪^-1 and a bijection : L → T satisfying (U) = _( (U)) for all U ∈ L.
>From this we deduce that the coset growth series of H in G is rational. 
Finally, we show that G has fellow projections on H but does not have bounded projections on H. 


Band-gap engineering in AB(OxS1-x)3  perovskite oxysulfides: A route to strongly polar materials for photocatalytic water splitting
    Ulrich Aschauer
    December 30, 2023
===================================================================================================================================







§ INTRODUCTION


Let S be a finite set. 
A Coxeter matrix over S is defined to be a square matrix M =(m_s,t)_s,t ∈ S indexed by the elements of S, with coefficients in ∪{∞}, such that m_s,s=1 for all s ∈ S, and m_s,t = m_t,s≥ 2 for all s,t ∈ S, s ≠ t.
For each s,t ∈ S, s ≠ t, and each integer m ≥ 2, we set Π(s,t,m) = (st)^m/2 if m is even and Π(s,t,m)= (st)^m-1/2 s if m is odd. 
In other words, Π(s,t,m) denotes the word sts ⋯ of length m.
The Artin group associated with the above Coxeter matrix  M is the group A=A_M defined by the presentation 

    A = A_M = ⟨ S |Π (s,t,m_s,t) = Π(t,s,m_s,t)  for all  s,t ∈ S, s ≠ t  and  m_s,t≠∞⟩ .

The Coxeter group associated with M, denoted by W=W_M, is the quotient of A by the relations s^2=1, s ∈ S.

Artin groups were introduced by Tits <cit.> as extensions of Coxeter groups. 
There are few known results valid for all Artin groups, and most of the work in the subject concerns particular families of them.
The family concerned by the present paper is the one of Artin groups of spherical type, that is, the Artin groups whose associated Coxeter groups are finite. 
Seminal work on these groups are Brieskorn <cit.>, Brieskorn–Saito <cit.> and Deligne <cit.> in relation with the so-called discriminant varieties.
They are involved in several subjects such as singularities, Hecke algebras, hyperplane arrangements, mapping class groups, and there is an extensive literature on them. 
The leading examples of spherical type Artin groups are the braid groups.

Let G be a group and let M be a submonoid of G such that M ∩ M^-1 = {1}.
Then we have two partial orders ≤_L and ≤_R on G defined by α≤_L β if α^-1β∈ M, and α≤_R β if βα^-1∈ M.
For each a ∈ M we set _L(a) = {b ∈ M |  b ≤_L a} and _R(a) = {b ∈ M | b ≤_R a}.
An element a ∈ M is called balanced if _L(a) = _R(a).
In this case we set (a) = _L(a) = _R(a).
On the other hand, we say that M is Noetherian if, for each a ∈ M, there exists an integer n ≥ 1 such that a cannot be decomposed as a product of more than n non-trivial factors.

Let G be a group, let M be a submonoid of G such that M ∩ M^-1 = {1}, and let Δ be a balanced element of M.
We say that G is a Garside group with Garside structure (G,M,Δ) if:


  (a)
M is Noetherian;

  (b)
(Δ) is finite, it generates M as a monoid, and it generates G as a group;

  (c)
(G, ≤_L) is a lattice. 

In this case Δ is called the Garside element and the elements of (Δ) are called the simple elements of G for the given Garside structure. 
The lattice operations of (G,≤_L) are denoted by ∧_L and ∨_L, where for α, β∈ G,

    α∧_L β =max_≤_L(γ∈ G |γ≤_L α and γ≤_L β)

and 

    α∨_L β =min_≤_L(γ∈ G |α≤_L γ and β≤_L γ) .

Remark that if α, β∈ M, then 1≤_L α  and 1 ≤_L β and therefore 1 ≤_L (α∧_L β) ≤_L (α∨_L β) and thus, ∧_L and ∨_L restrict to lattice operations of (M, ≤_L).
On the other hand, the ordered set (G, ≤_R) is also a lattice and its lattice operations are denoted by ∧_R and ∨_R and these operations also restrict to lattice operations of (M, ≤_R).

This definition is due to Dehornoy–Paris <cit.>. 
It is inspired by the work of Garside <cit.>, Epstein et al. <cit.>, Charney <cit.> and others on braid groups and, more generally, on Artin groups of spherical type. 
It isolates certain combinatorial characteristics of the braid groups and of the spherical type Artin groups that suffice to show certain algebraic properties such as the existence of a solution to the conjugacy problem, or the bi-automaticity.  
By Brieskorn–Saito <cit.> and Deligne <cit.>, the Artin groups of spherical type are Garside groups, and a large part of the study of these groups is made now in terms of Garside groups.
We refer to Dehornoy et al. <cit.> for a full account on the theory.

Let A be an Artin group associated with a Coxeter matrix M=(m_s,t)_s,t ∈ S.
The subgroup A_X of A generated by a subset X of S is called a (standard) parabolic subgroup of A.
By van der Lek <cit.> we know that A_X is itself an Artin group, associated with the Coxeter matrix M_X=(m_s,t)_s,t ∈ X.
Parabolic subgroups play a prominent role in the study of Artin groups in general and in that of Artin groups of spherical type in particular.
For example, they are one the main ingredients in the definition/construction of the Salvetti complex for Artin groups, which is one of the most important tools in the study of the K(π,1) conjecture for Artin groups (see for example Godelle–Paris <cit.> and Paris <cit.>) and in the calculation of the cohomology of these groups (see for example De Concini–Salvetti <cit.> and Callegaro–Moroni–Salvetti <cit.>).

The notion of parabolic subgroup was extended to Garside groups by Godelle <cit.> as follows. 
Let (G,M,Δ) be a Garside structure on a Garside group G and let δ be a balanced element in M.
Let G_δ (resp. M_δ) denote the subgroup of G (resp. the submonoid of M) generated by (δ).
Then we say that (G_δ,M_δ,δ) is a parabolic substructure if (δ) = (Δ) ∩ M_δ.
Note that this condition implies that δ∈ (Δ).
In this case we say that G_δ is a parabolic subgroup of G and that M_δ is a parabolic submonoid of M.

In this paper a parabolic subgroup will be always assumed to be non-trivial.


Let A be an Artin group of spherical type, let S be the standard generating set of A, and let X be a subset of S.
Then, by Brieskorn–Saito <cit.>, the subgroup A_X of A generated by X is a parabolic subgroup in Godelle's sense, and all parabolic subgroups of A are of this form.


Let H be a parabolic subgroup of a Garside group G with Garside structure (G, M, Δ). 
Then there is a unique parabolic substructure (G_δ, M_δ, δ) such that H=G_δ.
Indeed, the balanced element δ which defines this parabolic substructure is the greatest element of (Δ)∩ H for the ordering ≤_L, hence H determines δ.
Similarly, if N is a parabolic submonoid of M, then there is a unique parabolic substructure (G_δ, M_δ, δ) such that N=M_δ, where δ is the greatest element of (Δ) ∩ N for the ordering ≤_L.
So, we can speak of a parabolic subgroup and/or of a parabolic submonoid without necessarily mentioning the balanced element δ or the triple (G_δ,M_δ,δ).


The results of the present paper are new for Artin groups of spherical type and even for braid groups and, as often now in the theory, the whole study is done in terms of Garside groups.

Let G be a Garside group with Garside structure (G, M, Δ).
As often in the theory the generating set of G that will be considered in the present paper is the set = (Δ) ∖{1} of non-trivial simple elements. 
For each α∈ G we denote by (α) = _(α) the word length of α with respect to .
Let H be a parabolic subgroup of G.
Recall that a right-coset of H in G is a subset of G of the form H α = {βα|β∈ H}, with  α∈ G.
Recall also that a (right) transversal of H in G is a subset T of G such that C ∩ T is a singleton for every right-coset C of H in G. 
On the other hand, we define the length of a right-coset C of H in G to be (C) = min{(β) |β∈ C}.
In a first step we will determine an explicit transversal T of H in G which satisfies (θ) = (Hθ) for all θ∈ T (see Theorem <ref> and Theorem <ref>).

We denote by : (∪^-1)^* → G the map which sends each word U to the element of G that it represents. 
In a second step we will determine a regular language L over (∪^-1)^* satisfying (L) = T, the restriction : L → T is a bijective correspondence, and (U) = ( (U)) for all U ∈ L (see Theorem <ref>).
The notion of regular language will be recalled in Section <ref>.

For each n ∈ we denote by e(n) = e_G,H,(n) the number of right-cosets of H in G of length n.
The coset growth series of H in G is defined to be the formal series _G,H, (t) = ∑_n=0^∞ e(n) t^n.
By the above e(n) is the number of words of length n in the regular language L.
So, _G,H, (t) is equal to the growth series of L.
As we know that the growth series of a regular language is rational (see Flajolet–Sedgewick <cit.> for example), the formal series _G,H, (t) is rational.

The starting point of this work was the paper <cit.> where the first author studies the triples (G,,H) where G is a group,  a finite generating set of G and H is a subgroup of G such that (G,) has the falsification by fellow traveller property and has fellow projections and/or bounded projections on H. 
These notions will be recalled in Section <ref>.
In particular, it is proved in Antolín <cit.> that, if (G,) has the falsification by fellow traveller property and has fellow projections on H, then the language (H \ G, ) = {U ∈ (∪^-1)^* |(U) = (H  (U)) } is regular. 
It is also proved in Antolín <cit.> that, if (G,) has the falsification by fellow traveller property and has bounded projections on H, then the coset growth series _G,H, (t) is rational. 
Let G be a Garside group, =(Δ)∖{1} and let H be a parabolic subgroup of G.
We know by Holt <cit.> that (G,) has the falsification by fellow traveller property.
So, it is natural to ask whether G has fellow projections and/or bounded projections on H.

In the present paper we show that (G,) has fellow projections but does not have bounded projections on H (if H ≠ G) (see Corollary <ref> and Theorem <ref>).
This is the first known example of a triple (G,,H) where (G,) has the falsification by fellow traveller property, has fellow projections on H, and does not have bounded projections on H. 
On the other hand, note that, by the results of Section <ref>, the coset growth series _G,H, (t) is rational in our case, and we do not know if there exists such an example with a non-rational coset growth series.
Note also that the transversal T defined and studied in Section <ref> is an important tool in the proof of Theorem <ref>.





§ PRELIMINARIES


Let G be a Garside group with Garside structure (G, M, Δ).
Recall that =  (Δ) ∖{1} is the generating system of G that will be considered in the present paper and = _ denotes the word length with respect to . 
The left greedy normal form of an element a ∈ M is defined to be the unique expression a = u_1 u_2 ⋯ u_p of a over  such that u_p ≠ 1 and (u_i ⋯ u_p) ∧_L Δ = u_i for all i ∈{1, …, p}.
We define the right greedy normal form of a in a similar way. 
The following two theorems contain fundamental results on Garside groups.




  (1)
Let a ∈ M, let a = u_1 

u_2 ⋯ u_p be its left greedy normal form and let a=u_q' ⋯ u_2'u_1' be its right greedy normal form.
Then p=q =  (a).

  (2)
Let α∈ G.
There exists a unique pair (a,b) ∈ M × M such that α = b^-1 a and a ∧_L b = 1.
 Similarly, there exists a unique pair (a',b') ∈ M × M such that α = a'b'^-1 and a' ∧_R b'=1.
In this case we have (α) = (a) + (b) = (a') + (b').



The expressions α = b^-1 a and α = a' b'^-1 given in Theorem <ref> (2) are called left orthogonal form of α and right orthogonal form of α, respectively. 
Let α∈ G and let α = b^-1 a be its left orthogonal form.
Let a = u_1 u_2 ⋯ u_p and b = v_1 v_2 ⋯ v_q be the left greedy normal forms of a and b, respectively.
Then the expression α = v_q^-1⋯ v_2^-1 v_1^-1 u_1 u_2 ⋯ u_p is called the left greedy normal form of α.
Note that, by Theorem <ref>, (α) = p+q.
We define the right greedy normal form of an element of G in a similar way.

An element a ∈ M is called unmovable if Δ≰_L a or, equivalently, if Δ≰_R a.
On the other hand, we denote by Φ : G → G, α↦ΔαΔ^-1, the conjugation by Δ.
Note that Φ () = and Φ (M) = M, and therefore Φ preserves ≤_L and ≤_R and thus, it commutes with  ∧_L, ∨_L, ∧_R and ∨_R.


Let α∈ G.
There exists a unique pair (a,k) ∈ M × such that a is unmovable and α = Δ^k a.
Similarly, there exists a unique pair (a',k') ∈ M × such a' is unmovable and α = a' Δ^k', where k'=k and a' = Φ^k(a).


The expressions α = Δ^k a and α = a' Δ^k' given in Theorem <ref> are called the left Δ-form of α and the right Δ-form of α, respectively.
Note that a' Δ^k' = Φ^-k(Δ^k a). 
We denote by σ :  (Δ) → (Δ) the map such that Δ = u σ (u) for all u ∈ (Δ).
Note that σ (Δ) = 1 and σ (1) = Δ.
The following is proved in Picantin <cit.>. 


Let α∈ G and let α = v_q^-1⋯ v_2^-1 v_1^-1 u_1 u_2 ⋯ u_p be its left greedy normal form.


  (1)
Suppose that q=0.
Let r ∈{0,1, …, p} such that u_r = Δ and u_r+1≠Δ.
Set c = u_r+1⋯ u_p.
Then the left Δ-form of α is α = Δ^r c, and the left greedy normal form of c is c = u_r+1⋯ u_p.

  (2)
Suppose that p=0.
Let r ∈{0,1, …, q} such that v_r = Δ and v_r+1≠Δ.
For each i ∈{r+1, …, q} we set w_i = Φ^i (σ (v_i)).
Let c = w_q ⋯ w_r+1.
Then the left Δ-form of α is α = Δ^-q c, and the left greedy normal form of c is c = w_q ⋯ w_r+1.

  (3)
Suppose that p ≥ 1 and q ≥ 1.
For each i ∈{1, …, q} we set w_i = Φ^i (σ (v_i)).
Let c = w_q ⋯ w_1 u_1 ⋯ u_p.
Then the left Δ-form of α is α = Δ^-q c, and the left greedy normal form of c is c = w_q ⋯ w_1 u_1 ⋯ u_p.




Each of the cases of the proposition above  correspond to each of the cases of the corollary below.

Let α∈ G and let α = Δ^p a be its left Δ-form.


  (1)
If p ≥ 0, then (α) = (a) + p.

  (2)
If p ≤ -(a), then (α) = -p.

  (3)
If - (a) ≤ p ≤ 0, then (α) = (a).

Summarizing (α)= max( (a)+p, -p, (a)).


The following theorem contains fundamental results on parabolic subgroups of Garside groups.


Let (H, N, δ) be a parabolic substructure of (G, M, Δ).


  (1)
N= H ∩ M.

  (2)
H is a Garside group with Garside structure (H, N, δ).

  (3)
Let a ∈ N, let a = u_1 u_2 ⋯ u_p be its left greedy normal form, and let a = u_p' ⋯ u_2' u_1' be its right greedy normal form with respect to (G, M, Δ).
Then u_i,u_i' ∈ (δ) for all i ∈{1, …, p}, a = u_1 u_2 ⋯ u_p is the left greedy normal form of a with respect to (H,N, δ), and a = u_p' ⋯ u_2' u_1' is its right greedy normal form with respect to (H, N, δ).

  (4)
Let α, β∈ H and γ∈ G.
If α≤_L γ≤_L β, then γ∈ H.
Similarly, if α≤_R γ≤_R β, then γ∈ H.

  (5)
Let α, β∈ H.
Then α∧_L β, α∨_L β∈ H and α∧_R β , α∨_R β∈ H.

  (6)
Let α∈ H and let α = b^-1 a (resp. α = a' b'^-1)  be its left orthogonal form (resp. be its right orthogonal form) with respect to (G, M, Δ).
Then a,b ∈ N (resp. a',b' ∈ N) and α = b^-1 a (resp. α = a' b'^-1) is the left orthogonal form (resp. the right orthogonal form) of α with respect to (H, N, δ).



The following fact will be used frequently.

Let (H, N, δ) be a parabolic substructure of (G, M, Δ). 
Let a,b∈ M such that ab∈ N, then a,b∈ N. 
Indeed, since ab∈ N, 1≤_L a≤_L ab and by the above a∈ H∩ M=N.
Similarly, b ≤_R ab and 1≤_R b ≤_R ab and therefore b∈ H∩ M=N.






§ TRANSVERSAL


>From now on we fix a Garside group G with Garside structure (G, M, Δ) and a parabolic substructure (H, N, δ).
Our goal in the present section is to define a set T, to show that T is a transversal of H in G, and to show that (θ) =  (H θ) for all θ∈ T.
In order to define the set T we need the following.


Let a ∈ M.
There exists a unique b ∈ N such that { c ∈ N | c ≤_L a } = { c ∈ N | c ≤_L b }.


The element b of Lemma <ref> is called the N-tail of a and is denoted by b = τ_N (a) = τ (a).
We say that a is N-reduced if τ_N (a) = 1.
Note that a is N-reduced if and only if a ∧_L b = 1 for all b ∈ N, or, equivalently, if and only if a ∧_L δ = 1.
On the other hand we set ω = δ^-1Δ∈ M.
This element will play a key role in our study.
Recall that Φ : G → G, α↦ΔαΔ^-1, denotes the conjugation by Δ.
Furthermore, we denote by φ: H → H, β↦δβδ^-1, the conjugation by δ in H.
Note that ω^-1βω = (Φ^-1∘φ)(β) for all β∈ H.
In particular, ω^-1 N ω = Φ^-1 (N) ⊂ M.


































Let α∈ G and let α = a Δ^p be its right Δ-form. 
We say that α is (H,N)-reduced if a is N-reduced and either p=0 or (p<0 and ω≰_L a).
Define T to be the set of (H,N)-reduced elements of G.
The purpose of the present section is to prove the following two theorems.


The set T is a right transversal of H in G.



We have (θ) =  (H θ) for all θ∈ T.


The following three lemmas are preliminaries to the proofs of Theorem <ref> and Theorem <ref>.


Let b ∈ N.
Then b ∧_L ω = 1 and b ∨_L ω = b ω = ω b', where b' = (Φ^-1∘φ) (b).



Let x = b ∧_L ω.
First observe that 1 ≤_L x ≤_L b and hence x∈ N and δ x∈ N ⊆ M.
Since x ≤_L ω, we have δ x ≤_L δω = Δ, hence δ x ∈ (Δ)∩ N = (δ).

As δ x ∈(δ) implies that x^-1∈ N, we obtain that x ∈  N ∩ N^-1 = {1}.
This finish the proof of the first claim.

Now, let y = b ∨_L ω.
As previously observed, b' = (Φ^-1∘φ) (b) = ω^-1 b ω, hence b ω = ω b'.
In particular, b,ω≤_L b ω=ω b' and hence y≤_L bω= ω b'.
Let y_1' ∈ M such that ω y_1' = y.
Since y ≤_L ω b', we have y_1' ≤_L b', hence there exists y_2' ∈ M such that y_1' y_2' = b'.
We have b' ∈Φ^-1 (N) and Φ^-1 (N) is a parabolic submonoid, hence y_1', y_2' ∈Φ^-1(N).
Let y_1 = (φ^-1∘Φ) (y_1') and y_2 = (φ^-1∘Φ)(y_2').
Then y_1, y_2 ∈ N and b = y_1 y_2.
We have b = y_1 y_2 ≤_L y = ω y_1' = y_1 ω, hence y_2 ≤_L ω.
Since y_2 ∈ N and, by the above, y_2 ∧_L ω = 1, it follows that y_2 = 1, hence y_1 = b, and therefore y = b ω.


The following is a direct consequence of Dehornoy–Paris <cit.>.


Let a,b_1,b_2 ∈ M.
Then (b_1 a b_2) ≥ (a).



Let c be a N-reduced element in M, let k ≥ 0 be an integer, and let d = ω_1 ω_2 ⋯ω_k Φ^-k (c), where ω_i = Φ^-i+1 (ω) for all i ∈{1, …, k}.
Then d is N-reduced.



Let k ≥ 0 and let ω_i = Φ^-i+1 (ω) for all i ∈{1, …, k} as in the above statement.
Then ω_1 ⋯ω_k = δ^-kΔ^k.
This equality will be often used in the remainder of the paper.



We argue by induction on k.
The case k = 0 being trivial, we can assume that k ≥ 1 and that the inductive hypothesis holds. 
Note that, if k ≥ 1, then  ω≤_L d.
Let b ∈ N such that b ≤_L d.
In particular, b ∨_L ω≤ d.
By Lemma <ref>, b ∨_L ω = ω  (Φ^-1∘φ)(b) ≤_L ω_1 ω_2 ⋯ω_k  Φ^-k (c), hence (Φ^-1∘φ) (b) ≤_L ω_2 ⋯ω_k  Φ^-k (c), and therefore φ(b) ≤_L ω_1 ⋯ω_k-1 Φ^-k+1 (c). 
Recall that φ(N) = N.
By induction it follows that φ (b) = 1, hence b = 1.





We start by showing that each right-coset C of H in G contains an element of T.
Suppose first that C contains an element a ∈ M.
Let c ∈ M such that a = τ(a) c.
Then c ∈ T and C = Ha = Hc.
Now, we assume that C contains no element of M and note that elements not in M have right Δ-form a Δ^-p with p ≥ 1.
Let α∈ C and let α = a Δ^-p be the right  Δ-form of α.
We choose α so that p is minimal.

Let c ∈ M such that a = τ(a) c.
Set θ = c Δ^-p.
Since C = H α = H θ, it suffices to show that θ∈ T.
The element c is unmovable since c ≤_R a and a is unmovable.
Furthermore, c is N-reduced since a = τ(a) c.
Suppose that ω≤_L c.
Let c' ∈ M such that c = ω c'.
Then δθ = δω c' Δ^-p = Φ(c')  Δ^-p+1∈ H θ = C, which contradicts the minimality of p.
So, ω≰_L c, thus θ = c Δ^-p∈ T.

Now, we take two elements θ_1, θ_2 ∈ T, we suppose that there exists β∈ H such that βθ_1 = θ_2, and we prove that β = 1 and θ_1 = θ_2.
Let θ_1 = c_1 Δ^-p_1 and θ_2 = c_2 Δ^-p_2 be the right Δ-forms of θ_1 and θ_2, respectively. 
By definition, c_i is N-reduced, p_i ≥ 0, and ω≰_L c_i if p_i ≥ 1, for i ∈{ 1, 2}.
We can assume without loss of generality that p_1 ≥ p_2.
Let β = b_2^-1 b_1 be the left orthogonal form of β.
Then b_1 c_1 = b_2 c_2 Δ^p_1-p_2.
Suppose first that p_1-p_2 > 0.
In particular, p_1 > 0, hence ω≰_L c_1.
Since Δ≤_R b_1 c_1 in this case, we have Δ≤_L b_1 c_1, hence ω≤_L b_1 c_1, thus, by Lemma <ref>, ω∨_L b_1 = b_1 ω≤_L b_1 c_1, and therefore ω≤_L c_1: contradiction.
So, p_1 = p_2 and b_1 c_1 = b_2 c_2.
Let y = b_1 ∨_L b_2.
We have y ∈ N, since b_1, b_2 ∈ N and N is a parabolic submonoid.
Let y_1 ∈ M such that y = b_1 y_1.
Here again, y_1 ∈ N, since N is a parabolic submonoid.
We have y = b_1 y_1 ≤_L b_1 c_1, since b_1 c_1 = b_2 c_2, hence y_1 ≤_L c_1.
It follows that y_1 = 1, since c_1 is N-reduced, hence y=b_1.
Similarly, y = b_2, hence b_1 = b_2 = 1, because b_1 ∧_L b_2 = 1.
So, β=1, and θ_1 = θ_2.


Given θ∈ T and β∈ H we will need to understand βθ.
The following three lemmas are the cases for θ∈ T, and β∈ H that will appear in the proofs of Theorems <ref> and <ref>. 


Let c ∈ T∩ M and β∈ H. Let β = b_2^-1 b_1 be the left orthogonal form of β. Then 1= b_2 ∧_L (b_1c) and therefore  b_2^-1 (b_1 c) is the left orthogonal form of βθ.


Recall that b_1, b_2 ∈ N, since H is a parabolic subgroup.
Set y_1 = b_2 ∧_L (b_1 c).
We have y_1 ∈ N since y_1 ≤_L b_2.
Let y_2 = b_1 ∨_L y_1.
We have y_2 ∈ N since y_1, b_1 ∈ N.
Moreover, we have y_2 ≤_L b_1 c since b_1 ≤_L b_1 c and y_1 ≤_L b_1 c. 
Let y_3 ∈ M such that y_2=b_1 y_3.
We have y_3 ∈ N (since y_2 ∈ N), y_3 ≤_L c and c is N-reduced, hence y_3 = 1.
So, y_2= b_1, which implies that y_1 ≤_L b_1.
We also have y_1 ≤_L b_2 and b_1 ∧_L b_2 = 1, hence y_1=1.




Let θ =c Δ^-p∈ T ∖ M in right Δ-form with p≥ 1 and β = b ∈ N.
Then bc is unmovable and bc Δ^-p is the right Δ-form of βθ.


Notice that c is unmovable and N-reduced, ω≰_L c, and p ≥ 1.
If we had Δ≤_L b c, then we would have ω≤_L b c, hence, by Lemma <ref>, we would have b ∨_L ω = b ω≤_L b c, and therefore we would have ω≤_L c: contradiction.
So, b c is unmovable. 



Let θ =c Δ^-p∈ T ∖ M in right Δ-form with p≥ 1 and β = b δ^-k∈ H ∖ N in right δ-form with k≥ 1.
Then the right Δ-form of βθ is bω_1 …ω_kΦ^-k(c)Δ^-k-p, where ω_i = Φ^-i+1 for all i ∈{1, …, k}.


As θ∈ T, c is unmovable and N-reduced, ω≰_L c, and p ≥ 1.
By using the equality δ^-1 = ωΔ^-1 it is easily seen that βθ = b ω_1 ω_2 ⋯ω_k  Φ^-k (c) Δ^-p-k, where ω_i = Φ^-i+1 (ω) for all i ∈{1, …, k}.
By Lemma <ref> we have τ(b ω_1 ⋯ω_k  Φ^-k (c)) = b.
Thus, if Δ≤_L b ω_1 ⋯ω_k  Φ^-k (c), then δ≤_L b ω_1 ⋯ω_k Φ^-k (c), hence  δ≤_L b: contradiction.
So, Δ≰_L b ω_1 ⋯ω_k  Φ^-k (c).




We take θ∈ T and β∈ H and we show that (βθ) ≥ (θ).
Suppose first that θ = c ∈ M.
Let β = b_2^-1 b_1 be the left orthogonal form of β.











Lemma <ref> imples that  b_2^-1 (b_1 c) is the left orthogonal form of βθ.
By applying Theorem <ref> and Lemma <ref> we finally obtain (βθ) =  (b_2) +  (b_1 c) ≥ (c) =  (θ).

Assume that θ∉M and β = b ∈ N.
We write θ in the form θ = c Δ^-p, where c is unmovable and N-reduced, ω≰_L c, and p ≥ 1.


By Lemma <ref> bc is unmovable and bc Δ^-p is the right Δ-form of βθ. 
By Corollary <ref> it follows that (βθ) = max ( (bc), p) ≥max( (c), p) = (θ).

Assume that θ∉M and β∉N.
As before, we write θ in the form θ = c Δ^-p, where c is unmovable and N-reduced, ω≰_L c, and p ≥ 1.
On the other hand we write β in the form β = b δ^-k, where b ∈ N, δ≰_L b, and k ≥ 1.
By Lemma <ref>, the right Δ-form of βθ is  bω_1 ⋯ω_kΦ^-k(c)Δ^-k-p, where ω_i = Φ^-i+1 for all i ∈{1, …, k}.




By Corollary <ref> and Lemma <ref> it follows that (βθ) = max ( (b ω_1 ⋯ω_k  Φ^-k (c)), p+k) ≥max ( (c), p) = ( θ).






§ REGULAR LANGUAGE


A finite state automaton is defined to be a quintuple = (X, Å, μ, Y, x_0), where X is a finite set, called the set of states, Å is a finite set, called the alphabet, μ : X ×Å→ X is a function, called the transition function, Y is a subset of X, called the set of accepted states, and x_0 is an element of X, called the initial state.
For x ∈ X and U = u_1 u_2 ⋯ u_p ∈Å^* we define μ (x, U) ∈ X by induction on p as follows. 

    μ(x, U) =
    {[                          x                  if  p=0 ,; μ (μ (x,u_1 ⋯ u_p-1), u_p)                if  p ≥ 1 . ].

Then the set L_ = { U ∈Å^* |μ (x_0, U) ∈ Y} is called the language recognized by .
A regular language is a language recognized by a finite state automaton. 

Recall that G is a given Garside group with Garside structure (G, M, Δ), that (H, N, δ) is a parabolic substructure, and that T is the transversal of H in G defined in Section <ref>.
The following is used to understand the language defined by the automaton below.
Recall that σ :  (Δ) → (Δ) is the function such that Δ = u  σ(u) for all u ∈ (Δ).


Let u_1, …, u_p, v_1, …, v_q ∈.
Then v_q^-1⋯
v_2^-1 v_1^-1 u_1 u_2 ⋯ u_p is a left greedy normal form if and only if σ(u_i) ∧_L u_i+1 = 1 for all i ∈{1, …, p-1}, σ (v_j) ∧_L v_j+1 = 1 for all j ∈{1, …, q-1}, and u_1 ∧_L v_1 = 1.


We define a finite state automaton = (X, Å, μ, Y, x_0) as follows.
We set Å = ∪^-1, X = Å∪{x_0, x_1}, Y = Å∪{x_0}, and we define μ : X ×Å→ X as follows. 
Let u,v ∈.

    μ(x_0, v) = {[                 v if  v ∧_L δ = 1 ,;               x_1       otherwise , ].μ (x_0, v^-1) ={[              v^-1       if  v = Δ ,;              v^-1 if σ(v) ∧_L δ = 1;                     and ω≰_L σ(v) ,;               x_1       otherwise , ].
    μ(u, v) = {[                   v if σ(u) ∧_L v = 1 ,;                 x_1         otherwise , ].μ (u, v^-1) = x_1 ,
    μ (u^-1, v) = {[                 v if  u ∧_L v = 1 ,;               x_1       otherwise , ].μ (u^-1, v^-1) = {[                v^-1 if σ(v) ∧_L u = 1 ,;                 x_1         otherwise , ].
    μ(x_1 , v) = μ (x_1 , v^-1) = x_1 .


Recall that : Å^* → G is the map that sends each word U to the element of G that it represents. 
The purpose of the present section is to prove the following. 


We have (L_) = T, the restriction : L_→ T is a bijective  correspondence, and (U) =  ( (U)) for all U ∈ L_.


Recall that for each n ∈ we denote by e(n) = e_G,H,(n) the number of right cosets of H in G of length n.
Recall also that the coset growth series of H in G is _G,H, (t) = ∑_n=0^∞ e(n)t^n.
By Theorem <ref>, Theorem <ref> and Theorem <ref> e(n) is equal to the number of words of length n in the regular language L_.
In other words, _G,H,(t) is the growth series of L_.
Since we know that the growth series of a regular language is rational (see Flajolet–Sedgewick <cit.>, for example), it follows that:


The formal series _G,H,(t) is rational.



Set T' =  (L_).
By Theorem <ref> the restriction : L_→ T' is a bijective correspondence, and T' is the set of elements θ = v_q^-1⋯ v_2^-1 v_1^-1 u_1 u_2
⋯ u_p written in left greedy normal form such that:


  * if q = 0 and p ≥ 1, then u_1 ∧_L δ = 1,

  * if q ≥ 1, then either v_q = Δ or (σ(v_q) ∧_L δ = 1 and ω≰_L σ(v_q)).

Moreover, by Theorem <ref>, we have (U) =  ( (U)) for all U ∈ L_.
So, it remains to show that T' = T.

Let θ = v_q^-1⋯ v_2^-1 v_1^-1 u_1 u_2 ⋯ u_p be an element of G written in left greedy normal form.
Suppose first that q = 0.
Then θ = u_1 u_2 ⋯ u_p.
If p = 0, then θ = 1 ∈ T ∩ T'.
So, we can assume that p ≥ 1.
Since δ∈(Δ), we have θ∧_L δ = (θ∧_L Δ) ∧_L δ = u_1 ∧_L δ, hence 

    θ∈ T  ⇔ θ∧_L δ = 1  ⇔ u_1 ∧_L δ = 1  ⇔ θ∈ T' .


Suppose that p = 0 and q ≥ 1.
Then θ = v_q^-1⋯ v_2^-1 v_1^-1.
Let r ∈{0,1, … , q} such that v_i = Δ for all i ∈{1, …, r} and v_r+1≠Δ.
Set w_j = Φ^-j+1 (σ (v_q-j+1)) for j ∈{1, …, q-r} and c=w_1 ⋯ w_q-r.
Then, by Proposition <ref> and Theorem <ref>, θ = c Δ^-q, c is unmovable, and c = w_1 ⋯ w_q-r is the left greedy normal form of c.
Notice that w_1 = σ (v_q).
If v_q = Δ, then c = 1 and θ = Δ^-q∈ T ∩ T'.
So, we can assume that v_q ≠Δ, that is, q > r and c ≠ 1.
As above, since δ∈ (Δ), we have c ∧_L δ = w_1 ∧_L δ  = σ (v_q) ∧_L δ.
On the other hand, since ω∈ (Δ), we have ω≤_L c if and only if ω≤_L w_1 = σ (v_q).
So, 

    θ∈ T  ⇔ (c ∧_L δ = 1  and ω≰_L c)  ⇔ (σ (v_q) ∧_L δ = 1  and ω≰_L σ (v_q))  ⇔ θ∈ T' .


Suppose that p ≥ 1 and q ≥ 1.
Then θ = v_q^-1⋯ v_2^-1 v_1^-1 u_1 u_2 ⋯ u_p.
Since u_1 u_2 ⋯ u_p ∧_L v_1 v_2 ⋯ v_q = 1, we have u_i ≠Δ for all i ∈{1, …, p} and v_j ≠Δ for all j ∈{1, …, q}.
Set w_j = Φ^-j+1 (σ (v_q-j+1)) for all j ∈{1, …, q} and w_j = Φ^-q (u_j-q) for all j ∈{q+1, …, q+p}.
Let c = w_1 ⋯ w_q+p.
Then, by Proposition <ref> and Theorem <ref>, θ = c Δ^-q, c is unmovable, and c = w_1 ⋯ w_q+p is the left greedy normal form of c.
By applying the same reasoning as in the previous case, we then obtain 

    θ∈ T  ⇔ (c ∧_L δ = 1  and ω≰_L c)  ⇔ (σ(v_q) ∧_L δ = 1  and ω≰_L σ(v_q))  ⇔ θ∈ T' .







§ PROJECTIONS


Let G be a group generated by a finite set .
We set Å = ∪^-1 and, as before, we denote by : Å^* → G the map which sends each word U ∈Å^* to the element of G that it represents. 
We denote by = _ the word length in G with respect to  and by d : G × G → the distance function induced by .
Recall that d(α, β) =  (α^-1β) for all α, β∈ G. 
Recall also that, for α∈ G and X ⊂ G, the distance from α to X is d (α, X) = min{d (α, β) |β∈ X }. 
The diameter of a subset X ⊂ G is (X) = max{ d(α, β) |α, β∈ X }.

A word U ∈Å^* is called a geodesic (or a reduced word) if (U) =  ( (U)).
For a word U = x_1 x_2 ⋯ x_ℓ of length ℓ and i ∈ we set U(i) = x_1 ⋯ x_i if i ≤ℓ and U(i) = U if i >ℓ.
Let K be a positive constant.
We say that two words U,V ∈Å^* K-fellow travel if d((U(i)), (V(i))) ≤ K for all i ∈.
We say that (G,) has the falsification by K-fellow traveller property if for each non-geodesic word U ∈Å^* there exists a strictly shorter word V ∈Å^* such that (U) =  (V) and U,V K-fellow travel.

Let H be a subgroup of G.
The projection of an element α∈ G in H is defined to be π_H (α) = {β∈ H | d(α, β) = d(α, H) }.
Let K be a positive constant. 
We say that (G, ) has K-fellow projections on H if, for each α_1, α_2 ∈ G such that d(α_1, α_2) = 1 and each β_1 ∈π_H (α_1), there exists β_2 ∈π_H (α_2) such that d(β_1, β_2) ≤ K.
We say that (G,) has K-bounded projections on H if, for each α_1, α_2 ∈ G such that d(α_1, α_2) = 1, we have (π_H(α_1) ∪π_H (α_2)) ≤ K. 
Note that, if G has K-bounded projections on H, then G has K-fellow projections on H.

As pointed out in the introduction, the starting point of our study was the following two theorems. 


Let G be a group generated by a finite set , let Å = ∪^-1, and let H be a subgroup of G.
Assume that (G,) has the falsification by fellow traveller property and has fellow projections on H.
Then:


  (1)
The language (H \ G, ) = { U ∈Å^* | (U) = (H (U)) } is regular.

  (2)
If, furthermore, (G,) has bounded projections on H, then the coset growth series _G, H, (t) of H in G is rational.




Let G be a Garside group with Garside structure (G, M, Δ), and let =  (Δ) ∖{1}. 
Then G endowed with the generating set  has the falsification by fellow traveller property.


Let G be a Garside group with Garside structure (G, M, Δ) and let (H, N, δ) be a parabolic substructure.
So, it is natural to ask whether (G,) has bounded projections on H and, if not, whether it has fellow projections.
The answer is “NO” for the first question (see Corollary <ref>), and is “YES” for the second question (see Theorem  <ref>).
As pointed out in the introduction, this is the first example we know of a triple (G,,H), where G is a group,  a finite generating set and H is a subgroup of G such that (G,) has the falsification by fellow traveller property, it has fellow projections on H, but it does not have bounded projections on H.

>From now on G denotes a given Garside group with Garside structure (G, M, Δ) and (H, N, δ) denotes a given parabolic substructure. 
Recall that ω = δ^-1Δ, and Φ : G → G, α↦ΔαΔ^-1, denotes the conjugation by Δ.
The fact that G does not have bounded projections on H (if H ≠ G) is a direct consequence of the following. 


Suppose that H ≠ G.
Let k ≥ 1 and let d_k = ω_1 ω_2 ⋯ω_k, where ω_i = Φ^-i+1 (ω) for all i ∈{1, …, k}. 
Then (π_H(d_k)) ≥ k.



By Lemma <ref> the element d_k is N-reduced, hence d_k ∈ T, and therefore, by Theorem <ref>, (H d_k) =  (d_k). 
It follows that d(d_k, H) = (d_k), 1 ∈π_H(d_k), and β∈π_H (d_k) if and only if (β^-1 d_k) = (d_k) and β∈ H.
We have δΔ = Δ σ (ω), hence σ (ω) = Φ^-1 (δ), and therefore σ (ω_i) = Φ^-i (δ) for all i ∈{1, …, k}.
Let i ∈{1, …, k-1 }. 
Then ω_i+1 = Φ^-i (ω) and, by Lemma <ref>, δ∧_L ω = 1, hence σ (ω_i) ∧_L ω_i+1 = Φ^-i (δ) ∧_L Φ^-i (ω) = 1. 
It follows by Theorem <ref> that ω_1 ω_2 ⋯ω_k is the greedy normal form of d_k, hence (d_k) = k.
On the other hand, δ^k d_k = Δ^k, hence, by Corollary <ref>, (Δ^k) = k. 
Since δ^k ∈ H, this shows that δ^-k∈π_H (d_k). 

Finally, by Corollary <ref>, δ^k has length k with respect to (δ) ∖{1 }, hence, by Theorem <ref>, (δ^-k) =  (δ^k) = k.
So, (π_H (d_k)) ≥ k.



Suppose that H ≠ G (and H ≠ 1).
Then G does not have bounded projections on H.



For each k ≥ 1 we choose α_k ∈ G such that d(d_k, α_k) = 1. 
Then, by Lemma <ref>, (π_H (d_k) ∪π_H (α_k)) ≥ (π_H (d_k)) ≥ k, hence there is no K>0 such that (π_H (d_k) ∪π_H (α_k)) ≤ K  for all k ∈.


The rest of the section is dedicated to the proof of the following.


The group G has 5-fellow projections on H with respect to .


The following three lemmas are preliminaries to the proof of Theorem <ref>.
Lemma <ref> is known to experts but to our knowledge is nowhere explicitly written in the literature.


Let a,b ∈ M and let a = u_m ⋯ u_2 u_1 and b = v_n ⋯ v_2 v_1 be the right greedy normal forms of a and b, respectively.
If a ≤_R b, then m ≤ n and for all i ∈{1,…, m}, one has that u_i u_i-1⋯ u_1 ≤_R v_i v_i-1⋯ v_1.



We already know by Theorem <ref> and Lemma <ref> that m =  (a) ≤ (b) = n.
It remains to show that u_i ⋯ u_1 ≤_R v_i ⋯ v_1 for all i ∈{1, …, m}.
We argue by induction on i.
Note that for x, y ∈ M, if x ≤_R y then (x ∧_R Δ) ≤_R (y ∧_R Δ).
Therefore, the case i = 1 is true by definition of a right greedy normal form. 
So, we can assume that i ≥ 2 and that the inductive hypothesis holds.
By induction we have  u_i-1⋯ u_1 ≤_R v_i-1⋯ v_1.
Let c ∈ M such that c u_i-1⋯ u_1 = v_i-1⋯ v_1.
We have u_i ≤_R Δ, u_m ⋯ u_i ≤_R v_n ⋯ v_i+1 v_i c and, by Dehornoy <cit.>, (v_n ⋯ v_i+1 v_i c) ∧_R Δ = (v_i c) ∧_R Δ, hence u_i ≤_R v_i c, and therefore u_i u_i-1⋯ u_1 ≤_R v_i v_i-1⋯ v_1.



Let a be an element of M which can be written in the form a = ω_1 ω_2 ⋯ω_k c, where ω_i = Φ^-i+1 (ω) for all i ∈{1, …, k }, Φ^-k (ω) ≰_L c, and c is Φ^-k (N)-reduced. 
Then (a) = (c) + k.



We argue by induction on k.
The case k = 0 being trivial, we can assume that k ≥ 1 and that the inductive hypothesis holds.
It suffices to show that a ∧_L Δ = ω = ω_1. 
Indeed, in that case, by Theorem <ref>, we have (a) = (ω_2 ⋯ω_k c) + 1. Since Φ(  ) =, Φ preserves , thus (ω_2 ⋯ω_k c) =  (ω_1 ω_2 ⋯ω_k-1Φ(c)) and Φ(c) is Φ^-k+1(N)-reduced. By induction, (ω_2 ⋯ω_k c) = (c) + k -1, hence (a) =  (c) + k. 

Set x = a ∧_L Δ. 
Since ω = ω_1 ≤_L a and ω≤_L Δ, we have ω≤_L x. 
Let x_1 ∈ M such that x = ω x_1. 
We have ω x_1 σ (x) = x σ(x) = Δ = ωδ_1, where δ_1 = Φ^-1 (δ), hence x_1 ≤_L δ_1, thus x_1 ∈Φ^-1(N), since Φ^-1 (N) is a parabolic submonoid of M.
We also have x_1 ≤_L ω_2 ⋯ω_k c and ω_2 ⋯ω_k c is Φ^-1 (N)-reduced by Lemma <ref>, hence x_1 = 1 and x = ω. 



Let α∈ G, ℓ =  (H α) and (α) = {γ∈ H α|(γ) = ℓ}. 
Then ℓ = d (α, H) and we have a bijective map (α) →π_H (α) which sends γ to αγ^-1 for all γ∈ (α).



If β∈ H, then d(β, α) =  (β^-1α) ≥ℓ. 
On the other hand, if γ∈ (α) and β = αγ^-1, then β∈ H and d (β, α) = (β^-1α) =  (γ) = ℓ.
So, ℓ = d(α, H) and β∈π_H(α).
Reciprocally, if β∈π_H(α) and γ = β^-1α∈ H α, then (γ) = d(β, α) = ℓ and γ∈ (α).


The proof of Theorem <ref> is divided into three cases, each case being treated in one of the following three lemmas.


Let α∈ G, β∈π_H (α) and u ∈.
Denote by θ the element of T such that H α = H θ and assume that θ = c ∈ M. 
Then there exists β' ∈π_H(α u) such that d(β, β') ≤ 3.



Set ℓ =  (H α). 
By Theorem <ref>, (θ) = ℓ and c=θ∈ (α).
By Lemma <ref> there exists γ∈ (α) such that β = αγ^-1. 
Let β_1 ∈ H such that β_1 θ = γ. 
Let b_1'^-1 b_1 be the left orthogonal form of β_1. 
By Lemma <ref> we have that b_1' ∧_L (b_1c) = 1.
Thus, by Theorem <ref>, ℓ = (γ) = (b_1') +  (b_1c) and, by Lemma <ref>, (b_1 c) ≥(c).
Since ℓ =  (c ), it follows that b_1' = 1, β_1 = b_1 ∈ N and γ = b_1 c ∈ M.

Set b_2 = τ_N (cu) ∈ N and denote by c' the element of M such that cu = b_2 c'. 
Note that c' is N-reduced, hence c' ∈ T.
Note also that H c' = H α u, hence θ' = c' is the element of T which lies in H α u, and, by Theorem <ref>, (H α u) = (c').
Since c is N-reduced, we have b_2 ∧_L c = 1, hence, by Theorem <ref>, (b_2^-1 c) =  (b_2) + (c).
So, 

    (c) + 1 ≥ (cu) =(b_2c') ≥(c') = (b_2^-1 cu) ≥(b_2^-1 c) -1 = (b_2) + (c) -1 ,

hence (b_2) ≤ 2.
It follows that  

    (c') ≥(b_2 c') - (b_2) ≥(cu) -2 ≥(c)-2 .

Now we show that there exist b_3, b_4 ∈ N such that b_3 b_4 = b_1 b_2, (b_4 c') = (c') and (b_3) ≤ 3.
Set n =  (b_1 b_2 c') and m= (c').
We have  

    n = (b_1 b_2 c') =  (b_1 c u) ≤(b_1 c) + 1 = (c) + 1 ≤(c') + 3 = m+3 .

Let b_1 b_2 c' = v_n ⋯ v_2 v_1 be the right greedy normal form of b_1 b_2 c'.
Then c' ≤_R v_n ⋯ v_2 v_1. 
Set d = v_m ⋯ v_2 v_1. 
Since ( c' )=m, by Lemma <ref> we have c' ≤_R d and, by Theorem <ref>, m =  (d). 
Let b_4 ∈ M such that b_4 c' = d, and let b_3 = v_n ⋯ v_m+1. 
We have b_3 b_4 c' = b_1 b_2 c', hence b_3 b_4 =  b_1 b_2, therefore b_3, b_4 ∈ N since b_1 b_2 ∈ N and N is a parabolic submonoid. 
By the above we also have (b_3) = n-m ≤ 3 and (b_4 c') = (d) = lg(c').

Set γ' = b_4 c' and β' = (α u) γ'^-1.
By the above, γ' ∈ (α u), hence, by Lemma <ref>, β' ∈π_H (α u). 
Moreover, 

    β^-1β' = γ u γ'^-1 = b_1 c u c'^-1 b_4^-1 = b_1 b_2 b_4^-1 = b_3 ,

hence d(β, β') = (b_3) ≤ 3.



Let α∈ G, β∈π_H (α) and u ∈.
Denote by θ the element of T such that H θ = H α and assume that θ∈ M^-1∖{1}.
Then there exists β' ∈π_H (α u) such that d(β, β') ≤ 3.



Let θ = c Δ^-t be the right Δ-form of θ and ℓ =  (θ).
By Theorem <ref>, ℓ =  (H α) and θ∈ (α).
Since θ∈ M^-1 and θ≠ 1, by Proposition <ref> (2), t≥ (c)  and Corollary <ref>, ℓ = t ≥(c) and ℓ≥ 1. 
Moreover, since θ∈ T, the element c is N-reduced and ω≰_L c. 
By Lemma <ref>, there exists γ∈ (α) such that β = αγ^-1. 
Let β_1 ∈ H such that β_1 θ = γ. 
We show that β_1 = b_1 ∈ N. 
Suppose instead that β_1 ∉N.
Then β_1 is written β_1 = b_1 δ^-k where k ≥ 1 and δ≰_L b_1. 
By Lemma <ref>, the right Δ-form of γ is γ = b_1 ω_1 ω_2 ⋯ω_k Φ^-k(c) Δ^-k -ℓ, where ω_i = Φ^-i+1 (ω). 
By Corollary <ref> and Lemma <ref> it follows that  

    ℓ = (γ) = max ( (b_1 ω_1 ω_2 ⋯ω_k Φ^-k(c)), k+ ℓ)
    ≥ k + ℓ > ℓ :

contradiction.
So, β_1 = b_1 ∈ N and γ = (b_1 c) Δ^- ℓ.
By Lemma <ref>, b_1 c is unmovable, hence γ = (b_1 c)Δ^- ℓ is the right Δ-form of γ and, by Corollary <ref>, ℓ = (γ) = max( (b_1c), ℓ).
Thus, (c) ≤(b_1 c) ≤ℓ.

We have θ u = c Δ^- ℓ u = c u_1 Δ^-ℓ, where u_1 = Φ^-ℓ(u) ∈.
Let b_2 = τ (c u_1) ∈ N and let c_1 ∈ M such that c u_1 = b_2 c_1.
We write c_1 in the form c_1 = ω_1 ω_2 ⋯ω_p c_2, where ω_i = Φ^-i+1 (ω) for all i ∈{1, …, p}, and Φ^-p (ω) ≰_L c_2.
We show that p ≤ 1.
Assume instead that p ≥ 2.
Let u_1' ∈ (Δ) such that u_1' u_1 = Δ.
Recall that φ : H → H denotes the conjugation by δ in H.
Then 

    ω_1 ω_2 ≤_L c_1  ⇒  
    b_2 ω_1 ω_2 ≤_L b_2 c_1 = c u_1  ⇒δ^2 b_2 ω_1 ω_2 = φ^2(b_2) Δ^2 ≤_L δ^2 c u_1 .

Observe that for x∈ M one has that Δ^i≤_L x Δ^i and Δ^i ≤_R Δ^i x. We have that

    ω_1 ω_2 ≤_L c_1  ⇒Δ^2 ≤_L δ^2 c u_1  ⇒Δ^2 ≤_R  δ^2 c u_1  ⇒ Δ u_1' ≤_R δ^2 c  ⇒Δ≤_R δ^2 c  ⇒
    Δ≤_L δ^2 c  ⇒ω≤_L δ^2 c  ⇒ω∧_L δ^2 = δ^2 ω≤_L δ^2 c  ⇒ω≤_L c :

contradiction.
So, p ≤ 1.

Let b_1' = ω_p^-1⋯ω_1^-1 b_1 ω_1 ⋯ω_p ∈Φ^-p(N) and b_2' = ω_p^-1⋯ω_1^-1 b_2 ω_1 ⋯ω_p ∈Φ^-p(N).
Then b_1 c u_1 = b_1 b_2 c_1 = b_1 b_2 ω_1 ⋯ω_p c_2 = ω_1 ⋯ω_p b_1' b_2' c_2.
We show that there exist b_3', b_4' ∈Φ^-p(N) such that b_3' b_4' = b_1' b_2', (b_4' c_2) ≤max(ℓ-p,  (c_2)) and (b_3') ≤ 2.
Set  n =  (b_1' b_2' c_2) and m = max (ℓ-p,  (c_2)).
We have  

    (c_2) ≤ (b_2 ω_1 ⋯ω_p c_2) =  (c u_1) ≤ (c) + 1 ≤ℓ +1 ≤ℓ - p + 2 ,
 
hence ℓ - p ≤ m ≤ℓ - p + 2.
So, 

    n - m ≤ n - ℓ + p ≤ n - ℓ + 1 ≤( ω_1 ⋯ω_p b_1' b_2' c_2) - ℓ + 1
    
    =  (b_1 b_2 ω_1 ⋯ω_p c_2) - ℓ + 1
    =  (b_1 c u_1) - ℓ + 1 ≤ (b_1 c) - ℓ + 2 ≤ 2 .

Let b_1' b_2' c_2 = v_n ⋯ v_2 v_1 be the right greedy normal form of b_1' b_2' c_2.
Suppose first that m ≥ n.
Set b_3' = 1 and b_4' = b_1' b_2'.
Then (b_4' c_2) =  (b_1' b_2' c_2) = n ≤ m = max(ℓ - p, (c_2)) and (b_3') = 0 ≤ 2.
Suppose now that m < n.
Let d = v_m ⋯ v_2 v_1.
Since ( c_2) ≤ m, by Lemma <ref> we have that  c_2 ≤_R d.
Let b_4' ∈ M such that b_4' c_2 = d, and let b_3' = v_n ⋯ v_m+1.
Then (b_3') ≤ n-m ≤ 2, (b_4' c_2) ≤ m = max(ℓ - p,  (c_2)), b_3' b_4' = b_1' b_2', since b_3'b_4' c_2 =
b_1' b_2' c_2, and b_3', b_4' ∈Φ^-p(N), since b_3' b_4' = b_1' b_2' ∈Φ^-p(N) and Φ^-p(N) is a parabolic submonoid.

Let c' = Φ^p (c_2) and θ' = c' Δ^-ℓ + p.
We have Φ^-p (ω) ≰_L c_2, hence ω≰_L c'.
Since ω≤_L Δ, this also implies that Δ≰_L c', that is, c' is unmovable. 
Let b' ∈Φ^-p (N).
Set b = ω_1 ⋯ω_p b' ω_p^-1⋯ω_1^-1∈ N.
If b' ≤_L c_2, then ω_1 ⋯ω_p b' = b ω_1 ⋯ω_p ≤_L ω_1 ⋯ω_p c_2 = c_1, hence  b ≤_L c_1.
Since c_1 is N-reduced, it follows that b = 1, hence b' = 1.
This shows that c_2 is Φ^-p (N)-reduced, hence c' is N-reduced. 
Finally, since ℓ≥ 1 and p ≤ 1, we have ℓ - p ≥ 0.
So, θ' ∈ T.
On the other hand,

    α u = 
    βγ u = 
    β b_1 c Δ^-ℓ u = 
    β b_1 c u_1 Δ^-ℓ = 
    β b_1 b_2 ω_1 ⋯ω_p c_2 Δ^-ℓ
     = 
    β b_1 b_2 δ^-pΔ^p c_2 Δ^-ℓ = 
    β b_1 b_2 δ^-p c' Δ^-ℓ + p = 
    β b_1 b_2 δ^-pθ' ,

hence θ' is the element of T which lies in H α u.

Set b_3 = Φ^p (b_3') and b_4 = Φ^p (b_4').
Then b_3, b_4 ∈ N,  (b_3) ≤ 2, and (b_4 c') =  (b_4' c_2) ≤max (ℓ-p,  (c_2))  = max (ℓ-p, (c')) =  (θ').
Let γ' = (b_4 c') Δ^-ℓ+p = b_4 θ'.
If we had Δ≤_L b_4 c', then we would have ω≤_L b_4 c', hence we would have ω∨_L b_4 = b_4 ω≤_L b_4 c', and therefore ω≤_L c': contradiction.
So, b_4 c' is unmovable, hence (b_4 c') Δ^-ℓ+p is the right Δ-form of γ'.
By Corollary <ref> and the above it follows that (γ') = max ( (b_4 c'),ℓ-p) = max ((c'), ℓ-p) =  (θ'), hence, since θ' ∈ (α u), we have γ' ∈ (α u).
Let β' =  α u γ'^-1.
We have β' ∈π_H (α u) by Lemma <ref>.
Moreover, 

    β^-1β' 
    = γ u γ'^-1
    = b_1 c Δ^-ℓ u Δ^ℓ-p c'^-1 b_4^-1 
    = b_1 b_2 c_1 Δ^-p c'^-1 b_4^-1
    
    = b_1 b_2 ω_1  ⋯ω_p c_2 Δ^-p c'^-1 b_4^-1
    = ω_1 ⋯ω_p b_1' b_2' c_2 Δ^-p c'^-1 b_4^-1
    
    = δ^-pΔ^p b_3' b_4' c_2 Δ^-p c'^-1 b_4^-1 
    = δ^-p b_3 .

So, d(β, β') =  (δ^-p b_3) ≤ p +  (b_3) ≤ 3.



Let α∈ G, β∈π_H (α) and u ∈.
Denote by θ the element of T such that H θ = H α and assume that θ∉M ∪ M^-1.
Then there exists β' ∈π_H (α u) such that d(β, β') ≤ 5.



Let θ = c Δ^-ℓ be the right Δ-form of θ.
Since θ∉M ∪ M^-1, by Proposition <ref> and Corollary <ref>, we have 1 ≤ℓ <  (c) and (θ) = (c).
Furthermore, by Theorem <ref>, (H α) = (θ) and so θ∈ (α).
Moreover, since θ∈ T, the element c is N-reduced and ω≰_L c.
By Lemma <ref> there exists γ∈ (α) such that β = αγ^-1.
Let β_1 ∈ H such that β_1 θ = γ.
We show that β_1 = b_1 ∈ N.
Suppose instead that β_1 ∉N.
Then β_1 is written β_1 = b_1 δ^-k where k ≥ 1, b_1 ∈ N, and δ≰_L b_1.
By Lemma <ref>, the right Δ-form of γ is γ = b_1 ω_1 ω_2 ⋯ω_k Φ^-k(c) Δ^-k-ℓ, where ω_i = Φ^-i+1 (ω).
Then, by Corollary <ref> and Lemma <ref>, (γ) = max ( (b_1 ω_1 ⋯ω_k Φ^-k (c)), k+ ℓ) ≥max ( (ω_1 ⋯ω_k Φ^-k (c)), k+ ℓ) = max ( (c) + k, k + ℓ) >  (c) =  (θ): contradiction.
So, β_1 = b_1 ∈ N and γ = (b_1 c) Δ^-ℓ.
By Lemma <ref>, b_1 c is unmovable, hence γ = (b_1 c) Δ^-ℓ is the right Δ-form of γ.
By Corollary <ref>, (c) =  (θ) =  (γ) = max ( (b_1 c),ℓ) ≥ (b_1 c) and, by Lemma <ref>, (b_1 c) ≥ (c), hence (c) =  (b_1 c).

We have θ u = c Δ^-ℓ u = c u_1 Δ^-ℓ, where u_1 = Φ^-ℓ(u) ∈.
Let b_2 = τ (c u_1) ∈ N and let c_1 ∈ M such that c u_1 = b_2 c_1.
Since c is N-reduced, we have b_2 ∧_L c = 1, hence, by Theorem <ref>, (b_2^-1 c) =  (b_2) +  (c).
It follows that 

    (c) + 1 ≥ (c u_1) =  (b_2 c_1) ≥(c_1) =  (b_2^-1 c u_1)
    ≥ (b_2^-1 c) - 1 =  (b_2) + (c) -1 ,

hence (b_2) ≤ 2.

We write c_1 in the form c_1 = ω_1 ω_2 ⋯ω_p c_2, where ω_i = Φ^-i+1 (ω) for all i ∈{1, …, p}, and Φ^-p (ω) ≰_L c_2.
We show that p ≤ 1 in the same way as in the proof of Lemma <ref>.
Moreover, by the above,

    (c_2) ≥ (b_2 ω_1 ⋯ω_p c_2) -  (b_2) -  (ω_1 ⋯ω_p) ≥ (c u_1) -3 ≥ (c) -3 .


Let b_1' = ω_p^-1⋯ω_1^-1 b_1 ω_1 ⋯ω_p ∈Φ^-p (N) and b_2' = ω_p^-1⋯ω_1^-1 b_2 ω_1 ⋯ω_p ∈Φ^-p (N).
Then b_1 c u_1 = b_1 b_2 c_1 = b_1 b_2 ω_1 ⋯ω_p c_2 = ω_1 ⋯ω_p b_1' b_2' c_2.
We show now that there exist b_3', b_4' ∈Φ^-p (N) such that b_3' b_4' = b_1' b_2', (b_4' c_2) =  (c_2) and (b_3') ≤ 4.
Set n =  (b_1' b_2' c_2) and m =  (c_2).
We have n ≥ m by Lemma <ref> and, by the above, 

    n =  (b_1' b_2' c_2) ≤ (ω_1 ⋯ω_p b_1' b_2' c_2) =  (b_1 c u_1) ≤ (b_1 c) + 1
    
     = (c) + 1 ≤ (c_2)+4 = m+4 .

Let b_1' b_2' c_2 = v_n ⋯ v_2 v_1 be the right greedy normal form of b_1' b_2' c_2.
Set d = v_m ⋯ v_2 v_1.
By Lemma <ref> we have c_2 ≤_R d.
Let b_4' ∈ M such that b_4' c_2 = d and let b_3' = v_n ⋯ v_m+1.
We have b_3' b_4' c_2 = b_1' b_2' c_2, hence b_3' b_4' = b_1' b_2'.
In particular, b_3', b_4' ∈Φ^-p(N), since b_1' b_2' ∈Φ^-p (N) and Φ^-p (N) is a parabolic submonoid.
Furthermore, by the above, (b_3') = n-m ≤ 4 and (b_4' c_2) =  (d) = m = (c_2).

Let c' = Φ^p (c_2) and let θ' = c' Δ^-ℓ+p.
We show in the same way as in the proof of Lemma <ref> that θ' = c' Δ^-ℓ+p is the right Δ-form of θ', that ω≰_L c', that θ' ∈ T, and that θ' ∈ H α u.
Set b_3 = Φ^p (b_3') and b_4 = Φ^p(b_4').
Then b_3, b_4 ∈ N, (b_3) ≤ 4, and (b_4 c') =  (b_4' c_2) =  (c_2) =  (c').
Let γ' = (b_4 c') Δ^-ℓ+p = b_4 θ'.
If we had Δ≤_L b_4 c', then we would have ω≤_L b_4 c', hence we would have ω∨_L b_4 = b_4 ω≤_L b_4 c', and therefore ω≤_L c': contradiction.
So, b_4 c' is unmovable, hence (b_4 c') Δ^-ℓ+p is the right Δ-form of γ'.
By Corollary <ref> and the above it follows that (γ') = max ( (b_4 c'), ℓ-p) = max ( (c'), ℓ-p) =
 (θ').
So, since θ' ∈ (α u), we have γ' ∈ (α u).
Let β' = α u γ'^-1.
We have β' ∈π_H (α u) by Lemma <ref>.
Furthermore, 

    β^-1β' = γ u γ'^-1
    = b_1 c Δ^-ℓ u Δ^ℓ-p c'^-1 b_4^-1 
    = b_1 b_2 ω_1 ⋯ω_p c_2 Δ^-p c'^-1 b_4^-1
    
    = ω_1 ⋯ω_p b_1' b_2' c_2 Δ^-p c'^-1 b_4^-1
    = δ^-pΔ^p b_3' b_4' c_2 Δ^-p c'^-1 b_4^-1 
    = δ^-p b_3 .

Thus, d(β,β') = (δ^-p b_3) ≤ p +  (b_3) ≤ 5.



Follows directly from Lemma <ref>, Lemma <ref> and Lemma <ref>.





 §.§ Acknowledgments

The first author acknowledges partial
support from the Spanish Government through grant number MTM2017-82690-P and through the ”Severo Ochoa Programme for Centres of Excellence in R&D” (SEV–2015–0554)


Antol1
Y Antolín,
Counting subgraphs in fftp graphs with symmetry,
preprint, arXiv:1802.05213.

Bries1
E Brieskorn,
Die Fundamentalgruppe des Raumes der regulären Orbits einer endlichen komplexen Spiegelungsgruppe,
Invent. Math. 12 (1971), 57–61.

Bries2
E Brieskorn,
Sur les groupes de tresses [d'après V. I. Arnol'd], 
Séminaire Bourbaki, 24éme année (1971/1972), Exp. No. 401, pp. 21–44. Lecture Notes in Math., Vol. 317, Springer, Berlin, 1973.

BriSai1
E Brieskorn, K Saito,
Artin-Gruppen und Coxeter-Gruppen,
Invent. Math. 17 (1972), 245–271.

CaMoSa1
F Callegaro, D Moroni, M Salvetti,
Cohomology of affine Artin groups and applications,
Trans. Amer. Math. Soc. 360 (2008), no. 8, 4169–4188. 

Charn1
R Charney,
Artin groups of finite type are biautomatic,
Math. Ann. 292 (1992), no. 4, 671–683.

Charn2
R Charney,
Geodesic automation and growth functions for Artin groups of finite type,
Math. Ann. 301 (1995), no. 2, 307–324.

DeCSal1
C De Concini, M Salvetti,
Cohomology of Coxeter groups and Artin groups,
Math. Res. Lett. 7 (2000), no. 2-3, 213–232. 

Dehor1
P Dehornoy,
Groupes de Garside,
Ann. Sci. École Norm. Sup. (4) 35 (2002), no. 2, 267–306.

Dehor2
P Dehornoy,
Alternating normal forms for braids and locally Garside monoids,
J. Pure Appl. Algebra 212 (2008), no. 11, 2413–2439. 

DehEtAl
P Dehornoy, F Digne, E Godelle, D Krammer, J Michel,
Foundations of Garside theory,
EMS Tracts in Mathematics, 22, European Mathematical Society (EMS), Zürich, 2015.

DehPar1
P Dehornoy, L Paris,
Gaussian groups and Garside groups, two generalisations of Artin groups,
Proc. London Math. Soc. (3) 79 (1999), no. 3, 569–604. 

Delig1
P Deligne,
Les immeubles des groupes de tresses généralisés, 
Invent. Math. 17 (1972), 273–302. 

Epste1
D B A Epstein, J W Cannon, D F Holt, S V F Levy, M S Paterson, W P Thurston,
Word processing in groups,
Jones and Bartlett Publishers, Boston, MA, 1992.

FlaSed1
P Flajolet, R Sedgewick,
Analytic combinatorics,
Cambridge University Press, Cambridge, 2009.

Garsi1
F A Garside,
The braid group and other groups,
Quart. J. Math. Oxford Ser. (2) 20 (1969), 235–254.

Godel1
E Godelle,
Parabolic subgroups of Garside groups,
J. Algebra 317 (2007), no. 1, 1–16.

Godel2
E Godelle,
Parabolic subgroups of Garside groups II: ribbons,
J. Pure Appl. Algebra 214 (2010), no. 11, 2044–2062. 

GodPar1
E Godelle, L Paris,
K(π,1) and word problems for infinite type Artin-Tits groups, and applications to virtual braid groups,
Math. Z. 272 (2012), no. 3-4, 1339–1364.

Holt1
D F Holt,
Garside groups have the falsification by fellow-traveller property,
Groups Geom. Dyn. 4 (2010), no. 4, 777–784. 

Lek1
H Van der Lek,
The homotopy type of complex hyperplane complements,
Ph. D. Thesis, Nijmegen, 1983.

Paris1
L Paris,
K (π,1) conjecture for Artin groups,
Ann. Fac. Sci. Toulouse Math. (6) 23 (2014), no. 2, 361–415. 

Pican1
M Picantin,
The conjugacy problem in small Gaussian groups,
Comm. Algebra 29 (2001), no. 3, 1021–1039. 

Tits1
J Tits,
Normalisateurs de tores. I. Groupes de Coxeter étendus,
J. Algebra 4 (1966), 96–116.





