Christina Boura
email: christina.boura@inria.fr

Anne Canteaut
email: anne.canteaut@inria.fr

Christophe De Cannière
email: christophe.decanniere@esat.kuleuven.be

Higher-order

Keywords: Hash functions, degree, higher-order differentials, zero-sums, SHA-3

come

Introduction

The algebraic degrees of some hash function proposals and of their building blocks have been studied for analyzing their security. In particular, the fact that some inner primitive in a hash function has a relatively low degree can often be used to construct higher-order differential distinguishers, or zero-sum structures. This direction has been investigated in [START_REF] Aumasson | Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi[END_REF][START_REF] Watanabe | Higher Order Differential Attack on Step-Reduced Variants of Luffa v1[END_REF][START_REF] Boura | Zero-sum Distinguishers for Iterated Permutations and Application to Keccak-f and Hamsi-256[END_REF] for three SHA-3 candidates, Luffa, Hamsi and Keccak. Here, we show how to deduce a new bound for the degree of iterated permutations for a special category of SP-networks. This category includes functions that have for non-linear layer, a number of smaller balanced Sboxes. This class of functions is though quite general: it includes functions with a large number of small Sboxes (e.g. Sboxes operating on 3 or 4 bits), but it also includes any nonlinear permutation which can be decomposed as several independent Sboxes, even of large size. Our new bound shows in particular that, when it is iterated, the degree of the function grows in a much smoother way than expected when it approaches the number of variables.

For instance, this new bound enables us to find zero-sum partitions for the full inner permutations of the hash functions Keccak [START_REF] Bertoni | Keccak sponge function family main document[END_REF] and for the Luffa v1 hash function [START_REF] De Cannière | Hash Function Luffa: Specification[END_REF]. Furthermore, by applying a technique similar to that used in [START_REF] Watanabe | Higher Order Differential Attack on Step-Reduced Variants of Luffa v1[END_REF], and by combining it with the results given by the new bound, we show that the degree of the Luffa v2 compression function [START_REF] De Cannière | Hash Function Luffa: Specification[END_REF] is slightly lower than expected. This also enables us to find distinguishers for the Q j permutations and for the compression function of Luffa v2. These results do not seem to affect the security of Luffa v2, but are another confirmation of the fact that the internal components of Luffa do not behave as ideal random functions.

The rest of the paper is organized as follows. In Section 2, a new bound on the degree of iterated permutations is presented when the nonlinear layer consists of several parallel applications of smaller balanced Sboxes. Section 3 recalls how a low algebraic degree can be exploited for mounting higher-order differential distinguishers and zero-sum distinguishers. An application to the full Keccak-f permutation is presented in Section 4, while applications to the Luffa hash family are described in Section 5.

2 A new bound on the degree of some iterated permutations

In the whole paper, the addition in F n 2 , i.e. the bitwise exclusive-or will be denoted by +, while ⊕ will be used for denoting the direct sum of subspaces of F n 2 . A Boolean function f of n variables is a function from F n 2 into F 2 . It can be expressed as a polynomial, called algebraic normal form. The degree of f , denoted by deg(f ), is the degree of its algebraic normal form. Moreover, the degree of a vectorial function F from F n 2 into F m 2 is defined as the highest degree of its coordinates. The Hamming weight of a Boolean function, f , is denoted by wt(f ). It corresponds to the number of x such that f (x) = 1. Any function

F from F n 2 into F m 2 is said to be balanced if each element in F m 2 has exactly 2 n-m preimages under F .
In this paper, we are interested in estimating the degree of a composed function G • F . Obviously, we can bound the degree of the composition

G • F by deg(G • F ) ≤ deg(G)deg(F ).
Though, this trivial bound is often very little representative of the true degree of the permutation, in particular if we are trying to estimate the degree after a high number of rounds. A first improvement of the trivial bound was provided by Canteaut and Videau [START_REF] Canteaut | Degree of composition of highly nonlinear functions and applications to higher order differential cryptanalysis[END_REF] when the values occurring in the Walsh spectrum of F are divisible by a high power of 2, i.e. if the values wt(ϕ b • F + ϕ a ) for all a ∈ F n 2 and b ∈ F m 2 are divisible by a high power of 2, where ϕ a denotes the linear function x → a • x. Theorem 1. [START_REF] Canteaut | Degree of composition of highly nonlinear functions and applications to higher order differential cryptanalysis[END_REF] Let F be a function from

F n 2 into F n 2 such that all values wt(ϕ b • F + ϕ a ), a, b ∈ F n 2 , b = 0
are divisible by 2 ℓ , for some integer ℓ. Then, for any G :

F n 2 → F n 2 , we have deg(G • F ) ≤ n -1 -ℓ + deg(G).
In particular, this result applies to the functions composed of a nonlinear layer followed by a linear permutation, where the nonlinear layer is defined by the concatenation of m smaller balanced Sboxes S 1 , . . . , S m , defined over F n 0 2 , n 0 ≥ 2. Indeed, since all elements wt(ϕ b • S i + ϕ a ) for all smaller functions S 1 , . . . , S m are divisible by 2, then we deduce that, for the whole permutation, wt(ϕ b • F + ϕ a ) is divisible by 2 2m-1 . We will show here how this bound can be further improved in this particular case. The result mainly comes from the following observation.

Proposition 1. Let F be a balanced function from F n 2 into F m 2 , and let k be an integer with 1 ≤ k ≤ m. Then, all products of k coordinates of F have the Hamming weight 2 n-k .

In particular, if k < n, the product of any k coordinates of F has degree at most (n -1).

Proof. Let (f 1 , . . . , f m ) denote the coordinates of F . Let I be any subset of {1, . . . , m} of size k, and let F I be the function from F n 2 into F k 2 whose coordinates are the f i , i ∈ I. Since F I is balanced, the multiset {F I (x), x ∈ F n 2 } consists of all elements in F k 2 , each one with multiplicity 2 n-k . Therefore, there exist exactly 2 n-k values of x such that F I (x) is the all-one vector, or equivalently such that i∈I f i = 1.

From the last part of Proposition 1, we deduce the following theorem.

Theorem 2. Let F be a function from F n 2 into F n 2 corresponding to the concatenation of m smaller Sboxes, S 1 , . . . , S m , defined over F n 0 2 . Let δ k be the maximal degree of the product of any k coordinates of anyone of these smaller Sboxes. Then, for any function

G from F n 2 into F ℓ 2 , we have deg(G • F ) ≤ n - n -deg(G) γ , (1)
where γ = max

1≤i≤n 0 -1 n 0 -i n 0 -δ i .
Most notably, if all Sboxes are balanced, we have

deg(G • F ) ≤ n - n -deg(G) n 0 -1 .
Moreover, if n 0 ≥ 3 and all Sboxes are balanced functions of degree at most n 0 -2, we have

deg(G • F ) ≤ n - n -deg(G) n 0 -2 ,
Proof. Let us denote by π the product of d output coordinates of F . Some of the coordinates involved in π may belong to the same Sbox. Then, for any i, 1 ≤ i ≤ n 0 , we denote by x i the integer corresponding to the number of Sboxes for which exactly i coordinates are involved in π. Obviously, we have

deg(π) ≤ max (x 1 ,...,xn 0 ) n 0 i=1 δ i x i
where the maximum is taken over all vectors (x 1 , . . . , x n 0 ) satisfying

n 0 i=1 ix i = d and n 0 i=1 x i ≤ m .
Then, we have

γ deg(π) -d ≤ γ n 0 i=1 δ i x i - n 0 i=1 ix i ≤ (γ -1)n 0 x n 0 + n 0 -1 i=1 (γδ i -i)x i ≤ (γ -1)n 0 n 0 i=1 x i - n 0 -1 i=1 ((γ -1)n 0 -γδ i + i)x i ≤ (γ -1)n - n 0 -1 i=1 ((γ -1)n 0 -γδ i + i)x i ≤ (γ -1)n ,
where the last inequality comes from the fact that all coefficients in the sum are positive. Actually, we have (γ -1)n 0 -

γδ i + i = γ(n 0 -δ i ) -(n 0 -i) ≥ 0
by definition of γ. Thus, since γ deg(π) -d ≤ (γ -1)n, we deduce that

γ (n -deg(π)) ≥ n -d .
Now, we first show that, if all Sboxes are balanced, then γ ≤ n 0 -1. Indeed, for any 1

≤ i ≤ n 0 -1, we have n 0 -i n 0 -δ i ≤ n 0 -1 1 ,
since we know from Proposition 1 that the degree of the product of (n 0 -1) coordinates of a balanced n 0 × n 0 Sbox cannot be equal to n 0 , and thus δ i ≤ n 0 -1. Also, we can prove that, if the degrees of all Sboxes satisfy deg S < n 0 -1, then γ ≤ n 0 -2. Indeed, for i = 1, we have

n 0 -i n 0 -δ i = n 0 -1 n 0 -δ 1 ≤ n 0 -1 2 ≤ n 0 -2 since n 0 ≥ 3. Similarly, for any i, 2 ≤ i < n 0 , we have δ i ≤ n 0 -1, impling that n 0 -i n 0 -δ i ≤ n 0 -i ≤ n 0 -2 .
It is worth noticing that Bound (1) and the trivial bound are in some sense symetric. Indeed, we have

deg(G • F ) deg G ≤ max 1≤i<n 0 δ i i and n -deg(G • F ) n -deg G ≥ max 1≤i<n 0 n 0 -i n 0 -δ i -1
.

In other words, when representing deg(G • F ) as a function of deg G, the trivial bound states that the degree of G • F is upper-bounded by a line through the origin with coefficient deg F . When representing the "degree deficiency" (n -deg(G • F )) as a function of (n -deg G), [START_REF] Aumasson | Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi[END_REF] states that the degree deficiency of G • F is lower-bounded by a line through the origin with coefficient γ -1 . This can be observed on Figure 1 where the parameters correspond to the inverse of Keccak permutation. 3 Distinguishing properties related to the algebraic degree

Higher-order derivatives

The algebraic degree of a permutation F provides some particular distinguishers, which correspond to the values of any derivative of F with respect to a subspace of F n 2 with dimension (deg(F ) + 1). This result comes from the following property of higher-order derivatives of a function.

Definition 1. [12] Let F be a function from F n 2 into F m 2 . For any a ∈ F n 2 the derivative of F with respect to a is the function D a F (x) = F (x + a) + F (x). For any k-dimensional subspace V of F n
2 and for any basis of V , {a 1 , . . . , a k }, the k-th order derivative of F with respect to V is the function defined by

D V F (x) = D a 1 D a 2 . . . D a k F (x) = v∈V F (x + v), ∀x ∈ F n 2 .
It is well-known that the degree of any first-order derivative of a function is strictly less than the degree of the function. This simple remark, which is exploited in higher-order differential attacks [START_REF] Knudsen | Truncated and higher order differentials[END_REF], implies that for every subspace V of dimension (deg F + 1),

D V F (x) = v∈V F (x + v) = 0, for every x ∈ F n 2 .

Zero-sum structures

The existence of zero-sum structures is a distinguishing property which has been recently investigated by Aumasson and Meier [START_REF] Aumasson | Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi[END_REF], Knudsen and Rijmen [START_REF] Knudsen | Known-key distinguishers for some block ciphers[END_REF] and by Boura and Canteaut [START_REF] Boura | Zero-sum Distinguishers for Iterated Permutations and Application to Keccak-f and Hamsi-256[END_REF].

Definition 2. Let F be a function from F n 2 into F m 2 . A zero-sum for F of size K is a subset {x 1 , . . . , x K } ⊂ F n
2 of elements which sum to zero and for which the corresponding images by F also sum to zero, i.e., K i=1

x i = K i=1 F (x i ) = 0 .
It has been shown in [START_REF] Boura | Zero-sum Distinguishers for Iterated Permutations and Application to Keccak-f and Hamsi-256[END_REF] that any function from F n 2 into F m 2 has zero-sums of size less than or equal to 5. However, when F is a permutation over F n 2 , a much stronger property, named zero-sum partition, can be investigated.

Definition 3. Let P be a permutation from F n 2 into F n 2 . A zero-sum partition for P of size K = 2 k is a collection of 2 n-k disjoint zero-sums X i = {x i,1 , . . . , x i,2 k } ⊂ F n 2 i.e., 2 n-k i=1 X i = F n 2 and 2 k j=1 x i,j = 2 k j=1 P (x i,j ) = 0, ∀1 ≤ i ≤ 2 n-k .
Here, we focus on the search for zero-sum partitions coming from structural properties of the permutation P , when P is an iterated permutation of the form

P = R r • . . . • R 1 ,
where all R i are simpler permutations over F n 2 , named the round permutations. The fact that the permutation used in a hash function does not depend on any secret parameter allows to exploit the previous property starting from the middle, i.e., from an intermediate internal state. This property was used by Aumasson and Meier [START_REF] Aumasson | Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi[END_REF] and also by Knudsen and Rijmen in the case of a known-key property of a block cipher [START_REF] Knudsen | Known-key distinguishers for some block ciphers[END_REF]. The only information needed for finding such zero-sums on the iterated permutation using this first approach is an upper bound on the algebraic degrees of both the round transformation and its inverse.

More precisely, we consider P = R r • . . . • R 1 , and we choose some integer t, 1 ≤ t ≤ r. We define the following functions involved in the decomposition of P : F r-t consists of the last (r -t) round transformations, i.e., F r-t = R r • . . . • R t+1 and G t consists of the inverse of the first t round transformations, i.e.,

G t = R -1 1 • . . . • R -1 t .
Then, as detailed in [START_REF] Aumasson | Zero-sum distinguishers for reduced Keccak-f and for the core functions of Luffa and Hamsi[END_REF] and in [START_REF] Boura | Zero-sum Distinguishers for Iterated Permutations and Application to Keccak-f and Hamsi-256[END_REF], we can find many zero-sum partitions for P of size 2 d+1 where d = max(deg(F r-t ), deg(G t )).

Besides the degree of the round transformation, it has been shown in [START_REF] Boura | Zero-sum Distinguishers for Iterated Permutations and Application to Keccak-f and Hamsi-256[END_REF] that some properties of the linear layer in the round transformation may also be exploited for constructing zero-sum partitions, in particular when the nonlinear layer of the round transformation consists of parallel applications of smaller functions defined over F n 0 2 . In the following, we denote by B i , 0 ≤ i < m, the n 0 -dimensional subspaces corresponding to the inputs of these smaller Sboxes, i.e., B i = e n 0 i , . . . , e n 0 i+n 0 -1 where e 0 , . . . , e n-1 denotes the canonical basis of F n 2 and where the positions of the n bits in the internal state are numbered such that the n 0 -bit Sboxes apply on n 0 consecutive input variables. Then, it was shown in [START_REF] Boura | Zero-sum Distinguishers for Iterated Permutations and Application to Keccak-f and Hamsi-256[END_REF] that it is possible to extend a number of zero-sum partitions that have been found for t rounds, to t + 1 rounds, without increasing the complexity.

Proposition 2. [3] Let d 1 and d 2 be such that deg(F r-t-1 ) ≤ d 1 and deg(G t ) ≤ d 2 .
Let us decompose the round transformation after t rounds into R t+1 = A 2 • χ • A 1 where both A 1 and A 2 have degree 1 and χ corresponds to the concatenation of m smaller permutations defined over F n 0 2 . Let I be any subset of {0, . . . , m -1} of size (d + 1)/n 0 , let

V = i∈I B i
and W be its complement. Then, the sets

X a = {(G t • A -1 1 )(a + z), z ∈ V }, a ∈ W form a zero-sum partition of F n 2 of size 2 k , with k = n 0 d+1
n 0 , for the r-round permutation P .

It is worth noticing that the zero-sum partitions deduced from this proposition correspond to a structural property which can be described by means of some close formula. This implies for instance that they can be used for proving that some given permutations do not satisfy the expected property, and this may only require the evaluation of the permutation on a few sets X i . In this sense, they differ from the zero-sum partitions found by a generic algorithm since all generic algorithms known so far require the evaluation of the permutation at almost all points (see [START_REF] Boura | Zero-sum Distinguishers for Iterated Permutations and Application to Keccak-f and Hamsi-256[END_REF] for a discussion on generic algorithms for finding zero-sums and zero-sum partitions).

4 Application to the Keccak-f permutation 4.1 The Keccak-f permutation Keccak [START_REF] Bertoni | Keccak sponge function family main document[END_REF] is one of the fourteen hash functions selected for the second round of the SHA-3 competition. Its mode of operation is the sponge construction. The inner primitive in Keccak is a permutation, composed of several iterations of very similar round transformations. Within the Keccak-family, the SHA-3 candidate operates on a 1600-bit state, which is represented by a 3-dimensional binary matrix of size 5 × 5 × 64. Then, the state can be seen as 64 parallel slices, each one containing 5 rows and 5 columns. The permutation in Keccak is denoted by Keccak-f [b], where b is the size of the state. So, for the SHA-3 candidate, b = 1600.

The number of rounds in Keccak-f [1600] was 18 in the original submission, and it has been updated to 24 for the second round. Every round R consists of a sequence of 5 permutations modifying the state:

R = ι • χ • π • ρ • θ.
The functions θ, ρ, π, ι are transformations of degree 1 providing diffusion in all directions of the 3-dimensional state. Then, keeping the same notation as in the previous section, we have

A 1 = π • ρ • θ,
which is linear and A 2 = ι, which corresponds to the addition of a constant value. Therefore, the linear part of

A = A 1 • A 2 corresponds to L = π • ρ • θ.
The nonlinear layer, χ, is a quadratic permutation which is applied to each row of the 1600-bit state. In other words, 320 parallel applications of χ 0 are implemented in order to provide confusion. The inverse permutation, denoted by χ -1 , is a permutation of degree 3.

Zero-sum partitions for the full Keccak-f permutation

We apply here Theorem 2 to the Keccak-f round permutation, which is denoted by R. For any F ,

deg(F • R) = deg(F • χ) ≤ n - n -deg(F ) 3 and deg(F • R -1 ) = deg((F • L -1 ) • χ -1 ) ≤ n - n -deg(F )
3 by using that the inverse of χ has degree 3. By combining this bound with the trivial bound, we get the bound presented in Table 1 on the degree of several iterations of the round permutation of Keccak-f and of its inverse. With this new bound, we can use the technique presented in corresponding to a collection of 318 rows (out of the 320), implying dim V = 1590. Then, the sets

X a = {(G 10 • L -1 )(a + z), z ∈ V }, a ∈ F 1600 2 ,
where G 10 denotes the inverse of the first 10 rounds, form a zero-sum partition of size 2 1590 for the full Keccak-f permutation. This comes directly from Proposition 2 and from the fact that the inverse of the first 10 rounds of the permutation have degree at most 1589 < dim V , and that the last 13 rounds have degree at most 1578 < dim V.

Recently, Duan and Lai [START_REF] Duan | Improved zero-sum distinguisher for full round Keccak-f permutation[END_REF] have observed that the inverse of χ has the following remarkable property: the product of any 2 components of χ -1 has degree at most 3 (instead of 4 which is the bound obtained with Proposition 1). Then, we deduce that the value of the coefficient γ for χ -1 involved in Theorem 2 is γ = 2 since δ 2 = 3. By using this particular property of χ -1 , the previous result can be improved as follows: for any F ,

deg(F • R -1 ) = deg((F • L -1 ) • χ -1 ) ≤ n - n -deg(F ) 2 .
This leads to the new bound on several iterations of R -1 as presented in the last column of Table 1. Now, by choosing the intermediate states after the linear layer on the 12-th round of Keccak-f in any subspace V corresponding to a collection of 315 rows, we obtain a zero-sum partition for the full 24-round Keccak-f permutation of size 2 1575 . This comes from the fact that the inverse of the first 11 rounds have degree at most 1572 < dim V and that the last 12 rounds have degree at most 1536 < dim V .

5 Application to the hash function Luffa

The Luffa hash function

The Luffa hash function [START_REF] De Cannière | Hash Function Luffa: Specification[END_REF][START_REF] De Cannière | Hash Function Luffa: Specification[END_REF] is also a Round-2 candidate of the NIST SHA-3 competition. Its mode of operation is based on a variant of the sponge design. The internal state in Luffa consists of w 256-bit words where w equals 3, 4 and 5 for the output lengths 256, 384 and 512 bits respectively. At each iteration, a 256-bit message block is processed by applying a linear message injection function MI. Then, a permutation is applied to the output as follows: the state is split into w 256-bit words and w parallel 256-bit permutations Q j are applied to each word independently. Finally, a finalization step is applied. It consists of several iterations of a blank round with fixed message 0x0...00 followed by a linear output function OF. In Luffa v1, a blank round with message block 0x0...00 is applied at the beginning of the finalization, only if the number of padded message blocks is strictly greater than one. In Luffa v2 such a blank round is always applied, in order to prevent higher-order differential attacks.

The SubCrumb The input of every Sbox has four bits, every one coming from a different word a k : S substitutes the ℓ-th bits of a 0 , a 1 , a 2 , a 3 (or a 4 , a 5 , a 6 , a 7 ) by a 4 × 4 Sbox of degree 3. The Sbox used in the original submission, Luffa v1, was S 1 [16] = {7, 13, 11, 10, 12, 4, 8, 3, 5, 15, 6, 0, 9, 1, 2, 14} , but the terms of degree 3 in the first three coordinates of this Sbox are similar. This property has been exploited in [START_REF] Watanabe | Higher Order Differential Attack on Step-Reduced Variants of Luffa v1[END_REF] for showing that the degree of Q j does not grow as expected. In particular, Q j reduced to 5 rounds out of 8 has degree at most 130, and the sum of the first two coordinates of Q j after 6 rounds has degree at most 214. In order to avoid these unsuitable properties, the designers have modified the Sbox according to the strategy detailed in [START_REF] De Cannière | The reasons for the change of Luffa. Supplied with the second round package[END_REF]. The new Sbox used in Luffa v2, is then S 2 [16] = {13, 14, 0, 1, 5, 10, 7, 6, 11, 3, 9, 12, 15, 8, 2, 4} , and the algebraic normal forms of its outputs are

y 0 = 1 + x 0 + x 1 + x 1 x 2 + x 0 x 3 + x 1 x 3 + x 0 x 1 x 3 + x 0 x 2 x 3 y 1 = x 0 + x 3 + x 0 x 1 + x 1 x 2 + x 0 x 3 + x 1 x 3 + x 0 x 1 x 3 + x 0 x 2 x 3 y 2 = 1 + x 1 + x 3 + x 0 x 2 + x 1 x 2 + x 1 x 3 + x 2 x 3 + x 0 x 1 x 2 + x 0 x 1 x 3 y 3 = 1 + x 1 + x 2 + x 0 x 3 + x 0 x 2 + x 1 x 2 + x 1 x 3 + x 2 x 3 + x 0 x 1 x 2 + x 0 x 1 x 3
Then the substitution by S is given by in Luffa v1. In Luffa v2, the order of the last four input words is modified when entering the Sbox in order to break the symmetries exploited in [START_REF] Watanabe | Higher Order Differential Attack on Step-Reduced Variants of Luffa v1[END_REF]:

b 3,ℓ ||b 2,ℓ ||b 1,ℓ ||b 0,ℓ = S[a 3,ℓ ||a 2,ℓ ||a 1,ℓ ||a 0,ℓ ], 0 ≤ ℓ < 32,
b 3,ℓ ||b 2,ℓ ||b 1,ℓ ||b 0,ℓ = S[a 3,ℓ ||a 2,ℓ ||a 1,ℓ ||a 0,ℓ ], 0 ≤ ℓ < 32,

Algebraic degree of the Q j permutation and its inverse

We now show that the approach used in [START_REF] Watanabe | Higher Order Differential Attack on Step-Reduced Variants of Luffa v1[END_REF] still applies to some extent to the Luffa v2 nonlinear function, and that this approach can be combined with Theorem 2 in order to find a new upper bound on the degree of several iterations of the Step function.

The remarkable property comes from the fact that the sum of the four coordinates of S 2 has degree 2 only: indeed, we deduce from the algebraic normal forms of the coordinates of S 2 that

d = y 0 + y 1 + y 2 + y 3 = 1 + x 1 + x 2 + x 0 x 1 + x 0 x 3 . Let a r i = a r i,ℓ 0≤ℓ<32
denote the output words of r rounds of Step, and let d r 0,ℓ (resp. d r 4,ℓ ) denote the sum a r 0,ℓ + a r 1,ℓ + a r 2,ℓ + a r 3,ℓ (resp. a r 4,ℓ + a r 5,ℓ + a r 6,ℓ + a r 7,ℓ ). Now, let us consider the sum of any two distinct monomials of degree 3 in 4 variables. Any such two monomials share two variables. Then, if we denote by d the sum of all four variables, we obtain that

x i x j x k + x i x j x k ′ = x i x j x k + x i x j (x i + x j + x k + d) = x i x j x k + x i x j + x i x j + x i x j x k + x i x j d = x i x j d .
It follows that, since all coordinates of the Sboxes S 2 contain an even number of distinct monomials of degree 3, the degrees of their outputs (and then the degree of the output of (r + 1) rounds) satisfy deg

a r+1 i,ℓ ≤ 2 max 0≤j≤3 deg a r j,ℓ + deg d r 0,ℓ ∀0 ≤ i ≤ 3 . (2)
Moreover, this property holds for any ordering of the inputs and outputs of the Sbox, implying

deg a r+1 i,ℓ ≤ 2 max 4≤j≤7 deg a r j,ℓ + deg d r 4,ℓ ∀4 ≤ i ≤ 7 .
Now, since the linear layer consists of the same function applied to all pairs of words (b k , b k+4 ) for 0 ≤ k ≤ 3 separately, we deduce that

d r+1 0,ℓ = a r+1 0,ℓ + a r+1 1,ℓ + a r+1 2,ℓ + a r+1 3,ℓ = 3 i=0 MixWord 0,ℓ (b i , b i+4 ) = MixWord 0,ℓ 3 i=0 b i , 3 i=0 b i+4 and d r+1 4,ℓ = MixWord 1,ℓ 3 i=0 b i , 3 i=0 b i+4 .
Therefore, the degrees of d r+1 0,ℓ and of d r+1 4,ℓ correspond to the degrees of the sum of the four coordinates of the Sboxes, implying

deg d r+1 i,ℓ ≤ 2 max i≤j≤i+3 deg a r j,ℓ , i ∈ {0, 4} . (3)
Both recurrence relations ( 2) and (3) lead to the bounds presented in Table 2 on the degrees of several iterations of Step for the new nonlinear layer (i.e. for the new Sbox S 2 and the ordering of the input variables).

Table 2. Upper bounds on the algebraic degree of the output of r iterations of Step for Luffa v2 (and comparison with the results obtained in [START_REF] Watanabe | Higher Order Differential Attack on Step-Reduced Variants of Luffa v1[END_REF] for Luffa v1). Now, for r ≥ 6, we apply Theorem 2, exploiting the fact that Step is the composition of a linear layer and of several parallel applications of a smaller balanced Sbox of degree 3 defined over F 4 2 . Then, for any G, we have

r Luffa v2 Luffa v1 deg a r i,ℓ deg d r i,ℓ deg a r i,ℓ deg d r i,ℓ 1
deg(G • Step) ≤ 512 + deg(G) 3 , implying max i,ℓ deg(a r i,ℓ ) ≤ 512 + max i,ℓ deg(a r-1 i,ℓ ) 3 and max i,ℓ deg(d r i,ℓ ) ≤ 512 + max i,ℓ deg(d r-1 i,ℓ ) 3 .
These new bounds are given in Table 3.

Table 3. Upper bounds on the algebraic degree of the output of r iterations of Step for Luffa v1 and Luffa v2. It is worth noticing that the same upper bounds hold for the degree of r iterations of the inverse of Step in Luffa v2 since the algebraic normal form of the inverse of S 2 is

r Luffa v2 Luffa v1 deg x r i,ℓ deg d r i,ℓ deg x r i,ℓ deg d r i,ℓ 1
y 0 = x 0 + x 2 + x 3 + x 2 x 3 y 1 = 1 + x 3 + x 0 x 1 + x 0 x 2 + x 0 x 3 + x 2 x 3 + x 0 x 2 x 3 + x 1 x 2 x 3 y 2 = x 1 + x 2 + x 3 + x 0 x 1 + x 1 x 2 + x 0 x 3 + x 1 x 3 + x 0 x 1 x 3 + x 0 x 1 x 2 + x 0 x 2 x 3 + x 1 x 2 x 3 y 3 = x 1 + x 2 + x 3 + x 0 x 2 + x 2 x 3 + x 0 x 1 x 2 + x 0 x 1 x 3 .
Then, the sum of the four coordinates of S -1 2 is equal to

1 + x 0 + x 2 + x 1 x 2 + x 1 x 3 + x 2 x 3
and has degree 2 only. Moreover, all four coordinates of S -1 2 have an even number of monomials of degree 3. Then, the previously described technique for upper-bounding the degree of several iterations of the round function applies similarly when computing the inverse.

Higher-order differentials for the compression function of Luffa v2

The compression function in Luffa v2 takes as input a 256w-bit chaining value and a 256-bit message block and it outputs a new 256w-bit chaining value, where w equals 3, 4 and 5 when the output length is 256, 384 and 512. Then, we have proved that this function has degree at most 252, while it is expected from its construction to have degree 255.

A first consequence is the existence of all-zero higher-order differentials for the full compression function of Luffa v2, similar to those found in [START_REF] Watanabe | Higher Order Differential Attack on Step-Reduced Variants of Luffa v1[END_REF] for Luffa v1 reduced to 7 steps. Let us choose a position ℓ 0 among the 32 possible positions in a word, 0 ≤ ℓ 0 < 32, and let us consider any coset of the linear subspace V of the set of all possible message blocks defined as

V = e i,ℓ , 0 ≤ i ≤ 7, ℓ = ℓ 0 ,
where e i,ℓ denotes the 256-bit word of Hamming weight 1 having a one at position ℓ in word i. Then, V has dimension 248. For any fixed chaining value, the message injection function M I stabilizes the subspaces e i,ℓ , 0 ≤ i ≤ 7 , implying that the input of each Q j is a coset of V . Now, the tweak function at the beginning of each Q j rotates the least significant four words by a number of bits depending on j. Its output then corresponds to a coset of a subspace ′ , which is the direct sum of 4-dimensional subspaces of the form e i,ℓ , 0 ≤ i ≤ 3 or e i,ℓ , 4 ≤ i ≤ 7 . Since the first nonlinear layer applies to those 4-dimensional subspaces separately, it stabilizes the structure of V ′ . Therefore, the output of the first iteration of Step in each Q j varies in a coset of a subspace of dimension 248. Then, the outputs of the compression function, i.e., after 8 iterations of Step, sum to zero when the message block varies in any coset of V , since dim V = 248 > 246 > deg(Step 7 ). This observation holds for any size of the hash value. It should be noted that, by nature, this algebraic property is very different from the properties exploited in previously known distinguishers on the compression function of Luffa v2 (e.g. [START_REF] Khovratovich | Cryptanalysis of Luffa v2 components[END_REF]).

Zero-sum partitions for the Q j permutations

We consider the subspace V generated by the first 23 bits in a given word, that is V = e i 0 ,0 , e i 0 ,1 , . . . , e i 0 ,22 , for some 0 ≤ i 0 ≤ 7. Then, we can show that the sets

X a = {Tweak -1 j • Step -1 4 (a + z), z ∈ V }, a ∈ F 256 2 .
form a zero-sum partition of size 2 23 for each Q j . We first consider any coset of V as input of 4 rounds of Step. Then, the 23 active bits in V correspond to the inputs of 23 different Sboxes and thus the first round of Step is a function of degree 1 in these 23 input bits. As 3 iterations of Step have degree at most 22, we deduce that x∈Xa Q j (x) = 0 .

We now focus on the backward computation. We first take the image of V under the inverse of the linear application MixWord. As all the variables are in the same word a i 0 , after the application of the inverse of the linear layer, all words are constant except the words of index i 0 and (i 0 + 4). But the bits of the words a i 0 and a i 0 +4 all go to different Sboxes, implying that the first round backwards is linear. As we have proven that the inverse of 3 iterations of Step has degree at most 22, deduce that x∈Xa x = 0 .

There exist 32 23 × 8 = 2 27.7 such zero-sum partitions for each Q j corresponding to all possible choices for V , i.e., for all possible choices for i 0 and for the 23 positions within the word of index i 0 .

Higher-order differentials for the full Luffa v1 hash function

It is shown in [START_REF] Watanabe | Higher Order Differential Attack on Step-Reduced Variants of Luffa v1[END_REF] that, when hashing messages of length at most 256 bits, the reduced version of Luffa v1 hash function, with 7 out of 8 steps in each Q j , does not behave as a random function. Actually, if the message block varies in some particular subspace of dimension 216, then some linear combination of the output words of this reduced version of Luffa v1 sums to zero. This property comes from the fact that Luffa v1 does not perform any blank round for one-block messages, and that, after 6 rounds of Step, some linear combinations of the output words have degree at most 214. Even if the advantage that this property could give to an attacker is unclear, this unsuitable property has led the designers to modify the function for the second round of the SHA-3 competition. In particular, a blank round is performed for any message length in Luffa v2.

It turns out that this was probably a prudent decision, as the new upper bound on the degree of Q j for Luffa v1 given in Table 3 now shows that a similar distinguisher can be exhibited for the full Luffa v1, since the degree of the two words obtained by (y 0 + y 1 + y 2 + y 3 , y 4 + y 5 + y 6 + y 7 ) after 7 iterations of Step is at most 236. We then get a similar distinguisher based on the fact that the corresponding linear combinations of the bits of the hash values sum to zero when the message block varies in some particular subspace of dimension 240.

More interestingly, we have shown that the full Luffa v1 hash function, when applied to one-block messages, has degree at most 251 in the 255 bits of the message.

Degree of the full Luffa v2 hash function with chosen IVs

The previous observation does not hold for Luffa v2 since a blank round is performed for any message length. However, if we would consider the 256w bits of the initial value of Luffa v2 as an additional input which can freely be chosen, then we can still make some theoretical observations for the hash function applied to one-block messages. Recall that w equals 3, 4 and 5 for a message digest of 256, 384 and 512 bits respectively.

In this setting, Luffa v2 is a function from (256(w + 1) -1) bits to 128(w -1) bits, where the input bits correspond to the bits of the initial value and of the message block. But, Luffa v2 is composed of a linear message injection function, followed by a function G from 256w bits to 128(w -1) bits. Therefore, the degree of the (256(w + 1) -1)-bit function Luffa v2 is equal to the degree of G and cannot exceed 256w. Moreover, we can show that the degree of this function is even smaller than 256w due to the particular design of the inner permutation.

This new upper bound on the degree of Luffa v2 comes from the fact that G can be decomposed as the inner permutation P , i.e., the parallel applications of w independent nonlinear permutations Q j of n 0 = 256 variables with degree less than (n 0 -2), followed by some rounds of the finalization function Final. Moreover, the first 256 bits of the message digest are extracted after a single application of Final. Then, using that the finalization function consists For the (128(w -1))-bit version of Luffa v2, we get that the first 256 output bits of Luffa v2 have degree at most (256w -w). This property must be compared to the probability that this property holds for a randomly chosen function from F 256(w+1)-1 2 to F 256 2 bits. Such a function can be written as a polynomial with coefficients in F 2 256 and the number of its monomials of degree greater than (256w -w + 1) is 256+w-1 i=0 256(w + 1) -1 i .

Therefore, the probability that a randomly chosen function with the same parameters as Luffa v2-256 has degree at most 765 is 2 -2 837 . For the 384-bit version (resp. for the 512-bit version), i.e., for w = 4 (resp. w = 5), we get that Luffa v2 has 1280 variables (resp. 1536 variables) and degree at most 1020 (resp. 1275). The probability that this property holds for a randomly chosen function with the same parameters is 2 -2 933 (resp. 2 -2 1010 ).

Conclusions

We have found a new bound for the degree of iterated permutations. This improved bound has firstly led to zero-sum distinguishers for the full Keccak-f permutation. Even if the security of the hash function is not affected, our results contradict the so-called hermetic sponge strategy. Additionally, a number of structural properties related to the existence of all-zero higher-order differentials and of zero-sum partitions have been presented for the Luffa hash family.

Fig. 1 .

 1 Fig. 1. Evolution of the degree of G • F where F is a 1600-variable function composed of 320 cubic permutations over F 5 2 corresponding to the inverse of Keccak χ function.

Fig. 2 .

 2 Fig. 2. The Luffa construction

Fig. 3 .

 3 Fig. 3. The Step function

b 7 ,

 7 ℓ ||b 6,ℓ ||b 5,ℓ ||b 4,ℓ = S[a 7,ℓ ||a 6,ℓ ||a 5,ℓ ||a 4,ℓ ], 0 ≤ ℓ < 32.

b 4 ,

 4 ℓ ||b 7,ℓ ||b 6,ℓ ||b 5,ℓ = S[a 4,ℓ ||a 7,ℓ ||a 6,ℓ ||a 5,ℓ ], 0 ≤ ℓ < 32. The MixWord Permutation. MixWord is a linear permutation of two words. If z 0 , . . . , z 7 are the 8 words of the state after the application of Step have that (z 0 , z 4 ) = MixWord(b 0 , b 4 ), (z 1 , z 5 ) = MixWord(b 1 , b 5 ), (z 2 , z 6 ) = MixWord(b 2 , b 6 ), (z 3 , z 7 ) = MixWord(b 3 , b 7 ).

  of 8 iterations of Step and has then degree at most 252, Theorem 2 implies that deg(Final • P ) ≤ 256w -256w -deg(Final) 254 ≤ 256w -256w -252 254 < 256w -(w -1) .

Table 1 .

 1 Upper bounds on the degree of several rounds of Keccak-f and of its inverse (the results in bold are obtained with the new bound, while the other ones correspond to the trivial bound).Proposition 2 for finding zero-sum partitions for the full Keccak-f permutation. Namely, we consider the intermediate states after the linear layer L = π • ρ • θ in the 11-th round. Let us choose any subspace V in F 1600 2

		forward			backward
	# rounds bound on deg(R r ) # rounds bound on deg(R -r ) bound on deg(R -r ) using [8]
	1	2	1	3	3
	2	4	2	9	9
	3	8	3	27	27
	4	16	4	81	81
	5	32	5	243	243
	6	64	6	729	729
	7	128	7	1309	1164
	8	256	8	1503	1382
	9	512	9	1567	1491
	10	1024	10	1589	1545
	11	1408	11	1596	1572
	12	1536	12	1598	1586
	13	1578	13	1599	1593
	14	1592	14	1599	1596
	15	1597	15	1599	1598
	16	1599	16	1599	1599

Acknowledgments.

We would like to thank Gilles Van Assche for his valuable comments and interesting suggestions.

⋆ Partially supported by the French Agence Nationale de la Recherche through the SAPHIR2 project under Contract ANR-08-VERS-014.


Knuth Relations

Éphane St

Peter Gaussent

An Hoa Littelmann

Nguyen Dedicated

C S Seshadri

An Hoa Nguyen
email: ahnguyen@math.uni-koeln.de

TABLEAUX AND MV-CYCLES

We give a geometric interpretation of the Knuth equivalence relations in terms of the affine Graßmann variety. The Young tableaux are seen as sequences of coweights, called galleries. We show that to any gallery corresponds a Mirković-Vilonen cycle and that two galleries are equivalent if, and only if, their associated MV cycles are equal. Words are naturally identified to some galleries. So, as a corollary, we obtain that two words are Knuth equivalent if, and only if, their associated MV cycles are equal.

Introduction

In the theory of finite dimensional representations of complex reductive algebraic groups, the group GL n (C) is singled out by the fact that besides the usual language of weight lattices, roots and characters, there exists an additional important combinatorial tool: the plactic monoid of Knuth [START_REF] Knuth | Permutations, matrices, and generalized Young tableaux[END_REF], Lascoux and Schützenberger [START_REF] Lascoux | Le monoïde plaxique[END_REF], and the Young tableaux.

The plactic monoid is the monoid of all words in the alphabet A = {1, . . . , n} modulo Knuth equivalence (see [START_REF] Bia Lynicki-Birula | Some properties of the decompositions of algebraic varieties determined by actions of a torus[END_REF]). The map associating to a word its class in the plactic monoid has a remarkable section: the semi-standard Young tableaux. In the framework of crystal bases [START_REF] Joseph | Quantum Groups and their primitive ideals[END_REF], [START_REF] Hong | Introduction to quantum groups and crystal bases[END_REF], [START_REF] Kashiwara | Crystalizing the q-analog of Universal Enveloping Algebras[END_REF], [START_REF] Kashiwara | Crystal base and Littelmann's refined Demazure character formula[END_REF], [START_REF] Lusztig | Canonical bases arising from quantized enveloping algebras II[END_REF] and the path model of representations [START_REF] Littelmann | Paths and root operators in representation theory[END_REF], this monoid got a new interpretation, which made it possible to generalize the classical tableaux character formula to integrable highest weight representations of Kac-Moody algebras.

Mirković and Vilonen [START_REF] Mirković | Geometric Langlands duality and representations of algebraic groups over commutative rings[END_REF] gave a geometric interpretation of weight multiplicities for finite dimensional representations of a semi simple algebraic group G. Given a dominant coweight λ ∨ , let X λ ∨ ⊂ G be the Schubert variety in the associated affine Graßmann variety G [START_REF] Lusztig | Canonical bases arising from quantized enveloping algebras II[END_REF][START_REF] Kumar | Kac-Moody Groups, their Flag Varieties and Representation Theory[END_REF]. Let U -be the maximal unipotent subgroup opposite to a fixed Borel subgroup and denote by O the ring of formal power series C[[t]] and by K its quotient field. The irreducible components of G(O).λ ∨ ∩ U -(K).µ ∨ ⊂ X λ ∨ (Section 9) are called MV-cycles and the number of irreducible components is the weight multiplicity of the weight µ ∨ in the complex irreducible representation V (λ ∨ ) for the Langlands dual group G ∨ . This leads naturally to the question: is it possible to give a geometric formulation of the Knuth relations? The aim of this article is to do this for G = SL n (C). For 1 ≤ d ≤ n denote by I d,n the set {i = (i 1 , . . . , i d ) | 1 ≤ i 1 < i 2 < . . . i d ≤ n}, and set W = I 1,n ∪ I 2,n ∪ . . . ∪ I n-1,n ∪ I n,n . We can identify A with I 1,n and hence view A as a subset of W. Words in the alphabet W are called galleries, and we introduce on the set of galleries an equivalence relation ∼ K which, restricted to words in the alphabet A, is Date: 03.10.2012.

exactly the Knuth equivalence. To a given gallery γ, we associate in a canonical way a Bott-Samelson type variety Σ, a cell C γ ⊂ Σ, a dominant coweight ν ∨ , a map π : Σ → G and show (see Theorem 2):

Theorem. a) The closure of the image π(C γ ) is a MV-cycle in the Schubert variety X ν ∨ . b) Given a second gallery γ ′ with associated Bott-Samelson type variety Σ ′ , cell C γ ′ ⊂ Σ ′ and map π ′ : Σ ′ → G, then γ ∼ K γ ′ if and only if π(C γ ) = π ′ (C γ ′ ).

In particular we get:

Corollary. Two words in the alphabet A are Knuth equivalent if and only if the closure of the images of the corresponding cells define the same MV-cycle.

The theorem generalizes for G = SL n (C) the result in [START_REF] Gaussent | One-skeleton galleries, the path model and a generalization of Macdonald's formula for Hall-Littlewood polynomials[END_REF], where it was proved that (for semisimple algebraic groups) the image of a cell associated to a Lakshmibai-Seshadri galleries is an MV-cycle.

The construction of the Bott-Samelson type variety and the cell can be sketched out as follows: the elements of the alphabet can be identified with weights occurring in the fundamental representations of the group SL n (C) (for example i ↔ ǫ i ), so words and galleries can be viewed as polylines in the apartment associated to the maximal torus T of diagonal matrices in G = SL n (C). The vertices and edges of a polyline γ give naturally rise to a sequence P 0 ⊃ Q 0 ⊂ P 1 ⊃ . . . ⊂ P r of parabolic subgroups of the associated affine Kac-Moody group, and hence we can associate to a gallery the Bott-Samelson type variety Σ = P 0 × Q 0 P 1 × Q 1 . . . × Q r-1 P r /P r . In the language of buildings (which we do not use in this article) the variety Σ can be seen as the variety of all galleries in the building of the same type as γ and starting in 0, making Σ into a canonical object associated to γ. By choosing a generic anti-dominant one parameter subgroup η of T , we get a natural Bia lynicki-Birula cell [START_REF] Bia Lynicki-Birula | Some properties of the decompositions of algebraic varieties determined by actions of a torus[END_REF] decomposition of Σ. The η-fixed points in Σ correspond exactly to galleries of the same type as γ (section 3), and C γ = {x ∈ Σ | lim t→0 η(t)x = γ}. The variety Σ is a desingularization of a Schubert variety in G and is hence naturally endowed with a morphism π : Σ → G [START_REF] Gaussent | One-skeleton galleries, the path model and a generalization of Macdonald's formula for Hall-Littlewood polynomials[END_REF].

Given a gallery γ, we get a natural sequence of vertices (µ ∨ 0 , . . . , µ ∨ r ) crossed by the gallery. We attach to each vertex a subgroup U - j of U -(K) and show that the image of the cell is

U - 0 • • • U - r µ ∨
, where µ ∨ is the endpoint of the associated polyline. Using this description of the image and commuting rules for root subgroups, we show that the image of cells associated to Knuth equivalent galleries have a common dense subset. Since every equivalence class has a unique gallery associated to a semi-standard Young tableaux, the results in [START_REF] Gaussent | One-skeleton galleries, the path model and a generalization of Macdonald's formula for Hall-Littlewood polynomials[END_REF] show that the closure of such an image is a MV-cycle, and this correspondence semi-standard Young tableaux ↔ MV-cycles is bijective.

We conjecture that, as in the special case of Lakshmibai-Seshadri galleries in [START_REF] Gaussent | One-skeleton galleries, the path model and a generalization of Macdonald's formula for Hall-Littlewood polynomials[END_REF], a generalization of the theorem above holds (after an appropriate reformulation and using [START_REF] Littelmann | A Plactic Algebra for Semisimple Lie Algebras[END_REF] with Lakshmibai-Seshadri tableaux / galleries as section instead of Young tableaux) for arbitrary complex semi-simple algebraic groups.

Words and keys

We fix as alphabet the set A = {1, 2, . . . , n} with the usual order 1 < 2 < . . . < n. By a word we mean a finite sequence (i 1 , . . . , i k ) of elements in A, k is called the length of the word. The set of words W forms a monoid with the concatenation of words as an operation and with the empty word as a neutral element. We define an equivalence relation on the set of words as follows. We say that two words u, w are related by a Knuth relation if we can find a decomposition of u and w such that v 1 , v 2 are words, x, y, z ∈ A and

(1) u = v 1 xzyv 2 and w = v 1 zxyv 2 where x < y ≤ z or u = v 1 yzxv 2 and w = v 1 yxzv 2 where x ≤ y < z .

Definition 1. Two words are called Knuth equivalent: u ∼ K w, if there exists a sequence of words u = v 0 , v 1 , . . . , v r = w such that v j-1 is related to v j by a Knuth relation, j = 1, . . . , r.

Remark 1. The set of equivalence classes forms a monoid (called the plactic monoid, see [START_REF] Lascoux | Le monoïde plaxique[END_REF][START_REF] Schützenberger | La correspondance de Robinson[END_REF][START_REF] Littelmann | A Plactic Algebra for Semisimple Lie Algebras[END_REF]) with the concatenation of classes of words as an operation and with the class of the empty word as a neutral element.

Remark 2. Though we mostly refer to [START_REF] Fulton | Introduction to toric varieties[END_REF][START_REF] Lascoux | Cyclic permutations on words, tableaux and harmonic polynomials[END_REF][START_REF] Lascoux | Le monoïde plaxique[END_REF] for results concerning the word algebra and Knuth relations, note that there is a difference in the way the Knuth relations are stated. The reason for the change is the way we translate tableaux into words, see Remark 3. The key diagram D 1 is of column shape (4, 2, 4, 1), the Young diagram D 2 is of column shape (1, 2, 4)

Definition 3.
A key tableau of column shape (n 1 , . . . , n r ) is a filling of the corresponding key diagram with elements from the alphabet A such that the entries are strictly increasing in the columns (from top to bottom). A semistandard Young tableau of shape (n 1 , . . . , n r ), n 1 ≤ . . . ≤ n r , is a filling of the corresponding Young diagram with elements from the alphabet A such that the entries are strictly increasing in the columns (from top to bottom) and weakly increasing in the rows (left to right).

Example 2.

T 1 = 5 1 2 3 4 2 1 3 2 3 4 , T 2 = 1 1 3 2 4 3 4
.

The key tableau T 1 is of column shape (4, 2, 4, 1), T 2 is an example for a semistandard Young tableau of column shape [START_REF] Bia Lynicki-Birula | Some properties of the decompositions of algebraic varieties determined by actions of a torus[END_REF][START_REF] Bourbaki | Groupes et algèbres de Lie, Chapitre IV: Groupes de Coxeter et systèmes de Tits. Chapitre V: Groupes engendrés par des réflexions. Chapitre VI: systèmes de racines[END_REF][START_REF] Gaussent | One-skeleton galleries, the path model and a generalization of Macdonald's formula for Hall-Littlewood polynomials[END_REF].

Definition 4. Let T be a key tableau. The associated word w T is the sequence (i 1 , . . . , i N ) of elements in A obtained from T by reading the entries in the key tableau boxwise, from top to bottom in each column, starting with the right most column. The map T → w T , which associates to a key tableaux the word in the alphabet A is not bijective, in general there are several key tableaux giving rise to the same word. All the following key tableaux have (1, 2, 3) as the associated word:

(2) 3 2 1 , 2 1 3 , 3 1 2 , 1 2 3
.

Remark 3. Let wT be the word obtained from w T by reading the word backwards, then wT is the column word (the product of the column words, read from left to right, in each column from bottom to top), which is Knuth equivalent (using the definition of the relation in [START_REF] Lascoux | Le monoïde plaxique[END_REF]) to the row word as defined in [START_REF] Lascoux | Le monoïde plaxique[END_REF]. The change in the definition of the Knuth relation is due to the fact that the "backwards reading map" w → w respects the Knuth relations for x < y < z but not for x = y < z respectively x < y = z (see [START_REF] Lascoux | Le monoïde plaxique[END_REF]), but it sends equivalence classes for the relations in (1) onto the equivalence classes for the Knuth relations as defined in [START_REF] Lascoux | Le monoïde plaxique[END_REF].

Definition 5. Two key tableaux T , T ′ are called Knuth equivalent: T ∼ K T ′ if and only if the two associated words w T and w T ′ are Knuth equivalent, i.e. w T ∼ K w T ′ .

Example 4. The tableaux in (2) are all Knuth equivalent because they have the same associated word, but also

T 1 = 2 1 3 ∼ K T 2 = 1 3 2 because w T 1 = (1, 3, 2) ∼ K w T 2 = (3, 1, 2).
Recall (see for example [START_REF] Fulton | Introduction to toric varieties[END_REF] or [START_REF] Littelmann | A Plactic Algebra for Semisimple Lie Algebras[END_REF]):

Theorem 1. i) Given a key tableau T , there exists a unique semistandard Young tableau T ′ such that T ∼ K T ′ . ii) Given a word w in the alphabet A, there exists a unique semistandard Young tableau T such that w ∼ K w T .

Remark 4. The unique semistandard Young tableau can be obtained from the given key tableau or word by using the Jeu de Taquin algorithm of Lascoux and Schützenberger or the bumping algorithm, see for example [START_REF] Fulton | Introduction to toric varieties[END_REF].

Galleries and keys

For 1 ≤ d ≤ n denote by I d,n the set of all strictly increasing sequences of length d:

I d,n = {i = (i 1 , . . . , i d ) | 1 ≤ i 1 < i 2 < . . . i d ≤ n}.
We fix a second alphabet

W = I 1,n ∪ I 2,n ∪ . . . ∪ I n-1,n ∪ I n,n .
We can identify A with I 1,n and hence view A as a subset of W. Definition 6. A gallery is a finite sequence γ = (i 1 , . . . , i r ) of elements in the alphabet W, r is called the length of the gallery. We say that the gallery is of type (d 1 , . . . , d r ) if

i 1 ∈ I d 1 ,n , i 2 ∈ I d 2 ,n , . . ., i r ∈ I dr,n .
By the inclusion of A ֒→ W we can identify words in the alphabet A with galleries of type (1, . . . , 1) (where the number of 1's is equal to the length of the word).

Definition 7. Given a key tableau T of column shape (n 1 , . . . , n r ), we associate to T the gallery γ T = (i 1 , . . . , i t ), of type (n 1 , . . . , n r ), where the sequence i ℓ = (j 1 , . . . , j d ) ∈ I d ℓ ,n , ℓ = 1, . . . , r, is obtained by reading the entries in the ℓ-th column (counted from right to left) of the key tableau T from top to bottom.

Example 5. For the key tableaux T 1 and T 2 in Example 2 we get the galleries [START_REF] Bourbaki | Groupes et algèbres de Lie, Chapitre IV: Groupes de Coxeter et systèmes de Tits. Chapitre V: Groupes engendrés par des réflexions. Chapitre VI: systèmes de racines[END_REF][START_REF] Fulton | Introduction to toric varieties[END_REF], (1, 2, 3, 4), ( 5)) , γ T 2 = ((3), [START_REF] Bia Lynicki-Birula | Some properties of the decompositions of algebraic varieties determined by actions of a torus[END_REF][START_REF] Gaussent | One-skeleton galleries, the path model and a generalization of Macdonald's formula for Hall-Littlewood polynomials[END_REF], [START_REF] Bia Lynicki-Birula | Some properties of the decompositions of algebraic varieties determined by actions of a torus[END_REF][START_REF] Bourbaki | Groupes et algèbres de Lie, Chapitre IV: Groupes de Coxeter et systèmes de Tits. Chapitre V: Groupes engendrés par des réflexions. Chapitre VI: systèmes de racines[END_REF][START_REF] Fulton | Introduction to toric varieties[END_REF][START_REF] Gaussent | One-skeleton galleries, the path model and a generalization of Macdonald's formula for Hall-Littlewood polynomials[END_REF]).

γ T 1 = ((1, 2, 3, 4),
Definition 8. Given a gallery γ = (i 1 , . . . , i r ) of type d = (d 1 , . . . , d r ), let T γ be the key tableau of column shape (d 1 , . . . , d r ) such that the entries in the j-th column (counted from right to left) are (counted from top to bottom) given by the sequence i j .

Example 6. For the gallery γ = ((3, 6, 7), ( 2), [START_REF] Bourbaki | Groupes et algèbres de Lie, Chapitre IV: Groupes de Coxeter et systèmes de Tits. Chapitre V: Groupes engendrés par des réflexions. Chapitre VI: systèmes de racines[END_REF][START_REF] Fulton | Introduction to toric varieties[END_REF][START_REF] Gaussent | One-skeleton galleries, the path model and a generalization of Macdonald's formula for Hall-Littlewood polynomials[END_REF], [START_REF] Bia Lynicki-Birula | Some properties of the decompositions of algebraic varieties determined by actions of a torus[END_REF][START_REF] Gaussent | One-skeleton galleries, the path model and a generalization of Macdonald's formula for Hall-Littlewood polynomials[END_REF]) we get the key tableau:

T γ = 1 2 4 3 4 2 3 6 7
.

One obtains a natural bijection between galleries and key tableaux, so in the following we identify often a gallery with its key tableau and vice versa. For example, the word w γ associated to a gallery is the word associated to the key tableau T γ , and we say that two galleries are Knuth equivalent if their corresponding key tableaux are Knuth equivalent.

The loop group G(K) and the Kac-Moody group L(G)

Let G = SL n (C). For a C-algebra R let G(R) be the set of R-rational points of G, i.e., the set of algebra homomorphisms from the coordinate ring C[G] → R. Then G(R) comes naturally equipped again with a group structure. In our case we can identify SL n (R) with the set of n × n-matrices with entries in R and determinant 1.

Denote

O = C[[t]
] the ring of formal power series in one variable and let K = C((t)) be its fraction field, the field of formal Laurent series. Denote v :

K * → Z the standard valuation on K such that O = {f ∈ K | v(f ) ≥ 0}.
The loop group G(K) is the set of K-valued points of G, we denote by G(O) its subgroup of O-valued points. The latter has a decomposition as a semi-direct product G×G 1 (O), where we view G ⊂ G(O) as the subgroup of constant loops and G 1 (O) is the subgroup of elements congruent to the identity modulo t. Note that we can describe G 1 (O) also as the image of sl n ⊗ C tC[[t]] via the exponential map (where sl n = Lie G).

The rotation operation γ :

C * → Aut (K), γ(z) f (t) = f (zt) gives rise to group auto- morphisms γ G : C * → Aut (G(K)), we denote L(G(K)) the semidirect product C * ×G(K).
The rotation operation on K restricts to an operation on O and hence we have a natural subgroup L(G(O)) := C * ×G(O) (for this and the following see [START_REF] Kumar | Kac-Moody Groups, their Flag Varieties and Representation Theory[END_REF], Chapter 13).

Let L(G) be the affine Kac-Moody group associated to the affine Kac-Moody algebra

L(g) = g ⊗ K ⊕ Cc ⊕ Cd,
where 0 → Cc → g ⊗ K ⊕ Cc → g ⊗ K → 0 is the universal central extension of the loop algebra g ⊗ K and d denotes the scaling element. We have corresponding exact sequences also on the level of groups, i.e., L(G) is a central extension of L(G(K))

1 → C * → L(G) pr -→L(G(K)) → 1
(see [START_REF] Kumar | Kac-Moody Groups, their Flag Varieties and Representation Theory[END_REF], Chapter 13). Fix as maximal torus T ⊂ G the diagonal matrices and fix as Borel subgroup B the upper triangular matrices in G. Denote by B -⊂ G the Borel subgroup of lower triangular matrices. We denote •, • the non-degenerate pairing between the character group Mor (T, C * ) of T and the group Mor (C * , T ) of cocharacters. We identify Mor (C * , T ) with the quotient T (K)/T (O), so we use the same symbol λ ∨ for the cocharacter and the point in G = G(K)/G(O).

Let N = N G (T ) be the normalizer in G of the fixed maximal torus T ⊂ G, we denote by W the Weyl group N/T of G. Let N K be the subgroup of G(K) generated by N and T (K), the affine Weyl group is defined as W a = N K /T ≃ W ×Mor (C * , T ).

Roots, weights and coweights

We use for the root system and the (abstract) weights and coweights the same notation as in [START_REF] Bourbaki | Groupes et algèbres de Lie, Chapitre IV: Groupes de Coxeter et systèmes de Tits. Chapitre V: Groupes engendrés par des réflexions. Chapitre VI: systèmes de racines[END_REF]: Let R n be the real vector space equipped with the canonical basis ǫ 1 , . . . , ǫ n and a scalar product (•, •) such that the latter basis is an orthonormal basis. Denote by V ⊂ R n the subspace orthogonal to ǫ 1 + . . . + ǫ n . The root system Φ ⊂ V and the coroot system Φ ∨ can be identified with each other:

Φ = {±(ǫ i -ǫ j ) | 1 ≤ i < j ≤ n} = {α ∨ = 2α (α, α) | α ∈ Φ} = Φ ∨ .
Hence we can also identify the root lattice R and the coroot lattice R ∨ . Similarly, we can identify the abstract weight lattice

X = {µ ∈ V | ∀α ∨ ∈ Φ ∨ : (µ, α ∨ ) ∈ Z} and the abstract coweight lattice X ∨ = {µ ∈ V | (µ, α) ∈ Z ∀α ∈ Φ}.
To avoid confusion between weights and coweights, we write λ ∈ X for the (abstract) weights and λ ∨ ∈ X ∨ instead of λ ∈ X ∨ for the (abstract) coweights.

For the group G = SL n (C) we have X = Mor (T, C * ), so the character group is the full abstract weight lattice, and the group of cocharacters is the coroot lattice R ∨ = Mor (C * , T ). For the adjoint group G ′ = P SL n (C) let p : SL n (C) → G ′ be the isogeny and set T ′ = p(T ). We have in this case R = Mor (T ′ , C * ), so the character group is the root lattice, and the group of cocharacters is the full lattice of abstract coweights X ∨ = Mor (C * , T ).

A basis of the root system is Π = {α i = ǫ i -ǫ i+1 | i = 1, . . . , n -1}, let Φ + be the corresponding set of positive roots. We often identify V with R n /R(ǫ 1 + . . . + ǫ n ), the description for the fundamental weights as ω i = ǫ 1 + . . . + ǫ i , i = 1, . . . , n -1 is to be understood with respect to this identification. The abbreviation

ǫ i = ǫ i 1 + . . . + ǫ i d and ǫ ∨ i = (ǫ i 1 + . . . + ǫ i d ) ∨ for i ∈ I d,n
is meant in the same way and provides a natural bijection between elements of I d,n and Weyl group conjugates of ω d respectively ω ∨ d . Given a root and coroot datum, we have the hyperplane arrangement defined by the set {(α, n) | α ∈ Φ, n ∈ Z} of affine roots. The couple (α, n) corresponds to the real affine root α + nδ with δ being the smallest positive imaginary root of the affine Kac-Moody algebra L(g). We associate to an affine root (α, n) the affine reflection s α,n :

x ∨ → x ∨ -((α, x ∨ ) + n)α ∨ for x ∨ ∈ V, and the affine hyperplane H α,n = {x ∨ ∈ V | (α, x ∨ ) + n = 0}. We write H + α,n = x ∨ ∈ V | α,
x ∨ + n ≥ 0 for the corresponding closed positive half-space and analogously

H - α,n = x ∨ ∈ V | α, x ∨ + n ≤ 0 for the negative half space.
Definition 9. Given a gallery γ = (i 1 , . . . , i r ) of type d, the associated polyline of type

(d 1 , . . . , d r ) in V is the sequence of coweights ϕ(γ) = (µ ∨ 0 , µ ∨ 1 , . . . , µ ∨ r ) defined by µ ∨ 0 = 0, µ ∨ 1 = ǫ ∨ i 1 , µ ∨ 2 = ǫ ∨ i 1 + ǫ ∨ i 2 , µ ∨ 2 = ǫ ∨ i 1 + ǫ ∨ i 2 + ǫ ∨ i 3 , . . . , µ ∨ r = ǫ ∨ i 1 + . . . + ǫ ∨ i r .
We often identify the sequence with the polyline joining successively the origin 0 with µ ∨ 1 , µ ∨ 1 with µ ∨ 2 , µ ∨ 2 with µ ∨ 3 etc. The last coweight µ ∨ r is called the coweight of the gallery. The Weyl group W is the finite subgroup of GL(V) generated by the reflections s α,0 for α ∈ Φ, the affine Weyl group W a is the group of affine transformations of V generated by the affine reflections s α,n for (α, n) ∈ Φ × Z.

A fundamental domain for the action of W on V is given by the dominant Weyl chamber

C + = {x ∨ ∈ V | (α, x ∨ ) ≥ 0, ∀α ∈ Φ + }. Similarly, the fundamental alcove ∆ f = {x ∨ ∈ V | 0 ≤ (α, x ∨ ) ≤ 1, ∀α ∈ Φ + }
is a fundamental domain for the action of W a on V.

The affine Graßmann variety

Let L(G) be the affine Kac-Moody group as in section 4. Recall the exact sequences

1 → C * → L(G) pr -→L(G(K)) → 1
(see [START_REF] Kumar | Kac-Moody Groups, their Flag Varieties and Representation Theory[END_REF], Chapter 13). Denote P 0 ⊂ L(G) the maximal parabolic subgroup pr -1 (L(G(O))). We have four incarnations of the affine Grassmann variety:

(3) G = G(K)/G(O) = L(G(K))/L(G(O)) = L(G)/P 0 = G(C[t, t -1 ])/G(C[t]).
Note that G(K) and G are ind-schemes and G(O) is a group scheme (see [START_REF] Kumar | Kac-Moody Groups, their Flag Varieties and Representation Theory[END_REF], [START_REF] Lusztig | Singularities, character formulas, and a q-analog of weight multiplicities[END_REF]).

Let now G ′ be a simple complex algebraic group with the same Lie algebra sl n as G and let p : G → G ′ be an isogeny with G ′ being simply connected. Then In particular, if we start with P SL n (C) (instead of SL n (C)), then Mor (T ′ , C * ) is the root lattice R and we can identify Mor (C * , T ′ ) with the full coweight lattice X ∨ :

G ′ (O) ≃ G ′ ×(G) 1 (O), the natural map p O : G(O) → G ′ (O)
X ∨ = Mor (C * , T ′ ) = Zω ∨ 1 ⊕ . . . ⊕ Zω ∨ n-1 .
The quotient Mor (C * , T ′ )/Mor (C * , T ) measures the difference between G and the affine Graßmann variety G ′ = G ′ (K)/G ′ (O). In fact, G is connected, and the connected components of G ′ are indexed by Mor (C * , T ′ )/Mor (C * , T ). The natural maps p K :

G(K) → G ′ (K) and p O : G(O) → G ′ (O) induce a G(K)-equivariant inclusion G ֒→ G ′ ,
which is an isomorphism onto the component of G containing the class of 1. Now G(K) acts via p K on all of G ′ , and each connected component is a homogeneous space for G(K), isomorphic to G(K)/Q for some parahoric subgroup Q of G(K) which is conjugate to G(O) by an (outer) automorphism. In the same way the action of L(G) on G extends to an action on G ′ , each connected component being a homogeneous space.

Let ev : G ′ (O) → G ′ be the evaluation maps at t = 0, and let B O = ev -1 (B) be the corresponding Iwahori subgroup. Denote by B the corresponding Borel subgroup of L(G). Recall the orbit decomposition (see for example [START_REF] Kumar | Kac-Moody Groups, their Flag Varieties and Representation Theory[END_REF]):

G ′ = µ ∨ ∈X ∨+ G(O)µ ∨
where X ∨+ denotes the set of dominant (abstract) coweights.

Throughout the remaining part of the paper, we study for G = SL n (C) the action of the groups G(O), G(K) (and other relevant subgroups of G(K)) on the affine Graßmann variety G ′ for G ′ = P SL n .

For a dominant coweight λ ∨ ∈ X ∨ + denote by X λ ∨ the G(O)-stable Schubert variety

X λ ∨ = G(O)λ ∨ ⊆ G ′ .

Galleries and subgroups

Let γ = (i 1 , . . . , i r ) be a gallery of type d and denote ϕ(γ) = (µ ∨ 0 , µ ∨ 1 , . . . , µ ∨ r ) the associated polyline. Let [µ ∨ j-1 , µ ∨ j ] be the convex hull of the two vertices. We associate to the gallery and the vertices on the polyline some subgroups: Denote P µ ∨ j the parabolic subgroup of L(G) containing C * ×T and the root subgroups associated to the real roots

(4) Φj = {(α, n) | µ ∨ j ∈ H + α,n }, j = 0, . . . , r. Denote Q µ ∨
j the parabolic subgroups of L(G) containing C * ×T and the root subgroups associated to the real roots

(5) Φj,j+1 = {(α, n) | [µ ∨ j , µ ∨ j+1 ] ⊂ H + α,n }, j = 0, . . . , r -1, Note that P µ ∨ j ⊃ Q µ ∨ j ⊂ P µ ∨ j+1 .
Another important subgroup of P µ ∨ j is generated by its root subgroups corresponding to roots which are negative in the classical sense:

(6) U - µ ∨ j = U (β,m) | β ≺ 0, (β, m) ∈ Φj ⊂ P µ ∨ j , j = 0, . . . , r.
The following set of roots is relevant later for the description of certain cells. Let

Ψ γ,j = {(α, n) | α ≻ 0, µ ∨ j ∈ H α,n , [µ ∨ j , µ ∨ j+1 ] ⊆ H - α,n } and set U - γ,j = (α,n)∈Ψ γ,j U (-α,-n) ⊂ U - µ ∨ j .
We associate to the gallery the product of root subgroups

U - γ = U - γ,0 × U - γ,1 × • • • × U - γ,r-1 .

Galleries and Bott-Samelson varieties

For a gallery γ = (i

1 , i 2 , . . . , i r ) of type d = (d 1 , . . . , d r ) let ϕ(γ) = (µ ∨ 0 , . . . , µ ∨ r ) be the associated polyline. Recall that P µ ∨ j ⊃ Q µ ∨ j ⊂ P µ ∨ j+1
, so we can associate to γ the Bott-Samelson variety [START_REF] Kashiwara | Crystalizing the q-analog of Universal Enveloping Algebras[END_REF] Σ

d = P µ ∨ 0 × Q µ ∨ 0 P µ ∨ 1 × Q µ ∨ 1 × . . . × Q µ ∨ r-1 P µ ∨ r /P µ ∨ r , which is defined as the quotient of P µ ∨ 0 × P µ ∨ 1 × . . . × P µ ∨ r by Q µ ∨ 0 × Q µ ∨ 1 × . . . × Q µ ∨
r-1 × P µ ∨ r with respect to the action given by: (q 0 , q 1 , ..., q r-1 , q r ) • (p 0 , p 1 , ..., p r ) = (p 0 q 0 , q -1 0 p 1 q 1 , ..., q -1 r-1 p r q r ). The fibred product Σ d is a smooth projective complex variety, its points are denoted by [p 0 , . . . , p r ].

Corresponding to the parabolic subgroups Q µ ∨ j , P µ ∨ j of L(G) one has the parahoric subgroups

P µ ∨ j , Q µ ∨ j of G(K) such that P µ ∨ j = pr -1 (C * ×P µ ∨ j ) and Q µ ∨ j = pr -1 (C * ×Q µ ∨ j ). We get another description of Σ d as (8) Σ d = P µ ∨ 0 × Q µ ∨ 0 P µ ∨ 1 × Q µ ∨ 1 × . . . × Q µ ∨ r-1 P µ ∨ r /P µ ∨ r . Set F γ = L(G)/P µ ∨ 0 × L(G)/P µ ∨ 1 × • • • × L(G)/P µ ∨
r and consider the natural morphism ι : Σ d → F γ given by sending the class [p 0 , p 1 , . . . , p r ] to the sequence

(P µ ∨ 0 , p 0 Q µ ∨ 0 p -1 0 , p 0 P µ ∨ 1 p -1 0 , p 0 p 1 Q µ ∨ 1 p -1 1 p -1 0 , . . . , p 0 • • • p r-1 P r p -1 r-1 • • • p -1 0 ) ∈ F γ .
The image of Σ d can be described as the set of sequences of parabolic subgroups (see for example [START_REF] Gaussent | One-skeleton galleries, the path model and a generalization of Macdonald's formula for Hall-Littlewood polynomials[END_REF]) satisfying the following inclusion relations:

(9)      (P µ ∨ 0 , Q 0 , . . . , P r ) | P µ ∨ 0 ⊃ Q 0 ⊂ P 1 ⊃ . . . ⊂ P r P j is conjugate to P µ ∨ j ,∀j = 1, . . . , r Q j is conjugate to Q µ ∨ j ∀j = 0, . . . , r -1.     
The morphism ι is an isomorphism onto the image. If γ ′ is a gallery of the same type as γ with associated polyline ϕ(γ

′ ) = (µ ′ ∨ 0 , . . . , µ ′ ∨ r ), then µ ∨ 0 = µ ′ ∨ 0 = 0, µ ′ ∨ 1 is conjugate to µ ∨
1 by an element τ 0 in the Weyl group of P µ 0 and hence

P µ ′ 1 = τ 0 P µ 1 τ -1 0 , µ ′ ∨ 2 is conjugate to τ 0 (µ ∨
2 ) by an element τ 1 in the Weyl group of P µ ′ 1 = τ 0 P µ 1 τ -1 0 and hence

P µ ′ 2 = τ 1 τ 0 P µ 2 τ -1 0 τ -1 1
etc. So γ and γ ′ define in (9) the same variety and hence Σ d depends only on the type d and not on the gallery. We say that we consider Σ d with center γ if we want to emphasize that the parabolic subgroups in [START_REF] Kashiwara | Crystalizing the q-analog of Universal Enveloping Algebras[END_REF] correspond to the coweights lying on the polyline associated to γ.

For a fixed type d let T 0 be the unique key tableau of column shape d having as filling only 1's in the top row, 2's in the second row etc. Denote by γ 0 the associated gallery and let ϕ(γ 0 ) = (µ ∨ 0 , . . . , µ ∨ r ) be the associated polyline. The variety Σ d is by ( 8) naturally endowed with a T -action.

Lemma 1. We consider Σ d with center γ 0 . There exists a natural bijection between Tfixed points in Σ d and galleries of type d such that the gallery γ 0 corresponds to the class [1, . . . , 1] in

P µ ∨ 0 × Q µ ∨ 0 . . . × Q µ ∨ r-1 P µ ∨ r /P µ ∨ r .
Proof. We have a sequence of projections of the fibered spaces:

(10) Σ d φ r-1 -→P µ ∨ 0 × Q µ ∨ 0 . . . × Q µ ∨ r-3 P µ ∨ r-2 /Q µ ∨ r-2 φ r-2 -→ • • • φ 2 -→P µ ∨ 0 × Q µ ∨ 0 P µ ∨ 1 /Q µ ∨ 1 φ 1 -→P µ ∨ 0 /Q µ ∨ 0
such that the fibres of φ j are isomorphic to P µ ∨ j /Q µ ∨ j . The fibrations are locally trivial in the Zariski topology and equivariant with respect to the T -action. It is now easy to see that the T -fixed points in Σ d are in a natural one-to one correspondence with T -fixed points in

P µ ∨ 0 /Q µ ∨ 0 × P µ ∨ 1 /Q µ ∨ 1 × . . . × P µ ∨ r-1 /Q µ ∨ r-1 . Let L µ ∨ j ⊂ P µ ∨ j be the Levi subgroup containing C * ×T , then the semisimple part SL µ ∨ j of L µ ∨ j is isomorphic to SL n (C).
With respect to this isomorphism, the intersection

P = SL µ ∨ j ∩ Q µ ∨ j is a maximal parabolic subgroup of SL µ ∨ j such that P µ ∨ j /Q µ ∨ j ≃ SL µ ∨ j /P ≃ SL n (C)/P ω ∨ d j
.

The T -fixed points of this variety are naturally indexed by elements in I d j ,n , j = 1, . . . , r, proving the claim.

MV-cycles and galleries

We fix a type d = (d 1 , . . . , d r ). Since the Bott-Samelson variety Σ d depends only on the type and not on the choice of gallery, we fix during this section for convenience γ such that the associated polyline is wrapped around the fundamental alcove, i.e. if γ = (i 1 , . . . , i r ) and ϕ(γ) = (µ ∨ 0 = 0, µ ∨ 1 , . . . , µ ∨ r ), then all the coweights µ ∨ 0 , µ ∨ 1 , . . . , µ ∨ r are vertices of the fundamental alcove. Since the type of the gallery is fixed, there exists only one gallery of this type with this property.

Set λ ∨ = r j=1 ω ∨ d j and consider the Bott-Samelson variety of center γ:

Σ d = P µ ∨ 0 × Q µ ∨ 0 P µ ∨ 1 × Q µ ∨ 1 × . . . × Q µ ∨ r-1 P µ ∨ r /P µ ∨ r .
Note that for this choice of γ all the associated parabolic subgroups are standard parabolic subgroups, i.e. B ⊂ P µ ∨ j , Q µ ∨ j . The last parabolic subgroup P µ ∨ r in the fibered product corresponds to a maximal standard parabolic subgroup of L(G). In G ′ , this group corresponds to the point µ ∨ r (i.e. P µ ∨ r ⊂ L(G) is the stabilizer of this point with respect to the action of L(G) on G ′ ), so we get a canonical map

π : Σ d = P µ ∨ 0 × Q µ ∨ 0 P µ ∨ 1 × Q µ ∨ 1 × . . . × Q µ ∨ r-1 P µ ∨ r /P µ ∨ r → G ′ [p 0 , . . . , p r-1 , p r ] → p 0 • • • p r-1 µ ∨ r .
It is well known that the image π(Σ d ) is the Schubert variety X λ ∨ , and the map is in fact a desingularization (see for example [START_REF] Gaussent | One-skeleton galleries, the path model and a generalization of Macdonald's formula for Hall-Littlewood polynomials[END_REF]).

Let η : C * → T be a generic anti-dominant one parameter subgroup. Σ d is a smooth projective variety endowed with a T -action and hence a η-action. Since η is generic, the T -fixed points are the same as the η-fixed points, so the latter are naturally indexed by galleries of type d (see Lemma 1). To each fixed point y ζ corresponding to a gallery ζ of type d, we can associate the Bia lynicki-Birula cell [START_REF] Bia Lynicki-Birula | Some properties of the decompositions of algebraic varieties determined by actions of a torus[END_REF]:

C ζ = {x ∈ Σ d | lim t→0 η(t)x = ζ}.
Recall that Σ d is the disjoint union C ζ , where ζ is running over the set of all galleries of type d.

The Schubert variety X λ ∨ has a similar decomposition, but which is in general not given by cells. Let U -be the unipotent radical of B -. Given a coweight µ ∨ , the closure of an irreducible component of (

U -(K).µ ∨ ) ∩ (G(O).λ ∨ ) ⊂ G ′ is called a Mirković-Vilonen cycle, or short just MV-cycle [17] of coweight µ ∨ in X λ ∨ .
It is known that the intersection is nonempty if and only if in the finite dimensional irreducible representation of SL n (C) (viewed as Langlands dual group of P SL n (C)) of highest weight λ ∨ the weight space corresponding to µ ∨ is non-zero. Further, the number of irreducible components is equal to the dimension of this weight space. One has a disjoint union

X λ ∨ = µ ∨ ∈X ∨ (X λ ∨ ∩ U -(K).µ ∨ ),
and since lim t→0 η(t)uη(t) -1 = 1 for all u ∈ U -(K), it follows that

X λ ∨ ∩ U -(K).µ ∨ = {y ∈ X λ ∨ | lim t→0 η(t)y = µ ∨ }. The desingularization map π : Σ d → X λ ∨ is T -equivariant, hence if µ ∨ is the coweight of a gallery γ of type d, then the image π(C ζ ) of the cell is contained in X λ ∨ ∩ U -(K).µ ∨ .
Since the image is irreducible, it is contained in some MV-cycle.

Main Theorem

Let γ be a gallery of type d with associated polyline ϕ(γ) = (µ ∨ 0 , . . . , µ ∨ r ), set λ ∨ = r j=1 ω ∨ d j and denote by π d : Σ d → X λ ∨ the desingularization map. Let T be the unique semistandard Young tableau such that the words w γ and w T are Knuth equivalent. Let c = (c 1 , . . . , c s ) be the shape of T , set ν ∨ = s j=1 ω ∨ c j and let X ν ∨ ⊆ X λ ∨ be the corresponding Schubert variety.

Theorem 2.

a) The closure

π d (C γ ) ⊆ X λ ∨ is a MV-cycle for the (possibly smaller) Schubert variety X ν ∨ ⊆ X λ ∨ . The weight of the MV-cycle is µ ∨ r . b) Given a second gallery γ ′ of type d ′ , set λ ′ ∨ = r j=1 ω ∨ d ′ j and let π d ′ : Σ d ′ → X λ ′∨ be the desingularization map. The following conditions are equivalent: i) γ and γ ′ are Knuth equivalent. ii) π d (C γ ) = π d ′ (C γ ′ )
As a consequence we get a geometric interpretation of the Knuth relations:

Corollary 1. For two words w 1 , w 2 of the same length N in the alphabet A the following conditions are equivalent: i ) w 1 and w 2 are Knuth equivalent ii ) π(C w 1 ) = π(C w 2 ), where π is the canonical map π : Σ N ǫ ∨ 1 → X N ǫ ∨ 1 , and the words w 1 , w 2 are viewed as galleries of type (1, 1, . . . , 1) N . The proof will be given in section 13.

The cell C γ

We recall a description of the cell and determine its dimension. For a gallery γ =

(i 1 , i 2 , . . . , i r ) of type d = (d 1 , . . . , d r ) set λ ∨ = r j=1 ω ∨ d j . Let ϕ(γ) = (µ ∨ 0 , µ ∨ 1 , . . . , µ ∨ r
) be the associated polyline and denote by Σ d the associated Bott-Samelson variety of center γ. The coweights µ ∨ j and µ ∨ j+1 are joined by the segment [µ ∨ j , µ ∨ j+1 ], j = 0, . . . , r -1. Let H α,n , α > 0, be a hyperplane such that µ ∨ j ∈ H α,n . We say that γ crosses the wall

H α,n in µ ∨ j in the positive (negative) direction if [µ ∨ j , µ ∨ j+1 ] ⊂ H - α,n (respectively [µ ∨ j , µ ∨ j+1 ] ⊂ H + α,n ). Set ♯ + (γ) = r-1 j=0 (♯ positive wall crossings in µ ∨ j ) = r-1 j=0 |Ψ γ,j |; ♯ -(γ) = r-1 j=0 (♯ negative wall crossings in µ ∨ j ); ♯ ± (γ) = ♯ + (γ) + ♯ -(γ).
The value of the sum ♯ ± (γ) depends, by definition, only on the type of the gallery and not on the actual choice of the gallery. It is easy to check that

♯ ± (γ) = (λ ∨ , 2ρ ∨ ),
where ρ ∨ is the sum of the fundamental coweights.

The following proposition is proved in [START_REF] Gaussent | One-skeleton galleries, the path model and a generalization of Macdonald's formula for Hall-Littlewood polynomials[END_REF], Proposition 4.19.

Proposition 1. The map

U - γ,0 × U - γ,1 × U - γ,2 × . . . × U - γ,r-1 → Σ d , (u 0 , . . . , u r-1 ) → [u 0 , . . . , u r-1 , 1]
,

is an isomorphism onto the cell C γ . In particular, ♯ + (γ) is the dimension of the cell.

The image of the map

χ : U - µ ∨ 0 × U - µ ∨ 1 × . . . × U - µ ∨ r-1 → Σ d , (u 0 , . . . , u r-1 ) → [u 0 , . . . , u r-1 , 1] ,
is obviously (by the choice of η) a subset of

C γ . But U - γ,j is a subset of the group U - µ ∨ j , so
we get as an immediate consequence:

Corollary 2. The map χ has as image the cell C γ .

The description of the cell in the proposition above has as an immediate consequence:

Corollary 3. π(C γ ) = U - γ,0 U - γ,1 U - γ,2 • • • U - γ,r-1 .µ ∨ r = U - µ ∨ 0 U - µ ∨ 1 • • • U - µ ∨ r-1 .µ ∨ r .
Lemma 2. The dimension of the cell C γ depends only on the coweight of the gallery. More precisely, dim

C γ = ♯ + (γ) = (λ ∨ + µ ∨ r , ρ ∨ ).
Proof. The proof is by induction on the height of λ ∨ -µ ∨ r . If λ ∨ = µ ∨ r , then there exists only one gallery of this type with coweight λ ∨ , it must be γ = (ω ∨ d 1 , . . . , ω ∨ dr ). The hyperplanes crossed positively are exactly all the affine hyperplanes lying between the origin and λ ∨ , for each positve root there are exactly (λ ∨ , α ∨ ) such hyperplanes and hence for this gallery we get

♯ + (γ) = α∈Φ + (λ ∨ , α ∨ ) = (λ ∨ , 2ρ ∨ ) = (2λ ∨ , ρ ∨ ),
proving the claim in this case. Suppose now the claim holds if the height of λ ∨ -coweight of the gallery is strictly smaller than s. Suppose γ = (i 1 , . . . , i r ) is a gallery such that the height of λ ∨ -µ ∨ r is equal to s and s > 0. Then there exists a simple root α and 1

≤ t ≤ r such that ǫ ∨ i t = ω ∨ dt and s α (ǫ ∨ i t ) = ǫ ∨ i t + α ∨ . Let i ′ t be such that ǫ i ′ t = ǫ ∨ i t
+ α ∨ and let γ ′ be the gallery

γ ′ = (i 1 , . . . , i t-1 , i ′ t , i t+1 , . . . , i r ),
and denote by µ ′ ∨ r the coweight of γ ′ . Then the height of λ ∨ -µ ′ ∨ r is equal to s -1 and hence ♯ + (γ ′ ) = (λ ∨ + µ ′ ∨ r , ρ ∨ ). It follows:

♯ + (γ) = r j=1 ♯Ψ γ,j = ( r j=1 ♯Ψ γ ′ ,j ) + 1 = (λ ∨ + µ ′ ∨ r , ρ ∨ ) + 1 = (λ ∨ + µ ′ ∨ r , ρ ∨ ) + (α ∨ , ρ ∨ ) = (λ ∨ + µ ∨ r , ρ ∨ )
12. Tail of a gallery

Let γ be a gallery of type d. Let T γ be the corresponding key tableau. In Section 2, we have associated a to a key tableau a word in the alphabet A, we just write w γ for the word associated to T γ .

Corresponding to the type, we have the associated Bott-Samelson variety Σ d , the dominant coweight λ ∨ = ω ∨ d j and the desingularization map:

π 1 : Σ d → X λ ∨ .
And, associated to the gallery, we have the cell C γ ⊂ Σ d . Recall that the map γ → w γ which associates to a gallery γ the word w γ in the alphabet A is far from being injective. Let us first show the following.

Proposition 2. The image Z γ = π 1 (C γ ) depends only on the word w γ .

The proof will be given at the end of this section. Set Z γ = π 1 (C γ ) and note that pr(U -

µ ∨ 0 ) ⊆ U -(O) = U -(K) ∩ SL
Lemma 3. Z γ is U - µ ∨ 0 -stable.
We want to reformulate Lemma 3 to make it available in a more general situation. Let γ = (i 1 , i 2 , . . . , i r ) be a gallery of type d, denote by ϕ(γ) = (µ ∨ 0 , . . . , µ ∨ r ) the associated polyline. For k ≥ 0 consider the tail γ ≥k = (i k , . . . , i r ) of the gallery γ, denote by ϕ(γ ≥k ) = (µ ′ ∨ 0 , . . . , µ ′ ∨ r-k ) the associated polyline and by ϕ shif t (γ ≥k ) = (µ ∨ k , . . . , µ ∨ r ) the shifted polyline (starting in µ ∨ k instead of 0) of the tail gallery. Denote by Z γ ≥k the image of the cell C γ ≥k ⊂ Σ (d k ,...,dr) :

Z γ ≥k = U - γ ≥k ,0 • • • U - γ ≥k ,r-k-1 .µ ′ ∨ r-k = U - µ ′∨ 0 U - µ ′∨ 1 • • • U - µ ′∨ r-k-1 .µ ′ ∨ r-k
and let Z ≥k γ be the truncated image:

Z ≥k γ = U - γ,k U - γ,k+1 • • • U - γ,r-1 .µ ∨ r . Proposition 3. Z ≥k γ is U - µ ∨ k -stable.
Proof. Let T ′ ⊂ P SL n (C) be as in section 6. Corresponding to a coweight µ ∨ k let t µ ∨ k be the translation in the extended affine Weyl group. The translations act on the affine roots by shifts:

t µ ∨ k : (β, ℓ) → (β, ℓ + (µ ∨ k , β)) and t -µ ∨ k : (β, k) → (β, ℓ -(µ ∨ k , β)
). Denote by U β : C((t)) → G(K) the root subgroup corresponding to the root β. Note that the conjugation by t µ ∨ k acts on the root subgroups by a shift: given a ∈ C and ℓ ∈ Z, then

t µ ∨ k U β (at ℓ )(t µ ∨ k ) -1 = U β (at ℓ+(µ k ,β)
), so the conjugation on the group and the translation on the coweight lattice correspond to each other. It follows: [START_REF] Lascoux | Cyclic permutations on words, tableaux and harmonic polynomials[END_REF]

t µ ∨ k .Z γ ≥k = t µ ∨ k .(U - γ ≥k ,0 • • • U - γ ≥k ,r-k-1 .µ ′ ∨ r-k ) = U - γ,k U - γ,k+1 • • • U - γ,r-1 .µ ∨ r = Z ≥k γ . By Lemma 3, Z γ ≥k is stabilized by U - γ,0 , so t µ ∨ k U - γ,0 (t µ ∨ k ) -1 = U - γ,k stabilzes Z ≥k γ .
Proof of Proposition 2. Let w γ be the word (in the alphabet A) associated to γ. Since A ⊂ W, we can view w γ also as a gallery of type 1 N = (1, 1, . . . , 1),where N = r j=1 d j is the length of the word. For γ = (i 1 , i 2 , . . . , i r ) let i 1 = (j 1 , . . . , j d 1 ), i 2 = (h 1 , . . . .h d 2 ) etc. and set η ∨ 0,0 = 0 and

η ∨ 0,1 = ǫ ∨ j 1 , η ∨ 0,2 = η ∨ 0,1 + ǫ ∨ j 2 , . . . , η ∨ 0,d 1 -1 = η ∨ 0,d 1 -2 + ǫ ∨ j d 1 -1 , η ∨ 1,0 = ǫ i 1 , η ∨ 1,1 = ǫ i 1 + ǫ ∨ h 1 , . . . . Let (η ∨ 0,0 , η ∨ 0,1 , η ∨ 0,2 , . . . , η ∨ 0,d 1 -1 , η ∨ 1,0 , η ∨ 1,1 , . . . , η ∨ 1,d 2 -1 , . . . , η ∨ r-1,dr-1 η ∨ r,0
) be the polyline associated to w γ (viewed as a gallery of type 1 N ). The indexing is such that η ∨ k,0 = µ ∨ k . We use now Corollary 3 and compare the product of unipotent groups U - γ,k and the unipotent group U -

ℓ -ǫ ℓ ′ , 1 ≤ ℓ < ℓ ′ ≤ n, denote by p k ℓ,ℓ ′ the integer such that µ ∨ k ∈ H ǫ ℓ -ǫ ℓ ′ ,-p k ℓ,ℓ ′ . Let i k+1 = (j 1 , . . . , j d k )
, then we have for k = 0, . . . , r -1:

U - γ,k = j 1 <m≤n m =j 2 ,...,j d k U -ǫ j 1 +ǫm,p k j 1 ,m j 2 <m≤n m =j 3 ,...,j d k U -ǫ j 2 +ǫm,p k j 2 ,m • • • j d k <m≤n U -ǫ j d k +ǫm,p k j d k ,m . Note that µ ∨ k ∈ H ǫ j t -ǫm,-p k ℓ,m if and only if µ ∨ k + ǫ ∨ j 1 + . . . + ǫ ∨ j t-1 ∈ H ǫ j t -ǫm,-p k ℓ,m
, and hence

U - wγ,(k,0) • • • U - wγ,(k,d k -1) = j 1 <m≤n U -ǫ j 1 +ǫm,p k j 1 ,m j 2 <m≤n U -ǫ j 2 +ǫm,p k j 2 ,m • • • j d k <m≤n U -ǫ j d k +ǫm,p k j d k ,m . It follows that U - γ,k ⊆ U - wγ ,(k,0) • • • U - wγ,(k,d k -1) ⊆ U -
Z γ = U - γ,0 U - γ,1 • • • U - γ,r-1 .µ ∨ r ⊆ Z wγ = U - wγ,(0,0) U - wγ,(0,1) • • • U - wγ,(r-1,dr-1) .µ ∨ r ⊆ Z γ = U - µ ∨ 0 U - µ ∨ 1 • • • U - µ ∨ r-1 .µ ∨ r
This shows that Z γ depends only on the word w γ , which proves the proposition.

Proof of Theorem 2

We have seen that the image π(C γ ) of a cell depends only on the associated word, to prove part b) of Theorem 2 it remains to show that the closure of the image depends only on the equivalence class of the associated word modulo the Knuth relation. We discuss first the simplest case at length. The proof in the general case is very similar, we leave the details to the reader. As in the section before, we view a word as a gallery of type (1, 1, . . . , 1).

Lemma 4. If w 1 = yxz and w 2 = yzx, x ≤ y < z, then π(C w 1 ) = U - w 1 ,0 U - w 1 ,1 U - w 1 ,2 • (ǫ x + ǫ y + ǫ z ) ∨ and π(C w 2 ) = U - w 2 ,0 U - w 2 ,1 U - w 2 ,2 • (ǫ x + ǫ y + ǫ z ) ∨ have a common dense subset.
Proof. Assume first x < y < z. The key associated to w 1 is T 1 = z x y , let T ′ 1 be the key x y z having the same associated word. Set ν ∨ = (ǫ x + ǫ y + ǫ z ) ∨ , then we have:

π(C w 1 ) = U - γ T 1 • ν ∨ = U - γ T ′ 1 • ν ∨ = ( ℓ>y U (-ǫy+ǫ ℓ ,0) )( k>x k =y,z U (-ǫx+ǫ k ,0) )U (-ǫx+ǫy,-1) ( m>z U (-ǫz+ǫm,0) ) • ν ∨ = ( ℓ>y ℓ =z U (-ǫy+ǫ ℓ ,0) )U (-ǫy+ǫz,0) ( k>x k =y,z U (-ǫx+ǫ k ,0) )U (-ǫx+ǫy,-1) ( m>z U (-ǫz+ǫm,0) ) • ν ∨ = ( ℓ>y ℓ =z U (-ǫy+ǫ ℓ ,0) )( k>x k =y,z U (-ǫx+ǫ k ,0) )U (-ǫy+ǫz,0) U (-ǫx+ǫy,-1) ( m>z U (-ǫz+ǫm,0) ) • ν ∨
The first equality is implied by Corollary 3, the second follows from Proposition 2, the third equation is just expressing U γ T ′ 1 as a product of the unipotent factors corresponding to the vertices of the gallery γ T ′ 1 , the fourth equation is obtained by separating U (-ǫy+ǫz,0) from the remaining factors of the product ( ℓ>y ℓ =z U (-ǫy+ǫ ℓ ,0) ), which is possible since all the factors of this product commute. The last equality is obtained by switching the commuting factors U (-ǫy+ǫz,0) and ( k>x k =y,z U (-ǫx+ǫ k ,0) ).

The terms m>z U (-ǫz+ǫm,0) and U (-ǫx+ǫy,-1) commute, so we have

π(C w 1 ) = ( ℓ>y ℓ =z U (-ǫy+ǫ ℓ ,0) )( k>x k =y,z U (-ǫx+ǫ k ,0) )U (-ǫy+ǫz,0) ( m>z U (-ǫz+ǫm,0) )U (-ǫx+ǫy,-1) • ν ∨ .
Recall that for m > z and s, t ∈ C (see [START_REF] Steinberg | Lectures on Chevalley groups[END_REF] or [START_REF] Tits | Uniqueness and presentation of Kac-Moody groups over fields[END_REF]): U (-ǫy+ǫz,0) (s)U (-ǫz+ǫm,0) (t) = U (-ǫy+ǫm,0) (st)U (-ǫz+ǫm,0) (t)U (-ǫy+ǫz,0) (s) Now U (-ǫy+ǫm,0) , m > z, commutes with U (-ǫx+ǫ k ,0) , k = y, z, U (-ǫy+ǫz,0) and U (-ǫz+ǫq,0) , z < q, so we can join the factor U (-ǫy+ǫm,0) (st) into the first product (where this unipotent subgroup occurs already with a free parameter) and obtain: On the other side, the key associated to w 2 is T 2 = y x z . Let T ′ 2 be the key x z y having the same associated word. Then, we have:

π(C w 1 ) = (
π(C w 1 ) = U - γ T 1 • ν ∨ = U - γ T ′ 1 • ν ∨ = ( m>z U (-ǫz+ǫm,0) )( ℓ>x ℓ =z,y
U (-ǫx+ǫ ℓ ,0) )U (-ǫx+ǫz,-1)

( k>y k =z U (-ǫy+ǫ k ,0) )U (-ǫy+ǫ k ,0) • ν ∨
The same kind of computations as in the proof of Lemma 4 shows that those two images share a common dense subset. Now assume that x < y = y. Again, using an analogous tableaux of shape d and coweight µ ∨ and the MV-cycles in X ν ∨ of coweight µ ∨ . Since an arbitrary gallery is Knuth equivalent to a unique semistandard Young tableau, this proves the direction i)⇐ii) of the equivalence and also part a) of the theorem.

Definition 2 .

 2 A key diagram of column shape (n 1 , . . . , n r ) is a sequence of columns of boxes aligned in the top row, having n 1 boxes in the right most column, n 2 boxes in the second right most column etc. The key diagram is called a Young diagram if n 1 ≤ . . . ≤ n r .

Example 3 .

 3 For the key tableaux T 1 and T 2 in Example 2 we get w T 1 = (1, 2, 3, 4, 2, 3, 1, 2, 3, 4, 5), w T 2 = (3, 1, 4, 1, 2, 3, 4).

  is surjective and has the same kernel as p. Let T ′ be a maximal torus such that p(T ) = T ′ and consider the character group Mor (T ′ , C * ) the group Mor (C * , T ′ ) of cocharacters. The map p : T → T ′ induces an inclusion Mor (C * , T ) ֒→ Mor (C * , T ′ ).

  n (O) by definition. Recall that Σ d inherits by (8) naturally an SL n (O)-action, and the map π 1 is equivariant with respect to this action. The cell C γ is not SL n (O)-stable, but the cells are stable under the action of U -(O): recall that C γ = {z ∈ Σ d | lim t→0 η(t).z = γ} for a fixed anti-dominant one-parameter subgroup η : C * → T . Since lim t→0 η(t)uη(t) -1 = 1, it follows that u.z ∈ C γ for all z ∈ C γ and all u ∈ U -(O). By the definition of Ψ 0 we have as an immediate consequence:

  gallery γ and the product of unipotent groups U - wγ,(k,0) • • • U - wγ,(k,d k -1) associated to the gallery w γ . For a positive root ǫ

  µ k and hence by Corollary 3:

1 • ν ∨ = U - γ T ′ 1 •Lemma 5 .

 115 ℓ>y ℓ =z U (-ǫy+ǫ ℓ ,0) )( k>x k =y,zU (-ǫx+ǫ k ,0) )( m>z U (-ǫz+ǫm,0) )U (-ǫy+ǫz,0) U (-ǫx+ǫy,-1) • ν ∨ . Now for s, t ∈ C we have U (-ǫy+ǫz,0) (s)U (-ǫx+ǫy,-1) (t) = U (-ǫx+ǫy,-1) (t)U (-ǫx+ǫz,-1) (st)U (-ǫy+ǫz,0) (s).Since U (-ǫy+ǫz,0) (s) ⊆ P ν ∨ for all s ∈ C, we can omit this term and see that the set( ℓ>y ℓ =z U (-ǫy+ǫ ℓ ,0) )( k>x k =y,z U (-ǫx+ǫ k ,0) )( m>z U (-ǫz+ǫm,0) )U (-ǫx+ǫy,-1) ( * )U (-ǫx+ǫz,-1) ( * * ) • ν ∨for parameters * , * * = 0 forms a dense subset in π(C w 1 ). After switching the commuting factors ( k>x k =y,z U (-ǫx+ǫ k ,0) ) and ( m>z U (-ǫz+ǫm,0) ) we see that( ℓ>y ℓ =z U (-ǫy+ǫ ℓ ,0) )( m>z U (-ǫz+ǫm,0) )( k>x k =y,z U (-ǫx+ǫ k ,0) )U (-ǫx+ǫy,-1) ( * )U (-ǫx+ǫz,-1) ( * * ) • ν ∨ is also a dense subset in π(C w 2 ) = U - ǫy+ǫ ℓ ,0) )( m>z U (-ǫz+ǫm,0) )( k>x k =y,z U (-ǫx+ǫ k ,0) ) U (-ǫx+ǫy,-1) U (-ǫx+ǫz,-1) • ν ∨ ,where T 2 = x z y and T ′ 2 is the keyx y z having the same associated word, which finishes the proof in this case.Assume now x = y < z. The key associated to the word w 1 = xxz is a T 1 = z x x , let T ′ 1 be the keyx x z . Set ν ∨ = 2ǫ ∨ x + ǫ ∨ z .We get as image of the associated cell:π(C w 1 ) = U - γ T ν ∨ = k>x U (-ǫx+ǫ k ,0) ℓ>x ℓ =z U (-ǫx+ǫ ℓ ,1) m>z U (-ǫz+ǫm,0) • ν ∨ .The key associated to the word w 2 = xzx is T 2 = x z x and we get as image of the associated cellπ(C w 2 ) = U - T 2 • ν ∨ = k>x U (-ǫx+ǫ k ,0) m>z U (-ǫz+ǫm,0) ℓ>x U (-ǫx+ǫ ℓ ,1) • ν ∨ But U (-ǫx+ǫz,1) ⊂ P ν ∨ (since (2ǫ ∨ x + ǫ ∨ z , ǫ x -ǫ z ) -1 = 0) and the subgroups U (-ǫx+ǫ ℓ ,1) and U (-ǫz+ǫm,0) commute for ℓ > x, ℓ = z and m > z, soπ(C w 2 ) = U - T 2 • ν ∨ = k>x U (-ǫx+ǫ k ,0) ℓ>x ℓ =z U (-ǫx+ǫ ℓ ,1) m>z U (-ǫz+ǫm,0) • ν ∨ = π(C w 1 ),which finishes the proof of the lemma. If w 1 = xzy and w 2 = zxy, x < y ≤ z, thenπ(C w 1 ) = U - w 1 ,0 U - w 1 ,1 U - w 1 ,2 • (ǫ x + ǫ y + ǫ z ) ∨ and π(C w 2 ) = U - w 2 ,0 U - w 2 ,1 U - w 2 ,2 • (ǫ x + ǫ y + ǫ z ) ∨ have a common dense subset.Proof. We only give a sketch of proof and leave the details to the reader. Assume first x < y < z. The key associated to w 1 is T 1 = y z x , let T ′ 1 be the key y x z having the same associated word. Set ν ∨ = (ǫ x + ǫ y + ǫ z ) ∨ , then, as in the proof of Lemma 4, we have, on one side: π(C w 1 ) = U - ǫx+ǫ ℓ ,0) )( m>z U (-ǫz+ǫm,0) )( k>y k =z U (-ǫy+ǫ k ,0) )U (-ǫy+ǫz,-1) • ν ∨

Acknowledgment: Stéphane Gaussent thanks the project ANR-09-JCJC-0102-01 for some financial support. Peter Littelmann and An Hoa Nguyen have been supported by the priority program SPP 1388 Representation Theory of the German Science Foundation and the Research Training Group 1269 Global structures in geometry and analysis.

calculation with the keys T ′ 1 = y x y and T ′ 2 =

x y y , one can show that π(C w 1 ) and π(C w 2 ) have a common dense subset.

Let now w 1 , w 2 be words such that w 1 = (i 1 , . . . , i r , y, x, z, i r+4 , . . . , i N ) w 2 = (i 1 , . . . , i r , y, z, x, i r+4 , . . . , i N ), where x ≤ y < z, and let C w 1 , C w 2 ⊂ Σ (1, . . . , 1)

N be the associated cells. Denote by

Proof. Assume first x < y < z. Let γ 1 be the gallery of shape (1, . . . , 1) associated to w 1 and with key tableau i N . . . i 1 . Let γ ′ 1 be the gallery corresponding to the key tableau i N . . . i r+4 x y i r . . . i 1 z .

) for m > z and µ ∨ r+1 ∈ H (ǫx-ǫy,-p r x,y +1) . Using Corollary 3 and Proposition 3 we get:

x,y -1)

here we use the same arguments (switching commuting subgroups) as in the proof of Lemma 4. Recall that for m > z and s, t ∈ C (see [START_REF] Steinberg | Lectures on Chevalley groups[END_REF] or [START_REF] Tits | Uniqueness and presentation of Kac-Moody groups over fields[END_REF]):

As in the proof of Lemma 4, after switching and gathering the root subgroups we get:

Now for s, t ∈ C we have U (-ǫy+ǫz,p r y,z ) (s)U (-ǫx+ǫy,p r x,y -1) (t) = U (-ǫx+ǫy,p r x,y -1) (t)U (-ǫx+ǫz,p r x,z -1) (st) U (-ǫy+ǫz,p r y,z ) (s). Since U (-ǫy+ǫz,p r y,z ) (s) ⊆ U -

, we can omit this term and we see (after switching commuting terms as in the proof of Lemma 4) that the set (with parameters * , * * = 0) ( 12)

is a dense subset in π(C w 1 ). Now let γ 2 be the gallery of shape (1, . . . , 1) associated to w 2 and let γ ′ 2 be the gallery corresponding to the key tableau i N . . . i r+4 x y i r . . . i 1 z .

We get

It follows that the set S in ( 12) is a common dense subset of π(C w 1 ) and π(C w 2 ), proving the lemma in this case.

The arguments in the case x = y < z used in Lemma 4 are modified in the same way to prove that in this case we have π(C w 1 ) = π(C w 2 ).

It remains to consider the second Knuth relation. Let now w 1 , w 2 be words such that w 1 = (i 1 , . . . , i s-1 , x, z, y, i s+3 , . . . , i N ) w 2 = (i 1 , . . . , i s-1 , z, x, y, i s+3 , . . . , i N ), where x < y ≤ z, and let C w 1 , C w 2 ⊂ Σ (1,...,1) be the associated cells. The proof of the corresponding version of Lemma 6 for the Knuth relation w 1 ∼ K w 2 is nearly identical to the proof of the lemma above and is left to the reader. We just state the corresponding version of Lemma 6

Proof of Theorem 2. The direction i)⇒ii) of the equivalence in Theorem 2b) follows from Lemma 6 and Lemma 7. It was proved in [START_REF] Gaussent | One-skeleton galleries, the path model and a generalization of Macdonald's formula for Hall-Littlewood polynomials[END_REF] (in a more general context) that if T is a semistandard Young tableaux, then π(C γ T ) is a MV-cycle in X ν ∨ of coweight µ ∨ , where µ ∨ is the coweight of the gallery γ T , d = (d 1 , . . . , d r ) is the shape of T and ν ∨ = s j=1 ω ∨ d j . Moreover, the map T → π(C γ T ) induces a bijection between the semistandard Young