Jean Michel

T A Springer

COMMUTATION OF SHINTANI DESCENT AND JORDAN DECOMPOSITION

Let G F be a finite group of Lie type, where G is a reductive group defined over Fq and F is a Frobenius root. Lusztig's Jordan decomposition parametrises the irreducible characters in a rational series E(G F , (s)

Deshpande's approach to Shintani descent

We follow [START_REF] Deshpande | Shintani descent for algebraic groups and almost characters of unipotent groups[END_REF]. Let H be an algebraic group over an algebraically closed field k; we identify H to its points H(k) over k. Let γ 1 , γ 2 be two commuting bijective isogenies on H. We define the following subset of (H γ 1 ) × (H γ 2 ):

R γ1,γ2 = {(xγ 1 , yγ 2 ) | x, y ∈ H, [xγ 1 , yγ 2 ] = 1}
where [u, v] is the commutator uvu

-1 v -1 . A matrix a b c d ∈ GL 2 (Z) defines a map R γ1,γ2   a b c d   ------→ R γ a 1 γ c 2 ,γ b 1 γ d 2 : (xγ 1 , yγ 2 ) → ((xγ 1 ) a (yγ 2 ) c , (xγ 1 ) b (yγ 2 ) d )
There is an action of H on R γ1,γ2 by simultaneous conjugation: (xγ 1 , yγ 2 ) ad g

--→

(gxγ 1 g -1 , gyγ 2 g -1 ), which commutes with the maps a b c d , and we denote by R γ1,γ2 / ∼ H the space of orbits under this action. Assume now that H is connected and γ 1 is a Frobenius root (an isogeny such that some finite power is a Frobenius morphism). Then, by the Lang-Steinberg theorem any xγ 1 ∈ Hγ 1 is H-conjugate to γ 1 , and we can take as representatives of the H-orbits pairs of the form (γ 1 , yγ 2 ); on these pairs there is only an action of the fixator of γ 1 , that is H γ1 . Further, the condition [γ 1 , yγ 2 ] = 1 is equivalent to y ∈ H γ1 (since γ 1 and γ 2 commute). We can thus interpret R γ1,γ2 as the H γ1conjugacy classes on the coset H γ1 γ 2 , which we denote by H γ1 γ 2 / ∼ H γ1 . If a, c and γ 2 are such that γ a 1 γ c 2 is still a Frobenius root, we can thus interpret the map given by a b c d as a map

H γ1 γ 2 / ∼ H γ1 → H γ a 1 γ c 2 γ b 1 γ d 2 / ∼ H γ a 1 γ c
2 , a "generalised Shintani descent". We are interested here in the case of R F,Id where F is a Frobenius root. The matrix 1 0 1 1 defines a map, that we call the Shintani twisting and will just denote by Sh : R F,Id → R F,Id : (xF, y) → (xF y, y). With the identification above of R F,Id / ∼ H with the pairs (F, y) which identifies it with H F / ∼ H F , if we write y = λ. F λ -1 using the Lang-Steinberg theorem, Sh maps (F, y) to (F y, y) = (F λ. F λ -1 , λ. F λ -1 ) which is conjugate by F λ -1 to (F, F λ -1 λ), thus we recover the usual definition of the Shintani twisting Sh as being induced by the correspondence

λ F λ -1 → F λ -1 λ.
The advantage of Deshpande's approach is that the map Sh : R F,Id → R F,Id still makes sense when H is disconnected; this time the interpretation of R F,Id / ∼ H is different: the H-orbits on HF are parametrised by H 1 (F, H/H 0 ). If σ ∈ H is a representative of such an H-orbit, the H-orbits of pairs (σF, y) are in bijection with H σF / ∼ H σF , so we see that we must consider all rational forms of H corresponding to the various representatives σF ∈ H 1 (F, H/H 0 ) together, and Sh will act on the disjoint union of the conjugacy classes of each of these forms. Let σF be such a representative, let H 1 be a σF -stable coset of H 0 in H, let σ ∈ H σF 1 and let us compute the image by Sh of a commuting pair (σF, σ y) where y ∈ H 0 (thus y ∈ (H 0 ) σF ). Let us write using the Lang-Steinberg theorem y = λ. σ σF λ -1 . Then Sh maps (σF, σ y) to (σF σ y, σ y) = (σ σF λ. σ σF λ -1 , σ λ. σ σF λ -1 ) (using [σF, σ ] = 1) which is conjugate by σ σF λ -1 to (σ σF, σ . σF λ -1 λ). Thus Proposition 1. Sh is induced on σ (H 0 ) σF , where σ and σ are two representatives of H/H 0 such that σF and σ commute, by the correspondence between the element σ λ. σ σF λ -1 of σ (H 0 ) σF and the element σ . σF λ -1 λ of σ (H 0 ) σ σF .

Assume now that H/H 0 is commutative and that we can lift all elements of H/H 0 to commuting representatives, such that F -stable elements lift to F -stable representatives; then we can lift all pairs (σF, σ ) as in Proposition 1 which commute in H/H 0 to commuting pairs, thus we can see Sh as a linear map on the space C(H, F ) := ⊕ σ∈H 1 (F,H/H 0 ) C(H σF ), the direct sum of the spaces of class functions on the various rational forms H σF . Definition 2. Let H be a algebraic group with a Frobenius root F , then we say that H satisfies condition (*) if we can lift elements of H/H 0 to commuting elements of H, such that F -stable elements of H/H 0 lift to F -stable elements.

Beware that Sh on class functions is defined by Sh(f )(x) = f (Sh(x)) thus it maps class functions on σ (H 0 ) σ σF to class functions on σ (H 0 ) σF .

Note finally that when H 0 is trivial and F acts trivially on H/H 0 , the computations of this section recover the well-known action of GL 2 (Z) on the Drinfeld double of the finite group H/H 0 = H. See, for example [2, 8.4.2].

Conjectures

Definition 3. We extend the definition of Deligne-Lusztig characters to a disconnected reductive group H with a Frobenius root F by R H T (s) := Ind H F H 0F R H 0 T (s) where T runs over F -stable maximal tori of H and s over T * F * . We call unipotent characters the irreducible components of the R H T (1) and we denote by E(H F , 1) the set of unipotent characters of H F .

From now on, G will be a connected reductive group with a Frobenius root F and s an F * -stable semi-simple element of G * , the group dual to G. We denote by E(G F , (s) G * F * ) the G * F * -Lusztig series associated with s; this series consists of the irreducible components of the R G T * (s) where T * runs over F -stable maximal tori of C G * (s). We denote by E(G F , (s)) the geometric Lusztig series associated with s, that is the union of the series E(G F , (s ) G * F * ) where (s ) G * F * runs over the G * F * -classes in the geometric class of s.

Let ε G := (-1) F -rank G . Lusztig's Jordan decomposition of characters in a reductive group with a not necessarily connected centre is given by the following theorem (see for example [START_REF] Digne | Representations of finite groups of Lie type[END_REF]Theorem 11.5.1]).

Theorem 4. Let G be a connected reductive group with Frobenius root F and (G * , F * ) be dual to G; for any semi-simple element s ∈ G * F * , there is a bijection from E(G F , (s) G * F * ) to E(C G * (s) F * , 1). This bijection may be chosen such that, extended by linearity to virtual characters, it sends

ε G R G T * (s) to ε C G * (s) 0 R C G * (s) T *
(1) for any F * -stable maximal torus T * of C G * (s).

Conjecture 5. Let G be a connected reductive group with Frobenius root F . Then Sh, viewed as a linear operator on C(G F ), preserves the subspace spanned by E(G F , (s)) for each geometric class (s). Proposition 6. Assume that F is the Frobenius morphism corresponding to an F q -structure on G. Then Conjecture 5 holds when the characteristic is almost good for G in the sense of [7, 1.12] and ZG is connected or when G is of type A and either q is large or F acts trivially on ZG/(ZG) 0 .

Proof. The case of type A when F acts trivially on ZG/(ZG) 0 results from [START_REF] Bonnafé | Sur les caractères des groupes réductifs finis à centre non connexe: applications aux groupes spéciaux linéaires et unitaires[END_REF]Théorème 5.5.4]. Let us prove the other cases. In [9, Section 3.2] it is shown that the characteristic functions of character sheaves are eigenvectors of Sh; then in [START_REF] Shoji | Character sheaves and almost characters of reductive groups[END_REF]Theorem 5.7] and [10, Theorem 3.2 and Theorem 4.1] (resp. [START_REF] Bonnafé | Sur les caractères des groupes réductifs finis à centre non connexe: applications aux groupes spéciaux linéaires et unitaires[END_REF]Corollaire 24.11]) it is shown that when ZG is connected and the characteristic is almost good (resp. in type A with q large) the characteristic functions of character sheaves coincide up to scalars with "almost characters". Since for each s, the space CE(G F , (s)) is spanned by a subset of almost characters, this gives the result.

It is probable that the above proof applies to more reductive groups (see [START_REF] Shoji | Lusztig's conjecture for finite special linear groups[END_REF], [START_REF] Waldspurger | Une conjecture de Lusztig pour les groupes classiques[END_REF], and also [START_REF] Bonnafé | Sur les caractères des groupes réductifs finis à centre non connexe: applications aux groupes spéciaux linéaires et unitaires[END_REF]Introduction]), but it is difficult to find appropriate statements in the literature.

Assuming conjecture 5, a choice of a Jordan decomposition as specified by Theorem 4 will map the operator Sh on CE(G F , (s)) to a linear operator on the space

C(C G * (s) F * , F * , 1) := ⊕ σ∈H 1 (F * ,C G * (s)/C 0 G * (s)) CE(C G * (s) σF , 1). Conjecture 7. Let s ∈ G * F * . Then C G * (s) satisfies (*) and Sh on C(C G * (s), F * ) preserves the subspace C(C G * (s) F * , F * , 1)
, and the choice of a Jordan decomposition in Theorem 4 may be refined so that it maps Sh on CE(G F , (s)) to Sh on C(C G * (s) F * , F * , 1).

3. The case of a group of type A n-1 when n is prime.

Proposition 8. Conjectures 5 and 7 hold for any reductive group of type A n-1 , with n prime, if they hold for SL n .

Proof. We start with two lemmas.

Lemma 9. Let G be a connected reductive group with a Frobenius root F . Let G be a closed connected F -stable subgroup of G with same derived group. Let F * be a Frobenius root dual to F and let

s ∈ G * F * be such that C G * (s) F * = C 0 G * (s) F * . Then the characters in E(G F , (s) G * F * ) are the restrictions from GF to G F of the characters in E( GF , (s) G * F * ) where s ∈ G * F * lifts s ∈ G * F * .
Proof. By definition the characters in E( GF , (s) G * F * ) are those which occur in some R G T (s), where T is a maximal torus such that T * s, and by for instance [5, 11.3.10] we have Res

GF G F R G T (s) = R G T∩G (s).
It is thus sufficient for proving the lemma to prove that for any χ ∈ E( GF , (s) G * F * ) its restriction χ to G F is irreducible.

By, for instance [5, 11.3.9] we have χ, χ

G F = |{θ ∈ Irr( GF /G F ) | χθ = χ}|.
It is thus sufficient to prove that for any non-trivial such θ we have χθ = χ. But a non-trivial θ corresponds to a non-trivial z ∈ Z( G * ) F * with trivial image in G * , and since χθ ∈ E( GF , (sz) G * F * ) it is sufficient to prove that s and sz are not G * F *conjugate. But, indeed if g (sz) = s then ḡs = s where ḡ is the image of

g in G * , thus ḡ ∈ C G * (s) F * = C 0 G * (s) F * , whence g ∈ C G * (s) (a contradiction) since the preimage of C 0 G * (s) is C 0 G * (s) (by for example [5, 3.5.1 (i)]). Lemma 10. Consider a quotient 1 → Z → G 1 π -→ G → 1,
where Z is a connected subgroup of G 1 . Assume that G and G 1 have Frobenius roots both denoted by F and that π commutes with F ; then π is surjective from the conjugacy classes of G F 1 to that of G F , and commutes with Sh.

Proof. The group Z is F -stable since π commutes with F . Let x ∈ G F . Since Z is connected, by the Lang-Steinberg theorem π -1 (x) F is non-empty whence the surjectivity of π on elements, hence on conjugacy classes. If y ∈ π -1 (x) F the image by π of Sh(y) is Sh(x), whence the commutation of Sh with π.

Let now G be an arbitrary reductive group of type A n-1 . Since n is prime, the only semi-simple connected reductive groups of type A n-1 are SL n and PGL n ; thus any connected reductive group G of type A n-1 is the almost direct product of the derived G of G, equal to SL n or PGL n , by a torus S.

In the case G = PGL n the almost direct product is direct since PGL n has a trivial centre. If T is an F -stable maximal torus of G, then it has a decomposition

T 1 × S where T 1 = T ∩ G is F -stable since G is F -stable.
It is possible to find an F -stable complement S of T 1 (see for example the proof of [6, 2.2]) and then G has an F -stable product decomposition G × S . Since Sh is trivial on a torus the conjectures are reduced to the case of G = PGL n .

The same argument reduces the case of a direct product G = G × S where G = SL n to the case of SL n . The other possibility when G = SL n is an almost direct product SL n ×S amalgamated by Z SL n ; this is isomorphic to a product of the form GL n ×S ; in such a group all centralisers are connected, as well as in the dual group (isomorphic to G) thus both conjectures are trivial since Sh is the identity (by for example [4, IV, 1.1]).

Finally, in PGL n the action of Sh is trivial by Lemma 10 applied to the quotient GL n π -→ PGL n , and in the dual SL n semisimple elements have connected centralisers which are Levi subgroups of SL n ; considering the embedding of these centralisers in the corresponding Levi of GL n , on which Sh is trivial since it is isomorphic to a product of GL ni we get that Sh is trivial on the unipotent characters of these centralisers by Lemma 9.

We have thus shown that we only need to consider SL n . Up to isomorphism there are two possible F q -structures on SL n (only one if n = 2) thus F will be one of the Frobenius endomorphisms F + or F -where SL F+ n = SL n (F q ) and SL F- n = SU n (F q ). When we want to consider both cases simultaneously but keep track whether F = F + or F = F -, we will denote the Frobenius by F ε with ε ∈ {-1, 1}, where we always take ε = 1 if n = 2. We will use the dual group PGL n , the inclusion SL n ⊂ GL n and the quotient GL n → PGL n . Since (GL n , F ) is its own dual, we will write F (instead of F * ) for the Frobenius map on the dual of GL n and on PGL n . We choose for F + the standard Frobenius which raises all matrix entries to the q-th power, and choose for F -the map given by x → F + ( t (x -1 )). This choice is such that on the torus of diagonal matrices T * of G * , F -acts by raising all the eigenvalues to the power -q, and acts trivially on W G * (T * ).The torus T * is split for F + and of type w 0 (the longest element of the Weyl group) with respect to a quasi-split torus for F -.

Proposition 11. For the group SL n , n prime, with Frobenius F = F ε conjecture 5 holds. Further, conjecture 7 holds if it holds when q ≡ ε (mod n) for the series E(SL F n , (s)) with s ∈ PGL F n geometrically conjugate to diag(1, ζ, ζ 2 , . . . , ζ n-1 ) where ζ ∈ F q is a non-trivial n-th root of 1.

Proof. Lemma 9 applied with G = SL n and G = GL n shows that conjectures 5 and 7 hold when C PGLn (s) F = C 0 PGLn (s) F . Indeed, in this case, since Sh is trivial in GL n and commutes with the restriction to SL n by Lemma 10, Lemma 9 shows that Sh is trivial on E(SL F n , (s)); on the other hand, since C 0 PGLn (s) is the quotient with central kernel of a product of GL ni , the unipotent characters of C PGLn (s) F = C 0 PGLn (s) F can be lifted to this product (see [START_REF] Digne | Representations of finite groups of Lie type[END_REF]Proposition 11.3.8]). Since Sh is trivial in GL ni and commutes which such a quotient with connected central kernel by Lemma 10, it is trivial on the unipotent characters of C PGLn (s) F .

We have thus reduced the study of conjectures 5 and 7 to the case of semi-simple elements s ∈ PGL n with C PGLn (s) F = C 0 PGLn (s) F . By [5, Lemma 11.2.1(iii)], since n is prime a semi-simple element s ∈ PGL n has a non-connected centraliser if and only if |C PGLn (s)/C 0 PGLn (s)| = n. Since this group of components is a subquotient of the Weyl group S n , it has order n if and only if it is a subgroup of S n generated by an n-cycle. An easy computation shows that such an s is as in the statement of Proposition 11. Now the centraliser of s is the semidirect product of T * with the cyclic group generated by the n-cycle c = (1, . . . , n). Assume that the geometric class of s has an F -stable representative s in a torus of type w ∈ S n with respect to T * (or equivalently that wF s = s). Then C PGLn (s ) F C PGLn (s) wF hence is equal to C 0 PGLn (s ) F unless w commutes with c, that is w = c i for some i. Since c centralises s we get that s is F -stable, which means for F = F ε that n divides q -ε, in particular Conjecture 7 holds when q ≡ ε (mod n); we recall that we always take ε = 1 when n = 2.

Finally, conjecture 5 holds in any case, since Sh preserves all geometric series except possibly that of s and preserves orthogonality of characters, thus preserves also the series E(SL F n , (s)). Henceforth we assume that n is prime and divides q -ε, and study conjecture 7 for the particular s of Proposition 11.

Assumption 12. We choose ζ, a primitive n-th root of unity in F q . We choose an isomorphism F q × (Q/Z) p which maps ζ to 1/n and a group embedding

Q/Z → C × which maps 1/n to ζ C := exp(2iπ/n).
We denote by T the diagonal torus of SL n and by T the diagonal torus of GL n ; we choose the dual torus T * to be the diagonal torus of PGL n . We let s ∈ T * be the image of diag(1, ζ, ζ 2 , . . . , ζ n-1 ) ∈ T.

Sh on C PGLn (s).

We first study Sh on C(C PGLn (s) F , F, 1). We have C PGLn (s) = T * c where c is the permutation matrix representing the cycle (1, 2, . . . , n) ∈ S n , which acts on T * by sending diag(t 1 , . . . , t n ) to diag(t n , t 1 , . . . , t n-1 ). On T * the Frobenius F ε acts by t → t εq , and acts trivially on W G * (T * ). Note that C G * (s) satisfies condition (*) since c is F -stable. Since C PGLn (s)/C 0 PGLn (s) = c , and F acts trivially on c, we have H 1 (F, C PGLn (s)/C 0 PGLn (s)) = c and the geometric class of s splits into n rational classes parametrised by the powers of c. A representative of the class parametrised by c j is x s where x is such that x -1 F x = c j . This representative lies in a maximal torus T * c j = x T * of type c j with respect to T * . Choosing the PGL n -conjugacy by x -1 to identify (T * c j , F ) with (T * , c j F ), we identify back the representative of the class parametrised by c j with the element s in T * c j F . We have

C(C PGLn (s) F , F, 1) = ⊕ n-1 j=0 CE(T * c j F c , 1).
Since T * is a torus, the unipotent characters of T * c j F c are the n extensions of the trivial character of T * c j F . We parametrise these by Z SL n ×Z/nZ in the following way: if

z 0 = diag(ζ, . . . , ζ), we call θ z i 0 ,k the character of T * c k F c
which is trivial on T * c k F and equal to ζ i C on c. This allows us to define another basis of C(C PGLn (s) F , F, 1), the "Mellin transforms", defined for j, k ∈ Z/nZ by θ j,k := z∈Z SLn ŝj (z)θ z,k , where ŝj is the character of T c j F corresponding to the element s ∈ T * c j F through duality. The point is that it is more convenient to compute the action of Sh on the Mellin transforms:

Proposition 13. We have Sh θ j,i = θ j,i+j unless n = 2 (thus ε = 1) and q ≡ -1 (mod 4). In this last case we have Sh θ j,i = θ j,i+j-1

Proof.

Lemma 14. With the conventions of Assumption 12, when n is odd, we have

ŝj (z i 0 ) = ζ ij C ; when n = 2 (thus ε = 1) we have ŝj (z 0 ) = (-1) (q-1)/2 if j = 0 (-1) (q+1)/2 if j = 1 .
Proof. The correspondence between T * c j F and Irr(T c j F ) comes from the diagram of exact sequences X(T)

c j F -1 ----→ X(T) Res --→ Irr(T c j F ) → 1   ∼ Y (T * ) c j F -1 ----→ Y (T * ) π -→ T * c j F → 1
where π maps y ∈ Y (T * ) to N F m /c j F (y(1/(q m -1))) for any m such that (c j F ) m = F m (see [START_REF] Digne | Representations of finite groups of Lie type[END_REF]Proposition 11.1.7]); here y(1/(q m -1)) is defined using the choices of Assumption 12 and N F m /c j F is the norm map on T * given by x → x. c j F x . . . (c j F ) m-1 x.

When j = 0 we can take m = 2 in the above diagram. We have s = N F 2 /F (y(1/(q 2 -1))) = y(1/(εq -1)) where y is the cocharacter mapping λ ∈ F q × to the image in

T * of diag(1, λ (εq-1)
/n , λ 2(εq-1)/n , . . . , λ (n-1)(εq-1)/n ) ∈ T. The element y interpreted as a character of

T F maps z 0 = diag(ζ, . . . , ζ) ∈ Z SL n to ζ εq-1 n n(n-1) 2 C = ζ (n-1)(εq-1)/2 C
which is equal to 1 when n is odd-thus in this case ŝ0 is trivial on Z SL n . If n = 2 we have ε = 1 and we get ŝ0 (diag(-1, -1)) = (-1) (q-1)/2 .

When j = 0, we can take m = 2n. We want to find y ∈ Y (T * ) such that s = N F 2n /c j F (y(1/(q 2n -1))). Since (c j F ) n = F n we have

N F 2n /c j F (x) = N F n /c j F (x)F n (N F n /c j F (x)).
Let y 0 be a cocharacter mapping λ ∈ F × q 2n to the image in T * of diag(λ, 1, . . . , 1). We have (c j F ) k (λ, 1, . . . , 1) = (1, . . . , 1, λ (εq) k , 1, . . .) where λ (εq) k is at the place indexed by kj + 1, hence at the place indexed by i in N F n /c j F (y 0 (λ)) the exponent of λ is such that i ≡ kj + 1 (mod n), which since λ ∈ F × q n is equivalent to k = (i -1)j where jj ≡ 1 (mod n). Hence N F n /c j F (y 0 (λ)) is the image in T * of diag(λ, λ (εq) j , λ (εq) 2j , . . . , λ (εq) (n-1)j ) and N F 2n /c j F (y 0 (λ)) is the image in T * of diag(λ 1+(εq) n , λ (1+(εq) n )(εq) j , λ (1+(εq) n )(εq) 2j , . . . , λ (1+(εq) n )(εq) (n-1)j ). If we set µ = λ 1+(εq) n , the element diag(1, µ (εq) j -1 , µ (εq) 2j -1 , . . . , µ (εq) (n-1)j -1 ) has same image in T * . For µ εq-1 = ζ j we have µ (εq) kj -1 = ζ j(1+εq+...+(εq) kj -1 ) = ζ jkj = ζ k , the second equality since q ≡ ε (mod n). Hence N F 2n /c j F (y 0 ( j n(εq-1)((εq) n +1) )) = s, thus we can take y = j(q 2n -1)

n(εq-1)((εq) n +1) y 0 = j((εq) n -1)
n(εq-1) y 0 (note that (εq) n -1 n(εq-1) is an integer). As a character of T c j F it maps the element

z 0 = diag(ζ, . . . , ζ) ∈ Z SL n to ζ j((εq) n -1) n(εq-1)

C

. We now use:

Lemma 15. If n is odd, k > 0 and n k divides εq -1, we have (εq) n -1 n(εq-1) ≡ 1 (mod n k ).
Proof. Let us write εq = 1 + an k . We have (εq) n -1

εq-1 = 1 + εq + • • • + (εq) n-1 ≡ n+a n(n-1) 2 n k (mod n k+1 ).
Since n is odd it divides n(n-1)/2, so that (εq) n -1 εq-1 ≡ n (mod n k+1 ) which, dividing by n, gives the result. This lemma applied with k = 1 shows that ŝj maps

z i 0 to ζ ij C when n is odd. If n = 2 (thus ε = 1) we get ŝ1 (diag(-1, -1)) = (-1) (q+1)/2 .
Proposition 16. We have Sh χ j,i = χ j,i+j unless n = 2 (thus ε = 1) and q ≡ -1 (mod 4). In this last case we have Sh χ j,i = χ j,i+j-1 .

Proof. We note first that χ z,j (g) is independent of z if C SLn (g) is connected. Indeed, χ z,j and χ z ,j are conjugate by an element x ∈ GL F n since they are two components of the restriction of an irreducible character of GL F n . We have thus χ z ,j (g) = χ z,j ( x g). We can multiply x by a central element to obtain an element y ∈ SL n and, since y g = x g ∈ SL F n , we have y -1 . F y ∈ C SLn (g). If this centraliser is connected, using the Lang-Steinberg theorem we can multiply y by an element of C SLn (g) to get a rational element y , whence χ z ,j (g) = χ z,j ( y g) = χ z,j (g). For such an element g we thus have χ j,i (g) = 0 if j = 0.

Since C SLn (g) is connected we have Sh(g) = g thus Sh χ j,i (g) = χ j,i (g), in particular Sh χ 0,i = χ 0,i and if j = 0 we have (Sh χ j,i )(g) = χ j,i+j (g) = 0, whence (Sh χ j,i )(g) = χ j,i+j (g) for all j.

It remains to consider the conjugacy classes of SL n which have a non-connected centraliser.

Lemma 17. When n is prime the only elements of SL n which have a non-connected centraliser are the zu with z ∈ Z SL n and u regular unipotent.

Proof. Let su be the Jordan decomposition of an element of SL n with s semi-simple and u unipotent. We have C SLn (su) = C CSL n (s) (u). The group C SLn (s) is a Levi subgroup of SL n , that is the subgroup of elements of determinant 1 in a product k i=1 GL ni . Thus C SLn (su) is the subgroup of elements with determinant 1 in a product k i=1 H i where H i is the centraliser of u in GL ni , which is connected. We claim that if k > 1 the group C SLn (su) is connected. Indeed, since n is prime, if k > 1 the n i are coprime so that there exist integers a i satisfying k i=1 a i n i = -1. Then the map (h 1 , . . . , h k ) → (h 1 λ a1 , . . . , h k λ a k , λ) where λ = det(h

1 h 2 . . . h k ) is an isomorphism from H 1 × • • • × H k to C SLn (su) × F q .
Hence this last group is connected, thus its projection C SLn (su) is also connected.

It remains to look at the centralisers of elements zu with u unipotent and z ∈ ZSL n , that is the centralisers of unipotent elements. By [4, IV, Proposition 4.1], since n is prime, C SLn (u) is connected unless u is regular and when u is regular we have C SLn (u) = R u (C SLn (u)).ZSL n which is not connected.

Thus to prove the proposition we have only to consider the classes of the elements zu with u regular unipotent and z ∈ Z SL n . Fix a rational regular unipotent element u 1 . The conjugacy classes of rational regular unipotent elements are parametrised by H

1 (F, C SLn (u 1 )/C 0 SLn (u 1 )) = H 1 (F, ZSL n ) = Z SL n (the last equality since q ≡ ε (mod n)): a representative u z of the class parametrised by the F -class of z ∈ ZSL n is t u 1 where t ∈ T satisfies t -1 F t = z.
χ z,k (u z ) = z ∈H 1 (F,ZSLn) σ z z -1 (-1) F -semi-simple rank(SLn) D(χ z,k ), Γ z SL F n ,
where D is the Curtis-Alvis duality. If k = 0 and F = F + or if F = F -we claim that (-1) F -semi-simple rank(SLn) D(χ z,k ) = χ z,k : indeed, in both cases the character R GLn Tc k (s k ) is cuspidal since the torus Tc k is not contained in a proper rational Levi subgroup. Indeed when F = F + and k = 0 (resp. F = F -), the type c k (resp. the type w 0 c k ) of T c k with respect to a quasi-split torus is not contained in a standard parabolic subgroup of S n . Thus χ z,k is cuspidal as a component of the restriction to SL F n of R GLn Tc k (s k ), whence our claim since the duality on cuspidal characters is the multiplication by (-1) F -semi-simple rank(SLn) (take L = SL n in [5, 7.2.9]). If k = 0 and F = F + , the characters χ z,0 are the irreducible components of

R SLn T (ŝ 0 ) = Ind SL F n B F ŝ0
, where B is the Borel subgroup of upper triangular matrices and ŝ0 has been lifted to B F . The endomorphism algebra of this induced character is isomorphic to the group algebra of Z/nZ, hence the components of Ind SL F n B F ŝ0 are parametrised by the characters of Z/nZ and by [START_REF] Mcgovern | Multiplicities of principal series representations of finite groups with split (B, N )-pairs[END_REF]Theorem B] the effect of the duality is to multiply the parameters by the sign character of the endomorphism algebra which is trivial if n is odd and is -

1 if n = 2.
If n is odd or if n = 2 and k = 0, we thus have χ z,k (u z ) = σ z z -1 . If n = 2 and k = 0 we have χ z,0 (u z ) = -σ z z where {z, z } = {1, diag(-1, -1)}.

We consider first the case n odd. By Lemma 14 we have ŝk ( If n = 2 we have z 0 = diag(-1, -1). We have χ j,k (zu z ) = ŝk (z)(ŝ j (1)χ z 0 0 ,k (u z )+ ŝj (z 0 )χ z0,k (u z )). We get χ j,0 (zu z ) = ŝ0 (z)(-σ z0z -ŝj (z 0 )σ z ) and χ j,1 (zu z ) = ŝ1 (z)(σ z + ŝj (z 0 )σ z0z ). If ŝj is the identity character then χ j,0 and χ j,1 are invariant by Sh since Sh(u z ) = u z and Sh(z 0 u z ) = z 0 u z0z . If ŝj is not trivial then, χ j,0 (zu z ) and χ j,1 (zu z ) are equal if z = 1 and opposite if z = 1, thus, using again Sh(u z ) = u z and Sh(z 0 u z ) = z 0 u z0z we see that χ j,0 and χ j,1 are exchanged by Sh. By Lemma 14, if q ≡ 1 (mod 4) the character ŝ0 is trivial and we get the same result as in the odd case. If q ≡ -1 (mod 4), the character ŝ1 is trivial and Sh exchanges χ 0,0 and χ 0,1 and fixes χ 1,0 and χ 1,1 , which is the announced result.

z i 0 ) = ζ ki C .
We can now state: Proposition 18. For s = diag(1, ζ, . . . , ζ n-1 ), the bijection J : χ j,i → θ j,i from CE(SL F n , (s)) to CE(C PGLn (s) F , F, 1) restricts on characters to a refinement of the Jordan decomposition which satisfies Conjecture 7.

Proof. Propositions 13 and 16 give the commutation of J with Sh. It remains to show that J(R SLn T c j (s j )) = R

Id =

θ 0,j for n odd or q ≡ 1 (mod 4) θ 1,j for n = 2, q ≡ -1 (mod 4) . On the other hand for n odd or q ≡ 1 (mod 4), we have χ 0,j = z ŝ0 (z)χ z,j = z χ z,j since in that case ŝ0 is the trivial character. For n = 2, q ≡ -1 (mod 4), we have χ 1,j = z ŝ1 (z)χ z,j = z χ z,j since in that case ŝ1 is the trivial character. By definition of χ z,j we have z χ z,j = R SLn T c j (s j ), whence the proposition.

  By [4, IV,Proposition 1.2] Sh maps the SL F n -class of zu z to that of zu zz . Now χ z,k being a component of the restriction of the irreducible character R GLn Tc k (s k ) has central character equal to ŝk , independently of z, whence χ z,k (z u z ) = ŝk (z )χ z,k (u z ). By [5, Corollary 12.3.13], there is a family of Gauss sums σ z indexed by ZSL n such that

0 . 0 . 0 .C σ z z -i 0 =

 0000 Thus the values of the Mellin transforms areχ j,k (z u z ) = i ŝj (z i 0 )χ z i 0 ,k (z u z ) = i ŝj (z i 0 )ŝ k (z )σ z z -i 0 = ŝk (z ) i ζ ij C σ z z -i Let us put z = z l 0 ; we get χ j,k (z l 0 u z ) = ζ lk C i ζ ij C σ z z -i Now as recalled above we have Sh(z u z ) = z u z z , whence (Sh χ j,k )(z l 0 u z ) = χ j,k (z l 0 u z l 0 z ) = ζ lk C i ζ ij C σ z z l-i Taking i-l as new variable inthe summation we get (Sh χ j,k )(z l 0 u z ) = ζ lk χ j,j+k (z l 0 u z ), which gives the proposition for n odd.

  . As we have noticed after the proof of Proposition 13 we have R T c j c T c j

We thank Cédric Bonnafé for having suggested improvements to a previous version of this text.

We now compute the Mellin transforms θ j,k . If n is odd, we have by Lemma 14

We see that θ j,i is a function supported by the coset T c i F .c -j ⊂ T c i F c and is constant equal to n on this coset. By proposition 1, Sh maps a constant function on this coset to the constant function on T c i+j F .c -j with same value, hence Sh θ j,i = θ j,i+j .

If n = 2 we have

Thus θ j,i is supported by T c i F .c j if q ≡ 1 (mod 4) and by T c i F .c 1-j if q ≡ -1 (mod 4) and is constant equal to 2 on its support. We get the same result as in the odd case for the action of Sh when q ≡ 1 (mod 4). If q ≡ -1 (mod 4), since Sh maps functions on T c i c 1-j to functions on T c i+j-1 c 1-j we get Sh θ j,i = θ j,i+j-1 .

Proposition 13 shows that Sh preserves the space C(C PGLn (s) F , F, 1). Note that the computation made in the proof of Lemma 14 and Definition 3 show that R

For computing the other side of conjecture 7, that is Sh on SL F n , we first parametrise the characters in ∪ j E(SL F n , (s j ) PGL F n ), where s j ∈ (T * c j ) F is an F -stable representative of the rational class that we parametrised above by s ∈ T * c j F . We use the following notation: for z ∈ Z SL n we denote by Γ z the Gelfand-Graev character indexed by z as in [START_REF] Digne | Representations of finite groups of Lie type[END_REF]Definition 12.3.3]; that is Γ z = Ind SL F n U F ψ z where U is the unipotent radical of the Borel subgroup consisting of upper triangular matrices and ψ z is a regular character of U F indexed by z. This labelling depends on the choice of a regular character ψ 1 : we have ψ z = t ψ 1 where t ∈ T satisfies t -1 F t = z.

Let sj ∈ ( T * c j ) F be a lifting of s j . By [START_REF] Digne | Representations of finite groups of Lie type[END_REF]Proposition 11.3.10] R SLn Tc j ∩SLn (s j ) is the restriction of R GLn Tc j (s j ), hence the series E(SL F n , (s j ) PGL F n ) is the set of irreducible components of the restrictions of the elements of E(GL F n , (s j )). Moreover since C GLn (s j ) is a torus, the character R GLn Tc j (s j ) is irreducible, hence is the only character in E(GL F n , (s j )); thus this character must be a component of the (unique) Gelfand-Graev character of GL F n by [START_REF] Digne | Representations of finite groups of Lie type[END_REF]Theorem 12.4.12]. The restriction of this character to SL F n is equal to z∈Z SLn χ z,j where χ z,j is the unique irreducible component of the Gelfand-Graev character Γ z in the series E(SL F n , (s j )) (see [START_REF] Digne | Representations of finite groups of Lie type[END_REF]Corollary 12.4.10]). Thus we have E(SL F n , (s j )) = {χ z,j | z ∈ Z SL n }. It is again more convenient to compute Sh on the basis formed by the Mellin transforms χ j,k := z∈Z SLn ŝj (z)χ z,k .


Yeow Wei Choong

Lisa Di Jorio
email: dijorio@lirmm.fr

Anne Laurent
email: laurent@lirmm.fr

Dominique Laurent
email: dlaurent@u-cergy.fr

Maguelonne Teisseire
email: teisseire@teledetection.fr

CBGP: Classification Based on Gradual Patterns

Keywords: data mining, classification, gradual rules

In this paper, we address the issue of mining gradual classification rules. In general, gradual patterns refer to regularities such as "The older a person, the higher his salary". Such patterns are extensively and successfully used in command-based systems, especially in fuzzy command applications. However, in such applications, gradual patterns are supposed to be known and/or provided by an expert, which is not always realistic in practice.

In this work, we aim at mining from a given training dataset such gradual patterns for the generation of gradual classification rules. Gradual classification rules thus refer to rules where the antecedent is a gradual pattern and the conclusion is a class value.

I. INTRODUCTION

Classification is a key problem in many real world applications that aim at determining the class of objects knowing their values over a given set of attributes. For instance, considering gene analysis applications, determining whether a tumor is malignant or not based on observed gene expressions is a key issue.

In this framework, many methods have been defined, e.g., decision trees, naive bayes, neural networks, SVMs, (see [START_REF] Han | Data Mining Concepts and Techniques[END_REF], [START_REF] Mitchell | Machine Learning[END_REF]), some of these methods being more explicative/understandable for the user than other ones. In particular, decision tree-based approaches, such as C4.5 ([18]), provide the user with a set of rules (so-called classification rules) that explicitly show why an example has been labeled with a particular class.

In this paper, we address the problem of computing classification rules when traditional approaches fail, because considering attribute values as such is not appropriate. In such a case, we look for trends shown by sets of values over the same attribute, such as the higher/lower the value of attribute A, the higher/lower the value of attribute B.

For example, in gene analysis, it could be the case that the values of gene expressions do not allow for any prediction regarding the malignancy of a tumor, whereas sets of such values contain trends like the more gene G1 is expressed, the less gene G2 is expressed, when the tumor being considered is malignant. Therefore, this type of gradual rule can be used to determine whether a given new tumor is malingnant.

For this purpose, we consider gradual patterns to describe trends in a given training dataset, thus leading to a novel and appealing rule-based classification method, extending existing methods such as CBA (Classification Based on Association rules) [START_REF] Liu | Integrating Classification and Association Rule Mining[END_REF] or SPaC (Sequential Patterns for Classification) [START_REF] Jaillet | Sequential Patterns for Text Categorization[END_REF].

The paper is organized as follows: Section II introduces a running example considered throughout the paper to illustrate our approach. In Section III, we review previous work on gradual rules and rule-based classification methods. In Section IV, we introduce the basic definitions related to gradual frequent patterns and gradual classification rules. In Section V, we report on the experiments we have conducted to assess our method, and Section VI concludes the paper and provides further research directions.

II. RUNNING EXAMPLE

To illustrate our approach, we consider the (toy) example described in Table I, referring to fruit quality measurement as a mean to determine their provenance.

In this case, we assume that fruits, with properties size (S), weight (W ) and sugar rate (SR), are delivered in box containers that have to be dispatched according to their provenance. Assuming that this provenance is ignored, we try and predict it, knowing that two provenances (i.e., two classes) are possible, namely N orth and South.

As argued next, it turns that in Table I, the size-, weightand sugar rate values of fruits, considered one by one, do not allow for the prediction of the provenance, meaning that traditional classification approaches fail to predict fruit provenance based on their size, weight and sugar rate.

On the other hand, it will be seen shortly that, considering gradual patterns (i.e., tendencies of the size-, weight-and sugar rate values) allows to characterize the provenance.

As mentioned above, traditional classification methods do not apply in this example as no generality can be extracted tuple by tuple. Indeed, under Weka environment:

• Running C4.5 gives: J48 pruned tree ------: S (9.0/4.0) • Similarly, running a Naive Bayes method, a multilayer perceptron method and the KNN method gives a prediction accuracy of, respectively, 33%, 22.22% and 33.3333%. Thus, clearly, whatever the method, attribute values as such can not determine fruit provenance, due to the fact that all fruits have almost the same size, weight and sugar rate (implying that standard classification methods cannot avoid over-fitting).

However, we argue that the way these attributes co-variate can help determining fruit provenance. Indeed, it can be seen from Table I that in general:

• For fruits from North, the higher the size, the lower the sugar rate (referring to the first four tuples); but no correlation involving the weight can be found. • For fruits from South, the higher the size, the higher the weight, the higher the sugar rate (referring to the last five rows except tuple t 2 ). In our apporach, we formalize these tendencies through the following two gradual classification rules:

• {(S, ≥), (SR, ≤)} ⇒ N orth, and • {(S, ≥), (W, ≥), (SR, ≥)} ⇒ South Consider now a new set of fruits, known to have the same provenance, but which has to be determined. The measurements of these fruits, reported in Table II, show that the pattern the higher the size, the lower the sugar rate holds.

As this gradual pattern holds in Table I for northern fruits and not for southern fruits, the fruits described in Table II are considered as northern fruits, which can not be found using any traditional classification approach, as shown above.

III. RELATED WORK

A. Gradual Rules

Gradual patterns and gradual rules have been studied for many years in the framework of control, command and recommendation. More recently, data mining algorithms have been studied in order to automatically mine such patterns [START_REF] Berzal | An Alternative Approach to Discover Gradual Dependencies[END_REF], [START_REF] Jorio | Fast Extraction of Gradual Association Rules: A heuristic based method[END_REF], [START_REF] Jorio | Mining Frequent Gradual Itemsets from Large Databases[END_REF], [START_REF] Fiot | Gradual Trends in Fuzzy Sequential Patterns[END_REF], [START_REF] Hüllermeier | Association Rules for Expressing Gradual Dependencies[END_REF].

The approach in [START_REF] Hüllermeier | Association Rules for Expressing Gradual Dependencies[END_REF] uses statistical analysis and linear regression in order to extract gradual rules. In [START_REF] Berzal | An Alternative Approach to Discover Gradual Dependencies[END_REF], the authors formalize four kinds of gradual rules in the form The more/less X is in A, then the more/less Y is in B, and propose an Apriori-based algorithm to extract such rules. However, frequency is computed from pairs of objects, increasing the complexity of the algorithm. Despite a good theoretical study, the algorithm is limited to the extraction of gradual rules of length 3.

The approach in [START_REF] Fiot | Gradual Trends in Fuzzy Sequential Patterns[END_REF] is the first attempt to formalize gradual sequential patterns. This extension of itemsets allows for the combination of gradual temporality ("the more quickly") and gradual list of itemsets. The extraction is done by the algorithm GRaSP, based on generalized sequential patterns [START_REF] Masseglia | Pre-processing Time Constraints for Efficiently Mining Generalized Sequential Patterns[END_REF] to extract gradual temporal correlations.

In [START_REF] Jorio | Fast Extraction of Gradual Association Rules: A heuristic based method[END_REF] and [START_REF] Jorio | Mining Frequent Gradual Itemsets from Large Databases[END_REF], two methods to mine gradual patterns are proposed. The difference between these approaches lies in the computation of the support: whereas, in [START_REF] Jorio | Fast Extraction of Gradual Association Rules: A heuristic based method[END_REF], a heuristic is used and an approximate support value is computed, in [START_REF] Jorio | Mining Frequent Gradual Itemsets from Large Databases[END_REF], the correct support value is computed. It is important to note in this respect that, in the current paper, the method of [START_REF] Jorio | Mining Frequent Gradual Itemsets from Large Databases[END_REF] is used for the computation of frequent gradual patterns. We refer to Section IV for the corresponding formal definitions.

B. Classification Based on Rules

Classification has been extensively studied [START_REF] Mitchell | Machine Learning[END_REF]. In this paper, we focus on classification based on rules as this is the method we aim at extending.

In [START_REF] Liu | Integrating Classification and Association Rule Mining[END_REF] the authors propose a text categorization method based on association rules, called CBA. The method consists of two steps: (i) rule generation (CBA-RG), based on the well-known Apriori algorithm, and (ii) building the classifier (CBA-CB), based on generated rules.

In the first step, each assignment of a text to a category is represented by a pair ρ = condset, C i , called a ruleitem, and where condset is a set of items and C i is a class label. Each ruleitem ρ should be thought of as a rule condset → C i , whose support and confidence are defined as follows:

supp(ρ) = #texts from Ci matching condset #texts in D conf (ρ) = #texts in Ci matching condset #texts in D matching condset
Ruleitems whose support is above a given threshold are said to be frequent, and the set of class association rules (CARs) consists of all frequent ruleitems whose confidence is greater than a minimum confidence threshold. Once all CARs are generated, they are totally ordered according to the following precedence relation: If r i and r j are two CARs, r i ≺ r j (precedes) if:

• either conf (r i ) > conf (r j ) • or conf (r i ) = conf (r j ) and supp(r i ) > supp(r j ) • or conf (r i ) = conf (r j )
and supp(r i ) = supp(r j ) and r i has been generated before r j . Let R be the set of CARs and D the training data. The basic idea of the algorithm is to choose a set of high precedence rules in R to cover D. The categorizer is represented by an ordered list of rules r i ∈ R, leading to pairs such as (r 1 , r 2 , ..., r k ), C i , where C i is a target category.

Each rule is then tested on D. If a rule does not improve the accuracy of the classifier, this rule and the following ones are discarded from the list.

Once the categorizer has been built, each ordered rule r i ∈ R is tested on every new text to classify. As soon as the condset part of a rule is supported by the text, the text is then assigned to the target class of the rule.

Many other research has been done using association rules for classification. In [START_REF] Janssens | Adapting the CBA-Algorithm by Means of Intensity of Implication[END_REF], the authors replace the confidence by the intensity implication. In [START_REF] Liu | Classification Using Association Rules: Weaknesses and Enhancements[END_REF], the authors integrate the CBA method with other methods such as decision trees, Naive Bayes, RIPPER, etc. to increase the classification score. In [START_REF] Baralis | Majority Classification by Means of Association Rules[END_REF], the authors investigate a method for association rule classification called L 3 . Contrary to CBA-CB which takes only one rule into account, the authors propose to determine the category of a text by considering several rules, using a majority voting.

In [START_REF] Ali | Partial Classification Using Association Rules[END_REF], association rules are used for partial classification. Partial classification means that the classifier does not cover all cases. In particular, this work is interesting when dealing with missing values.

CAEP [START_REF] Dong | CAEP: Classification by Aggregating emerging patterns[END_REF], LB, ADT [START_REF] Wang | Growing Decision Trees on Support-Less Association Rules[END_REF], CMAR [START_REF] Li | CMAR: Accurate and Efficient Classification Based on Multiple Class-Association Rules[END_REF] are other existing classification systems using association rules. LB and CAEP are based on rule aggregation rather than rule selection. ARC-CB [START_REF] Antonie | Text Document Categorization by Term Association[END_REF] proposes a solution for multi-classification (i.e., a text is associated to one or more classes).

To end the section, we emphasize that none of these classification approaches have considered using gradual patterns, as we do in this paper.

IV. CBGP: CLASSIFICATION BASED ON GRADUAL PATTERNS In this section, we detail our proposal for Classification Based on Gradual Patterns. We recall that our approach is composed of two parts: first we compute the gradual patterns representing each class value (thus constructing the gradual pattern-based classifier), and then we define how to determine the class values of new examples. We recall that the notions of gradual itemsets and their support are borrowed from [START_REF] Jorio | Mining Frequent Gradual Itemsets from Large Databases[END_REF]; these definitions are stated next.

A. Basic Definitions

In this work, we assume that we are given a database DB that consists of a single table whose tuples are defined on the attribute set I. In this context, gradual patterns are defined to be subsets of I whose elements are associated with an ordering, meant to take into account increasing or decreasing variations.

In the definitions given below, using standard notation from the relational database model, for each tuple t in DB and each attribute I in I, t[I] denotes the value of t over attribute I.

Definition 1: (Gradual Itemset) Given a table DB over the attribute set I, a gradual item is a pair (I, θ) where I is an attribute in I and θ a comparison operator in {≥, ≤}.

A gradual itemset g = {(I 1 , θ 1 ), ..., (I k , θ k )} is a set of gradual items of cardinality greater than or equal to 2.

We point out that gradual itemsets are assumed to be sets of cardinality greater than or equal to 2, because sorting tuples according to one attribute is always possible, which is not the case when considering more than one attribute.

The support of a gradual itemset in a database DB is defined as follows.

Definition 2: (Support of a Gradual Itemset) Let DB be a database and g = {(I 1 , θ 1 ), ..., (I k , θ k )} a gradual itemset. The cardinality of g in DB, denoted by λ(g, DB), is the length of the longest list l = t 1 , . . . , t n of tuples in DB such that, for every p = 1, . . . , n-1 and every j = 1, . . . , k, the comparison t p [I j ] θ j t p+1 [I j ] holds.

The support of g in DB, denoted by supp(g, DB), is the ratio of λ(g, DB) over the cardinality of DB, which we denote by |DB|. That is, supp(q, DB) = λ(g,DB)

|DB| . In order to compute λ(g, DB), [START_REF] Jorio | Mining Frequent Gradual Itemsets from Large Databases[END_REF] proposes to consider the graph where nodes are the tuples from DB and where there exists a vertex between two nodes if the corresponding tuples can be ordered according to g.

Example 1: Referring back to our running example, since we aim at building rules to determine fruit provenance, the table DB to be considered for the definition of gradual itemsets is the projection of Table I over the attributes S, W and SR. In other words, we consider that I = {S, W, SR}.

Figure 1 shows the ordering of the tuples of DB, according to the gradual itemset g = {(S, ≥), (SR, ≤)}, whose intuitive meaning is the higher the size, the lower the sugar rate. As in this graph, the length of the longest totally ordered list of tuples is 5, and as DB contains 9 tuples, we have supp(g, DB) = 5 9 . The two step processing works as follows: During the first step, frequent gradual itemsets are computed for each class. Then, during the second step, for every class, the corresponding gradual rules are defined based on the frequent gradual itemsets previously computed. The quality of these gradual rules is assessed, based on the notion of discriminance of a given rule that measures to which extent a gradual rule is representative of the class it has been extracted from.

More formally, let C be a set of class values, and I be a set of attributes, we aim at building a set of gradual classification rules in the form g ⇒ c where g is a gradual itemset and c ∈ C.

The training database, denoted by DB T , is defined over the attribute set I ∪ {C}. Intuitively, every tuple in DB T is characterized by its values over attributes in I and its class value, stored as an attribute value. Table I shows an example of such a training database, in which the set C of class values is {N orth, South}, seen as the domain of the attribute showing the provenance.

The table DB T is partitioned according to the values in C, and for every c in C, we denote by DB T (c) the set of all restrictions over I of all tuples in DB T where the class value is c. That is, DB

T (c) = {t[I] | t ∈ DB T and t[C] = c}.
Given an itemset g over I, the support of g in class c is the support of g in DB T (c), that is, according to Definition 2, supp(g, DB T (c)), which we denote by supp(g, c) for the sake of simplification.

Given a minimum support threshold minsup, for every class value in C, all gradual itemsets g such that supp(g, c) ≥ minsup are computed using the method of [START_REF] Jorio | Mining Frequent Gradual Itemsets from Large Databases[END_REF]. These gradual patterns are then considered in order to define whether they are discriminant for the class. The discriminance measure is defined as follows.

Definition 3: (Discriminance of a Gradual Itemset) Let g be a gradual itemset and c be a class value in C. Denoting by Γ(g) the set of all class values γ such that supp(g, γ) ≥ minsup, the discriminance of g regarding c is defined as:

disc(g, c) = supp(g, c) γ∈Γ(g)
supp(g, γ) .

Given a support threshold minsup and a discriminance threshold mindisc, the problem of building a set of gradual classification rules amounts to computing, for every class value c in C, the set of all rules of the form g ⇒ c such that supp(g, c) ≥ minsup and disc(g, c) ≥ mindisc.

In what follows, we denote by G c the set of all gradual itemsets g such that supp(g, c) ≥ minsup and disc(g, c) ≥ mindisc.

Example 2: Referring back to our running example, consider minsup = 0.75 and mindisc = 0.25.

It can be seen that for the class value N orth, g = {(S, ≥), (SR, ≤)} is the only gradual itemset such that supp(g, N orth) ≥ minsup. Therefore, the only rule to be considered in this case is {(S, ≥), (SR, ≤)} ⇒ N orth, and by Definition 3, disc(g, N orth) = 1. Thus G N orth = {g}.

For the class value South, the frequent gradual itemsets are g 1 = {(S, ≥), (SR, ≥)}, g 2 = {(S, ≥), (W, ≥)}, g 3 = {(W, ≥), (SR, ≥)} and g 4 = {(S, ≥), (W, ≥), (SR, ≥)}, with respective supports in DB T (South) 4 5 , 1, 4 5 and 4 5 . Thus, Γ(South) = 17 5 , and so, disc(g 2 , South) = 5 17 ≥ 0.25 and for i = 1, 3 or 4, disc(g i , South) = 4 17 < 0.25. Therefore, G South = {g 2 }.

Gradual classification rules are used for the classification of new examples, as shown below.

C. Classification of New Examples

Considering the classification rules constructed in the previous step, we address the issue of labelling new examples where the class values are unknown. We consider in this respect that we are provided with:

1) either a set of tuples known to be of the same class, 2) or a single tuple. Notice that, in the second case above, a set of tuples not known to be of the same class can be considered. In this case, the tuples are processed one by one.

1) Set of Tuples of the Same Class: Let DB N ew be a set of tuples, known to be of the same class that has to be determined. In this case, we first extract all frequent gradual itemsets from DB N ew , considering the same minsup threshold as above. Denoting this set by G N ew , in order to compute which class is the most appropriate, we compare G N ew to every G c . The class c N ew issued by our method is such that:

c N ew = argmax c∈C   g∈G N ew (disc(g, c))   where disc(g, c) = 0 if g ∈ G c
Example 3: Let us consider the set of fruits as described in Table II, where the common provenance is ignored. It is easy to see that G N ew contains the only gradual itemset g = {(S, ≥), (SR, ≤)} with support 0.75. Since g ∈ G N orth and g ∈ G South , we obtain c N ew = N orth, meaning that the fruits are considered from the North.

2) Single Tuple: We now assume that we are provided with a single tuple t defined over I. Computing the class of t is achieved as follows: for every class value c and every g in G c , we compute to which extent t complies with g, as described in Algorithm 1. The criterion introduced to this end, called relevance of c, is denoted by rel(c). It should be noticed that computing supp(g, DB T (c) ∪ {t}) can be performed incrementally provided that the ordering graphs are stored when constructing the frequent gradual itemsets of G c . In this case, the computation simply amounts to inserting the new tuple within the graph. It is easy to see that, if the insertion results in a longer maximal ordered list then s ≥ supp(g, DB T (c)), else the test fails.

Example 4: Referring back to our running example, for the thresholds minsup = 0.75 and mindisc = 0.25, let n = (12, 14, 5.0) (over attributes S, W and SR) be a new tuple to be classified.

As seen in Example 2, for the class value N orth, G N orth = {g} where g = {(S, ≥), (SR, ≤)} and disc(g, N orth) = 1. Since supp(g, DB T (N orth) ∪ {n}) = 1 (by inserting n between t 2 and t 3 ), we obtain that rel(N orth) = 1. (since n cannot be inserted in DB T (South) so as to preserve the ordering according to g 2 ). Thus, supp(g 2 , DB T (South) ∪ {n}) < supp(g 2 , DB T (South)), showing that rel(South) = 0. Hence, c N ew = N orth.

V. EXPERIMENTS In this section, we report on preliminar experiments conducted to assess our approach on synthetic data sets. We show that the runtime for classification new examples is not prohibitive, assuming that gradual rules have been mined.

To this end, the following criteria have been considered, in the case where a set of 500 new examples known to be of the same class value is considered: the size of the database, the number of class values, and the number of attributes.

Figure 2 reports on the runtime for classifying a set of 500 new tuples regarding the number of attributes. We notice that the number of underlying class values in C has a very low impact on runtime, showing that the runtime is constant whatever the number of class values.

On the other hand, it can be seen that, for up to 6 attributes, runtime is far below 5 seconds, and that, for 6 up to 8 attributes, runtime does not exeed 10 seconds. It should be noticed in this respect that, as reported in [START_REF] Berzal | An Alternative Approach to Discover Gradual Dependencies[END_REF], most existing approaches for mining gradual rules encounter difficulties when handling more than 6 attributes.

Figure 3 reports on the runtime regarding the size of the training database DB T , when classifying 500 new examples. In particular, this figure shows that for less than 10 attributes in I, the increase of runtime is not significant (since less than 10 seconds for up to 5000 tuples in DB T ), whereas for 10 attributes (and more) this increase is more important.

Clearly, more experiments are needed in order to better assess our approach. In particular, we plan to consider real data sets collected from satellite pictures for the classification of land areas, according to the type of farming. Indeed,

VI. CONCLUSION

In this paper, we have proposed a novel classification method based on gradual rules. In this context, we have provided an approach for computing gradual rules and for assigning a class value to new examples. The experiments reported in this paper show that our approach is tractable.

Further work include conducting more experiments to better assess the performance and the relevance of our approach. We also intend to investigate other measures to determine to what extent a new tuple t complies with a gradual pattern g. The heuristic presented in [START_REF] Jorio | Fast Extraction of Gradual Association Rules: A heuristic based method[END_REF] will be investigated in this respect, as well as the computation of the number of attributes that prevent a tuple t to be inserted according to the ordering specified by a given gradual itemset. We also intend to study how to efficiently maintain the discriminence updated when new examples are inserted in the training database.

Figure 1 .

 1 Figure 1. Graph of g = {(S, ≥), (SR, ≤)} as computed on TableI

Algorithm 1 :

 1 Data: t a tuple defined over I ; Result: cNew ; foreach c ∈ C do rel(c) ← 0 ; foreach g ∈ Gc do s ← supp(g, DBT (c) ∪ {t}) ; if s ≥ supp(g, DBT (c)) then rel(c) ← rel(c) + disc(g, c) end end end cNew ← argmaxc∈C(rel(c)) ; Classifying a new tuple

Figure 2 .

 2 Figure 2. Runtime for Classifying New Tuples With Respect to the Number of Attributes

Figure 3 .

 3 Figure 3. Runtime for Classifying New Tuples With Respect to the Size of the Database

ACKNOWLEDGMENT

The authors acknowledge Fabien Millet, a Master Student at the Polytech'Montpellier Engineering School, University of Montpellier 2 for his work in implementing and testing the methods and algorithms presented in this paper.