Nantel Bergeron
email: bergeron@mathstat.yorku.ca.

Cesar Ceballos
email: ceballos@mathstat.yorku.ca.

Jean-Philippe Labbé
email: labbe@math.huji.ac.il.

Fan realizations of type A subword complexes and multi-associahedra of rank 3

Keywords: simplicial fans, multiassociahedra, subword complex, Gale duality, realization space

We present complete simplicial fan realizations of any spherical subword complex of type An for n ≤ 3. This provides complete simplicial fan realizations of simplicial multi-associahedra ∆ 2k+4,k , whose facets are in correspondence with k-triangulations of a convex (2k + 4)-gon. This solves the first open case of the problem of finding fan realizations where polytopality is not known. The techniques presented in this paper work for all finite Coxeter groups and we hope that they will be useful to construct fans realizing subword complexes in general. In particular, we present fan realizations of two previously unknown cases of subword complexes of type A4, namely the multi-associahedra ∆9,2 and ∆11,3.

Résumé. Nous construisons des éventails simpliciaux complets ayant la combinatoire des complexes de sous-mots de type An pour n ≤ 3. Par conséquent, nous obtenons des constructions d'éventails des multi-associaèdres ∆ 2k+4,k , dont les facettes correspondent aux k-triangulations d'un (2k + 4)-gone. Cette construction confirme l'existence d'éventails ayant la combinatoire du multi-associaèdres pour une famille dont la polytopalité n'est pas confirmée. Les techniques utilisées fonctionnent pour tous les groupes de Coxeter et nous espérons qu'elles seront utiles afin de construire des éventails réalisant les complexes de sous-mots en général. En particulier, nous présentons des éventails pour deux complexes de sous-mots de type A4 dont l'existence était inconnue: les multi-associaèdres ∆9,2 et ∆11,3.

Introduction

Subword complexes are simplicial complexes introduced by Knutson and Miller [START_REF] Knutson | Subword complexes in Coxeter groups[END_REF] motivated from the study of Gröbner geometry of Schubert varieties [START_REF] Knutson | Gröbner geometry of Schubert polynomials[END_REF]. They proved that any subword complex is either a topological ball or sphere [KM04, Corollary 3.8], and asked the question of whether every spherical subword complex can be realized as the boundary complex of a polytope [START_REF] Knutson | Subword complexes in Coxeter groups[END_REF]Question 6.4]. The answer to this question has been verified to be positive only for a few cases, which include interesting families of polytopes such as all even dimensional cyclic polytopes [START_REF] Ceballos | Subword complexes, cluster complexes, and generalized multi-associahedra[END_REF], the duals of c-generalized associahedra [START_REF] Ceballos | Subword complexes, cluster complexes, and generalized multi-associahedra[END_REF], the pseudotriangulation polytope of any planar point set in general position [START_REF] Rote | Expansive motions and the polytope of pointed pseudo-triangulations[END_REF], and the brick polytopes of "root-independent subword complexes" [START_REF] Pilaud | The brick polytope of a sorting network[END_REF][START_REF] Pilaud | Brick polytopes of spherical subword complexes: A new approach to generalized associahedra[END_REF]. Another family of closely related simplicial complexes is the family of multi-associahedra. Given any two positive integers k ≥ 1 and ≥ 2k + 1, the (simplicial) multi-associahedron ∆ ,k is a simplicial complex whose facets correspond to k-triangulations of a convex -gon [START_REF] Jonsson | Generalized triangulations and diagonal-free subsets of stack polyominoes[END_REF]. This simplicial complex is conjectured to be realizable as the boundary complex of a polytope [Jon05, Section 1.2]. The only cases for which this conjecture has been verified are summarized in Table 1.

∆ ,k
Realizable as a k = 1 dual of a classical associahedron [CSZ14, MHPS12] = 2k + 1 single vertex = 2k + 2 simplex = 2k + 3 cyclic polytope [PS09, CLS14] = 2k + 4 complete simplicial fan (this paper) ∆ 8,2 6-dimensional polytope [START_REF] Bokowski | On symmetric realizations of the simplicial complex of 3-crossing-free sets of diagonals of the octagon[END_REF][START_REF] Ceballos | On associahedra and related topics[END_REF] (this paper) ∆ 9,2 complete simplicial fan (this paper) ∆ 11,3 complete simplicial fan (this paper)

Tab. 1: Known results about polytopality of multi-associahedra.

Subword complexes and multi-associahedra turn out to be quite related: every multi-associahedron can be obtained as a well chosen subword complex of type A [START_REF] Pilaud | Multitriangulations, pseudotriangulations and primitive sorting networks[END_REF][START_REF] Stump | A new perspective on k-triangulations[END_REF], see also [START_REF] Serrano | Maximal fillings of moon polyominoes, simplicial complexes, and Schubert polynomials[END_REF]. Conversely, the family of multi-associahedra is universal, in the sense that every spherical subword complex of type A can be obtained as the link of a face in a multi-associahedron [PS12, Proposition 5.6], see also [START_REF] Ceballos | Subword complexes, cluster complexes, and generalized multi-associahedra[END_REF]Theorem 2.15]. The relation between these two families of simplicial complexes has been extended to arbitrary finite Coxeter groups in [START_REF] Ceballos | Subword complexes, cluster complexes, and generalized multi-associahedra[END_REF].

In this extended abstract, we present complete simplicial fan realizations for any spherical subword complex of type A n for n ≤ 3. This is particularly interesting for the case n = 3, where the answer to the question of polytopality is not known. In particular, we obtain complete simplicial fan realizations of multi-associahedra ∆ ,k for ≤ 2k + 4, which solves the previously unknown case when = 2k + 4. Our constructions also lead to a large connected component of the fan realization space in each case, see Section 5. It is also natural to ask whether the complete simplicial fans constructed here are normal fans of polytopes. Although it is often true for k ≤ 2, we do not know if any of our fan realizations for ∆ 10,3 is the normal fan of a polytope. The multi-associahedron ∆ 10,3 is a 3-neighborly simplicial complex of dimension 8 with f -vector (1, 15, 105, 455, 1320, 2607, 3465, 2970, 1485, 330). We tested 144139 different fans realizing it among the infinitely many produced by our construction, and none of them is the normal fan of a polytope, see Table 4. Nevertheless, the polytopality question of multiassociahedra remains open in general, see Section 4 for more details.

Our construction of the fans can be applied for any subword complex of type A n . Although it does not produce the right fans for n ≥ 4, it seems to be close to a valid construction, at least for small values of k and n. We argue this fact in Section 6, where we apply a slight modification to our construction to produce fan realizations of two previously unknown cases of subword complexes of type A 4 , namely the multi-associahedra ∆ 9,2 and ∆ 11,3 . We remark that these two cases are far from trivial. In particular, they are intractable with computational methods previously used in the literature [START_REF] Bokowski | On symmetric realizations of the simplicial complex of 3-crossing-free sets of diagonals of the octagon[END_REF][START_REF] Ceballos | On associahedra and related topics[END_REF]. The corresponding f -vectors are presented in Table 2. Interestingly, we show that the two fans we present for ∆ 9,2 and ∆ 11,3 can not be obtained as the normal fan of a polytope. Tab. 2: f -vectors of two multi-associahedra of type A4.

Definitions and main results

Let (W, S) be a finite Coxeter system. Let Q = (q 1 , . . . , q r ) be a word in the generators S and π ∈ W be an element of the group.

Definition 2.1 ) The subword complex SC(Q, π) is the simplicial complex whose faces are subsets I ⊂ [r] such that the subword of Q with positions at [r] I contains a reduced expression for π.

As mentioned above, a subword complex is either a ball or sphere. It was proven in [CLS14, Theorem 3.7] that every spherical subword complex is isomorphic to a subword complex of the form SC(Q, w • ), where w • is the longest element of the group. Therefore, we restrict our study to subword complexes of this form and write SC(Q) for simplicity. We denote by N := (w • ) the length of w • . Definition 2.2 Given a word Q and a matrix M ∈ R (r-N )×r , we define a natural collection of cones F Q,M in R r-N . Its rays are given by the column vectors of M and its cones are spanned by the columns corresponding to faces of subword complex SC(Q).

The techniques in this paper work for arbitrary finite Coxeter groups. However, part of our main results are devoted to the Coxeter groups of type A. Let W be a Coxeter group of type A generated by the set S = {s 1 , . . . , s n } of simple transpositions s i = (i i + 1). Let ∆ be the corresponding set of simple roots and Φ = W • ∆ = Φ + Φ -be the set of roots partitioned into positive and negative roots respectively. Let c = (s 1 , . . . , s n ) be a Coxeter element, and P m = c m = (p 1 , . . . , p mn ) be a sufficiently long word that contains Q as a subword. The main ingredient in our construction is a counting matrix D c,m , whose entries count the number of reduced expressions of c in P m using the letter p i , after restricting to standard parabolic subgroups.

Definition 2.3 The counting matrix D c,m is a (N × mn)-matrix whose rows correspond to positive roots and columns to the positions 1 ≤ j ≤ mn of the letters of P m = c m = (p 1 , . . . , p mn ). Given α ∈ Φ + and 1 ≤ j ≤ mn, denote by S α ⊂ S the subset of generators whose corresponding simple roots are used in the unique decomposition of the root α in the basis ∆ and by c α the restriction of c to the generators in S α . The entry d α,j of D c,m is the number of reduced expressions of c α in P m (copies of c α up to commutations) using the letter p j . In particular, if p j / ∈ S α , then d α,j = 0.

For any embedding ϕ : Q → c m of Q into a sufficiently long word P m = c m we construct, in Theorem 2.6, a complete simplicial fan realization of the spherical subword complex SC(Q) . This embedding can be thought as a map ϕ : [r] → [mn] from positions in Q to positions in P m .

Definition 2.4 The restricted matrix D ϕ is the restriction of D c,m to the columns ϕ(1), . . . , ϕ(r) corresponding to the positions of the letters of Q embedded in c m .

Example 2.5 Let P 4 = c 4 = (s 1 , s 2 , s 1 , s 2 , s 1 , s 2 , s 1 , s 2 , ) be a word of type A 2 . The counting matrix D c,4 is given below, where the rows correspond to the positive roots {α 1 , α 1 + α 2 , α 2 } in this order. If we take Q corresponding to the underlined letters embedded in P 4 , the dual restricted matrix D ϕ is the restriction of D c,4 to the corresponding columns.

D c,4 = 1 0 1 0 1 0 1 0 4 1 3 2 2 3 1 4 0 1 0 1 0 1 0 1 D ϕ = 1 0 0 1 1 4 1 2 2 1 0 1 1 0 0
Given a full rank matrix D, we say that M is a Gale dual matrix of D if the rows of M form a basis for the kernel of D, see [START_REF] Jesús | Triangulations[END_REF]Definition 4.1.35]. This dual matrix is determined up to linear transformation of its rows. Let M ϕ be a Gale dual matrix of D ϕ .

Theorem 2.6 Let SC(Q) be a spherical subword complex of type A n with n ≤ 3, and ϕ be an embedding of Q into c m . The fan F Q,Mϕ is a complete simplicial fan realization of SC(Q).

This result provides infinitely many complete simplicial fan realizations of any spherical subword complex of type A n with n ≤ 3. In the particular cases where the word Q = c m is naturally embedded into itself we get explicit realizations. In the corollaries below, the entries of the matrices depend on the functions S(i) = i 2 and T (i) = i(i + 1)/2. Corollary 2.7 Let c = (s 2 , s 1 , s 3 ) be a bipartite Coxeter element of type A 3 and Q = c m , with m ≥ 3. The fan F Q,M213,m is a complete simplicial fan realization of SC(Q) for the matrix M 213,m below.

M 213,m :=              -I 3m-6 B 213,m-2 . . . B 213,1              (3m-6)×(3m) B t 213,i :=         S(i + 1) -T (i) -T (i) 2T (i) -T (i -1) + 1 -T (i) 2T (i) -T (i) -T (i -1) + 1 -S(i + 1) + 1 T (i) T (i) -2T (i) T (i -1) T (i) -2T (i) T (i) T (i -1)        
A similar corollary holds for the Coxeter element c = (s 1 , s 2 , s 3 ).

Example 2.8 (3-dimensional associahedron) Let c = (s 2 , s 1 , s 3 ) be a bipartite Coxeter element of type A 3 and Q = c 3 . The subword complex SC(Q) is isomorphic to a 3-dimensional simplicial associahedron. It can be realized as a complete simplicial fan F Q,M213,3 where

M 213,3 = -1 0 0 4 2 2 -3 -2 -2 0 -1 0 -1 1 -1 1 0 1 0 0 -1 -1 -1 1 1 1 0
This fan is the normal fan of a polytope. Figure 1 illustrates eight polytopal realizations associated to appropriate words Q and different choices of embeddings ϕ in Theorem 2.6. Corollary 2.7 can also be restated in terms of multi-associahedra. Before giving a precise statement let us recall some basic definitions. Let k ≥ 1 and ≥ 2k + 1 be two positive integers. We say that a set of k + 1 diagonals of a convex -gon forms a (k + 1)-crossing if all the diagonals in this set are pairwise crossing. A diagonal is called k-relevant if it is contained in some (k + 1)-crossing, that is, if there are at least k vertices of the -gon on each side of the diagonal. The simplicial multi-associahedron ∆ ,k is the simplicial complex of (k + 1)-crossing-free sets of k-relevant diagonals of a convex -gon. We are particularly interested in the case = 2k + 4, where the polytopality conjecture is still open. In this case, there are exactly 3k + 6 k-relevant diagonals, which are in correspondence with the columns of the matrix M 213,k+2 as follows: cyclically label the vertices of the -gon from 1 up to . The first k-relevant diagonal in lexicographic order corresponds to the last column of M 213,k+2 , the other k-relevant diagonals correspond to the other columns in the order they appear in lexicographic order, see Example 2.10. Let F k be the simplicial fan in R 3k whose rays are the column vectors of M 213,k+2 , and whose cones are spanned by the column vectors corresponding to faces of ∆ 2k+4,k . Using this terminology, Corollary 2.7 can be read as follows.

Corollary 2.9 The fan F k is a complete simplicial fan realization of the multi-associahedron ∆ 2k+4,k .

Example 2.10 (Multi-associahedron ∆ 10,3 ) The multi-associahedron ∆ 10,3 can be realized as the complete simplicial fan F 3 . The rays are the column vectors of the matrix M 213,5 below, and the cones are spanned by the column vectors corresponding to faces of ∆ 10,3 . The pairs of numbers on top of the matrix are the 3-relevant diagonals of the 10-gon associated to each of the columns of the matrix.

M 213,5 = 1, 6 1, 7 2, 6 2, 7 2, 8 3, 7 3, 8 3, 9 4, 8 4, 9 4, 10 5, 9 5, 10 6, 10 1, 5

                          -1 0 0 0 0 0 0 0 0 16 12 12 -15 -12 -12 0 -1 0 0 0 0 0 0 0 -6 -2 -6 6 3 6 0 0 -1 0 0 0 0 0 0 -6 -6 -2 6 6 3 0 0 0 -1 0 0 0 0 0 9 6 6 -8 -6 -6 0 0 0 0 -1 0 0 0 0 -3 0 -3 3 1 3 0 0 0 0 0 -1 0 0 0 -3 -3 0 3 3 1 0 0 0 0 0 0 -1 0 0 4 2 2 -3 -2 -2 0 0 0 0 0 0 0 -1 0 -1 1 -1 1 0 1 0 0 0 0 0 0 0 0 -1 -1 -1 1 1 1 0
Remarkably, this fan can not be obtained as the normal fan of a polytope. Even more surprising, using different embeddings of an appropriate word into c m , we tested more than a hundred thousand different fans realizing ∆ 10,3 and none of them turned out to be the normal fan of a polytope, see Table 4. We refer to Section 4 for more details.

3 The sign function and Coxeter signature matrices

Theorem 2.6 relies on a reformulation of the problem in terms of two notions related to Coxeter groups: a sign function on reduced expressions of an element and a Coxeter signature matrix, see Theorem 3.6.

Graph of reduced expressions of w and sign function

Given a finite Coxeter group W and an element w ∈ W , we consider the graph G(w) of reduced expressions of w connected by braid relations, see [START_REF] Reiner | Diameter of graphs of reduced words and galleries[END_REF][START_REF] Humphreys | Reflection groups and Coxeter groups[END_REF]. Figure 2 illustrates an example of the graph G(w • ) for the symmetric group W = S 4 . The 16 vertices are labeled by the subscript sequence of the 16 reduced expressions of w • . For example, 123121 represents the reduced expression s 1 s 2 s 3 s 1 s 2 s 1 . We say that the pairs {i, j} and {i , j } are in the same conjugate class if s i = w -1 s i w and s j = w -1 s j w for some w ∈ W .

Proposition 3.1 Let W be a finite Coxeter group and w be an element in W . Then, any loop in the graph G(w) contains an even number of edges labeled by pairs in the conjugate class of {i, j} (corresponding to a braid relation m ij ) for any fixed pair {i, j}. In particular 1. Any loop in G(w) contains an even number of edges.

2. Any loop in G(w) contains an even number of edges corresponding to even braid relations.

3. Any loop in G(w) contains an even number of edges corresponding to odd braid relations.

Remark 3.2 Taking the conjugate classes of pairs {i, j} is necessary for the result to be true. Consider the reduced expression s 1 s 2 s 1 s 4 in A 4 . The sequence of braid moves

s 1 s 2 s 1 s 4 14 -→ s 1 s 2 s 4 s 1 24 -→ s 1 s 4 s 2 s 1 14 -→ s 4 s 1 s 2 s 1 12 -→ s 4 s 2 s 1 s 2 24 -→ s 2 s 4 s 1 s 2 14 -→ s 2 s 1 s 4 s 2 24 -→ s 2 s 1 s 2 s 4 12 -→ s 1 s 2 s 1 s 4
is a loop in the graph of G(w) that contains three braid relations {1, 4}, not an even number. But if we consider both {1, 4} and {2, 4}, then we get six braid relations of that type, an even number.

Part 2 of this proposition allows the following sign function to be well-defined.

Definition 3.3 The sign function on reduced expressions of w • is a map

sign : {reduced expressions of w • } → {1, -1}
such that if w, w are two reduced expressions of w • connected by a braid move m ij , then sign(w ) = (-1) mij -1 • sign(w).

(1)

Since the graph of reduced expressions of w • is connected [START_REF] Tits | Le problème des mots les groupes de Coxeter[END_REF], this function is unique up to global multiplication by -1. Two reduced expressions connected by an odd braid move have the same sign, while two connected by an even braid move have opposite signs. In the case of type A n , this sign function also appears in a connection between scattering amplitudes in physics and the positive Grassmannian [AHBC + 14]. More precisely, the authors sign function arising from the case of the Grassmannian G(2, n) coincides with the sign function of reduced expressions of w • in type A n . Figure 2 The sign function of type A n can be easily described in terms of their inversions. Let w = w 1 . . . w N be a reduced expression of w • and t 1 , . . . , t N be the corresponding inversions given by t k = w 1 . . . w k . . . w 1 . Each t k is a transposition of the form (i k , j k ). If we replace each t k by min{i k , j k }, we obtain a multi-permutation of

111 . . . 1 n times 22 . . . 2 n-1 times . . . n -1 n -1 n.
The sign(w) is the sign of this multi-permutation. According to personal communication with Alexander Postnikov, the sign of w can be alternatively obtained as the product of the sign of the permutation of inversions of w with -1 to the number of higher inversions of w.

∆ 2k+3,k

A 2 m Regular fans Non-regular fans the subword complex Obs(A 3 ) is polytopal, see [AS76, Table 3]. During FPSAC 2013, Francisco Santos obtained an explicit construction of a 4-dimensional polytope whose boundary complex is Obs(A 3 ). We are grateful to him and his great insight.

∆ 5,1 k = 1 m ≤ 11 6006 0 ∆ 7,2 k = 2 m ≤ 11 12870 0 ∆ 9,3 k = 3 m ≤ 11 16016 0 ∆ 11,4 k = 4 m ≤ 11 12376 0 ∆ 13,5 k = 5 m ≤ 10 1360 0 ∆ k = 6 m ≤

Fan realization space

This section presents a large connected component of the fan realization space of spherical subword complexes of type A 3 . We tested regularity of many fans arising this way and none of them were regular. For a collection of real parameters a = {a i , b i , c i } i=1,...,m define the a-counting matrix D 123,a as the matrix

D 123,a =    D a m • • • D a 1    6×3m D a i =         1 0 0 a i m -b i + 1 0 ai+1 2 (m -b i + 1)(b i ) m-ci+2 2 0 1 0 0 b i m -c i + 1 0 0 1         ,
and denote by M 123,a any Gale dual matrix of D 123,a . We are particularly interested in parameters satisfying the c-signature inequalities in Figure 3, for c = (s 1 , s 2 , s 3 ).

Theorem 5.1 Let c = (s 1 , s 2 , s 3 ) be a Coxeter element of type A 3 and Q = c m , with m ≥ 3. For any choice of real parameters a = {a i , b i , c i } i=1,...,m satisfying the c-signature inequalities in Figure 3, the fan F Q,M123,a is a complete fan realizing SC(Q).

A similar result is valid for the bipartite Coxeter element c = (s 2 , s 1 , s 3 ). Let c = (s 2 , s 4 , s 1 , s 3 ) be a bipartite Coxeter element of type A 4 and Q = c k w • (c). For this particular Coxeter element w • (c) = (2, 4, 1, 3, 2, 4, 1, 3, 2, 4). The subword complex SC(Q) is isomorphic to the multi-associahedron ∆ 2k+5,k . We refer to [CLS14, Section 2.4] for an explicit bijection between positions in the word Q and k-relevant diagonals in the polygon. We tested if the counting matrix from Definition 2.3 is a signature matrix for different values of k and gathered the results in Table 5. In the cases k = 2 and k = 3 (∆ 9,2 and ∆ 11,3 ) almost all determinants had the right signs with the exception of a few that were equal to zero. We found complete simplicial fan realizations in these cases by modifying some of the columns involved in the zero determinants, in such a way that they become nonzero determinants with the right signs. These modifications were small enough to make sure that all other determinants still have good signs. Note that we are not able to obtain complete simplicial fan realizations for the case k = 4 because such a small modification would not correct the bad signs that appear. Example 6.1 (Multi-associahedra ∆ 9,2 and ∆ 11,3 ) The multi-associahedron ∆ 9,2 can be realized as the complete simplicial fan whose rays are the row vectors of the matrix on the left below and whose cones are spanned by the row vectors corresponding to faces of ∆ 9,2 . The pairs of numbers on the left of the matrix are the 2-relevant diagonals of the 9-gon associated to each of the rows of the matrix. The multi-associahedron ∆ 11,3 can be realized as the complete simplicial fan whose rays are the row vectors of the matrix on the right below and whose cones are spanned by the row vectors corresponding to faces of ∆ 11,3 . The pairs of numbers on the left of the matrix are the 3-relevant diagonals of the 11-gon associated to each of the rows of the matrix. Remarkably, these 2 fans are not the normal fan of polytopes.

am bm cm am-1 bm-1 cm-1 • • • • • • • • • a2 b2 c2 a1 b1 c1 ai -ai-1 > 0 bi -bi-1 > 0 ci -ci-1 > 0 2bi -ci -ai-1 + 2bj -cj -aj-1 > 0 ci+1 + ai -2bi + cj+1 + aj -2bj > 0
     1, 6 -1 0 0 0 0 0 0 0 2, 5 0 -1 0 0 0 0 0 0 1, 7 0 0 -1 0 0 0 0 0 2, 6 0 0 0 -1 0 0 0 0 2, 7 0 0 0 0 -1 0 0 0 3, 6 0 0 0 0 0 -1 0 0 2, 8 0 0 0 0 0 0 -1 0 3, 7 0 0 0 0 0 0 0 -1 3, 8 77 5 4 -4 -9 6 1 -1 -2 4, 7 189
-8 -3 9 0 -3 -1 3 1, 4 -397 20 -8 3 15 -6 -2 0 3 5, 9 -20 -8 5 13 -6 -2 1 2 1, 5 -73 10 -4 1 6 -2 -1 0 1 6, 9 -41      1, 7 -1 0 0 0 0 0 0 0 0 0 0 0 2, 6 0 -1 0 0 0 0 0 0 0 0 0 0 1, 8 0 0 -1 0 0 0 0 0 0 0 0 0 2, 7 0 0 0 -1 0 0 0 0 0 0 0 0 2, 8 0

QFig. 1 :

 1 Fig. 1: Eight different polytopal realizations of the 3-dimensional associahedron using embeddings of a word Q into some c m for the Coxeter elements c = s1s2s3 and c = s2s1s3

Fig. 2 :

 2 Fig. 2: The sign function on reduced expressions of w• in type A3: red (thick) edges represent even braid relations (commutations in this case), and blue (thin) edges represent odd braid relations

Fig. 3 :

 3 Fig. 3: Signature inequalities for c = (s1, s2, s3) in type A3. The dashed shapes on the right show an example of the parameters involved in the fourth equation

Tab. 5 :

 5 Signs of the determinants of reduced expressions of w• in c k w•(c) for the counting matrix associated to multi-associahedra of type A4.

  Results of regularity tests on complete simplicial fans of type A2. Results of regularity tests on complete simplicial fans of type A3.

			10	306	0
	Tab. 3: ∆ 2k+4,k	A 3	m	Regular fans Non-regular fans
	∆ 6,1	k = 1 m ≤ 12	1 144 293	136
	∆ 8,2	k = 2 m ≤ 11	66 293	743 560
	∆ 10,3	k = 3 m ≤ 10	0	144 939
	Tab. 4:

Acknowledgements

The authors are grateful to Bruno Benedetti, Frank Lutz, Thomas McConville, and Vic Reiner for important conversations that influenced the results in this paper. They are specially grateful to Darij Grinberg for his important comments, and to Francisco Santos for his polytopal construction in Remark 4.1. We are also grateful to Vincent Pilaud and Vic Reiner for their comments on previous versions of this paper.

Partially supported by NSERC. Supported by the government of Canada through a Banting Postdoctoral Fellowship and by a York University research grant.

Coxeter signature matrix

Let Q = (q 1 , . . . , q r ) be a word in S containing at least one reduced expression of w • , and let N = (w • ) be the length of the longest element in W . Definition 3.5 (Coxeter signature matrix) A matrix M ∈ R N ×r is a signature matrix of type W for the pair

where det(w) is the determinant of the matrix M restricted to the columns corresponding to w, and sign(w) is the sign function of w according to Definition Consider a full rank matrix M ∈ R (r-N )×r and a Gale dual matrix M G ∈ R N ×r , as well as the associated fan F Q,M from Definition 2.2. Theorem 3.6 F Q,M is a complete simplicial fan realization of SC(Q) if and only if (S) M G is a Coxeter signature matrix for the pair (Q, w • ) (Signature), and (I) there is a facet of SC(Q) for which the interior of its associated cone is not intersected by any other cone (Injectivity).

Proposition 3.7 Let W be a Coxeter group of type A n with n ≤ 3, let c be a Coxeter element and Q = c m . The counting matrix D c,m is a signature matrix for the pair (Q, w • ).

Proposition 3.7 is proved using explicit computations of the determinants in (2). We remark that it does not hold for n ≥ 4 and address the problem of finding Coxeter signature matrices in general.

Polytopality

Following [START_REF] Jesús | Triangulations[END_REF], we say that a fan is regular if it is the normal fan of a polytope. One natural question is whether the fans in Theorem 2.6 are regular. The answer is negative in general, most of the fans F Q,Mϕ are not. We restrict the verification of regularity to the family of multi-associahedra ∆ ,k , whose facets are in bijection with k-triangulations of a convex -gon. The multi-associahedron ∆ n+2k+1,k can be obtained as a subword complex SC(Q) for any word Q equal to c k w • (c) up to commutations, where w • (c) denotes the lexicographically first reduced expression of w • in c ∞ . We refer to [START_REF] Ceballos | Subword complexes, cluster complexes, and generalized multi-associahedra[END_REF] for more details on this connection. We used the computer algebra system Sage [S + 14] to produce all the words Q satisfying this property and tested regularity of the fans corresponding to embeddings of Q into a longer word c m for different values of m in types A 2 and A 3 . The results are summarized in Tables 3 and4. It is surprising to have so many different non-regular fans realizing ∆ 10,3 .

Remark 4.1 Our computational results reveal that more than a hundred thousand possible fans realizing the multi-associahedron ∆ 10,3 are not the normal fan of a polytope. We do not know if there are embeddings into longer words c m for which the fan is regular. We found out that the fans associated to the subword complex Obs(A 3 ) := SC(1212321212) embedded in words c m with m ≤ 10 and c any Coxeter element are not regular. This obstruction is minimal: removing any letter to Obs(A 3 ) yields a regular complete fan. The subword complex Obs(A 3 ) appears to be a possible candidate to disprove the polytopality conjecture for subword complexes. The f -vector of Obs(A 3 ) is (1, 9, 30, 42, 21). As it turns out,


Thomas Mcconville
email: mcco0489@umn.edu.

Lattice structure of Grassmann-Tamari orders

Keywords: Tamari lattice, congruence-uniform, lattice quotient, noncrossing complex, Grassmann-Tamari associahedron, biclosed sets

diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

Introduction

The Tamari lattice is a poset of proper bracketings of a word, with covering relations defined by the associativity law. Tamari lattices and their generalizations have appeared in many parts of the literature. We recommend the book [START_REF] Tamari | Associahedra, Tamari Lattices and Related Structures: Tamari Memorial Festschrift[END_REF] for an introduction to many recent developments on these posets.

In this extended abstract, we consider a new generalization of the Tamari lattice, the Grassmann-Tamari order, introduced by Santos, Stump, and Welker [START_REF] Santos | Noncrossing sets and a grassmann associahedron[END_REF]. One of the conjectures they pose is that these posets are lattices. We give an affirmative answer to this conjecture, and show that some of the very good lattice properties of Tamari lattices hold in this larger family of posets; see Theorem 1.1 for a precise statement.

The Grassmann-Tamari order GT k,n is a partial order on the maximal "non-crossing" subsets of [n] k , the k-element subsets of {1, . . . , n}. Two sets I, J ∈ [n] k are crossing if i t < j t < i t+1 < j t+1 for some A maximal family of non-kissing paths excluding horizontal and vertical paths.

t where

I -J = {i 1 < • • • < i l } and J -I = {j 1 < • • • < j l }.
The sets I, J are non-crossing otherwise. For example, {1, 4, 5} and {2, 3, 6} are non-crossing, whereas {1, 4, 5} and {2, 4, 6} are crossing. The non-crossing complex ∆ N C k,n is the collection of all pairwise non-crossing subsets of [n] k . For l ≥ 1, let C l be a chain poset with l elements. The complex ∆ N C k,n may be realized as a regular, unimodular, Gorenstein triangulation of the order polytope O k,n on C k × C n-k ; i.e., the polytope in R k(n-k) defined by the inequalities 0 ≤ x i,j ≤ 1, x i,j ≤ x i+1,j , and Theorem 8.1] or [START_REF] Santos | Noncrossing sets and a grassmann associahedron[END_REF]Theorem 1.7]). This triangulation of O k,n is distinct from the equatorial triangulation defined in [START_REF] Reiner | On the charney-davis and neggers-stanley conjectures[END_REF], which is not flag in general. As a consequence of this geometric realization, after removing cone points, ∆ N C k,n is a pure, thin complex of dimension (k -1)(n -k -1) -1. Moreover, there exists a simple polytope, the Grassmann-associahedron, with facial structure anti-isomorphic to ∆ N C k,n . In the full paper, we present an alternative proof of this result by constructing the dual Grassmann-associahedron by a sequence of suspensions and edge-stellations, starting from an empty complex.

x i,j ≤ x i,j+1 for 1 ≤ i ≤ k, 1 ≤ j ≤ n -k ([6,
Any triangulation of O k,n naturally gives rise to a monomial basis for the coordinate ring of the Grassmannian, the C-algebra generated by the maximal minors of a k × n matrix of indeterminates (x ij ) [START_REF] Kyle Petersen | A non-crossing standard monomial theory[END_REF]. Namely, a monomial r 1 x Ij is in the basis if {I 1 , . . . , I r } is a face of the triangulation. The classical standard basis for this algebra is indexed by semistandard Young tableaux. The columns of a semistandard Young tableaux satisfy a compatibility condition that resembles a non-nesting analogue of the non-crossing condition defined above. Thus these two bases may be viewed as "opposite" in some sense. One may hope to develop a straightening law for these monomials, though we do not pursue this here.

Let J be the set of order ideals of C k × C n-k . The Hibi ideal is the ideal generated by {x I x Jx I∩J x I∪J : I, J ∈ J ) in the polynomial ring on {x I : I ∈ J }. By results of [START_REF] Sturmfels | Grobner bases and convex polytopes[END_REF], regular unimodular triangulations of O k,n are in bijection with squarefree monomial initial ideals of the Hibi ideal. As observed in the introduction of [START_REF] Santos | Noncrossing sets and a grassmann associahedron[END_REF], the triangulation induced by ∆ N C k,n corresponds to a particularly nice initial ideal. We refer to the survey [2, Section 6] for more background on Hibi ideals.

There is a natural orientation on the dual graph of

∆ N C k,n . If two facets F 1 = F ∪ {I}, F 2 = F ∪ {J} are adjacent,
then there is a unique index t for which i t < j t < i t+1 < j t+1 where [START_REF] Santos | Noncrossing sets and a grassmann associahedron[END_REF], the Grassmann-Tamari order GT k,n is the transitive closure of this relation. The smallest Grassmann-Tamari order not isomorphic to a Tamari lattice is drawn in Figure 4.

I -J = {i 1 < • • • < i l } and J -I = {j 1 < • • • < j l }. We orient the edge F 1 → F 2 if
The non-crossing condition translates to a non-kissing condition on paths via the standard bijection between k-subsets of [n] and paths in a k × (n -k) rectangle with South and East steps. For example, the set {1, 4, 5} corresponds to the path from the NW-corner to the SE-corner of a 3 × 3 rectangle such that the first, fourth, and fifth steps are to the South, while the others are to the East. Two paths p 1 , p 2 in the plane are kissing if they agree on some subpath between vertices v and v , p 1 enters v from the West and leaves v to the South, and p 2 enters v from the North and leaves v to the East; see Figure 1. The non-kissing complex ∆ N K (λ) associated to a (possibly not rectangular) shape λ is the collection of pairwise non-kissing paths supported by λ. A poset GT(λ) analogous to the Grassmann-Tamari orders may be defined on the facets of this complex. We call GT(λ) the Grid-Tamari order; see Section

2. If λ is a k × (n -k) rectangle, then GT(λ) is isomorphic to GT k,n .
Our main result is Theorem 1.1 For any shape λ, GT(λ) is a congruence-uniform lattice.

We recall congruence-uniformity and related lattice properties in Section 3.

To prove Theorem 1.1, we express GT(λ) as a lattice quotient of a much simpler lattice. Namely, we define a finite topological space whose clopen sets, which we call biclosed sets, form a congruenceuniform lattice under inclusion. Then we define a map from the collection of biclosed sets to facets of the non-kissing complex that carries this lattice structure. A similar approach was applied by Nathan Reading to prove that Tamari posets are lattice quotients of the weak order on the symmetric group (see e.g. [START_REF] Reading | From the tamari lattice to cambrian lattices and beyond[END_REF]).

The rest of this extended abstract is organized as follows. In Section 2, we establish the purity and thinness of the non-kissing complex combinatorially, similar to the methodology employed in [START_REF] Santos | Noncrossing sets and a grassmann associahedron[END_REF] for proving purity and thinness of the non-crossing complex. We close the section by defining the orientation on the dual graph of the non-kissing complex whose transitive closure is a Grid-Tamari order. We emphasize that this directed graph is acyclic as a consequence of Theorem 1.1. A geometric proof of acyclicity in the non-crossing case appears in [START_REF] Santos | Noncrossing sets and a grassmann associahedron[END_REF].

To set up the appropriate generalization of the weak order, we prove some general results on biclosed sets in Section 3. Biclosed sets may be defined for any closure operator on a set, though the resulting poset of biclosed sets may not be interesting. We provide some conditions on the closure that makes the poset of biclosed sets a semidistributive or congruence-normal lattice. In particular, these conditions are satisfied by the convex closure on the positive roots of a finite root system.

In Section 4, we introduce a poset of biclosed subsets of segments in a shape λ. We show that this poset satisfies the hypotheses given in Section 3, so it is a congruence-uniform lattice.

A special lattice congruence on the lattice of biclosed sets of segments is presented in Section 5. In Section 6, we define a map η from biclosed sets of segments to the facets of the non-kissing complex, and show that the fibers of η are precisely the equivalence classes of this lattice congruence. We deduce Theorem 1.1 by comparing the order induced by η with the Grid-Tamari order.

In this extended abstract, most of the intermediary results are illustrated by example in place of proof. Proofs will appear in the full version.

Non-kissing complexes

A shape λ is a finite (vertex)-induced subgraph of the Z × Z square grid. A vertex v ∈ λ is interior if λ contains the 2 × 2 grid centered at v. Otherwise, v is a boundary vertex. A horizontal (vertical) edge e of λ is interior if the 1 × 2 (2 × 1) box centered at e is contained in λ. w 0 w 1 w 2 w 3 w 4
Fig. 2: A shape with a path w0, w1, w2, w3, w4.

A path supported by λ is a sequence of vertices v 0 , . . . , v t such that

• v 0 and v t are boundary vertices,

• v 1 , . . . , v t-1 are interior vertices, and

• v i is one step South or East of v i-1 for all i.
A path supported by λ is called a segment if its endpoints are also interior vertices. If s is a segment containing vertices v and v , then s[v, v ] denotes the sub-segment of s whose endpoints are v and v . The initial (terminal) vertex of a segment s is denoted s init (s term ).

A path w 0 , w 1 , w 2 , w 3 , w 4 is drawn in Figure 2. This path contains the segment w 2 , w 3 , for example. Two paths p 1 , p 2 are kissing if they share vertices v, v such that

• p 1 [v, v ] = p 2 [v, v ],
• p 1 enters v from the West and leaves v to the South, and

• p 2 enters v from the North and leaves v to the East.

Otherwise p 1 and p 2 are non-kissing. The non-kissing complex ∆ N K (λ) is the flag simplicial complex whose faces are collections of pairwise non-kissing paths supported by λ. As horizontal and vertical paths are non-kissing with any path, we define the reduced non-kissing complex ∆ N K (λ) to be the deletion of all horizontal and vertical paths from ∆ N K (λ).

Although a pair of non-kissing paths may twist around each other several times, there is a natural way to totally order paths that contain a specific edge. Let e be an interior edge of λ. If p 1 and p 2 are distinct non-kissing paths containing e, then they agree on some maximal subpath p 1 [v, v ] containing e. Order p 1 ≺ e p 2 if either p 1 enters v from the North or p 1 leaves v to the South. We note that both cases may not occur if v or v is a boundary vertex.

If F is a set of non-kissing paths, we say a path p ∈ F is the bottom path (top path) at an edge e if p is minimal (maximal) in F with respect to ≺ e . Theorem 2.1 Let F be a facet of ∆ N K (λ).

1. The map that takes an interior edge e to the top path at e is a bijection between vertical interior edges of λ and non-horizontal paths in F .

2. For paths p ∈ F with at least one turn, there exists a unique path q distinct from p such that F -{p} ∪ {q} is non-kissing. Moreover, p and q kiss at a unique segment.

A simplicial complex is pure if its facets all have the same dimension. A pure complex is thin if every face of codimension 1 is contained in exactly two facets. Theorem 2.1 immediately implies the following corollary.

Corollary 2.2 For any shape λ, the reduced non-kissing complex ∆ N K (λ) is a pure, thin simplicial complex.

Example 2.3 We illustrate Theorem 2.1 with the facet F = {145, 146, 236, 245} of ∆ N C 3,6 . The sets in F correspond to the four non-kissing paths drawn in Figure 1. Including the two vertical paths 234 and 345, each of the six paths in F ∪ {234, 345} is the top path at a unique interior vertical edge.

The unique facet distinct from F containing F -{145} is (F -{145}) ∪ {246}. If one removes 145 from F , then 245 is on top at two different vertical edges. The segment supported by 245 between these two vertical edges is the unique segment along which the paths 145 and 246 kiss.

The dual graph of a pure thin complex is the set of facets where two facets are adjacent if they intersect at a codimension 1 face. We define an orientation on the dual graph of ∆ N K (λ) as follows. Let F 1 , F 2 be adjacent facets, and let

p 1 ∈ F 1 -F 2 , p 2 ∈ F 2 -F 1 .
Then p 1 and p 2 are kissing at a unique segment, say p 1 [v, v ]. Orient the edge F 1 → F 2 if p 1 enters v from the West (so p 2 enters v from the North). Let GT(λ) be the transitive closure of this relation.

Theorem 2.4 (see [START_REF] Santos | Noncrossing sets and a grassmann associahedron[END_REF], Theorem 2.17) GT(λ) is a partially ordered set.

We call GT(λ) the Grid-Tamari order. When λ is a 2 × n rectangle, GT(λ) is the usual Tamari lattice. For general λ, Theorem 2.4 is far from obvious. In [START_REF] Santos | Noncrossing sets and a grassmann associahedron[END_REF], it is proved for all rectangle shapes by identifying GT(λ) with a poset of facets of a regular triangulation of a polytope, whose order is induced by a generic linear functional. We prove this combinatorially in Section 6 along with Theorem 1.1 by identifying GT(λ) with a lattice quotient of some other lattice.

Biclosed Sets

A closure operator on a set S is an operator X → X on subsets of S such that for X, Y ⊆ S, X ⊆ X, X = X, and

X ⊆ Y implies X ⊆ Y .
In addition, we assume ∅ = ∅. A subset X of S is closed if X = X. A subset X is biclosed if X and S \ X are both closed. We let Bic(S) be the poset of biclosed subsets of S ordered by inclusion. By our assumption, S and ∅ are always biclosed.

What we call biclosed sets are often called clopen sets elsewhere in the literature; see, for example [START_REF] Santocanale | Lattices of regular closed subsets of closure spaces[END_REF]. The term biclosed typically refers to a subset of a convex geometry which is 2-closed and whose complement is 2-closed. We choose the term biclosed because all of the closure operators we consider come from some convex geometry in this way. This connection will be explained further in the full paper.

A collection B of subsets of S is ordered by single-step inclusion if for all X, Y ∈ B such that X Y there exists y ∈ Y \ X such that X ∪ {y} ∈ B. If ∅, S ∈ B and B is ordered by single-step inclusion, then it is a graded poset with rank function X → |X| for X ∈ B; in particular, every maximal chain has length |S|.

A lattice L is meet-semidistributive if L satisfies x ∧ z = y ∧ z ⇒ (x ∨ y) ∧ z = x ∧ z for x, y, z ∈ L.
A lattice is join-semidistributive if its dual is meet-semidistributive. A lattice is semidistributive if it is both meet-and join-semidistributive. We give some criteria on semidistributivity for biclosed sets.

. W ∪ (X ∪ Y ) \ W is biclosed for W, X, Y ∈ Bic(S) with W ⊆ X ∩ Y , then Bic(S) is a semidistributive lattice. Suppose Bic(S) is a lattice. If W, X, Y ∈ Bic(S) with W ⊆ X ∩ Y , then X ∪ Y ⊆ W ∪ (X ∪ Y ) \ W ⊆ X ∪ Y ⊆ X ∨ Y, so X ∨ Y and W ∪ (X ∪ Y ) \ W are equal if the latter is biclosed. Example 3.2
The inversion set of a permutation π of [n] is the collection of pairs {i, j} for which π -1 (i) > π -1 (j). For example, the inversion set of 2314 is {12, 13}. The weak order on permutations of [n] is the ordering by inclusion of inversion sets.

The weak order on permutations may be identified with a collection of "biclosed" subsets of [n] 2 , ordered by inclusion. A subset X of [n] 2 is closed if {i, k} is in X whenever {i, j} and {j, k} are in X for some j with i < j < k. Then X is biclosed if both X and [n] 2 -X are closed. The map taking a permutation to its inversion set is an isomorphism between the weak order and the poset of biclosed subsets of [n] 2 . More generally, the weak order on any finite Coxeter group may be identified with a poset of biclosed sets of positive roots ordered by inclusion. That these posets are ordered by single-step inclusion is well-known. Dyer proved that W ∪ (X ∪ Y ) \ W is a biclosed set whenever W, X, Y are biclosed and W ⊆ X ∩ Y [START_REF] Dyer | On the weak order of coxeter groups[END_REF]. He also proved this holds for infinite root systems if X ∪ Y is finite. By Theorem 3.1 we may deduce that the weak order for finite lower intervals of (possibly infinite) Coxeter groups is a semidistributive lattice. Other proofs of semidistributivity appear in [5] and [START_REF] Reading | Lattice and order properties of the poset of regions in a hyperplane arrangement[END_REF]; see also [START_REF] Reading | Sortable elements in infinite coxeter groups[END_REF]Section 8] for a refinement of this result.

A subset C of a poset P is order-convex if z ∈ C whenever x, y ∈ C and x ≤ z ≤ y. Given an order-convex subset C of P , the doubling P [C] is the induced subposet of P × {0, 1} with elements

P [C] = (P ≤C × {0}) [(P -P ≤C ) ∪ C] × {1},
where P ≤C = {x ∈ P : (∃c ∈ C) x ≤ c}. If P is a lattice, then P [C] is a lattice where (x, ) ∨ (y, ) = (x ∨ y, max( , )) if x ∨ y ∈ P ≤C (x ∨ y, 1) otherwise , Fig. 3: A sequence of doublings, ending with the weak order on S4.

for (x, ), (y, ) ∈ P [C]. A finite lattice L is congruence-normal if there exists a sequence of lattices L 1 , . . . , L t such that L 1 is the one-element lattice, L t = L, and for all i, there exists an order convex subset

C i of L i such that L i+1 ∼ = L i [C i ].
A finite lattice is congruence-uniform (or bounded) if it is both congruence-normal and semidistributive. The weak order on permutations is a congruence-normal lattice; see Figure 3 for a sequence of doublings that creates the weak order on S 4 . The general case is discussed in Example 3.5.

Congruence-normal and congruence-uniform lattices admit other characterizations in terms of lattice congruences [START_REF] Day | Congruence normality: the characterization of the doubling class of convex sets[END_REF]. Additionally, congruence-uniform lattices may be characterized as lattice quotients of free lattices for which every fiber is a closed interval. As free lattices on finite sets are typically infinite, this interval property is quite special.

For our purposes, it is easier to employ Reading's characterization of congruence-normal lattices by CN-labelings defined as follows. For elements x and y of a poset P , y covers x if x < y and x ≤ z ≤ y implies x = z or z = y for z ∈ P . We write x y if y covers x, and let Cov(P ) denote the set of pairs (x, y) for which x y. An edge-labeling of a poset P is a function from Cov(P ) to some label set R. An edge-labeling λ : L → R from a lattice L to a poset (R, ) is a CN-labeling if L and its dual L * satisfy the following condition: For elements x, y, z ∈ L, (z, x), (z, y) ∈ Cov(L) and maximal chains

C 1 , C 2 ∈ [z, x ∨ y] with x ∈ C 1 , y ∈ C 2 , (CN1) The elements x ∈ C 1 , y ∈ C 2 such that (x , x ∨ y), (y , x ∨ y) ∈ Cov(L) satisfy λ(z, x) = λ(y , x ∨ y), λ(z, y) = λ(x , x ∨ y). (CN2) If (u, v) ∈ Cov(C 1 ) with z < u, v < x ∨ y, then λ(z, x) ≺ λ(u, v) and λ(z, y) ≺ λ(u, v).
(CN3) The labels on Cov(C 1 ) are all distinct. Theorem 3.3 ([7], Theorem 4) A finite lattice L is congruence-normal if and only if it admits a CNlabeling.

A CN-labeling of the Grassmann-Tamari order GT 3,6 is drawn in Figure 4. The first hypothesis in Theorem 3.4 gives a natural labeling of the covering relations in Bic(S). The third hypothesis gives an order structure on these labels. The proof of Theorem 3.4 amounts to showing that this labeling is a CN-labeling.

Example 3.5 For the closure operator on [n] 2 in Example 3.2, we define a partial order {i, j} {k, l} if k ≤ i < j ≤ l. As this partial order satisfies property (3), we deduce that the weak order on permutations is congruence-normal by Theorem 3.4. This holds more generally for the weak order of any finite Coxeter group ([1, Theorem 6] or [START_REF] Reading | Lattice and order properties of the poset of regions in a hyperplane arrangement[END_REF]Theorem 27]).

Biclosed Sets of Segments

For the remainder of this abstract, we fix a shape λ and let S denote the set of segments supported by λ, partially ordered by inclusion. Two segments s and t are composable if s term is one unit North or West of t init . If s and t are composable, then the composite s • t is the segment containing both s and t. Given a set X of segments of λ, say X is closed if s • t ∈ X whenever s, t ∈ X and s • t exists; see Figure 5. We let Bic(S) denote the poset of biclosed sets of segments, as in Section 3.

Example 4.1 Suppose λ is a 2 × n rectangle. Labeling the interior vertices 1, . . . , n -1 from left to right, a segment s may be identified with the set {i, j} ∈ [n] 2 where i is the label on s init and j -1 is the label on s term . The closure on segments then agrees with the closure on [n] 2 defined in Example 3.2. Hence, Bic(S) is isomorphic to the weak order on permutations of [n]. Theorem 4.2 For S and λ defined above, Fig. 6: The four non-vertical and non-horizontal paths in η(X) where X is the set of black segments. Proposition 6.1 η(X) is a maximal collection of non-kissing paths.

When Bic(S) is viewed as a lattice, we claim that η defines a lattice quotient map, thus endowing the set of facets of ∆ N K (λ) with the structure of a lattice. Explicitly, we claim that η is surjective, and if X and Y are biclosed, then η(X) = η(Y ) if and only if X ≡ Y mod Θ.

To prove this claim, we define another function φ from facets of ∆ N K (λ) to Bic(S) as follows. For a path p, let A p be the set of SW-subsegments of p. If F is a facet of ∆ N K (λ), we define φ(F ) to be p∈F A p . It may be shown that φ and η are inverse bijections between facets of ∆ N K (λ) and biclosed sets X for which X ↓ = X.

To complete the proof of Theorem 1.1, it remains to show that the ordering on facets of ∆ N K (λ) induced by η is identical to the Grid-Tamari order. For this, it suffices to compare covering relations.

Fig. 1 :

 1 Fig. 1: (left) Two paths kissing along the indicated segment from v to v . The paths correspond to the sets 145 and 246, which are crossing. (right)

Theorem 3 . 1

 31 Let S be a set with a closure operator. If 1. Bic(S) is ordered by single-step inclusion, and 2

Theorem 3 . 4

 34 Let (S, ≺) be a poset with a closure operator. Assume that1. Bic(S) is ordered by single-step inclusion, 2. W ∪ (X ∪ Y ) \ W is biclosed for W, X, Y ∈ Bic(S) with W ⊆ X ∩ Y , and

Fig. 4 :

 4 Fig. 4: (left) GT3,6 (right) Ordering on edge labels

  the pair {i t , i t+1 } is lexicographically smaller than {j t , j t+1 }.

	For example, {145, 146, 236, 245} and {146, 236, 245, 246} are adjacent facets
	of ∆ N C 3,6 with orientation {145, 146, 236, 245} → {146, 236, 245, 246} since 145 and 246 cross at 15 and
	26. Defined by Santos, Stump, and Welker in

Acknowledgements

I thank Nathan Reading for pointing out the reference [11]. I also thank Christian Stump for making his data on Grassmann-Tamari orders available for my use. Lastly, I thank Nathan Reading, Vic Reiner, Pasha Pylyavskyy, and the referees for many helpful remarks in the preparation of this extended abstract.

Supported by RTG grant NSF/DMS-1148634 1365-8050

Thomas McConville

3. X ↓ = Y ↓ if and only if X ↑ = Y ↑ for X, Y ∈ Bic(S).

An equivalence relation Θ on a lattice L is a lattice congruence if x ≡ y mod Θ implies x ∨ z ≡ y ∨ z mod Θ and x ∧ z ≡ y ∧ z mod Θ for x, y, z ∈ L. The set of equivalence classes L/Θ of a lattice congruence forms a lattice where

for x, y ∈ L. We say L/Θ is a quotient lattice of L, and the natural map L → L/Θ is a lattice quotient map. The following characterization of lattice congruences is well-known. Example 5.4 Let λ be the 2 × n rectangle from Example 4.1. If X is a biclosed subset of S, then X ↓ is the set obtained by removing horizontal segments for which some initial part is not in X. The set X ↑ is obtained by adding horizontal segments to X for which some initial part is not in X but the corresponding terminal part is in X. By this observation it follows that X ↓ is the largest biclosed set for which (X ↑ ) ↓ = X ↓ . In particular, the equivalence classes are all closed intervals of the form [X ↓ , X ↑ ] for some X ∈ Bic(S). Moreover, π ↑ (X) = X ↑ and π ↓ (X) = X ↓ , so π ↑ and π ↓ are both orderpreserving maps, thus verifying Corollary 5.3 in this case. The argument for general shapes follows similar reasoning.

When λ is a 2 × n rectangle, the bijection in Example 4.1 takes biclosed sets X for which X ↓ = X to inversion sets of 312-avoiding permutations. Indeed, if a permutation σ = σ 1 • • • σ n contains a 312 pattern, say with values i < j < k, then the corresponding biclosed set X has a long segment labeled {i, k} for which the initial part {i, j} is not in X. [START_REF] Kyle Petersen | A non-crossing standard monomial theory[END_REF] The Grid-Tamari order as a lattice quotient Let E V denote the set of interior vertical edges in λ and let P be the set of paths supported by λ.

We define a function η : Bic(S) → 2 P as follows. Let X ∈ Bic(S) be given. If e ∈ E V is an edge from u to v, let p e be the path such that for interior vertices u ∈ p e [•, u] and v ∈ p e [v, •]:

Let η(X) be the union of {p e : e ∈ E V } with the set of horizontal paths supported by λ. For example, if X is the biclosed set of six black segments in Figure 6, each of the six interior vertical edges corresponds to a non-horizontal path in η(X). In Figure 6, the four paths corresponding to the four marked purple edges are drawn. The other two vertical edges correspond to vertical paths.


Jennifer Morse
email: morsej@math.drexel.edu

Anne Schilling

Affine charge and the k-bounded Pieri rule

Keywords: Charge statistic, Pieri rule, k-Schur functions, energy function, affine Schubert calculus

We provide a new description of the Pieri rule of the homology of the affine Grassmannian and an affine analogue of the charge statistics in terms of bounded partitions. This makes it possible to extend the formulation of the Kostka-Foulkes polynomials in terms of solvable lattice models by Nakayashiki and Yamada to the affine setting.

Résumé. Nous proposons une nouvelle description de la règle de Pieri de l'homologie de la variété Grassmannienne affine et un analogue affine de la statistique de charge en termes de partitions bornées . Il est ainsi possible d'étendre au cas affine la formulation due à Nakayashiki et Yamada des polynômes de Kostka-Foulkes en termes de modèles de réseaux résolubles.

Introduction

Our study concerns an affine generalization of the Kostka-Foulkes polynomials. Kostka-Foulkes polynomials comprise a fascinating family of polynomials in a single parameter t that arises in diverse contexts such as cohomology of Springer fibers [START_REF] Springer | A construction of representations of Weyl groups[END_REF][START_REF] Hotta | A specialization theorem for certain Weyl group representations and an application to the Green polynomials of unitary groups[END_REF], representation theory of GL n (F q ) [21, Ch. IV], affine Kazhdan-Lusztig theory [START_REF] Lusztig | Green polynomials and singularities of unipotent classes[END_REF], solvable lattice models and crystal base theory [START_REF] Nakayashiki | Kostka polynomials and energy functions in solvable lattice models[END_REF], the Bethe Ansatz and rigged configurations [START_REF] Kirillov | The Bethe ansatz and the combinatorics of Young tableaux[END_REF], and the study of subgroups of finite abelian groups [START_REF] Butler | Subgroup lattices and symmetric functions[END_REF]. They also encode the irreducible decomposition of the Garsia-Procesi graded S n -modules [START_REF] Garsia | On certain graded Sn-modules and the q-Kostka polynomials[END_REF].

In symmetric function theory, the Kostka-Foulkes polynomials appear as Schur transition coefficients with Macdonald's P -functions, defined by

P λ (x; t) = 1 v λ (t) w∈Sn w x λ i<j x i -tx j x i -x j , (1)
where λ is a partition of length ≤ n (with allowable zero parts), v λ (t) = j≥0 mj i=1

1-t i 1-t for m j the multiplicity of j in λ, and S n is the symmetric group on n elements. The set {P λ } forms a basis of the ring of symmetric functions Λ over Q(t) and P λ (x; t) reduces to the monomial symmetric function m λ when t = 1. Kostka-Foulkes polynomials are inscribed in its transition with the Schur basis:

s λ (x) = µ K λµ (t) P µ (x; t) . (2)
Lascoux and Schützenberger [START_REF] Lascoux | Sur une conjecture de H. O. Foulkes[END_REF][START_REF] Butler | Subgroup lattices and symmetric functions[END_REF] proved that the Kostka-Foulkes polynomials can be expressed as the generating function of the set SSYT(λ, µ) of semi-standard Young tableaux of shape λ and content µ graded by the (non-negative integer) charge statistic

K λµ (t) =
T ∈SSYT(λ,µ)

t charge(T ) . (3)
Subsequently, Nakayashiki and Yamada [START_REF] Nakayashiki | Kostka polynomials and energy functions in solvable lattice models[END_REF] showed that the Kostka-Foulkes polynomials can instead be interpreted as the partition function of an exactly solvable lattice model in statistical mechanics. In particular, K λµ (t) is expressed in terms of tensor products of type A Kirillov-Reshetikhin (KR) crystals graded by the energy function. KR crystals B r,s are labeled by r ∈ {1, 2, . . . , n} and an integer s ≥ 1. In type A

(1) n , B r,s can be considered as the set of all semi-standard Young tableaux of rectangular shape (s r ) over the alphabet {1, 2, . . . , n + 1}. The classical crystal operators fi and ẽi for 1 ≤ i ≤ n are defined in terms of certain bracketing rules involving the letters i and i + 1. The affine Kashiwara operators ẽ0 and f0 are defined as ẽ0 = pr -1 • ẽ1 • pr and ẽ0 = pr -1 • ẽ1 • pr, where pr is the promotion operator. See for example [START_REF] Fourier | Kirillov-Reshetikhin crystals for nonexceptional types[END_REF].

For any partition µ

= (µ 1 , µ 2 , . . . , µ N ), let B µ = B 1,µ N ⊗ • • • ⊗ B 1,µ1
be a tensor product of single row KR crystals and let E : B µ → Z be the (right) energy function (see for example [START_REF] Nakayashiki | Kostka polynomials and energy functions in solvable lattice models[END_REF][START_REF] Lenart | Crystal energy functions via the charge in types A and C[END_REF]). Here we use the opposite of Kashiwara's convention for tensor products of crystals. Since the elements of B 1,s are single row-shaped tableaux, each factor b N ⊗ • • • ⊗ b 1 ∈ B µ can be associated (by RSK column-insertion) to a recording tableau; it is obtained by placing the letter i into the boxes of shape(b i . . . b 1 )/shape(b i-1 . . . b 1 ). For highest weight vectors b ∈ B µ (that is ẽi (b) = 0 for i = 1, 2, . . . , n), this is equivalent to placing a letter i in row j of the recording tableau if j occurs in b i . It was proven in [START_REF] Nakayashiki | Kostka polynomials and energy functions in solvable lattice models[END_REF] that the energy function is equal to the charge of the recording tableau and consequently,

K λµ (t) = b∈B µ ,weight(b)=λ ẽi(b) = 0 for i = 1, 2, . . . , n t E(b) . (4)
Example 1.1 For µ = (2, 2, 1), the highest weight crystal elements in

B 1,1 ⊗ B 1,2 ⊗ B 1,2 are 3 ⊗ 2 2 ⊗ 1 1 , 3 ⊗ 1 2 ⊗ 1 1 , 1 ⊗ 2 2 ⊗ 1 1 , 2 ⊗ 1 2 ⊗ 1 1 , 1 ⊗ 1 2 ⊗ 1 1 , 2 ⊗ 1 1 ⊗ 1 1 , 1 ⊗ 1 1 ⊗ 1 1 ,
with energies 0, 1, 1, 2, 2, 3, 4, respectively. Inserting the factors from right to left, recording the i-th factor with the letter i yields the following corresponding tableaux:

2 1 1 2 3 , 3 1 1 2 2 , 1 1 2 2 3 .
The charge of each recording tableau agrees with the energy of the corresponding tensor.

Note that the Kostka-Foulkes polynomials can also be related to tensor products of column KR crystals B r,1 [START_REF] Nakayashiki | Kostka polynomials and energy functions in solvable lattice models[END_REF][START_REF] Lenart | From Macdonald polynomials to a charge statistic beyond type A[END_REF]. Yet another direction ties Kostka-Foulkes polynomials to affine Schubert calculus. The algebraic nil-Hecke ring construction of Kostant and Kumar [START_REF] Kostant | The nil Hecke ring and cohomology of G/P for a Kac-Moody group G[END_REF] and the work of Peterson [START_REF] Peterson | Quantum cohomology of G/P , Lecture notes[END_REF] developed the study of Schubert bases associated to Schubert cells of the affine Grassmannian Gr for type SL n :

{ξ λ ∈ H * (Gr, Z) | λ ∈ P n } and {ξ λ ∈ H * (Gr, Z) | λ ∈ P n } ,
indexed by the subset P n of partitions with all parts shorter than n. Separately, distinguished k-Schur and dual k-Schur bases for certain symmetric function spaces which are isomorphic to H * (Gr) and H * (Gr) were introduced and connected to Gromov-Witten invariants (quantum cohomology of Grassmannians) in [START_REF] Lapointe | A k-tableau characterization of k-Schur functions[END_REF][START_REF] Lapointe | Quantum Cohomology and the k-Schur Basis[END_REF]. The approaches merged with Lam's proof [START_REF] Lam | Schubert polynomials for the affine Grassmannian[END_REF] that these bases are sets of representatives for the Schubert classes of H * (Gr) and H * (Gr) (hereafter, k = n -1).

Recently, a t-generalization for the dual k-Schur basis was introduced in [3] using a construction in the spirit of ( 2) and (3). A non-negative statistic called kcharge is associated to certain chains in the Bruhat order on the type-A affine Weyl group. The generating functions

K (k) λµ (t) = T ∈T (λ,µ) t kcharge(T ) (6)
are used to define polynomials, for λ ∈ P n , by

S λ (x; t) = µ∈P n K (k) λµ (t) P µ (x; t) . (7)
These form a basis for the subspace Λ t (n) = span{P λ (x; t)} λ1<n which reduces to a set of representatives for the Schubert cohomology classes {ξ λ } λ∈P n when t = 1.

To complement their geometric interpretation, our goal in this paper is to connect the affine Kostka-Foulkes polynomials of (6) with Kirillov-Reshetikhin (KR) crystals. Our approach gives a new formulation for the Pieri rule for the homology of Gr in terms of partitions with restricted part sizes. From this, we use a description of kcharge given by Lapointe and Pinto in [START_REF] Lapointe | Charge on tableaux and the poset of k-shapes[END_REF] in their study of the branching rules for k-Schur functions and also reformulate it in the k-bounded setting. In this setup, the Nakayashiki-Yamada correspondence with exactly solvable lattice models (or Kirillov-Reshetikhin crystals) is immediate. Another application of this new point of view is the pursuit of a combinatorial description of Gromov-Witten invariants (k-Schur structure constants). The Schur structure constants can be described by counting skew tableaux with charge zero. The combinatorics presented here is in the same vein as classical tableaux combinatorics and should be useful in approaching the k-Schur constants.

Affine Pieri rule

The ring structure in homology H * (Gr) is determined by a refinement of the Pieri rule for Schur functions. The main ingredient used in [START_REF] Lapointe | Tableaux on k +1-cores, reduced words for affine permutations, and k-Schur expansions[END_REF]Section 9] to formulate the rule is an involution on P n which refines partition conjugation. It is naturally defined through a bijection p between n-cores (partitions that have no hooks of length n) and bounded partitions:

p (γ) = (λ 1 , . . . , λ )
where λ i is the number of cells with a k-bounded hook in row i of an n-core γ. The k-conjugate of a shape λ ∈ P n is then the shape

λ ω k = p(p -1 (λ) ) ,
where λ denotes the conjugate of λ.

Theorem 2.1 [START_REF] Lapointe | A k-tableau characterization of k-Schur functions[END_REF] For any µ ∈ P n , the affine Pieri rule is

ξ m ξ µ = λ∈Hµ,m ξ λ , (8)
where the sum is over the subset of the partitions, called weak horizontal m-strips, defined by

H µ,m = {λ | λ/µ = horizontal m-strip and λ ω k /µ ω k = vertical m-strip} . (9)
Central to our study are coefficients arising in the following iteration of the affine Pieri relation:

ξ µ1 • • • ξ µ = λ K (k) λµ ξ λ . (10)
These "affine Kostka coefficients" K

λµ count certain tableaux that are defined using n-cores and another notion from modular representation theory called the n-residue (the label j -i mod n of a cell (i, j)). Definition 2.2 Let γ be a (k + 1)-core with m k-bounded hooks and let α = (α 1 , . . . , α r ) be a composition of m. A "weak k-tableau" of shape γ and weight α is a tableau of shape γ with integers 1, 2, . . . , r such that the collection of cells filled with letter i is labeled by exactly α i distinct (k + 1)-residues. Standard weak k-tableaux are those of weight (1 r ).

Note that for a weak k-tableau associated to a shape γ and weight α, in contrast to usual tableaux, |α| equals the number of k-bounded hooks in γ. We use T (λ, µ) to denote the set of weak k-tableaux of weight µ and shape p -1 (λ). This given, K

(k) λµ = |T (λ, µ)|.
The first step towards expressing affine Kostka polynomials in terms of KR crystals is to identify which recording tableaux of highest weight crystal elements correspond to weak k-tableaux. To do so, we reinterpret the Pieri rule for ξ λ in the context of a distinguished subset of semi-standard tableaux that gives yet another realization of weak k-tableaux.

Consider a semi-standard tableau T of shape λ and weight µ. Denote by λ (i) the shape of the subtableau consisting only of the letters less than or equal to i. By (9), T is a k-bounded weak k-tableau if both λ (i) /λ (i-1) and (λ (i)ω k ) /(λ (i-1)ω k ) are horizontal strips for all i ≥ 1.

(

) 11
We have discovered a new characterization for k-bounded weak k-tableaux that employs an alternate formulation of k-conjugation due to Karola Mészáros [START_REF] Mészáros | [END_REF].

Lemma 2.3 [22] [11, Chapter 2, Section 1.3]
1. Each row of a k-bounded partition λ = (λ 1 , λ 2 , . . . , λ ) ∈ P k+1 is assigned to a string as follows: the first string s 1 = (λ i1 , λ i2 , . . . , λ it ) is constructed starting with the longest part λ i1 = λ 1 and assigning other rows λ ij satisfying i j = k + 1 -λ ij-1 + i j-1 . Successively construct strings s i for i > 1, each time beginning with the longest row λ i1 that was not previously assigned to a string. Then

λ ω k = (|s 1 |, |s 2 |, . . . , |s |) .
2. The i-th part of p -1 (λ) is obtained by adding all elements in the string containing λ i that are weakly above λ i .

Example 2.4 For λ (4, 3, 3, 2, 1, 1) and k = 4, rows are assigned to the strings

3 2 1 2 1 1
, where the first cell in a row is labeled by its string, and

(λ ω4 ) = (λ 1 + λ 2 + λ 4 , λ 3 + λ 5 , λ 6 ) = (9, 4 , 1)
,

p -1 (λ) = (λ 1 + λ 2 + λ 4 , λ 2 + λ 4 , λ 3 + λ 5 , λ 4 , λ 5 , λ 6 ) = (9, 5 , 4, 2, 1, 1).
Remark 2.5 Given a partition γ where γ i < γ i-1 , let (γ i1 , . . . , γ it ) denote the string to which γ i belongs.

By construction, γ ij -1 is the first entry in its string for the smallest index i j larger than i.

We reformulate the conditions in [START_REF] Lam | k-Schur functions and affine Schubert calculus[END_REF] in terms of the strings defined in Lemma 2.3.

Lemma 2.6 Let λ, τ ∈ P k+1 such that λ/τ consists of one box in row r. Consider the string s j to which τ r is assigned and let s j >r = (τ r1 , τ r2 , . . .) be the subset of parts in s j where r 1 > r. Here we include parts of size 0. Then (λ ω k ) /(τ ω k ) is a skew partition if and only if τ ri = τ ri-1 for all i ≥ 1.

Proof: Let s 1 , s 2 , . . . and b 1 , b 2 , . . . denote the strings of τ and λ, respectively. Consider the string to which τ r belongs; s j = (τ i1 , . . . , τ ia , τ r1 , τ r2 , . . .) where r 1 > r = i a . Let s t denote the string to which τ r1-1 belongs. Note by Remark 2.5 that s t = (τ r1-1 , τ r 2 , . . .). Since λ differs from τ by only an additional box in row r, s i = b i for all i = t, j. The additional box causes r 1 = k + 1 -τ r + r = (k + 1λ r + r) + 1 and thus implies that the string to which λ r belongs is b j = (τ i1 , . . . , τ ia + 1, τ r1-1 , τ r 2 , . . .) while b t = (τ r1 , τ r2 , . . . , ). Note by the string construction that τ ri ≤ τ r i implying that

|s j | < |b j | but |s t | ≥ |b t |.
By Lemma 2.3 (1), it suffices to show that |s i | ≤ |b i | if and only if τ ri = τ ri-1 , for all i ≥ 1. Note that |s i | ≤ |b i | for all i implies that |s t | = |b t |. In turn, this ensures that τ ri = τ r i for all i. In particular, τ ri = τ ri-1 . On the other hand, given τ ri = τ ri-1 for all i, τ r i = τ ri-1 and the claim follows.

2

Example 2.7 Take k = 5 and the partition τ with the strings as indicated

2 3 4 1 2 3 1 2 1
.

Then adding a box to row 2 of τ yields λ such that (λ ω k ) /(τ ω k ) is a valid skew partition since τ 4 = τ 5 and τ 8 = τ 9 , but adding a box in row 4 would not be allowed since τ 8 = τ 7 .

Let λ, τ ∈ P k+1 such that λ/τ is a horizontal strip. Suppose that for a given row r the skew partition λ/τ contains boxes, set r 1 = r + k + 1 -τ r (that is, the smallest row in τ above row r in the same string as row r), and let s = (λ r1 , λ r2 , . . .) be the tuple of parts of λ weakly above row r 1 that belong to the string of Lemma 2.3 passing through row r 1 . Again we include parts of size 0.

Lemma 2.8 With the notation above, (λ ω k ) /(τ ω k ) is a horizontal strip if and only if λ ri = τ ri-for all i ≥ 1 and all rows r with > 0.

Proof: The lemma follows from Lemma 2.6 by successively adding boxes. Adding boxes in different strings in τ is independent. Boxes within the same string need to be added from top to bottom, left to right.

2

Example 2.9 Take k = 5 and τ = we have = 1 cells in row 1 of λ/τ and r 1 = 3, but 0 = λ 5 = λ r2 = τ r2-= τ 4 = 1. Hence λ/τ is not a weak horizontal strip for k = 5.

Given the Pieri rule Theorem 2.1, we may deduce a different formulation.

Theorem 2.10 Let 1 ≤ m < n and τ ∈ P n . The Pieri rule in H * (Gr) can be described by

ξ m ξ τ = λ ξ λ , (12)
over all partitions λ ∈ P n where λ/τ is a horizontal m-strip and λ ri = τ ri-for all i ≥ 1 and all rows r in λ/τ with > 0 boxes, where r i is as defined in Lemma 2.8.

Theorem 2.11

Let T be a semi-standard tableau of k-bounded shape λ and weight µ. Then T is a kbounded weak k-tableau if for each letter i in T , the skew shape λ (i) /λ (i-1) satisfies the conditions of Lemma 2.8.

Proof: This follows directly from Lemma 2.8 by noting that for a semi-standard tableau T of k-bounded shape, condition (11) must hold for every λ (i) /λ (i-1) in order to correspond to a weak k-tableau. 2

As a corollary of Theorem 2.11 we can now determine which highest weight crystal elements contribute to a k-Schur expansion of the Hall-Littlewood polynomials. Namely, it will be those whose insertion tableau is a k-bounded weak k-tableau by the conditions in Theorem 2.11. This, together with the kcharge in this language, is summarized in Theorem 3.8.

Example 2.12 Let us determine which insertion tableaux from Example 1.1 contribute for k = 3. Since the shape needs to be 3-bounded only the first four tableaux in (5) can potentially contribute. Looking at the strings in λ (i) /λ (i-1) for each i = 1, 2, 3 we find that

3 2 2 1 1 : 1 → 2 1 → 1 2 1 3 2 1 1 2 : 1 → 1 1 → 2 1 1 2 3 1 1 2 : 1 → 1 1 → 1 1
satisfy the conditions of Lemma 2.8 and hence contribute. On the other hand

2 2 1 1 3 : 1 → 2 1 → 1 1
does not satisfy the condition of Lemma 2.8 for λ (3) /λ (2) since in this case τ = (2, 2), r = 1, = 1, r 1 = 3, and

0 = λ 3 = τ 2 = 2.
Since the shapes of the surviving tableaux are (2, 2, 1), (3, 1, 1), and (3, 2), this agrees with the terms in the 3-Schur expansion in [START_REF] Lapointe | Charge on tableaux and the poset of k-shapes[END_REF]. How to obtain the powers of t is discussed in the next section.

Affine charge

In [START_REF] Lapointe | Charge on tableaux and the poset of k-shapes[END_REF], Lapointe and Pinto introduced a statistic called k-charge on weak k-tableaux. In analogy to (3), the affine Kostka numbers are thus lifted to affine Kostka polynomials

K (k) λµ (t) = T ∈T (λ,µ) t kcharge(T ) . (13)
It was recently proven [START_REF]Several approaches to affine charge[END_REF] that the functions S λ (x; t) can be defined in these terms. The k-charge statistic is easiest to describe first on standard (of weight (1 n )) weak k-tableaux. Let diag(c 1 , c 2 ), associated to cells c 1 and c 2 in a (k + 1)-core, be the number of diagonals of residue x that are strictly between c 1 and c 2 where x is the residue of the lower cell. Instead of taking a cell as input, the diag function can also take a specific instance of an entry in the tableau as input (which then determines a cell). Definition 3.1 Given a standard weak k-tableau T on m letters, put a bar on the topmost occurrence of letter r, for each r = 1, . . . , m. Define the index of T , starting from I 1 = 0, by

I r = I r-1 + 1 + diag(r, r -1) if r is east of r -1, I r-1 -diag(r, r -1) otherwise , (14)
for r = 2, . . . , m. The k-charge of T is the sum of entries in I(T ), denoted by kcharge(T ).

The definition of k-charge extends to semi-standard weak k-tableaux by successively computing an appropriate choice of standard sequences. The trick is to introduce a method for making this choice in weak k-tableaux. Definition 3.2 From an x (of some residue i) in a semi-standard k-tableau T , the appropriate choice of x + 1 will be determined by choosing its residue from the set A of all (k + 1)-residues labelling x + 1's. Reading counter-clockwise from i, this choice is the closest j ∈ A on a circle labelled clockwise with 0, 1, . . . , k.

A standard subtableau is extracted by choosing the rightmost x = 1 and then selecting subsequent letters x using the choice of Definition 3.2. The same procedure is then repeated with the yet unselected letters.

Example 3.3 For k = 3, we compute the k-charge:

3 2 1 1 2 2 3 2 1 1 2 2 3 2 1 1 2 2
=⇒ kcharge = (0 + 0 + 0) + (0 + 1) = 1

Hall-Littlewood polynomials {H µ (x; t)} arise as the basis dual to {P µ (x; t)} with respect to the Hall inner product m λ , h µ = δ λµ , where m λ are the monomial symmetric functions and h λ are the complete homogeneous symmetric functions. Hence, [START_REF] Kostant | The nil Hecke ring and cohomology of G/P for a Kac-Moody group G[END_REF] implies that

H µ (x; t) = λ K (k) λµ (t) s (k) λ (x; t) , (15)
with charge(w (1,4) ) + charge(w (2,4) ) = 4 + 7 = 11. Note that the words selected for the usual charge (or for large k) are different w (1,∞) = 7326154 and w (2,∞) = 651432

with charge(w (1,∞) ) + charge(w (2,∞) ) = 4 + 5 = 9.

The term diag(r, r -1) in the definition of the index in Definition 3.1 can be elegantly expressed in terms of the strings in the partition λ (r) (or λ (r-1) ). Recall that the letter r in a weak k-tableaux in the (k + 1)-core setting becomes the letter r in the k-bounded analogue. Lemma 3.6 Let T be a k-bounded weak k-tableau.

1. If r is east of r -1 in T , diag(r, r -1) is the number of rows strictly between the rows containing r and r -1 that are in the same string as the row containing r in λ (r) .

2. Otherwise, diag(r, r -1) is the number of rows strictly between the rows containing r and r -1 that are in the same string as the row containing r -1 in λ (r-1) .

Proof: Suppose that r is east of r -1 in T . By definition, diag(r, r -1) is the number of diagonals of the same residue as the cell containing r between r and r -1 in the (k + 1)-core analogue p -1 (T ) of T .

In other words, it counts how many multiples of k + 1 are in the number of cells between r and r -1 when forming a hook between the two cells. Note that by Lemma 2.3(2) that describes how to pass from a k-bounded partition to a (k + 1)-core using the strings, it suffices to restrict in T to the rows between r and r -1. Consider λ (r) and let λ(r) be the restriction of λ (r) to the rows weakly between r and r -1 in T . The hook distance between r and r -1 in p -1 (T ) is the same as the hook distance in p -1 ( λ(r) ) between the corresponding cells. Note that by the definition of strings, the hook distance between the cells at the end of the rows in rows of the same string is always k + 1. This proves the claim for part [START_REF] Butler | Subgroup lattices and symmetric functions[END_REF]. Part (2) can be argued in a similar fashion. Since the strings of the lower cell matter, one uses λ (r-1) in this case.

2

With the definitions and results above, the k-charge of Definition 3.1 can be written as where the sum is over all k-bounded weak k-tableaux of shape λ and weight µ as characterized in Theorem 2.11 with k-charge as computed in this section.

Since the recording tableaux of the highest weight KR crystal elements are given in the k-bounded language, this can be translated directly to the statistical mechanical formulation of the affine Kostka-Foulkes polynomials via [START_REF] Nakayashiki | Kostka polynomials and energy functions in solvable lattice models[END_REF] as demonstrated in Example 2.12.

  so that λ/τ has cells in rows 1 and 4. Note that for row 1, we have r 1 = 4, = 1 and 2 = λ r1 = τ r1-. Similarly, for row 4 we have r 1 = 10, = 2 and 0 = λ r1 = τ r1-. Hence λ/τ is a weak horizontal strip for k = 5.On the other hand, for

# 17 ) 3 . 7

 1737 kcharge(T ) = charge(w (k) ) + O(T ), where O(T ) = r≥1 O r (T ) with O 1 (T ) = 0 and O r = O r-1 + of rows strictly between rows containing if r east of r -1, r and r -1 in same string as r in λ (r) -# of rows strictly between rows containing otherwise. r and r -1 in same string as r -1 in λ (r-1) (Example Let us compute O r (T ) for T in Example 3.5. For the first selected standard word we get a contribution to (17) from r = 4 and r = 5 of 1 and -1, respectively (where we filled the rows contributing to (17))

Theorem 3 . 8

 38 so that O 4 (T ) = 1 and all other O r (T ) = 0, which implies O(T ) = 1 and kcharge(T ) = 12. Let λ, µ ∈ P n . Then the affine Kostka-Foulkes polynomial is given byK w λ ,µ (t) = T t kcharge(T ) ,

2 2 1 1 , 3 2 1 1 2 , 2 2 1 1 3 , 2 3 1 1 2 ,(5)

† Partially supported by the NSF grant DMS-1301695. ‡ Partially supported by the NSF grant OCI-1147247.

where {s (k) λ (x; t)} λ∈P n is the dual basis to {S λ (x; t)} λ∈P n . At t = 1, s (k) λ (x; t) reduce to the parameterless k-Schur functions (discussed in the introduction).

Example 3. [START_REF] Fourier | Kirillov-Reshetikhin crystals for nonexceptional types[END_REF] We have

221 + ts [START_REF] Garsia | On certain graded Sn-modules and the q-Kostka polynomials[END_REF] 311 + (t + t 2 )s [START_REF] Garsia | On certain graded Sn-modules and the q-Kostka polynomials[END_REF] 32 + (t 2 + t 3 )s

where we have dropped the dependence on x and t in the notation. For example, the coefficient of s

The k-charge in terms of (k + 1)-cores as given in Definitions 3.1 and 3.2 can be reformulated for k-bounded weak k-tableaux.

Given a k-bounded weak k-tableau T as characterized by Theorem 2.11, recall that λ (i) denotes the shape of T restricted to the letters smaller or equal to i. Draw all intermediate shapes λ (i) together with their corresponding strings. Then for the new boxes in each step, compute the residues using p -1 (λ) as described in Lemma 2.3 (2). Definition 3.2 is still used to select the standard subtableaux. From these we can obtain subwords w (1,k) , . . . , w ( ,k) by reading the selected cells columnwise top to bottom, left to right. The definition of index in Definition 3.1 without the terms diag(r, r -1) is the usual charge of the subwords w (1,k) , . . . , w ( ,k) . This is due to the fact that the topmost ocurrence of the letter r, which we denoted r, in a weak k-tableau in the (k + 1)-core setting becomes the letter r in the k-bounded analogue under the map p. Note, however, that the selected subwords do depend on k and for small k are usually different from the subwords selected for the usual charge of T . which is the k-bounded analogue of [START_REF] Lam | k-Schur functions and affine Schubert calculus[END_REF]Chapter 2,Example 3.20]. Now we draw the sequence of partitions λ (i) and mark the strings in the left columns and the residues of the added boxes as exponents at each step:

.

The cells selected for w (1,4) are marked in bold which shows that w (1,4) = 7653214 and w (2,4) = 164352