Jean-Baptiste Boyer

On the affine random walk on the torus

ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction and main results

Let d ∈ N, d 2 and T d := R d /Z d be the torus of dimension d. Let µ be a borelian probability measure on G := SL d (Z) ⋉ T d . Define, for any x ∈ T d , a random walk starting at x by denoting, for any n ∈ N,

X 0 = x X n+1 = a n+1 X n + b n+1
where ((a n , b n )) ∈ G N is an iid sequence of law µ.

Then, we denote by P x the measure on X N that is the image of the measure µ ⊗N on G N by the map ((g n ) → (x, g 1 x, g 2 g 1 x, . . . , g n . . . g 1 x, . . . )) and by E x the operator of integration against the measure P x .

We denote by P the Markov operator associated to µ. This is the operator defined for any borelian non-negative function f on T d and any x ∈ T d by

P f (x) = G f (gx)dµ(g)
Thus, for any n ∈ N, we have that

P n f (x) = G f (gx)dµ * n (g) = T d f (y)dµ * n * δ x (y) = (T d ) N f (X n )dP x ((X n )) = E x f (X n )
Where we noted µ * n the n-th power of convolution of the measure µ (µ * 0 is by convention the Dirac measure at (I d , 0)).

Bourgain, Furmann, Lindenstrauss and Mozes studied in [BFLM11] the case where µ is concentrated on SL d (Z)⋉{0} and they proved that, under assumptions on the support of µ, the only P -invariant probability measures on the torus where the Lebesgue's measure ν and the uniform measures on unions of rational orbits (which are finite). their result is even more precise since they give the rate of convergence of E x f (X n ) to f dν in terms of diophantine properties of x and this allowed us to study the sequence (f (X n )) for starting points x that are not too well approximable by rational points in [START_REF] Boyer | Central limit theorem and law of the iterated logarithm for the linear random walk on the torus[END_REF].

In this article, we are interested in the case where µ is not concentrated on SL d (Z) ⋉ Q d /Z d . A result by Benoist-Quint (see [BQ11]) shows that in this case, under assumptions on the projection on SL d (Z) of the subgroup spanned by the support of µ, the only P -invariant probability measure on the torus is Lebesgue's measures and this proves that for any continuous function f on T d and any x ∈ T d ,

1 n n-1 k=0 f (X k ) -→ f dν P x -a.e.
The aim of this article is to precise the previous convergence by proving a Central Limit Theorem, a Law of the Iterated Logarithm, etc.

To do so, we are going to make a few assumptions on the subgroup spanned by {a|(a, b) ∈ supp µ}.

In the sequel, we will say that a closed subgroup H of SL d (R) is strongly irreducible if it doesn't fix any finite union of non-trivial subspaces of R d . Moreover, we will say that H is proximal if it contains an element g such that there is v + g ∈ R d \ {0}, λ ∈ R and a g-invariant hyperplane V < g in R d such that R d = Rv + g ⊕ V < g , gv + g = λv + g and the spectral radius of g in V < g is strictly smaller that |λ|. Finally, we will say that a probability measure µ on SL d (R) is strongly irreducible and proximal if the closure of the subgroup spanned by the support of µ has these properties.

These two assumptions are actually assumptions on the Zariski-closure of H and so, as an example, they are satisfied if H is Zariski-dense in SL d (R).

Finally, we will say that a measure µ on SL d (R) has an exponential moment if there is some ε ∈ R * + such that

SL d (R)
g ε dµ(g) < +∞

We will see in the sequel that our study of the random walk on the torus requires arguments of orbit closures. This is why we give a name to the property that we will use and we will see right after examples of measures satisfying it.

Definition 1.1. Let µ be a borelian probability measure on G.

We say that µ satisfies an effective shadowing lemma if for any C ′ , t ′ ∈ R * + , there are C 1 , C 2 , M, t, L ∈ R * + such that for any x, y ∈ T d , any r ∈ R * + and any n ∈ N, with r C 1 e -Ln , if µ * n ({g ∈ G|d(gx, y) r}) C 2 e -tn then, there are x ′ , y ′ ∈ T d such that d(x, x ′ ), d(y, y ′ ) re M n and

µ * n g ∈ G gx ′ = y ′ C ′ e -t ′ n
Remark 1.2. For a measure to satisfy this property means that if a lot of elements g ∈ supp µ * n send x close to y, it is only because x and y are close to points of the same orbit. The name comes from the theory of hyperbolic diffeomorphisms since when µ = δ g 0 , saying that µ satisfies an effective shadowing lemma means that there is some constant M such that for any large enough K, any n ∈ N and any x, y ∈ T d with d(g n 0 x, y) e -Kn , there are x ′ , y ′ ∈ T d such that d(x, x ′ ), d(y, y ′ ) e -(K-M )n and g n 0 x ′ = y ′ . Example 1.3. This is a technical definition but we will see in section 4 a criterion (the proposition 4.7) that allows to tell if a measure satisfies to an effective shadowing lemma and we will deduice examples from it.

In particular, we will see in example 4.4 that if b 0 ∈ T 1 is such that there are C, L ∈ R * + such that for any q ∈ N * , d(qb 0 , 0) C q L , then, any borelian probability measure µ on G whose projection on SL d (Z) is strongly irreducible, proximal and has an exponential moment and such that F (µ) := {coefficients of b|(a, b) ∈ supp µ} ⊂ {0, b 0 } satisfies an effective shadowing lemma.

Moreover, in example 4.6 we will prove that if a 1 , . . . , a N ∈ SL d (Z) generate a strongly irreducible and proximal group, then for a.e. b 1 , . . . , b N ∈ T d , the measure µ = 1 N N i=1 δ (a i ,b i ) satisfies an effective shadowing lemma.

For α ∈]0, 1], we denote by C 0,α (T d ) the space of α-hölder-continuous functions f on T d endowed with the norm

f α := f ∞ + m α (f )
where

f ∞ := sup x |f (x)| and m α (f ) := sup x =y |f (x) -f (y)| d(x, y) α
where d is the distance induced by some norm on R d . Moreover, for any two borelian probability measures ϑ 1 , ϑ 2 on T d , we denote by W α (ϑ 1 , ϑ 2 ) the Kantorovich-Rubinstein's distance of ϑ 1 and ϑ 2 and this is defined by

W α (ϑ 1 , ϑ 2 ) := sup f ∈C 0,α (T d ) f α 1 f dϑ 1 -f dϑ 2
This will allow us to prove the Theorem 1.4. Let µ be a borelian probability measure on

G := SL d (Z) ⋉ T d that is not concentrated on SL d (Z) ⋉ Q d /Z d
and satisfies an effective shadowing lemma. Note µ 0 the projection of µ on SL d (Z) and assume that µ 0 is strongly irreducible, proximal and has an exponential moment. Denote by P the Markov operator associated to µ.

Then, the Lebesgue's measure ν on T d is the only P -invariant borelian probability measure on the torus. Moreover, for any α ∈ ]0, 1], there are C, t ∈ R * + such that for any f ∈ C 0,α (T d ) and any n ∈ N,

sup x∈T d W α (µ * n * δ x , ν) Ce -tn f α
In particular, for any α-hölder-continuous function f on the torus, there is a continuous function g such that f -f dν = g -P g and g ∞ C f α Remark 1.5. We don't know if the function g that we construct in this theorem is höldercontinuous. This theorem will allow us to prove a few of the classical results in probability theory for the sequence (f (X n )) in the Theorem 1.6. Under the same assumptions than in theorem 1.4.

Denote, for any continuous function f on the torus, f = f -f dν and, for any sequence

x = (X n ) ∈ (T d ) N , S n f (x) = n-1 k=0 f (X k ) = n-1 k=0 f (X k ) -n f dν Moreover, for any t ∈ [0, 1], set ξ n (t) = 1 √ n S i f (x) + n t - i n f (X i ) for i n t i + 1 n and 0 i n -1
Then, for any continuous function f on the torus and any x ∈ T d ,

S n f (x) n -→ 0 P x -a.e.
Moreover, for any α ∈]0, 1] there is t ∈ R * + such that for any ε ∈]0, 1] there is a constant C such that for any α-hölder-continuous function f on the torus, any x ∈ T d and any n ∈ N,

P x x ∈ X N |S n f (x)| > nε f α Ce -tε 2 n
Finally, set

σ 2 (f ) := T d g 2 -(P g) 2 dν
and then, (1) If σ 2 (f ) = 0 then for any bounded continuous

F : C 0 ([0, 1]) → R and any x ∈ T d , E x F (ξ n ) -→ EF (W σ 2 ) and 1 ln n n k=1 1 k F (ξ k ) -→ EF (W σ 2 ) P x -a.e.
Where W σ 2 denotes Wiener's measure of variance σ 2 . And for any continuous function ϕ on R such that t 2 ϕ(t) is bounded and for any x ∈ T d ,

1 ln n n k=1 1 k ϕ S k f (x) √ k -→ Eϕ(W σ 2 (1)) P x -a.e.
(2) If σ 2 (f ) = 0 then for any x ∈ T d and any n ∈ N, S n f ∈ L ∞ (P x ) and

S n f L ∞ (Px) 2C f α
Remark 1.7. The two convergences of (F (ξ n )) in point (1) are respectively called functional central limit theorem (FCLT) and almost-sure functional central limit theorem (ASFCLT). There is no obvious link between the convergence in law of (F (ξ n )) and the a.e. convergence of it's logarithmic average (see [START_REF] Berkes | A universal result in almost sure central limit theory[END_REF] for a criterion). However, note that we have to take a logarithmic mean because of the arc sine law.

Remark 1.8. The FCLT and the ASFCLT have many corollaries such as the cental limit theorem and the almost sure central limit theorem (taking F ϕ (ξ) = ϕ(ξ(1)) for any continuous and bounded function ϕ on R), the law of the iterated logarithm (see theorem 2.4 in [START_REF] Chaabane | Version forte du théorème de la limite centrale fonctionnel pour les martingales[END_REF]), a control of

max k∈[0,n] S k f (x) √ n (taking F (ξ) := sup t∈[0,1] ξ(t)), or an estimation of σ 2 (f ) (taking ϕ(x) = x 2 ).
Before we continue, we give an example where there is a non-constant function f such that σ 2 (f ) = 0.

Example 1.9. Let A = 2 1 1 1 and B = 0 1 -1 0 Then, the subgroup spanned by A and B is strongly irreducible and proximal.

Let

b 0 ∈ T 1 \ Q/Z be a diophantine number 1 , b = (b 0 , 0) and µ = 1 2 δ (A,b) + 1 2 δ (BA,Bb)
. Then, according to proposition 4.7, the measure µ satisfies to the assumptions of theorem 1.4.

1 There are C, L ∈ R * + such that for any q ∈ N * , d(qb0, 0) Cq -L .

Let g be the function defined for any x ∈ T 2 by g(x) = d(x, 0). We made everything so that for any x ∈ T 2 , g(Bx) = g(x).

Then, for any x ∈ T 2 ,

P g(x) = 1 2 g(Ax + b) + 1 2 g(BAx + Bb) = g(Ax + b)
And,

X |P g(x)| 2 dν(x) = X |g(Ax + b)| 2 dν(x) = X |g(x)| 2 dν(x)
Moreover, if we set f = g -P g, then, we just saw that σ 2 (f ) = g 2 -(P g) 2 dν = 0 and for any x ∈ X, n ∈ N and any (g 1 , . . .

g n ) ∈ {(A, b), (BA, Bb)} n , we have that g(g n+1 . . . g 1 x) = g(Ag n . . . g 1 x + b)
And so,

n-1 k=0 f (g k . . . g 1 x) = g(x) -g(g n . . . g 1 x) + n-1 k=0 g(g k+1 . . . g 1 x) -g(Ag k . . . g 1 x + b) = g(x) -g(g n . . . g 1 x)
This proves that for any x ∈ X, the sequence ( n-1 k=0 f (g k . . . g 1 x)) is bounded in L ∞ (P x ). The results in section 3 of [START_REF] Boyer | Central limit theorem and law of the iterated logarithm for the linear random walk on the torus[END_REF] actually prove that this example is really general.

We will see in sub-section 1.3 that theorem 1.6 is a quite general corollary of theorem 1.4 since we can easily study functions f on the torus that writes f = g -P g + f dν with g continuous and theorem 1.4 precisely says that any holder-continuous function can be written in this way.

Therefore, the main point of this article is the proof of theorem 1.4. To do so, we use the same method as Bourgain, Furmann, Lindenstrauss and Mozes. In section 2, we prove that the only obstacle in the equidistribution of the measure µ * n * ϑ is the lower regularity of ϑ i.e. the existence of points x such that for some r depending on n, ϑ(B(x, r)) r ε

In particular, if µ * n+m * ϑ is far from Lebesgue's measure then there has to be points x such that µ * m * ϑ(B(x, r)) r ε Then, our assumptions that µ satisfies an effective shadowing lemma and that supp µ is not a subset of SL d (Z) ⋉ Q d /Z d will allow us to prove in section 3 that this cannot happen when r ≪ e -m ≪ r ε .

The precise proof of the theorem is in subsection 1.2.

Finally, in section 4, we prove proposition 4.7 that is a criterion that shows that under some diophantine conditions on the translations in it's support, a measure satisfies an effective shadowing lemma and we will use this criterion to produce examples of such measures.

In the appendix, we state results on the products of random matrices in the case where the action is not irreducible and that we use in section 3.

1.1. Some kind of diophantine assumption is necessary. We already said (and we will prove in section 4) that a way to guarantee that a measure satisfies an affective shadowing lemma is to require diophantine conditions on the coefficients of the translations of it's support. In this sub-section, we prove that this kind of assumptions is indeed necessary to get theorem 1.4.

Proposition 1.10. Let a, b ∈ SL d (Z) and v ∈ T d . Set µ = 1 2 δ (a,0) + 1 2 δ (b,v)
. Assume that for some α ∈]0, 1], there are C, t ∈ R * + such that for any α-höldercontinuous function f on the torus and any n ∈ N, sup

x∈T d P n f (x) -f dν Ce -tn f α
Then, there are constants C 0 , L ∈ R * + such that for any rational point

p q ∈ Q d /Z d , d v, p q C 0 q L
Proof. For q ∈ N * and x ∈ T d , we set X q = 1 q Z d /Z d and

f q (x) = 1 -min 1, q 2α d(x, X q ) α
This function is chosen so that it takes the value 1 on 1 q Z d /Z d , it vanishes on the complementary of the 1 q 2 -neighborhood of 1 q Z d /Z d and it is hölder-continuous with f q α q 2α .

In particular, we have that, for some constant C depending only on d (and on the distance on T d ),

f q dν p q ∈ 1 q Z d /Z d ν B p q , 1 q 2 C q d
Moreover, for µ ⊗N -a.e. ((a n , b n )), we have that

f q n k=1 a n . . . a k+1 b k -1 f q α d n k=1 a n . . . a k+1 b k , X q α e αM n (e M -1) α d(v, X q ) α q 2α
where we noted e M = max( A , B ). Indeed, for any p q ∈ X q , we have that f q (p/q) = 1 and n k=1 a n . . . a k+1 b k can be written Dv where D is a matrix with integer coefficients and D n k=1 a n . . . a k+1 n k=1 e M (n-k) . This proves that for any n ∈ N,

|P n f q (0) -1| = G f q (b)dµ * n (a, b) -1 e αM n (e M -1) α d(v, X q ) α q 2α
But, by assumption, we also have that

P n f q (0) -f q dν
Ce -tn f q α Ce -tn q 2α

So, this proves that for any n, q ∈ N * , 1 -C q d -Ce -tn q 2α e αM n (e M -1) α d(v, X q ) α q 2α Thus, for any p ∈ Z d , any q ∈ N * such that q d 4C and any n such that Ce -tn q -2α /4, we have that

d v, p q e M -1 2 1/α e M n q 2
In particular, for n = ⌊ 1 t ln(4Cq 2α )⌋ + 1, we find that, for some constant C ′ depending only on M, α, t, C,

d v, p q C ′ q 2+2αM/t
And this is what we intended to prove.

Remark 1.11. We can prove the same kind of results for rates more general than Ce -tn and this shows that even convergences slower than exponential require some kind of diophantine assumption. 1.2. Proof of theorem 1.4 given the results of sections 2 and 3. Let α ∈]0, 1] and ε ∈ R * + . According to theorem 2.1 there are constants c 0 , ε ′ ∈ R * + with ε ′ < ε such that for any ϑ ∈ M 1 (T d ), any t ∈]0, 1] and any n ∈ N with n c 0 (1 + |ln t|),

W α (µ * n * ϑ, ν) t ⇒ ϑ x ∈ T d ϑ(B(x, r)) r ε t c 0 where r = e -(Λ 1 +ε ′ )n t 16 1/α
In particular, for any m, n ∈ N, any ϑ ∈ M 1 (T d ) any t ∈ R * + small enough and any C large enough,

W α µ * n+m * ϑ, ν Ce -tn ⇒ µ * m * ϑ x ∈ T d µ * m * ϑ(B(x, r)) r ε Ce -tn c 0 for r = e -(Λ 1 +ε ′ -δ/α)n
16 1/α But, since the measure satsfies to an effective shadowing lemma, according to proposition 3.1, there are C 1 , C 2 , t 0 , L ∈ R * + such that for any x, y ∈ T d , any m ∈ N and any

r ∈ R * + with r C 1 e -Lm , µ * m ({g ∈ G|d(gx, y) r}) C 2 e -t 0 m
And so, to get a contradiction, we only need to assume that

r = e -(Λ 1 +ε ′ -δ/α)n 16 1/α C 1 e -Lm and r ε = e -ε(Λ 1 +ε ′ -δ/α)n 16 ε/α C 2 e -t 0 m
And this is always possible for n = Km with K ∈ N large enough and ε small enough.

We just proved that there are C, t ∈ R * + and K ∈ N * such that for any borelian probability measure ϑ on T d and any m ∈ N,

W α µ * (K+1)m * ϑ, ν Ce -tm
Let n ∈ N and let m, L ∈ N be such that n = (K + 1)m + L and 0 L < K + 1. Then,

W α (µ * n * ϑ, ν) W α µ * (K+1)m * µ * L * ϑ, ν Ce -tm = Ce -t K+1 (n-L)
Ce t e -tn/(K+1)

And this finishes the proof of the first part of the theorem.

In particular, with ϑ = δ x for some x ∈ T d , we get that for any α-hölder-continuous function f on T d and any x ∈ T d ,

P n f (x) -f dν Ce -tn f α
Let f be an α-hölder-continuous function on T d . Set, for any n ∈ N,

g n = n-1 k=0 P k f -f dν Then, (I d -P )g n = f -f dν -P n f -f dν And so, lim n g n -P g n = f -f dν
Moreover, the series is normally convergent since

n P n f -f dν ∞ C 1 -e -t f α
And so, the function g = lim n g n exists, is continuous and satisfies

g -P g = f -f dν and g ∞ C 1 -e -t f α
Now, let ϑ be a P -invariant borelian probability measure on T d . Then, for any hölder-continuous function f ,

f dϑ = P n f dϑ -----→ n→+∞ f dν
Where we first used the P -invariance of ϑ and then the dominated convergence theorem since for any x ∈ T d , lim n P n f (x) = f dν according to the first part of the proof. And, finally, as the hölder-continuous functions are dense in the space of continuous functions on the torus, this proves that ϑ = ν and so, ν is the unique P -invariant borelian probability measure on T d . 1.3. Proof of theorem 1.6.

Proof of the law of large numbers. This result is a consequence of the uniqueness of the P -invariant borelian probability measure seen in theorem 1.4. Indeed, if we manage to prove that for any x and P x -a.e. x = (X n ) ∈ (T d ) N , the accumulation points of ν n,x := 1 n n-1 k=0 δ X k are P -invariant, we will get that they have to be the Lebesgue's measure and so, for any continuous function f on the torus,

1 n n-1 k=0 f (X k ) -→ f dν P x -a.e.
For any continuous function f on the torus, we can compute,

f dν n,x -P f dν n,x = 1 n n-1 k=0 f (X k ) - 1 n n-1 k=0 P f (X k ) = 1 n n-1 k=0 f (X k+1 ) -P f (X k ) + 1 n (f (X 0 ) -f (X n )) But, M n = n-1 k=0 f (X k+1 )-P f (X k
) is a martingale with bounded increments so 1 n M n -→ 0 a.e. and as f is bounded, we also have that 1

n (f (X 0 ) -f (X n )) -→ 0 in L ∞ (P x
). Thus, we just proved that for any x ∈ T d and any continuous function

f on T d , there is X f ⊂ (T d ) N such that P x (X f ) = 1 and for any x ∈ X f , lim n f dν n,x -P f dν n,x = 0 Let (f i ) be a dense sequence in C 0 (T d ) and X ∞ = ∩ i X f i . Then, P x (X ∞ ) = 1 and for any x ∈ X ∞ and any i ∈ N, lim n f i dν n,x -P f i dν n,x = 0
So, as the sequence (f i ) is dense, we get that for any continuous function f on T d and any

x ∈ X ∞ , lim n f dν n,x -P f dν n,x = 0
This proves that for any x ∈ X ∞ , the accumulation points of (ν n,x ) are P -invariant and so they are equal to ν and this proves the law of large numbers.

To prove the remaing part of the theorem, we are going to use Gordin's method and deduce the non-concentration inequality, the FCLT and the ASFCLT from these results for martingales. Indeed, according to theorem 1.4, for any α ∈]0, 1], there is a constant C such that for any α-hölder-continuous function f on the torus there is a continuous function g such that

f -f dν = g -P g and g ∞ C f α Set, for x = (X n ) ∈ X N , S n f (x) = n-1 k=0 f (X k ) -n f dν and M n = n-1 k=0 g(X k+1 ) -P g(X k ) Then, S n f (x) = M n + g(X 0 ) -g(X n )
And M n is a martingale with bounded increments.

Proof of the non-concentration inequality. For any n ∈ N, we have that

|M n | |S n f (x)| -2 g ∞ |S n f (x)| -2C f α
So, using Azuma-Hoeffding's inequality, if nε > 2C, we get that

I n (x) : = P x (|S n f (x)| > nε f α ) P x (|M n | (nε -2C) f α ) 2 exp -(nε -2C) 2 f 2 α 2n(2C f α ) 2 = 2 exp - nε 2 8C 2 + ε 4C - 1 2n
And this finishes the proof of this point.

Proof of points 1 and 2. As the function g is bounded, the sequence (

S n f (x) -M n ) is bounded in L ∞ (P x
) and so it is clear that to prove the FCLT and the AEFCLT, it is enough to study the martingale M n (that has bounded increments). But, according to the functional central limit theorem for martingales (see corollary 4.1 in [HH80]) and it's almost sure extension (see [START_REF] Chaabane | Version forte du théorème de la limite centrale fonctionnel pour les martingales[END_REF]), it is enough to prove the a.e. convergence of the variance (when the limit doesn-t vanish). But, for any n ∈ N * ,

1 n n-1 k=0 E x |M k+1 -M k | 2 X 0 , . . . , X k = 1 n n-1 k=0 E x |g(X k+1 ) -P g(X k )| 2 X 0 , . . . , X k = 1 n n-1 k=0 P (g 2 )(X k ) -(P g(X k )) 2
So, according to the law of large numbers that we already proved and applied to the continuous function P (g 2 ) -

(P g) 2 , 1 n n-1 k=0 E x |M k+1 -M k | 2 X 0 , . . . , X k -→ σ 2 (f ) := g 2 -(P g) 2 dν P x -a.e.
(We used the P -invariance of ν to get that P (g 2 )dν = g 2 dν). And this proves point 1 since we suppose in it that σ 2 (f ) = 0.

To conclude, remark that, using the G-invariance of ν, we can compute

G X |g(γx) -P g(x)| 2 dν(x)dµ(γ) = G X g(γx) 2 + g(x) 2 -2P g(x)g(γx)dν(x)dµ(γ) = 2 X g 2 -(P g) 2 dν = 2σ 2 (f )
And so, if σ 2 (f ) = 0, then, as g is continuous, we get that for any γ ∈ supp µ and any x ∈ T d , g(γx) = P g(x). This proves that for any n ∈ N, M n = 0 P x -a.e. and so,

S n f (x) = g(X 0 ) -g(X n ). Thus, for any x ∈ T d , S n f ∈ L ∞ (P x ) and sup x∈T d sup n∈N S n f L ∞ (Px) 2 g ∞ 2C f α
This inequality finishes the proof of point 2.

2. The non-equidistribution comes from the lower regularity of the measure Like Bourgain, Furmann, Lindenstrauss and Mozes did for the linear random walk on the torus, we are going to prove in this section that if the measure µ * n * ϑ is far from being equidistributed, it is only because of atoms i.e. of points x ∈ T d such that ϑ(B(x, r)) r ε for some r ∈ R * + depending on n. More specifically, the aim of this section is to prove the Theorem 2.1. Let µ be a borelian probability measure on SL d (Z) ⋉ T d . Denote by µ 0 the projection of µ on SL d (Z) and assume that µ 0 is strongly irreducible, proximal and has an exponential moment. Let λ 1 ∈ R * + be the largest Lyapunov exponent of µ 0 (see appendix A).

Then for any α ∈ ]0, 1] and any

ε ∈ R * + , there is c 0 , ε ′ ∈ R * + with ε ′ < ε such that for any ϑ ∈ M 1 (T d ), any t ∈ ]0, 1] and any n ∈ N with n c 0 (1 + |ln t|), W α (µ * n * ϑ, ν) t ⇒ ϑ x ∈ T d ϑ(B(x, r)) r ε t c 0
Where we set r = e -(λ 1 +ε ′ )n t 16

1/α
In the case of the linear random walk, this statement is a reformulation of an intermediate result (propositions 7.1 and 7.2) of [BFLM11]. We could prove it for the affine random walk just like they do for the linear one that is to say, by studying, for any borelian probability measure ϑ on T d , the set of Fourier-coefficients of µ * n * ϑ and by remarking that for any c ∈ Z d ,

µ * n * ϑ(c) = T d SL d (Z)⋉T d e 2iπ c,ax+b dµ * n (a, b)dν(x) = SL d (Z)⋉T d e 2iπ c,b ϑ( t ac)dµ * n (a, b)
And so,

µ * n * ϑ(c) SL d (Z)⋉T d ϑ( t ac) dµ * n (a, b) = SL d (Z) ϑ( t ac) dµ * n 0 (a)
Where we recall that we denoted by µ 0 the projection of µ onto SL d (Z).

Thus, if µ * n * ϑ(c) t, then for many a, we also have that ϑ( t ac) t and this is the key remark in the proof of BFLM.

Instead, we are going to see that this result can also be obtained as a corollary of the one of BFLM for the linear walk : at first, we are going to prove that their result gives informations on the spectral radius of the operator P in L p (T d , ν) (even for the affine random walk) and then, that this implies the theorem.

2.1. Spectral gap in L p (T d ). Let G be a second countable locally compact group acting measurably on a standard borelian space X endowed with a G-invariant probability measure ν.

Let µ be a borelian probability measure on G and P the Markov operator associated to µ. This is the operator defined for any non-negative borelian function f on X and any x ∈ X by

P f (x) = G f (gx)dµ(g)
As ν is a G-invariant probability measure, it is clear that for any p ∈ [1, +∞], 1 ∈ L p (X, ν) and P 1 = 1. Moreover, we can prove, using Jensen's inequality that P p = 1. So, we note, for any p ∈]1, +∞],

L p 0 (X, ν) := f ∈ L p (X, ν) f dν = 0
and ρ p the spectral radius of P in L p 0 (X, ν). We say that P has a spectral gap in L p 0 (X, ν) (or, by abuse of notations in L p (X, ν)) if ρ p < 1.

In the sequel, we will need a more flexible tool than the spectral gap. This is why, for any P -invariant subspace H of L p (X, ν) endowed with a norm . H such that P is continuous on (H, . H ) and the injection of (H, . H ) into (L p , . p ) is also continuous, we set

κ(µ, H, L p (X, ν)) := -ln lim sup n→+∞ sup f ∈H\{0} P n f p f H 1/n
Remark 2.2. The sequence sup f ∈H\{0}

P n f p f H
is not sub-multiplicative in general so it may converge to 0 only at polynomial rate and in this case, we would have that κ(µ, H, L p (X, ν)) = 0. This is impossible if H = L p (X) because in this case, if it converges to 0, it has to be at exponential rate.

With this definition, if (H, . H ) = (L p (X, ν), . p ), then e -κ(µ,H,L p (X,ν)) = ρ p and, for any (H, . H ), we have, since the inclusion of H into L p (X, ν) is supposed to be continuous,

κ(µ, H, L p (X, ν)) -ln ρ p
In particular, when H is a subset of L ∞ (X, ν), we can define and study the function (p → κ(µ, H, L p (X, ν))).

Remark 2.3. Remind that, according to Hölder's inequality, for any 1 p p ′ and any function

f ∈ L ∞ (X, ν) with f ∞ 1, f p ′ p ′ = X |f | p ′ dν X |f | p dν = f p p and f p f p ′
So, we get that the function (p → κ(µ, H, L p (X, ν))) is decreasing whereas the function (p → pκ(µ, H, L p (X, ν))) is non-decreasing.

In the same way that we defined L p 0 (T d ), we set

C 0,α 0 (T d ) := f ∈ C 0,α (T d ) f dν = 0
The definition of the function κ is made to get the Proposition 2.4. Let µ be a strongly irreducible and proximal probability measure on SL d (Z) having an exponential moment.

Then, for any α ∈]0, 1] small enough,

lim p→+∞ p κ µ, C 0,α 0 T d , L p T d , ν = λ 1 d
This theorem implies in particular that for any ε ∈ R * + , there are p ∈ N and C ∈ R + such that for any n ∈ N and any f ∈ C 0,α 0 (T d ),

P n f L p (T d ) Ce -(λ 1 d-ε)n/p f α
Proof. First of all, since µ has an exponential moment, for any α ∈]0, 1] small enough, any f ∈ C 0,α (T d ) and any x ∈ T d ,

|P f (x)| f ∞ and for any y ∈ T d , |P f (x) -P f (y)| G |f (gx) -f (gy)|dµ(g) f α G d(gx, gy) α dµ(g) f α d(x, y) α G g α dµ(g)
So, P f is α-hölder-continuous and P is a continuous operator on C 0,α 0 (T d ). According to the result of Bourgain, Furmann, Lindenstrauss and Mozes in [BFLM11] (that we use as stated in proposition 4.5 in [START_REF] Boyer | Central limit theorem and law of the iterated logarithm for the linear random walk on the torus[END_REF]), we have that for any α ∈]0, 1] and any ε ∈ R * + , there is a constant C such that for any n ∈ N, any t ∈]0, 1] with n -C ln t and any f ∈ C 0,α (T d ) with f dν = 0,

{x||P n f (x)| t f α } ⊂ p q ∈Q d /Z d q Ct -C B p q , e -(λ 1 -ε)n
In particular, for any L ∈ N * ,

|P n f | L dν (t f α ) L + ν ({x||P n f (x)| t f α }) f L ∞ t L + (Ct -C ) d e -(λ 1 -ε)dn f L α
And so, taking t = e -δn with δ ∈ R * + small enough and L ∈ N large enough, we find that for some constant C,

|P n f | L dν Ce -(λ 1 -2ε)dn f L α
And this proves (reminding that the limit exists according to remark 2.3) that lim

p p κ µ, C 0,α 0 T d , L p T d , ν λ 1 d
We are now going to prove the other inequality. Let δ ∈]0,

1/4], f ∈ C ∞ (T d ) such that f = 1 on B(0, δ), f ∞ 1 and f = 0.
Then, for any ε ∈ R * + and any x ∈ B(0, e -(λ 1 +ε)n δ), we have that

P n f (x) = G 1 g e (λ 1 +ε)n f (gx)dµ * n (g) + G 1 g e (λ 1 +ε)n f (gx)dµ * n (g) = µ * n g g e (λ 1 +ε)n + G 1 g e (λ 1 +ε)n f (gx)dµ * n (g) 1 -2µ * n g g e (λ 1 +ε)n
But, according to theorem A.5, there are C, t ∈ R * + such that µ * n g g e (λ 1 +ε)n Ce -tn

And so, for n ∈ N large enough, we have that for any x ∈ T d ,

|P n f (x)| 1 -2Ce -tn 1 B(0,e -(λ 1 +ε)n δ) (x)
In particular, for any L ∈ N,

|P n f (x)| L dν 1 -2Ce -tn L ν(B(0, e -(λ 1 +ε)n δ)) = 1 -2Ce -tn L e -(λ 1 +ε)dn δ d
And this proves that lim

p p κ µ, C 0,α 0 T d , L p T d , ν λ 1 d
And this finishes the proof of the proposition.

We are now going to extend the previous result to measures on SL d (Z)⋉T d by proving the Corollary 2.5. Let µ be a borelian probability measure on G := SL d (Z) ⋉ T d . Let µ 0 be the projection of µ onto G 0 := SL d (Z) and assume that µ 0 is strongly irreducible, proximal and has an exponential moment.

Then, for any α ∈]0, 1] small enough,

lim p→+∞ p κ µ, C 0,α 0 T d , L p T d , ν λ 1 d
Remark 2.6. Theorem 1.4 actually proves that for any measure µ satisfying it's assumptions we have that for any f ∈ C 0,α (T d ) with f dν = 0, any n ∈ N and any p ∈ N * ,

|P n f | p dν C p e -tpn f p α
And so, for any p ∈ [1, +∞[,

κ µ, C 0,α 0 T d , L p T d , ν t
And, in particular,

lim p→+∞ p κ µ, C 0,α 0 T d , L p T d , ν = +∞
We are going to prove this result in three steps. First, we are going to prove it for trigonometric functions, then, for regular ones and last, for hölder-continuous functions. Proof. Using Fubini's theorem, we can make the following computation

X |P n 0 e c (x)| 2L dν(x) = X (P n 0 e c (x)) L (P n 0 f (x)) L dν(x) = X G 2L e c (a 1 x) . . . e c (a L x)e c (a L+1 x) . . . e c (a 2L x)dµ * n 0 (a 1 ) . . . dµ * n 0 (a 2L )dν(x) = G 2L X e 2iπ c,(a 1 +•••+a L -(a L+1 +•••+a 2L ))x dν(x)dµ * n 0 (a 1 ) . . . dµ * n 0 (a 2L ) = G 2L 1 { t (a 1 +•••+a L -(a L+1 +•••+a 2L ))c=0} dµ * n 0 (a 1 ) . . . dµ * n 0 (a 2L )
Doing the same kind of computations for the measure µ, and noting, to simplify notations, for (a

1 , b 1 ), . . . , (a 2L , b 2L ) ∈ supp µ, a j i = a i + • • • + a j and b j i = b i + • • • + b j , we find that X |P n e c | 2L dν = G 2L e 2iπ c,b L 1 -b 2L L+1 1 { t (a L 1 -a 2L L+1 )c=0} dµ * n (a 1 , b 1 ) . . . dµ * n (a 2L , b 2L ) G 2L 1 { t (a L 1 -a 2L L+1 )c=0} dµ * n 0 (g 1 ) . . . dµ * n 0 (g 2L ) = X |P n 0 e c | 2L dν
Where the last inequality comes from the first part of the proof and precisely gives what we intended to prove.

For s ∈ R * + , we denote by H s (T d ) the Sobolev space of exponent s.

Lemma 2.8. With the same assumptions than in corollary 2.5, for any s ∈ R * + large enough and any ε ∈ R * + , there is L ∈ R + such that for any f ∈ H s (T d ) and any n ∈ N,

P n f -f dν 2L dν Ce -(λ 1 d-ε)n f 2L H s (T d ) Proof. Let f ∈ H s (T d ).
Then, by definition, we can expand f in Fourier series :

f = c∈Z d f (c)e c with f H s := c∈Z d (1 + c 2 ) s/2 | f (c)| 2 1/2
< +∞ and so, for any

L ∈ N * , T d |P n f | 2L dν 1/2L c∈Z d | f (c)| T d |P n e c | 2L dν 1/2L
Using the previous lemma and proposition 2.4, we get that for any ε ∈ R * + , there is

L ∈ R + such that for any c ∈ Z d \ {0}, T d |P n e c (x)| 2L dν(x) Ce -(λ 1 d-ε)n c 2L
Combining this inequality with the previous one, we get that for any f ∈ H s (T d ) with f (0) = f dν = 0,

T d |P n f | 2L dν 1/2L C 1/2L e -(λ 1 d-ε)n/2L c∈Z d \{0} | f (c)| c C ′ e -(λ 1 d-ε)n/2L f H s
For some constant C ′ depending on d, s, µ, L but non on f .

End of the proof of corollary 2.5. According to Jackson-Bernstein's lemma, for any α ∈ ]0, 1] and any s ∈ R + large enough, there is a constant C such that for any

f ∈ C 0,α (T d ), there is a sequence (f m ) ∈ H s (T d ) N such that for any m ∈ N * , f dν = f m dν, f -f m ∞ C m α f α and f m H s Cm f α
This implies that for any x ∈ T d and any m, n ∈ N * ,

|P n f m (x)| |P n f (x)| - C m α f α Let ε ∈ R * + , m ∈ N * and t = 2C m α .
Then, using the equality t -C/m α = t/2 and lemma 2.8, we get that

|P n f | 2L dν (t f α ) 2L + ν ({|P n f | t f α }) f 2L ∞ t 2L + ν |P n f m | t - C m α f α f 2L α t 2L + 2 t f α 2M |P n f m | 2M dν f 2L α t 2L + 2 t f α 2M C 2M m 2M e -(λ 1 d-ε)n f 2M α f 2L α
So, for m = e δn , we get that for some constant C ′ ,

|P n f | 2L dν C ′ e -δα2Ln + e δ(1+α)2M n-(λ 1 d-ε)n f 2L α
And so, for δ small enough and L large enough, we get that

|P n f | 2L dν Ce -(λ 1 d-2ε)n f 2L α
And this is what we intended to prove. 2.2. Equidistribution, lower regularity and spectral gap. In this subsection, we finish the proof of theorem 2.1 by studying the link between equidistribution and the lower regularity of the measure when the spectral gap is large. Lemma 2.9. Under the same assumptions as in theorem 2.1, for any ε ∈ R * + , there are C, t ∈ R * + such that for any x, y ∈ T d , any f ∈ C 0,α (T d ) and any n ∈ N,

|P n f (x) -P n f (y)| e α(λ 1 +ε)n d(x, y) α + Ce -tn f α Proof. Let's compute, for any x, y ∈ T d , n ∈ N, f ∈ C 0,α (T d ) and ε ∈ R * + , |P n f (x) -P n f (y)| = G f (gx) -f (gy)dµ * n (g) G 1 g e (λ 1 +ε)n |f (gx) -f (gy)|dµ * n (g) + G 1 g e (λ 1 +ε)n |f (gx) -f (gy)|dµ * n (g) m α (f ) G 1 g e (λ 1 +ε)n d(gx, gy) α dµ * n (g) + 2 f ∞ µ * n g ∈ G g e (λ 1 +ε)n d(x, y) α e α(λ 1 +ε)n + 2µ * n g ∈ G g e (λ 1 +ε)n f α
Where we used the fact that for any x, y ∈ T d and any g ∈ G,

d(gx, gy) g d(x, y)

To conclude, we use theorem A.5 and we get that there are C, t ∈ R * + such that

µ * n g ∈ G g e (λ 1 +ε)n Ce -tn
We are now ready to prove theorem 2.1. The idea of the proof is that if we have some point x 0 of the torus such that |P n f (x 0 )| t, then, on a neighborhood B(x 0 , r) for r ≈ e -λ 1 n we also have that |P n f (x)| ≈ t. But, the control on κ(µ, C 0,α , L p ) implies that ν(x||P n f (x)| t) ≈ e -λ 1 dn and so, we have that ν(x||P n f (x)| t) ≈ e -λ 1 dn ≈ ν(B(x 0 , r)) and this proves that {x||P n f (x)| t} cannot be much bigger than B(x 0 , r).

Proof of theorem 2.1. Let α, t ∈]0, 1], ϑ ∈ M 1 (T d ) and n ∈ N. As, for any 0 < α ′ < α the inclusion of C 0,α (T d ) into C 0,α ′ (T d ) is continuous, we may assume without any loss of generality that α is small enough so that corollary 2.5 holds.

Assume that W α (µ * n * ϑ, ν) t. By definition, there is f ∈ C 0,α (T d ) with f α 1 and such that

P n f dϑ -f dν t 2
We can assume without any loss of generality that f dν = 0 and f α 2. And this proves that

T d |P n f (x)| dϑ(x) T d P n f (x)dϑ(x) t 2 We set, for any n ∈ N and t ∈]0, 1], X n,t := x ∈ T d |P n f (x)| t Then, using that P n f ∞ f ∞ 2, we find that t 2 X |P n f (x)|dϑ(x) t 4 + 2ϑ X n,t/4
And so, ϑ X n,t/4 t 8 Moreover, according to lemma 2.9, for any ε 2 ∈ R * + , there are C, t 0 ∈ R * + such that for any x ∈ X n,t/4 and any y ∈ T d , we have that

|P n f (y)| t 4 -e α(λ 1 +ε 2 )n d(x, y) α -Ce -t 0 n t 8 -e α(λ 1 +ε 2 )n d(x, y) α
Since we can take c 0 so large that Ce -t 0 n t 8 for n c 0 (1 + | ln t|). In particular, noting r = e -(λ 1 +ε 2 )n t 16 1/α , we have that for any x ∈ X n,t/4 , B(x, r) ⊂ X n,t/16 . Moreover, according to the classical covering results, there is a constant C(d), depending only on d and points x 1 , . . . , x N ∈ T d such that

X n,t/4 ⊂ N i=1 B(x i , r) ⊂ X n,t/16
and the union has multiplicity at most C(d).

This implies in particular that

N i=1 1 B(x i ,r) C(d)1 X n,t/16
And so, taking the integral against the measure ν and using the equality ν(B(x, r)) = r e (λ 1 +ε 2 )dn ν(X n,t/16 ) And that, according to Markov's inequality and corollary 2.5, for any

ε 1 ∈ R * + , there are C, L ∈ R + such that ν(X n,t/16 ) 16 t 2L X |P n f (x)| 2L dν(x) 16 t 2L Ce -(λ 1 d-ε 1 )n f 2L α 32 t 2L Ce -(λ 1 d-ε 1 )n
This proves that for some constant C depending on ε 1 , d, µ, N C t C e (ε 1 +ε 2 d)n And so, taking ε 1 , ε 2 small enough and c 0 large enough, we get that

t 16N t C+1 C e -(ε 1 +ε 2 d)n (2r) ε
and this is what we intended to prove.

Measure of points-stabilizers

The aim of this section is to prove the following Proposition 3.1. with the same assumptions as in theorem 1.4, there are C, t ∈ R * + such that for any x ∈ T d and any n ∈ N,

µ * n ⊗ µ * n ({g 1 , g 2 ∈ G|g 1 x = g 2 x}) Ce -tn
This proposition will be a direct corollary of lemmas 3.2 and 3.3 since if µ is not concentrated on SL d (Z) ⋉ Q d , then the measure µ 1 of lemma 3.2 is not concentrated on SL d (R) ⋉ {0}.

To evaluate the measure of the stabilizer of a point, we are going to lift the situation from T d to R d since we know better the products of random elements of SL d (R) ⋉ R d (through the theory of products of random matrices since this group can be identified to a subgroup of SL d+1 (R)) than those of elements of SL d (Z) ⋉ T d .

To understand what we are going to do, remark that if

µ = 1 2 δ (g 1 ,v 1 ) + 1 2 δ (g 2 ,v 2 ) with g 1 , g 2 ∈ SL d (Z), v 1 ∈ Q d /Z d and v 2 ∈ T d such that the coefficients of v 2 and 1 are Q-linearly independent, then, for µ * n -a.e. (g, v) ∈ SL d (Z) ⋉ T d , we can write v = M 1 v 1 + M 2 v 2 with M i ∈ M d (Z). So, in particular, noting -→ v 1 , -→ v 2 some representatives of v 1 , v 2 in R d , we get that if v = 0 in T d , then there is p ∈ Z d , such that, M 1 -→ v 1 + M 2 -→ v 2 = p
As we assumed that the coefficients of v 2 and 1 are Q-linearly independent and that

v 1 ∈ Q d , we get that M 2 -→ v 2 = 0 and M 1 -→ v 1 = p.
So, we set

µ 1 = 1 2 δ (g 1 ,0) + 1 2 δ (g 2 , -→ v 2 ) ∈ M 1 SL d (R) ⋉ R d
and what we just proved is that

µ * n (SL d (Z) ⋉ {0}) µ * n 1 (SL d (R) ⋉ {0}
) And so we are let with a problem on probability measures on SL d (R) ⋉ R d . Thus, to lift the situation from T d to R d , we are going to project the translation part of elements in the support of µ onto a complementary subspace of Q d in the Q-vector space R d . To do so, we fix some Q-linear projection π

Q : R d → R d onto Q d and we remark that for any v ∈ R d /Z d , v -π Q v ∈ R d is well defined and the application SL d (Z) ⋉ T d ∋ (g, v) → (g, v -π Q v) ∈ SL d (Z) ⋉ R d is a group-morphism.
Now, we can prove the following Lemma 3.2. Let µ be a borelian probability measure on SL d (Z) ⋉ T d . Then, for any n ∈ N and any y ∈ T d ,

µ * n ⊗ µ * n (g 1 , g 2 ) g -1 2 g 1 ∈ Stab(y) µ * n 1 ⊗ µ * n 1 (g 1 , g 2 ) g -1 2 g 1 ∈ Stab(y -π Q y)
where µ 1 is the measure on SL d (Z) ⋉ R d defined by µ 1 (A) = µ(ϕ -1 (A)) where ϕ :

SL d (Z) ⋉ T d → SL d (Z) ⋉ R d is the function defined by ϕ(g, v) = (g, v -π Q v) and π Q is some Q-linear projection onto Q d .
Proof. As ϕ is a morphism, we only need to prove that for any g ∈ SL d (Z) ⋉ T d and any

y ∈ T d , if gy = y then ϕ(g)(y -π Q y) = (y -π Q y). Write g = (a, b) with a ∈ SL d (Z) and b ∈ T d . Then, ϕ(g) = (a, b -π Q b). So, ϕ(g)(y -π Q y) = a(y -π Q y) + b -π Q b
But, gy = y, so, noting -→ b , -→ y some representatives of b, y, we get that there is

p ∈ Z d such that a -→ y + -→ b = -→ y + p
Projecting onto Q d , we also get that

aπ Q -→ y + π Q -→ b = π Q -→ y + p
And this proves that

a(I d -π Q ) -→ y + (I d -π Q ) -→ b = (I d -π Q ) -→ y Finally, as (I d -π Q ) -→ y and (I d -π Q ) -→
b don't depend on the choices of the representatives of y and b, this finishes the proof of the fact that

a(y -π Q y) + b -π Q b = y -π Q y
and this finishes the proof of the lemma.

Lemma 3.3. Let µ be a borelian probability measure on SL d (R) ⋉ R d that is not concentrated on SL d (R) ⋉ {0} and has an exponential moment. Let µ 0 be the projection of µ onto SL d (R) and assume that µ 0 is strongly irreducible and proximal.

Then, there are C, t ∈ R * + such that for any x ∈ R d and any n ∈ N,

µ * n ⊗ µ * n ({(g 1 , g 2 )|g 1 x = g 2 x}) Ce -tn
Proof. We denote by μ the measure on SL d (R) ⋉ R d defined by μ(A) = µ(A -1 ) for any borelian subset A of SL d (R) ⋉ R d and where A -1 := {g -1 |g ∈ A}.

Let λ 1 • • • λ d be the Lyapunov exponents of µ 0 (see appendix A). Then, the largest Lyapunov exponent of μ is -λ d . Moreover, as

λ 1 • • • λ d , λ 1 > 0 and λ 1 + • • • + λ d = 0, we have that λ d < 0 and so, -λ d > 0. Let n ∈ N, ε ∈ R * + and x ∈ R d . We can compute, I n (x) : = µ * n ⊗ µ * n ({g 1 , g 2 ∈ G|g 1 x = g 2 x}) = µ * n ⊗ μ * n (g 1 , g 2 ) ∈ G 2 g 2 g 1 x = x µ * n ⊗ μ * n (g 1 , g 2 ) 1 + g -1 2 g 1 x 1 + x e (λ 1 -λ d -ε)n But 1 + g 2 g 1 x 1 + x = 1 + g 2 g 1 x 1 + g 1 x 1 + g 1 x 1 + x
So, we obtain that

I n (x) µ * n g 1 1 + g 1 x 1 + x e (λ 1 -ε/2)n + G μ * n g 2 1 + g 2 g 1 x 1 + g 1 x e (-λ d -ε/2)n dµ * n (g 1 )
And we can conclude with corollary A.9 applied to the measures µ and μ.

Effective shadowing lemmas

The aim of this section is to prove a criterion to produce measures satisfying an effective shadowing lemma.

First of all, we recall the Definition 4.1. Let µ be a borelian probability measure on G.

We say that µ satisfies an effective shadowing lemma if for ant

C ′ , t ′ ∈ R * + , there are C 1 , C 2 , M, t, L ∈ R * + such that for any x, y ∈ T d , any r ∈ R * + and any n ∈ N with r C 1 e -Ln , if µ * n ({g ∈ G|d(gx, y) r}) C 2 e -tn
then there are x ′ , y ′ ∈ T d such that d(x, x ′ ), d(y, y ′ ) re M n and

µ * n g ∈ G gx ′ = y ′ C ′ e -t ′ n
The criterion that we are going to prove will use the diophantine properties of the translation parts of the elements in supp µ. More specifically, we want a condition that ensures that if (g 1 , v 1 ), (g 2 , v 2 ) ∈ supp µ * n are such that v 1 and v 2 are close (in some sense) then v 1 = v 2 . This is why we make the following

4.4. Let b ∈ T 1 \ Q/Z. Asking {b} to be diophantine is asking for C, L ∈ R * + such that for any q ∈ N * , d(qb, 0) > C q L
The name comes from this property.

Remark 4.5. Let d 2 and B a subset of T d . It is not the same thing to say that B is diophantine and that {coefficients of b|b ∈ B} is a diophantine subset of T 1 (consider B = {(b 1 , b 2 )} with b 1 diophantine and b 2 not). This last property is stronger but this is the one that we will need in the sequel and we refer to lemma 4.8 for more details.

Example 4.6. Let N ∈ N * . Then, for a.e. b 1 , . . . b N ∈ T 1 , the set {b 1 , . . . b N } is diophantine.

We are now ready to state the main result of this section Proposition 4.7. Let µ be a borelian probability measure on SL d (Z) ⋉ T d and let µ 0 be it's projection on SL d (Z). Assume that µ 0 is strongly irreducible, proximal and that it has an exponential moment and that {coefficients of b|(a, b) ∈ supp µ} is a diophantine subset of T 1 .

Then, µ satisfies an effective shadowing lemma.

To prove this proposition, we first come back to the difference for a subset B of T d between being diophantine and having elements whose coefficients form a diophantine subset of T 1 . Lemma 4.8. Let B be a finite subset of T d and

F := {coefficients of B} ⊂ T 1 Then, F is (C, L)-diophantine if and only if there is C ′ ∈ R * + such that for any non zero (M b ) ∈ M d (Z) B , d b∈B M b b, 0 C ′ (max b M b ) L ⇒ b M b b = 0 Proof. First, assume that F is (C, L)-diophantine and set C ′ = C/(d|B|) L . Let 0 = (M b ) ∈ M d (Z) B be such that d( b∈B M b b, 0) C ′ (max b M b ) L Each coefficient of b M b b is a sum of
  f L f f, 0   C ′ max b M b L C ′ (d|B|) L max f |L f | L = C (max f |L f |) L
And as F is (C, L)-diophantine, this implies that f L f f = 0 and so, as this is true for any

coefficient of b M b b, we get that b M b b = 0.
Reciprocally, if there is

C ′ ∈ R * + such that for any 0 = (M b ) ∈ M d (Z) B d b∈B M b b, 0 C ′ (max b M b ) L ⇒ b M b b = 0 Then, we set C = C ′ /d L and let 0 = (L f ) ∈ Z F be such that d   f ∈F L f f, 0   C (max f |L f |) L For any element f of F , choose an element (b(f ), i(f )) in {(b, i) ∈ B × [1, d]|f is the i -th coefficient of b}
Now, for any b ∈ B, we denote by M b the matrix where we set L f in the i-th column if there is f ∈ F such that (b(f ), i(f )) = (b, i) and 0 otherwise. Thus, by definition, b∈B

M b b =    f L f f . . . f L f f    And max b M b d max f |L f | so d b M b b, 0 C (max f |L f |) L C ′ (max b M b ) L
And this proves, as B is (C, L)-diophantine, that b M b b = 0 and so we also get that f L f f = 0 and this finishes the proof of the lemma. From now on, we set To prove proposition 4.7, we are going to use some control of the translation parts of elements of supp µ * n . To do so, for any Q ∈ N * and any finite subset B of T d , we set

X Q (B) = p + b∈B M b b q p ∈ Z d , q ∈ Z, |q| Q, (M b ) ∈ M d (Z) B , max b∈B M b Q
Thus some x ∈ T d belongs to X Q (B) if there is q ∈ N * with q Q such that each coefficient of qx can be obtained from translations by coefficients of elements of B with multiplicities smaller than Q.

This definition is made so that for any M large enough we have that for any n ∈ N * , with large probability, any element (g, v) ∈ supp µ * n is such that v ∈ X e M n (B(µ)).

To make this idea more precise, we set, for any M ∈ R * + and n ∈ N,

G M n := (a i ) ∈ G n 0 max k∈[1,n] max 1 i 1 <•••<i k n a i k . . . a i 1 e M n
The aim of the following lemma is to prove that elements of G M n are generic. Lemma 4.9. Let µ be a borelian probability measure on G and let µ 0 be the image of µ on SL d (Z). Assume that µ 0 has an exponential moment.

Then, for any

M ∈ R * + large enough, there is t ∈ R * + such that for any n ∈ N, µ ⊗n 0 G M n 1 -e -tn Moreover, if B(µ) is finite (see equation (4.1)), then, for any (a 1 , b 1 ), . . . , (a n , b n ) ∈ supp µ such that (a i ) ∈ G M n , n k=1 a n . . . a k+1 b k ∈ X e (M +1)n (B(µ))
Lemma 4.11. With the assumptions of proposition 4.7, for any M ∈ R * + large enough there are C, t ∈ R * + such that for any r ∈]0, 1], any n ∈ N, any x, y ∈ T d , if µ * n ({g ∈ G|d(gx, y) r}) Ce -tn then there is

x ′ ∈ X e M n (B(µ)) such that d(x, x ′ ) re M n
Proof. The idea that makes the demonstration work is that if a 1 x + b 1 , . . . , a d x + b d are close to each-others, then setting c 1 = 1 -d and c i = 1 for i ∈ [2, d], we get that i c i a i x is close to i c i b i . But, according to lemma 4.10, with large probability, the matrix i c i a i is invertible and, according to lemma 4.9, the b i belong to X e M n (B(µ)), and so x ∈ X e M n (B(µ)).

We keep the notations G 1 0 and G d 0 from lemma 4.10 and the notation G M n from lemma 4.9. Then, for any ε ∈ R * + and any large enough M we denote by C, t the constants given by lemma 4.10 and by t 0 the one given by lemma 4.9.

Then, we set

G * := ((a 1 , b 1 ), . . . , (a d , b d )) ∈ G d (a i ) ∈ G d 0 and for any i, b i ∈ X e (M +1
)n (B(µ)) By definition, we have that

µ * n ⊗ • • • ⊗ µ * n (G * ) Ce -tn + de -t 0 n
So, we can compute, for any x, y ∈ T d ,

I n (x, y) : = (µ * n ({g ∈ G|d(gx, y) r})) d = G d 1 B(y,r) (a 1 x + b 1 ) . . . 1 B(y,r) (a d x + b d )dµ * n (a 1 , b 1 ) . . . dµ * n (a d , b d ) Ce -tn + de -t 0 n + G * d i=1 1 B(y,r) (a i x + b i )dµ * n (a 1 , b 1 ) . . . dµ * n (a d , b d )
Thus, if M is large enough, we can find C, t ∈ R * + such that for any r ∈]0, 1], any n ∈ N, if µ * n ({g ∈ G|d(gx, y) r}) Ce -tn then

G * d i=1 1 B(y,r) (a i x + b i )dµ * n (a 1 , b 1 ) . . . dµ * n (a d , b d ) > 0 In particular, there is ((a 1 , b 1 ), . . . , (a d , b d )) ∈ G * such that for any i, d(a i x + b i , y) r Now, we let -→ x , -→ y , -→ b i be representatives of x, y, b i in R d . We have that for any i ∈ [1, d] there is p i ∈ Z d such that a i -→ x + -→ b i --→ y -p i r So, noting c 1 = 1 -d and c i = 1 for i = 1, we get that ( i c i a i )x + i c i b i - i c i p i 2dr But, by definition of G d 0 , det ( i c i a i ) ∈ Z * . So, 1 det i c i a i i c i a i d d 2d e (λ 1 +ε)dn Let U = i c i a i .
Then U is invertible and we can write,

U -1 = 1 det U V with V ∈ M d (Z)
and for some constant C(d) depending only on d, V C(d) U d-1 . Thus, we get that

x + U -1 i c i b i -U -1 i c i p i 2dr U
To conclude, we only need to remark that we can write

b i = b∈B(µ) M i g b with max b M i b e (M +1)n
And this proves that

-U -1 i c i b i + U -1 i c i p i = i c i V p i det(U ) + b∈B(µ) i c i V M i b b det(U ) And that max b∈B(µ) i c i V M i b 2d V max b M i b 2dC(d)e (M +1
)n e (λ 1 +ε)(d-1)n So, maybe for some M ′ M we get that

x ′ := -U -1 i c i b i + U -1 i c i p i ∈ X e M ′ n (supp µ) and d(x, x ′ ) re M ′ n .
Lemma 4.12. With the same assumptions as in proposition 4.7, there are C 0 , L such that for any M ∈ R + large enough, there are C, t ∈ R * + such that for any n ∈ N * , any r ∈]0, 1] with r

C 0 e M Ln we have that for any y ∈ T d , any x ′ ∈ X e (M +1)n (B(µ)) and any x ∈ T d with d(x, x ′ ) r,

(µ * n ({g ∈ G|d(gx, y) r})) 2 Ce -tn + µ * n ⊗ µ * n g 1 , g 2 g 1 x ′ = g 2 x ′
Proof. To simplify our notations, we set B = B(µ) and F = F (µ). let x, x ′ , y ∈ T d as in the proposition. By definition of X Q (B), there is

(M v ) ∈ M d (Z) B with max M v Q, there is p ∈ Z d and q ∈ N * with |q| Q such that x ′ = p + b∈B M b b q
Let, for any ε ∈ R * + and M ∈ N,

G * := (a, b) ∈ G a e (λ 1 +ε)n et b ∈ X e (M +1)n (B)
Lemmas 4.10 and 4.9 prove that for any ε ∈ R * + and any M ∈ R + large enough, there are C, t ∈ R * + such that for any n ∈ N,

µ * n (G * ) 1 -Ce -tn
Let's compute

I n (x, y) : = (µ * n ({g ∈ G|d(gx, y) r})) 2 = G 2 1 B(y,r) (g 1 x)1 B(y,r) (g 2 x)dµ * n (g 1 )dµ * n (g 2 ) 2µ * n (G * ) + G 2 1 G * (g 1 )1 G * (g 2 )1 d(g 1 x,g 2 x) 2r dµ * n (g 1 )dµ * n (g 2 ) 2Ce -tn + G 2 1 G * (g 1 )1 G * (g 2 )1 d(g 1 x,g 2 x) 2r dµ * n (g 1 )dµ * n (g 2 )
Moreover, for g 1 = (a 1 , b 1 ) and g 2 = (a 2 , b 2 ), we have that

d(g 1 x ′ , g 2 x ′ ) d(g 1 x ′ , g 1 x) + d(g 1 x, g 2 x) + d(g 2 x, g 2 x ′ ) a 1 r + d(g 1 x, g 2 x) + a 2 r
And this proves that

I n (x, y) 2Ce -tn + G 2 1 G * (g 1 )1 G * (g 2 )1 d(g 1 x ′ ,g 2 x ′ ) 3re (λ 1 +ε)n dµ * n (g 1 )dµ * n (g 2 )
To conclude, we only need to prove that, under the diophantine condition, if x ′ ∈ X e (M +1)n , g 1 , g 2 ∈ G * are such that d(g 1 x ′ , g 2 x ′ ) 3re (λ 1 +ε)n then g 1 x ′ = g 2 x ′ . To do so, remark that if x ′ ∈ X e (M +1)n (B) and g = (a, b) ∈ G * , alors, ax ′ + b ∈ X 2e (M +1+λ 1 +ε)n (B) Thus, we have that (g 1 -g 2 )x ′ ∈ X 4e (M +1+λ 1 +ε)n (B) and that d((g 1 -g 2 )x ′ , 0) 3re (λ 1 +ε)n .

In particular, there is q ∈ N * with q 4e (M +1+λ 1 +ε)n such that q(g 1 -g 2 )x ′ is a sum of elements of b multiplied on the left by matrices of norm smaller than (4e (M +1+λ 1 +ε)n ) 2 and d(q(g 1 -g 2 )x ′ , 0) |q|3re (λ 1 +ε)n 12re (M +1+2λ 1 +2ε)n

So, as F is (C, L)-diophantine, according to lemma 4.8, there are constants C ′ , L such that if

12re (M +1+2λ 1 +2ε)n C ′ (4e (M +1+λ 1 +ε)n ) 2L
then we have that qg 1 x ′ = qg 2 x ′ . But, this proves that g 1 x ′ = g 2 x ′ + p q for some p ∈ Z d . And

d p q , 0 = d(g 1 x ′ , g 2 x ′ ) 3re (λ 1 +ε)n
So, if 1 |q| > 3re (λ 1 +ε)n , we have that p q = 0 and so, g 1 x ′ = g 2 x ′ .

• For any

x ∈ V ω i \ V ω i+1 , lim n 1 n ln g n . . . g 1 x = Λ i
We call Lyapunov exponents the paramaters Λ 1 , . . . , Λ r and we note

λ 1 = • • • = λ m 1 = Λ 1 , λ m 1 +1 = • • • = λ m 1 +m 2 = Λ 2 , etc.
However, if x ∈ V, this theorem doesn't say anything on the behavior of g n . . . g 1 x for some generic (g n ) ∈ G N because we have no information on the sequences (g n ) such that x ∈ V (gn) i

. To avoid this problem, we usually assume that the subgroup of G spanned by the support of µ acts irreducibly on V (it doesn't fix any non-trivial subspace of V). And in this case, Furstenberg proved the Theorem A.2 ([BL85]). Let µ be a borelian probability measure on G having a momen tof order 1 and whose support generates a group acting irreducibly on V.

Then, for any x ∈ V \ {0},

1 n ln g n . . . g 1 x -→ λ 1 a.e.
This irreducibility assumption is not good enough for us since we will identify SL

d (R)⋉ R d with the subgroup SL d (R) R d 0 1
of SL d+1 (R) whose action on R d+1 is not irreducible.

A first important case of reducible actions on V is when the support of µ generates a group Γ 1 * 0 Γ 2 where Γ i < SL(V i ) with V 1 ⊕ V 2 = V and Γ i acts irreducibly on V i . Indeed, in this case, we can study the action on V 1 and on V 2 to get the one on V. This motivates the following Definition A.3. Let µ be a borelian probability measure on GL(V).

We say that some subspace W of V is adapted to µ if it is proper, invariant by the subgroup of GL(V) spanned by the support of µ and if there are ∆

1 > ∆ 2 ∈ R such that • For any x ∈ V/W \ {0}, 1 n ln g n . . . g 1 x -→ ∆ 1 a.e. • For any x ∈ W \ {0}, lim sup 1 n ln g n . . . g 1 x ∆ 2 a.e.
This definition is only useful since there is always an adapted subspace.

Theorem A.4 ([FK83] or [START_REF] Hennion | Loi des grands nombres et perturbations pour des produits réductibles de matrices aléatoires indépendantes[END_REF]). Let µ be a borelian probability measure on GL(V) having a moment of order 1.

Then there is some subspace W of V that is adapted to µ.

This theorem proves that we can always block-triangularize the group G µ spanned by the support of µ. Indeed, we can find by induction ∆

1 > • • • > ∆ s ∈ R and a flag V = W 1 ⊃ • • • ⊃ W s+1 := 0 adapted to µ : W i is G µ -invariant and for any i and any x ∈ W i /W i+1 \ {0}, (A.1) 1 n ln g n . . . g 1 x -→ ∆ i a.e.
The flag that we obtain in this way is included in the flag given by Oseledec's theorem (it means that {W i } ⊂ {V i } and that {∆ i } ⊂ {Λ i } with ∆ 1 = Λ 1 ) but it has the advantage of being invariant and the convergence in equation (A.1) gives us Furstenberg's law of large numbers without any irreducibility assumption.

We are going to precise the convergence in equation (A.1) through a non-concentration inequality that we state in next Theorem A.5. Let µ be a borelian probability measure on GL(V) having an exponential moment.

Then, for any ε ∈ R * + , there are C, t ∈ R * + such that for any n ∈ N,

µ * n g ∈ GL(V) 1 n ln g -Λ 1 ε Ce -tn
Moreover, if W is adapted to µ then, for any x ∈ V and any n ∈ N,

µ * n g ∈ GL(V) e (Λ 1 -ε)n d(x, W) gx e (Λ 1 +ε)n x 1 -Ce -tn
where we noted

d(x, W) = inf y∈W x -y
To prove this theorem, we first prove the following Lemma A.6. Let µ be a borelian probability measure on GL(V) having an exponential moment.

Let

∆ 1 > • • • > ∆ s ∈ R and V := W 1 ⊃ • • • ⊃ W s+1 := {0}
be the flag adapted to µ and given by induction by theorem A.4.

Then for any ε ∈ R * + , there are C, t ∈ R * + such that for any n ∈ N and any x ∈ V\{0},

µ * n g ∈ GL(V) ∆ s -ε 1 n ln gx x ∆ 1 + ε 1 -Ce -tn
Proof. The proof of this lemma is an adaptation of the proof of proposition 3.2 in [START_REF] Benoist | Central limit theorem for linear groups[END_REF] where Benoist and Quint only have polynomial moments. First, for g ∈ G and X = Rx ∈ P(R d ), we set

σ(g, X) = ln gx x , ϕ(X) = G σ(g, X)dµ(g) et σ ′ (g, X) = σ(g, X) -ϕ(X)
Then, for any X = Rx ∈ P(R d ) and any sequence (

g n ) ∈ GL(V) N , noting X k = g k . . . g 1 X, we have that ln g n . . . g 1 x x = n-1 k=0 σ(g k+1 , X k ) = n k=1 σ ′ (g k+1 , X k ) + n-1 k=0 ϕ(X k ) Now, let M n = n-1 k=0 σ ′ (g k+1 , X k ). We can compute E [M n+1 -M n |X 0 , . . . , X n ] = E σ ′ (g n+1 , X n ) X 0 , . . . , X n = G σ ′ (g, X n )dµ(g) = 0
This proves that M n is a martingale. Moreover, for any ε ∈ R * + , E e ε|M n+1 -Mn| X 0 , . . . , X n = G e ε|σ ′ (g,Xn)| dµ(g)

And the inequality

-ln g -1 σ(g, X) = ln gx x ln g
shows that E e ε|M n+1 -Mn| X 0 , . . . , X n G e 2ε ln max( g , g -1 ) dµ(g) And so, as µ has an exponential moment, there is ε ∈ R * + and some constant C 0 such that for any X ∈ P(V) and any n ∈ N, E X e ε|M n+1 -Mn| X 0 , . . . , X n C 0 a.e.

Thus, according to the non-concentration inequality for martingales (see theorem 1.1 in [START_REF] Liu | Exponential inequalities for martingales and asymptotic properties of the free energy of directed polymers in a random environment[END_REF]), for any ε ∈ R * + , there is C, t ∈ R * + such that for any X ∈ P(V) and any n ∈ N, P X (|M n | εn) Ce -tn (it is important to remark that the constants C, t don't depend on X but only on ε and C 0 ).

To conclude, we only need to study n-1 k=0 ϕ(X k ). To do so, we just proved (using Borel-Cantelli-s theorem) that 1 n M n -→ 0 a.e.

Moreover, by definition of ∆ 1 , . . . , ∆ s and W 1 , . . . , W s , we have that for any X ∈ P(V),

∆ s lim inf n 1 n n-1 k=0 σ(g k+1 , X k ) lim sup n 1 n n-1 k=0 σ(g k+1 , X k ) ∆ 1 a.e.
This proves that

∆ s lim inf n 1 n n-1 k=0 ϕ(X k ) lim sup n 1 n n-1 k=0 ϕ(X k ) ∆ 1 a.e.
And so, for any stationary probability measure ν on P(V),

∆ s ϕdν = lim n E x 1 n n-1 k=0 ϕ(X k )dν(x) ∆ 1
Finally, using proposition 3.1 of [START_REF] Benoist | Central limit theorem for linear groups[END_REF], we get that for any ε ∈ R * + , there are C, t ∈ R * + such that for any n ∈ N and any X ∈ P(R d ),

P X ∆ s -ε 1 n n-1 k=0 ϕ(X k ) ∆ 1 + ε Ce -tn
And this finishes the proof of the lemma.

End of the proof of theorem A.5. We refer to the proof of proposition 4.1 in [START_REF] Benoist | Central limit theorem for linear groups[END_REF]. First, remark that for any basis (v 1 , . . . , v d ) of V there is a constant C such that for any

g ∈ GL(V), 1 C gv 1 g C max i∈[1,d] gv i
And so, the non-concentration inequality for ln gv v for any v ∈ V \ {0} implies the one for ln g .

Then, remark that according to lemma A.6, for any ε ∈ R * + , there are C, t ∈ R * + such that for any x ∈ V and any n ∈ N, µ * n g ∈ GL(V) gx > e (Λ 1 +ε)n x Ce -tn

We endow V/W with the norm

x V/W := inf y∈W x -y
Then, we have that for any x ∈ V,

x d(x, W) = πx V/W
where π is the projection onto V/W and, by definition, since W is adapted to µ, for any x ∈ V/W \ {0}, 1 n ln g n . . . g 1 x V/W -→ Λ 1 a.e.

This proves that {0} is adapted to the image of µ in GL(V/W). And so, according to lemma A.6, for any ε ∈ R * + , there are C, t ∈ R * + such that for any n ∈ N and any x ∈ V/W \ {0},

µ * n g 1 n ln gx x -Λ 1 ε Ce -tn
And this proves that for any n ∈ N and any x ∈ V, µ * n g gx e (Λ 1 -ε)n d(x, W) Ce -tn And this finishes the proof of the theorem.

We end this section with the study, for a borelian probability measure µ on SL d (R) ⋉ R d , of the translation part b of the µ * n -generic elements g = (a, b). The aim is to prove that if we make some assumptions on µ, for any n, with large µ * n -probability, an element g = (a, b) ∈ SL d (R) ⋉ R d is such that b ≈ e Λ 1 n .

To do so, we wirst compare the Lyapunov exponents of µ and of it's projection on SL d (R) in next Lemma A.7. Let µ be a borelian probability measure on SL d (R) ⋉ R d having an exponential moment and let µ 0 be the projection of µ onto SL d (R).

See µ as a probability measure on SL d+1 (R) and define Λ 1 (µ) this way. Then, Λ 1 (µ) = Λ 1 (µ 0 )

Proof. This way, for any ε ∈ R * + , there is N ε such that for any n ∈ N with n N ε , e (Λ 1 (µ)-ε)n g n . . . g 1 , g 2n . . . g n+1 e (Λ 1 (µ)+ε)n and, a n . . . a 1 , a 2n . . . a n+1 e (Λ 1 (µ 0 )+ε)n Thus, we have that for any ε ∈ R * + and any large enough n, e 2(Λ 1 (µ)-ε)n g 2n . . . g 1 max e 2(Λ 1 (µ 0 )+ε)n , e (Λ 1 (µ)+Λ 1 (µ 0 )+2ε)n + e (Λ 1 (µ)+ε)n

This proves that for any ε ∈ R * + , 2(Λ 1 (µ) -ε) max(2Λ 1 (µ 0 ) + ε, Λ 1 (µ) + Λ 1 (µ 0 ) + 2ε) And so, we get that 2Λ 1 (µ) max(2Λ 1 (µ 0 ), Λ 1 (µ) + Λ 1 (µ 0 )) Finally, as we already proved that Λ 1 (µ 0 ) Λ 1 (µ), the previous inequality actually is an equality and we get the expected result.

Until now, we didn't say anything on the positivity of Λ 1 . If µ is a measure on SL(V), then, as for µ-a.e. g ∈ G, det(g) = 1, we have that λ 1 + • • • + λ dim(V) = 0 and so, λ 1 = 0 if and only if for any i, λ i = 0.

To get conditions that ensure that λ 1 > 0, we will say that a subgroup H of SL d (R) is strongly irreducible if it doesn't fix any non trivial finite union of subspaces of R d .

We remind the following result Theorem A.8 (see [START_REF] Bougerol | Products of random matrices with applications to Schrödinger operators[END_REF] or [Gui81]). Let µ be a borelian probability measure on SL(V) having a moment of order 1 and such that the subgroup spanned by the support of µ is strongly irreducible and non-compact.

SL d (R)
ln g dµ(g) < +∞

Then, Λ 1 > 0.

Corollary A.9. Let µ be a borelian probability measure on SL d (R) ⋉ R d having an exponetial moment and that is not concentrated on SL d (R) ⋉ {0}. Assume that the projection onto SL d (R) of the subgroup spanned by the support of µ is strongly irreducible and non-compact. Then, for any ε ∈ R * + , there are C, t ∈ R * + such that for any n ∈ N and any x ∈ R d ,

µ * n g ∈ SL d (R) ⋉ R d 1 n ln 1 + gx 1 + x -Λ 1 ε Ce -tn
Proof. We see µ as a probability measure on SL d+1 (R) and we are going to prove that the subspace W adapted to µ and given by theorem A.4 is {0}.

First, since the projection of supp µ on SL d (R) spans a group G µ that acts strongly irreducibly and non-compactly on R d , the only subspaces of R d+1 that can be invariant by supp µ are R d+1 , Vect(e 1 , . . . e d ), Vect(e d+1 ) and {0}. But, assuming that supp µ is not a subset of SL d (R) ⋉ {0} implies that Vect(e d+1 ) is not invariant by the group spans by the support of µ. Moreover, according to theorem A.8, there is Λ 1 ∈ R * + such that for any x ∈ Vect(e 1 , . . . , e d ) \ {0}, 1 n ln g n . . . g 1 x -→ Λ 1 a.e.

Then, for any x ∈ R d+1 \ Vect(e 1 , . . . , e d+1 ), we have, according to lemma A.7 that lim sup n 1 n ln g n . . . g 1 x Λ 1

So we also have that W = Vect(e 1 , . . . , e d ) and, as W is proper, we have that W = {0}. Thus, according to lemma A.5, for any ε ∈ R * + , there are C, t ∈ R * + such that for any x ∈ R d+1 \ {0},

µ * n g ∈ SL d (R) ⋉ R d 1 n ln gx x -Λ 1 ε Ce -tn
And in particular, with x = x 0 + e d+1 for x 0 ∈ Vect(e 1 , . . . , e d ) we get the expected result.

  Lemma 2.7. Let µ be a borelian probability measure on G and µ 0 it's projection on G 0 . Denote by P the Markov operator associated to µ and by P 0 the one associated to µ 0 .Then, for any c ∈ Z d , any n ∈ N and any L ∈ N,T d |P n e c | 2L dν T d |P n 0 e c | 2L dνWhere, for c ∈ Z d , e c is the function defined for x ∈ T d by e c (x) := e 2iπ c,x

  Definition 4.2 (Diophantine subsets of T d ). Let d ∈ N * and B ⊂ T d a finite subset.We that that B is (C, L)-diophantine if for any non zero(M b ) ∈ Z B , d b∈B M b b, 0 C max b |M b | L ⇒ b M b b = 0More generally, we say that B is diophantine if it is (C, L)-diophantine for some C, L ∈ R * + . Remark 4.3. With this definition, a diophantine subset can contain rational points.

Example

  elements of F multiplied by integers that are smaller than d|B| max b M b . In other words, for any coefficient of b M b b, we get a sum f ∈F L f f with |L f | d|B| max b M b and d

  (4.1) B(µ) := {b|(a, b) ∈ supp µ} and F (µ) := {coefficients of b|b ∈ B(µ)}

  First for any n ∈ N * and any ε ∈ R * + ,µ ⊗N 1 n ln g 2n . . . g n+1 -Λ 1 (µ) ε = µ ⊗N 1 n ln g n . . . g 1 -Λ 1 (µ) ε So, according to lemma A.5, 1 n ln g 2n . . . g n+1 -→ Λ 1 (µ) µ ⊗N -a.e.We can write, for any g∈ SL d (R) ⋉ R d , g = a b 0 1and if g has law µ, then a has law µ 0 . Thus,g 2n . . . g 1 = a 2n . . . a 1 a 2n . . . a n+1 n k=1 a n . . . a k+1 b k + 2n k=n+1 a 2n . . . a k+1 b k 0 1And so,, g n . . . g 1 a n . . . a 1 This proves that Λ 1 (µ) Λ 1 (µ 0 ).Let now Ω ∈ G N be such that µ ⊗N (Ω) = 1 and for any (g n ) ∈ Ω, lim n 1 n ln g n . . . g 1 = lim n 1 n ln g 2n . . . g n+1 = Λ 1 (µ) and lim n 1 n ln a n . . . a 1 = lim n 1 n ln a 2n . . . a n+1 = Λ 1 (µ 0 )

Proof. First, remark that as µ 0 is concentrated on SL d (Z), for µ 0 -a.e. g ∈ G 0 , g 1 and so, noting δ ∈ R * + such that G 0 g δ dµ 0 (g) < +∞, we have that for any M ∈ R * + and any n ∈ N,

And this finishes the proof of the first part of the lemma.

To prove the second one, take (a

This proves that n k=1 a n . . . a k+1 b k ∈ X ne M n (B(µ)).

In the sequel, we will have to control sums of the form c i a i where the a i are µ * n -generic and c i ∈ Z. To do so, we will use the Lemma 4.10 ([BFLM11]). Let µ 0 be a strongly irreducible and proximal borelian probability measure on SL d (Z) having an exponential moment.

Set

where we put c 1 = 1 -d and

Then, for any ε ∈ R * + , there are C, t ∈ R * + such that for any n ∈ N,

Proof. In [BFLM11], this lemma is not stated as we do it here but it corresponds to the lemmas 4.3, 4.6 and 7.9 and to some part of the proof of proposition 7.3.

We are now ready to prove proposition 4.7. The proof consists in two lemmas. In lemma 4.11, we study points that are far from points of X e n (B(µ)) and in lemma 4.12 we study points that are close to it.

End of the proof of proposition 4.7. According to lemma 4.11, we have that for any M ∈ R * + large enough, there are C, t ∈ R * + such that for any r ∈]0, 1], any n ∈ N and any x, y ∈ T d , if µ * n ({g ∈ G|d(gx, y) r}) Ce -tn then there is x ′ ∈ X e M n (B(µ)) such that

But, in this case, we have, according to lemma 4.12, that if

And this is what we intended to prove since

Products of random matrices

In this section, we are going to recall some of the properties of products of random matrices.

To do so, we fix some finite dimensional R-vector space V that we endow with an euclidian norm.

Let µ be a borelian probability measure on G := GL(V). We set, for any g ∈ G, N (g) = max( g , g -1 ) and we say that µ has a moment of order 1 if G ln N (g)dµ(g) < +∞ and that it has an exponential moment if there is some

Remark that there is some constant C depending only on dim(V) such that for any g ∈ SL d (V), g -1 C g dim V and so, if µ is a measure on SL(V), it is enough to ask that for some ε

We would like to study the product g n . . . g 1 where (g i ) is an iid sequence of law µ.

The first result in this direction is Oseledec's theorem :

Theorem A.1. Let µ be a borelian probability measure on G := GL(V) having a moment of order 1.

Then, there are m 1 , . . . , m r ∈ N * with i m i = dim V, there is Λ 1 > • • • > Λ r ∈ R and some measurable function from G N into the space of flags

j=i m j and such that for µ ⊗N -a.e. ω = (g

where ϑ is the shift on G N .


Petr Dokládal
email: petr.dokladal@mines-paristech.fr

Statistical Threshold Selection for Path Openings to Detect Cracks

Keywords: Mathematical morphology, parsimonious path filters, rank-max opening, a contrario model

Inspired by the a contrario approach this paper proposes a way of setting the threshold when using parsimonious path filters to detect thin curvilinear structures in images. The a contrario approach, instead of modeling the structures to detect, models the noise to detect structures deviating from the model. In this scope, we assume noise composed of pixels that are independent random variables. Henceforth, cracks that are curvilinear sequences of bright pixels (not necessarily connected) are detected as abnormal sequences of bright pixels. In the second part, a fast approximation of the solution based on parsimonious path openings is shown.

Introduction

The detection of thin, curvilinear elements is a frequent task in automated visual inspection to detect cracks. Similar applications can be found in other image processing domains to detect the blood vessels (medicine), facial wrinkles (cosmetology), neurites or DNA molecule chain (biology), roads in satellite images, or a few others. An accurate detection of such structures that are thin, curved, discontinuous and often rare and sometimes absent (in which case we want to avoid false detection) from the images is a difficult problem. In mathematical morphology the operator enhancing curvilinear, thin objects is the path opening.

However, the main difficulty to produce a binary results is to find a convenient value for the subsequent thresholding. One solution, based on the same hypothesis formulated using the a contrario model, and combined with the percolation, has been investigated by Aldea and Le Hégarat-Mascle [START_REF] Aldea | Robust crack detection for unmanned aerial vehicles inspection in an a-contrario decision framework[END_REF]. Long, thin structures are then detected as deviations from normality.

The same hypothesis of sparcity of defects is used throughout this paper. The principal contribution here is the proposition of a method of identifying parameter values such that the detected structures are perceptually significant. The principle is inspired from the idea of meaningful alignments proposed by Desolneux et al. [START_REF] Desolneux | Meaningful alignments[END_REF], detecting perceptually significant, straight segments in images. The perceptual significance stems from the Helmholtz principle stating that a perceptually significant element is improbable to occur by chance. Any perceptual significant segment is hence a deviation from randomness. The model proposed in [START_REF] Desolneux | Meaningful alignments[END_REF] is based on the hypothesis of random distribution of the orientation of the isophote 1 in noise. A perceptually significant segment is defined as a sequence of isophotes aligned with the orientation of the segment. Notice that a perceptually significant segment does not need to be contiguous.

In this work we extend the original model based on the orientation of isophotes to that of the distribution of intensity in images, and from straight segments to curvilinear structures. As well as in the case of the isophotes, the points do not necessarily need to be connected to form a perceptually significant structure, but only sufficiently densely follow each another in a sequence. This idea can be efficiently implemented using mathematical morphology that indeed possesses an operator conceived for the detection of such structures. It is derived from the original concept of the path opening, due to Buckley and Talbot [START_REF] Buckley | Flexible linear openings and closings[END_REF][START_REF] Heijmans | Path openings and closings[END_REF], and formalized in Heijmans et al. [START_REF]Path openings and closings[END_REF]. Later, Talbot and Appleton [START_REF] Talbot | Efficient complete and incomplete path openings and closings[END_REF] propose a more efficient implementation and introduce incomplete path openings robust to noise due to the capability to tolerate missing pixels. The originally exponential complexity has been reduced later to a constant by Morard et al. [START_REF] Morard | Parsimonious path openings and closings[END_REF] by limiting the search of paths to only a relevant subset of all paths in an image and using a constant-time opening algorithm for the filtering alongside these paths or a closing-opening to increase the robustnes to noise. Using closing-opening instead of opening alone does not increase the complexity, and is indeed similar to another version proposed by Cokelaer et al. [START_REF] Cokelaer | Efficient Robust d-Dimensional Path Operators[END_REF] that tolerates gaps up to some maximal admissible width.

The main contribution of the present paper is to set correct parameter values for parsimonious path filters to detect perceptually meaningful structures longer than some chosen minimal length. The morphological tool allowing to implement efficiently the above ideas is parsimonious incomplete path opening applying a 1-D rank-max-opening alongside these paths.

The meaningfulness

According to the Helmholtz principle, an object is perceived as meaningful provided it is unlikely for it to occur by chance. The complement of these structures is the background that we assume random with a priory unknown distribution.

Definition 1 (ε-meaningful event (Desolneux et al. [START_REF] Desolneux | Meaningful alignments[END_REF])). An even of type "such configuration of points has such property" is ε-meaningful if the expectation of the number of occurrences in an image of this event is less than ε.

For an event to be meaningful one needs to consider ε 1, in which case our perception is likely to see it. Notice that the ε-meaningfulness is related to the statistical p-significance.

In the following we develop a framework to detect thin, curvilinear structures in gray-scale images. These structures are perceived due to the deviation of their intensity from the normality. They are either brighter or darker. We develop the framework for bright structures; dark structures can be detected after inverting the image. In the simulated experiment Fig. 1 the sinusoidal curve -composed of closely grouped points somewhat brighter than the surrounding -is perceived as one object even though not necessarily contiguous. The difficulty to extract this structure is due to that we do not know the parameters: i) the distribution of the noise, ii) how much the curve points are brighter than the noise, iii) how densely these points populate this curve. In the remainder of this text, the ideas from Desolneux et al. [START_REF] Desolneux | Meaningful alignments[END_REF] originally applied to isophote orientation, are developed and applied to the distribution of gray values. We use identical notation wherever possible and refer the reader for details to [START_REF] Desolneux | Meaningful alignments[END_REF] for additional details.

In [START_REF] Desolneux | Meaningful alignments[END_REF] the distribution of orientation of the isophotes in noise is uniformly distributed on [0, 2π]. It is independent of the values of the pixels, provided the pixels are independent, random variables. The detection of curvilinear structures can not use alignment of isophotes since the local orientation is not constant. We therefore extend the ideas from [START_REF] Desolneux | Meaningful alignments[END_REF] to the distribution of pixel values in the image. Compared to the distribution of isophotes, the distribution of pixel values not only does not obey the uniform law but is even often unknown. Also an isophote is either aligned or misaligned with the segment. It is a boolean property. Analogously, a "pixel is brighter than" is also boolean but requires some threshold. On the other hand, the statement that "a pixel is bright" does not require a threshold and is not boolean any longer since it can be true to various degrees of truth. Consequently, a curvilinear bright structure will be perceptually meaningful depending of two properties, its brightness and its length. For the same perception stimulus a shorter structure must be brighter than a longer one. Consequently, even a single, isolated pixel in noise can be perceptually meaningful provided it is exceptionally bright. Compared to that, one isophote in noise can never become meaningful.

Let f denote a realization, i.e. a gray-scale image, on a domain M × N ⊂ Z 2 , of a random variable following the law F , assumed unknown. The complementary cumulative distribution function

F (α) = P [f (x) > f α ] = p (1)
gives the probability p that the value of pixel x exceeds the quantile α.

Let C be a curvilinear structure formed by a sequence of l connected 2 points {x 1 , x 2 , . . . , x l }. Let X i be a random variable equal to 1 if f (x i ) > f α and 0 otherwise. Let S l =X 1 + X 2 + . . . + X l , with 0 ≤ S l ≤ l, be a random variable counting in C the number of points brighter than f α . Provided X i are independent we have the probability that exactly k pixels in the curve C exceed the intensity f α given by the binomial distribution

P [S l = k] = l k p k (1 -p) l-k

Number of False alarms

A path is generated by a connectivity class given by a graph. The vertices of the graph represent the image pixels, and the edges connect pixels that are connected. The graph is directed and acyclic. A path in an image is therefore a path in the graph. The connectivity is assumed translation invariant, except image borders. Suppose every vertex is connected to n neighbors (with n=3 in the example Fig. 6). There are therefore n l-1 l-pixel-long paths starting in any pixel in Z 2 . In a N ×N image, the number of possible starting points for a l-pixel-long path (generated by either of these graphs) is (N -l) 2 . Hence, the number of l-pixel-long paths generated by either of the connectivity graphs in Fig. 6 can be approximated by

Π(l; N ) = (N -l) 2 n l-1
Given the exponential rule we drop the multiplicative factor given by the number of possible rotations of the graph. Following the idea from [START_REF] Desolneux | Meaningful alignments[END_REF] we are interested in detecting structures "longer than" rather than "exactly as long as" since the exact length is not known. We set up the detection threshold by decreasing the number of false alarms to below an acceptable (arbitrary but small enough) value.

In statistical terms the presence of a meaningful structure is a test and the number of possible paths along which it can occur is the number of trials. The probability of occurrence multiplied by the number of tests gives the expectation of false alarms NFA

NFA[k, l] = Π(N )P [S l ≥ k] = l i=k Π(i, N ) l i p i (1-p) l-i (2)
The upper length limit l in the sum being unknown we let it equal to the length of the diagonal of the image

√ 2N . Comparing NFA to ε NFA[k, l] ≤ ε (3)
is equivalent to saying whether the structure is ε meaningful.

Intensity threshold

The first thing one can do is to set k=l in eq. 2 and isolate p as a function of the length l

p ≤ l ε Π(l)e l-1 (4)
Illustrated in Fig. 2a as a function of the length it shows that shorter structures, to be meaningful, must contain points that are less probable, that is more deviating from the normality. If the law of the intensity distribution in an image is known and invertible eq. 4 can be used to determine the intensity threshold to detect meaningful structures. If the law is unknown or not invertible, a rank-order filter ξ 1-p in a sliding window with the rank 1-p will select points with intensity above the quantile level 1-p, that is those with probability less or equal p. Example: The intensity threshold corresponding to the probability p for a normal law N(µ, σ 2 ), with µ=0, σ=1, is given by Fig. 2b. It says that even an isolated point becomes meaningful provided its intensity exceeds 3.5σ. Long, connected structures are meaningful as long as their intensity remains above 0.5σ of the noise.

Isolating k, with k ≤ l, from eq. 2 allows saying in how many pixels out of a sequence of l connected pixels the intensity must exceed the p-th quantile value for the structure to become meaningful. This means that we search for structures that are composed of bright, not necessarily connected, sequences of points.

k(l) = min{k ∈ N, NFA[k, l] ≤ ε} (5)
Given some l, eq. 5 can be directly solved for k. In a typical image, e.g. 512×512 pixels, the number of paths Π l is a large number, given that it increases exponentially with l, itself bounded by the length of the diagonal of the image.

Consider a collection of L independent, random points. Let p denote the probability that the intensity of a point exceeds some threshold. The probability that in k points out of L the intensity exceeds some fixed threshold follows the binomial law, see illustration Fig. 3a for p = 0.1. If these L points form a path in a Z 2 grid there are many trials to this test. There are 3 L-1 paths generated by a three-connected graph (either of the graphs in Fig. 6) that start in every point of this grid. This gives a huge number on unbounded (or large) supports, see Fig. 3b. The expectation of false alarms NFA is given Fig. 4a. We search for a configuration where NFA in a given image remains low (condition eq. 3) that is the smallest k where the tail of the distribution remains under ε. See Fig. 4b for k expressed as a function of L, for p=0.05. Solving eq. 3 requires counting the number of paths Π(i, N ) in eq. 2. Exact counting not being easy on bounded supports, we provide a convenient approximation. Recall that a point in Z 2 is an origin for 3 L-1 L-pixel-long paths. However, restricting this estimation to bounded supports by multiplying this number by the number of points in a bounded support gives an unacceptably strong overestimation. We propose another, more precise approximation.

A pair of points (a, b) in Z 2 is connected by a path which is either i) a line segment running straight from a to b or ii) a path oriented from a to b and containing as many right turns as left turns. The count of such paths is given by

L k=1 L k L -k k
This number multiplied by the number of possible points L segments distant each from the other. This approximation provides a sufficiently precise estimation of paths on bounded supports.

Next, we fix some fixed fraction r=const., r ∈ R + , 0 < r ≤ 1, for having k ∈ N + bright pixels in a sequence k= rl 0 , with . meaning rounding to nearest integer. We solve eq. 2 for the lowest p satisfying the condition on the meaningfulness eq. 3. Observe in Fig. 5 the values of p that we obtain for various r. Notice that the curve for r=1 coincides with the one given by Fig. 2a (that of a complete path). Observe that for longer curves and higher r lower threshold suffices to ensure meaningfulness. These probabilities allow obtaining correct threshold values for the rank filter ξ r , as explained below.

Efficient Implementation with morphological tools

We have seen that an obvious obstacle in the search of efficient implementation is the overwhelming number of trials to test in an image. The test "intensity in k out of l points in a path exceeds a value" done alongside all paths is computationally very intensive; the number of paths in an image increases linearly with the image size and exponentially with the length of the paths. Testing even a much smaller number of trials in the case of straight lines in the algorithm in [START_REF] Desolneux | Meaningful alignments[END_REF], takes seconds on a recent computer [START_REF] Grompone Von Gioi | LSD: a Line Segment Detector[END_REF]. In what follows we present a convenient fast approximation of the solution using path openings.

Given some function f : D → V , the morphological opening of f by a structuring element B ⊂ D defined by

γ B f = sup{B(u) + v ≤ f ; (u, v) ∈ D × V } (6)
is a supremum of all translates of B that do not exceed f , where B(u)+v denotes B translated horizontally by u and vertically by v. That is, for some x ∈ D, there is a translate B(u) such that for any y ∈ B(u), f (y) ≥ γ B f (x). Defining g = {x | γ B f (x)>th}, then x ∈ g means that there is some B(u), x ∈ B(u) that f (y) > th, for all y ∈ B(u). For a connected B with |B| = k, g indicates where f > th larger than k. In 1-D these subdomains are intervals.

In presence of noise the strict inclusion of B is likely to fail. This motivated the introduction of the rank-max opening, proposed by Ronse [START_REF] Ronse | Erosion of narrow image features by combination of local low rank and max filters[END_REF] and later described in Ronse and Heijmans [START_REF] Ronse | The algebraic basis of mathematical morphology : II. openings and closings[END_REF], defined as the supremum of openings by all subsets of cardinal k of a chosen structuring element

B γ B,k = i {γ Bi | B i ⊆ B, card(B i ) = k} (7)
where 1 ≤ k ≤ n with n=card(B). It acts as an opening tolerating n -k missing pixels. Note that r, in r = k/l, is to be understood as the rate of pixels that are required to be intensive, and inversely 1 -r the rate of tolerated missing pixels.

A naive implementation of eq. 7 requires computing n k openings which is prohibitive for most applications. Instead of the naive implementation, Heijmans [START_REF] Heijmans | Morphological image operators[END_REF] shows that eq. 7 can be efficiently implemented by using this identity

γ B,k = 1l ∧ (δ B ξ B,n-k+1 ) (8)
where δ B is the conjugate dilation with B(x)=B(-x) and ξ B,r a rank order filter ξ B,r f (x) = r-th largest value of {f (y), y ∈ B(x)}

Isolating in some original image f perceptually significant sequences of pixels longer than L can be done by thresholding the rank-max opening γ L,k > ξ r . An approximate solution can be obtained using parsimonious path openings Morard et al. [START_REF] Morard | Parsimonious path openings and closings[END_REF] allowing to test only a fraction of all trials. Once the paths are isolated, both the conjugate dilation and the rank filter implemented by definition are reasonably fast on 1-D data. For time-critical applications one can use fast, O(1) algorithms for both, e.g. [START_REF] Dokládal | Computationally efficient, one-pass algorithm for morphological filters[END_REF] for dilation and [START_REF] Perreault | Median filtering in constant time[END_REF] for the rank order filter. We apply the morphological 1-D rank-max opening alongside the paths with statistically obtained parameters to detect cracks as statistically meaningful structures in images. The following paragraph shortly recalls the essentials.

Let f : D → V , with e.g. V = R + be an image such that D is a rectangular subset of Z 2 . Suppose D equipped with a translation-invariant, acyclic connectivity graph G : D → P(D), with P denoting the powerset. We say a sequence π

= (x 1 , x 2 , . . . , x n ), n ∈ N, of points is a path if x i+1 ∈ G(x i ) for all 1 ≤ i ≤ n-1.
The path length is n. Points x 1 and x n are its starting and end points. The starting points are on the edges of the image and each path goes to the facing image edge so that the mean intensity is maximized alongside. The set of the paths generated by G in this way is denoted by Π G . The opening is applied alongside all paths in Π G . The complement of Π G in spt(f ) is set to 0.

Results

We illustrate the method on the detection of road cracks. Prior to the detection of cracks, the original image -where cracks appear dark -is inverted so that an opening can be used to detect the cracks. Notice that even though the background texture is non-stationary no other preprocessing is needed as long as the rank order filter is applied in a sliding window. This image has a resolution of 1 mm/pixel in both directions. We choose to detect cracks longer than L = 100 mm. See Fig. 7 for the results.

Notice that discontinuous cracks are still detected but appear as composed of segments that are not necessarily all longer than the parameter L. This occurs due to the non-increasingness of the opening (ensured by ∧ in eq. 8).

Regarding the timing: the processing time of an 11294x4096 image is ∼8 s for the rank filter, and ∼4 s the parsimonious rank-max path opening on a 2.70GHz Intel i7 CPU (without using the CPU's parallelism capabilities).

Properties and discussion

The result of rank-max path opening is not necessarily composed of connected paths the length of which is equal or greater than L as for path openings. Indeed, the tolerance to noise of rank-max openings makes the result disconnected if the object in the input image is disconnected (as in the simulation Fig. 1 and the road cracks Fig. 7). The rank-max opening may also create small spurious branches due to local random noise arrangements. As a direct consequence, the results obtained with a sequence of increasing lengths are not strictly decreasing (in the sense "being included") though global, non-strict decreasing is observed.

In presence of dense grouping of more cracks the threshold at some quantile is biased upwards which counterbalances the sensitivity. Nonetheless, this comes somewhat in relation with the perception law saying that isolated structures are perceived individually whereas groupings are perceived as a whole first.

One, well known, limitation comes from the path openings. Their underlying acyclic graph puts a limit on the tortuosity of the structures. The length of excessively tortuous structures becomes underestimated. This drawback is however widely accepted since counter-balanced by the linear computational complexity of this algorithm and rapidity even on large images.

Fig. 1 .

 1 Fig. 1. a) a curvilinear structure in noise N (µ, σ 2 ), b) points above the 88.2 quantile, c) the detected structure with L=20, k=16 (see below for parameters setting).

Fig. 2 .

 2 Fig. 2. a) the probability of point as function of the length, b) the threshold obtained as the quantile level corresponding to p for law N(µ, σ 2 ), for µ=0, σ=1.

Fig. 3 .

 3 Fig. 3. (a) Probability mass function of the binomial law, (b) Number of 3-connected paths on Z 2 for L ≤ 50.

Fig. 4 .

 4 Fig. 4. (a) NFA as a function of k. In red: Choosing k for = 0.01. (b) Minimum k ensuring meaningfulness as a function of the length L and parametrized by p.

Fig. 5 .

 5 Fig. 5. The pixel probability p as a function of the sequence length L for various fixed fill fraction levels r.

Fig. 6 .

 6 Fig. 6. An example of a commonly used connectivity graph (a), and its rotations (b-d)

Fig. 7 .

 7 Fig. 7. Detection of road cracks. (top) original, 11294x4096 image, (bottom) the cracks obtained for L ≥ 100, k = 65 and r = 0.15. The sliding window is a 100×100 rectangle.