Bachar Alhajjar
email: bachar.alhajjar@gmail.com

THE FILTRATION INDUCED BY A LOCALLY NILPOTENT DERIVATION

We investigate the filtration corresponding to the degree function induced by a non-zero locally nilpotent derivations ∂ and its associated graded algebra. As an application we provide an efficient method to recover the Makar-Limanov invariants, isomorphism classes and automorphism groups of classically known algebras. We also present a new class of examples which can be fully described with this method.

Introduction

Let k be a field of characteristic zero, and let B be a commutative k-domain. A k-derivation ∂ ∈ Der k (B) is said to be locally nilpotent if for every a ∈ B, there is an integer n ≥ 0 such that ∂ n (a) = 0. An important invariant of k-domains admitting non-trivial locally nilpotent derivations is the so called Makar-Limanov invariant which was defined by Makar-Limanov as the intersection ML(B) ⊂ B of kernels of all locally nilpotent derivations of B ( [START_REF] Makar-Limanov | On the hypersuface x + x 2 y + z 2 + t 3 = 0 in C 4 or a C 3 -like threefold which is not C 3[END_REF]). This invariant was initially introduced as a tool to distinguish certain k-domains from polynomial rings but it has many other applications for the study of k-algebras and their automorphism groups ( [START_REF] Makar-Limanov | On the group of automorphisms of a surfacex n y = P (z)[END_REF]). One of the main difficulties in applications is to compute this invariant without a prior knowledge of all locally nilpotent derivations of a given k-domain.

In [START_REF] Sh | AK-invariant of affine domains[END_REF] S. Kaliman and L. Makar-Limanov developed general techniques to determine the ML-invariant for a class of finitely generated k-domains B. The idea is to reduce the problem to the study of homogeneous locally nilpotent derivations on graded algebras Gr(B) associated to B. For this, one considers appropriate filtrations F = {F i } i∈R on B generated by so called real-valued weight degree functions in such a way that every non-zero locally nilpotent derivation on B induces a non-zero homogeneous locally nilpotent derivation on the associated graded algebra Gr F (B).

In particular, every k-domain B admitting a non-zero locally nilpotent derivation ∂ comes equipped with a natural filtration by the k-sub-vector-spaces F i = ker(∂ i+1 ), i ≥ 0, that we call the ∂-filtration.

In this article we show that this filtration is convenient for the computation of the ML-invariant, and we give general methods to describe the sub-spaces ker(∂ i+1 ) and their associated graded algebra.

Knowing this filtration gives a very precise understanding of the structure of semi-rigid k-domains, that is,k-domains for which every locally nilpotent derivation gives rise to the same filtration. For such rings the study of the ∂-filtration is a very efficient tool to determine isomorphism types and automorphism groups. We illustrate how the computation of ML-invariant of classically known semi-rigid kdomains can be simplified using these types of filtration. We also present a new class of semi-rigid k-domains which can be studied with this method.

Preliminaries

In this section we briefly recall basic facts on filtered algebra and their relation with derivation in a form appropriate to our needs.

In the sequel, unless otherwise specified B will denote a commutative domain over a field k of characteristic zero. The set Z 0 of non-negative integers will be denoted by N.

1.1. Filtration and associated graded algebra. Definition 1.1. An N-filtration of B is a collection {F i } i∈N of k-sub-vector-spaces of B with the following properties:

1-

F i ⊂ F i+1 for all i ∈ N . 2-B = ∪ i∈N F i .
3-F i .F j ⊂ F i+j for all i, j ∈ N . The filtration is called proper if the following additional property holds:

4-If a ∈ F i \ F i-1 and b ∈ F j \ F j-1 , then ab ∈ F i+j \ F i+j-1 .
There is a one-to-one correspondence between proper N-filtrations and so called N-degree functions: Indeed, for an N-degree function on B, the sub-sets

F i = {b ∈ B | deg(b) ≤ i} are k-subvector spaces of B that give rise to a proper N-filtration {F i } i∈N . Conversely, every proper N-filtration {F i } i∈N , yields an N-degree function ω : B -→ N∪{-∞} defined by ω(0) = -∞ and ω(b) = i if b ∈ F i \ F i-1 . Definition 1.3. Given a k-domain B = ∪ i∈N F i equipped with a proper N-filtration, the associated graded algebra Gr(B) is the k-vector space Gr(B) = ⊕ i∈N F i /F i-1
equipped with the unique multiplicative structure for which the product of the elements a

+ F i-1 ∈ F i /F i-1 and b + F j-1 ∈ F j /F j-1 , where a ∈ F i and b ∈ F j , is the element (a + F i-1 )(b + F j-1 ) := ab + F i+j-1 ∈ F i+j /F i+j-1 .
Property 4 (proper) in Definition 1.1 ensures that Gr(B) is a commutative k-domain when B is an integral domain. Since for each a ∈ B the set {n ∈ N | a ∈ F n } has a minimum, there exists i such that a ∈ F i and a / ∈ F i-1 . So we can define a k-linear map gr : B -→ Gr(B) by sending a to its class in F i /F i-1 , i.e a → a + F i-1 , and gr(0) = 0. We will frequently denote gr(a) simply by a. Observe that gr(a) = 0 if and only if a = 0. If so, we define a k-linear map D : Gr(B) -→ Gr(B) as follows: If D = 0, then D = 0 the zero map. Otherwise, if D = 0 then we let d be the least integer such that D(F i ) ⊂ F i+d for all i ∈ N and we define

+ F i-1 = (a + F i-1 ) + (b + F i-1 ), and since F j-1 ⊂ F j ⊆ F i-1 as i > j, we get b + F i-1 = 0. P3) is
D : F i /F i-1 -→ F i+d /F i+d-1
by the rule D(a + F i-1 ) = D(a) + F i+d-1 . One checks that D satisfies the Leibniz rule, therefore it is a k-derivation of the graded algebra Gr(B). Moreover it is homogeneous of degree d, i.e D sends homogeneous elements of degree i to zero or to homogeneous elements of degree i + d .

Observe that D = 0 if and only if D = 0. In addition, gr(ker D) ⊂ ker D.

LND-Filtrations and Associated Graded Algebras

In this section we introduce the ∂-filtration associated with a locally nilpotent derivation ∂. We explain how to compute this filtration and its associated graded algebra in certain situation. Definition 2.1. A k-derivation ∂ ∈ Der k (B) is said to be locally nilpotent if for every a ∈ B, there exists n ∈ N (depending of a) such that ∂ n (a) = 0. The set of all locally nilpotent derivations of B is denoted by LND(B).

In particular, every locally nilpotent derivation ∂ of B gives rise to a proper Nfiltration of B by the sub-spaces F i = ker∂ i , i ∈ N, that we call the ∂-filtration. It is straightforward to check (see Prop. 1.9 in [START_REF] Freudenburg | Algebraic Theory of Locally Nilpotent Derivation[END_REF]) that the ∂-filtration corresponds to the N-degree function deg The next Proposition, which is due to Daigle (Theorem 2.11 in [START_REF] Freudenburg | Algebraic Theory of Locally Nilpotent Derivation[END_REF]), implies in particular that if B is of finite transcendence degree over k, then every non-zero D ∈ LND(B) respects the ∂-filtration and therefore induces a non-zero homogeneous locally nilpotent derivation D of Gr ∂ (B). Proposition 2.2. (Daigle) Suppose that B is a commutative domain, of finite transcendence degree over k. Then for every pair D ∈ Der k (B) and ∂ ∈ LND(B), D respects the ∂-filtration. Consequently, D is a well defined homogeneous derivation of the integral domain Gr ∂ (B) relative to this filtration, and it is locally nilpotent if D is locally nilpotent.

Computing the ∂-filtration.

Here, given a finitely generated k-domain B, we describe a general method which enables the computation of the ∂-filtration for a locally nilpotent derivation ∂ with finitely generated kernel. First we consider a more general situation where the plinth ideal pl(∂) is finitely generated as an ideal in ker ∂ then we deal with the case where ker ∂ is itself finitely generated as a k-algebra.

Let B = k[X 1 , . . . , X n ]/I = k[x 1 , . . . , x n ] be a finitely generated k-domain, and let ∂ ∈ LND(B) be such that pl(∂) is generated by precisely m elements f 1 , . . . , f m as an ideal in ker ∂. Denote by F = {F i } i∈N the ∂-filtration, then:

By definition F 0 = ker ∂. Furthermore, given elements s i ∈ F 1 such that ∂(s i ) = f i for every i ∈ {1, . . . , m}, it is straightforward to check that

F 1 = F 0 s 1 + . . . + F 0 s m + F 0 . Letting deg ∂ (x i ) = d i , we denote by H j the F 0 -sub-module in B generated by elements of degree j relative to deg ∂ of the form s u1 1 . . . s um m x v1 1 . . . x vn n , i.e., H j := j uj + i di.vi=j F 0 (s u1 1 . . . s um m x v1 1 . . . x vn n )
where u j , v i ∈ N for all i and j. The integer

j u j + i d i v i is nothing but deg ∂ (s u1 1 .s u2 2 . . . .s um m .x v1 1 .x v2 2 . . . . .x vn n ). Then we define a new N-filration G = {G i } i∈N of B by setting G i = j≤i H j .
By construction G i ⊆ F i for all i ∈ N, with equality for i = 0, 1. The following result provides a characterization of when these two filtrations coincide: Lemma 2.3. The filtrations F and G are equal if and only if G is proper.

Proof. One direction is clear since F is proper. Conversely, suppose that G is proper with the corresponding N-degree function ω on B (see [START_REF] Makar-Limanov | Locally nilpotent derivations, a new ring invariant and applications[END_REF]). Since ω(g) = 0 (resp. ω(g) = 1) for every g ∈ F 0 (resp. g ∈ F 1 \ F 0 ), we obtain

§1.1). Given f ∈ F i \ F i-1 , i > 1, for every local slice s ∈ F 1 \ F 0 , there exist f 0 = 0, a i = 0, a i-1 , . . . , a 0 ∈ F 0 such that f 0 f = a i s i + a i-1 s i-1 + • • • + a 0 ( see the proof of Lemma 4 in
ω(f ) = ω(f 0 f ) = ω(a i s i + a i-1 s i-1 + • • • + a 0 ) = max{ω(a i s i )} = i,
and so f ∈ G i .
Next, we determine the ∂-filtration, for a locally nilpotent derivation ∂ with finitely generated kernel, by giving an effective criterion to decide when the Nfiltration G defined above is proper.

Hereafter, we assume that 0 ∈ Spec(B) and that ker(∂) is generated by elements

z i (x 1 , . . . , x n ) ∈ B such that z i (0, . . . , 0) = 0, i ∈ {1, . . . , r}, which is always possible since k ⊂ ker ∂. Since ker(∂) is finitely generated k-algebra, the plinth ideal pl(∂) is finitely generated. So there exist s 1 (x 1 , . . . , x n ), . . ., s m (x 1 , . . . , x n ) ∈ F 1 such that F 1 = F 0 s 1 + . . . + F 0 s m + F 0 .
We can also assume that s i (0, . . . , 0) = 0.

Letting

J ⊂ k [r+n+m] = k[Z 1 , . . . , Z r ][X 1 , . . . , X n ][S 1 , .
. . , S m ] be the ideal generated by I and the elements

Z 1 = z 1 (X 1 , . . . , X n ), . . . , Z r = z r (x 1 , . . . , x n ), S 1 = s 1 (X 1 , . . . , X n ), . . . , S m = s m (x 1 , . . . , x n ), then we have B = k[Z 1 , . . . , Z r ][X 1 , . . . , X n ][S 1 , . . . , S m ]/J.
Note that by construction (0, . . . , 0)

r+n+m times ∈ Spec(k [r+n+m] /J).
We define an N-degree function ω on k [r+n+m] by declaring that ω(Z i ) = 0 = deg ∂ (z i ) for all i ∈ {1, . . . , r}, ω(S i ) = 1 = deg ∂ (s i ) for all i ∈ {1, . . . , m}, and ω(X i ) = deg ∂ (x i ) = d i for all i ∈ {1, . . . , n}. The corresponding proper N-filtration

Q i := {P ∈ k [n] | ω(P ) ≤ i}, i ∈ N, on k [r+n+m] has the form Q i = ⊕ j≤i H j where H j := ⊕ j uj + i divi=j k[Z 1 , . . . , Z r ]S u1 1 . . . S um m X v1 1 . . . X vn n . By construction π (Q i ) = G i where π : k [r+n+m] -→ B denotes the natural projec- tion. Indeed, since π (Q i ) = j≤i π (H j ) and π (H j ) = j uj + i divi=j k[z 1 , . . . , z r ]s u1 1 . . . .s um m x v1 1 . . . x vn n , we get π (H j ) = j uj + i divi=j (ker ∂) s u1 1 . . . . s um m x v1 1 . . . . x vn n which means precisely that π (Q i ) = G i . Let Ĵ ⊂ k [r+n+m]
be the homogeneous ideal generated by the highest homogeneous components relative to ω of all elements in J. Then we have the following result, which is inspired by the technique developed by S. Kaliman and L. Makar-Limanov:

Proposition 2.4. The N-filration G is proper if and only if Ĵ is prime.

Proof. It is enough to show that G = {π (Q i )} i∈N coincides with the filtration corresponding to the N-semi-degree function ω B on B defined by ω B (p) := min P ∈π -1 (p) {ω(P )}. Indeed, if so, the result will follow from Lemma 3.2 in [START_REF] Sh | AK-invariant of affine domains[END_REF] which asserts in particular that ω B is an N-degree function on B if and only if Ĵ is prime. Let {G

′ i } i∈N be the fil- tration corresponding to ω B . Given f ∈ G ′ i there exists F ∈ Q i such that π(F ) = f , which means that G ′ i ⊂ π (Q i ). Conversely, it is clear that ω B (z i ) = ω(Z i ) = 0 for all i ∈ {1, . . . , r}. Furthermore ω B (s i ) = ω(S i ) = 1 for all i ∈ {1, . . . , m}, for oth- erwise s i ∈ ker ∂ which is absurd. Finally, if d i = 0 and ω B (x i ) < ω(X i ) = d i = 0, then x i ∈ π (Q di-1 ) ⊂ ker ∂ di-1 which implies that deg ∂ (x i ) < d i , a contradic- tion. So ω B (x i ) = d i . Thus ω B (f ) ≤ i for every f ∈ π (Q i ) which means that π (Q i ) ⊂ G ′ i .
The next Proposition, which is a reinterpretation of Prop. 4.1 in [START_REF] Sh | AK-invariant of affine domains[END_REF], describes in particular the associated graded algebra Gr ∂ (B) of the filtered algebra (B, F ) in the case where the N-filtration G is proper:

Proposition 2.5. If the N-filtration G is proper then Gr ∂ (B) ≃ k [r+n+m] / Ĵ.
Proof. By virtue of ( Prop. 4.1 in [START_REF] Sh | AK-invariant of affine domains[END_REF]) the graded algebra associated to the filtered algebra (B, G) is isomorphic to k [r+n+m] / Ĵ. So the assertion follows from Lemma 2.3.

Semi-Rigid and Rigid k-Domains

In [START_REF] Finston | Constructing (almost) rigid rings and a UFD having infinitely generated Derksen and Makar-Limanov invariant[END_REF] D. Finston and S. Maubach considered rings B whose sets of locally nilpotent derivations are "one-dimensional" in the sense that LND(B) = ker(∂).∂ for some non-zero ∂ ∈ LND(B). They called them almost-rigid rings. Hereafter, we consider the following definition which seems more natural in our context (see Prop. Proof. Existence: since B is satisfies the ACC on principal ideals, then for every non-zero T ∈ LND(B), there exists an irreducible T 0 ∈ LND(B) and c ∈ ker(T ) such that T = cT 0 . (see [START_REF] Freudenburg | Algebraic Theory of Locally Nilpotent Derivation[END_REF], Prop. 2.2 and Principle 7).

Uniqueness: the following argument is similar to that in [START_REF] Freudenburg | Algebraic Theory of Locally Nilpotent Derivation[END_REF] Prop. 2.2.b, but with a little difference, that is, in [START_REF] Freudenburg | Algebraic Theory of Locally Nilpotent Derivation[END_REF] it is assumed that B itself is an HCF-ring while here we only require that ML(B) is an HCF-ring.

Let D, E ∈ LND(B) be irreducible derivations, and denote A = ML(B). By hypothesis ker(D) = ker(E) = A, so there exist non-zero a, b ∈ A such that aD = bE (see [START_REF] Freudenburg | Algebraic Theory of Locally Nilpotent Derivation[END_REF] Principle 12). Here we can assume that a, b are not units otherwise we are done. Set T = aD = bE. Since A is an HCF-ring, there exists c ∈ A such that aA ∩ bA = cA. Therefore, T (B) ⊂ cB, and there exists T 0 ∈ LND(B) such that T = cT 0 . Write c = as = bt for s, t ∈ B. Then cT 0 = asT 0 = aD implies D = sT 0 , and likewise E = tT 0 . By irreducibility, s and t are units of B, and we are done.

In particular, for a ring B as in 3.2, every D ∈ LND(B) has the form D = f ∂ for some irreducible ∂ ∈ LND(B) and f ∈ ker(∂), and so B is almost rigid in the sense introduced by Finston and Maubach.

Recall that a ring A is called rigid if the zero derivation is the only locally nilpotent derivation of A. Equivalently, A is rigid if and only if ML(A) = A. It is well known that the only non rigid k-domains of transcendence degree one are polynomial rings in one variable over algebraic extensions of k ([1] Corollary 1.24 and Corollary 1.29). In particular, we have the following elementary criterion for rigidity that we will use frequently in the sequel: Lemma 3.3. A domain B of transcendence degree one over a field k of characteristic zero is rigid if one of the following properties hold:

(1) B is not factorial.

(2) Spec(B) has a singular point. We first consider in 4.1.1, certain surfaces in A [3] defined by equations X n Z -P (Y ) where n > 1 and deg Y P (Y ) > 1, which were first discussed by Makar-Limanov in [START_REF] Makar-Limanov | Locally nilpotent derivations, a new ring invariant and applications[END_REF], where he computed their ML-invariants. Later on Poloni [START_REF] Poloni | Sur les plongements des hypersurfaces de Danielewski[END_REF] used similar methods to compute ML-invariants for a larger class. In the second example 4.1.2, we consider certain threefolds whose invariants were computed by S. Kaliman and L. Makar-Limanov [START_REF] Sh | On the Russell-Koras contractible threefolds[END_REF] in the context of the linearization problem for C * -action on C 3 .

In these examples, the use of LND-filtrations is more natural and less tedious than other existing approaches.

4.1.1. Danielewski hypersurfaces. Let B n,P = k[X, Y, Z]/ X n Z -P (X, Y ) where P (X, Y ) = Y m + f m-1 (X)Y m-1 + • • • + f 0 (X), f i (X) ∈ k[X], n ≥ 2,
F mi+j = k[x]y j z i + F mi+j-1
where i ∈ N and j ∈ {0, . . . m -1}. 2-The associated graded algebra Gr(B n,P ) = ⊕ i∈N B i , where

B i = F i /F i-1
, is generated by x = gr ∂ (x), y = gr ∂ (y), z = gr ∂ (z) as an algebra over k with relation

x n z = y m , i.e. Gr(B n,P ) = k[X, Y , Z]/ X n Z -Y m .
And we have :

B mi+j = k[x]y j z i
where i ∈ N and j ∈ {0, . . . m -1}. (2) is an immediate consequence of Proposition 3.2.

Koras-Russell hypersurfaces of the second type.

Here we consider hypersurfaces associated with k-algebras of the form:

B n,e,l,Q = k[X, Y, Z, T ]/ Y (X n + Z e ) l -Q(X, Z, T where Q(X, Z, T ) = T m + f 1 (X, Z)T m-1 + . . . + f m (X, Z) f i (X, Z) ∈ k[X, Z], n > 1, e > 1,
l > 1, and m > 1. We may assume without loss of generality that Q(0, 0, 0) = 0 . A particular case of this family corresponds to the so called Koras-Russell hypersurfaces of the second type considered by S. Kaliman and L. Makar-Limanov ( [START_REF] Sh | On the Russell-Koras contractible threefolds[END_REF]) where they computed their ML-invariants. Here we explain how to apply the LND-filtration method to compute this invariant for all algebras B n,e,l,Q . Let x, y, z, t be the images of X, Y , Z, T in B n,e,l,Q . Define ∂ by

∂ = ∂Q ∂t ∂ y + (X n + Z e ) l ∂ t We see that ∂ ∈ LND(B n,e,l,Q ) with ker(∂) = k[x, z],
F mi+j = k[x, z]t j y i + F mi+j-1
where i ∈ N, and j ∈ {0, . . . , m -1}. 2-The associated graded algebra Gr(B n,e,l,Q ) = ⊕ i∈N B i , where B i = F i /F i-1 , is generated by x = gr ∂ (x), y = gr ∂ (y), z = gr ∂ (z), t = gr ∂ (t) as an algebra over k with the relation y(

x n + z e ) l = t m , i.e. Gr(B n,e,l,Q ) = k[X, Y , Z, T ]/ Y (X n + Z e ) l -T m .
And we have :

B mi+j = k[x, z]t j y i
where i ∈ N, and j ∈ {0, . . . , m -1}. (2) follows again from Proposition 3.2.

A new class of semi-rigid rings

In this section, we use the LND-filtration method to establish the semi-rigidity of new families of two dimensional domains of the form

R = k[X, Y, Z]/ X n Y -P (X, Q(X, Y ) -X e Z)
for suitable integers n, e ≥ 2 and polynomials P (X, T ), Q(X, T ) ∈ k[X, T ]. They share with Danielewski hypersurfaces discussed in 4.1.1 above, the property to come naturally equipped with an irreducible locally nilpotent derivation induced by a locally nilpotent derivation of k[X, Y, Z]. But in contrast with the Danielewski hypersurfaces case, the corresponding derivation on k[X, Y, Z] are no longer triangular, in fact not even triangulable by virtue of characterization due to Daigle [START_REF] Daigle | A necessary and sufficient condition for triangulability of derivation of k[X, Y, Z][END_REF].

We will begin with a very elementary example illustrating the steps needed to determine the LND-filtration and its associated graded algebra, and then we proceed to the general case.

A toy example.

We let

R = k[X, Y, Z]/ X 2 Y -(Y 2 -XZ) 2
and we let x, y, z be the images of X, Y , Z in R. A direct computation reveals that the derivation

2XS∂ Y + (4Y S -X 2 )∂ Z of k[X, Y, Z]
where S := Y 2 -XZ is locally nilpotent and annihilates the polynomial

X 2 Y -(Y 2 -XZ) 2 . It induces a locally nilpotent derivation ∂ of R for which we have ∂(x) = 0, ∂ 3 (y) = 0, ∂ 5 (z) = 0. Furthermore, the element s = y 2 -xz is a local slice for ∂ with ∂(s) = x 3 . The kernel of ∂ is k[x]
and the plinth ideal is the principal ideal generated by x 3 . We have deg

∂ (x) = 0, deg ∂ (y) = 2, deg ∂ (z) = 4, deg ∂ (s) = 1.
Proposition 5.1. With the notation above, we have:

(1) The ∂-filtration {F i } i∈N is given by :

F 4i+2j+l = k[x]s l y j z i + F 4i+2j+l-1
where i ∈ N, j ∈ {0, 1}, l ∈ {0, 1}.

(2) The associated graded algebra

Gr ∂ (R) = ⊕ i∈N R i , where R i = F i /F i-1
, is generated by x = gr ∂ (x), y = gr ∂ (y), z = gr ∂ (z), s = gr ∂ (s) as an algebra over k with relations x 2 z = s 2 and x z = y 2 , i.e.

Gr ∂ (R) = k[X, Y , Z, S]/ X 2 Z - S 2 , XZ -Y 2 . Furthermore: R 4i+2j+l = k[x]s l y j z i where i ∈ N, j ∈ {0, 1}, l ∈ {0, 1, 2, 3}. Proof. 1) First, the ∂-filtration {F i } i∈N is given by F r = h≤r H h where H h := u+2v+4w=h k[x] (s u y v z w ) and u, v, w, h ∈ N.
To show this, let J be the ideal in k [4]

= k[X, Y, Z, S] defined by J = X 2 Y -(Y 2 -XZ) 2 , Y 2 -XZ -S .
Define an N-degree function ω on k [4] by declaring that ω(X) = 0, ω(S) = 1, ω(Y ) = 2, and ω(Z) = 4. By Lemma 2.4, the N-filtration {G r } i∈N where G r = h≤r H h is proper if and only if Ĵ is prime. Which is the case since Ĵ = X 2 Y -S 2 , Y 2 -XZ is prime. Thus by Lemma 2.3 we get the desired description.

Second, let l ∈ {0, 1} and j ∈ {0, 1, 2, 3} be such that l := r mod 2, j := r -l mod 4, and i := r-2j-l 4 . Then we get the following unique expression r = 4i + 2j + l. Since F r = u+2v+4w=r k[x] (s u y v z w ) + F r-1 , we conclude in particular that F r ⊇ k[x]s l y j z i + F r-1 . For the other inclusion, the relation x 2 y = s 2 allows to write s u y v z w = x e s l y v0 z w and from the relation y 2 = s + zx we get x e s l y v0 z w = x e s l y j (s + xz) n z w . Since the monomial with the highest degree relative to deg ∂ in (s+xz) n is x n .z n , we deduce that x e s l y j (s+xz) n z w = x e+n s l y j z w+n + M β where M β is monomial in x, y, s, z of degree less than r. Since the expression r = 4i+2j+l is unique, we get w + n = i. So s u y v z w = x e+n s l y j z i + f where

f ∈ F r-1 . Thus k[x] (s u y v z w ) ⊆ k[x]s l y j z i + F r-1 and finally F r = k[x]s l y j z i + F r-1 .
2) By part (1), an element f of degree r can be written as f = g(x)s l y j z i + f 0 where f 0 ∈ F r-1 , l = r mod 2, j = r -l mod 4, i = r-2j-l 4 , and i ∈ N, j ∈ {0, 1}, l ∈ {0, 1}. So by Lemma 1.4, P2, P1, P3 respectively we get f = g(x)s l y j z i + h = g(x)s l y j z i = g(x)s l y j z i = g(x)s l y j z i and therefore B 4i+2j+l = k[x]s l y j z i .

Finally, by Proposition 2.5, Gr

∂ (B) = k[X, Y , Z, S]/ X 2 Z -S 2 , X Z -Y 2 .

A more general family.

We now consider more generally rings R of the form

k[X, Y, Z]/ X n Y -P (X, Q(X, Y ) -X e Z)
where 1-The ∂-filtration {F i } i∈N is given by :

P (X, S) = S d + f d-1 (X)S d-1 + • • • + f 1 (X)S + f 0 (X) Q(X, Y ) = Y m + g m-1 (X)Y m-1 + • • • + g 1 (X)Y + g 0 (X) n ≥ 2, d ≥ 2, m ≥ 1,
F mdi+dj+l = k[x]s l y j z i + F mdi+dj+l-1
where i ∈ N, j ∈ {0, . . . , m -1}, l ∈ {0, . . . , d -1}. 2-The associated graded algebra Gr(R) = ⊕ i∈N R i , where (2) follows again from Proposition 3.2. The following Corollary shows a nice property of a semi-rigid ring. That is, every algebraic automorphism α has to preserve the unique filtration induced by any locally nilpotent derivation ∂, i.e. α sends an element of degree i relative to ∂ to an element of the same degree relative to ∂. Which makes the computation of the group of automorphisms easier up to the automorphism group of ker(∂). where Aut k (B, ML(B)) is by definition the sub-group of Aut k (B) consisting of elements whose induced action on ML(B) is trivial. Furthermore, every element of Aut k (B, ML(B)) induces for every i ≥ 1 an automorphism of F 0 -module of each F i . In this section we illustrate how to exploit these information to compute Aut k (B) for certain semi-rigid k-domains B. In [START_REF] Makar-Limanov | Locally nilpotent derivations, a new ring invariant and applications[END_REF] Makar-Limanov computed the k-automorphism group for surfaces in k [3] defined by equation X n Z -P (Y ) = 0 where n > 1 and deg Y P (Y ) > 1. Then Poloni, see [START_REF] Poloni | Sur les plongements des hypersurfaces de Danielewski[END_REF], generalized Makar-Limanov's method to obtained similar results for the rings considered in 4. In addition, x n divides every coefficient of H as a polynomial in y, so x n divides -µ m f m-i (x) + µ m-i f m-i (λx) because coefficients of H(y) are of the form q(x, y)b(x) -µ m f m-i (x) + µ m-i f m-i (λx) and b(x) is divisible by x n . So x n divides -µ i f m-i (x) + f m-i (λx) for every i. And we are done. 6.1.2. Aut k for example 5.2. The same method as in 6.1.1 can be applied to compute automorphism groups of rings R defined as in Theorem 5.2. For simplicity we only deal with the case where Q(X, Y ) = Y m , the general case can be deduced in the same way at the cost of longer and more complicated computation. Again we make a substitution in S as in 6.

R i = F i /F i-1 ,

Definition 1 . 2 .

 12 An N-degree function on B is a map deg : B -→ N∪{-∞} such that, for all a, b ∈ B, the following conditions are satisfied: (1) deg(a) = -∞ ⇔ a = 0. (2) deg(ab) = deg(a) + deg(b). (3) deg(a + b) ≤ max{deg(a), deg(b)}. If the equality in (2) replaced by the inequality deg(ab) ≤ deg(a) + deg(b), we say that deg is an N-semi-degree function.

Lemma 1 . 4 .

 14 Denote by deg the N-degree function deg : B -→ N ∪ {-∞} corresponding to the proper N-filtration {F i } i∈N . We have the following properties. Given a, b ∈ B the following holds: P1) a b = a b, i.e. gr is a multiplicative map. P2) If deg(a) > deg(b), then a + b = a. P3) If deg(a) = deg(b) = deg(a + b), then a + b = a + b. P4) If deg(a) = deg(b) > deg(a + b), then a + b = 0, in particular gr is not an additive map in general. Proof. Let us assume that deg(a) = i and deg(b) = j. By definition, deg(ab) = i + j means that ab ∈ F i+j and ab / ∈ F i+j-1 , so ab = ab + F i+j-1 := (a + F i-1 )(b + F j-1 ) = a b. Which gives P1. For P2 we observe that since deg(a + b) = deg(a), we have a + b = (a + b)

Definition 1 . 5 .

 15 immediate, by definition. Finally, assume by contradiction that a+b = 0, then a+b = (a+F i-1 )+(b+F i-1 ) = ((a+b)+F i-1 ) = 0, which means that a + b / ∈ F i-1 and deg(a + b) = i, which is absurd. So P4 follows. 1.2. Derivations. By a k-derivation of B, we mean a k-linear map D : B -→ B which satisfies the Leibniz rule: For all a, b ∈ B; D(ab) = aD(b) + bD(a). The set of all k-derivations of B is denoted by Der k (B). The kernel of a derivation D is the subalgebra ker D = {b ∈ B; D(b) = 0} of B. The plinth ideal of D is the ideal pl(D) = ker D ∩ D(B) of kerD, where D(B) denotes the image of B. An element s ∈ B such that D(s) ∈ ker(D) \ {0} is called a local slice for D. Given a k-algebra B = ∪ i∈N F i equipped with a proper N-filtration, a k-derivation D of B is said to respect the filtration if there exists an integer d such that D(F i ) ⊂ F i+d for all i ∈ N.

  ∂ : B -→ N ∪ {-∞} defined by deg ∂ (a) := min{i ∈ N | ∂ i+1 (a) = 0}, and deg ∂ (0) := -∞. Note that by definition F 0 = ker ∂ and that F 1 \ F 0 consists of all local slices for ∂. Let Gr ∂ (B) = ⊕ i∈N F i /F i-1 denote the associated graded algebra relative to the ∂-filtration {F i } i∈N . Let gr ∂ : B -→ Gr ∂ (B); a gr ∂ -→ a be the natural map between B and Gr ∂ (B) defined in 1.3, where a denote gr ∂ (a).

  3.2 below for a comparison between the two notions).Definition 3.1. A commutative domain B over a field k of characteristic zero is called semi-rigid if all non-zero locally nilpotent derivations of B induce the same proper N-filtration (equivalently, the same N-degree function).Recall that the Makar-Limanov invariant of a commutative k-domain B over a field k of characteristic zero is defined byML(B) := ∩ D∈LND(B) ker(D).In particular, B is semi-rigid if and only if ML(B) = ker(∂) for any non-zero ∂ ∈ LND(B). Indeed, given D, E ∈ LND(B) \ {0} such that A := ker(D) = ker(E), there exist non-zero elements a, b ∈ A such that aD = bE (see[START_REF] Freudenburg | Algebraic Theory of Locally Nilpotent Derivation[END_REF] Principle 12) which implies that the D-filtration is equal to the E-filtration. So if ML(B) = ker(∂) for any non-zero ∂ ∈ LND(B) then B is semi-rigid. The other implication is clear by definition.Recall that D ∈ Der k (B) is irreducible if and only if D(B) is contained in no proper principal ideal of B, and that B is said to satisfy the ascending chain condition (ACC) on principal ideals if and only if every infinite chain (b 1 ) ⊂ (b 2 ) ⊂ (b 3 ) ⊂ • • • of principal ideals of B eventually stabilizes. B is said to be a highest common factor ring, or HCF-ring, if and only if the intersection of any two principal ideals of B is again principal. Proposition 3.2. Let B be a semi-rigid k-domain satisfying the ACC on principal ideals. If ML(B) is an HCF-ring, then there exists a unique irreducible ∂ ∈ LND(B) up to multiplication by unit.

3. 1 . 4 . 4 . 1 .

 1441 Elementary examples of semi-rigid k-domains. The next Proposition, which is due to Makar-Limanov ([START_REF] Makar-Limanov | Locally nilpotent derivations, a new ring invariant and applications[END_REF] Lemma 21, also[START_REF] Crachiola | An algebraic proof of a cancellation theorem for surfaces[END_REF] Theorem 3.1), presents some of the simplest examples of semi-rigid k-domains. Proposition 3.4. (Makar-Limanov) Let A be a rigid domain of finite transcendence degree over a field k of characteristic zero. Then the polynomial ring A[x] is semi-rigid.Proof. For the convenience of the reader, we provide an argument formulated in the LND-filtration language. Let ∂ be the locally nilpotent derivation of A[x] defined by ∂(a) = 0 for every a ∈ A and ∂(x) = 1. Then the ∂-filtration {F i } i∈N is given by F i = Ax i ⊕ F i-1 where F 0 = ker(∂) = A. So the associated graded algebra is Gr(A[x]) = ⊕ i∈N Ax i ,where x := gr(x). By Proposition 2.2, every nonzero D ∈ LND(A[x]) respects the ∂-filtration and induces a non-zero homogeneous locally nilpotent derivation D of Gr(A[x]) of a certain degree d. Let f ∈ ker(D) and assume that f / ∈ A. Then x divides f . Since f ∈ ker(D) and ker(D) is factorially closed ([1] Principle 1), we have x ∈ ker(D). Note that D sends homogeneous elements of degree i to zero or to homogeneous elements of degree i + d, therefore D has the form D = ax d E, where a ∈ A, d ∈ N, and E ∈ LND(A) see [1] Principle 7. But since A is rigid, E = 0. Thus D = 0, a contradiction. This means f ∈ A which implies that ker(D) ⊂ A. Finally, since tr.deg k (A) = tr.deg k (ker(D)) and A is algebraically closed in A[x], we get the equality ker(D) = A. Hence ML(A[x]) = A. Computing the ML-Invariant using LND-Filtration Here we illustrate the use of the ∂-filtration in the computation of ML-invariants, for classes of already well-studied examples. Classical examples of semi-rigid k-domains.

and m ≥ 2 .

 2 Let x, y, z be the images of X, Y , Z in B n,P . Define ∂ by ∂(x) = 0, ∂(y) = x n , ∂(z) = ∂P ∂y where ∂P ∂y = my m-1 + (m -1)f m-1 (x)y m-2 + . . . + f 1 (x) We see that ∂ ∈ LND(B n,P ) with ker(∂) = k[x], and y is a local slice for ∂. Moreover, we have deg ∂ (x) = 0, deg ∂ (y) = 1, deg ∂ (z) = m. The plinth ideal is pl(∂) = x n . Up to a change of variable of the form Y → Y -c where c ∈ k, we can always assume that 0 ∈ Spec(B). A consequence of Lemma 2.3, Proposition 2.4, and Proposition 2.5 (see the Proof of Prop. 5.1 for more details) is that 1-The ∂-filtration {F i } i∈N is given by:

Proposition 4 . 1 .

 41 With the notation above we have: (1) ML(B n,P ) = k[x]. Consequently B n,P is semi-rigid. (2) Every D ∈ LND(B n,P ) has the form D = f (x)∂. Proof. (1) By Proposition 2.2 a non-zero D ∈ LND(B) induces a non-zero D ∈ LND (Gr(B)). Let f ∈ ker(D) \ k, then f ∈ ker(D) \ k. There exists i ∈ N such that f ∈ B i . Assume that f / ∈ k[x] = B 0 , then one of the elements y, z must divide f . Which leads to a contradiction as follows: If y divides f , then y ∈ ker(D) because ker(D) is factorially closed in Gr(B) ([1] Principle 1). For the same reason x, z ∈ ker(D) because x n z = y m . So D = 0, a contradiction. If z divides f , then D(z) = 0. So D extends to a locally nilpotent derivation D of the ring B = k(z)[x, y]/ x n z -y m . Since 0 ∈ Spec(B) is a singular point when n ≥ 2 and m ≥ 2 , B is rigid (Lemma 3.3). Therefore, D = 0 which means D = 0, a contradiction. So the only possibility is that f ∈ k[x]. This means that deg ∂ (f ) = 0, and hence that f ∈ k[x]. So ker(D) ⊂ k[x], and finally k[x] = ker(D) because tr.deg k (ker(D)) = 1 and k[x] is algebraically closed in B. So we get ML(B) = k[x].

Proposition 4 . 2 .

 42 With the notation above we have: (1) ML(B n,e,l,Q ) = k[x, z]. Consequently B is semi-rigid. (2) Every D ∈ LND(B n,e,l,Q ) has the form D = f (x, z)∂. Proof. (1) Given a non-zero D ∈ LND(B). By Proposition 2.2 D induces a nonzero D ∈ LND (Gr(B)). Suppose that f ∈ ker(D) \ k, then f ∈ ker(D) \ k. So there exists i ∈ N such that f ∈ B i . Assume that f / ∈ k[x, z] = B 0 , then one of the elements t, y must divides f (see §4.1.2 above). Which leads to a contradiction as follows: If t divides f , then t ∈ ker(D) as ker(D) is factorially closed, and for the same reason y, (x n + z e ) l ∈ ker(D) due to the relation y(x n + z e ) l = t m . So x n + z e ∈ ker(D) which implies that x, z ∈ ker(D) ([1] Lemma 9.3). This means D = 0, a contradiction. Finally, if y divides f , then D(y) = 0. Choose H ∈ ker(D) which is homogeneous and algebraically independent of y, which is possible, since tr.deg k ker(D) = 2 and ker(D) is generated by homogeneous elements. Then by §4.1.2, H has the form H = h(x, z).y l . By algebraic dependence, we may assume H = h(x, z), which is non-constant, and that h(0, 0) = 0. So D extends to a locally nilpotent derivation D of the ring B = k(y, H)[x, z, t]/ h(x, z) -H, y(x n + z e ) l -t m . But B is of transcendence degree one over the field k(y, H) whose spectrum has a singular point at 0. This means that B is rigid (Lemma 3.3). Thus D = 0, which implies D = 0, a contradiction. So the only possibility is that f ∈ k[x, z], and this means deg ∂ (f ) = 0, thus f ∈ k[x, z] and ker(D) ⊂ k[x, z]. Finally, k[x, z] = ker(D) because tr.deg k (ker(D)) = 2. So we get ML(B) = k[x, z]

and e ≥ 1 .

 1 Up to a change of variable of the form Y → Y -c where c ∈ k, we may assume that 0 ∈ Spec(R).Let x, y, z be the images of X, Y , Z in R. Define ∂ by: ∂(x) = 0, ∂(s) = x n+e where s := Q(x, y) -x e z. Considering the relationx n y = P (x, Q(x, y) -x e z), a simple computation leads to ∂(y) = x e ∂P ∂s ,∂(z) = ∂Q ∂y ∂P ∂s -x n , i.e. ∂ := x e ∂P ∂s ∂ y + ( ∂Q ∂y ∂P ∂s -x n )∂ z where ∂P ∂s = ds d-1 + (d -1)f d-1 (x)s d-2 + • • • + f 1 (x), and ∂Q ∂y = my m-1 + (m -1)g m-1 (x)y m-2 + • • •+ g 1 (x). Since ∂(x n y -P (x, Q(x, y)-x e z)) = 0 and ∂ d+1 (y) = 0, ∂ md+1 (z) = 0, ∂ is a well-defined locally nilpotent derivation of R. The kernel of ∂ is equal to k[x]and the element s is a local slice for ∂ by construction. One checks further that the plinth ideal is equal to pl(∂) = x n+e . A direct computation shows that deg ∂ (x) = 0, deg ∂ (y) = d, deg ∂ (z) = md and deg ∂ (s) = 1. Furthermore:

Theorem 5 . 2 .

 52 is generated by x = gr ∂ (x), y = gr ∂ (y), z = gr ∂ (z), s = gr ∂ (s) as an algebra over k with relations x n z = s d and x e z = y m , i.e.Gr(R) = k[X, Y , Z, S]/ X n Z -S d , X e Z -Y m .And we have :R mdi+dj+l = k[x]s l y j z iwhere i ∈ N, j ∈ {0, . . . , m -1}, l ∈ {0, . . . , d -1}. With the above notation the following hold:(1) ML(R) = k[x]. Consequently R is semi-rigid. (2) Every D ∈ LND(R) has form D = f (x)∂, i.e. R is almost rigid. Proof. (1) Given a non-zero D ∈ LND(R). By Proposition 2.2, D respects the ∂filtration and induces a non-zero locally nilpotent derivation D of Gr(R). Suppose that f ∈ ker(D) \ k, then f ∈ ker(D) \ k is an homogenous element of Gr(R). So there exists i ∈ N such that f ∈ R i . Assume that f / ∈ k[x] = R 0 ,then one of the elements s, y, z must divides f by 5.2,2. Which leads to a contradiction as follows : If s divides f , then s ∈ ker(D) as ker(D) is factorially closed, and for the same reason x, y ∈ ker(D) due to the relation x n y = s d . Then by the relation x e z = y m , we must have z ∈ ker(D), which means D = 0, a contradiction. In the same way, we get a contradiction if y divides f . Finally, if z divides f , then D(z) = 0. So D induces in a natural way a locally nilpotent derivation D of the ring R = k(z)[x, y, s]/ x n z -s d , x e z -y m . But since 0 ∈ Spec( R) is a singular point, R is rigid (Lemma 3.3). So D = 0, which implies D = 0, a contradiction. So the only possibility is that f ∈ k[x], and this means deg ∂ (f ) = 0, thus f ∈ k[x] and ker(D) ⊂ k[x]. Finally, k[x] = ker(D) because tr.deg k (ker(D)) = 1 and k[x] is algebraically closed in B. So ML(R) = k[x].

6 .

 6 Further applications of the LND-filtratoin Given a commutative domain B over an algebraically closed field k of characteristic zero, we denote Aut k (B) the group of algebraic k-automorphisms of B. This group acts by conjugation on LND(B). An immediate consequence is that α(ML(B)) = ML(B) for every α ∈ Aut k (B) which yield in particular an induced action of Aut k (B) on ML(B). Let ∂ α = α -1 ∂α be the conjugate of ∂ by a given automorphism α of B, it is straightforward to check that α{ker(∂ α )} = ker(∂) and more generally that deg ∂α (b) = deg ∂ (α(b)) for any b ∈ B. In other words, α respects deg ∂ and deg ∂α (i.e. α sends an element of degree n relative to deg ∂α , to an element of the same degree n relative to deg ∂ . Definition 6.1. We say that an algebraic k-automorphism α preserves the ∂filtration for some ∂ ∈ LND(B) if deg ∂ (α(b)) = deg ∂ (b) for any b ∈ B. Lemma 6.2. Let ∂ ∈ LND(B) and α ∈ Aut k (B). Then ∂ and ∂ α are equivalent, i.e. have the same kernel, if and only if α preserve the ∂-filtration. Proof. Suppose that ∂ and ∂ α are equivalents, then deg ∂ (α(b)) = deg ∂α (b) for every b ∈ B, and by hypothesis ker(∂) = ker(∂ α ), so deg ∂ = deg ∂α . Then we obtain deg ∂ (α(b)) = deg ∂ (b). Thus α preserves the ∂-filtration. Since the other direction is obvious we are done.

Corollary 6 . 3 . 6 . 1 .

 6361 Let B be a semi-rigid k-domain, then every k-automorphism of B preserve the ∂-filtration for every ∂ ∈ LND(B). Proof. A direct consequence of Definition 3.1 and Lemma 6.2. The group of algebraic k-automorphisms of a semi-rigid k-domain. Suppose that B is a semi-rigid k-domain. Then, it has a unique proper filtration {F i } i∈N which is the ∂-filtration corresponding to any non-zero locally nilpotent derivation ∂ of B. Since every algebraic k-automorphism of B preserves this filtration (Corollary 6.3), we obtain an exact sequence 0 → Aut k (B, ML(B)) → Aut k (B) → Aut k (ML(B))

6. 1 . 1 .

 11 Aut k for example 4.1.1.

  1.1 above. Here we briefly indicate how to recover these results using LND-filtrations. So letB n,P = k[X, Y, Z]/ X n Z -P (X, Y ) where P (X, Y ) = Y m + f m-1 (X)Y m-1 + • • • + f 0 (X), f i (X) ∈ k[X], n ≥ 2, and m ≥ 2. Up to change of variable of the form Y by Y -fm-1(X) mwe may assume without loss of generality that f m-1 (X) = 0. Proposition 6.4. Let B n,P be as above. Then every algebraic k-automorphism α of B has the form α(x, y, z) = (λx, µy + x n a(x), µ m λ n z +P (λx, µy + x n a(x)) -µ m P (x, y) λ n x n ) where λ, µ ∈ k * satisfy f m-i (λx) ≡ µ i .f m-i (x) mod x n for all i, and a(x) ∈ k[x].Proof. By Proposition 4.1, (1) and§4.1.1, ML(B) = k[x] and the ∂-filtration {F i } i∈N is given by F im+j = k[x]y im+j + k[x]y im+j-m z + . . . + k[x]y j z i + F im+j-1 , where ∂ = x n .∂ y + ∂P ∂y .∂ z , deg ∂ (x) = 0, deg ∂ (y) = 1, and deg ∂ (z) = m. In particular F 0 = k[x], F 1 = k[x]y + F 0 , and F m = k[x]y m + k[x]z + F m-1 .Now by Corollary 6.3 α preserve deg ∂ , so we must have α(x)∈ F 0 = k[x], α(y) ∈ F 1 = k[x]y + k[x] and α(z) ∈ F m = k[x]y m + k[x].z + F m-1 . Since α is invertible we get α(x) = λx + c, α(y) = µy + b(x), and α(z) = ξz + h(x, y) where λ, µ, ξ ∈ k * , c ∈ k, b ∈ k[x], h(x, y) ∈ k[x, y], and deg y h(x, y) ≤ m. By Proposition 4.1 (2) every D ∈ LND(B) has the form D = f (x)∂. In particular, ∂ α = f (x)∂ for some f (x) ∈ k[x]. Since α∂ α = ∂α we have ∂(α(y)) = α(f (x)∂(y)) = f (α(x))α(x n ) where (∂(y) = x n ). So we get ∂(µy + b(x)) = f (α(x)) (λx + c) n . Since ∂(µy + b(x)) = µx n , x divides (λx + c) n in k[x], and this is possible only if c = 0, so we get α(x) = λx. Applying α to the relation x n z = P (x, y) in B P,n , we get λ n x n α(z) = P (λx, µy + b(x)) = µ m P (x, y) + mµ m-1 y m-1 b(x) + H(x, y) where deg y H ≤ m -2. Since x n divides P = x n z and deg y H ≤ m -2, x n divides mµ m-1 y m-1 b(x) + H(x, y) in k[x, y]. So x n divides b(x), i.e. α(y) = µy + x n a(x).

  1.1 to get relation of the form presented in the following result:Theorem 6.5. Let R denote the ring R = k[X, Y, Z]/ X n Y -P (X, Y m -X e Z) = k[x, y, z] where P (X, S) = S d + f d-2 (X)S d-2 + • • • + f 1 (X)S + f 0 (S), n ≥ 2, d ≥ 2,

  and t is a local slice for ∂. Moreover, we have deg∂ (x) = 0, deg ∂ (y) = m, deg ∂ (z) = 0, and deg ∂ (t) = 1. The plinth ideal is pl(∂) = (X n + Z e ) l. By Lemma 2.3, Prop. 2.4, and Prop. 2.5 we get the following.1-The ∂-filtration {F i } i∈N is given by:

m ≥ 1, and e ∈ N. Then, every algebraic k-automorphism of B has the form α(x, y, z) = (λx, µ d λ n y + F, µ dm λ nm+e .z + ( µ d λ n y + F ) mµ dm λ nm y m + x n+e a(x) λx e )

where: λ, µ ∈ k * verify both µ dm λ nm = µ and f d-i (λx) ≡ µ i f d-i (x) mod x n+e for every i ∈ {2, . . . , d}. s = y m -x e z , and F = P (λx,µs+x n+e a(x))-µ d P (x,s)

Proof. A similar argument as in the proof of Proposition 6.4 leads to α(x) = λx and α(s) = µs + x n a(x) where λ, µ ∈ k * verify f d-i (λx) ≡ µ i f d-i (x) modx n for all i. Now α(x) and α(s) determine

Apply α to x e z = y m -s to get λ e x e α(z) = ( µ h λ n y + F ) m -µs -x n a(x) where F = P (λx,µs+x n a(x))-µ h P (x,s)

Thus x e divides every coefficients of G as a polynomial in y because deg s G ≤ d -1. So x e divides F and µ hm λ nm -µ = 0. This means that x n+e divides f d-i (λx) -µ i f d-i (x) for all i ∈ {2, . . . , d} (see proof of Proposition 6.4), and µ hm λ nm = µ. Finally, by the relation s = y m -x e z, we get

, and we are done.

Isomorphisms.

We are going to use the previous facts about semi-rigid k-domains to give a necessary and sufficient condition for two hypersurfaces of the family 4.1.1 to be isomorphic.

Let Ψ : A -→ B be an algebraic isomorphism, we refer to this by Ψ ∈ Isom k (A, B), between two finitely generated k-domains A = k[y 1 , . . . , y r ], B = k[x 1 , . . . , x r ] where y 1 , . . . , y r and x 1 , . . . , x r are minimal sets of generators. Since Ψ(A) = k[Ψ(y 1 ), . . . , Ψ(y r )] = k[x 1 , . . . , x r ], there exists an automorphism ψ : B -→ B such that for every i ∈ {1, . . . , r} there exists j ∈ {1, . . . , r} such that ψ(x i ) = Ψ(y j ).

Given ∂ ∈ LND(B) and Ψ ∈ Isom k (A, B). For any n ∈ N we have (

and f m-i (λx) ≡ µ i g m-i (x) mod x n for every i ∈ {2, . . . , m} .

In addition, every isomorphism between B 1 and B 2 takes the form

where a(x) ∈ k[x] and λ ∈ k * , µ ∈ k * satisfy f m-i (λx) ≡ µ i g m-i (x) mod x n for all i.

Proof. ). This implies that the only possibility for ψ defined as in 6.2 is ψ(x 2 ) = Ψ(x 1 ), ψ(y 2 ) = Ψ(y 1 ) and ψ(z 2 ) = Ψ(z 1 ). Now by Proposition 6.4

where a(x 2 ) ∈ k[x 2 ] and λ ∈ k * , µ ∈ k * such that g m-i (λx) ≡ µ i g m-i (x) mod x n2 for all i. So we get

). By applying Ψ to relation x n1 1 z 1 = Q 1 (x 1 , y 1 ) in B 1 , we obtain

Since deg

Applying the map gr D to the last equation, we get

On the other hand

)), the last two equations give λ n1 µ m 2 λ n 2 x n1 2 = µ m2 x n2 2 which means that n 1 = n 2 . We could have obtained that n 1 = n 2 in this way: from λ n1 x n1 2 Ψ(z 1 ) = Q 1 (λx 2 , µy 2 + x n2 2 a(x 2 )) we conclude that λ n1 x n1 2 ∂(Ψ(z 1 )) = ∂(y 2 )H(x 2 , y 2 ) where deg y2 H < m 2 and x 2 does not divide H. So x n1 2 divides ∂(y 2 ) = x n2 2 where ∂ is defined as in 4.1.1, which mean that n 1 ≤ n 2 . Since B 1 and B 2 play symmetric roles the equality follows.


Cédric Piette

Youssef Hamadi

Lakhdar Saïs

Sat Presat:

Solver

Lakhdar Sais

preSAT: SAT Solver Description

This document briefly describes preSAT 1.0, a new technique designed to efficiently solve structured CNF formulae. preSAT is based on an original preprocessing technique called revival [START_REF] Piette | Vivifying propositional clausal formulae[END_REF]. This technique aims at producing either sub-clauses or relevant additional clauses for the tested CNF.

To this end, revival heuristically checks whether each clause is minimally (w.r.t. set-theorical inclusion of literals) irredundant. The efficiency of revival relies on its full integration into a modern SAT solver. Hence, its computation benefits from the classical components of modern DPLLs (watched literals, learning scheme, VSIDS-like heuristics, etc.), boosting (sub-)clauses production. However, on some large industrial problems, revival can be time consuming. To avoid losing time in such cases, our pre-processor has a time limit empirically set to 60 seconds. Therefore, even if new sub-clauses could be produced, the CNF is delivered in its current state.

After the application of our revival pre-processor, SatElite [START_REF] Eén | Effective preprocessing in SAT through variable and clause elimination[END_REF] is used to even more simplify the formula before running an exhaustive approach. For the complete solver, Rsat [START_REF] Pipatsrisawat | RSAT 2.0: SAT solver description[END_REF] has been selected. The addition of revival to this solver is expected to improve its behavior on many benchmarks.


Guillaume Cerutti
email: guillaume.cerutti@liris.cnrs.fr

Laure Tougne
email: laure.tougne@liris.cnrs.fr

Didier Coquin
email: didier.coquin@univ-savoie.fr

Antoine Vacavant
email: antoine.vacavant@iut.u-clermont1.fr

Curvature-Scale-based Contour Understanding for Leaf Margin Shape Recognition and Species Identification *

Keywords: curvature-scale space, contour characterization, leaf identification, shape classification

In the frame of a tree species identifying mobile application, designed for a wide scope of users, and with didactic purposes, we developed a method based on the computation of explicit leaf shape descriptors inspired by the criteria used in botany. This paper focuses on the characterization of the leaf contour, the extraction of its properties, and its description using botanical terms. Contour properties are investigated using the Curvature-Scale Space representation, the potential teeth explicitly extracted and described, and the margin classified into a set of inferred shape classes. Results are presented for both margin shape characterization, and leaf classification over nearly 80 tree species.

INTRODUCTION

Plants, trees and herbs that used to constitute the most immediate environment for past generations, seem somehow disconnected from our everyday life, in a world of rampant urbanization and invasive technology. Knowledge of the uses and properties of numerous species got away, kept only by a handful of botanists. Even identifying a simple plant has merely become a case for the specialists.

But the blossoming of mobile technology curiously offers the opportunity of spreading back this knowledge into everyone's pocket. Providing an intuitive and flexible way to recognize species, to teach anyone who feels the need how to look at a plant, is now a possibility. Attempts in this direction have come to light with great success, being with user-based (TreeId, Fleurs en Poche) or automatic recognition (LeafSnap 1 ) on white background images.

Leaves are a choice target for such application, present almost all year long, easy to photograph, and with well studied geometrical specificities that make the identification, if not trivial, possible. Our main objective is to build a system for leaf shape analysis of photographs in a natural environment, relying on high-level geometric criteria inspired by those used by botanists to classify a leaf into a list of species.

In this paper, we focus on the characterization of the leaf margin shape, introducing a dedicated description of the shape contour. Section 2 presents works connected to this matter. The processing performed on the contour is described in Section 3 and the descriptor we use detailed in Section 4. Section 5 expounds its interest for both margin shape classification and species identification, and conclusions are drawn in Section 6.

RELATED WORKS

Leaf Identification

Leaf image retrieval and plant identification have been a growing topic of interest in the past few years. Some authors [START_REF] Belhumeur | Searching the world's herbaria: A system for visual identication of plant species[END_REF]) also aim at conceiving a mobile guide, achieving great performance on plain background images by the combination of established shape descriptors (Inner-Distance Shape Context) and classification methods. Some works tackle the challenge of segmentation over natural background [START_REF] Teng | Leaf segmentation, its 3d position estimation and leaf classification from a few images with very close viewpoints[END_REF][START_REF] Wang | Classification of plant leaf images with complicated background[END_REF], but most elude this obstacle, working on plain background images, where sensitivity to noisy shapes is less of an issue given the general accuracy of the obtained contours.

Many methods rely on statistical features such as moments [START_REF] Wang | Classification of plant leaf images with complicated background[END_REF], histogram of gradients or local interest points [START_REF] Goëau | Participation of inria & pl@ntnet to imageclef 2011 plant images classification task[END_REF] or generic contout descriptors such as the Curvature-Scale Space [START_REF] Mokhtarian | Matching shapes with self-intersections: Application to leaf classification[END_REF]. Such descriptors were not designed to take into account the nature of the object, but fit quite well with its specificities. A commonly used geometrical descriptor for leaf image retrieval is the Centroid-Contour Distance (CCD) curve [START_REF] Wang | Leaf image retrieval with shape features[END_REF][START_REF] Teng | Leaf segmentation, its 3d position estimation and leaf classification from a few images with very close viewpoints[END_REF] though it can be applied to any type of object.

On the other hand, some morphological features explicitly computed on the shape of the object to model its natural properties have also been used [START_REF] Du | Leaf shape based plant species recognition[END_REF][START_REF] Goëau | Participation of inria & pl@ntnet to imageclef 2011 plant images classification task[END_REF]. Even more dedicated methods have been designed, basing their recognition on an explicit representation of the leaf contour and of its teeth [START_REF] Im | A hierarchical method of recognizing plant species by leaf shapes[END_REF][START_REF] Caballero | Plant species identification using leaf image retrieval[END_REF] but suitable only for image retrieval and applied to a small number of species.

Curvature for Contour Description

Since the leaf margin shape is a very discriminant feature for identification, characterizing the contour of the leaf is a crucial step. The CCD curve provides an interesting view, but lacks precision, as the curve for a leaf with small teeth will be very close to a smooth one. To discriminate such contours, the use of curvature is very advantageous.

A rich representation of the contour is the Curvature-Scale Space (CSS), that has already been used in the context of shape recognition [START_REF] Mokhtarian | A theory of multiscale, curvature-based shape representation for planar curves[END_REF]) and even leaf image retrieval [START_REF] Mokhtarian | Matching shapes with self-intersections: Application to leaf classification[END_REF][START_REF] Caballero | Plant species identification using leaf image retrieval[END_REF]. It piles up curvature measures at each point of the contour over successive smoothing scales, summing up the information into a map where concavities and convexities clearly appear.

Curvature has also been used to detect dominant points on the contour, and provide a compact description of a contour by its curvature optima. This is a well studied problem [START_REF] Teh | On the detection of dominant points on digital curves[END_REF] in which the introduction of the curvature-scale transform has proved to be beneficial [START_REF] Pei | The detection of dominant points on digital curves by scale-space filtering[END_REF]. The detection and characterization of salient features on a leaf contour is a problem that can be addressed with a similar perspective.

CONTOUR INTERPRETATION

Our starting point is a segmented leaf, from either a plain or natural background, along with its preliminary global shape estimation [START_REF] Cerutti | Guiding active contours for tree leaf segmentation and identification[END_REF]. This polygonal model conveys interesting information on the leaf's geometry, and provides notably the number of appearing lobes n L and an estimation of its main axis (possibly more than one in the case of a palmately lobed leaf). Our frame of work here comprises only simple and palmately lobed leaves (nearly 75% of all European tree specie) species with compound leaves being left aside. Since our goal is to represent the morphology of the margin, knowing where to look is important to select the accurate features and, for instance, not consider the apex as a simple tooth.

Leaf Contour Partition

The contour needs then to be divided into areas corresponding to the apex, to the base, to the potential lobe tips, and finally to the rest of the margin, so that the most salient features do not absorb the rest of the information. Relying on the polygonal leaf model is here useful to solve what would otherwise be a much more complicated task. Supposing that the axes of the polygonal model are accurate, we can use them to mark off contour points that are in one of these areas of interest. To achieve the labelling shown in Figure 1, we define sets of vertices as the intersection of the contour with a fixed angular sector, built around the corresponding axis using the model points, issuing from the opposite point (base for the apices, and apex for the base) and with a minimal distance relatively to this point : A for the apical area (red), B for the basal area (blue), L for the lobe tips (brown), and the actual margin area M , divided into for lM the left margin area and rM for the left margin area (green).

This partition first makes possible the accurate location of the actual base point B and the apex point  of the leaf, as the most salient features in their respective area B or A, a crucial information to estimate the local shape of the leaf around them, a determining feature for botanists. And secondly, outside of these areas, we can study the properties of potential teeth, lobes, sinuses and other salient features in M , and characterize the leaf margin shape, and only it.

Curvature-Scale Space Transform

As a matter of fact, the salient features on the contour appear very clearly on the Curvature-Scale Space transform of the contour, as shown in Figure 3(b). The CSS is a very powerful description but is too informative to be used as a descriptor and to build class models by averaging several of them. As we wish to locate and characterize precisely curvaturedefined elements on the contour, it was a more judicious choice to look, not at zero-curvature points as the original method would do [START_REF] Mokhtarian | A theory of multiscale, curvature-based shape representation for planar curves[END_REF], but on the contrary at the maxima and minima of curvature. These salient points are the ones that visually stand out in the CSS image and can be intuitively be matched to existing structures on the leaf contour, reason why we want to detect them explicitly.

Detecting Teeth and Pits

To locate these points, we actually want to detect dominant points on the leaf contour and to find the scale of the concave or convex part they correspond to. The method we use is largely inspired of existing works [START_REF] Teh | On the detection of dominant points on digital curves[END_REF][START_REF] Pei | The detection of dominant points on digital curves by scale-space filtering[END_REF] where the process of detection is performed at each scale level. Starting with S = 4 (lower scale elements being arguably indiscernible from noise) the set of dominant points at each scale D(S) is initialized with all the contour points and the process is then the following: 1. Extract points for which the curvature value is a local optimum in a neighbourhood of size S 2. Suppress points the curvature intensity of which is below a threshold k min 3. Suppress points that can not be traced to a dominant point at the previous scale (if S > 4)

4. Keep only the median point of potential remaining groups of size ≤ S

The result we obtain is a map of the located dominant points at each scale, as presented in Figure 3(c). This representation reveals the teeth and pits of the contour in the form of chains of dominant points.

LEAF MARGIN DESCRIPTION

Once the salient features are detected on the contour, it is necessary to interpret this dense information in order to make the discriminant characteristics of the margin appear. To know what to look for, we relied on the distinctions made by botanists to discriminate the different species.

Leaf Margin Shapes in Botany

To describe the shape of the leaf margin, botanists use a terminology that refers both to the properties of teeth taken separately and to their repartition over the margin. Some of these terms are shown in Figure 2. For instance a "doubly serrate" leaf implies two levels of teeth with different sizes and frequencies, with bigger teeth divided into smaller sub-teeth. The words themselves are vague enough so that leaves with teeth that look rather different may fall inside the same term. [START_REF] Coste | Flore descriptive et illustrée de la France de la Corse et des contrées limitrophes[END_REF] The margin shape constitutes however a very discriminant criterion for species identification that generally presents less variability than the global shape, with the exception of some pathological species. Our descriptor will have to capture the differences regarding size, sharpness, orientation, repartition and variability of the teeth implied in the botanical terms, but also to benefit from the use of numerical values to be more precise and discriminate leaves of different aspect that would be called the same.

Margin Interpretation

For the sake of interpretation, we want to use the representation of the contour by dominant points to retrieve the properties of every located structure on the contour. Each chain that appears on the dominant points map corresponds indeed to a convex or a concave part, and its actual size, as a human eye would interpret it, is the scale until which it persists, that is to say the scale of the chain's end point. We scan the dominant points starting from the highest scale to keep only these terminal points. When a dominant point is found at scale S, all the dominant points of the same curvature sign are simply suppressed at lower scales, in a neighbourhood of size S. This way, we ensure that a single structure is not counted twice, and small structures which are included in larger ones are merged into one.

Each point kept after this selection step corresponds to a concave or convex structure of scale S. To complete this size information, we estimate the actual curvature K of a dominant point of scale S belonging to D(S), as the average curvature of all the dominant points belonging to the same chain. This computation is done while suppressing the points at lower scales. Finally the final set of dominant points is a semantically rich interpretation of the leaf contour, where the base and apex points B and  are precisely located, and where teeth are detected and characterized independently in terms of position on the contour (u), size (S) and curvature (K) : each point p in then represented by a vector (u(p); S(p); K(p)). This representation is displayed in Figure 4.

To improve robustness, and avoid that errors in segmentation or unwanted leaf artefacts (cracks, holes, spots) are taken into account, we want to keep only points that can be found on both sides of the leaf. Here again, the contour partition is very useful to know on which side lies a given point, and where to look on the contour to know if a similar one exists on the opposite side. The matching is performed by computing a distance term to all the points on the opposite side of same curvature sign, that takes into account their scale, curvature, relative position on the axis B Â , and relative distance to this same axis. This method is somewhat risky but ensures that eccentric structures as in Figure 5 do not bias the understanding of the margin.

Describing the Margin

Even if this explicit representation is full of information and could be used as such to compare two leaves, it is still too heavy if we want to average several of them for classification purposes. It is necessary to sum it up into a condensed descriptor to capture the main properties of the margin, and allow a semantic interpretation of its specificities.

A first characterization consists in measuring how much of the leaf margin is convex, concave or neither of the two. Since the detected structures, given their definition, account for a number of vertices equal to their scale, we just have to sum the scales of dominant points and normalize them, to compute 3 parameters w + , w -and w 0 , corresponding to the percentage of the set M of margin vertices that belong respectively to convex structures, concave structures, and no structure.

To describe teeth properties in a condensed way, we compute averages and standard deviations for the properties we extracted on each dominant point. That gives 8 parameters computed on either concave (-) or convex (+) points, respectively S+ , σ S+ , S-, σ S-for scale, and K+ , σ K+ , K-, σ K-for curvature. These values are computed by weighting the considered parameter of each point by the point's scale, so that each vertex on the margin contributes at the same level.

Even if computing standard deviations provide a measure for the variability of the properties, such aggregating representation constitute a loss of spatial information. To keep a trace of the repartition of teeth along the margin, we computed the relative distances d ↑ (p) and d ↓ (p) of each point p, respectively to the next and previous points of opposite curvature on the same side M (p), when they exist.

These distances are once again averaged over points of the same curvature sign to produce 4 additional parameters d ↑ + , d ↓ + for convex points, and d ↑ -, d ↓ -for concave points, that account for the spatial repartition of teeth on the margin. What we finally use to describe the margin is a vector P of 11 parameters :

• S+ + σ S+ • S+ -σ S+ • K+ + σ K+ • K+ -σ K+ • S-+ σ S- • S--σ S- • K-+ σ K- • K--σ K- • w 0 • d ↑ + /d ↓ + • d ↑ -/d ↓ -
Taken together, these parameters constitute a very condensed yet efficient representation of what is important on a leaf contour, summing up the properties a botanist would investigate to characterize the margin. Most of the computational time comes from the CSS transform, but can be greatly reduced by computing only a limited number of scales and interpolating the curvature value for intermediate scales, leading to an execution time below the second on a computer processor, and of nearly 3 seconds on an iPhone 4 processor.

CLASSIFICATION & RESULTS

To assess the relevance of our margin descriptors, we chose to classify leaves in botanical terms. However, it is impossible to have a database of leaves labelled with their exact shapes because of the intra-species variability and the subjectivity and vagueness of those words. The only way to learn automatically these shapes was to train a semi-supervised classifier using the possible shapes for each species and let it infer the concept represented by the classes.

Learning Margin Shapes

As a matter of fact, trying to evaluate the concepts behind the botanical words without exactly labelled examples is a very challenging issue. Those words maybe used to cover different shapes that may share some properties but not all of them. The method we used to learn these concepts tries to consider both the theoretical knowledge on leaf shapes and the uncertainty on the correspondence of one given leaf to one particular class.

Each considered species s was labelled with one or more possible margin shapes M(s), according to a reference botanical description [START_REF] Coste | Flore descriptive et illustrée de la France de la Corse et des contrées limitrophes[END_REF]. We retained 12 terms that were applicable to all the species we considered, namely :

• Entire

• Denticulate • Undulate • Crenate • Serrate • Dentate • Doubly Serrate • Sinuate • Spiny • Angular • Lobate
• Pinnatifid Then we used a semi-supervised Fuzzy C Means (FCM) clustering algorithm to learn the 12 centroids representing the shapes. Each individual i in the database of species s(i) is represented by a descriptor vector P i = (P k,i ) k=1..K and is assigned a membership value (µ m,i ) m=1..12 representing its degree of belonging to each of the clusters. The supervising here consists of a constraint that the membership of an individual to clusters corresponding to shapes outside of the possible shapes M(s(i)) of its species must remain zero: ∀i, ∀m = 1..12, m / ∈ M(s(i)) =⇒ µ m,i = 0. The initial membership values are set to be the same for each possible shape of the species, and the centroids are then computed following the regular FCM procedure, with a parameter β set to 1.8.

Each class is finally represented by its resulting centroid C m and by the estimated standard deviation vector Σ m , computed using the memberships of each individual. A new leaf, represented by its margin parameter vector P = (P k ) is then classified by computing its normalized Euclidean distance to all the class centroids, and assigning it to the closest.

Species Identification

The database used to test our algorithms is a subset of the Pl@ntLeaves [START_REF] Goëau | The clef 2011 plant images classification task[END_REF] database, keeping only 5668 leaf images (out of 8422) on white, plain or natural backgrounds of 80 species (out of 126) with non-compound leaves.

Parameters extracted on the images, outside of the margin descriptors described here [CS], are parameters from the polygonal leaf model [MP] [START_REF] Cerutti | Guiding active contours for tree leaf segmentation and identification[END_REF] accounting for the global shape of the leaf, and parameters of Bezier curves based basal and apical shape models [B/A] estimated around the located points B and Â.

The data formed by all the parameters from all the images is first centered and normalized. Assuming that each parameter simply follows a Gaussian distribution, we compute class centroids and standard deviations with examples from the training dataset. For each species s, and for each possible number of lobes n L up to 3 we build a class Φ s,n L = (µ s,n L ,k , σ s,n L ,k ) if at least 10% of all the species examples have this value.

To classify a new example, we will simply have to compare its descriptors with the centroids of the classes sharing the same number of lobes n L . For each one of the 3 sets of parameters, we compute a Euclidean distance to the surface of the ellipsoid defined by means and standard deviations :

D(P,Φ s,n L ) = P -µ S ,n L 2 max 1 - 1 P -µ S ,n L M , 0 P -µ S ,n L M = ∑ k (P k -µ s,n L ,k ) 2 σ s,n L ,k 2
Each one of these terms is then weighted differently after having learned the classes, dividing it by the average distance of the correct class over the training base, which weights it accordingly to its significance. The final distance we use for classification is simply the sum of these weighted terms, and the classes are then ordered accordingly to their distance, producing an ranked list of species.

Experimental Results

To evaluate the classification into botanical shapes, we performed a cross validation on the training base, learning the classes by FCM on two thirds of the database, and classifying the remaining third. A classification is assessed to be correct if the returned shape is one of the possible shapes taken by the leaf species. Results show a correct classification in 65% of cases, climbing up to 76% if we take into account the two first ranked classes.

We tried to refine this evaluation by building a confusion matrix for the shapes. It is not an easy task since the examples are not labelled by their actual shape, but by their species and thus their possible shapes. We decided to put a weight of 1 per example in the matrix, placing it in the diagonal cell if the classification was considered as correct, and splitting it among the theoretical possible classes in the recognized class column if not. The percentages are then obtained by dividing those weights by the total weight of each theoretical class. The matrix we obtain is displayed in Table 1 and provides a good light on what our descriptors are good at discriminating or not. It appears clearly that margins with larger structures are easier to differentiate than smaller ones. It is difficult to capture the differences between for instance Serrate and Dentate leaves especially since the small scale we are looking at makes errors more common. Dentate is visibly a very variable class, making it more easily detected given the classification distance we use. Very small teeth of Denticulate leaves seem also hard to represent, such leaves being regularly seen as without teeth or with regular ones.

Concerning the species classification, results were evaluated following the same cross validation process.

We computed classification rates for the different types of images in the Pl@ntLeaves Database (Scan, Pseudoscan and Photograph) and measured the presence of the true species among the top k answers (k going from 1 to 10) returned by the classification algorithm.

Figure 6 presents the results obtained with the global, base and apex shape descriptors only [MP+B/A] and with the addition of the margin descriptors [MP+B/A+CS], underlining the interest of considering the contour in a very specific way, with an average recognition score of 53%, and a presence of the correct species in the 5 first answers of 85%. The great improvement induced by the use The enhancement is less important on photographs given the hardness of the task of retrieving the exact leaf contour, which obviously deteriorates the relevance of the contour description.

These scores may be compared to the results of the 2011 ImageCLEF Plant Identification task [START_REF] Goëau | The clef 2011 plant images classification task[END_REF] concerning a very similar database, and where the best participants reached an average score of 45%.

CONCLUSION

The method presented in this article constitutes an interesting step towards an explicative system of leaf classification for an independent mobile application. Being able to place high-level semantic concepts over the values extracted from an image gives the user a feedback that may prove of great usefulness for both interactive and educational purposes.

A first implementation of the recognition process on mobile devices is engaged with very satisfactory results, but not yet with the nearly 150 native European tree species we aim at recognizing. With the number of potential classes increasing, it will become a necessity to reduce the scope of the search, by including geographical information linked to the GPS system present in every smartphone. Knowing in advance which species are likely to be found in the geographical area where the user stands may be a decisive step towards a truly reliable identification.

However, what we have now is a good base structure for a new tree identification application, designed to be functional in a natural environment, and destined to anyone with interest in plants but without the otherwise compulsory botanical background.

Figure 1 :

 1 Figure 1: Polygonal model and labelling of contour parts corresponding to leaf areas

Figure 2 :

 2 Figure 2: Examples of leaf margin shapes : Entire, Denticulate, Dentate, Sinuate, Lobate. Images taken from[START_REF] Coste | Flore descriptive et illustrée de la France de la Corse et des contrées limitrophes[END_REF]

  Traced dominant points over scale (c) and their curvature, obtained from the curvature-scale space transform (b) of a leaf contour (a)

  Various leaf contours with detected base, apex, teeth and pits ; apex area in red, base area in dark blue ; convexities in orange, concavities in blue, brightness representing curvature intensity, extent representing scale.

Figure 5 :

 5 Figure 5: Suppression of points that can not be matched on a deteriorated leaf ; only connected points are kept

  Classification rates on the Pl@ntLeaves Database on scan (a) pseudoscan (b) and photograph (c) images of curvature-based descriptors is here clearly visible.

Table 1 :

 1 Confusion Matrix for Leaf Margin Classification

* This work has been supported by the French National Agency for Research with the reference ANR-10-CORD-005 (REVES project).

1 http://leafsnap.com : developed by researchers from Columbia University, the University of Maryland, and the Smithsonian Institution (Belhumeur et al., 2008)