Julien Worms
email: worms@math.uvsq.fr

Rym Worms
email: rym.worms@univ-paris12.fr

Estimation of second order parameters using Probability Weighted Moments

Keywords: AMS Classification : Primary 62G32; Secondary 60G70 Extreme values, Domain of attraction, Excesses, Generalized Pareto Distribution, Probability-Weighted Moments, Second order parameter, Third order conditions

The P.O.T. method (Peaks Over Threshold) consists in using the generalized Pareto distribution (GPD) as an approximation for the distribution of excesses over a high threshold. In this work, we use a refinement of this approximation in order to estimate second order parameters of the model using the method of probability-weighted moments (PWM): in particular, this leads to the introduction of a new estimator for the second order parameter ρ, which will be compared to other recent estimators through some simulations. Asymptotic normality results are also proved. Our new estimator of ρ looks especially competitive when |ρ| is small.

Introduction

In statistical extreme value theory, on is often interested by the estimation of the far tail of a distribution. The quality of this estimation especially depends on knowledge about the so-called tail index γ = γ(F ) of the underlying model F , which is the shape parameter of the Generalized Pareto Distribution (GPD) with distribution function (d.f.)

G γ,σ (x) =    1-1 + γx σ -1 γ , for γ = 0 1 -exp -x σ , for γ = 0.
The GPD appears as the limiting d.f. of excesses over a high threshold u defined for x ≥ 0 by

F u (x) := P(X -u ≤ x | X > u)
, where X has d.f. F .

It was established in Pickands' and Balkema and de Haan's results (see [START_REF] Pickands | Statistical inference using extreme order statistics[END_REF] and [START_REF] Balkema | Residual life time at a great age[END_REF]) that F is in the domain of attraction of an extreme value distribution with shape parameter γ if and only if lim

u→s+(F ) sup 0<x<s+(F )-u F u (x) -G γ,σ(u) (x) = 0
for some positive scaling function σ(u) depending on u, where s + (F ) = sup{x : F (x) < 1}. Since the far tail of the unknown underlying distribution F is closely tied to the d.f. of excesses over a high threshold, accurate modelisation of the distribution of excesses is an important topic.

In what follows, we suppose that F is twice differentiable and that its inverse F -1 exists. Let V and A be the two functions defined by V (t) = F -1 (e -t ) and A(t) = V ′′ (ln t) V ′ (ln t) γ.

1

We suppose the following first and second order conditions hold (RV ρ below stands for the set of regularly varying functions with coefficient of variation ρ) : lim t→+∞ A(t) = 0 (1.1) A is of constant sign at ∞ and there exists ρ ≤ 0 such that |A| ∈ RV ρ , (

Under these assumptions, it is proved in [START_REF] Raoult | Rate of convergence for the generalized Pareto approximation of the excesses[END_REF] that if (u n ) is a sequence of thresholds such that u n → s + (F ) as n→ ∞, then we have the following development

F un (σ n y) -G γ (y) = a n D γ,ρ (y) + o(a n ), as n → +∞, (1.3)
for all y, where G γ (y) := 1 -G γ, 1 (y), The idea of the present work is that, according to the result (1.3), G γ,σ(u) (x) + a n D γ,ρ (x/σ(u)) is a better approximation of F u (x) than G γ,σ(u) (x) alone : this is the starting point of our method for the estimation of the second order parameters a n and ρ.

σ n := σ(u n ) = V ′ V -1 (u n ) , a n := A e V -1 (
The estimation of ρ is of great importance (for instance for the determination of the optimal sample fraction needed in the estimation of the tail index or of high quantiles) and has been studied by several authors during the last 15 years. Many of the existing estimators of ρ are based on functionals of the moment statistics

M (j) n (k n ) = k n -1 kn i=1 (ln X n-i+1:n -ln X n-kn:n ) j
, where X i:n denotes the ith ascending order statistic associated to a sample (X 1 , . . . , X n ) of d.f. F , and k n is the number of excesses retained for the estimation (where k n → ∞ but slower than n). We can cite those introduced in [14], [START_REF] Drees | Selecting the optimal sample fraction in univariate extreme value estimation[END_REF], [START_REF] Peng | Asymptotically unbiased estimator for the extreme value index[END_REF], [START_REF] Gomes | Semi-parametric estimation of the second order parameter in statistics of extremes[END_REF], [START_REF] Fraga Alves | A new class of semi-parametric estimators of the second order parameter[END_REF], [START_REF] Fraga Alves | Estimation of the parameter controlling the speed of convergence in extreme value theory[END_REF] and [START_REF] Ciuperca | Semi-parametric estimation for heavy-tailed distributions[END_REF].

The estimation of a n can also be very useful. For instance, if we consider the estimation of the tail index γ by the PWM estimator, it was proved in [START_REF] Diebolt | Asymptotic behaviour of the probability-weighted moments and penultimate approximation[END_REF] that the main component of the bias of this estimator is of order a n . An estimation of the latter parameter could thus be used to reduce this bias. Moreover, it was proved in [START_REF] Worms | Penultimate approximation for the distribution of the excesses[END_REF] that, in the case ρ = 0, the GPD G γ+an,σn is a better approximation of the distribution of the excesses F u than G γ,σn ; this is called the penultimate approximation, and the estimation of a n is important in this framework.

In this work, we use the probability-weighted moments (PWM) techniques introduced by Hosking and Wallis in [START_REF] Hosking | Parameter and quantile estimation for the generalized Pareto distribution[END_REF] to estimate the second order parameters ρ and a n , as well as the scale parameter σ n . The proposed estimators are based on an "external" estimation of γ : a similar procedure was undertaken in [START_REF] Fraga Alves | Estimation of the parameter controlling the speed of convergence in extreme value theory[END_REF], as well as in [START_REF] Gomes | Asymptotically unbiased" estimators of the tail index based on external estimation of the second order parameter[END_REF] but in the reverse way (i.e. the estimator of γ was based on an external estimator of ρ).

Under conditions (1.1) and (1.2), it is known (see [START_REF] Raoult | Rate of convergence for the generalized Pareto approximation of the excesses[END_REF]) that

∀x ∈ R, lim t→+∞ V (t+x)-V (t) V ′ (t) - x 0 e γs ds A(e t ) = I γ,ρ (x). (1.4)
In order to achieve asymptotic normality results, we will need the following third order condition which specifies the rate of convergence in (1.4) :

∀x ∈ R, lim t→+∞ 1 B(e t )   V (t+x)-V (t) V ′ (t) - x 0 e γs ds A(e t ) -I γ,ρ (x)   = R γ,ρ,β (e x ), (1.5)
where R γ,ρ,β (e x ) := and the function B tends to 0 and is of constant sign at ∞ and |B| ∈ RV β , for some β ≤ 0. This condition has been introduced in [START_REF] Fraga Alves | Estimation of the parameter controlling the speed of convergence in extreme value theory[END_REF] and studied in more details in [START_REF] Fraga Alves | Third order extended regular variation[END_REF].

Remark 1 We can choose, in our regular case, B(t) := tA ′ (t) A(t)ρ (F should then be three times differentiable).

In Section 2, we introduce the new model based on (1.3) and the associated probability-weighted moments and establish the asymptotic normality of their estimators. In Section 3, we present our estimators for ρ, a n and σ n and establish their asymptotic normality, first when γ is supposed to be known and then for the unknown γ case. Section 4 contains some simulations illustrating the behaviour of our new estimator of ρ, by comparison to two other recent estimators.

2 Estimators for the Probability-Weighted Moments

Definition of the Probability-Weighted Moments

In [START_REF] Hosking | Parameter and quantile estimation for the generalized Pareto distribution[END_REF], Hosking and Wallis introduced the PWM method in order to define estimators of γ and σ n based on a sample with d.f. supposed to be an exact GPD. These estimators were obtained through a substitution method based on the following quantities, the probability-weighted moments

ν j = E(XG j γ,σn (X))
where j ∈ {0, 1} and X has d.f. G γ,σn . The results were generalized in [START_REF] Diebolt | Asymptotic behaviour of the probability-weighted moments and penultimate approximation[END_REF] to the case where the sample was only supposed to be in the domain of attraction of a GPD. In this work, more parameters are considered, and we note θ n = (γ, σ n , a n , ρ). According to the asymptotic result (1.3), we define our extended model by the distribution function

B θn (x) = G γ,σn (x) -a n D γ,ρ x σ n , for all x,
and consider the corresponding first three PWM as follows, where X has d.f. B θn ṽj = E(XB j θn (X)), for j ∈ {0, 1, 2}.

It is easy to see that ṽj = +∞ 0

(1 -B θn (x)) j+1 j + 1 dx.

Note that for all the PWM and their estimators, the subscript n is ommited in order to simplify the notations.

The following lemmas provide expressions of these PWM as functions of the parameters.

Lemma 1 For j ∈ {0, 1, 2}, ρ ≤ 0 and -1 < γ < 1,

ν j = σ n (j + 1)(j + 1 -γ) .
Lemma 2

ṽ0 = ν 0 + a n +∞ 0 D γ,ρ x σ n dx := v 0 ,
and, for j ∈ {1, 2},

ṽj = ν j + a n +∞ 0 G j γ,σn (x) D γ,ρ x σ n dx + o(a n ) := v j + o(a n ),
Lemma 3 For j ∈ {0, 1, 2}, ρ ≤ 0 and -1 < γ < 1, we have ṽj = v j + o(a n ) where

v j := σ n (j + 1)(j + 1 -γ) + a n σ n u j and u j := (j + 1)(j + 1 -γ)(j + 1 -γ -ρ).
In the sequel, we will use the quantities v 0 , v 1 , v 2 (rather than ṽ0 , ṽ1 , ṽ2 ) in order to estimate ρ, a n , σ n , by a classical substitution method, relying on Lemma 3 above which gives the relations between the two triplets of parameters. The proof of lemmas 2 and 3 are given in Appendices 5.1 and 5.2 respectively. That of Lemma 1 can be found in [START_REF] Diebolt | Asymptotic behaviour of the probability-weighted moments and penultimate approximation[END_REF] for j = 0, 1 : the case j = 2 is similar. According to (1.3), the distribution B θn is then likely to be a good approximation for the distribution F un of Y 1,Nn , . . . , Y Nn,Nn . This method is of the Peak-Over-Threshold (POT) type.

Remark 2 Note that N n is binomial distributed with mean n(1 -F (u n )) which will be chosen as going to infinity : consequently, N n → ∞ and N n /(n(1 -F (u n )) → 1 in probability as n→ ∞.

Definition 1 For j ∈ {0, 1, 2}, define the estimator of v j by

vj := +∞ 0 (1 -A n,un (x)) j+1 j + 1 dx,
where,

A n,un (x) = 1 N n Nn i=1 I {Yi≤x} .
It follows that, conditionnally on

N n = k n , vj := 1 j + 1 Nn i=1 1 - i -1 k n j+1 -1 - i k n j+1 Y i,kn . Let b n = B(e V -1 (un) ).
Theorem 1 Under assumptions (1.1), (1.2) and (1.5), with -1 < γ < 1/2, and if

lim n→∞ n (1 -F (u n )) a n b n = λ 1 , λ 1 ∈ R, (2.1)
lim n→∞ n (1 -F (u n )) a 2 n = λ 2 , λ 2 ∈ R, (2.2)
lim n→∞ n (1 -F (u n )) a n = ∞, (2.3)
we have, for almost all sequences k n → +∞, conditionally on

N n = k n , k n         v 0 σ n - v 0 σ n v 1 σ n - v 1 σ n v 2 σ n - v 2 σ n         d -→ N (λ 1 C, Γ) ,
where

Γ =    ((1 -2γ)(1 -γ) 2 ) -1 ((2 -γ)(1 -γ)(2 -2γ)) -1 ((3 -γ)(1 -γ)(3 -2γ)) -1 ((2 -γ)(1 -γ)(2 -2γ)) -1 ((3 -2γ)(2 -γ) 2 ) -1 ((2 -γ)(3 -γ)(4 -2γ)) -1 ((3 -γ)(1 -γ)(3 -2γ)) -1 ((2 -γ)(3 -γ)(4 -2γ)) -1 ((5 -2γ)(3 -γ) 2 ) -1    (2.4)
and

C =   c 0 γ,ρ,β c 1 γ,ρ,β c 2 γ,ρ,β   where c j γ,ρ,β = ((j + 1)(j + 1 -γ)(j + 1 -γ -ρ)(j + 1 -γ -ρ -β)) -1 . Proof of Theorem 1 Note that A n,un d = F un + 1 √ k n α kn • F un ,
where α kn is the uniform empirical process based on k n i.i.d. random variables uniformly distributed on [0, 1]. We have, for j ∈ {0, 1, 2},

v j σ n - v j σ n = v j σ n - ν j σ n - a n u j = T 1 j,kn - 1 √ k n T 2 j,kn + 1 √ k n T 3 j,kn - a n u j ,
where,

T 1 j,kn = 1 j + 1 +∞ 0 (F un (σ n y)) j+1 -(G γ (y)) j+1 dy T 2 j,kn = +∞ 0 [α kn • F un (σ n y)] (F un (σ n y)) j dy T 3 j,kn =    +∞ 0 1 0 (1 -t) 1 √ kn [α kn • F un ] 2 (σ n y).j F un (σ n y) -t √ kn α kn • F un (σ n y) j-1 dt dy if j ∈ {1, 2} 0 if j = 0.
This is indeed straightforward for j = 0, whereas for j ∈ {1, 2} we use a Taylor expansion, as in the proof of Theorem 1 in [START_REF] Diebolt | Approximation of the distribution of excesses through a generalized probability-weighted moments method[END_REF] (page 850), with power functions instead of their general weight functions, which have to be null at zero1 .

The following lemma concerns the terms T 1 j,kn and will be proved in Appendix 5.3.

Lemma 4 Under the assumptions of Theorem 1,

T 1 j,kn - a n u j = c j γ,ρ,β a n b n + o(a n b n ).
T2 0,kn has been studied in [START_REF] Diebolt | Asymptotic behaviour of the probability-weighted moments and penultimate approximation[END_REF]. The other terms T 2 j,kn and T 3 j,kn , for j ∈ {1, 2}, have been treated in [START_REF] Diebolt | Approximation of the distribution of excesses through a generalized probability-weighted moments method[END_REF] (see pages 851-853), in a more general framework. The results are stated in the following lemma and the proofs remains valid under our slightly different assumptions (where the role of the condition

√ k n a n → λ is replaced here by √ k n a 2 n → λ).
Lemma 5 Under the assumptions 2 of Theorem 1, as n→ ∞,

T 3 j,kn P -→ 0 and T 2 j,kn d -→ 1 0 t -γ-1 t j B(t) dt,
where B is a Brownian Bridge on [0, 1]. Moreover, the vector of coordinates 1 0 t -γ-1 t j B(t) dt with j ∈ {0, 1, 2} has a multivariate normal distribution with mean 0 and covariance matrix Γ defined by (2.4).

We deduce from these lemmas that

k n v j σ n - v j σ n d = c j γ,ρ,β k n a n b n + Z j n + o P (1),
where, using [START_REF] Serfling | Approximation Theorems of Mathematical Statistics[END_REF] (p. 18), the vector of coordinates Z j n (for j ∈ {0, 1, 2}) converges in distribution to N (0, Γ). The statement of Theorem 1 follows by the assumption

√ k n a n b n → λ 1 .

Remark 3

The third order condition is not used to prove Lemma 5. This implies that the consistance of the vector of coordinates vj /σ n could be obtained under weaker assumptions.

3 Asymptotic normality of the PWM estimators of the parameters

Asymptotic normality for known γ

From now on we will use the following notations :

V n = (v 0 , v 1 , v 2 ) t , V n = ( v 0 , v 1 , v 2 ) t
The expressions of the probability weighted-moments as functions of the parameters ρ, a n , σ n are stated in Lemma 3. Elementary calculus leads to the following equations (recall that u j = (j +1)(j +1-γ)(j +1-γ -ρ)

for j ∈ {0, 1, 2}) : ρ = φ 1,γ (V n ) , a n = φ 2,γ (V n ) , σ n = φ 3,γ (V n )
where

φ 1,γ : (x, y, z) → (1-γ) 2 x-4(2-γ) 2 y+3(3-γ) 2 z (1-γ)x-4(2-γ)y+3(3-γ)z φ 2,γ : (x, y, z) → 2((1-γ)x-2(2-γ)y)((1-γ)x-3(3-γ)z)(2(2-γ)y-3(3-γ)z) ((1-γ)x-4(2-γ)y+3(3-γ)z)(6(3-γ)z[(1-γ)x-2(2-γ)y]-2(2-γ)y[(1-γ)x-3(3-γ)z]) φ 3,γ : (x, y, z) → 6(3-γ)z[(1-γ)x-2(2-γ)y]-2(2-γ)y[(1-γ)x-3(3-γ)z] (1-γ)x-4(2-γ)y+3(3-γ)z
First assuming that the first order parameter γ is known (the case γ unknown will be handled in the next section), we can then define our estimators of the parameters ρ, a n , and σ n as :

  ργ ân,γ σn,γ   =   φ 1,γ ( Vn ) φ 2,γ ( Vn ) φ 3,γ ( Vn )   hence   ργ ân,γ σn,γ /σ n   =   φ 1,γ ( Vn /σ n ) φ 2,γ ( Vn /σ n ) φ 3,γ ( Vn /σ n )  
Proving the asymptotic normality of these estimators by the delta-method (see [START_REF] Van Der | Asymptotic Statistics[END_REF] for instance) would be straightforward if the functions φ j,γ were well-defined at the limit

v := lim n→∞ V n σ n = (1 -γ) -1 , (2(2 -γ)) -1 , (3(3 -γ)) -1 t .
However this is not the case here, and the proof needs more care than it seems at first glance.

k n a n (ρ γ -ρ) d -→ N (λ 1 ∇ t 1 H γ C, ∇ t 1 H γ ΓH γ ∇ 1 ) (3.1) k n a n ân,γ a n -1 d -→ N (λ 1 ∇ t 2 H γ C, ∇ t 2 H γ ΓH γ ∇ 2 ) (3.2) k n σn,γ σ n -1 d -→ N (λ 1 ∇ t 3 H γ C, ∇ t 3 H γ ΓH γ ∇ 3 ) (3.3)
where ∇ 1 , ∇ 2 , ∇ 3 and H γ are defined in the proof of this proposition, and λ 1 in (2.1).

Proof of Proposition 1

Let H γ denote the matrix

H γ =   1 -γ 0 0 0 2(2 -γ) 0 0 0 3(3 -γ)  
and let us define the following functions

ψ 1,γ : (x, y, z) → (1 -γ)x -2(2 -γ)y + (3 -γ)z x -2y + z ψ 2 : (x, y, z) → 2(x -y)(x -z)(y -z) (x -2y + z)(2z(x -y) -y(x -z)) ψ 3 : (x, y, z) → 2z(x -y) -y(x -z) x -2y + z If U denotes the subset of R 3 on which ψ 2 is defined, we have φ 1,γ (u) = ψ 1,γ (H γ u), φ 2,γ (u) = ψ 2 (H γ u) and φ 3,γ (u) = ψ 3 (H γ u), for every u = (x, y, z) t ∈ U .
The proof of the proposition relies on the introduction of the following modified probability-weighted moments

V ′ n = V n /σ n -v a n and V ′ = V n /σ n -v a n = 1 u 0 , 1 u 1 , 1 u 2 t
(where the u j are defined in the statement of Lemma 3). If we note e = (1, 1, 1) t , then for every u ∈ U we have

ψ 1,γ (u + e) = ψ 1,γ (u) , ψ 2 (u + e) = ψ2 (u)(1 + d 2 (u)/d 1 (u)) -1 , ψ 3 (u + e) = ψ 3 (u) + 1 , (3.4)
where

d 1 (x, y, z) = x -2y + z, d 2 (x, y, z) = 2z(x -y) -y(x -z) and ψ2 : (x, y, z) → 2(x -y)(x -z)(y -z) (x -2y + z) 2 . Defining V ′′ := H γ V ′ = ((1 -γ -ρ) -1 , (2 -γ -ρ) -1 , (3 -γ -ρ) -1 ) t (3.5)
and noticing that H γ v = e, d 2 (V ′′ ) = 0 and d 1 (V ′′ ) = 0, it is now easy to prove the following identities using (3.4) :

k n a n (ρ γ -ρ) = k n a n (φ 1,γ ( V n /σ n ) -φ 1,γ (V n /σ n )) = k n a n (ψ 1,γ (H γ V ′ n ) -ψ 1,γ (V ′′ ))(3.6) k n a n (â n,γ /a n -1) = k n (φ 2,γ ( V n /σ n ) -φ 2,γ (V n /σ n )) = k n a n ( ψ2 (H γ V ′ n ) -ψ2 (V ′′ )) + R n (3.7) k n (σ n,γ /σ n -1) = k n (φ 3,γ ( V n /σ n ) -φ 3,γ (V n /σ n )) = k n a n (ψ 3 (H γ V ′ n ) -ψ 3 (V ′′ )) (3.8)
where

R n = k n a n ψ2 (H γ V ′ n ) (1 + a n d 2 (H γ V ′ n )/d 1 (H γ V ′ n )) -1 -1 . (3.9)
The point is that the functions ψ 1,γ , ψ 2 and ψ 3 and their derivatives are well-defined at V ′′ defined by (3.5) (it was not the case for the functions φ j,γ at the limit v = lim V n /σ n ). The delta-method can thus be called upon to obtain relations (3.1) and (3.3) by combining equations (3.6) and (3.8), Theorem 1 and the following equality

k n a n (H γ V ′ n -V ′′ ) = H γ ( k n ( V n /σ n -V n /σ n )) where ∇ 1 = ∇ψ 1,γ (V ′′ ) =   p(1 -γ -ρ)/2 -p(2 -γ -ρ) p(3 -γ -ρ)/2   and ∇ 3 = ∇ψ 3 (V ′′ ) =   (1 -γ -ρ) 2 /2 -(2 -γ -ρ) 2 (3 -γ -ρ) 2 /2   . p = (1 -γ -ρ)(2 -γ -ρ)(3 -γ -ρ).
We can deal with the case of a n,γ similarly : with ∇ 2 defined by

∇ 2 = ∇ ψ2 (V ′′ ) =   1 2 (1 -γ -ρ)(-5 + 7γ + 7ρ -2(γ + ρ) 2 ) 2(2 -γ -ρ)(4 -4γ -4ρ + (γ + ρ) 2 ) 1 2 (3 -γ -ρ)(-9 + 9γ + 9ρ -2(γ + ρ) 2 )   relation (3.
2) will follow from (3.7) by the delta-method, provided R n (defined in (3.9)) converges to 0 in probability. This is the case, since H γ V ′ n → V ′′ in probability as n→ ∞, and consequently

R n = -k n a 2 n ψ2 (H γ V ′ n ) d 2 (H γ V ′ n ) d 1 (H γ V ′ n ) 1 + a n d 2 (H γ V ′ n )/d 1 (H γ V ′ n ) -1
vanishes to 0 as n→ ∞ (in probability) because ψ2 (V ′′ ) = 1, d 1 (V ′′ ) = 2/p, d 2 (V ′′ ) = 0, and using assumption (2.2) (which ensures that √ k n a 2 n has a real limit as n→ ∞).

Asymptotic normality for unknown γ

We can now define our final estimators of the parameters ρ, a n , and σ n , by plugging-in an external estimator of γ. We set   ρ ân σn

  =   φ 1,γ ( Vn ) φ 2,γ ( Vn ) φ 3,γ ( Vn )  
where γ = γn defines a sequence of estimators of γ based on the Ñn upper excesses associated to a threshold ũn such that ũn → s + (F ). Let ãn = A(e V -1 (ũn )) and λ, c, d denote some real constants.

Theorem 2 Let the assumptions of Proposition 1 hold with ρ < 0 and suppose that for some real constant λ, n(1 -F (ũ n )) ãn → λ as n→ ∞.

(3.10)

If conditionally on Ñn = kn k1/2 n (γ -γ) d -→ N ( λc, d) as n→ ∞, (3.11)
then for almost all sequences k n → ∞ and kn → ∞ such that kn = o(k n ), we have, conditionally on N n = k n and Ñn = kn ,

k1/2 n a n (ρ -ρ) d -→ N ( λcc 1 , dc 2 1 ) (3.12) k1/2 n a n ân a n -1 d -→ N ( λcc 2 , dc 2 2 ) (3.13) k1/2 n σn σ n -1 d -→ N ( λcc 3 , dc 2 3 ) (3.14)
for some constants c 1 , c 2 , c 3 depending on γ and ρ (which expressions are given in the proof of the theorem).

Remark 4

The condition kn = o(k n ) means that we take less excesses for the estimation of the first-order parameter γ than for the estimation of the second-order parameter ρ.

Remark 5 Proposition 1 is valid in the whole scope ρ ≤ 0, whereas Theorem 2 excludes the case ρ = 0. However, according to (3.12) and the expression of c 1 , the asymptotic mean square error (AMSE) of ρ tends to 0 when ρ → 0, while this is not the case for many other estimators of ρ studied in the litterature, for which the AMSE goes to infinity when ρ → 0. This has to be linked with the fact that our estimator of ρ looks especially competitive in situations where |ρ| is small, as it will be seen in the simulations below (Section 4).

Remark 6

In our simulations, we used the PWM estimator defined by Hosking & Wallis in [START_REF] Hosking | Parameter and quantile estimation for the generalized Pareto distribution[END_REF] (and studied in [START_REF] Diebolt | Asymptotic behaviour of the probability-weighted moments and penultimate approximation[END_REF]).

Proof of Theorem 2

We keep using the notations previously introduced in the proof of Proposition 1 and add the following one :

V ′′ n,γ = H γ V n /σ n -v γ a n = H γ V ′ n,γ where v γ = (1 -γ) -1 , (2(2 -γ)) -1 , (3(3 -γ)) -1 .
We first study the deviation

ρ -ργ = ψ 1,γ ( V ′′ n,γ ) -ψ 1,γ ( V ′′ n,γ ) = ψ 1,γ ( V ′′ n,γ ) -ψ 1,γ ( V ′′ n,γ ) + ψ 1,γ ( V ′′ n,γ ) -ψ 1,γ ( V ′′ n,γ ) = γ -γ + ψ 1,γ ( V ′′ n,γ ) -ψ 1,γ ( V ′′ n,γ ) (3.15)
where we used the fact that ψ 1,γ (x, y, z) = -γ + (x -4y + 3z)/(x -2y + z). We thus have to concentrate on the second term. If we note J the 3 × 3 diagonal matrix with diagonal coefficients 1, 2 and 3, after some calculations we obtain the following essential development

V ′′ n,γ -V ′′ n,γ = (H γ -H γ ) V ′ n,γ + H γ ( V ′ n,γ -V ′ n,γ ) = (γ -γ)J V ′ n,γ + H γ (v γ -v γ )/a n = (γ -γ)J V ′ n,γ + γ - γ a n J v γ . (3.16)
Note that, according to assumptions (3.11), (3.10) and the second order condition (1.2) (which ensures that ãn an → 0, when ρ < 0), we have

γ - γ a n = ãn a n k1/2 n (γ -γ) k1/2 n ãn → 0 as n→ ∞, in probability. (3.17) Since V ′ n,γ → V ′ as n→ ∞, V ′′ n,γ = H γ V ′ n,γ
converges in probability to V ′′ (defined in (3.5)), and consequently relations (3.16) and (3.17) imply that

lim n→∞ V ′′ n,γ = lim n→∞ V ′′ n,γ = V ′′ in probability. (3.18)
Therefore, in view of (3.15) and (3.18), there exists some sequence W n converging to

V ′′ such that ρ -ρ = (γ -γ) + a -1 n (γ -γ) < ∇ψ 1,γ (W n ) , J v γ + a n J V ′ n,γ > + (ρ γ -ρ).
The central term of the right-hand side of the relation above makes it impossible to have √ k n a n as the speed for the asymptotic normality of ρρ (because

√ k n a n (γ -γ) → 0 in probability but √ k n (γ -γ) does not) : we have instead k1/2 n a n (ρ -ρ) = k1/2 n a n (γ -γ) + k1/2 n (γ -γ) < ∇ψ 1,γ (W n ) , J v γ + a n J V ′ n,γ > + ( kn /k n ) 1/2 k n a n (ρ γ -ρ).
which, according to assumptions (3.10), (3.11) and Proposition 1, converges in distribution to the gaussian distribution with mean λcc 1 and variance dc 2 1 where

c 1 = ∇ t 1 J v γ = p 2 ((1 -γ -ρ)(1 -γ) -1 -2(2 -γ -ρ)(2 -γ) -1 + (3 -γ -ρ)(3 -γ) -1 ) = -pρ (1 -γ)(2 -γ)(3 -γ)
The proof of the asymptotic normality for the other two parameters relies on the same tools as above. As before, there exists some sequence (W n ) converging to V ′′ in probability such that

σn σ n - σn,γ σ n = a n (ψ 3 ( V ′′ n,γ ) -ψ 3 ( V ′′ n,γ )) = (γ -γ) < ∇ψ 3 (W n ) , J v γ + a n J V ′ n,γ > .
The limiting distribution of k1/2 n (σ n /σ n -1) is therefore N ( λcc 3 , dc 2 3 ) where c 3 = ∇ t 3 Jv γ . The case of ân needs a few more details. Setting h(u) = ψ2 (u)(1 + d 2 (u)/d 1 (u)) -1 (d 2 (u)/d 1 (u)) and e = (1, 1, 1) t , using (3.4) we find that

ân -ân,γ = φ 2,γ ( V n /σ n -v γ + v γ ) -φ 2,γ ( V n /σ n -v γ + v γ ) = ψ 2 (a n V ′′ n,γ + e) -ψ 2 (a n V ′′ n,γ + e) = ψ2 (a n V ′′ n,γ ) -ψ2 (a n V ′′ n,γ ) + h(a n V ′′ n,γ ) -h(a n V ′′ n,γ ) = a n ( ψ2 ( V ′′ n,γ ) -ψ2 ( V ′′ n,γ )) + a 2 n o P (1)
where we used (3.18) and the following facts :

d 2 (V ′′ ) = 0, ψ2 (V ′′ ) = 1, ψ2 (αu) = α ψ2 (u) and (d 2 /d 1 )(αu) = α(d 2 /d 1 )(u)
for any α = 0 and u ∈ U . We thus have, for some sequence

(W n ) converging to V ′′ in probability, k1/2 n a n (â n /a n -1) = k1/2 n (γ-γ) < ∇ ψ2 (W n ) , J v γ +a n J V ′ n,γ > + o P ( k1/2 n a 2 n )+( kn /k n ) 1/2 k n a n (â n,γ /a n -1)
which converges in distribution to N ( λcc 2 , dc 2 2 ) where c 2 = ∇ t 2 Jv γ .

Simulation results

In this section, we shall present some of the graphics obtained, concerning bias and mean square errors of our estimator of ρ, compared with two others, for three different classes of underlying distributions.

For the three estimators considered, the P.O.T. method we use consists in choosing a threshold u n = F -1 (p n ) for the estimation of ρ, as well as a second threshold ũn = F -1 (p n ) for the preliminary estimation of γ (only when necessary, since one of the estimators studied below does not rely on such an initial estimation of γ) : the corresponding number of excesses k n and kn are then random, and p n and pn are the sample fractions retained for the estimation of ρ and γ respectively. In our simulations, we take, for γ = γ( kn ), the Hosking and Wallis' estimator defined in [START_REF] Hosking | Parameter and quantile estimation for the generalized Pareto distribution[END_REF] and studied in [START_REF] Diebolt | Asymptotic behaviour of the probability-weighted moments and penultimate approximation[END_REF] and [START_REF] Diebolt | Approximation of the distribution of excesses through a generalized probability-weighted moments method[END_REF].

We compare our estimator, denoted in this section by ρP W M , with two others: the one presented in Fraga Alves, de Haan, Gomes [START_REF] Fraga Alves | A new class of semi-parametric estimators of the second order parameter[END_REF], which will be noted ρF GH and the one presented in Fraga Alves, de Haan, Lin [START_REF] Fraga Alves | Estimation of the parameter controlling the speed of convergence in extreme value theory[END_REF], which will be noted ρF HL . They are defined as

ρF GH = - 3(T (τ ) n (k n ) -1) T (τ ) n (k n ) -3
(see [START_REF] Fraga Alves | A new class of semi-parametric estimators of the second order parameter[END_REF] for the definition of T (τ ) n (k n )), with the tuning parameter τ equal to 0 whenever one expects ρ to be in the range [-1, 0) and equal to 1 otherwise (as suggested for instance in [START_REF] Caeiro | A note on the asymptotic variance at optimal levels of a biascorrected Hill estimator[END_REF]), and

ρF HL = 3 -8γ -( kn ) + 6 -12γ -( kn ) T n (k n ) -3
(see [START_REF] Fraga Alves | Estimation of the parameter controlling the speed of convergence in extreme value theory[END_REF] for the definition of T n (k n ) and γ-( kn ), the latter being an estimator of γ -= min(0, γ)). Recall that k n is the number of excesses used for the estimation of ρ and the calculation of Tn (k n ), and kn the one used for the estimation of γ -. The estimator ρF GH does not depend on an initial estimation of the parameter γ, though.

The models presented in our simulations are the following :

• The Burr(λ, τ ) distribution (for which γ = 1/λτ and ρ = -1/λ) defined by

F (x) = (1 + x τ ) -λ , x > 0.
• The Arcsin model (for which γ = ρ = -2) defined by

F (x) = 2 π arcsin √ x, x ∈ (0, 1).
• The model, for which γ > 0 and ρ = 0 (see [START_REF] Fraga Alves | A note on second order conditions in extreme value theory: linking general and heavy tail conditions[END_REF]), defined by

U (t) = F -1 (1/t) = t γ (1 + ln t), t > 0. (4.1)
We consider 1000 samples of size n (where n = 5000 for the Arcsin model and 1000 otherwise) and present the bias and the mean square error of the three estimators of ρ considered above, as function of the fraction p n of the excesses used for the estimation of ρ. The sample fraction pn used for the calculation of ρP W M was chosen as 0.1 for the Burr model (as in [START_REF] Diebolt | Asymptotic behaviour of the probability-weighted moments and penultimate approximation[END_REF]), 0.05 for the third model, and in the sense of the minimization of the simulated MSE for the Arcsin model. For the preliminary estimation of γ -in the calculation of ρF HL , the sample fraction pn was set to the same values as for our estimator ρP W M , except for the Arcsin model where the criterion of minimization of the asymptotic MSE was chosen (as suggested in [START_REF] Fraga Alves | Estimation of the parameter controlling the speed of convergence in extreme value theory[END_REF], see figure 4 and details therein). Note however that the simulations undertaken showed that ρF HL was much less sensitive to the choice of kn than ρP W M .

Our simulations (see Figures 1 and2) confirm that in order to estimate the correct value of ρ, one should generally use even more than half of the order statistics of the sample. This is coherent with our theoretical result which says that the number of order statistics to use for the estimation of ρ must be of larger order than the order needed for the estimation of the tail index γ.

The flat pattern of the RMSE of ρP W M for a reasonably wide region of sample fractions makes the exact determination of the optimal choice of the sample fraction p n to use less relevant, from a practical point of view.

The figures presented here show that our estimator can be competitive especially when |ρ| is small. The same conclusions have been drawn for sample sizes n = 500 and n = 5000 for the distributions presented here. Note that none of the 4 particular distributions presented here satisfy the restriction -1 < γ < 1/2 imposed in our theorems.

B θn (x) dx = +∞ 0 G γ,σn (x) + a n D γ,ρ (x/σ n ) dx = ν 0 + a n +∞ 0 D γ,ρ (x/σ n ) dx.
and, for j ∈ {1, 2},

ṽj = +∞ 0 B j+1 θn (x) j+1 dx = 1 j+1 +∞ 0 G γ,σn (x) + a n D γ,ρ (x/σ n ) j+1 dx = 1 j+1 +∞ 0 G j+1 γ,σn (x) dx + a n s+(B θn ) 0 G j γ,σn (x) D γ,ρ (x/σ n ) dx + o(a n ) = ν j + a n +∞ 0 G j γ,σn (x) D γ,ρ (x/σ n ) dx + o(a n ).

Proof of lemma 3

In the case γ = 0, ρ < 0 and γ + ρ = 0,

D γ,ρ (x) = (1 + γx) -1/γ γρ(γ + ρ) γ(1 + γx) ρ/γ + ρ(1 + γx) -1 -γ -ρ .
At the end of this subsection, we will give expressions of D γ,ρ in the other cases.

We give the sketch of the proof in case γ > 0, ρ < 0 and γ + ρ = 0. All the other cases are similar. We will see below how the restriction γ < 1 appears (similarly, in case γ < 0, appears the restriction γ > -1). In the sequel, we will note σ instead of σ(u n ).

(i) Calculation of v 0 : We have,

+∞ 0 D γ,ρ (x/σ) dx = 1 ρ(γ+ρ) +∞ 0 (1 + γx/σ) (ρ-1)/γ dx + 1 γ(γ+ρ) +∞ 0 (1 + γx/σ) -1/γ-1 dx -1 γρ +∞ 0 (1 + γx/σ) -1/γ dx = 1 ρ(γ+ρ) I 1 + 1 γ(γ+ρ) I 2 -1 γρ I 3 ,
where, for γ < 1,

I 1 = σ 1 -γ -ρ , I 2 = σ, I 3 = σ 1 -γ . Therefore +∞ 0 D γ,ρ (x/σ) dx = σ (1-γ)(1-γ-ρ) and the result for v 0 follows. (ii) Calculation of v 1 : We have, +∞ 0 G γ,σ (x) D γ,ρ (x/σ) dx = 1 ρ(γ+ρ) +∞ 0 (1 + γx/σ) (ρ-2)/γ dx + 1 γ(γ+ρ) +∞ 0 (1 + γx/σ) -2/γ-1 dx -1 γρ +∞ 0 (1 + γx/σ) -2/γ dx = 1 ρ(γ+ρ) I 1 + 1 γ(γ+ρ) I 2 -1 γρ I 3 ,
where, Defining g n and g by g n (x) = V -1 (u n + σ n x) -V -1 (u n ) and g(x) = 1 γ ln(1 + γx),

I 1 = σ 2 -γ -ρ , I 2 = σ/2, I 3 = σ 2 -γ . Therefore +∞ 0 G γ,σ (x) D γ,ρ (x/σ) dx =
we have, F un (σ n y) = e -gn(y) and G γ (y) = e -g(y)

Setting W (x) = x j+1 j+1 , integration by parts yields (where we used the fact that yW (F un (σ n y)) → 0 as y → +∞) and

I 2 = +∞ 0
W (e -g(y) ) dy = +∞ 0 yW ′ (e -g(y) )g ′ (y)e -g(y) dy = +∞ 0 g -1 (s)e -(j+1)s ds.

It follows that, for j ∈ {0, 1, 2}, In order to conclude the proof, it remains to use the dominated convergence theorem to show that 1 anbn (T 1 j,knan uj ) converges to +∞ 0

e -(j+1)s R γ,ρ,β (e s ) ds. Under the third order condition (1.5), we can use the following bound which is proved in [START_REF] Fraga Alves | Third order extended regular variation[END_REF] (see equation (2.9) in Theorem 2.1 of [START_REF] Fraga Alves | Third order extended regular variation[END_REF]): ∀ǫ > 0, ∃n 0 , ∀n ≥ n 0 , ∀s ≥ V -1 (u n0 ) -V -1 (u n ), |Γ n (s) -R γ,ρ,β (e s )| ≤ ǫe ǫs e (γ+ρ+β)s .

Therefore,

+∞ 0 e -(j+1)s (Γ n (s) -R γ,ρ,β (e s )) ds ≤ ǫ +∞ 0 e (j+1-γ-ρ-β-ǫ)s ds, with the right hand side of the inequality being bounded, since ǫ can be set sufficiently small to insure that j + 1γρβǫ > 0. Finally, elementary calculus leads to +∞ 0 e -(j+1)s R γ,ρ,β (e s ) ds = 1 (j + 1)(j + 1γ)(j + 1γρ)(j + 1γρβ) = c j γ,ρ,β which concludes the proof of Lemma 4.

1 γ

 1 un) , D γ,ρ (y) := C 0,ρ (y), if γ = 0, C γ,ρ ln(1 + γy) if γ = 0, and C γ,ρ (y) := e -(1+γ)y I γ,ρ (y) and I γ,ρ (y) :=

1 Figure 1 :

 11 Figure 1: Bias and RMSE of three estimators of ρ for some models (Burr(2, 1/2) and Burr(8, 1/8), for which respectively γ = 1, ρ = -1/2, and γ = 1, ρ = -1/8) as a function of the sample fraction p n . The dashed line is for ρF HL , the thin solid line for ρF GH , and the thick solid line for ρP W M .

Figure 2 : 5 Appendix 5 . 1

 2551 Figure 2: Bias and RMSE of three estimators of ρ for some models (Arcsin model, for which γ = ρ = -2, and model (4.1) with γ = 1, for which ρ = 0) as a function of the sample fraction p n . The dashed line is for ρF HL , the thin solid line for ρF GH , and the thick solid line for ρP W M .

σ 2 (G 2 γ( 1 +( 1 + 1 γρ +∞ 0 ( 1 + 1 ρ 2 γ 2 ln( 1 += e -x ρ 1 ρ(F

 221110112211 2-γ)(2-γ-ρ) and the expression of v 1 follows. (iii) Calculation of v 2 : We have,+∞ 0 ,σ (x) D γ,ρ (x/σ) dx = 1 ρ(γ+ρ) +∞ 0 γx/σ) (ρ-3)/γ dx + 1 γ(γ+ρ) +∞ 0 γx/σ) -3/γ-1 dx γx/σ) -3/γ dx = (γ+ρ) I 1 + 1 γ(γ+ρ) I 2 -1 γρ I 3 , ,σ (x) D γ,ρ (x/σ) dx = σ 3(3-γ)(3-γ-ρ)which yields the result for v 2 . Here are the expressions of D γ,ρ in the different other cases :D γ,ρ (x) = (1+γx) -1/γ γρ (1 + γx) -1 (1 + ln(1 + γx)) -1 if γ = 0, ρ < 0, γ + ρ = 0 = (1+γx) -1/γ γ γx) -1 + (1 + γx) -1 if γ = 0, ρ = 0 (e ρx -1)x if γ = 0, un (σ n y)) j+1 -(G γ (y)) j+1 dy = 1 j+1 +∞ 0 (F un (σ n y)) j+1 -1 j+1 +∞ 0(G γ (y)) j+1 dy =: I 1 -I 2 .

I 1 = 0 W

 10 +∞ (e -gn(y) ) dy = +∞ 0 yW ′ (e -gn(y) )g ′ n (y)e -gn(y) dy = +∞ 0 g -1 n (s)e -(j+1)s ds.

  n (s)g -1 (s) e -(j+1)s ds = +∞ 0 p un (s)e -(j+1)s ds,where p un (s) = V (s+V -1 (un))-un V ′ (V -1 (un)) -s 0 e γu du.Moreover, it is easy to see that +∞ 0 e -(j+1)s I γ,ρ (s) We deduce from the third order condition (1.5) that Γ n (s) := pu n (s) an -I γ,ρ (s) b n n→∞ -→ R γ,ρ,β (e s ).

  2.2 Asymptotic behaviour of the estimators of the Probability-Weighted Moments Let (X 1 , . . . , X n ) be n i.i.d. random variables with distribution function F , and X 1:n , . . . , X n:n denote the corresponding order statistics. For a given thresold u n , we introduce Y 1,Nn , . . . , Y Nn,Nn the N n excesses over u n , in ascending order, i.e. Y j,Nn = X n-Nn+j : nu n where N n =

	n i=1 I Xi>un .

this fact exludes the case j=0, where the weight function is identically equal to 1, from their study.

The restriction γ < 1 2 comes from the study of T 2 0,kn


Samuele Giraudo
email: samuele.giraudo@univ-eiffel.fr.

Mockingbird lattices

Keywords: Partial orders, Lattices, Combinatory logic, Rewrite systems, Treelike structures, Formal power series

We study combinatorial and order theoretic structures arising from the fragment of combinatory logic spanned by the basic combinator M. This basic combinator, named as the Mockingbird by Smullyan, is defined by the rewrite rule Mx 1 → x 1 x 1 . We prove that the reflexive and transitive closure of this rewrite relation is a partial order on terms on M and that all connected components of its rewrite graph are Hasse diagrams of lattices. This last result is based on the introduction of lattices on some forests. We enumerate the elements, the edges of the Hasse diagrams, and the intervals of these lattices with the help of formal power series on terms and on forests.

Introduction

Combinatory logic [START_REF] Hindley | Lambda-calculus and combinators, an introduction[END_REF] is a model of computation introduced by Schönfinkel [START_REF] Schönfinkel | Über die Bausteine der mathematischen Logik[END_REF] and developed by Curry [START_REF] Curry | Grundlagen der Kombinatorischen Logik[END_REF] with the objective to abstain from the need of bound variables specific to the λ-calculus. Its combinatorial heart is formed by terms, which are binary trees with labeled leaves, and rules to compute a result from a term, which are rewrite relations on trees [START_REF] Bezem | Term Rewriting Systems[END_REF]. An important instance is the system containing the basic combinators K and S with the rewrite rules Kx 1 x 2 → x 1 and Sx 1 x 2 x 3 → x 1 x 3 (x 2 x 3 ). This system is important because it is combinatorially complete: each λ-term can be translated, by bracket abstraction algorithms [START_REF] Schönfinkel | Über die Bausteine der mathematischen Logik[END_REF] into a term over K and S emulating it.

A lot of other basic combinators with their own rewrite rules have been introduced by Smullyan in [START_REF] Smullyan | To Mock a Mockingbird[END_REF] after -now widely used-bird names, forming the enchanted forest of combinator birds. For instance, K is the Kestrel and S is the Starling. Usual computer science questions consist in considering a fragment of combinatory logic, that is a finite set of basic combinators with their rewrite rules, and to ask whether (a) Given two terms t and t ′ , can we decide if t and t ′ can be rewritten eventually in a same term? This is known as the word problem [START_REF] Bezem | Term Rewriting Systems[END_REF][START_REF] Statman | On the Word Problem for Combinators[END_REF]. It admits a positive answer for some basic combinators like the Lark [START_REF] Sprenger | How to decide the lark[END_REF][START_REF] Statman | The word problem for Smullyan's lark combinator is decidable[END_REF] and the Warbler [START_REF] Sprenger | How to decide the lark[END_REF] but is still open for the Starling [START_REF] Barendregt | Dance of the starlings[END_REF]; (b) Given a term t, can we decide if all rewrite sequences starting from t are finite? This is known as the strong normalization problem. It admits a positive answer for the Starling [START_REF] Waldmann | The combinator[END_REF] and the Jay [START_REF] Probst | How to normalize the Jay[END_REF].

Here, we pursue this study in a different direction by adopting a combinatorial, order theoretic, and enumerative point of view. In particular, by denoting by ≼ (resp. ≡) the reflexive and transitive (resp. reflexive, symmetric, and transitive) closure of the rewrite relation, we try to (a') Determine if ≼ is a partial order relation; (b') Determine in this case if each interval of this poset is a lattice; (c') Enumerate the ≡-equivalence classes of terms w.r.t. some size notions. This work fits in this general project consisting in mixing combinatory logic with combinatorics.

We start this project by studying the system made of the basic combinator M, known as the Mockingbird [START_REF] Smullyan | To Mock a Mockingbird[END_REF][START_REF] Statman | Some tweets about Mockingbirds[END_REF]. By drawing some portions of its rewrite graph, the first properties that stand out are that the graph does not contain any nontrivial loops and that its connected components are finite and have exactly one minimal and one maximal element. At this stage, driven by computer exploration, we conjecture that ≼ is a partial order relation and that each ≡-equivalence class is a lattice w.r.t. ≼. This lattice property is for us a good clue for the fact that this system contains rather rich combinatorial properties. To prove this, we introduce a new lattice on duplicative forests, that are kinds of treelike structures, and construct a poset isomorphism between this last poset and the poset on terms on M. The Mockingbird lattice of order d ⩾ 0 is the lattice M(d) consisting in the combinators on M greater than or equal to the right comb combinator on M of degree d. Since any combinator on M can be seen as a binary tree, this provides a new lattice structure on these objects. Many similar lattices have been studied on binary trees such as among others the Tamari lattice [START_REF] Tamari | The algebra of bracketings and their enumeration[END_REF]. However, unlike these lattices having for any d ⩾ 0 a cardinality equal to the d-th Catalan number, the elements of M(d) are enumerated by a different integer sequence. To obtain enumerative results about the Mockingbird lattices and all the posets of terms on M in general, we use formal power series on terms and on duplicative forests. In this way, we enumerate the maximal and minimal elements of the poset of all terms on M, and the cardinality, the number of edges of the Hasse diagram, and the number of intervals of M(d).

This paper is organized as follows. Section 1 contains definitions about terms, rewrite relations, and combinatory logic systems. In Section 2, we study the combinatory logic system on M and the Mockingbird lattices. Section 3 contains enumerative results. This text ends with the presentation of some open questions.

General notations and conventions. For any integers i and j, [i, j] denotes the set {i, i + 1, . . . , j}. For any integer i, [i] denotes the set [1, i] and i] denotes the set [0, i]. For any set A, A * is the set of words on A. For any w ∈ A * and a ∈ A, |w| a is the number of occurrences of a in w. The only word of length 0 is the empty word ϵ. If P is a statement, we denote by 1 P the indicator function (equals to 1 if P holds and 0 otherwise).

Combinatory logic systems

An alphabet is a finite set G. Its elements are called basic combinators. Any element of the set X := n⩾1 X n , where X n := {x 1 , . . . , x n }, is a variable. The set T(G) of G-terms is so that any variable of X is a G-term, any basic combinator of G is a G-term, and if t 1 and t 2 are two G-terms, then (t 1 ⋆ t 2 ) is a G-term. Any term is thus a rooted planar binary tree where leaves are decorated by variables or by basic combinators. We shall express terms concisely by removing superfluous parentheses by considering that ⋆ associates to the left and also by removing the symbols ⋆. For instance, if G = {A, B}, the G-term t := (((A ⋆ B) ⋆(x 1 ⋆ x 2 )) ⋆ A) writes concisely as AB(x 1 x 2 )A. Let t be a G-term. The degree deg(t) of t is the number of internal nodes of t seen as a binary tree. The depth of a node u of t is the number of internal nodes in the path connecting the root of t and u. The height ht(t) of t is the maximal depth among all the nodes of t. A combinator is a term having no occurrence of any variable.

Let

t
′ i . For instance x 1 (Ax 1 )(x 4 x 2 )[B, x 1 x 3 ] = B(AB)(x 4 (x 1 x 3 )).
Given two G-terms t and s, s is a factor of t if t = t ′ [s 1 , . . . , s i-1 , s, s i+1 , . . . , s n ][r 1 , . . . , r m ] for some integers n, m ⩾ 0 and G-terms t ′ , s 1 , . . . , s i-1 , s i+1 , . . . , s n , r 1 , . . . , r m , where x i appears in t ′ . When this property does not hold, t avoids s.

A rewrite relation on T(G) is a binary relation → on T(G). A combinatory logic system (or CLS for short) is a pair C := (G, →) where G is an alphabet and → is a rewrite relation on T(G) such that for each basic combinator C of G, there is exactly one rule of the form Cx 1 . . . x n → t C where n ⩾ 1 and t C is a term having no basic combinators and having all variables in X n . The integer n is the order of C in C. Some well-known combinators C together with the terms t C appearing among other in [START_REF] Smullyan | To Mock a Mockingbird[END_REF] are the Identity bird I of order 1 with t I = x 1 , the Mockingbird M of order 1 with t M = x 1 x 1 , the Kestrel K of order 2 with t K = x 1 , and the Starling S of order 3 with t S = x 1 x 3 (x 2 x 3 ). The context closure of → is the binary relation ⇒ on T(G) defined as follows. For any C ∈ G, by denoting by n the order of C, we have Cx 1 . . .

x n [s 1 , . . . , s n ] ⇒ t C [s 1 , . . . , s n ] for any s 1 , . . . , s n ∈ T(G), and t 1 t 2 ⇒ t ′ 1 t 2 for any t 1 , t 2 ∈ T(G) whenever t 1 ⇒ t ′ 1 , and t 1 t 2 ⇒ t 1 t ′ 2 for any t 1 , t 2 ∈ T(G) whenever t 2 ⇒ t ′ 2 .
For instance, if C is the CLS containing the basic combinators K and S, we have S(KKS)K(SS) ⇒ SKK(SS) ⇒ K(SS)(K(SS)) ⇒ SS.

Given a CLS C := (G, →), we denote by ≼ the preorder defined as the reflexive and transitive closure of ⇒.

The rewrite graph G C of C is the digraph of the binary relation ⇒ on T(G). For any t ∈ T(G), G C (t) is the subgraph of G C restrained on {t ′ ∈ T(G) : t ≼ t ′ }.
When ≼ is antisymmetric, C has the poset property and we denote by P C the poset (T(G), ≼). For any t ∈ T(G), P C (t) is the subposet of P C having t as smallest element. When C has the poset property and, for any t ∈ T(G), P C (t) is a lattice, C has the lattice property. We denote by ≡ the equivalence relation defined as the S. Giraudo reflexive, symmetric, and transitive closure of ⇒. If for any t ∈ T(G), the ≡-equivalence class [t] ≡ of t is finite, then C is locally finite. When C has the poset property and, for any t ∈ T(G), [t] ≡ has a unique minimal element, C is rooted. If for any t, s 1 ,

s 2 ∈ T(G), t ≼ s 1 and t ≼ s 2 implies the existence of t ′ ∈ T(G) such that s 1 ≼ t ′ and s 2 ≼ t ′ , then C is confluent.
Consider for instance the CLS C containing the combinator I. It is straightforward to show that C has the poset property. Nevertheless, C has not the lattice property, as suggested by the Hasse diagram shown in Figure 1a. It is known that the CLS containing the combinators K and S has not the poset property. Figure 1b shows a subgraph of the rewrite graph of this CLS. Figure 1c shows a subgraph of the rewrite graph of the CLS containing the combinator M. We shall study in details this CLS in the next sections.

SSK(SS)K S(SS)(K(SS))K SSK(K(SS)K) S(K(SS)K)(K(K(SS)K)) SSK(SS) S(SS)(K(K(SS)K)) S(K(SS)K)(K(SS))

S(SS)(K(SS))

(b) G → (SSK(SS)K).

M(M(MM)) M(MM)(M(MM)) M(MM)(MM(MM)) MM(MM)(M(MM)) MM(MM)(MM(MM)) M(MM(MM))

(c) G → (M(M(MM))). A basic combinator C is hierarchical if for any i ∈ [n], x i appears in t C at depth n + 1i. For instance, all the terms t C such that C are hierarchical and of order 3 or less are x 1 x 1 , x 1 x 1 x 2 , x 2 (x 1 x 1 ), x 1 x 1 x 2 x 3 , x 2 (x 1 x 1 )x 3 , x 3 (x 1 x 1 x 2 ), and x 3 (x 2 (x 1 x 1 )). Observe that by Propositions 1.1 and 1.2, if C has the poset property and all its basic combinators are hierarchical, then for any t ∈ T(G), the subposet [t] ≡ of P C has exactly one maximal element. If additionally C is rooted, then for any t ∈ T(G), the subposet [t] ≡ of P C has exactly one minimal element.

The Mockingbird combinatory logic system

Let C := (G, →) be the CLS such that G := {M}.

M(x 1 x 2 ) (resp. (x 1 x 2 )(x 1 x 2 )).
A duplicative tree is a planar rooted tree such that each node is either a black node or a white node . A duplicative forest is a word f of duplicative trees. We denote by D (resp. D * ) the set of such trees (resp. forests). The height ht(f) of f is the number of internal nodes in a longest path following edges connecting a node to one of its child. Each expression using some occurrences of denotes the two expressions obtained by replacing simultaneously all either by or by . The grafting product is the operation on D * such that for any f ∈ D * , (f) is the duplicative tree obtained by grafting the roots of the duplicative trees of f on a common root node . The concatenation product is the binary operation on D * such that for any f 1 , f 2 ∈ D * , f 1 f 2 is the duplicative forest made of the trees of f 1 and then of the trees of f 2 .

Let ⇒ ⇒ be the binary relation on D * such that for any f, f ′ ∈ D * , we have f ⇒ ⇒ f ′ if f ′ can be obtained from f by selecting a white node of f, by turning it into black, and by duplicating its sequence of descendants. For instance, we have

⇒ ⇒ . (2.1)
Observe that in this case, there are more black nodes in f ′ than in f. Hence, the reflexive and transitive closure ≪ of ⇒ ⇒ is antisymmetric so that (D * , ≪) is a poset. For any f ∈ D * , we denote by D * (f) the subposet of (D * , ≪) on the set {f ′ ∈ D * : f ≪ f ′ }.

S. Giraudo

diagram, the poset D * is not graded. Let ∧ and ∨ be the two binary, commutative, and associative partial operations on D * defined, for any ℓ ⩾ 0, f 1 , . . . ,

f ℓ ∈ D, f ′ 1 , . . . , f ′ ℓ ∈ D, and f, f ′ , f ′′ ∈ D * , by f 1 . . . f ℓ ∧ f ′ 1 . . . f ′ ℓ := f 1 ∧ f ′ 1 . . . f ℓ ∧ f ′ ℓ , (f) ∧ f ′ := f ∧ f ′ , (f) ∧ f ′ f ′′ := f ∧ f ′ ∧ f ′′ (2.2) f 1 . . . f ℓ ∨ f ′ 1 . . . f ′ ℓ := f 1 ∨ f ′ 1 . . . f ℓ ∨ f ′ ℓ , (f) ∨ f ′ := f ∨ f ′ , (f) ∨ f ′ f ′′ := f ∨ f ′ f ∨ f ′′ . (2.3)
Proposition 2.3. For any f ∈ D * , the poset D * (f) is a lattice for the operations ∧ and ∨.

We call duplicative forest lattice of f ∈ D * the lattice D * (f). To show that each subposet P (t), t ∈ T(G), of P is a lattice, we introduce a poset isomorphism between P (t) and an interval of a lattice of duplicative forests. For this, let fr : T(G) → D * be the map defined, for any x i ∈ X and t, t ′ , t ′′ ∈ T(G), by fr(x i ) := fr(M) := fr(MM) := ϵ, fr(Mx i ) := , fr(M(tt ′ )) := (fr(tt ′ )), fr(x i t) := fr(t), and fr((tt ′ )t ′′ ) := fr(tt ′ ) fr(t ′′ ). For instance,

M x 1 x 1 M M M M M x 3 x 2 x 2 x 2 M
Immediately from the definition, we observe that this map is not injective. It can be shown by structural induction on duplicative forests that the image of fr is the set of all duplicative forests with no black nodes. Proposition 2.4. For any t ∈ T(G), the posets P (t) and D * (fr(t)) are isomorphic. Theorem 2.5. For any t ∈ T(G), the poset P (t) is a finite lattice.

The Mockingbird lattice of order d ⩾ 0 is the lattice M(d) := P (r d ) where r d is the combinator defined by r 0 := M and, for any d ⩾ 1, by r d := Mr d-1 . Figure 3 shows the Hasse diagrams of the first Mockingbird lattices. These lattices are not graded, not self-dual, and not semidistributive. Theorem 2.6. For any f ∈ D * , the poset D * (f) is isomorphic to a maximal interval of a Mockingbird lattice.

Theorem 2.6 justifies the fact that the study of the Mockingbird lattices is universal enough because these lattices contain as maximal interval all duplicative forests lattices.

Enumerative properties

Let K be any field of characteristic zero. For any set X, let K⟨X⟩ be the linear span of X. The dual space of K⟨X⟩ is denoted by K⟨⟨X⟩⟩ and is by definition the space of the maps f : X → K, called X-series. The coefficient f(x) of any x ∈ X is denoted by ⟨x, f⟩.

The support of f is the set Supp(f) := {x ∈ X : ⟨x, f⟩ ̸ = 0}. The characteristic series of any subset X ′ of X is the series c(X ′ ) having X ′ as support and such that the coefficient of each x ∈ X ′ is 1. For any k ⩾ 0, T k K⟨⟨X⟩⟩ is the k-th tensor power of K⟨⟨X⟩⟩. Elements of this space are possibly infinite linear combinations of tensors x 1 ⊗ • • • ⊗ x k , where for any i ∈ [k], x i ∈ X. The tensor algebra of K⟨⟨X⟩⟩ is the space T * K⟨⟨X⟩⟩ := k⩾0 T k K⟨⟨X⟩⟩.

A linear map ϕ :

T k 1 K⟨⟨X⟩⟩ → T k 2 K⟨⟨X⟩⟩, k 1 , k 2 ⩾ 0, is a (k 1 , k 2 )
-operation on K⟨⟨X⟩⟩. The diagonal coproduct is the (1, 2)-operation ∆ on K⟨⟨X⟩⟩ satisfying ∆(x) = x ⊗ x for any x ∈ X. When X is endowed with an associative operation ⋆ : X 2 → X, the ⋆-flattening map is for any k ⩾ 1 the (k, 1)-operation P k ⋆ on K⟨⟨X⟩⟩ satisfying P

k ⋆ (x 1 ⊗ • • • ⊗ x k ) = x 1 ⋆ • • • ⋆ x k for any x 1 , . . . , x k ∈ X. When X is endowed with an n-ary operation ⋆ : X n → X, n ⩾ 0, the linearization of ⋆ is the (n, 1)-operation ⋆ on K⟨⟨X⟩⟩ satisfying ⋆(x 1 ⊗ • • • ⊗ x n ) = ⋆(x 1 , . . . , x n ) for any x 1 , . . . , x n ∈ X. When n = 1,
by a slight abuse of notation, for any k ⩾ 1 and x 1 , . . . ,

x k ∈ X, we set ⋆(x 1 ⊗ • • • ⊗ x k ) := ⋆(x 1 ) ⊗ • • • ⊗ ⋆(x k ).
To lighten the notation, when ⋆ is a (2, 1)-operation on K⟨⟨X⟩⟩, we will use ⋆ as an infix operation by writing

f 1 ⋆ f 2 for ⋆(f 1 ⊗ f 2 ) for any f 1 , f 2 ∈ K⟨⟨X⟩⟩.
The space of the usual power series on the formal parameter z is denoted by K⟨⟨z⟩⟩. For any F, F ′ ∈ K⟨⟨z⟩⟩, F[z := F ′ ] is the series of K⟨⟨z⟩⟩ obtained by substituting F ′ for z in F. The Hadamard product is the binary operation ⊠ on K⟨⟨z⟩⟩ defined linearly for any n 1 , n 2 ⩾ 0 by z n 1 ⊠ z n 2 := 1 n 1 =n 2 z n 1 . The max product is the binary operation ↑ on K⟨⟨z⟩⟩ defined linearly for any n 1 , n 2 ⩾ 0 by z n 1 ↑ z n 2 := z max{n 1 ,n 2 } . If X is endowed with a map ω : X → N, the ω-enumeration map is the partial map en ω : T * K⟨⟨X⟩⟩ → K⟨⟨z⟩⟩ defined linearly for any k ⩾ 1 and x 1 , . . . ,

x k ∈ X by en ω (x 1 ⊗ • • • ⊗ x k ) := z ω(x 1 ) ↑ . . . ↑ z ω(x k ) .

S. Giraudo

For any f ∈ T * K⟨⟨X⟩⟩, the generating series en ω (f) is the ω-enumeration of f. In the sequel, we shall use the following strategy to enumerate a set X w.r.t. such a map ω: we shall provide a description of c(X), then deduce a description of en ω (c(X)), and finally deduce from this a formula to compute the coefficients ⟨z n , en ω (c(X))⟩, n ⩾ 0.

Recall now that ⋆ is the binary operation on T(G) satisfying, for any t 1 , t 2 ∈ T(G), t 1 ⋆ t 2 = t 1 t 2 . Proposition 2.2 leads to the following result.

Proposition 3.1. The characteristic series f max of the maximal combinators of P satisfies

f max = M + MM + f max ⋆ f max -M ⋆ f max (3.1)
and the characteristic series f min of the minimal combinators of P satisfies

f min = M + MM + f min ⋆ f min -⋆(∆(f min )). (3.2)
A consequence of Proposition 3.1 is that the deg-enumeration F max of f max satisfies

F max = 1 + z + zF 2 max -zF max . The first coefficients are 1, 1, 1, 2, 4, 9, 21
, 51 and form Sequence A001006 (Motzkin numbers) of [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF]. Another consequence of Proposition 3.1 is that the deg-enumeration F min of f min satisfies

F min = 1 + z + zF 2 min -z F min z := z 2 .
We deduce from this that the number of these terms of degree d ⩾ 0 is a(d) where a is the integer sequence satisfying a(0) = a(1) = 1 and, for any d ⩾ 2,

a(d) = b(d -1) -1 d is odd a((d -1)/2) where b(d) := ∑ i∈ d] a(i) a(d -i). (3.3)
The first numbers are 1, 1, 2, 4, 12, 34, 108, 344 and form Sequence A343663 of [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF].

By Proposition 2.1, C has the properties described at the very end of Section 1. Therefore, the ht-enumerations of f max and f min are equal and is the generating series of the ≡-equivalence classes of terms w.r.t. the height of their terms. By Proposition 3.1, by denoting it by F, it satisfies F = 1 + z + z(F ↑ F) -zF. Therefore, the number of these ≡-equivalence classes of terms of height h ⩾ 0 is a(h) where a is the integer sequence satisfying a(0) = a(1) = 1 and, for any h ⩾ 2,

a(h) = a(h -1) 2 -a(h -1) + 2a(h -1) ∑ i∈[h-1] a(i -1). ( 3.4)
The first numbers are 1, 1, 2, 10, 170, 33490, 1133870930, 1285739648704587610 and form Sequence A063573 of [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF].

Let us now consider series on duplicative forests in order to obtain enumerative results on the Mockingbird lattices by using Proposition 2.4. For any k ⩾ 1 and u ∈ { , } k , the merging product is the (k + |u| , k)-operation on K⟨⟨D * ⟩⟩ satisfying, for any f 1 , . . . , Let gr be the (1, 1)-operation on K⟨⟨D * ⟩⟩ satisfying, for any f ∈ D * ,

f k+|u| ∈ D * , mg (f 1 ) = (f 1 ), mg u ′ (f 1 ⊗ • • • ⊗ f k ) = mg (f 1 ) ⊗ mg u ′ (f 2 ⊗ • • • ⊗ f k ), mg (f 1 ⊗ f 2 ) = (f 1 f 2 ), and mg u ′ (f 1 ⊗ • • • ⊗ f k ) = mg (f 1 ⊗ f 2 ) ⊗ mg u ′ (f 3 ⊗ • • • ⊗ f k ), where u ′ ∈ { , } * . For instance, mg ( ⊗ ⊗ ⊗ ⊗ ) = ⊗ ⊗ . ( 3
gr(f) = ∑ f ′ ∈D * (f) f ′ . (3.7)
By definition, gr(f) is the characteristic series of D * (f). For instance,

gr = + + + + + + + . (3.8)
Observe that gr(ld) is the characteristic series of L and that en ht (gr(ld)) is the generating series of the cardinalities of the lattices D * (l d ), enumerated w.r.t. d ⩾ 0.

Theorem 3.2. The series gr(ld) satisfies gr(ld) = ϵ + ¯(gr(ld)) + ¯ gr P 2 (∆(ld)) .

(3.9)

We deduce from Theorem 3.2 that the ht-enumeration F of gr(ld) satisfies F = 1 + zF + z(F ⊠ F) so that for any d ⩾ 1, the number of elements in M(d) is a(d -1) where a is the integer sequence satisfying a(0) = 1 and, for any d ⩾ 1,

a(d) = a(d -1) + a(d -1) 2 .
(3.10)

The sequence of the cardinalities of M(d), d ⩾ 0, starts by 1, 1, 2, 6, 42, 1806, 3263442, 10650056950806 and forms Sequence A007018 of [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF].

Let cv be the (1, 1)-operation on K⟨⟨D * ⟩⟩ satisfying, for any f ∈ D * ,

cv(f) = ∑ f ′ ∈D * f ⇒ ⇒ f ′ f ′ . (3.11)
Let also ni be the (1, 1)-operation on K⟨⟨D * ⟩⟩ satisfying ni(f) = cv(gr(f)) for any f ∈ D * . By a straightforward computation, we obtain

ni(f) = ∑ f ′ ∈D * (f) # f ′′ ∈ D * (f) : f ′′ ⇒ ⇒ f ′ f ′ , (3.12)
S. Giraudo so that the coefficient of each f ′ ∈ D * (f) in ni(f) is the number of duplicative forests admitting f ′ as covering in D * (f). For instance (see at the same time Figure 2),

ni = + + 2 + + 2 + + + 2 + 2 + 3 + 4 . ( 3
a(d) = a(d -1) + b(d -1) + 2a(d -1)b(d -1), (3.15)
where b is the integer sequence such that for any d ⩾ 0, b(d) is the number of elements of D * (l d ), satisfying therefore (3.10). The sequence of the number of edges of the Hasse diagram of M(d), d ⩾ 0, starts by 0, 0, 1, 7, 97, 8287, 29942737, 195432804247687. This sequence does not appear in [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF] for the time being. Now, let ns be the (1, 1)-operation on K⟨⟨D * ⟩⟩ satisfying ns(f) = gr(gr(f)) for any f ∈ D * . By a straightforward computation, we obtain Contrary to what we have undertaken previously to express gr(ld) and ni(ld), we fail to directly express ns(ld). The trick here consists in considering first a slightly different series depending on a parameter k ⩾ 1 which can be seen as a catalytic parameter. For any k ⩾ 1, let md k be the (1, k)-operation on K⟨⟨D * ⟩⟩ satisfying, for any f ∈ D * ,

ns(f) = ∑ f ′ ∈D * (f) # f, f ′ f ′ , ( 3
md k (f) = ∑ g 1 ,...,g k ∈D * (f) g 1 ∧...∧g k =f g 1 ⊗ • • • ⊗ g k . ( 3

.18)

We call md k (f) the meet k-decomposition of f. Observe that md 1 is the identity map.

Observe that Supp(ns(ld)) = L and that en ht (md 1 (ns(ld))) is the generating series of the number of intervals of the lattices D * (l d ), enumerated w.r.t. d ⩾ 0.

Theorem 3.4. The series ns(ld) satisfies ns(ld) = md 1 (ns(ld)) where, for any k ⩾ 1, the series md k (ns(ld)) satisfies md k (ns(ld)) = ϵ ⊗k + ∑ u∈{ , } k mg u md k+|u| (ns(ld)) + ¯ md k ns P k (∆(ld)) .

(3.19)

We deduce from Theorem 3.4 that the ht-enumeration F of ns(ld) satisfies F = F 1 where, for any k ⩾ 1, F k is the ht-enumeration of md k (ns(ld)) which satisfies

F k = 1 + z(F k ⊠ F k ) + z ∑ i∈ k] ( k i )F k+i .
Therefore, for any d ⩾ 1, the number of intervals in M(d) is a 1 (d -1) where for any k ⩾ 1, a k is the integer sequence satisfying a k (0) = 1 and, for any d ⩾ 1,

a k (d) = a k (d -1) 2 + ∑ i∈ k] k i a k+i (d -1). (3.20)
The sequence of the number of intervals of M(d), d ⩾ 0, starts by 1, 1, 3, 17, 371, 144513, 20932611523, 438176621806663544657. This sequence does not appear in [START_REF] Sloane | The On-Line Encyclopedia of Integer Sequences[END_REF] for the time being.

Open questions and future work

We have studied a CLS having many rich combinatorial properties despite its simplicity. This can be considered as the prototypical example for this kind of investigation. We expect to discover similar properties for more complex CLS. Additionally, here are three open questions raised by this work. (1) The description of minimal and maximal elements of P uses a notion of pattern avoidance in terms. This is a general fact: when a CLS (G, →) has the poset property, its minimal (resp. maximal) elements are the terms avoiding terms deduced from the ones appearing as right-hand (resp. left-hand) members of →. Such an enumerative problem has been considered in [START_REF] Giraudo | Tree series and pattern avoidance in syntax trees[END_REF] for the particular case of terms without repeating variables. We ask here for the general enumeration of terms avoiding a set of terms wherein multiple occurrences of a same variable are allowed.

(2) We have shown that the Mockingbird CLS has the poset property, is rooted, and has the lattice property by employing some specific reasoning from the definition of the basic combinator M. A question here concerns the existence of a general criterion to decide if a CLS has the poset (resp. lattice) property and if it is rooted. (3) Finally, we have seen from Proposition 1.2 that being hierarchical is a sufficient condition for a CLS C to be locally finite. The question in this context consists in strengthening this result in order to obtain a necessary and sufficient condition for this last property.

  G → (II(III)).

Figure 1 :

 1 Figure 1: Some subgraphs of rewrite graphs of some CLS.

Proposition 1 . 1 .Proposition 1 . 2 .

 1112 Any CLS is confluent. If all basic combinators of a CLS C are hierarchical, then C is locally finite and all the G-terms of a same connected component of G C have the same height.

Figure 2 :

 2 Figure 2: The Hasse diagram of a maximal interval of the poset of duplicative forests.

Figure 3 :

 3 Figure 3: The Hasse diagrams of the Mockingbird lattices M(d) for d ∈ 4].

. 5 )

 5 For any d ⩾ 0, the d-ladder is the duplicative forest l d defined recursively by l 0 := ϵ and, for any d ⩾ 1, by l d := (l d-1 ). Let us denote by L the set d⩾0 D * (l d ). The series of ladders is the unique D * -series ld satisfying ld = ϵ + ¯(ld). Hence, ld = ∑ d⩾0 l d = ϵ + + + + + • • • . (3.6)

. 13 )Theorem 3 . 3 .

 1333 Observe that Supp(ni(ld)) = L \ {l d : d ⩾ 0} and that en ht (ni(ld)) is the generating series of the number of edges of the Hasse diagrams of the lattices D * (l d ), enumerated w.r.t. d ⩾ 0. The series ni(ld) satisfies ni(ld) = ¯(ni(ld)) + ¯ ni P 2 (∆(ld)) + ¯ P 2 (∆(gr(ld))) . (3.14) We deduce from Theorem 3.3 that the ht-enumeration F of ni(ld) satisfies F = zF + zG + 2z(F ⊠ G) where G is the ht-enumeration of gr(ld). Therefore, for any d ⩾ 1, the number of edges in the Hasse diagram of M(d) is a(d -1) where a is the integer sequence satisfying a(0) = 0 and, for any d ⩾ 1,

  and t ′ 1 , . . . , t ′ n , n ⩾ 0, be G-terms. The composition of t with t ′ 1 , . . . , t ′ n is the G-term t[t ′ 1 , . . . , t ′ n ] obtained by simultaneously replacing for all i ∈ [n] all occurrences of the variables x i in t by t

  We call C the Mockingbird CLS. From now, we shall simply write G instead of G C . The Mockingbird CLS is locally finite, has the poset property, and is rooted. Proposition 2.1 is a consequence of the fact that M is hierarchical and of Proposition 1.2. By Proposition 2.1, P C is a well-defined poset. From now, we shall simply write P instead of P C . A combinator t is a maximal (resp. minimal) element of P if and only if t avoids

	Proposition 2.1. Proposition 2.2.

  .16) so that the coefficient of each f ′ ∈ D * (f) in ns(f) is the number of duplicative forests smaller than or equal to f ′ in D * (f). For instance (see at the same time Figure2),

	ns	=	+ 2 + 2 + 4 + 2	+ 4	+ 3	+ 3	+ 6	+ 6
						+ 6	+ 12	. (3.17)

M ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ ⋆ fr -→ . (2.4)

This research has been partially supported by the projects CARPLO (ANR-20-CE40-0007) and LambdaComb (ANR-21-CE48-0017) of the Agence nationale de la recherche.