Jean-Yves Charbonnel

On some subspaces of the exterior algebra of a simple Lie algebra

Keywords: Mathematics Subject Classification. 14A10, 14L17, 22E20, 22E46 . root system, exterior algebra, Borel subalgebra. 1

In this article, we are interested in some subspaces of the exterior algebra of a simple Lie algebra g. In particular, we prove that some graded subspaces of degree d generate the g-module d (g) for some integers d.

Introduction

In this note, the base field k is algebraically closed of characteristic 0, g is a simple Lie algebra of finite dimension, ℓ is its rank, and G is its adjoint group.

1.1. Main results. Let b be a Borel subalgebra of g, h a Cartan subalgebra of g, contained in b and u the nilpotent radical of b. Set b g := dim b and n := b gℓ. For k a nonnegative integer, let k (g) be the component of degree k of the exterior algebra (g) of g. The adjoint action of G in g induces an action of G in (g). For all k, k (g) is invariant under this action.

For p parabolic subalgebra of g, containing b, denote by p u the nilpotent radical of p, l the reductive factor of p, containing h, z the center of l and p -,u the complement to p in g, invariant under the adjoint action of h. Let d be the derived algebra of l and d 1 , . . . , d n its simple factors. Set:

E p := p -,u ⊕ z ⊕ p u , n i := dim d i ∩ u,

I k := {( j 1 , . . . , j n ) ∈ N n | j 1 ≤ n 1 , . . . , j n ≤ n n , j 1 + • • • + j n = k}
for k positive integer. Denote by V ′ k,p and V k,p the subspaces of k (g),

V ′ k,p := ( j 1 ,..., j n )∈I k j 1 (d 1 ) ∧ • • • ∧ j n (d n ) and V k,p := k i=0 i (E p ) ∧ V ′ k-i,p .
The goal of this note is the following theorem:

Theorem 1.1. Let k = 1, . . . , n. Then k (g) is the G-submodule of k (g) generated by V k,p .

This result arises from the study of the commuting variety of g (see [START_REF] Charbonnel | Projective dimension and the Commuting variety of a reductive Lie algebra[END_REF]). One of the main step of the proof is to consider the orthogonal complements to some subspaces of k (g) in k (g) with respect to the canonical extension of the Killing form of g to k (g).

1.2. Notations. • Let k * := k \ {0}. For E a finite set, its cardinality is denoted by |E|. For k, m positive integers, set:

N m k := {( j 1 , . . . , j m ) ∈ N m | j 1 + • • • + j m = k}. As usual, for i = (i 1 , . . . , i m ) in N m , |i| := i 1 + • • • + i m .
• For V vector space, denote by (V) the exterior algebra of V. This algebra has a natural gradation. For i integer, denote by i (V) the space of degree i of (V). In particular, for i negative, i (V) is equal to {0}. As g is a G-module for the adjoint action, so is i (g) for all i.

Lemma 1.2. Let A be a subgroup of G, k a positive integer, i a positive integer smaller than k, V a subspace of i (g) and W the A-submodule of i (g) generated by V. Then, for all A-submodule W ′ of k-i (g), W ∧ W ′ is the A-submodule of k (g) generated by V ∧ W ′ .

Proof. Let W ′′ be the A-submodule of k (g) generated by V ∧ W ′ . Let ω and ω ′ be in W and W ′ respectively. For some ω 1 , . . . , ω m in V and g 1 , . . . , g m in A,

ω = g 1 .ω 1 + • • • + g m .ω m , whence ω ∧ ω ′ = g 1 .(ω 1 ∧ g -1 1 .ω ′ ) + • • • + g m .(ω m ∧ g -1 m .ω ′ ) and W ′′ = W ∧ W ′ .
• The Killing form of g is denoted by ., . . For k positive integer, the Killing form of g has a natural extension to k (g) and this extension is not degenerate.

• For a a semisimple Lie algebra, denote by b a the dimension of its Borel subalgebras and ℓ a its rank.

• Let R be the root system of h in g, R + the positive root system of R defined by b and Π the basis of R + . For α in R, H α is the coroot of α, the corresponding root subspace is denoted by g α and a generator x α of g α is chosen so that x α , x -α = 1.

• We consider on Π its structure of Dynkin diagram. As g is simple, Π is connected and has three extremities when Π has type D ℓ , E 6 , E 7 , E 8 , one extremity when Π has type A 1 and 2 otherwise. The elements β 1 , . . . , β ℓ of Π are ordered as in [Bou02, Ch. VI].

• Let X be a subset of Π. We denote by R X the root subsystem of R generated by X and we set

< X >:= R + ∩ R X so that R X =< X > ∪-< X > .
Let p X be the parabolic subalgebra of g,

p X := b ⊕ α∈<X> g -α ,
p X,u its nilpotent radical, l X the reductive factor of p X containing h, z X the center of l X , d X the derived algebra of l X , p X,-,u the complement to p X in g, invariant under ad h and E X the sum of z X , p X,u , p X,-,u . When X is empty, p X is the Borel subalgebra b.

• Let X be a nonempty subset of Π and X 1 , . . . , X n X its connected components. For i = 1, . . . , n X , denote by n i the cardinality of < X i > and d i the subalgebra of g generated by g ±β , β ∈ X i . Then d 1 , . . . , d n X are the simple factors of d X . For k positive integer, set:

V k,p X := n 1 j 1 =0 • • • n n X j n X =0 j 1 (d 1 ) ∧ • • • ∧ j n X (d n X ) ∧ k-j 1 -•••-j n X (E X )
and denote by V k,X the G-submodule of k (g) generated by V k,p X .

Orthogonal complement

Let ℓ ≥ 2 and X a nonempty subset of Π. Set:

p := p X , p u := p X,u , l := l X , p -,u := p X,-,u , p ±,u := p u ⊕ p -,u , p -:= l ⊕ p -,u , d := dim p u .
2.1. General fact. Let A be a subgroup of G. For k positive integer and W subspace of k (g), denote by W ⊥ the orthogonal complement to W in k (g). As the bilinear form on k (g), defined by the Killing form, is not degenerate,

dim W + dim W ⊥ = dim k (g).
Lemma 2.1. Let k be a positive integer smaller than dim g. Let V be a subspace of k (g). Denote by W the A-submodule of k (g) generated by V.

Then W ⊥ is the biggest A-submodule of k (g), contained in V ⊥ . Proof. Denote by W # the biggest A-submodule contained in V ⊥ . As W is a A-module, so is W ⊥ . Then W ⊥ is contained in W # . Moreover, V is contained in the orthogonal complement to W # in k (g). Hence W is orthogonal to W # since the orthogonal complement to W # is a A-module. As a result, W # = W ⊥ .
2.2. Orthogonality. Let V be a finite dimensional vector space with a non degenerate symmetric bilinear form on V. For k positive integer, it induces a non degenerate symmetric bilinear form on k (V). Let V 1 , . . . , V m be pairwise orhogonal subspaces of V such that V is the direct sum of these subspaces. For i = (i 1 , . . . , i m ) in N m k , set:

C i,V := i 1 (V 1 ) ∧ • • • ∧ i m (V m ). If V m is the direct sum of two isotropic subspaces V m,+ and V m,-, for i = (i 1 , . . . , i m+1 ) in N m+1 k , set: i * := (i 1 , . . . , i m-1 , i m+1 , i m ) and C ′ i,V := i 1 (V 1 ) ∧ • • • ∧ i m-1 (V m-1 ) ∧ i m (V m,+ ) ∧ i m+1 (V m,-). Lemma 2.2. Let k be a positive integer. (i) For i, i ′ in N m k , if i i ′ then C i,V is orthogonal to C i ′ ,V . (ii) Suppose that V m is the direct sum of two isotropic subspaces V m,+ and V m,-. For i, i ′ in N m+1 k , if i ′ i * then C ′ i,V is orthogonal to C ′ i ′ ,V .
Proof. Denote by ., . the symmetric bilinear form on V and k (V). As V 1 , . . . , V m are pairwise orthogonal and V is the direct sum of these subspaces, for i = 1, . . . , m, the restriction to V i × V i of ., . is non degenerate. For j = 1, . . . , m, let n j be the dimension of the sum

V 1 ⊕ • • • ⊕ V j
and v 1 , . . . , v n m an orthonormal basis of V such that {v 1 , . . . , v n j } is contained in the union of V 1 , . . . , V j for j = 1, . . . , m.

(i) Let i and i ′ be in N m k such that i i ′ . If k > n m , there is nothing to prove. Suppose k ≤ n m . For j = j 1 , . . . , j k in {1, . . . , n m } such that 1 ≤ j 1 < • • • < j k ≤ n m , set:

w j := v j 1 ∧ • • • ∧ v j k .
Setting n 0 := 0, w j is in C i,V if and only if |{l ∈ {1, . . . , k} | n s-1 + 1 ≤ j l ≤ n s }| = i s for s = 1, . . . , m. Denote by I i the set of j satisfying this condition so that w j , j ∈ I i is a basis of C i,V .

Let ( j, j ′ ) be in

I i × I i ′ . By definition, w j , w j ′ = det ( v j l , v j ′ l ′ , 1 ≤ l, l ′ ≤ k). As the basis v 1 , . . . , v n m ′ is orthonormal, v j l , v j ′ l ′ = δ j l , j ′ l ′
with δ s,s ′ the Kronecker symbol. As a result, if all the lines of the above matix are all different from 0 then

|{l ∈ {1, . . . , k} | n s-1 + 1 ≤ j l ≤ n s }| = |{l ∈ {1, . . . , k} | n s-1 + 1 ≤ j ′ l ≤ n s }| for s = 1, . . . , m since V 1 , .
. . , V m are pairwise orthogonal. Then w j , w j ′ = 0 since i i ′ , whence the assertion.

(ii) Let i and i ′ be in N m+1 k such that i ′ i * . By (i), we can suppose that i s = i ′ s for s = 1, . . . , m -1. Since V m,+ and V m,-are isotropic, they have the same dimension m 0 and V m has a basis u 1 , . . . , u 2m 0 such that

{u 1 , . . . , u m 0 } ⊂ V m,+ , {u m 0 +1 , . . . , u 2m 0 } ⊂ V m,-, u s , u s ′ +m 0 = δ s,s ′ for 1 ≤ s, s ′ ≤ m 0 . Let v ′ 1 , . . . , v ′ n m be the basis of V such that v ′ l = v l for l = 1, . . . , n m-1 and v ′ l ′ = u l ′ -n m-1 for l ′ = n m-1 + 1, . . . , n m . For j = j 1 , . . . , j k in {1, . . . , n m } such that 1 ≤ j 1 < • • • < j k ≤ n m , set: w ′ j = v ′ j 1 ∧ • • • ∧ v ′ j k . Then w ′ j is in C ′ i,V if and only if |{l ∈ {1, . . . , k} | n m-1 +1 ≤ j l ≤ n m-1 +m 0 }| = i m , |{l ∈ {1, . . . , k} | n m-1 +m 0 +1 ≤ j l ≤ n m }| = i m+1 , |{l ∈ {1, . . . , k} | n s-1 + 1 ≤ j l ≤ n s }| = i s for s = 1, . . . , m -1. Denote by I i the set of j satisfying this condition so that w ′ j , j ∈ I i is a basis of C ′ i,V . Let ( j, j ′ ) be in I i × I i ′ . By definition, w ′ j , w ′ j ′ = det ( v ′ j l , v ′ j ′ l ′ , 1 ≤ l, l ′ ≤ k). Then j l ≤ n m-1 =⇒ v ′ j l , v ′ j ′ l ′ = δ j j , j ′ l ′ , j l > n m-1 and j ′ l ′ > n m-1 =⇒ v ′ j l , v ′ j ′ l ′ = δ | j j -j ′ l ′ |,m 0 .
As a result, if all the lines of the above matix are all different from 0 then

|{l ∈ {1, . . . , k} | n m-1 + 1 ≤ j l ≤ n m-1 + m 0 }| = |{l ∈ {1, . . . , k} | n m-1 + m 0 + 1 ≤ j ′ l ≤ n m }| since i s = i ′ s for s ≤ m -1 and V 1 , .
. . , V m are pairwise orthogonal. Then w j , w j ′ = 0 since i ′ i * , whence the assertion.

For i = (i 1 , i 2 , i 3 ) in N 3 , set:

C i := i 1 (l) ∧ i 2 (p u ) ∧ i 3 (p -,u ) and denote by i * the element (i 1 , i 3 , i 2 ) of N 3 . Corollary 2.3. Let k be a positive integer. (i) For i, i ′ in N 3 k , C i is orthogonal to C i ′ if i * i ′ . (ii) For i in N 3 k , the orthogonal complement to C i in k (g) is equal to i ′ ∈N 3 k \{i * } C i ′ .
Proof. (i) Let i and i ′ be in N 3 k such that i * i ′ . By Lemma 2.1(ii), C i is orthogonal to C i ′ since l and p ±,u are orthogonal and p u and p -,u are isotropic.

(ii

) Since k (g) is the direct sum of C i ′ , i ′ ∈ N 3 k , the orthogonal complement to C i in k (g) is the direct sum of C i ′ , i ′ ∈ N n+3 k \ {i * } by (i). Corollary 2.4. Let k = 1, . . . , d. (i) The orthogonal complement to k (p -,u ) in k (g) is equal to p -∧ k-1 (g). (ii) The orthogonal complement to k (p ±,u ) in k (g) is equal to l ∧ k-1 (g).
Proof. (i) Let I 1 be the subset of

N 3 k , I 1 := {(i 1 , i 2 , i 3 ) ∈ N 3 k | i 1 = i 2 = 0}. The complement to I * 1 in N 3 k is equal to {(i 1 , i 2 , i 3 ) ∈ N 3 k | i 1 > 0 or i 3 > 0}, whence the assertion by Corollary 2.3 since k (p -,u ) = i∈I 1 C i . (ii) Let I 2 be the subset of N 3 k , I 2 := {(i 1 , i 2 , i 3 ) ∈ N 3 k | i 1 = 0}. The complement to I * 2 in N 3 k is equal to {(i 1 , i 2 , i 3 ) ∈ N 3 k | i 1 > 0}, whence the assertion by Corollary 2.3 since k (p ±,u ) is the sum of C i , i ∈ I 2 .

Action of the unipotent radical of a parabolic subgroup

Let ℓ ≥ 2 and X a subset of Π. Set:

p := p X , p u := p X,u , l := l X , p -,u := p X,-,u , p ±,u := p u ⊕ p -,u , p -:= l ⊕ p -,u , d := dim p u .
Denote by L and H the connected closed subgroups of G whose Lie algebras are l and h respectively. Let P and P -be the normalizers of p and p -in G and P u and P -,u their unipotent radicals.

Invariant subspaces. Let

k = 1, . . . , d, W k the biggest P u -submodule of k (g) contained in p -∧ k-1 (g) and V k,u the P u -submodule of k (g) generated by k (p -,u ). Lemma 3.1. Let W k,0 be the subspace of elements of p -∧ k-1 (g) invariant under u. (i) The subspace W k of k (g) is invariant under u. (ii) The subspace W k,0 of k (g) is contained in W k and generated by highest weight vectors. (iii) The subspace U(u -).W k,0 of k (g) is the biggest G-submodule of k (g) contained in p -∧ k-1 (g). Proof. (i) Denote by W ′ k the L-submodule of k (g) generated by W k . As p -∧ k-1 (g) is invariant under L, W ′ k is contained in p -∧ k-1 (g). For x in p u and g in L, x.g.W k = g.Adg -1 (x).W k ⊂ W ′ k , since p u is invaraint under the adjoint action of L in g. Then W ′ k is invariant under P u , whence W k = W ′ k . As a result, W k is a u-submodule of k (g) since u is contained in p. (ii) For ω in W k,0 , the subspace of k (g) generated by ω is a P u -submodule contained in p -∧ k-1 (g). Hence W k,0 is contained in W k . Moreover, for x in u and g in H, x.g.ω = g.Adg -1 (x).ω = 0. Hence W k,0 is invariant under H. As a result, W k,0 is generated by highest weight vectors. (iii) By (ii), U(u -).W k,0 is the G-submodule of k (g) generated by W k,0 . As u -is contained in p -, p -∧ k-1 (g) is a U(u -)-submodule of k (g) so that U(u -).W k,0 is contained in p -∧ k-1 (g). Since a G-submodule of k (g) is generated by highest weight vectors, U(u -).W k,0 is the biggest G-submodule of k (g) contained in p -∧ k-1 (g). Corollary 3.2. (i) The subspace W k of k (g) is the biggest G-submodule contained in p -∧ k-1 (g). (ii) The subspace V k,u of k (g) is a G-submodule of k (g). Proof. (i) Denote by W k the biggest G-submodule of k (g) contained in p -∧ k-1 (g). Then W k is contained in W k . Let W k,1 be a complement to W k in k (g), invariant under G. Then W k is the direct sum of W k and W k ∩ W k,1 . By Lemma 3.1(i), W k ∩ W k,1 is invariant under u. Then, by Lie's Theorem, W k,0 ∩ W k,1 {0} if W k ∩ W k,1 {0}. Hence W k = W k since W k,0 is contained in W k by Lemma 3.1(iii).
(ii) By Corollary 2.4(i) and Lemma 2.1, W k is the orthogonal complement to V k,u in k (g). Hence V k,u is a G-module by (i).

3.2.

A particular case. In this subsection, for some β in Π, X := Π \ {β}. Denote by h β the orthogonal complement to H β in h. Let Z be the subset of elements α of < X > such that β + α is a root. Set:

Y := R + \ (< X > ∪{β}), Z ′ :=< X > \Z, E := α∈Y g α , E -:= α∈Y g -α , u 0 := α∈Z g α , u 0,+ := α∈Z ′ g α , u 0,0 := α∈Z g -α , u 0,-:= α∈Z ′ g -α . Then g := E -⊕ g -β ⊕ u 0,-⊕ u 0,0 ⊕ kH β ⊕ h β ⊕ u 0 ⊕ u 0,+ ⊕ g β ⊕ E. For i = (i 1 , . . . , i 10 ), set: C i := i 1 (E -) ∧ i 2 (g -β ) ∧ i 3 (u 0,-) ∧ i 4 (u 0,0 ) ∧ i 5 (kH β )∧ i 6 (h β ) ∧ i 7 (u 0 ) ∧ i 8 (u 0,+ ) ∧ i 9 (g β ) ∧ i 10 (E). For k positive integer, k (g) is the direct sum of C i , i ∈ N 10 k .
For α in Z, denote by ω ′ α and ω α the elements of 2 (g),

ω ′ α := H β ∧ [x β , x α ] + 2x β ∧ x α , ω α := H β ∧ [x -β , x -α ] + c α x -β ∧ x -α , with c α := - 1 2 H β , H β [x β , x α ], [x -β , x -α ] so that ω α is orthogonal to ω ′ α . Lemma 3.3. Let k = 1, . . . , d. Denote by I the subset of elements i of N 10 k such that i 1 + • • • + i 8 ≥ 2, M ′ the subspace of elements µ α , α ∈ Z of k-1 (E) Z such that α∈Z [x β , x α ] ∧ µ α = 0
and M the image of M ′ by the map

k-1 (E) Z / / k (g) , (µ α , α ∈ Z) -→ α∈Z x α ∧ µ α . The space W k is contained in the subspace of k (g) generated by M, ω ′ α ∧ k-2 (E), α ∈ Z, C i , i ∈ I. Proof. By Corollary 2.4(i) and Corollary 3.2, W k is the biggest G-module contained in p -∧ k-1 (g). Denoting by I ′ the subset of elements i of N 10 k such that i 1 + • • • + i 8 > 0, p -∧ k-1 (g) is the sum of C i , i ∈ I ′ . Then for i in I and x in g, x.C i is contained in p -∧ k-1 (g). The complement to I in I ′ is equal to the subset of elements i of I ′ such that i 9 + i 10 = k -1. For i in I ′ \ I such that i 5 = i 7 = 0, x β .C i is contained in p -∧ k-1 (g) since [x β , E -] ⊂ p -, [x β , g -β ] ⊂ p -, [x β , u 0,-+ u 0,0 + h β + u 0,+ ] = {0}. For i in I ′ \ I, i 7 = 1 and i 9 = 0 =⇒ x β .C i ⊂ C i ⊕ k (E), i 7 = 1 and i 9 = 1 =⇒ x β .C i ⊂ C i ⊕ g β ∧ k-1 (E), i 5 = 1 and i 9 = 0 =⇒ x β .C i ⊂ C i ⊕ g β ∧ k-1 (E), i 5 = 1 and i 9 = 1 =⇒ x β .C i ⊂ C i .
As a result, for ω and

µ α , α ∈ Z in k-1 (E) and µ ′ α , α ∈ Z in k-2 (E) such that ω ′ + H β ∧ ω + α∈Z x α ∧ µ α + α∈Z x β ∧ x α ∧ µ ′ α ∈ W k for some ω ′ in the sum of C i , i ∈ I, -2ω + α∈Z [x β , x α ] ∧ µ ′ α = 0 and α∈Z [x β , x α ] ∧ µ α = 0 since x β .W k is contained in p -∧ k-1 (g)
, whence the lemma.

For i = (i 1 , . . . , i 10 ) in N 10 , denote by i * the element of N 10 , i * := (i 10 , i 9 , i 8 , i 7 , i 5 , i 6 , i 4 , i 3 , i 2 , i 1 ).

By Lemma 2.2(ii), for k positive integer and i, i

′ in N 10 k , C i is orthogonal to C i ′ if and only if i ′ i * . Corollary 3.4. Let k = 1, . . . , d and α in Z. (i) The space ω α ∧ k-2 (E -) is contained in V k,u . (ii) The space g α ∧ k-1 (E -) is contained in V k,u . (iii) The spaces H α ∧ k-2 (E -) and g -α ∧ k-1 (E -) are contained in V k,u . (iv) The space h β ∧ k-1 (E -) is contained in V k,u .
Proof. (i) Let I 1 be the subset of elements i of N 10 k such that (i 1 = k -1 and i 5 = 1) or

(i 1 = k -2, i 2 = 1, i 4 = 1). Then ω α ∧ k-2 (E -) is contained in the sum of C i , i ∈ I 1 . Hence ω α ∧ k-2 (E -) is orthogonal to C i
for all i in I and for i such that i 7 = 1 and

i 10 = k -1. By Corollary 2.3(i), for all γ in Z, ω α ∧ k-2 (E -) is orthogonal to ω ′ γ ∧ k-2 (E)
since ω α and ω ′ γ are orthogonal, whence the assertion by Lemma 3.3 since V k,u is the orthogonal complement to W k in k (g) by Lemma 2.1.

(ii) The space

g α ∧ k-1 (E -) is contained in C i with i in N 10 k such that i 7 = 1 and i 1 = k -1. Hence g α ∧ k-1 (E -) is orthogonal to C j for all j in I. Moreover, it is orthogonal to C j for j in N 10
k such that j 7 = 1 and j 10 = k-1 and C j ′ for j ′ in I 1 . As a result, g α ∧ k-1 (E -) is orthogonal to W k by Lemma 3.3, whence the assertion since V k,u is the orthogonal complement to W k in k (g) by Lemma 2.1.

(iii) By (ii) and Corollary 3.2(ii), for ω in k-1 (E -),

V k,u ∋ x -α .(x α ∧ ω) = -H α ∧ ω + x α ∧ x -α .ω and x -α .(H α ∧ ω) = 2x -α ∧ ω + H α ∧ x -α .ω. As E -is invariant under the adjoint action of x -α , x α ∧ x -α .ω is in V k,u
by (ii), whence the assertion.

(iv) The space

h β ∧ k-1 (E -) is equal to C i for i such that i 1 = k -1 and i 6 = 1. Then C i is orthogonal to C j for j in I. Moreover, it is orthogonal to g α ∧ k-1 (E) for all α in Z and H β ∧ k-1 (p u ) since h β is orthogonal to H β and u. As a result, h β ∧ k-1 (E -) is orthogonal to W k by Lemma 3.3, whence the assertion since V k,u is the orthogonal complement to W k in k (g) by Lemma 2.1.
Denote by d the derived algebra of l.

Proposition 3.5. Let k = 1, . . . , d, i = 0, . . . , k -1.

(i) Let M be a P u -submodule of i (g). Then the P u -submodule of k (g)

generated by k-i (p -,u )∧ M contains k-i-1 (p -,u ) ∧ d ∧ M.
(ii) Let N be a P -,u -submodule of i (g). Then the P -,u -submodule of k (g) generated by

k-i (p u ) ∧ N contains k-i-1 (p u ) ∧ d ∧ N. Proof. (i) By Lemma 1.2, it is sufficient to prove that V k-i,u contains k-i-1 (p -,u ) ∧ d since M is a P u -module. For α in Z, H α ∈ β(H α ) 2 H β + h β .
So, by Corollary 3.4,(iii) and (iv),

H β ∧ k-i-1 (E -) is contained in V k-i,u . Then, by Corol- lary 3.4(i), V k-i,u ⊃ g -β ∧ g -α ∧ k-i-2 (E -).
As a result, by Corollary 3.4(iii), for all α in Z,

g -α ∧ k-i-1 (p -,u ) is contained in V k-i,u . As g is simple, the l-submodule of g, generated by g α , α ∈ Z is equal to d. By Corollary 3.2(ii), V k-i,u is a l-module. Then, by Lemma 1.2, V k-i,u contains k-i-1 (p -,u ) ∧ d since k-i-1 (p -,u
) is a l-module, whence the assertion.

(ii) For some automorphism g of g, g(p u ) = p -,u , g(p -,u ) = p u , g(h) = h. Then l and d are invariant under g. A a result, by (i), the P -,u -submodule of k (g) generated by

k-i (p u ) ∧ N contains k-i-1 (p u ) ∧ d ∧ N since g(N) is a P u -submodule of i (g).

Proof of Theorem 1.1

Let ℓ ≥ 2 and X a nonempty subset of Π, different from Π. Set:

p := p X , p u := p X,u , l := l X , z := z X , d := d X , n := n X , p -,u := p X,-,u , p ±,u := p u ⊕ p -,u , E := E X , p -:= l ⊕ p -,u , d := dim p u .
Recall that d 1 , . . . , d n are the simple factors of d and for i = 1, . . . , n, n i is the number of positive roots α such that g α is contained in d i . Let P u and P -,u be as in Section 3. For k = 1, . . . , n, set V k,p := V k,p X and V k,X := V k .

A partial result. Let n ′ be the sum n

1 + • • • + n n . For k = 1, . . . , n, denote by V ′ k the subspace of k (g), V ′ k := n ′ j=0 j (d) ∧ k-j (E). Proposition 4.1. Suppose |X| = ℓ -1. Let k = 1, . . . , n. Then k (g) is the G-submodule of k (g) generated by V ′ k . Proof. For k = 1, . . . , d, denote by E k the G-submodule of k (g) generated by k (E). For k = 1, . . . , n ′ , V ′ k = k (g) and for k > n ′ , V ′ k = n ′ (g) ∧ k-n ′ (E). So, by Lemma 1.2, it is sufficient to prove that E k = k (g) for k = 1, . . . , d since n = n ′ + d.
Prove the assertion by induction on k. For k = 1 the assertion is true since g is simple. Suppose k > 1 and the assertion true for k -1. As |X| = ℓ -1, z has dimension 1 and

k (E) = k (p ±,u ) ⊕ z ∧ k-1 (p ±,u ) = k j=0 k-j (p -,u ) ∧ j (p u ) ⊕ k-1 j=0 k-1-j (p -,u ) ∧ z ∧ j (p u ).
For j = 0, . . . , d, j (p u ) and j+1 (p u ) + z ∧ j (p u ) are P u -submodules of j (g) and j+1 (g) respectively. Then, by Proposition 3.5(i),

E k contains k-j-1 (p -,u ) ∧ d ∧ j (p u ) and k-j ′ -2 (p -,u ) ∧ z ∧ d ∧ j ′ (p u )
for j = 0, . . . , k -1 and

j ′ = 0, . . . , k -2. Hence E k contains k-j-1 (p -,u ) ∧ g ∧ j (p u ) and k-j ′ -2 (p -,u ) ∧ z ∧ g ∧ j ′ (p u )
for j = 0, . . . , k -1 and

j ′ = 0, . . . , k -2 since k (E) contains k-j (p -,u ) ∧ j (p u ), k-j-1 (p -,u ) ∧ j+1 (p u ), k-j-1 (p -,u ) ∧ z ∧ j (p u ), k-j ′ -2 (p -,u ) ∧ z ∧ j ′ +1 (p u )
for j = 0, . . . , k -1 and j ′ = 0, . . . , k -2. As a result, E k contains g ∧ k-1 (E). Then, by Lemma 1.2 and the induction hypothesis, E k = k (g), whence the proposition.

Remark 4.2. When X is connected, V k,p = V ′ k,p .
Then, in this case under the assumption |X| = ℓ -1, V k = k (g) by Proposition 4.1.

4.2.

A first particular case. In this subsection, |X| = ℓ -1 so that n ∈ {1, 2, 3}. As a matter of fact, n = 3 only for type D and E. As in Subsection 4.1, n ′ = n 1 + • • • + n n . For i = (i 1 , . . . , i n ) and k = 0, . . . , n, set:

D i := i 1 (d 1 ) ∧ • • • ∧ i n (d n ) and I k := {(i 1 , . . . , i n ) ∈ N n k | 0 ≤ i 1 ≤ n 1 , . . . , 0 ≤ i n ≤ n n }.
For l, l ′ nonnegative integers and i in N n , set:

V l,l ′ ,i := l (p -,u ) ∧ D i ∧ l ′ (p u ) and V ′ l,l ′ ,i := l (p -,u ) ∧ z ∧ D i ∧ l ′ (p u ).
For j in N n and t = 0, . . . , | j|, denote by ∆ j and ∆ j,t the subsets of N n ,

∆ j := { j ′ ∈ N n | j ′ 1 ≤ j 1 , . . . , j ′ n ≤ j n } and ∆ j,t := ∆ j ∩ N n t . Lemma 4.3. Let k = 1, . . . , n, (l, l ′ ) in N 2 such that l + l ′ ≤ 2d, i in I k-l-l ′ and i ′ in I k-l-l ′ -1 . (i) Suppose that V l,l ′ +s, j is contained in V k for all nonnegative integer s such that l + l ′ + s ≤ 2d and all j in ∆ i,|i|-s . Then d ∧ V l-1,l ′ ,i is contained in V k .
(ii) Suppose that V l+s,l ′ , j is contained in V k for all nonnegative integer s such that l + l ′ + s ≤ 2d and all j in

∆ i,|i|-s . Then d ∧ V l,l ′ -1,i is contained in V k .
(iii) Suppose that V ′ l,l ′ +s, j is contained in V k for all nonnegative integer s such that l+l ′ + s ≤ 2d and all j in

∆ i ′ ,|i ′ |-s . Then d ∧ V ′ l-1,l ′ ,i ′ is contained in V k . (iv) Suppose that V ′ l+s,l ′ , j is contained in V k for all nonnegative integer s such that l +l ′ + s ≤ 2d and all j in ∆ i ′ ,|i ′ |-s . Then d ∧ V ′ l,l ′ -1,i ′ is contained in V k . Then V k = k (g).
Proof. Prove the proposition by induction on k. For k = 1, it is true since g is simple. Suppose k > 1 and the proposition true for k -1. By Lemma 1.2 and the induction hypothesis, it is sufficient to prove that g ∧ V k-1,p is contained in V k . As a matter of fact, we have to prove that g ∧ V l,l ′ ,i and g

∧ V ′ l,l ′ ,i ′ are contained in V k for (l, l ′ ) in N 2 such that l + l ′ ≤ 2d, i in I k-l-l ′ -1 and i ′ in I k-l-l ′ -2 since V k-1,p = 2d t=0 (l,l ′ )∈N 2 t i∈I k-t-1 V l,l ′ ,i ⊕ 2d t=0 (l,l ′ )∈N 2 t i ′ ∈I k-t-2 V ′ l,l ′ ,i ′ . Let (l, l ′ ) be in N 2 such that l + l ′ ≤ 2d, i in I k-l-l ′ -1 and i ′ in I k-l-l ′ -2 . If Condition (1) or Condition (2) is satisfied, then l + l ′ < 2d by Proposition A.1. As a result, by Corollary 4.4, g ∧ V l,l ′ ,i and g ∧ V ′ l,l ′ ,i ′ are contained in V k . If Condition (3) is satisfied, l l ′ < 2d or l + l ′ = 2d, i 1 < n 1 , i 2 < n 2 .
In the first case, by Corollary 4.4, g ∧ V l,l ′ ,i and g ∧ V ′ l,l ′ ,i ′ are contained in V k . In the second case, g ∧ V l,l ′ ,i and g ∧ V ′ l,l ′ ,i ′ are contained in V k,p , whence the proposition. Remark 4.6. By the proof of Proposition 4.5, when n = 2, for k = 1, . . . , inf{2d+n 1 -1, 2d+n 2 -1}, V k = k (g).

A second particular case. In this subsection, |X|

= ℓ -1, Π has classical type, n = 2 and 2d + n 1 ≤ n. By Proposition A.1, 2d + n 2 > n, ℓ ≥ 6 for Π of type A ℓ , ℓ ≥ 7 for Π of type B ℓ or C ℓ , ℓ ≥ 8 for Π of type D ℓ .
For i = (i 0 , i 1 , i 2 , i 3 , i 4 ) in N 5 , set:

C i := i 0 (z) ∧ i 1 (d 1 ) ∧ i 2 (d 2 ) ∧ i 3 (p -,u ) ∧ i 4 (p u ).
Let k = 2d + n 1 , . . . , n and j = k -2dn 1 . Set: d, d -1). Lemma 4.7. Denote by M ι and M ι ′ the G-submodules of k (g) generated by C ι and C ι ′ respectively.

ι := (0, n 1 , j, d, d), ι ′ := (1, n 1 , j -1, d, d), ι + := (0, n 1 + 1, j -1, d, d), ι ′ + := (1, n 1 + 1, j -2, d, d), κ := (0, n 1 + 1, j, d -1, d), κ ′ := (1, n 1 + 1, j -1, d -1, d), κ -:= (0, n 1 + 1, j, d, d -1), κ ′ -:= (1, n 1 + 1, j -1,
(i) The subspace M ι of k (g) contains C κ and C κ -, and

M ι ′ contains C κ ′ and C ′ κ ′ - . (ii) The spaces C ι + and C ι ′ + are contained in M ι and M ι ′ respectively. Proof. (i) The subspaces of k-d (g), n 1 (d 1 ) ∧ j (d 2 ) ∧ d (p u ) and n 1 (d 1 ) ∧ j (d 2 ) ∧ z ∧ d (p u ),
are invariant under P u . So, by Proposition 3.5(i), M ι and M ι ′ contain C κ and C κ ′ respectively. The subspaces of k-d (g),

d (p -,u ) ∧ n 1 (d 1 ) ∧ j (d 2 ) and d (p -,u ) ∧ n 1 (d 1 ) ∧ j (d 2 ) ∧ z,
are invariant under P -u . So, by Proposition 3.5(ii), M ι and M ι ′ contain C κ -and C κ ′ -respectively.

(ii) For i = (i 0 , i 1 , i 2 , i 3 , i 4 ) in N 5 , set: i * := (i 0 , i 1 , i 2 , i 4 , i 3 , ). By corollary 2.3(i), for i, j in N 5 , C i is orthogonal to C j if and only if j i * .

Denote by M ⊥ ι and C ⊥ ι the orthogonal complements to M ι and C ι in k (g) respectively. By Lemma 2.1,

M ⊥ ι is the biggest G-module contained in C ⊥ ι . Suppose that C ι + is not contained in M ι . A contradiction is expected. As k (g) is the direct sum of C i , i ∈ N 5 k , C ⊥ ι is the direct sum of C i , i ∈ N 5 k \ {ι} since ι * = ι. By (i), M ⊥ ι is contained in the sum of C i , i ∈ N 5 k \ {ι, κ, κ -}. Since ι * + = ι + , the orthogonal complement to C ι + is the sum of C i , i ∈ N 5 k \ {ι + }. Then M ⊥ ι is not contained in the direct sum of C i , i ∈ N 5 k \ {ι, κ, κ -, ι + } since C ι + is not contained in M ι . Hence for some subspace M of n 1 +1 (d 1 ) ∧ j-1 (d 2 ), M {0} and M ⊥ ι ⊃ d (p -,u ) ∧ M ∧ d (p u ) since d (p -,u ) ∧ d (p u ) has dimension 1.
As a result, by Proposition 3.5, (i) and (ii),

M ⊥ ι ⊃ d-1 (p -,u ) ∧ d 2 ∧ M ∧ d (p u ) M ⊥ ι ⊃ d (p -,u ) ∧ d 2 ∧ M ∧ d-1 (p u ) since M ∧ d (p u ) is a P u -submodule of d+ j+n 1 (g) and M ∧ d (p -,u ) is a P -,u -submodule of d+ j+n 1 (g). As j is smaller than dim d 2 and M is different from zero, d 2 ∧ M {0}. Then C κ +C κ,- is not contained in M ι since C κ + C κ -is orthogonal to C i for all i in N 5 k \ {κ, κ -}, whence the contradiction. Denote by M ⊥ ι ′ and C ⊥ ι ′ the orthogonal complements to M ι ′ and C ι ′ in k (g) respectively. By Lemma 2.1, M ⊥ ι ′ is the biggest G-module contained in C ⊥ ι ′ . Suppose that C ι ′ + is not contained in M ι ′ . A contradiction is expected. As k (g) is the direct sum of C i , i ∈ N 5 k , C ⊥ ι ′ is the direct sum of C i , i ∈ N 5 k \ {ι ′ } since ι ′ * = ι ′ . By (i), M ⊥ ι ′ is contained in the sum of C i , i ∈ N 5 k \ {ι ′ , κ ′ , κ ′ -}. Since ι ′ + * = ι ′ + , the orthogonal complement to C ι ′ + is the sum of C i , i ∈ N 5 k \ {ι ′ + }. Then M ⊥ ι ′ is not contained in the direct sum of C i , i ∈ N 5 k \ {ι ′ , κ ′ , κ ′ -, ι ′ + } since C ι ′ + is not contained in M ι ′ . Hence for some subspace M ′ of n 1 +1 (d 1 ) ∧ j-2 (d 2 ), M ′ {0} and M ⊥ ι ′ ⊃ d (p -,u ) ∧ z ∧ M ′ ∧ d (p u ) since z ∧ d (p -,u ) ∧ d (p u )
has dimension 1. As a result, by Proposition 3.5, (i) and (ii),

M ⊥ ι ′ ⊃ d-1 (p -,u ) ∧ z ∧ d 2 ∧ M ′ ∧ d (p u ) M ⊥ ι ′ ⊃ d (p -,u ) ∧ z ∧ d 2 ∧ M ′ ∧ d-1 (p u ) since z ∧ M ′ ∧ d (p u ) is a P u -submodule of d+ j+n 1 (g) and z ∧ M ′ ∧ d (p -,u ) is a P -,u -submodule of d+i+n 1 (g). As j is smaller than dim d 2 and M ′ is different from zero, d 2 ∧ M ′ {0}. Then C κ ′ + C κ ′ ,-is not contained in M ι ′ since C κ ′ + C κ ′ -is orthogonal to C i for all i in N 5 k \ {κ ′ , κ ′ -}, whence the contradiction. Proposition 4.8. For k = 2d + n 1 , . . . , n, V k is equal to k (g).
Proof. Prove the proposition by induction on k. Let (l, l ′ ) be in

N 2 such that l+l ′ ≤ 2d, i ∈ I k-l-l ′ -1 , i ′ ∈ I k-l-l ′ -2 . If l + l ′ < 2d then g ∧ V l,l ′ ,i and g ∧ V ′ l,l ′ ,i ′ are contained in V k by Corollary 4.4. If l = l ′ = d and i 1 < n 1 then g ∧ V l,l ′ ,i is contained in V k,p since 2d + n 2 > n by Proposition A.1. If
Let Y be as in Lemma 4.9. Then d Y has two simple factors d 1 and a and d 1 is a simple factor of d. Denote by V k,Y the G-submodule of k (g) generated by V k,p Y . Then, by Proposition 4.5, Remark 4.6 and Proposition 4.8, V k,Y = k (g). The intersection q := a ∩ p is a parabolic subalgebra of a. Let E ′ be the intersection of E and a. Then E is the direct sum of E ′ and E Y . As a result, setting n * := b aℓ a ,

V k,p = n 1 i=0 n * j=0 i (d 1 ) ∧ V j,q ∧ k-i-j (E Y ).
Let A be the connected closed subgroup of G whose Lie algebra is a. By the hypothesis, for j = 1, . . . , n * , the A-submodule of j (a), generated by V j,q , is equal to j (a). Hence, by Lemma 1.2,

V k,p Y is contained in V k since d 1 and E Y are invariant under A, whence V k = k (g).
To finish the proof of Theorem 1.1, we have to consider the case when X does not contain all the extremities of Π.

Lemma 4.11. Suppose that X does not contain all the extremities of Π.

(i) There exists a sequence X 0 ⊂ • • • ⊂ X m = Π of connected subsets of Π satisfying the following conditions:

(1)

for i = 1, . . . , m, |X i \ X i-1 | = 1,
(2) X contains the extremities of X 0 . (ii) For i = 0, . . . , m, let a i be the subalgebra of g generated by g ±β , β ∈ X i . Then a i is a simple algebra and p i := p ∩ a i is a parabolic subalgebra of a i .

(iii) For i = 0, . . . , m, E is the direct sum of E i := E ∩ a i and E X i .

Proof. (i) Define X i by induction on i. Let X 0 be a connected subset of Π, containing X of minimal cardinality. By minimality of |X 0 |, X contains the extremities of X 0 . Suppose i > 0 and X i-1 defined. If X i-1 = Π there is nothing to do. Suppose X i-1 Π. As Π is connected, there is some β in Π \ X i-1 , not orthogonal to an extremity of X i-1 . Then X i := X i-1 ∪ {β} is a connected subset of Π since so is X i-1 , whence the assertion. (ii) As X i is connected, a i is a simple algebra. For α in < X i >, g α is contained in a i ∩ p. Hence p i contains the Borel subalgebra of a i generated by h ∩ a i and g β , β ∈ X i , whence the assertion.

(iii) Let α be a positive root such that g α is contained in E. If α is in < X i > then g α and g -α are contained in E i . Otherwise, g α and g -α are contained in E X i by definition.

Let z be in E ∩h. By definition, h∩E X i is the orthogonal complement to a i in h. Then z = z 1 +z 2 with z 1 in a i ∩ h and z 2 in E X i . Hence z 1 is orthogonal to a i ∩ p. As a result, z 1 is in E i and z is in E i + E X i , whence the assertion.

We can now give the proof of Theorem 1.1.

Proof. Prove the theorem by induction on ℓ. First of all, for X empty subset of Π, V k,p X = k (g). For ℓ = 1, n = 1. Hence the theorem is true in this case and we can suppose X nonempty and ℓ ≥ 2. By Proposition 4.1 and Remark 4.2, V k = k (g) when X is connected. In particular, the theorem is true in rank 2. Then, by Proposition 4.10, the theorem is true for ℓ = 3 since in this case X contains all the extremities of Π when it is not connected.

Suppose ℓ > 3 and the theorem true for the simple algebras of rank smaller than ℓ. By induction hypothesis and Proposition 4.10, V k = k (g) when X contains all the extremities of Π. So, we can suppose that X does not contain all the extremities of Π. Let X 0 , . . . , X m be as in Lemma 4.11. For i = 0, . . . , m, set e i := | < X i > | and prove by induction on i the inclusion

e i j=0 j (a i ) ∧ k-j (E X i ) ⊂ V k .
For i = 0, . . . , n, denote by A i the connected closed subgroup of G whose Lie algebra is a i . By Lemma 4.11,(ii) and (iii),

V k,p = e i j=0 V j,p i ∧ k-j (E X i ),
for i = 0, . . . , m. Then, by Proposition 4.10, the induction hypothesis and Lemma 1.2, the inclusion is true for i = 0 since E X 0 is invariant under A 0 . Suppose i > 0 and the inclusion true for i -1. Let E ′ X i be the intersection of E X i-1 and a i . Denote by q i the parabolic subalgebra of a i containing b ∩ a i and such that a i-1 is the derived algebra of the reductive factor of q i containing h ∩ a i . Then

E X i-1 = E ′ X i ⊕ E X i , a i = a i-1 ⊕ E ′ X i , j (a i-1 ) ∧ k-j (E X i-1 ) = k-j l=0 j (a i-1 ) ∧ l (E ′ X i ) ∧ k-j-l (E X i-1 )
for j = 0, . . . , e i-1 . As a result,

e i-1 j=0 j (a i-1 ) ∧ k-j (E X i-1 ) = e i j=0 V j,q i ∧ k-j (E X i ).
By Proposition 4.1 and Remark 4.2, for j = 0, . . . , e i , the A i -submodule of j (a i ) generated by V j,q i is equal to j (a i ) since a i-1 is simple and ℓ a iℓ a i-1 = 1. Then, by Lemma 1.2, the A i -submodule of k (g) generated by

e i-1 j=0 j (a i-1 ) ∧ k-j (E X i-1 ) is equal to e i j=0 j (a i ) ∧ k-j (E X i )
since E X i is invariant under A i , whence the assertion and the theorem since for i = m the sum is equal to k (g).

If the left hand side is nonnegative then

s ≤ 1 6 (2ℓ -3 - √ 4ℓ 2 + 12ℓ + 9) or s ≥ 1 6 (2ℓ -3 + √ 4ℓ 2 + 12ℓ + 9).
The first inequality is impossible since its right hand side is negative. The first inequality is impossible since its right hand side is negative. The second inequality is impossible since

s ≤ ℓ -

  12ℓ -9) > ℓ -2, whence Assertion (ii) of Proposition A.1.A.3. Type D ℓ . As X is not connected, β is different from β 1 , β ℓ-1 , β ℓ . If β = β ℓ-2 then X has three connected components andd = ℓ(ℓ -1) -2 -1 2 (ℓ -3)(ℓ -2).In this case n < 2d. Suppose ℓ ≥ 5 and β = β s+1 for some s in {1, . . . , ℓ -4}.Thenn 1 = s(s + 1) 2 , n 2 = (ℓs -1)(ℓs -2), d = nn 1n 2 , n -2dn 1 = 5s 2s(4ℓ -7) + ℓ 2 -5ℓ + 4. If n -2dn 1 ≥ 0 then s ≤ 1 10 (8ℓ -13 -√ 24ℓ 2 -8ℓ + 9) or s ≥ 1 10 (8ℓ -13 + √ 24ℓ 2 -8ℓ + 9).As s ≥ 1, the first inequality is possible only if ℓ ≥ 8. The second inequality is impossible since its right hand side is bigger than ℓ -4 and s is at most ℓ -4. By the above equalities,n -2dn 2 = 2s 2 + (-2ℓ + 4)s -2ℓ + 2.If the left hand side is nonnegative thens ≤ -1 or s ≥ ℓ -1.These inequalities are impossible since s is positive and smaller than ℓ -3, whence Assertion (iii) of Proposition A.1.A.4. The exceptional case. Set l := l X , d := d X . Then 2d = dim gdim l. For each case, we give all the possible dimensions of l when |X| = ℓ -1.(a) The algebra g has type G 2 . Then X is connected, whence Assertion (iv) of Proposition A.1 for this case.(b) The algebra g has type F 4 . In this case n = 24 and dim l ∈ {12, 22} whence 2d ∈ {40, 30}and Assertion (iv) of Proposition A.1 for this case. (c) The algebra g has type E 6 . In this case n = 36 and dim l ∈ {20, 28, 36, 46} whence 2d ∈ {58, 50, 42, 32} and Assertion (iv) of Proposition A.1 for this case since d is simple of type D 5 when 2d = 32. (d) The algebra g has type E 7 . In this case n = 63 and dim l ∈ {27, 33, 39, 49, 67, 79} whence 2d ∈ {106, 100, 94, 84, 66, 54} and Assertion (iv) of Proposition A.1 for this case since d is simple of type E 6 when 2d = 54. (e) The algebra g has type E 8 . In this case n = 120 and dim l ∈ {36, 40, 52, 54, 64, 82, 92, 134} whence 2d ∈ {212, 208, 196, 194, 184, 166, 156, 114} and Assertion (iv) of Proposition A.1 for this case since d is simple of type E 7 when 2d = 114.

  The second inequality is possible only if ℓ ≥ 7 since s ≤ ℓ -2. Moreover, it is not possible to have n ≥ 2d + n 1 and Type B ℓ or C ℓ . As X is not connected, n = 2 and β = β s+1 for some s in {1, . . . , ℓ -2}.Thenn 1 = s(s + 1) 2 , n 2 = (ℓs -1) 2 , d = nn 1n 2 , + (-8ℓ + 9)s + 2ℓ 2 -8ℓ + 4).As s ≥ 1, the first inequality is possible only if ℓ ≥ 7. The second inequality is impossible since its right hand side is bigger than ℓ -2 and s is at most ℓ -2. By the above equalities, n -2dn 2 = 2s 2 + (-2ℓ + 5)s -4ℓ + 4.

	n ≥ 2d + n 2 since	1 6	(2ℓ -3 +	√ 4ℓ 2 + 12ℓ + 9) >	1 6	(4ℓ -3 -	√ 4ℓ 2 + 12ℓ + 9),
	whence Assertion (i) of Proposition A.1.
	A.2. n -2d -n 1 = (5s 2 If n -2d -n 1 ≥ 0 then 1 2 s ≤ 1 10 (8ℓ -9 -√ 24ℓ 2 + 16ℓ + 1) or s ≥	1 10	(8ℓ -9 +	√ 24ℓ 2 + 16ℓ + 1).
	If the left hand side is nonnegative then
	s ≤	1 4	(2ℓ -5 -	√ 4ℓ 2 + 12ℓ -7) or s ≥	1 4	(2ℓ -5 +	√ 4ℓ 2 + 12ℓ -9).

Then M m, j is a P u -submodule of m+| j| (g), M m, j,-is a P -,u -submodule of m+| j| (g), M ′ m, j is a P u -submodule of m+| j|+1 (g), M ′ m, j,-is a P -,u -submodule of m+| j|+1 (g). (i) By hypothesis, V k ⊃ l (p -,u ) ∧ M l ′ ,i ⊃ V l,l ′ ,i . Then by Proposition 3.5(i), d ∧ V l-1,l ′ ,i is contained in V k .

(ii) By hypothesis,

l ′ ,i and p -,u ∧V l,l ′ ,i are contained in V k,p . Moreover, for all nonnegative integer s such that l+l ′ + s+1 ≤ 2d and all j in ∆ i,|i|-s , p u ∧V l,l ′ +s, j , p -,u ∧V l,l ′ +s, j , p u ∧ V l+s,l ′ , j , p -,u ∧ V l+s,l ′ , j are contained in V k,p . Then, by Lemma 4.3,(i) and (ii),

, n. Suppose that one of the following condition is satisfied:

(1) Π is exceptional, (2) Π has type D ℓ and n = 3, (3) Π has classical type, n = 2, 2d + n 1 and 2d + n 2 are bigger than n.

As a result, by our previous remark, V k contains g ∧ V k-1,p , whence the proposition by Lemma 1.2 and the induction hypothesis.

4.4. The general case. First, we consider the case when X contains the extremities of Π.

Lemma 4.9. Suppose ℓ ≥ 2, n ≥ 2 and the extremities of Π contained in X. If |X| is smaller than ℓ -1 then for some β in Π \ X, Y := Π \ {β} has two connected components, X is contained in Y and a connected component of Y is a connected component of X.

Proof. Suppose |X| < ℓ -1. We consider the following cases:

(1) Π has not type D, E, (2) Π has type D ℓ , (3) Π has type E 6 , (4) Π has type E 7 , (5) Π has type E 8 .

(1) Let X 1 be the connected component of X containing β 1 . There is only one element β of Π \ X not orthogonal to X 1 . Then Y := Π \ {β} has two connected components and X 1 is a connected component of Y.

(2) Let X 1 be the connected component of X containing β 1 . As β ℓ and β ℓ-1 are in X, for some i smaller than ℓ -2, β i is not in X since |X| < ℓ -1. Then there is only one element β in Π \ X not orthogonal to X 1 so that Y := Π \ {β} has two connected components and X 1 is a connected component of Y.

(3) As β 1 , β 2 , β 6 are in X, β 3 or β 5 is not in X since |X| < ℓ -1. Setting Y i := Π \ {β i } for i = 3, 5, Y i has two connected components and for some i, X is contained in Y i and a connected component of X is a connected component of Y i .

(4) As β 1 , β 2 , β 7 are in X, β 3 or β 5 or β 6 is not in X since |X| < ℓ -1. Setting Y i := Π \ {β i } for i = 3, 5, 6, Y i has two connected components and for some i, X is contained in Y i and a connected component of X is a connected component of Y i .

(5) As β 1 , β 2 , β 8 are in X, β 3 or β 5 or β 6 or β 7 is not in X since |X| < ℓ -1. Setting Y i := Π \ {β i } for i = 3, 5, 6, 7, Y i has two connected components and for some i, X is contained in Y i and a connected component of X is a connected component of Y i . Proposition 4.10. Let k = 1, . . . , n. Suppose that Theorem 1.1 is true for the simple algebras of rank smaller than ℓ and X contains the extremities of Π. Then V k = k (g).

Proof. As X contains the extremities of Π and is different from Π, ℓ ≥ 3 and n ≥ 2. By Proposition 4.5, Remark 4.6 and Proposition 4.8, V k = k (g) when |X| = ℓ -1. In particular, V k = k (g) when ℓ = 3. Suppose ℓ > 3 and |X| < ℓ -1.

Appendix A. Some remarks on root systems Let β be in Π and X := Π \ {β}. Set p u := p u,X and d := dim p u,X . The goal of the section is the following proposition: Proposition A.1. (i) Suppose Π of type A ℓ and X not connected. Then β = β s+1 for some s in {1, . . . , ℓ -2},

(ii) Suppose Π of type B ℓ or C ℓ and X not connected. Then β = β s+1 for some s in {1, . . . , ℓ -2},

(iv) Suppose that Π is exceptional. If 2d ≤ n then X is connected.

We prove the proposition case by case. So, in the classical case, we suppose ℓ ≥ 3 and X not connected.

A.1. Type A ℓ . As X is not connected, n = 2 and β = β s+1 for some s in {1, . . . , ℓ -2}. Then

If n -2dn 1 ≥ 0 then s ≤ 1 6 (4ℓ -3 -√ 4ℓ 2 + 12ℓ + 9) or s ≥ 1 6 (4ℓ -3 + √ 4ℓ 2 + 12ℓ + 9).

As s ≥ 1, the first inequality is possible only if ℓ ≥ 6. The second inequality is impossible since its right hand side is bigger than ℓ -2 and s is at most ℓ -2. By the above equalities, n -2dn 2 = 3s 2 + (-2ℓ + 3)s -2ℓ.


Tanguy Kerdoncuff
email: tanguy.kerdoncuff@univ-st-etienne.fr

Rémi Emonet
email: remi.emonet@univ-st-etienne.fr

Marc Sebban
email: marc.sebban@univ-st-etienne.fr

Metric Learning in Optimal Transport for Domain Adaptation

Domain Adaptation aims at benefiting from a labeled dataset drawn from a source distribution to learn a model from examples generated according to a different but related target distribution. Creating a domain-invariant representation between the two source and target domains is the most widely technique used. A simple and robust way to perform this task consists in (i) representing the two domains by subspaces described by their respective eigenvectors and (ii) seeking a mapping function which aligns them. In this paper, we propose to use Optimal Transport (OT) and its associated Wasserstein distance to perform this alignment. While the idea of using OT in domain adaptation is not new, the original contribution of this paper is two-fold: (i) we derive a generalization bound on the target error involving several Wasserstein distances. This prompts us to optimize the ground metric of OT to reduce the target risk. (ii) From this theoretical analysis, we design an algorithm (MLOT) which optimizes a Mahalanobis distance leading to a transportation plan that adapts better. Experiments demonstrate the effectiveness of this original approach.

Introduction

Domain adaptation (DA) has been shown to be very effective in many real world applications, e.g., in computer vision, medical diagnosis, or recommender systems, to cite a few. The main idea is to use labeled data of a source domain to improve the performance of a classifier deployed on a related target domain which suffers from a lack of labeled examples. In this paper, we address a complex setting, called unsupervised DA, where there is only unlabeled data available from the target distribution.

Different approaches have been proposed to tackle this problem, some of them coming with theoretical guarantees (see, e.g. the survey [Redko et al., 2019b]). One classical way is to learn a common latent space where the distribution shift is smaller. For instance, the Subspace Alignment algorithm (SA) [START_REF] Fernando | [END_REF] learns a classifier in a subspace obtained after a linear alignment of the source and target eigenvectors. In a similar manner, the Correlation Alignment (CORAL) [Sun et al., 2016] uses the covariance of the source and target distributions to reduce the shift, while Transfer Component Analysis (TCA) [START_REF] Pan | [END_REF] looks for common features between the two domains. Some other works directly learn the target labels but do not gather the two distributions in a common feature space. This is the case of MEDA [Wang et al., 2018] which learns a domaininvariant classifier in Grassman manifold. On the other hand, DA with deep learning has received much attention during the past decade from the computer vision community leading to a substantial amount of research to address visual tasks for which a large amount of training data or a pre-trained model is available (see, e.g. the survey [START_REF] Wang | [END_REF]).

More recently, Optimal Transport (OT) has been shown to be a very promising tool to perform DA tasks. OT consists in mapping two source and target probability measures with a minimal cost of transportation associated to the socalled Wasserstein distance. Beyond its use in deep learning to solve visual DA tasks (see, e.g., [Sun and Saenko, 2016;[START_REF] Damodaran | [END_REF]), this idea of reducing the shift by OT has been exploited in a more generic DA setting by the algorithm OTDA [Courty et al., 2017b]. OTDA modifies the original Kantorovich optimization problem by resorting to a regularization preventing the transportation plan from moving two source points of different labels onto the same target example. Then, a classifier can be learned from the labeled source data and deployed over the target distribution. Based on this work, [Courty et al., 2017a] ensures that the final classifier is coherent with the transportation plan.

Inspired from both SA and OTDA, our contribution aims at using OT for domain adaptation by aligning the source and target subspaces. The main conjecture we formulate in this paper is that the Euclidean distance usually used as the cost matrix in OT may not be the best metric to perform the adaptation. While learning a better metric (especially a Mahalanobis distance) in OT has been recently studied [START_REF] Deshpande | [END_REF][START_REF] Genevay | [END_REF][START_REF] Paty | Franc ¸ois-Pierre Paty and Marco Cuturi[END_REF]Cuturi and Avis, 2014], optimizing such a ground metric to address DA tasks has not receive attention yet. We fill this gap from both a theoretical and an algorithmic perspective. First, we formally establish a relation between the target error and the magnitude of different Wasserstein distances. This prompts us to see the Wasserstein distance as a parameterized metric that might be minimized, leading to a better transportation plan for DA. We also formally make a link between a PCA and the minimization of the Wasserstein distance. Based on this theoretical analysis, we propose MLOT, an algorithm which optimizes a Mahalanobis distance that improves the Optimal Transport between the source and target subspaces generated by a PCA. Unlike OTDA which does not change the feature space, MLOT jointly optimizes (i) the dimensionality reduction of the source domain, (ii) the transportation plan between the source and the target and (iii) the underlying metric used in the transportation. The intuition behind MLOT is illustrated in Figure 1. The original source and target examples are represented on the left. The second figure shows the limitation of OTDA when the transportation is performed in the original feature space. The figure on the right gives evidence on the advantage of performing a PCA before learning jointly the ground metric and the transportation plan.

The rest of the paper is organized as follows: Section 2 reminds the main principles of OT, DA and Metric Learning. Section 3 is dedicated to the theoretical contribution of our paper which leads to the design of our MLOT algorithm in Section 4. An extensive experimental study is presented in Section 5 before our conclusion in Section 6.

Optimal Transport and Metric Learning

In this section, we briefly introduce Optimal Transport, its use in OTDA, and Metric Learning.

Optimal Transport and OTDA

Let X ⊆ R n be a feature space. We consider here a source distribution µ s and a target distribution µ t both defined over X . OT [START_REF] Villani | Optimal transport: old and new[END_REF] aims at moving µ s on the top of µ t with a transportation plan of minimal cost. We will use in this paper the formulation proposed by Kantorovich [1942] which gives the Wasserstein distance between µ s and µ t . Let Π(µ s , µ t ) be the collection of all joint probability measures on X ×X with marginals µ s and µ t respectively. Let suppose that µ s and µ t have a finite p-order moment with p ≥ 1. One can define the p-Wasserstein distance at the power p as

W p p (µ s , µ t ) = min γ∈Π(µs,µt) X ×X c(x s , x t ) p dγ(x s , x t ), (1)
where c : X × X → R is a cost function. The minimizer of the previous problem γ * corresponds to the Optimal Transport plan. In practice, we deal with the empirical measures μs and μt supported on m s and m t examples respectively. In such a case, γ * can be represented by a matrix of size m s × m t where γ * i,j corresponds to the mass that should be sent from the point x i s to the point

x j t . Let Π(μ s , μt ) = {γ ∈ R ms×mt + |γ1 mt = μs , γ T 1 ms = μt }.
Considering the Euclidean distance as the cost function, we denote by C p the m s × m t matrix composed of the costs

C p ij = x i s -x j t p 2 .
The p-Wasserstein distance can be reformulated as follows:

W p p (μ s , μt ) = min γ∈ Π(μs,μt) ms i=1 mt j=1 x i s -x j t p 2 γ ij = min γ∈ Π(μs,μt) γ, C p .
(2)

It is worth noting that (i) Problem ( 2) is a linear program, (ii) the solution is not stable and (iii) the algorithmic complexity is supercubic. To change it into a strongly convex problem with a unique solution, we usually add a regularization term in the form of the classic Shannon entropy [Cuturi, 2013]. Let λ e ∈ R + be a small regularization parameter, we get

W p p (μ s , μt ) ≈ argmin γ∈ Π(μs,μt) γ, C p -λ e Ω e (γ), C p , (3)
with Ω e (γ) = - 3) can be efficiently solved by resorting to the Sinkhorn-Knopp algorithm [Cuturi, 2013]. The mass of a source point will now be spread across several target points preventing the algorithm from overfitting and leading to smoother solutions.

ms i=1 mt j=1 γ ij log(γ ij ). Problem (
OTDA (Optimal Transport for Domain Adaptation) [Courty et al., 2017b] was the first attempt to use Optimal Transport for Domain Adaptation. While Problem (3) is totally unsupervised, OTDA takes into account the labels of the transported points. Let us suppose that a discrete label y s ∈ Y = 1, c is associated to each source example, with c the number of classes. OTDA adds a penalty term to prevent two source points of different labels from being sent to the same target location. This takes the form of the following optimization problem:

min γ∈ Π(μs,μt) γ, C p -λ e Ω e (γ) + λ c Ω c (γ), (4)
where Ω c (γ) = mt j=1 c cl=1 γ(I cl , j) 2 and γ(I cl , j) is the column j of matrix γ with only the rows corresponding to samples of class cl.

Metric Learning

As said before, the cost matrix C used in OT is usually set to the Euclidean distance. Though this choice seems natural, it has a direct impact on the quality of the transportation. We suggest here to optimize this matrix by learning a metric that allows us to better match in a DA setting the source and target distributions, hopefully in a smaller feature space. Metric Learning (ML), and especially Mahalanobis distance learning, has been widely studied in the literature during the past decade (see, e.g., the survey [START_REF] Bellet | [END_REF]). It typically boils down to optimizing the shape and the orientation of an ellipsoid rather than using the Euclidean ball. More formally, let L ∈ R k×n with k ∈ 1, n and M be a PSD matrix such as

M = L T L. For all (i, j) ∈ 1, m s 2 , the squared Maha- lanobis distance D 2 M parameterized by M is defined as D 2 M (x i s , x j s ) = (x i s -x j s ) T M (x i s -x j s ) = L(x i s -x j s ) 2 2 .
(5) Notice that L defines a unique M but there is more than one Cholesky decomposition of M . The goal of Metric Learning is to learn either the matrix L or M under semantic constraints, which typically aim to bring closer examples of the same class while pushing away data of different labels (see, e.g. LMNN [START_REF] Weinberger | [END_REF] or ITML [START_REF] Davis | [END_REF]). The problem is often convex in M but the PSD constraint makes the optimization more complicated. The minimization in L is not convex but is simpler and gives good results in practice. In the rest of this paper, we will denote by Ω l (L) the underlying objective function of the metric learning problem. Note that learning a Mahalanobis distance for OT has been recently studied [START_REF] Deshpande | [END_REF][START_REF] Genevay | [END_REF][START_REF] Paty | Franc ¸ois-Pierre Paty and Marco Cuturi[END_REF]Cuturi and Avis, 2014]. Our objective in the rest of this paper is to show how to optimize such a ground metric when OT is used to address domain adaptation tasks by the alignment of the source and target subspaces.

Theoretical Analysis of DA with OT

In this section, we derive two theoretical results. First, we establish a strong relation between a PCA and the minimization of the Wasserstein distance. Then, we derive a generalization bound on the target error whose terms depend on several Wasserstein distances. By changing the Euclidean costs by a Mahalanobis distance, we can see W p p (μ s , μt ) as a parameterized distance that might be optimized from training data. This leads to the design of a new Domain Adaptation algorithm, called MLOT (see Section 4), which learns the ground metric allowing us to optimize the transportation plan while performing the adaptation.

μ g # μ P CA(μ) ⇐⇒ min g W(μ, g # μ)
Figure 2: Standard PCA projecting a discrete distribution μ (data in orange) onto a one-dimensional subspace (in purple). This projection is equivalent to finding the optimal mapping function g that minimizes the Wasserstein distance W(μ, g # μ).

PCA and Wasserstein Distance

As usually done in OT, let us use the push forward notation.

For any measurable function g : X -→ X and distribution µ on X , we define g # µ(B) = µ(g -1 (B)) for all Borel B ∈ B(X ). In practice, this means that we draw a point from µ and then apply the transformation g to that point. If g is a linear function, it can be assimilated to its associated matrix G. Let Dim(Im(g)) be the dimension of the affine subspace formed by the image of g. This notation allows us to define the dimension of a non-centered vector space.

The following theorem aims at showing that PCA is the best way to reduce the dimension of a distribution in the sense of the Wasserstein distance. By dimensionality reduction, we mean that the transformed distribution lays in a subspace (not necessarily centered) of X , but the points are still defined in X (see Figure 2). For the sake of clarity, we consider here the case of the 2-Wasserstein with the Euclidean distance as the underlying distance. We also focus on the case of a discrete centered distribution. The complete derivation for the more general case can be proved in a similar way.

g∈G d W 2 2 (μ, g # μ) = V T V. (6)
Proof. Suppose that the minimizer g * ∈ G d of Problem (6) exists. In such a case, let γ g * be the associated optimal coupling matrix. With these notations, we get:

min g∈G d W 2 2 (μ, g # μ) = i,j x i -g * (x j ) 2 2 (γ g * ) i,j . (7)
To get rid of the last term of Eq. ( 7), let us reorder the function g * into g * (x i ) = g * (x j ) when (γ g * ) i,j = 1 m . In this case, the corresponding matrix γ g * = 1 m I m with I m the identity matrix, and we get:

min g∈G d W 2 2 (μ, g # μ) = i,j x i -g * (x j ) 2 2 (γ g * ) i,j min g∈G d W 2 2 (μ, g # μ) = 1 m i x i -g * (x i ) 2 2 ≥ 1 m i x i -V T V x i 2 2 .
The last line comes from the PCA. It shows that V T V associated with 1 m I m upper bounds the optimal solution g * . But since V T V ∈ G d , it is actually the optimal solution.

Theorem 1 tells us that PCA is the best way to reduce the dimension in the sense of the Wasserstein distance. The next result provides a generalization bound on the target error where Wasserstein distances are the main terms to minimize.

Upper Bound on the Target Risk

Let H = {h|h : X → Y} be the hypothesis space. We assume the existence of a deterministic ground-truth function f : X → Y which gives the label associated to each point of X . For all (h, h ) ∈ H 2 , we define t (h, h

) = P x∼µt (h(x) = h (x)) and s (h, h ) = P x∼µs (h(x) = h (x))
which represent the disagreement between two classifiers. The goal of DA is to find the best h ∈ H which minimizes the target risk t (h, f ) = P x∼µt (h(x) = f (x)). In the same way, s (h, f ) = P x∼µs (h(x) = f (x)) is the source risk. To simplify the notations, let us use t (h, f ) = t (h) and s (h, f ) = s (h). Lemma 1 (Generalization bound [START_REF] Shen | [END_REF]). Let µ s , µ t be two probability measures on X . Assume the hypotheses h ∈ H are all K-Lipschitz continuous for some K ∈ R * + . Then, ∀(h, h) ∈ H 2 , the following holds: t (h, h ) ≤ s (h, h ) + 2KW 2 (µ s , µ t ).

(8) Building on the proof of [START_REF] Redko | Theoretical analysis of domain adaptation with optimal transport[END_REF] based on the seminal works of Ben-David et al. [2007] and Mansour et al. [2009], we derive the following bound. Theorem 2. Let g s : X -→ X and g t : X -→ X . Under the assumption of Lemma 1, ∀h ∈ H, the following holds:

t (h) ≤ s (h) + 2K [W 2 (g s# μs , g t# μt )] + 2K [W 2 (μ s , g s# μs ) + W 2 (g t# μt , μt )] + 2K [W 2 (µ s , μs ) + W 2 (μ t , µ t )] + λ (9)
where λ is the combined error of the ideal hypothesis h * that minimizes the combined error s (h * ) + t (h * ).

Proof. We have :

t (h) ≤ t (h * ) + t (h * , h) = t (h * ) + s (h, h * ) + t (h * , h) -s (h, h * ) ≤ t (h * ) + s (h, h * ) + 2KW 2 (µ s , µ t ) ≤ t (h * ) + s (h) + s (h * ) + 2K [W 2 (µ s , μs ) + W 2 (μ s , µ t )] ≤ s (h) + λ + 2K [W 2 (µ s , μs ) + W 2 (μ s , μt ) + W 2 (μ t , µ t )] ≤ s (h) + 2K [W 2 (g s# μs , g t# μt )] + 2K [W 2 (μ s , g s# μs ) + W 2 (g t# μt , μt )] + 2K [W 2 (µ s , μs ) + W 2 (μ t , µ t )] + λ. Algorithm 1 MLOT Input: η (gradient step) X s X t Y s 1: V s = P CA(X s ), V t = P CA(X t ) 2: L s = V T s V s , L t = V T t V t 3: for i = 1 to N do 4: γ = argmin γ∈ Π(μs,μt) γ, C 2 (L s , L t ) -λ e Ω e (γ)+λ c Ω cl (γ) 5: L s = L s -η∇ Ls ( γ, C 2 (L s , L t ) +λ l Ω l (L s ))
6: end for 7: Xs = γL t X t 8: classifier = classifier method( Xs , Y s ) 9: Ŷt = classifier(X t ) 10: return Ŷt Note that if g s and g t are linear, g s# μs and g t# μt can be seen as linear projections of the source and target examples taking the form of two matrices that can be learned by any standard metric learning algorithm. Therefore, rather than discussing about its tightness, it is worth noticing that the previous bound is the first one which jointly relates (i) the target risk in domain adaptation, (ii) the minimization of the Wasserstein distance and (iii) the metrics that can be learned to get a better transportation plan. We can use Theorem 1 to minimize both W 2 (μ s , g s# μs ) and W 2 (g t# μt , μt ). Note that W 2 (µ s , μs ) and W 2 (μ t , µ t ) can be bounded under some assumptions using Theorem 2.1 in [START_REF] Bolley | [END_REF]. Moreover, λ is supposed to be small to allow the adaptation. A theoretical analysis about λ is available in [Redko et al., 2019a].

The last term of interest that has to be minimized in the bound of Theorem 2 is W 2 (g s# μs , g t# μt ). We address this problem from an algorithmic perspective thanks to our algorithm MLOT presented in the next Section.

MLOT: Metric Learning in OT for DA

Inspired from OTDA [Courty et al., 2017b], our algorithm MLOT leverages our previous theoretical analysis and resorts to an additional term Ω l (L s ) dedicated to optimize a metric allowing us to get a better transportation plan. Let us consider the cost function

C 2 (L s , L t ) ij = L s x i s -L t x j t 2
2 . MLOT takes the form of the following joint optimization problem:

min Ls∈R n×n ,γ∈ Π(μs,μt) γ, C 2 (L s , L t ) -λ e Ω e (γ) + λ c Ω cl (γ) + λ l Ω l (L s ).
(10) Note that MLOT only learns the matrix L s associated to the source data. The reason is twofold. First, it prevents the algorithm from leading to a trivial minimal solution W 2 (L s# μs , L t# μt ) where both matrices L s and L t are null. By this way, MLOT tends to provide two different matrices L s (which is learned) and L t (set to V T t V t according to Theorem 1) which better capture the peculiarities of the two distributions. Second, labels -that are required to learn a metric -are available only in the source domain. To find the solution of Problem (10), we minimize the objective function w.r.t. γ and L s alternately. From a practical point of view, we apply one step of gradient descent over L s and then completely compute the optimal γ. Since the problem is not convex, the initialization of L s is key. According to Theorem 1, we use a PCA to set L s = V T s V s . At the initialization, L s is a n × n matrix of rank d. But note that along the iterations, this rank can increase if it allows a better adaptation. The pseudo-code of MLOT is described in Algo. 1, where X s and X t are the source and target datasets, and Y s is the set of source labels.

µ s µ t X s X t L s X s L t X t Samples Samples ML with PCA PCA Optimal Transport
Note that any gradient descent-based metric learnign algorithm can be used to learn L s via the term λ l Ω l (L s ). Note also that the computation of the barycenter of the transported points Xs = γL t X t makes sense only if the 2-Wasserstein is used. Figure 3 summarizes the workflow of MLOT.

Experiments

In this section, we perform experiments and demonstrate the effectiveness of MLOT compared to OTDA and other baselines on various datasets and types of features.

Datasets

We use the Office-Caltech dataset [START_REF] Gong | [END_REF] which is a classic benchmark on visual DA. We study the effect of using different features such as SURF features [Bay et al., 2006] and DeCAF Deep Learning features [START_REF] Donahue | [END_REF]. The Office-Caltech dataset is composed of 4 different subsets (Amazon, Caltech, DSRL, Webcam) that are combined in a pairwise manner, to create 12 DA subproblems. The notation A → C means that Amazon is used as the source and Caltech as the target. There are the same 10 classes in each dataset containing from 157 to 1,123 images.

We also use the Office31 dataset [START_REF] Saenko | [END_REF] with features extracted from the 7 th layer of DeCAF Deep Learning network. The dataset is composed of 4,110 images in 3 subsets (Amazon, DSLR, Webcam) with 31 classes.

Setup and Cross-validation

We compare 10 different methods1 that are able to handle arbirtary features. We exclude deep learning methods as they require having the original images and fine tuning a network. We compare: NA(No Adaptation). The classifier is learned on the source dataset and directly applied on the target. LMNN: Large Margin Nearest Neighbor [START_REF] Weinberger | [END_REF]. SA: Subspace Alignment [START_REF] Fernando | [END_REF]. CORAL: CORrelation ALignment [Sun et al., 2016]. TCA: Transfer Component Analysis [START_REF] Pan | [END_REF]. OT:

Optimal Transport with entropy [Cuturi, 2013]. OTDA: Optimal Transport with entropy and class regularization [Courty et al., 2017b]. OTDA p : OTDA after a PCA. JDOT: Joint Distribution Optimal Transportation [Courty et al., 2017a]. MLOT: our method. Following [Courty et al., 2017b] the final classification is done with a 1-Nearest Neighbor (1NN).

In unsupervised DA, there is no target label and it is impossible to use the classical cross-validation procedure to choose the best hyper-parameters. To fairly compare methods, we take inspiration from the work of [Zhong et al., 2010] and apply the following strategy for all methods. We first assign pseudo-labels to the target points (using the considered method) and then use these target labels to re-assign labels to the source data, using a basis DA algorithm. Here, we choose SA [START_REF] Fernando | [END_REF] which has been shown to be one of the most robust DA method. We can then compare the actual source labels with the predicted source ones. We take the set of hyper-parameters that gives the best accuracy over 48 hours, limited to 1000 iterations. This back-and-forth adaptation is done independently for each pair of datasets. MLOT is parameterized by 5 hyper-parameters: the three regularization parameters (λ e , λ c , λ l ) which control the trade-off between each term in Eq. ( 10), the number of dimensions kept by the PCA (d) and the number of iterations (N ). Note that in these experiments, we used arbitrarily LMNN [START_REF] Weinberger | [END_REF]] to learn L s in the term Ω l (L s ). Therefore, an additional parameter has to be tuned corresponding to the margin used in this metric learning algorithm. Note that SA and MLOT resort to a PCA. To speed-up the process, we used a "randomized"-PCA [START_REF] Halko | [END_REF] and run 10 iterations. This explains why the variance is indicated for these three methods in the reported results in Table 1.

The code of the 10 methods is available2 , together with the datasets, the code for the cross-validation that recreates Table 1, and the code that produces automatically Figures 1 and4.

Analysis of the Results

The results are reported in Table 1. For the SURF features, MLOT outperforms, on average, all the other methods. MLOT outperforms OTDA 8 times over the 12 DA subproblems and yields impressive improvements for some cases (e.g. W -→ A and C -→ D) and a clear gain on average (1.5 points). The results on Office-Caltech DeCAF6 features show the effectiveness of our method on deep learning features. MLOT outperforms by 1.8 the second best method (here OT). On the Office31 dataset, the best results are obtained by SA. MLOT is still very competitive and outperforms OTDA by 0.9 point on average.

As already mentioned, cross-validating the hyperparameters in unsupervised DA is key and is still an open problem, since we do not have access to labels from the target domain. We performed an experimental comparison to show how the cross-validation method used in this paper behaves when compared to a scenario where we would use the actual labels of the target examples. Table 2 reports the gap between the optimal hyperparameters and those obtained by our method inspired from [Zhong et al., 2010]. We can see Table 2: Accuracy comparison on Office-Caltech (SURF features) between a cross-validation method that uses the true target labels (first line) and the cross-validation method used in this paper that exploits pseudo-labels in the unsupervised DA setting (second line). CORAL and NA are excluded as they do not have hyperparameter. that the ranking of the methods is preserved, even though this experiment shows that there is still room for improving the way we may tune the parameters in unsupervised DA. Note that the other datasets show similar behaviors. To show the specific gain brought by MLOT compared to OTDA, we performed a last experiment where we set the hyper-parameters of MLOT as follows: λ l = 1, N = 10, margin LM N N = 10, d = 70; and we tune λ e and λ c . The results are reported in Figure 4. It is worth noticing that whatever the set of parameters, MLOT always yields better accuracy, which confirms the interest of learning a metric and using the PCA to initialize L s and L t . Note that when the entropy term has more impor-tance (last column), the difference between the two methods is smaller because γ tends to be uniform. When the class regularization is set to 0 (first row), OTDA becomes similar to OT (Sinkhorn algorithm). This shows the effectiveness of MLOT even without the class regularization. However, the performances drop without this supervised information which tends to show that the metric learned and the class regularization are complementary. Notice that the results of MLOT are quite good for many values of the entropy and class regularizations (Figure 4 on the right). The best performance is 50.9 which is better than the result obtained by the cross-validation method. Once again, this is an evidence about the difficulty of tuning parameters in unsupervised DA.

Conclusion

We proposed in this paper a new Domain Adaptation (DA) method, called MLOT, benefiting from both Metric Learning (ML) and Optimal Transport (OT). Dedicated to address problems in the complex unsupervised DA setting, MLOT jointly learns a good metric and the optimal transportation plan. A theoretical study has driven the design of MLOT. We derived a bound on the target error which prompts us to learn the ground metric involved in the Wasserstein distance. The experimental study has shown very competitive results and a significant improvement compared to OTDA, the first method coupling OT and DA. Although deep learning is not at the core of this paper, note that we designed a differentiable version of MLOT using the PyTorch framework. While the first results, with pre-extracted features, did not bring any performance boost, this implementations opens the door to a full end-to-end model for Wasserstein-based domain adaptation.

Figure 1 :

 1 Figure1: Behavior of MLOT on a toy dataset. On the left, the original source and target examples. In the middle, OTDA fails to transport correctly the blue and red classes. On the right, the proposed MLOT which combines a learned metric and some per-domain dimensionality reduction, leads to a perfect transportation plan. Notice the difference in scale between the two axes.

  Theorem 1. Given a set of m examples {x i } m i=1 lying in a n dimensional space and i.i.d. from a distribution µ. Let μ the empirical counterpart of µ defined as μ = 1 m m i=1 δ x i with E(μ) = 0. Let d ∈ 1, n and V be the d × n matrix formed with the first d normalized eigenvectors of the covariance matrix of μ. Let G d = {g : R n -→ R n |Dim(Im(g)) ≤ d}. Then, we have argmin

Figure 3 :

 3 Figure 3: Workflow of MLOT.

Figure 4 :

 4 Figure 4: Absolute difference between the mean accuracy of MLOT and OTDA (on the left). The rows (resp. columns) correspond to the results with different values of the regularization parameter λc (resp. λe) on the entire Office-Caltech dataset with SURF features. On the right, accuracy of MLOT for each pair of parameters.

Table 1 :

 1 Accuracy of all the methods on 3 different types of features. The best method for each dataset is in bold.

		Dataset	NA	LMNN	SA	CORAL TCA	OT	OTDA	OTDAp	JDOT	MLOT
		A→C	26.0		40.3	40.2±0.2	25.4	40.0 33.9	40.2	39.4±0.5	39.9	42.3±0.6
		A→D	25.5		36.9	39.3±2.5	26.8	31.8 30.6	40.1	39.6±1.1	37.6	40.8±0.8
		A→W 29.8		38.0	39.9±1.3	26.8	41.7 32.5	37.3	39.8±0.9	38.0	41.3±1.1
		C→A	23.7		46.0	41.3±1.1	23.6	39.8 41.0	52.7	48.5±0.7	48.1	51.5±0.8
		C→D	25.5		45.9	45.4±1.2	26.1	44.6 36.9	47.8	51.4±1.4	49.7	52.2±1.3
	SURF	C→W	25.8		41.7	36.6±1.1	23.7	36.9 28.1	46.4	45.8±1.4	43.4	45.9±0.8
		D→A	28.5		31.1	35.4±1.0	28.8	32.9 29.3	32.4	37.8±1.0	32.8	37.8±0.7
		D→C	26.3		30.7	32.3±0.6	30.0	31.5 31.7	32.0	33.5±0.7	31.7	34.4±0.5
		D→W 63.4		77.3	88.5±1.1	84.4	84.7 88.8	88.8	87.5±1.2	82.7	87.8±0.7
		W→A 23.0		32.3	32.6±0.5	26.2	29.4 34.1	33.7	37.6±0.6	37.6	38.0±0.8
		W→C	19.9		30.4	29.0±0.6	22.6	29.2 30.1	34.1	33.3±0.5	33.1	33.2±0.6
		W→D 59.2		86.6	89.5±1.0	84.1	91.7 89.2	92.4	91.8±1.2	89.8	90.8±0.8
		AVG		31.4		44.8	45.8±1.0	35.7	44.5 42.2	48.2	48.8±0.9	47.0	49.7±0.8
	DeCAF6	AVG		71.0		79.4	83.7±0.5	77.2	83.4 83.9	83.2	82.6±0.5	78.2	84.7±0.3
	Office31	AVG		64.3		64.7	66.5±0.2	64.1	64.1 65.3	65.3	65.2±0.1	64.4	66.2±0.1
	All datasets	AVG		53.8		62.6	65.1 ± 0.6	58.0	64.0 63.5	65.6	65.6 ± 0.6	63.0	67.0 ± 0.5
	OT TCA LMNN SA JDOT OTDA OTDAp MLOT
	45.3 45.3	47.9	47.4 48.5	52.8	54	55.1
	42.2 44.5	44.8	45.8 47.0	48.2	48.8	49.7

Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence

We could not run MEDA[Wang et al.,

2018] because the implementation requires the use of a proprietary software.

https://github.com/Hv0nnus/MLOT Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence

Acknowledgements

This paper is part of the TADALoT Project funded by the region Auvergne-Rhône-Alpes (France) with the Pack Ambition Recherche (2017, 17 011047 01).