Steven N Karp
email: skarp@berkeley.edu.

Sign variation, the Grassmannian, and total positivity

Keywords: sign variation, totally nonnegative Grassmannian, oriented matroid, positroid, Grassmann necklace

Introduction

The (real) Grassmannian Gr k,n is the set of k-dimensional subspaces of R n . Given V ∈ Gr k,n , take a k × n matrix A whose rows span V ; then for k-subsets I ⊆ {1, • • •, n}, we let ∆ I (V ) be the k × k minor of A with columns I. (The ∆ I (V ) depend on our choice of A only up to a global constant.) If all nonzero ∆ I have the same sign, then V is called totally nonnegative. For example, the span of (1, 0, 0, -1) and (-1, 2, 1, 3) is a totally nonnegative element of Gr 2,4 . The set of such V , called the totally nonnegative Grassmannian, has become a hot topic in algebraic combinatorics in the past two decades. The general algebraic study of total positivity (for reductive algebraic groups G and partial flag varieties G/P ) was initiated by Lusztig [START_REF] Lusztig | Total positivity in reductive groups[END_REF]. The totally nonnegative Grassmannian (the particular case G/P = Gr k,n ) was later studied from a combinatorial perspective by Postnikov [Pos]. Of particular interest to us is the stratification of the totally nonnegative Grassmannian by whether each ∆ I is zero or nonzero. This stratification is a cell decomposition, which was conjectured by Lusztig [START_REF] Lusztig | Total positivity in reductive groups[END_REF] and proved by Rietsch [START_REF] Rietsch | An algebraic cell decomposition of the nonnegative part of a flag variety[END_REF] (for the general case G/P ), and later proved combinatorially by Postnikov [Pos]. Total positivity originated, however, in the 1930's in oscillation theory in analysis, where positivity conditions on matrices can imply special oscillation and spectral properties. It was in this context that Gantmakher and Krein [START_REF] Gantmakher | Ostsillyatsionnye matritsy i yadra i malye kolebaniya mekhanicheskikh sistem. Gosudarstvennoye Izdatel'stvo Tekhniko-Teoreticheskoy Literatury[END_REF], and independently Schoenberg and Whitney [START_REF] Schoenberg | A theorem on polygons in n dimensions with applications to variation-diminishing and cyclic variation-diminishing linear transformations[END_REF], proved the first result about (what would later be called) the totally nonnegative Grassmannian. Theorem 1.1 (5.3 of [START_REF] Gantmakher | Ostsillyatsionnye matritsy i yadra i malye kolebaniya mekhanicheskikh sistem. Gosudarstvennoye Izdatel'stvo Tekhniko-Teoreticheskoy Literatury[END_REF], [START_REF] Schoenberg | A theorem on polygons in n dimensions with applications to variation-diminishing and cyclic variation-diminishing linear transformations[END_REF]). An element V of Gr k,n is totally nonnegative iff all vectors in V (viewed as sequences of n numbers, ignoring any zeros) change sign fewer than k times.

For example, the two vectors (1, 0, 0, -1) and (-1, 2, 1, 3) each change sign exactly once, and we can check that any vector in their span changes sign at most once. Every element of Gr k,n has a vector which changes sign at least k -1 times (put a k × n matrix whose rows span V into row reduced echelon form, and take the alternating sum of the rows), so the totally nonnegative elements are those whose vectors change sign as few times as possible.

There are two main results in this paper. The first generalizes Theorem 1.1 to all V ∈ Gr k,n by giving a criterion for when the vectors in V change sign fewer than l times, in terms of the ∆ I (V ). (Theorem 1.1 is the case l = k; see Corollary 4.7 for details.) The second shows, in the case that V is totally nonnegative, how to determine the cell of V in the cell decomposition of the totally nonnegative Grassmannian.

We now describe our first main result, split into two parts (Theorem 1.2 and Theorem 1.4). For more details see Section 2, specifically Theorem 2.1 and Theorem 2.7. Theorem 1.2. (i) If the vectors in V ∈ Gr k,n change sign fewer than l times, then (∆ J∪{i} (V )) i / ∈J changes sign fewer than l -k + 1 times for all (k -1)-subsets

J ⊆ {1, • • •, n}. (ii) If V ∈ Gr k,n such that ∆ I (V ) = 0 for all k-subsets I ⊆ {1, • • •, n}, and (∆ J∪{i} (V )) i /
∈J changes sign fewer than l -k + 1 times for all (k -1)-subsets J ⊆ {1, • • •, n}, then the vectors in V change sign fewer than l times.

Example 1.3. Let V ∈ Gr 2,4 be the row span of the matrix 1 0 -2 3 0 2 1 4 . Then ∆ I (V ) = 0 for all 2-subsets I ⊆ {1, 2, 3, 4}, so the fact that the vectors in V change sign fewer than l := 3 times is equivalent to the fact that the 4 sequences

(∆ {1,2} (V ), ∆ {1,3} (V ), ∆ {1,4} (V )) = (2, 1, 4), (∆ {1,2} (V ), ∆ {2,3} (V ), ∆ {2,4} (V )) = (2, 4, -6), (∆ {1,3} (V ), ∆ {2,3} (V ), ∆ {3,4} (V )) = (1, 4, -11), (∆ {1,4} (V ), ∆ {2,4} (V ), ∆ {3,4} (V )) = (4, -6, -11)
each change sign fewer than l -k + 1 = 2 times.

Part (ii) of Theorem 1.2 applies only to generic elements of Gr k,n , i.e. those V such that ∆ I (V ) = 0 for all I. In the case that V is not generic, we show how to construct a generic perturbation W of V , such that if the vectors in V change sign fewer than l times, then so do the vectors in W . (A perturbation of V is an element V ∈ Gr k,n such that for all k-subsets I ⊆ {1, • • •, n} with ∆ I (V ) nonzero, ∆ I (V ) is also nonzero with the same sign as ∆ I (V ).) This gives the following generalization of Theorem 1.2 to non-generic V .

Theorem 1.4. The vectors in V ∈ Gr k,n change sign fewer than l times iff there exists a generic perturbation V of V such that

(∆ J∪{i} (V )) i / ∈J changes sign fewer than l -k + 1 times for all (k -1)-subsets J ⊆ {1, • • •, n}. (1)
By a certain algorithm (see Theorem 2.7) we can construct a generic perturbation W of V ∈ Gr k,n such that the vectors in V change sign fewer than l times iff (1) holds for V = W .

The algorithm involves perturbing one coordinate of V by an adjacent coordinate at most 2(n -1)(n -k) times; see Theorem 2.7 for the details. The natural framework in which to consider sign patterns of vectors in V , and signs of the ∆ I (V ), is that of oriented matroids. Our results hold in this context, suitably interpreted in the language of oriented matroids (see Section 4), and are more general because while every subspace gives rise to an oriented matroid, not every oriented matroid comes from a subspace.

We now describe our second main result. For each totally nonnegative V ∈ Gr k,n , we define the positroid of V as the set of k-subsets I of {1, • • •, n} such that ∆ I (V ) is nonzero. The stratification of the totally nonnegative Grassmannian by positroids is a cell decomposition [START_REF] Rietsch | An algebraic cell decomposition of the nonnegative part of a flag variety[END_REF][START_REF] Postnikov | Total positivity, Grassmannians, and networks[END_REF]. We also define the Grassmann necklace of V as the n-tuple

(I 1 , • • •, I n ) of k-subsets of {1, • • •, n}
, where I j is the lexicographically minimal I such that ∆ I (V ) = 0, with respect to the total order ≤ j on {1, • • •, n} given by j < j j + 1 [Pos] showed that the positroid of V is uniquely determined by its Grassmann necklace.

< j • • • < j n < j 1 < j • • • < j j -1. Postnikov
How can we determine the positroid of V , or equivalently its Grassmann necklace, from the sign patterns of vectors in V ? Given a subset I ⊆ {1, • • •, n} and a sign vector ω ∈ {+, -} I , we say that V realizes ω if there exists a vector in V whose restriction to I has signs given by ω. For example, if (2, 3, -2, -1) ∈ V , then V realizes (+, -, -) on {1, 3, 4}. It is not difficult to show that for all V ∈ Gr k,n , we have ∆ I (V ) = 0 iff V realizes all 2 k sign vectors in {+, -} I . Furthermore, we potentially have to check all of the 2 k sign vectors, since given any ω ∈ {+, -} I (and assuming n > k), there exists a V ∈ Gr k,n which realizes all 2 k sign vectors in {+, -} I except for ±ω. However, in the case that V is totally nonnegative, we show that we need only check 2k particular sign vectors in {+, -} I to verify that ∆ I (V ) = 0, and moreover that we can use these sign vectors to pick out the Grassmann necklace of V .

Theorem 1.5. Suppose that V ∈ Gr k,n is totally nonnegative.

(i) (Positroid criterion) Let J be a k-subset of {1, • • •, n}. Then ∆ J (V ) = 0 iff V realizes all 2k
sign vectors in {+, -} J which alternate between every pair of consecutive components, with at most one exceptional pair. (For example, if k = 5 these sign vectors are (+,+,+),(+,+,+,(+,+,(+,+,+,(+,+,, and their negations.) (ii) (Grassmann necklace criterion) Let (I 1 , • • •, I n ) be the Grassmann necklace of V . Then I j is the j-Gale minimum among all k-subsets J of {1, • • •, n} such that V realizes a sign vector on J which alternates except precisely from component max({i ∈ J : i < j}) to component min({i ∈ J : i ≥ j}) (if both components exist). (For example, if J = {1, 4, 6, 8, 9} and j = 7, then such a sign vector is (+, -, +, +, -) or its negation. The j-Gale order is given by {i

1 < j • • • < j i k } ≤ j-Gale {i 1 < j • • • < j i k } iff i 1 ≤ j i 1 , • • •, i k ≤ j i k .)
Neither (i) nor (ii) hold for all V ∈ Gr k,n ; see Example 3.8 and Example 3.3. For further details on Theorem 1.5 see Section 3, specifically Corollary 3.6 and Corollary 3.4.

Example 1.6. Let V ∈ Gr 3,5 be the row span of the matrix   2 1 0 0 3 0 0 1 0 0 0 0 0 1 1   , which is totally nonnegative. Part (i) of Theorem 1.5 states that for 3-subsets I of {1, 2, 3, 4, 5}, we have ∆ I (V ) = 0 iff the 3 sign vectors (+, -, +), (+, +, -), (+, -, -) on I are realized by V . For I = {1, 3, 5}, the vectors (2, 1, -1, 0, 3), (2, 1, 1, -4, -1), (2, 1, -1, -4, -1) in V realize the sign vectors (+, -, +), (+, +, -), (+, -, -) on I, so ∆ {1,3,5} (V ) = 0. (We do not need to check that (+, +, +), the remaining sign vector on I up to sign, is realized.) For I = {1, 4, 5}, the vectors (2, 1, 0, -1, 2) and (2, 1, 0, -4, -1) in V realize the sign vectors (+, -, +) and (+, -, -) on I, but no vector in V realizes the sign vector (+, +, -) on I, so ∆ {1,4,5} (V ) = 0. Part (ii) of Theorem 1.5 for j = 1 states that the lexicographic minimum I 1 = {1, 3, 4} of the positroid of V is also the Gale minimum of {{1, 3, 4}, {1, 3, 5}, {1, 4, 5}, {2, 3, 4}, {2, 3, 5}, {2, 4, 5}, {3, 4, 5}}, the set of 3-subsets of {1, 2, 3, 4, 5} on which V realizes the alternating sign vector (+, -, +).

3

Acknowledgements. I thank Lauren Williams, my advisor, for many helpful conversations and suggestions. I also thank Sylvie Corteel and the Laboratoire d'Informatique Algorithmique: Fondements et Applications at Université Paris Diderot for hosting me while I conducted this work.

Sign changes and the Grassmannian

In this section we characterize the maximum number of times a vector in V changes sign, in terms of the Plücker coordinates of V . In the case that V is generic, we give a direct criterion (Theorem 2.1); otherwise, we show how to perturb V into a generic subspace, whence we may apply the same criterion to the perturbation (Theorem 2.7).

We introduce some terminology. Let Gr k,n denote the Grassmannian of k-dimensional subspaces of R n . Given V ∈ Gr k,n , take a k × n matrix A whose rows span V . For I ∈ [n] k , we define the Plücker coordinate ∆ I (V ) as the minor of A which uses the columns in I (where [n] k denotes the set of k-subsets of [n] := {1, • • •, n}). Note that if A is another k × n matrix whose rows span V , then the corresponding minors of A and A are equal up to multiplication by a global nonzero constant. Hence ∆(V ) is welldefined in the projective space P ( n k )-1 . Also, for v ∈ R n and I ⊆ [n], we say that v alternates on I if the components of v alternate sign on I, i.e.

I = {i 1 , • • •, i k } (i 1 < • • • < i k ) and v i1 v i2 , v i2 v i3 , • • •, v i k-1 v i k are all negative.
For example, (3, 1, -2) alternates on {1, 3} and {2, 3}, but not on {1, 2}. The number of sign changes of v ∈ R n is one less than the maximum size of a subset I ⊆ [n] on which v is alternating. For example, (3, 1, -2) changes sign once.

We say that

V ∈ Gr k,n is generic if ∆ I (V ) = 0 for all I ∈ [n]
k . We have the following criterion for when the vectors in a generic V change sign fewer than l times.

Theorem 2.1. (i) If the vectors in V ∈ Gr k,n change sign fewer than l times, then (∆ J∪{i} (V )) i / ∈J changes sign fewer than l -k + 1 times for all J ∈ [n] k-1 .

(ii) If V ∈ Gr k,n is generic and (∆ J∪{i} (V )) i / ∈J changes sign fewer than l -k + 1 times for all J ∈ [n] k , then the vectors in V change sign fewer than l times.

We give an example which shows that part (ii) above does not hold for all V ∈ Gr k,n .

Example 2.2. Let V ∈ Gr 2,4 be the row span of the matrix 1 0 1 0 0 1 0 1 . Note that the 4 sequences of Plücker coordinates

(∆ {1,2} (V ) : ∆ {1,3} (V ) : ∆ {1,4} (V )) = (1 : 0 : 1), (∆ {1,2} (V ) : ∆ {2,3} (V ) : ∆ {2,4} (V )) = (1 : -1 : 0), (∆ {1,3} (V ) : ∆ {2,3} (V ) : ∆ {3,4} (V )) = (0 : -1 : 1), (∆ {1,4} (V ) : ∆ {2,4} (V ) : ∆ {3,4} (V )) = (1 : 0 : 1)
each change sign fewer than l -k + 1 = 2 times (where we take l := 3), but the vector (1, -1, 1, -1) ∈ V changes sign l = 3 times. Note that if we were forced to pick a sign for ∆ {1,3} (V ), then either the first or third sequence above would change sign twice. This motivates the introduction of perturbations below. 3

Given V, V ∈ Gr k,n , we say that V is a perturbation of V if for all I ∈ [n] k with ∆ I (V ) nonzero, ∆ I (V )
is also nonzero and has the same sign as ∆ I (V ). It is not hard (using the theory of oriented matroids; see Definition 4.3) to show that if the vectors in V change sign fewer than l times, then so do the vectors in V . Conversely, however, if the vectors in V change sign fewer than l times, it is not obvious that there exists a nontrivial perturbation V of V whose vectors also change sign fewer than l times. This is what we now show, leading up to a generalization of Theorem 2.1 to such non-generic V (Theorem 2.7). We build our perturbations using sequences of elementary perturbations called i → j-perturbations.

Definition 2.3 (i → j-perturbation). Let i, j ∈ [n] be distinct and ∈ {+, -}. Given V ∈ Gr k,n , take a k × n matrix A = [x (1) | • • • |x (n) ] whose rows span V , where x (1) , • • •, x (n) ∈ R k are column vectors. For α ∈ R, let V ∈ Gr k,n be the row span of the k × n matrix A := [x (1) | • • • |x (j-1) |x (j) + αx (i) |x (j+1) | • • • |x (n) ].
(Note that V depends only on α, not on our choice of A.) We say that V is an i → j-perturbation of V if α is nonzero, has the same sign as , and is sufficiently small that if I ∈ [n] k indexes a nonzero minor of A, then the I-minor of A is also nonzero with the same sign.

The possible values of α form an open interval between 0 and some number, or ±∞, with sign .

Example 2.4. Let V ∈ Gr 2,4 be the row span of the matrix A := 1 0 2 0 0 3 -1 4 , and for α < 0 let V ∈ Gr 2,4 be the row span of the perturbed matrix A := 1 0 2 α 0 3 -1 4 . Note that the {3, 4}-minor of A equals 8, and the {3, 4}-minor of A equals 8 + α, so we should pick α > -8 so that these minors agree in sign. In fact, for any α ∈ (-8, 0) the I-minors of A and A have the same sign whenever the

I-minor of A is nonzero (for I ∈ [4] 2 ), whence V is a 1 → -4-perturbation of V . 3
If the vectors in V ∈ Gr k,n change sign fewer than l times, then certain i → j-perturbations preserve this property, and are in fact sufficient to perturb V into a generic subspace.

Lemma 2.5. (i) If the vectors in V ∈ Gr k,n change sign fewer than l times, then so do the vectors in any (i + 1) → + i-, i → + (i + 1)-, 1 → (-1) l-1 n-, or n → (-1) l-1 1-perturbation of V (for any i ∈ [n -1]).

(ii) Applying the sequence of perturbations

2 → 1, 3 → 2, • • •, n → (n -1), 1 → n, 2 → 1, 3 → 2, • • •, (n -1) → (n -2)
in order from left to right n -k times to any V ∈ Gr k,n gives a generic subspace. (Here an i → jperturbation denotes either of the i → j-perturbations for ∈ {+, -}; the sign of is not important.) Similarly, applying the sequence of perturbations

2 → 1, 3 → 2, • • •, n → (n -1), (n -1) → n, (n -2) → (n -1), • • •, 1 → 2
in order from left to right n -k times to any V ∈ Gr k,n gives a generic subspace.

Note that part (i) above follows in general from the specific case of 2 → + 1-perturbations, by the following symmetries: if the vectors in the row span of the matrix [x (1) | • • • |x (n) ] change sign fewer than l times, then so do the vectors in the row span of the cyclic shift

[x (2) | • • • |x (n) |(-1) l-1 x (1) ] and the reversal [x (n) | • • • |x (1)
]. Also note that part (ii) above gives two specific algorithms for constructing a generic perturbation of any V ∈ Gr k,n in 2(n -1)(n -k) < 2n 2 steps.

Example 2.6. Let V ∈ Gr 2,3 be the row span of the matrix 0 1 3 1 0 0 , whose vectors change sign fewer than l := 2 times. Then V is not generic, but we can get a generic subspace by applying a 1 → -3perturbation, which gives the row span of 0 1 3 1 0 α (α < 0), or by applying a 1 → + 2-perturbation, which gives the row span of 0 1 3 1 β 0 (β > 0). The vectors in these two subspaces change sign fewer than l = 2 times. Note that we cannot make V generic by applying only 2 → 1and 3 → 2-perturbations. Also note that, for example, applying a 1 → -2-perturbation gives the row span of 0 1 3 1 γ 0 (γ < 0), which has a vector (e.g. (-2 γ , -1, 3)) that changes sign twice. 3

Theorem 2.7. The vectors in V ∈ Gr k,n change sign fewer than l times iff there exists a generic perturbation V of V such that (∆ J∪{i} (V )) i / ∈J changes sign fewer than l -k + 1 times for all J ∈ [n] k-1 . Explicitly, let W be obtained from V ∈ Gr k,n by applying the sequence of perturbations

2 → + 1, 3 → + 2, • • •, n → + (n -1), 1 → (-1) l-1 n, 2 → + 1, 3 → + 2, • • •, (n -1) → + (n -2)
in order from left to right n -k times, or by applying the sequence of perturbations

2 → + 1, 3 → + 2, • • •, n → + (n -1), (n -1) → + n, (n -2) → + (n -1), • • •, 1 → + 2
in order from left to right n -k times, so that W is a generic perturbation of V . Then the following are equivalent: (i) the vectors in V change sign fewer than l times; (ii) the vectors in W change sign fewer than l times; and (iii) (∆ J∪{i} (W )) i / ∈J changes sign fewer than l -k + 1 times for all J ∈ [n] k-1 .

In principle the results in this section are about components of vectors in subspaces, and their Plücker coordinates, only up to sign (zero, positive, or negative). There is an object M(V ) which, given V ∈ Gr k,n , records precisely the vectors of V up to sign, or equivalently the Plücker coordinates ∆(V ) up to sign; it is called the oriented matroid associated to V . There is a general notion of an oriented matroid, among which those of the form M(V ) comprise the strict subset of realizable oriented matroids. All the results in this section generalize naturally to oriented matroids, using the following dictionary: subspaces oriented matroids sign vectors of vectors in

V covectors of M(V ) ∆(V ), up to sign the chirotope χ M(V ) V is generic M(V ) is uniform V is a perturbation of V M(V ) ≤ M(V )
We also generalize i → j-perturbation to oriented matroids. We give precise statements in Section 4.

Positroids from sign patterns

We say that V ∈ Gr k,n is totally nonnegative if ∆ I (V ) ≥ 0 for all I ∈ [n] k (or equivalently, ∆ I (V ) ≤ 0 for all I ∈ [n] k , since ∆(V ) is defined in projective space). Let Gr ≥0 k,n be the subset of Gr k,n of totally nonnegative elements, called the totally nonnegative Grassmannian. The goal of this section is to describe several ways to recover the positroid cell of a given V ∈ Gr ≥0 k,n from the sign patterns of vectors in V . For V ∈ Gr k,n , let M (V ) := {I ∈ [n] k : ∆ I (V ) = 0} be the matroid of V . In the case that V is totally nonnegative, we call M (V ) a positroid. Postnikov [Pos] showed that the positroid stratification of Gr ≥0 k,n (i.e. its partition into equivalence classes, where

V ∼ W iff M (V ) = M (W )
) is a cell decomposition, which coincides with the one earlier conjectured by Lusztig [START_REF] Lusztig | Total positivity in reductive groups[END_REF] and proven by Rietsch [START_REF] Rietsch | An algebraic cell decomposition of the nonnegative part of a flag variety[END_REF] in the more general context of total positivity in partial flag varieties G/P . Postnikov constructed in particular, for each stratum, a homeomorphism between R d >0 and the stratum using a certain bicolored planar graph 1 drawn inside a disk. He also showed that for V ∈ Gr ≥0 k,n , the positroid M (V ) is uniquely determined by its Grassmann necklace

(I 1 , • • •, I n ) ∈ [n] k n
, where I j (for j ∈ [n]) is the lexicographic minimum of M (V ) with respect to the total order ≤ j on [n] given by j < j j + 1

< j • • • < j n < j 1 < j • • • < j j -1.
For example, the Grassmann necklace of the positroid M = [4] 2 is ({1, 2}, {2, 3}, {3, 4}, {4, 1}). Given V ∈ Gr ≥0 k,n , how can we determine the positroid M (V ), or equivalently its Grassmann necklace, from the sign vectors of V , i.e. those ω ∈ {0, +, -} n such that some vector in V has signs given by ω? It follows from the theory of oriented matroids (see Section 4) that for any V ∈ Gr k,n , given the signs (either 0, +, or -) of all Plücker coordinates ∆ I (V ), we can determine the sign vectors of V , and vice versa. Hence we can recover M (V ) from the sign vectors of V . We now focus on criteria for V ∈ Gr ≥0 k,n which take advantage of the special properties of the totally nonnegative Grassmannian.

Oh [START_REF] Oh | Positroids and Schubert matroids[END_REF] explicitly described a positroid in terms of its Grassmann necklace. With Corollary 3.4, we immediately get a characterization of the positroid of V ∈ Gr ≥0 k,n in terms of sign patterns of vectors in V . Given I ⊆ [n] and a sign vector ω ∈ {+, -} I , we say that V realizes ω if there exists a vector in V whose restriction to I has signs given by ω.

Theorem 3.5 (Theorem 6 of [START_REF] Oh | Positroids and Schubert matroids[END_REF]). Suppose that M is a set of k-subsets of [n] which is a matroid with Grassmann necklace

(I 1 , • • •, I n ) ∈ [n] k n . Then M is a positroid iff M = {J ∈ [n] k : I j ≤ j-Gale J for j ∈ [n]}.
Corollary 3.6. For all V ∈ Gr ≥0 k,n and I ∈ [n] k , we have I ∈ M (V ) iff V realizes all 2k sign vectors in {+, -} I which alternate between every pair of consecutive components, with at most one exceptional pair.

We remark that we can also prove Corollary 3.6 directly from Theorem 1.1, as follows. If I ∈ M (V ) then V | I = R I , and so V realizes all sign vectors on I. Conversely, if I / ∈ M (V ), then we take j ∈ [n] \ I such that V | I∪{j} has rank greater than that of V | I , i.e. there exists a vector v ∈ V with v| I = 0 and v j = 0. Using v, we can extend any sign vector which V realizes on I to a sign vector which V realizes on I ∪ {j}, with our choice of sign in component j. Since no vector in V alternates on I ∪ {j}, there is no vector in V which alternates on I except precisely from component max(I ∩ [1, j)) to component min(I ∩ [j, n]) (if both components exist).

By way of contrast to Corollary 3.6, we offer a similar criterion for general V ∈ Gr k,n , which is not difficult to prove using the fact that

I ∈ M (V ) iff V | I = R I .
Proposition 3.7. For V ∈ Gr k,n and I ∈ [n] k , we have I ∈ M (V ) iff V realizes all 2 k sign vectors in {+, -} I .

Moreover, given ω ∈ {+, -} I , we can construct V ∈ Gr k,n (assuming n > k) such that V realizes all 2 k sign vectors in {+, -} I except for ±ω, by taking v ∈ R I with sign vector ω and letting V | I be the hyperplane in R I perpendicular to v. Thus for general V ∈ Gr k,n , we potentially need to check (up to sign) that 2 k-1 sign vectors on I are realized, whereas if V is totally nonnegative then we need only check k by Corollary 3.6. We give an explicit example of this phenomenon.

Example 3.8. Let V ∈ Gr 3,4 be the row span of the matrix   1 0 -1 0 0 1 -1 0 0 0 0 1   , which is not totally nonnegative, and let I := {1, 2, 3}. Then the vectors (1, -2, 1, 0), (1, 1, -2, 0), (2, -1, -1, 0) in V realize the sign vectors (+, -, +), (+, +, -), (+, -, -) on I, but I / ∈ M (V ). 3

The results in this section also hold for oriented matroids, but this gives no new information: by a recent result of Ardila, Rincón, and Williams [ARW], all oriented matroids which are totally nonnegative (called positively oriented matroids) come from totally nonnegative subspaces.

Results generalized to oriented matroids

In this section we generalize the results of Section 2 to oriented matroids. A comprehensive account of the theory of oriented matroids, and our reference throughout, is [BLVS + 99]. We begin by describing oriented matroids coming from subspaces of R n (called realizable oriented matroids), which can serve as a reference point for our results. For α ∈ R we let sign(α) ∈ {0, +, -} be the sign of α, and for v ∈ R E we define the sign vector sign(v) ∈ {0, +, -} E by sign(v) e := sign(v e ) for e ∈ E. The support of a sign vector X ∈ {0, +, -} E is the subset of E which indexes the nonzero components of X. For example, sign(5, 0, -1, 2) = (+, 0, -, +) has support {1, 3, 4}. Definition 4.1 (realizable oriented matroids; 1.2 of [BLVS + 99]). Let V ∈ Gr k,n . The (realizable) oriented matroid M(V ) is uniquely determined by [n] (the ground set of M(V )) and any one of the following three objects:

• the set V * := {sign(v) : v ∈ V }, called the covectors of M(V ); or • the set C * := {X ∈ V * : X has minimal nonempty support}, called the cocircuits of M(V ); or • the function χ : [n] k → {0, +, -} (up to multiplication by ±1), called the chirotope of M(V ), where χ(I) := sign(∆ I (V )) for I ∈ [n] k . The rank of M(V ) is k.

A general oriented matroid M is determined by its ground set E (where E is a totally ordered finite set), and any one of the three objects V * (M) ⊆ 2 {0,+,-} E (the covectors), C * (M) ⊆ 2 {0,+,-} E (the cocircuits), or χ M : E k → {0, +, -} up to multiplication by ±1 (the chirotope), where k is the rank of M. (Usually one does not require that E is totally ordered, but it will be essential for us here.) The bases of M are those I ∈ E k such that χ M (I) = 0, so χ M assigns an orientation (either + or -) to every basis of M. The objects V * (M), C * (M), and χ M are characterized by certain axioms, and each can be determined from any other; see chapter 3 of [BLVS + 99].

We can now begin translating the results of Section 2 to the more general framework of oriented matroids. We say that an oriented matroid of rank k is uniform if every k-subset of its ground set is a basis, so that V ∈ Gr k,n is generic iff M(V ) is uniform.

Theorem 4.2. Suppose that M is an oriented matroid of rank k with ground set [n], and l ≥ k. (i) If the covectors of M change sign fewer than l times, then (χ M (J ∪ {i})) i / ∈J changes sign fewer than l -k + 1 times for all J ∈ [n] k-1 . (ii) If M is uniform and (χ M (J ∪ {i})) i / ∈J changes sign fewer than l -k + 1 times for all J ∈ [n] k , then the covectors of M change sign fewer than l times.

We now describe a partial order on oriented matroids with a fixed ground set, coming from what are called weak maps in the literature. We use the partial order on sign vectors given by X ≤ Y iff X e = Y e for all e ∈ E such that X e = 0 (for X, Y ∈ {0, +, -} E ). This also defines a partial order on chirotopes, regarded as sign vectors in {0, +, -} ( E k ) .

Definition 4.3 (partial order on oriented matroids; 7.7.5 of [BLVS + 99]). Let M and N be oriented matroids with ground set E. We say that M ≤ N if for every covector X of M, there exists a covector Y of N with X ≤ Y . Then ≤ is a partial order on oriented matroids with ground set E. If M and N have the same rank, then M ≤ N iff χ M ≤ ±χ N .

Note that for V, V ∈ Gr k,n , we have M(V ) ≤ M(V ) iff V is a perturbation of V . We now generalize i → j-perturbation of subspaces to oriented matroids. Let M be an oriented matroid with ground set E. A single element extension of M at a is an oriented matroid M with ground set E {a} and the same rank as M, such that the covectors of M are precisely the restriction of covectors of M to E. Las Vergnas [LV78] studied single element extensions; we refer to his results as given in [BLVS + 99]. For a sign vector X ∈ {0, +, -} E and y ∈ {0, +, -}, we let (X, y) a ∈ {0, +, -} E {a} Finally, we explain how to obtain the generalization of Theorem 1.1 to oriented matroids, as a consequence of these results for l = k. Let M be an oriented matroid of rank k with ground set [n]. We say that M is positively oriented if every basis of M has the same orientation. If M is positively oriented, we let N be the uniform positively oriented matroid of rank k with ground set [n]; then N ≥ M, so the covectors of M change sign fewer than k times by Theorem 4.6. Conversely, if the covectors of M change sign fewer than k times, then by Theorem 4.2(i) any two bases of M with k -1 elements in common have the same orientation; it follows from the basis exchange property for (oriented) matroids that all bases of M have the same orientation. Hence we have the following corollary.

Corollary 4.7. An oriented matroid of rank k is positively oriented iff its covectors change sign fewer than k times.

We remark that since all positively oriented matroids are realizable [ARW], the forward direction follows from [ARW] and Theorem 1.1.

Fig. 1 :

 1 Fig. 1: A homeomorphism from R 4 >0 to the cell of Gr ≥0 2,4 labeled by the positroid M = [4] 2 .

I am partially supported by an NSERC postgraduate scholarship and a Chateaubriand fellowship. 1365-8050

We begin by examining the Schubert cell of V , which is labeled by I 1 , the lexicographic minimum of M (V ). We use the Gale partial order ≤ Gale , which is the partial order of [n] k given by

Proposition 3.1. Suppose that V ∈ Gr ≥0 k,n and I ∈ [n] k is the lexicographic minimum of M (V ). (i) For all J ∈ M (V ), there exists a vector in V which alternates on J. (ii) If some vector in V alternates on J ∈ [n] k , then I ≤ Gale J. Thus I is the Gale-minimal element of [n] k on which some vector in V alternates.

Example 3.2. Let V ∈ Gr ≥0 2,4 be the row span of the matrix 1 2 0 -1 0 0 1 0 . Then no vector in V alternates on {1, 2}, and (1, 2, -1, -1) ∈ V alternates on {1, 3}, so {1, 3} is the lexicographic minimum of M (V ). Note that the vector (1, 2, 0, -1) ∈ V alternates on {1, 4} / ∈ M (V ), so the converse to part (i) above does not necessarily hold.

3

, where V | J denotes the restriction of V to the coordinates in J), but not part (ii), as the next example shows.

Example 3.3. Let V ∈ Gr 3,6 be the row span of the matrix

Then the vector

(1, -1, -2, -3, 1, 0) ∈ V alternates on {1, 2, 5}, and (3, 2, -1, 1, 3, 0) ∈ V alternates on {1, 3, 4}, but no vector in V alternates on {1, 2, 3} or {1, 2, 4}. Hence {J ∈ [6] 3 : some vector in V alternates on J} has no Gale minimum.

3

We can generalize Proposition 3.1 to the entire Grassmann necklace, as follows. Let V ∈ Gr k,n and

k n be the Grassmann necklace of V . For j ∈ [n], we define the j-cyclic shift V j of V as follows: take a k × n matrix [x (1) | • • • |x (n) ] whose rows span V , and let V j be the row span of

Note that V j does not depend on our choice of matrix, and if V is totally nonnegative then so is V j (which explains why we have the signs (-1) k-1 ). Then I j is the lexicographically minimal index of a nonzero Plücker coordinate of V j (given our labeling of the columns), and v ∈ V j alternates on J ∈ [n] k (with respect to the total order ≤ j ) iff v ∈ V alternates on J except precisely from component max(J ∩ [1, j)) to component min(J ∩ [j, n]) (if both components exist). For example, if J = {1, 3, 4} and j = 3, then v = (1, 1, 1, -1) satisfies this condition, but not v = (1, 1, -1, 1). Applying Proposition 3.1 to V j gives the following corollary, where ≤ j-Gale is the Gale order on [n] k induced by the total order

, and j ∈ [n]. (i) For all J ∈ M (V ), there exists a vector in V which alternates on J except precisely from component max

Thus I j is the j-Gale-minimal element of [n] k on which some vector in V alternates except precisely from component max(J ∩ [1, j)) to component min(J ∩ [j, n]) (if both components exist).

denote the sign vector whose restriction to E is X and whose ath component is y. By 7.1.4 of [BLVS + 99], there exists a unique function σ : C * (M) → {0, +, -} such that (C, σ(C)) a is a cocircuit of M for all cocircuits C of M. In this case, we say that M is the single element extension of M at a by σ. (In general, not all functions σ : C * (M) → {0, +, -} give rise to single element extensions.) Definition 4.4 (i → j-perturbation). Let i, j ∈ [n] be distinct and ∈ {+, -}. Given an oriented matroid M with ground set [n], we define the i → j-perturbation of M as the oriented matroid N with rank k and ground set [n] as follows. If j is in every basis of M, then we define N := M. Otherwise, we write M as the single element extension of M (with ground set [n] \ {j}) at j by σ : C * (M ) → {0, +, -}, and let N be the single element extension of M at j by σ • τ , where τ : We have the same desirable properties of i → j-perturbation of oriented matroids as for subspaces.

Lemma 4.5. Suppose that M is an oriented matroid of rank k with ground set [n]. (i) If the covectors of M change sign fewer than l times, then so do the covectors of the (i + 1)

in order from left to right n-k times to M gives a uniform oriented matroid. (Here an i → j-perturbation denotes either of the i → j-perturbations for ∈ {+, -}; the sign of is not important.) Similarly, applying the sequence of perturbations

in order from left to right n -k times to M gives a uniform oriented matroid. (iii) If V is an i → j-perturbation of V ∈ Gr k,n , then M(V ) is the i → j-perturbation of M(V ).

Theorem 4.6. Suppose that M is an oriented matroid of rank k with ground set [n]. The covectors of M change sign fewer than l times iff there exists a uniform M ≥ M of rank k with ground set [n] such that (χ M (J ∪ {i})) i / ∈J changes sign fewer than l -k + 1 times for all J ∈ [n] k-1 . Explicitly, let N be obtained from M by applying the sequence of perturbations

in order from left to right n -k times, or by applying the sequence of perturbations

in order from left to right n -k times, so that N ≥ M is uniform. Then the following are equivalent: (i) the covectors of M change sign fewer than l times; (ii) the covectors of N change sign fewer than l times; and (iii) (χ N (J ∪ {i})) i / ∈J changes sign fewer than l -k + 1 times for all J ∈ [n] k-1 .


Seung Jin Lee

Pieri rule for the affine flag variety

Keywords: affine flag variety, k-Schur function, nilCoxeter algebra, Pieri rule, strong Schur function

We prove the affine Pieri rule for the cohomology of the affine flag variety conjectured by Lam, Lapointe, Morse and Shimozono. We study the cap operator on the affine nilHecke ring that is motivated by Kostant and Kumar's work on the equivariant cohomology of the affine flag variety. We show that the cap operators for Pieri elements are the same as Pieri operators defined by Berg, Saliola and Serrano. This establishes the affine Pieri rule.

Résumé. Nous prouvons la règle affine Pieri pour la cohomologie de la variété affine de drapeau conjecturé par Lam, Lapointe, Morse et Shimozono. Nous étudions l'opérateur de bouchon sur l'affine nilHecke anneau qui est motivé par le travail de Kostant et Kumar sur la cohomologie équivariante de la variété affine de drapeau. Nous montrons que les opérateurs de capitalisation pour les éléments Pieri sont les mêmes que les opérateurs Pieri définies par Berg, Saliola et Serrano. Ceci établit la règle affine Pieri.

Introduction

Affine Schubert calculus is a subject that ties combinatorics, algebraic geometry and representation theory together. Its modern development is motivated by the relation between k-Schur functions and the (co)homology of the affine Grassmannian of SL(n). k-Schur functions were introduced by Lapointe, Lascoux, Morse in [START_REF] Lapointe | Tableau atoms and a new Macdonald positivity conjecture[END_REF] in the study of Macdonald polynomial positivity, a mostly combinatorial branch of symmetric function theory.

Peterson [START_REF] Peterson | Lecture notes at MIT[END_REF] identified the equivariant homology of the affine Grassmannian with a subalgebra of the affine nilHecke algebra A, now called the Peterson algebra. Lam proved that k-Schur functions can be identified with the Schubert classes of the homology of the affine Grassmannian of SL(n) in [START_REF] Lam | Schubert polynomials for the affine Grassmannian[END_REF] . The nilHecke ring acts as divided difference operators on the equivariant cohomology of Kac-Moody partial flag varieties. By using the correspondence, one can investigate problems about the (co)homology of the affine Grassmannian of SL(n) by translating them into the theory of k-Schur functions and understanding the combinatorics of k-Schur functions. There are affine analogues of the classical theory of Pieri rules, tableaux, and Stanley symmetric functions. See [START_REF] Lam | Affine Stanley symmetric functions[END_REF][START_REF] Morse | Tableaux on k + 1-cores, reduced words for affine permutations, and k-schur expansions[END_REF][START_REF] Morse | A k-tableau characterization of k-Schur functions[END_REF].

Lam, Lapointe, Morse and Shimozono introduced the strong Schur functions, indexed by elements in the affine symmetric group W af in [START_REF] Lam | Affine insertion and Pieri rules for the affine Grassmannian[END_REF]. These strong Schur functions generalize the k-Schur functions combinatorially. They conjectured a series of properties of strong Schur functions such as the symmetry of the strong Schur functions. Berg, Saliola and Serrano studied the Pieri operators acting on the affine nilCoxeter ring A 0 in [START_REF] Berg | The down operator and expansions of near rectangular k-Schur functions[END_REF][START_REF] Berg | Pieri operators on the affine nilCoxeter algebra[END_REF] to establish some of conjectures in [START_REF] Lam | Affine insertion and Pieri rules for the affine Grassmannian[END_REF].

In this extended abstract, we describe ideas for proving the affine Pieri rule for the cohomology of the affine flag variety conjectured in [START_REF] Lam | Affine insertion and Pieri rules for the affine Grassmannian[END_REF]. We introduce the cap operators acting on the affine nilCoxeter ring A 0 by investigating the work in [START_REF] Kostant | The nil Hecke ring and cohomology of G/P for a Kac-Moody group G[END_REF] and show that the cap operators for Pieri elements are the same as the Pieri operators defined in [START_REF] Berg | Pieri operators on the affine nilCoxeter algebra[END_REF] by using the strong strips. The affine Pieri rule gives us geometric interpretation of the skew strong Schur functions as an affine Grassmannian part of the cap product of the Schubert classes in (co)homology of the affine flag variety. We now describe these two operators.

Cap operators

Let us consider the affine type A root datum and corresponding Kac-Moody flag variety F l (See [START_REF] Kostant | The nil Hecke ring and cohomology of G/P for a Kac-Moody group G[END_REF] for details). Let {ξ w |w ∈ W af } denote the Schubert basis for the equivariant cohomology H * T ( F l) of F l. One of main problems in affine Schubert calculus is to find a combinatorial formula for the structure constants p w u,v where ξ u ξ v = w p w u,v ξ w . In [START_REF] Kostant | The nil Hecke ring and cohomology of G/P for a Kac-Moody group G[END_REF], Kumar and Kostant identified the torus-equivariant cohomology H * T ( F l) of the affine flag variety and the dual of the nilHecke ring. Using this connection, one can compute the structure constants p w u,v by calculating the coproduct structure constants of A. More precisely, we have

∆(A w ) = u,v∈Waf p w u,v A u ⊗ A v .
For u ∈ W af , a cap operator D u on A 0 is defined by

D u (A w ) = v∈Waf (v)= (w)-(u) p w u,v A v .
Geometrically, the cap operator is the cap product on the ordinary homology and cohomology of the affine flag variety. More precisely, the cap operator D u can be considered as an element in H * ( F l) and A w can be considered in H * ( F l) so that the cap product

H * ( F l) × H * ( F l) → H * ( F l) can be described by (D u , A w ) = D u (A w ).
Note that the cap operator only keep track of ordinary cohomology since p w u,v is constant when (v) = (w) -(u). Let ρ i be the Pieri element s i-1 . . . s 1 s 0 in W af where indices are taken modulo n. We study the cap operators D ρi for ρ i and show that D ρi satisfy the properties of the Pieri operators D i that Berg, Saliola and Serrano proved in [START_REF] Berg | Pieri operators on the affine nilCoxeter algebra[END_REF]. This establishes the following main theorems equivalent to the affine Pieri rule conjectured in [START_REF] Lam | Affine insertion and Pieri rules for the affine Grassmannian[END_REF].

Theorem 1.1 For w, u ∈ W af with i = (w) -(u) ∈ N, p w ρi,u counts the number of strong strips from w to u.

Theorem 1.2 Let w ∈ W af and 1 ≤ m. Then in H * ( F l) we have

ξ ρm ξ w = S ξ outside(S) ,
where the sum runs over strong strips S of size m such that inside(S) = w.

Note that Theorem 1.1 and 1.2 are equivalent. As a corollary, one can compute

p w v,u for v = ρ -1 m or v = s i+m-1 s i+m-2 • • • s i+1 s i
for any i by applying automorphisms on Dynkin diagram of affine type A, namely, the map j → -j and j → j + i for j ∈ Z/nZ.

The paper is structured as follows. In section 2, we recall some notions about the affine symmetric group, k-Schur functions, strong Schur functions and root systems. In section 3, we define the affine nilHecke ring A and study its properties. In section 4, we recall some statements concerning the affine flag variety and its equivariant cohomology as well as the relationship between the equivariant cohomology of affine flag variety and the coproduct structure of the affine nilHecke ring. In section 5, we define the cap operator. We show that these cap operators for Pieri elements agree with the Pieri operators defined by Berg, Saliola and Serrano. We also prove the affine Pieri rule for the ordinary cohomology of the affine flag variety. In section 6, we apply the affine Pieri rule to show that the structure constants p w u,v for the cohomology of the affine flag variety can be described in terms of strong Schur functions when u is 0-Grassmannian. This also gives a geometric interpretation of the skew strong Schur functions.

Preliminaries

Affine symmetric group

Positive integers n ≥ 2 and k = n -1 will be fixed throughout the extended abstract. Let W af denote the affine symmetric group with simple generators s 0 , s 1 , . . . , s n-1 satisfying the relations

s 2 i = 1 s i s i+1 s i = s i+1 s i s i+1 s i s j = s j s i if i -j = 1, -1.
where indices are taken modulo n. An element of the affine symmetric group may be written as a word in the generators s i . A reduced word of the element is a word of minimal length. The length of w, denoted (w), is the number of generators in any reduced word of w.

The Bruhat order, also called strong order, on affine symmetric group elements is a partial order where u < w if there is a reduced word for u that is a subword of a reduced word for w. If u < w and (u) = (w) -1, we write u w. It is well-known that u w if and only if there exists a reflection t ∈ {ws i w -1 |w ∈ W af , 0 ≤ i < n} such that w = ut and (u) = (w) -1. For type A, the set {ws i w -1 |w ∈ W af } consists of transpositions t ij . See [BB] for instance. The subgroup of W af generated by {s 1 , • • • , s n-1 } is naturally isomorphic to the symmetric group W . The 0-Grassmannian elements are minimal length coset representatives of W af /W .

Symmetric functions

Let Λ denote the ring of symmetric functions. For a partition λ, we let m λ , h λ , e λ , s λ denote the monomial, homogeneous, elementary and Schur symmetric functions, respectively, indexed by λ. Each of these families forms a basis of Λ. Let Λ (k) denote the subalgebra generated by h 1 , h 2 , . . . , h k . The elements h λ with λ 1 ≤ k form a basis of Λ (k) . Let Λ (k) = Λ/I k denote the quotient of Λ by the ideal I k generated by m λ with λ 1 > k. The image of elements m λ with λ 1 ≤ k form a basis of Λ (k) . Lam [Lam08, Theorem 7.1] showed that Λ (k) (resp. Λ (k) ) are isomorphic to homology(resp. cohomology) of affine Grassmannian as Hopf-algebras.

k-Schur and Strong Schur functions

There are many conjecturally equivalent definitions of k-Schur functions in [LLM + 14]. We follow the definition of k-Schur functions in [LLMS10] using strong strips. Note that the marking of strong covers and strong strips defined in this extended abstract follows the notation of [START_REF] Berg | The down operator and expansions of near rectangular k-Schur functions[END_REF]. This differs from the definition of strong covers and strips in [LLMS10] by reversing direction.

A marked strong cover C = u a -→ v consists of u, v ∈ W af and an integer a such that u = vt ij , v u, a = u(j) = v(i) where i ≤ 0 < j. We use the notation inside(C) = u and outside(C) = v. A strong strip S of length i from u to v, denoted by u -→ (i) v, is a path u a1 -→ u 1 a2 -→ • • • ai -→ u i = v
where a 1 > a 2 > . . . > a i . We let inside(S) = u, outside(S) = v, and size(S) = i. A strong tableau is a sequence T = (S 1 , S 2 , . . .) of strong strips S i such that outside(S j ) = inside(S j+1 ) for all j ∈ Z >0 and size(S i ) = 0 for all sufficiently large i. We define inside(T ) = inside(S 1 ) and outside(T ) = outside(S i ) for i large. The weight wt(T ) of T is the sequence wt(T ) = (size(S 1 ), size(S 2 ), . . .).

We say that T has shape u/v where u = inside(T ) and v = outside(T ) so that we have u > v.

Definition 2.1 For fixed u, v ∈ W af , define the Strong Schur function

Strong u/v (x) = T x wt(T )
where T runs over the strong tableaux of shape u/v.

If u is 0-Grassmannian and v is the identity element, Strong u (x) is a k-Schur function s (k) c(u)
where c is a bijection between the set of 0-Grassmannian elements and the set of k-bounded partitions. For details, see [START_REF] Lam | Affine insertion and Pieri rules for the affine Grassmannian[END_REF] for instance.

Root systems

We shall assume basic familiarity with Weyl groups, root systems, and weights. See [START_REF] Humphreys | Reflection groups and Coxeter groups[END_REF] for details. Let A = (a ij ) i,j∈Iaf denote an affine Cartan matrix, where I af = I ∪ {0}, so that (a ij ) i,j∈I is corresponding finite Cartan matrix. For type A n-1 (corresponding to W af ), we have I af = Z/nZ and

a ij =    2 if i = j -1 if |i -j| = 1 0 otherwise.
Let R be the root system for W . Let R + , R -denote the set of positive roots, negative roots respectively. Let {α i | i ∈ I} denote the simple roots and {α ∨ i | i ∈ I} denote the simple coroots. Let θ denote the highest root α 1 + α 2 + . . . + α n-1 of R + . Let R af and R + af denote the affine root system and positive affine roots. The positive simple affine roots (resp. coroots) are

{α i | i ∈ I af } (resp. {α ∨ i | i ∈ I af }). The null root δ is given by δ = α 0 + θ = α 0 + • • • + α n-1 . Similarily, the canonical central element c is given by α ∨ 0 + • • • + α ∨ n-1 . A root α is real if it is in W af -
∈ Z. The root α + kδ is positive if k > 0, or if k = 0 and α ∈ R + . Let R + re denote the set of positive roots in R af . Let Q = ⊕ i∈I Z • α i denote the root lattice and let Q ∨ = ⊕ i∈I Z • α ∨
i denote the coroot lattice. Let P and P ∨ be the weight lattice and coweight lattice respectively. We have inclusions Q ⊂ P, Q ∨ ⊂ P ∨ and a map Q af = ⊕ i∈Iaf Z • α i → P given by sending δ to 0. Let •, • denote the pairing between P and P ∨ satisfying α ∨ i , α j = a ij .

For a real root α, we let s α denote the corresponding reflection, defined by s α = ws i w -1 if α = w • α i . The reflection s α acts on weights by s α λ = λ -α, λ α. For a strong cover v w, let α v,w denote the unique positive root satisfying the equation v -1 w = s av,w .

3 NilHecke algebra

Definition

Let S = Sym(P ) be the polynomial ring having a variable for each free generator of P and let F = Frac(S) be the fraction field. Define the F -vector space F Waf = w∈Waf F w with basis W af , with product given by (pv)(qw) = (p(v • q)) (vw) for p, q ∈ F and v, w ∈ W af .

For any real root α ∈ R re define the element A α ∈ F Waf by

A α = α -1 (1 -s α ).

We write

A i = A αi for i ∈ I.

For α = w • α i ∈ R + re , we have wA i w -1 = A α s α A α = A α A α s α = -A α A 2 α = 0.
The A i satisfy the braid relations as the s i in W af , i.e., A i A i+1 A i = A i+1 A i A i+1 . Therefore it makes sense to define

A w = A i1 • • • A i l where w = s i1 • • • s i l is a reduced decomposition.

One can check that

A v A w = A vw if (vw) = (v) + (w) 0 otherwise.
The nilCoxeter algebra A 0 is the subring of F Waf generated by A i over Z for i ∈ I af . The set {A w |w ∈ W af } forms a basis of A 0 over Z. The nilHecke algebra A is the subring of F Waf generated by S and A 0 .

Remark 3.1 The affine nilHecke algebra A defined above is slightly different from those defined in [START_REF] Kostant | The nil Hecke ring and cohomology of G/P for a Kac-Moody group G[END_REF]. Kostant and Kumar set S = Sym(P af ) instead of Sym(P ) where P af denote the affine weight lattice. We have a projection P af → P and the map induces Sym(P af ) → Sym(P ) which is compatible with Theorem 4.1. The image of the null root δ = α 0 + θ in P is 0. Geometric interpretation of P and P af will be discussed in section 4.

Cyclically decreasing elements and Peterson algebra

A word s i1 s i2 • • • s i l with indices in Z/nZ is called cyclically decreasing if each letter occurs at most once and whenever s i and s i+1 both occurs in the word, s i+1 precedes s i . For J Z/nZ there is the unique cyclically decreasing element w J with letters {s j |j ∈ J}. For i ∈ {0, 1, . . . , n -1}, let

h i = J⊂Iaf |J|=i A w J ∈ A 0
where h 0 = 1 and h i = 0 for i < 0 by convention. In [START_REF] Lam | Affine Stanley symmetric functions[END_REF], Lam showed that the elements {h i } i<n commute and freely generate a subalgebra B of A 0 called affine Fomin-Stanley algebra. It is well-known that B is isomorphic to Λ (k) via the map sending h i to h i . Therefore, the set {h λ = h λ1 . . . h λ l |λ 1 ≤ k} forms a basis of B.

Coproduct structure of A

There is a coproduct structure on the nilHecke ring A. Kumar and Kostant showed that the structure constants of the coproduct in A are the same as the structure constants of the equivariant cohomology ring of F l. Details and proofs can be found in [KK86, LLM + 14, Pet97]. Let ∆ : F Waf → F Waf ⊗ F F Waf be the left F -linear map defined by

∆(w) = w ⊗ w for all w ∈ W af Theorem 3.2 The map ∆ : F W af → F W af ⊗ F F W af induces the unique left S-module homomorphism ∆ : A → A ⊗ S A such that ∆(A i ) = A i ⊗ 1 + s i ⊗ A i = 1 ⊗ A i + A i ⊗ s i for all i ∈ I ∆(ab) = ∆(a)∆(b)
for all a, b ∈ A.

For w, u 1 , u 2 ∈ W af , the equivariant Schubert structure constants p w u1,u2 ∈ S are defined as the coefficients in the expansion ∆(A w ) = p w u1,u2 A u1 ⊗ A u2 . The followings are properties of p w u1,u2 .

Theorem 3.3

1. p w u1,u2 = 0 unless w ≥ u 1 and w ≥ u 2 .

2. p w u1,u2 is homogeneous of degree (u 1 ) + (u 2 ) -(w).

3. [Gra01, Kum02] (-1) (u1)+ (u2)-(w) p w u1,u2 ∈ Z ≥0 [α i |i ∈ I af ].
The last property in Theorem 3.3 is called Graham positivity. One can use Theorem 3.2 to compute p w u1,u2

explicitly.

Theorem 3.4 [KK86] Let w = s i1 s i2 . . . s i l and l = (w). Then

p w u1,u2 = As i j 1 As i j 2 ...As i j k =Au 1 j1<j2<...<j k l p=1 f j1,j2,...,j k (A si p ) Au 2
where f j1,j2,...,j k (A si p ) = s ip if p ∈ {j 1 , j 2 , . . . , j k } and = A si p otherwise, and c w A w | Au = c u .

Affine flag varieties

In this section, we define the Kac-Moody flag variety F l and establish the relationship between the equivariant cohomology of F l and the coproduct structure on A. There are two definitions of Kac-Moody flag variety F l in [LLM + 14], but we only recall F l as the Kac-Moody flag ind-variety in [START_REF] Kostant | The nil Hecke ring and cohomology of G/P for a Kac-Moody group G[END_REF][START_REF] Kumar | Kac-Moody groups, their flag varieties and representation theory[END_REF]. Let G af denote the Kac-Moody group of affine type associated with SL(n) and let B af denote its Borel subgroup. The Kac-Moody flag ind-variety

F l = G af /B af is paved by cells B af ẇB af /B af ∼ = C (w) whose closure X w is called the Schubert variety. Schubert variety defines a Schubert class [X w ] Taf ∈ H * Taf ( F l)
where T af is the maximal torus in B af . For our setting, we consider H * T ( F l) where T is a maximal torus in SL(n). Kumar and Kostant [START_REF] Kostant | The nil Hecke ring and cohomology of G/P for a Kac-Moody group G[END_REF] identified the equivariant cohomology ring of F l with the dual of nilHecke ring A. By restricting the group action from T af to T , this identification shows that the structure constant of H * T ( F l) is the same as p w u,v defined in Section 3.3.

Theorem 4.1 [KK86] The T -equivariant cohomology of F l has a basis {[X w ] T ∈ H * T ( F l)} over S ∼ = H * T (pt).
Moreover, the structure constants of H * T ( F l) are p w u1,u2 , i.e.,

[X u1 ] T [X u2 ] T = p w u1,u2 [X w ] T .
Remark 4.2 The ordinary cohomology of F l has a basis {[X w ] ∈ H * ( F l)} over Z and corresponding structure constants are just φ(p w u1,u2 ) where φ : S → Z is the evaluation at 0.

Pieri operators and Affine Pieri rule for type A

Let φ : S → Z denote the map sending a polynomial to its constant term, called the evaluation map at 0. It extends to the map φ : A → A 0 given by φ( w a w A w ) = φ(a w )A w . Pieri elements ρ i are defined by s i-1 s i-2 . . . s 1 s 0 for i > 0. For w ∈ W af , let us define the cap operator D w on A (and A 0 ) by

D w (A v ) := φ u∈Waf p v w,u A u = u∈Waf (u)= (v)-(w) p v w,u A u .
If w = ρ i , we call D ρi the Pieri operator and denote by D i . Note that p v w,u ∈ Z ≥0 when (v) = (w) + (u) by Theorem 3.3. Finding a combinatorial formula for such p v w,u is one of the important problems in Schubert calculus and it is not completely known even for finite flag varieties. In this section, we will describe main ideas showing that D i is the same as the Pieri operator D i defined by Berg, Saliola, Serrano in [START_REF] Berg | Pieri operators on the affine nilCoxeter algebra[END_REF]. This identification gives a combinatorial description of the Pieri rule for the ordinary cohomology of F l and therefore proves Theorem 1.1. Let us state properties of D i described in [START_REF] Berg | Pieri operators on the affine nilCoxeter algebra[END_REF].

Theorem 5.1 [BSS14, Theorem 4.8] Suppose w ∈ W af and v ∈ W . Then

D i (A w A v ) = D i (A w )A v .
Lemma 5.2 [BSS14, Lemma 4.5] For r < n and i ≥ 1,

D i (h r ) = h r-i .
Theorem 5.3 [BSS14, Proposition 4.3] For p < n,w ∈ W af and i ≥ 1, we have

D i (h p A w ) = i j=0 D j (h p )D i-j (A w ) = i j=0 h p-j D i-j (A w ).
For w ∈ W af , there is a unique decompostion w = w λ w(0) where w λ is 0-Grassmannian and w(0) ∈ W . Note that λ = c(w λ ) where c is the bijection between 0-Grassmannian elements and k-bounded partitions mentioned in section 2. In this setup, the set {h λ A w(0) : w = w λ w(0) ∈ W af } forms a basis of A (See [START_REF] Berg | Pieri operators on the affine nilCoxeter algebra[END_REF]). This follows from the fact that h λ has the unique 0-Grassmannian term A w λ . Therefore, above theorems uniquely determine D i . It turns out that the same theorems hold for D i . This implies that D i = D i and Theorem 1.1 follows.

for w, u ∈ W af where the summation is over all k-bounded partitions and •, • A0 is the inner product on A 0 satisfying A w1 , A w2 A0 = δ w1,w2 . If w ∈ W 0 and v is the identity element, Weak w/u (x) is the affine Stanley symmetric function Fw . Let Gr denote the affine Grassmannian associated with SL(n, C). Since Gr ∼ = G af /P for the affine Kac-Moody group G af and its maximal parabolic subgroup P, we have the Schubert bases

{ζ w ∈ H * (Gr, Z) | w ∈ W 0 } {ζ w ∈ H * (Gr, Z) | w ∈ W 0 }.
In [START_REF] Lam | Schubert polynomials for the affine Grassmannian[END_REF], Lam showed that ζ w and ζ w can be represented by k-Schur functions Strong w (x) and affine Stanley symmetric functions Weak w (x) via the isomorphisms H * (Gr) ∼ = Λ (n) and H * (Gr) ∼ = Λ (n) . In fact, affine insertion described in [START_REF] Lam | Affine insertion and Pieri rules for the affine Grassmannian[END_REF] offers a duality between weak and strong orders combinatorially. Define the affine Cauchy kernel Ω n (x, y) by

Ω n (x, y) = i 1 + y i h 1 (x) + y 2 i h 2 (x) + • • • + y n-1 i h n-1 (x) = λ:λ1<n h λ (x)m λ (y) = λ m λ (x) hλ (y). as an element in Λ (n) (x) ⊗Λ (n) (y) ⊂ Λ(x) ⊗Λ (n) (y)
where hλ (y) is the image of h λ (y) in Λ (n) . By the definition of Ω n and Theorem 1.2, we have

Strong w/u (x) = Ω n • ξ u , ξ w F l (1)
where Ω n • ξ u ∈ Λ ⊗H * (Gr) and •, •, F l is the inner product on H * ( F l) satisfying ξ u , ξ w F l = δ u,w . The duality between strong and weak orders produces the following affine Cauchy identity [LLMS10, Corollary 4.6]. Theorem 6.2 (Affine Cauchy Identity) The following identity holds in the formal power series ring: Therefore, Strong w/u (x) captures the 0-Grassmannian part of D u (ξ w ). Note that when w is not 0-Grassmannian, we have Strong w (x) = 0 (See [START_REF] Lam | Affine insertion and Pieri rules for the affine Grassmannian[END_REF]).

Ω n (x, y) =
Note that Lam, Lapointe, Morse and Shimozono defined the marked strong cover wt ij → w where i ≤ l < j for a fixed constant l instead of i ≤ 0 < j in our setup. The affine Pieri rule conjectured in [START_REF] Lam | Affine insertion and Pieri rules for the affine Grassmannian[END_REF] is the following. where the sum runs over strong strips S of size m with respect to l such that inside(S) = w.

We can obtain Theorem 6.4 by applying ψ l to Theorem 1.2. Recall that ω is the automorphism of W af sending s i to s n-i . By applying ω to Theorem 1.2, we get the dual affine Pieri rule. Theorem 6.5 Let w ∈ W af and 1 ≤ m. Then in H * ( F l) we have ξ ω(ρm) ξ w = S ξ ω(outside(S)) , where the sum runs over strong strips S of size m such that inside(S) = ω(w).

Since the image of ξ ω(ρm) under the projection H * ( F l) → H * (Gr) ∼ = Λ (n) is Weak ω(ρm) = ẽm , the image of e m ∈ Λ (n) , so we recover the dual Pieri rule for the affine Grassmannian in [START_REF] Lam | Affine insertion and Pieri rules for the affine Grassmannian[END_REF].

  orbit of the simple affine roots, and imaginary otherwise. The imaginary roots are exactly {kδ | k ∈ Z\{0}}. Every real affine root is of the form α + kδ, where α ∈ R and k

w∈W 0

 0 Strong w (x)Weak w (y) in Z[[x 1 , x 2 , . . . , y 1 , y 2 , . . .]] Theorem 6.1 can be obtained by combining Theorem 6.2 and Equation (1) with slight modification. Remark 6.3 The skew strong Schur function Strong w/u (x) can be geometrically interpreted as the image of D u (ξ w ) under the projection H * ( F l) → H * (Gr) where D u is the cap product acting on H * ( F l). Indeed, by the definition of D u and Remark 4.2 we have D u (ξ w ) = v p w uv ξ v . Since the projection H * ( F l) → H * (Gr) maps ξ w to Strong w (x), it sends D u (ξ w ) to Strong w/u (x) by Theorem 6.1(3).

  Theorem 6.4 [LLMS10, Conjecture 4.15] Let w ∈ W af and 1 ≤ m. Then in H * ( F l) we have ξ ψ -l (ρm) ξ w = S ξ outside(S) ,

Acknowledgements

I would like to thank Thomas Lam for helpful discussions.

Theorem 5.4 Suppose w ∈ W af and v ∈ W . Then

Theorem 5.6 For r < n and all i ≥ 1,

In order to prove analogue of Theorem 5.3 for D i , we need the following lemmas.

Lemma 5.7 [Lam08, Lemma 7.2] Let b ∈ B and s ∈ S. Then

Lemma 5.8 Let ψ : W af → W af be the group automorphism defined by s i → s i-1 . The automorphism induces the ring automorphism ψ :

Theorem 5.9 For p < n,w ∈ W af and i ≥ 1, we have

Theorems 5.4, 5.6 and 5.9 imply that D i = D i , hence Theorem 1.1.

Applications

Let W 0 denote the set of 0-Grassmannian elements in W af . In this section, we describe how Theorem 1.1 implies the following conjecture, as stated in [START_REF] Lam | Affine insertion and Pieri rules for the affine Grassmannian[END_REF].

Theorem 6.1 [LLMS10, Conjecture 4.18] Let w, u ∈ W af be two affine permutations. Then

Note that (1), (2) of Theorem 6.1 and (3) when w, v are in W 0 are proved in [START_REF] Berg | Pieri operators on the affine nilCoxeter algebra[END_REF]. To be more precise, they showed that for w, v, u ∈ W 0 , p w u,v is the coefficient of Fw in Fu Fv , where Fw is the affine Stanley symmetric function labeled by w. Lam, Lapointe, Morse and Shimozono introduced weak Schur functions in [START_REF] Lam | Affine insertion and Pieri rules for the affine Grassmannian[END_REF] defined by Weak w/u (x) = λ h λ A u , A w A0 m λ (x)


C Y Amy Pang

Card-Shuffling via Convolutions of Projections on Combinatorial Hopf Algebras

Keywords: shuffling, combinatorial Hopf algebras, Markov chains, noncommutative symmetric functions, hyperplane walks, dual graded graphs

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

Background: Markov chains from Hopf-powers

Possibly the most popular model of card-shuffling is the Gilbert-Shannon-Reeds (GSR) riffle-shuffle: cut the deck into two piles according to the (symmetric) binomial distribution, then drop one-by-one the bottom card from either pile, chosen with probability proportional to the current pile size. This second step is equivalent to all interleavings of the two piles (counted with multiplicity) being equally likely.

Amongst the plethora of results concerning this shuffle, the most notable must be the work of [START_REF] Bayer | Trailing the dovetail shuffle to its lair[END_REF], who determined that 3 2 log n shuffles are necessary and sufficient to randomise a deck of n cards. Central to their argument is the generalisation of the GSR model to a-handed shuffles: cut the deck into a piles according to a (symmetric) multinomial distribution, then drop the bottom cards from a pile chosen with probability proportional to pile size as before. Performing the GSR shuffle t times is then the same as a 2 t -handed shuffle, so analysing long-term behaviour of 2-handed riffle-shuffles is equivalent to letting the number of hands tend to infinity. [START_REF] Diaconis | Hopf algebras and Markov chains: two examples and a theory[END_REF] observed that the transition probabilities of the riffle-shuffle are, up to scaling, the coefficients of the coproduct-then-product map m∆ on the shuffle algebra. Furthermore, the coefficients of the ath Hopf-power map m [a] ∆ [a] on the shuffle algebra give the transition probabilities of the a-handed riffle-shuffle. We then defined Markov chains on the bases of other combinatorial Hopf algebras by setting their transition probabilities to be such Hopf-power coefficients, with a little modificiation (via the Doob transform). These Hopf-power Markov chains model the breaking then recombining of the combinatorial objects indexing the bases of the algebras. The thesis of [START_REF] Pang | Hopf algebras and Markov chains[END_REF] greatly extends the Hopf-power Markov chain framework; this encompasses a restriction-then-induction chain on representations of the symmetric groups, and a tree-pruning model -see Examples 3.5 and 5.3 below.

Probabilistic conclusions from Hopf-algebraic techniques

The benefit of this viewpoint is two-fold. Firstly, as recorded by (Pang, 2014, Th. 4.7.1), maps between Hopf algebras which "respect the bases" induce projections of the related chains. [START_REF] Pang | A Hopf-power Markov chain on compositions[END_REF] applied this to a map from the shuffle algebra to the algebra of quasisymmetric functions, to conclude that the positions of descents under riffle-shuffling of a deck of distinct cards is a Markov statistic. (A descent occurs where a card has greater value than the card immediately below it.) This means that the probability of a shuffle producing descents in prescribed positions depends only on the positions of descents before the shuffle, and not on the exact deck order. (This fact also follows from the descent set being a "shufflecompatible statistic", which Gessel (2010) attributes to Stanley.) (Pang, 2014, Sec. 4.7) constructs many Markov statistics for inverse riffle-shuffling out of commutation quotients of the free associative algebra.

The second way in which the Hopf formulation aids in studying these Markov chains is that, in many cases, there are algorithms to compute a basis of eigenvectors for the Hopf-power maps and hence the transition matrices. This gives interesting information about the long term behaviour of the chain. As an example, (Pang, 2014, Prop. 6.1.3 and Prop. 6.1.5) state that, if a deck of n distinct cards was originally in ascending order, then, after t iterations of the a-handed shuffle, the expected number of descents is (1 -a -t ) n-1 2 , and the expected number of peaks is (1 -a -2t ) n-2 3 . (A peak is a triple of adjacent cards with the middle one having greatest value.) Although the algorithms do not provide all eigenvectors of all Hopf-power Markov chains, their stationary distributions are always computable.

A new extension: Markov chains from convolutions of projections

As (Pang, 2014, Th. 4.4.1) shows, the breaking step of a Hopf-power Markov chain always involves a symmetric multinomial distribution. However, it is sometimes more natural to consider other distributions. For example, the restriction-then-induction chain mentioned above is difficult to express in terms of partitions, because the restriction of a symmetric group representation to a multinomially-chosen Young subgroup involves Littlewood-Richardson coefficients. Simpler is the Markov chain which removes a random corner box and re-inserts it in a random position.

The discovery in this extended abstract is that, by replacing m [a] ∆ [a] in the definition of a Hopf-power Markov chain with a non-negative convolution of projections (Definition 2.3), one can change the piece sizes in the breaking step to have any desired distribution. For example, the "remove and re-insert a box" chain above comes from the map m(Proj 1 ⊗ι)∆, using exactly the same Doob transform. (ι is the identity map and Proj 1 is projection to the subspace of degree 1.) On the shuffle algebra, m(Proj 1 ⊗ι)∆ defines the much studied top-to-random shuffle: take the top card off the deck, then re-insert it at a uniformly chosen position. The other non-negative convolutions of projections recover the shuffles of [START_REF] Diaconis | Analysis of top to random shuffles[END_REF], where the deck is cut in some specified distribution, and then the cards dropped one by one from the bottom of piles chosen with probability proportional to pile size. Their Corollaries 5.1 and 5.2 are a formula for the composition of such shuffles, and an upper bound for the mixing time. The inverses of such shuffles are examples of pop shuffles of [START_REF] Bidigare | A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements[END_REF], so the eigenvalues and multiplicities can be calculated with their hyperplane walk theory.

This new class of Markov chains admit analysis by the same techniques as for Hopf-power Markov chains. Maps between Hopf algebras "respecting the bases" again induce projections of their associated chains (Theorem 4.1 below). Consequently, the descent set is a Markov statistic under all these shuffling schemes. Existing literature on convolutions of projections provides the eigenvalues and multiplicities of these transition matrices. In some cases, there are eigenbasis algorithms resembling those for the Hopfpower chains. Once again, the stationary distributions of all these chains are accessible -they are precisely the same as those for the Hopf-power chains.

One notable shuffle outside this framework is random-to-random: uniformly choose a card to remove from the deck, and re-insert it in a uniform position. Its defining linear map is an interesting operator on other combinatorial Hopf algebras, and it would be great to find a probability interpretation.

This extended abstract is organised as follows: Section 2 gives the conditions on the two main characters in this story, the state space basis of a combinatorial Hopf algebra and the non-negative convolution of projections map. Section 3 explains how to construct the Markov chain via the Doob transform. Section 4 states the three main theorems: how morphisms of Hopf algebras lead to Markov statistics; the eigenvalues of the transition matrices and their multiplicities; and the common stationary distributions. Section 5 shows one scenario where explicit eigenbasis formulae are available, and gives probability applications both for shuffling and for a chain on trees.

Combinatorial Hopf Algebras and the Convolution Product

The starting point of our Markov chain construction is a combinatorial Hopf algebra, which encodes the breaking and combining rules for our family of combinatorial objects. An instructive example is the shuffle algebra, whose associated Markov chains describe various models of shuffling.

Example 2.1 The shuffle algebra has a basis B of words, which we will think of as decks of cards. For example, the word accb will denote the deck with card a on top, followed by two copies of card c, and card b on the bottom. This algebra is graded by the lengths of the words, or the number of cards in the deck. The product of two words is the sum of all their interleavings (with multiplicity), and the coproduct of a word is the sum of all its deconcatenations. For example,

m(ac ⊗ cb) = 2accb + acbc + cacb + cabc + cbac; ∆(accb) = 1 ⊗ accb + a ⊗ ccb + ac ⊗ cb + acc ⊗ b + accb ⊗ 1.
The exposition of [START_REF] Grinberg | Hopf algebras in combinatorics[END_REF] gives background on combinatorial Hopf algebras, and the opening of Foissy ( 2012) contains an extensive list of examples with references. Like many recent treatments, these focus on generalisations of the symmetric functions, which, though extremely important, are not so integral to the present Markov chain application. The thesis of (Klausner, 2011, Sec. 4) is closer to the viewpoint herein.

There is no rigorous definition of a combinatorial Hopf algebra. The intuition is that such an algebra H should have a basis B indexed by a family of combinatorial objects, graded by their sizes. (Assume throughout that the ground field is Q or R, to facilitate the probability applications.) Write H n for the subspace of H of degree n, so H = H n . Since the empty object is the only object of size 0, the vector space H is connected, i.e. dim H 0 = 1. Now equip H with a multiplication map m : H i ⊗ H j → H i+j : for w, z ∈ B, set m(w ⊗ z) to be the sum (possibly weighted) of all possible results from "combining" w and z. Similarly, the coproduct map ∆ :

H n → n i=0 H i ⊗ H n-i takes x ∈ B
to the sum (possibly weighted) of w ⊗ z over all pairs (w, z) obtainable by "breaking" x. There are various axioms that these operations must satisfy.

The above combinatorial interpretation of the product and coproduct motivates that the structure constants be non-negative (conditions i and ii below). This is crucial for the transition probabilities in Definition 3.1 to be non-negative. As we will discover in Section 3, another important hypothesis for the construction of the associated Markov chains is that ∆(x) = 1 ⊗ x + x ⊗ 1 for any x ∈ B of degree greater than 1. Intuitively, it mandates that "every combinatorial object of size greater than 1 can be broken into strictly smaller pieces". Combining these criteria leads to the following definition:

Definition 2.2 (Pang, 2014, Def. 4.3.3) A basis B = n B n of a graded connected Hopf algebra H = n H n is a state space basis if:
i) for all w, z ∈ B, the expansion of m(w ⊗ z) in the B basis has all coefficients non-negative;

ii) for all x ∈ B, the expansion of ∆(x) in the B ⊗ B basis has all coefficients non-negative;

iii) for n > 1, the basis B n contains no primitive elements. That is, ∆(x) = 1 ⊗ x + x ⊗ 1 for all

x ∈ B n with n > 1.

Note that H may contain primitive elements of high degree, so long as they are not in the basis B.

Having fixed a combinatorial Hopf algebra and a degree n, the next step is to choose the distribution of sizes of pieces in the breaking step of the Markov chain. As Step 1 of the interpretation in Section 3 will show, these distributions are in bijection, up to scaling, with the class of non-negative convolutions of projections, as defined below. For example, the operator Proj d1 * Proj d2 will constrain the first piece to be of size exactly d 1 , and the second piece to be of size exactly d 2 .

Given maps f, g : H → H, their convolution product f * g : H → H is the composition

f * g := m(f ⊗ g)∆.
Since the product m on H is associative and the coproduct is coassociative, the convolution product is associative, and it is useful to view

f 1 * • • • * f a as m [a] (f 1 ⊗ • • • ⊗ f a )∆ [a] .
Here m [a] : H ⊗a → H and ∆ [a] : H → H ⊗a are the a-fold product and a-fold coproduct respectively, describing the combining of a objects and breaking one object into a pieces (some of which may be trivial). So m [2] = m and ∆ [2] = ∆. (A precise definition, by induction, is as follows:

m [1] := ι, m [a] := m(m [a-1] ⊗ ι); ∆ [1] := ι, ∆ [a] := (ι ⊗ • • • ⊗ ι ⊗ ∆)∆ [a-1] .)
The present Markov chain application uses only the case f i = Proj di , the projection to the subspace of degree d i . In other words, Proj d : H → H d is the linear map satisfying Proj d (x) = x for x ∈ H d , and Proj d (H i ) = 0 if i = d. It will be convenient to allow the case d = 0.

Patras (1994) studied linear combinations of these convolutions of projections. He called them descent operators, since his Theorem II.7 shows that, on a commutative or cocommutative Hopf algebra, these operators form an algebra under composition isomorphic to the descent algebra of the symmetric group. This connection is central to the eigenbasis algorithms for the present Markov chains, which come from the following subset of these operators: ii) for some weak-composition D of n where each

d i = n, the coefficient α D is positive.
The second axiom ensures that T : H n → H n is not merely multiplication by a constant. Note that the map T does not uniquely determine the coefficients α D , because of the possibility of parts of size 0. Different choices of α D lead to different interpretations of the same Markov chain. One final remark on this definition: it is fine for infinitely many α D to be non-zero, as the image T(x) of any particular x ∈ H is always a finite sum. This is because there are only finitely many weak-compositions of a given integer into exactly a parts.

One key example of a non-negative convolution of projections is the ath Hopf-power map m [a] ∆ [a] . This is the ath convolution power of the identity map, so it corresponds to setting α D ≡ 1 for all weakcompositions D. As the three-step interpretation of Section 3 will explain, the associated Markov chains have a symmetric multinomial breaking step. This is the case previously studied in [START_REF] Diaconis | Hopf algebras and Markov chains: two examples and a theory[END_REF] and in [START_REF] Pang | Hopf algebras and Markov chains[END_REF]. Another important specialisation comes from α (1,n-1) = 1, α D = 0 if D = (1, n -1) for any n, so T = Proj 1 * ι. This map produces Markov chains which break off a singleton and reattach it, analogous to the top-to-random shuffle of the introduction.

More examples are at the end of the next section.

Building The Markov Chain

The following fact is the main motivation for the definition of a Markov chain for each non-negative convolution of projections: the probability that a riffle-shuffle takes a deck x of n cards to a deck y is the coefficient of y in 1 2 n m∆(x). In other words, the transition matrix of the riffle-shuffling of n cards is 1 2 n m∆ T Bn , the transpose of the matrix of the linear operator 1 2 n m∆ with respect to the basis B n of words. A similar direct calculation shows that the top-to-random shuffle of n cards has transition matrix T Bn do not sum to the same number. One of the major findings of (Diaconis, Pang, and Ram, 2014, Th. 3.4) is that, when T is a Hopf-power map T = m [a] ∆ [a] , and B is a state space basis, then it is possible to define a rescaling B of B so the row sums of [T] T Bn are equal. (Pang, 2014, Sec. 4.3) gives a much slicker and more general description of this rescaling, in terms of the Doob transform. This allows a generalisation to linear maps on H that are not the Hopf-power. Indeed, (Pang, 2014, Th. 3.1) describes the choice of rescalings B of B that are available for arbitrary linear maps.

It happens that the standard rescaling for the Hopf-power maps also applies to non-negative convolutions of projections; indeed, the rescaling necessary to construct a T-Markov chain depends only on the underlying Hopf algebra, and not on the map T. This resulting Markov chain is:

Definition 3.1 Let H = ⊕ n≥0
H n be a graded connected Hopf algebra with state space basis B. For x ∈ B n , let η(x) denote the sum of the coefficients (in the B ⊗n basis) of Proj ⊗n 1 ∆ [n] (x), and let

Bn := x η(x)
x ∈ B n .

Let T = α D Proj d1 * • • • * Proj da be a non-negative convolution of projections on H n . Then the T-Markov chain on B n has transition matrix

1 β n T T Bn
, where

β n := d1+•••+da=n α D n d 1 . . . d a .
The hypotheses of a state space basis ensure that η(x) is never zero. In the shuffle algebra, η(x) = 1 always, so no rescaling is necessary.

Expressing the above transition probabilities in terms of a "natural" process requires careful analysis of the underlying Hopf algebra. Fortunately, one only needs to do this once for each Hopf algebra to interpret all its T-Markov chains, as an analogue of (Pang, 2014, Th. 4.4.1) shows that these have the form:

1.

Choose a weak-composition (d 1 , . . . , d a ) of n with probability 1 βn α D n d1...da .

2.

Choose a way to break into pieces of sizes d 1 , . . . , d a .

3.

Choose a way to combine these pieces.

Here, the probabilities of the choices in steps 2 and 3 depend only on the Hopf algebra, not on T. (The exact expressions for these probabilities are unsightly and not instructive; the interested reader may consult (Pang, 2014, Th. 4.4.1).) For example, a T-shuffle (the T-Markov chain on the shuffle algebra) of n cards is the following:

1,2.

Cut the deck into piles of sizes (d 1 , . . . , d a ) with probability 1 βn α D n d1...da .

3.

Drop one-by-one the bottommost card from a pile chosen with probability proportional to the current pile size.

Aside from the GSR riffle-shuffle, its a-handed generalisation, and the top-to-random shuffle, here are some additional notable T-shuffles: [START_REF] Assaf | Riffle shuffles with biased cuts[END_REF] give the mixing time for shuffles with biased cuts, when the shuffler prefers to take more cards in one hand than the other. Here, the probability of cutting i cards off the top of a deck of n cards is the asymmetric binomial, q i (1 -q) n-i n i , for some parameter q ∈ (0, 1). The associated non-negative convolution of projections is

Example 3.2 Assaf,
T = n i=0 q i (1 -q) n-i Proj i * Proj n-i .
This has an obvious a-handed generalisation, with a -1 parameters. Setting all parameters to 1 a then recovers the a-handed riffle-shuffle (even though the associated non-negative convolution of projections is then a -n ι * a instead of ι * a , as these Markov chains depend on T only up to scaling).

Example 3.3 (Diaconis, Fill, and Pitman, 1992, Sec. 2 and Sec. 6, Ex. 2) discuss two notions of top-mto-random shuffles: T = Proj m * ι corresponds to cutting off m cards and re-inserting them randomly, keeping their relative order, whilst T = Proj * m 1 * ι cuts m cards off and inserts them randomly in any order. For both schemes, they show that n m log n shuffles suffice to randomise the deck. Example 3.4 Taking T = Proj 1 * ι + ι * Proj 1 produces a shuffle where the pile sizes are (1, n -1) or (n -1, 1), each with probability 1 2 . In other words, flip a fair coin, and perform a top-to-random shuffle if the coin shows heads, and a bottom-to-random shuffle if it shows tails. This is the (symmetric) top-orbottom-to-random shuffle of (Diaconis, Fill, and Pitman, 1992, Sec. 6, Ex 4). It is easy to introduce an asymmetry here: for q ∈ [0, 1], take T = q Proj 1 * ι + (1 -q)ι * Proj 1 . Setting q = 1 then recovers the top-to-random shuffle. Theorem 5.1 below exhibits an eigenbasis for this map on cocommutative Hopf algebras.

The Markov chains coming from the above choices of T, on other Hopf-algebras, are also interesting. Example 3.5 The irreducible representations of the symmetric groups form a basis of a Hopf algebra, with product being external induction, and coproduct coming from restriction to Young subgroups. It is straightforward to adapt (Pang, 2014, Ex. 4.4.3) to give the following description for each step of a T-Markov chain, starting from a representation x of S n :

1.

Choose a Young subgroup

S d1 × • • • × S da of S n with probability 1 βn α D n d1...da . 2.
Restrict the starting state x to the chosen subgroup.

3.

Induce it back up to S n , then pick an irreducible constituent with probability proportional to the dimension of its isotypic component.

In particular, the Proj 1 * ι-chain is restricting to S n-1 , inducing back to S n , then choosing an irreducible constituent as in step 3. This chain previously appeared in the work of [START_REF] Fulman | Commutation relations and Markov chains[END_REF], where it generates central limit theorems for character ratios. For a more involved example, see Example 5.3 regarding the (q Proj 1 * ι+(1-q)ι * Proj 1 )-Markov chain on trees.

As outlined in the introduction, viewing Markov chains in this Hopf-theoretic framework gives two useful consequences. The first is the construction of Markov statistics from maps between Hopf algebras: Theorem 4.1 Let H, H be graded, connected Hopf algebras with bases B, B respectively. Suppose in addition that B is a state space basis. Let T be a non-negative convolution of projections. If θ : H → H is a Hopf-morphism such that θ(B n ) = Bn for all n, then the T-chain on Bn is the projection under θ of the T-chain on B n .

It follows that θ is a Markov statistic for the T-chain on B n -this fact would be interesting by itself even if the projected chain were not identified as the T-chain on the target Hopf algebra.

The second profit of the Hopf formulation is the following expression for all the eigenvalues and multiplicites of these Markov chains, which hint at their long term behaviour. It follows from (Patras, 1994, Th. II.7), (Krob, Leclerc, and Thibon, 1997, Prop. 3.12), (Bonnafé and Pfeiffer, 2008, Prop. 3.10) and the arguments of (Krob, Leclerc, and Thibon, 1997, Th. 3.21) and of [START_REF] Aguiar | Antipode and convolution powers of the identity in graded connected Hopf algebras[END_REF], or alternatively from the Poincaré-Birkhoff-Witt straightening algorithm and the Perron-Frobenius theorem.

β λ β n := 1 β n D n α D λ, D λ n ,
and the multiplicity of the eigenvalue β λ βn is the coefficient of x λ := x λ1 . . . x λ l in the generating function i (1 -x i ) -bi , where b i satisfies

n dim H n t n = i (1 -t i ) -bi . Futhermore, T is diagonalisable if H is commutative or cocommutative.
Note that β (n) agrees with the β n of Definition 3.1, so this is not a point of confusion. Here's how this formula specialises to some key examples: Example 4.3 Let T = Proj 1 * ι, the top-to-random map. Recall that this corresponds to α (1,n-1) = 1, and all other α D = 0. So, for all partitions λ of n, it holds that β λ = λ, (1, n -1) , and this is the number of parts of size 1 in λ, which can be 0, 1, . . . , n -2, or n. So the eigenvalues of a top-to-random chain on any Hopf algebra are β λ /β (n) = 0, 1 n , 2 n , . . . , n-2 n , 1. In the case of the shuffle algebra, for a deck of distinct cards, (Diaconis, Fill, and Pitman, 1992, Th. 4.1) show that the multiplicity of the eigenvalue j n is the number of permutations with n -j fixed points, and find projection operators for each eigenspace (on the right). (Hivert, Luque, Novelli, and Thibon, 2011, Sec. 4.6) produce an eigenbasis by associating each permutation with n -j fixed points to an eigenvector of eigenvalue j n . The present Proj 1 * ι-chain framework generalises this eigenbasis algorithm for decks with repeated cards; see the remark after Proposition 5.2. It follows from a multigraded refinement of Theorem 4.2 above that, for any T-shuffle of a deck of distinct cards, the multiplicity of the eigenvalue β λ /β (n) is the number of permutations of cycle type λ.

Example 4.4 Take T = (q Proj 1 * ι + (1 -q)ι * Proj 1 ), the "asymmetric top-or-bottom-to-random" operator. Its eigenvalues are

β λ β n = q λ, (1, n -1) + (1 -q) λ, (n -1, 1) n .
Note that the definition of λ, D depends only on the part sizes of the composition D and not on their order, so λ, (1, n -1) = λ, (n -1, 1) . Hence the eigenvalues of top-or-bottom-to-random are the same as for top-to-random in Example 4.3 above, with the same multiplicities.

Using the multiplicity in Theorem 4.2 for the eigenvalue 1 =

β (n)
βn shows that the following expressions, which are easily shown to be linearly independent stationary distributions, do span the eigenspace of eigenvalue 1. Theorem 4.5 For a fixed state space basis B, all T-Markov chain on B n have the same set of stationary distributions. These can be uniquely written as a linear combination of the functions

π c1,...,cn (x) := η(x) n! 2 σ∈Sn coefficient of x in the product c σ(1) . . . c σ(n)
for each multiset {c 1 , . . . , c n } in B 1 . (Here, η(x) are the rescaling constants of Definition 3.1.)

As noted in (Pang, 2014, Th. 4.5.1), π c1,...,cn (x) essentially enumerates the ways to build x out of c 1 , . . . , c n using the multiplication of the combinatorial Hopf algebra, and to then break it into singletons. In the case of card-shuffling, the unique stationary distribution for all T-shuffles is the uniform distribution.

Eigenvectors and Applications

Since the coefficients α D of a non-negative convolution of projections can take any non-negative value, it's not surprising that there is no neat universal eigenbasis algorithm for these chains. However, one case which works out nicely, thanks to the theory of dual graded graphs of (Fomin, 1994, Th. 1.6.6), is the top-or-bottom-to-random chain of Example 3.4: Theorem 5.1 Let H be a graded connected Hopf algebra, and P be a (graded) basis of its primitive subspace. Write P as the disjoint union P 1 P >1 , where P 1 has degree 1. Set

E j :=    j i=0 σ∈Sj j i q i (1 -q) j-i c σ(1) . . . c σ(i) τ ∈S k p τ (1) . . . p τ (k) c σ(i+1) . . . c σ(j)    ,
ranging over all multisets {c 1 , . . . , c j } of P 1 , and all multisets {p 1 , . . . , p k } of P >1 where deg p

1 + • • • + deg p k = n -j.
Then E j is a linearly independent set of eigenvectors of eigenvalue j n for the operator 1 n (q Proj 1 * ι + (1 -q)ι * Proj 1 ) : H n → H n . Furthermore, if H is cocommutative, then n-2 j=0 E j E n is a basis.

Here are some simple applications of these eigenvectors to the top-or-bottom-to-random shuffle of a deck of distinct cards, analogous to the statements for riffle-shuffling in the fifth paragraph of the introduction. (The shuffle algebra is commutative, so its dual is cocommutative, and the eigenvectors of T on this dual give right eigenfunctions of the transition matrix, from which one deduces these results.) of superiority from him becomes a VP. Then the employees who produced subpar work are fired, one by one starting from the most superior. Each firing causes a cascade of promotions: first, someone further down the chain of superiority from the fired employee is uniformly selected to replace him. Then, if the promoted employee was superior to anyone, then one of those is uniformly selected and promoted to his position. This process continues until someone who is not superior to anyone is promoted.

The chain keeps track of the structure of the regular employees, but does not know which employee is taking which position in the forest structure, nor does it see the structure of the VPs.

The cases j = 2, 3 below are analogues of Proposition 5.2 for this chain. These are inequalities, rather than equalities, because the exact eigenvectors in Theorem 5.1 are very complicated (involving a second sum), so to obtain a slicker result, we use instead the estimates ≈ f j . Defining these requires some more notation: for a regular employee u, let desc(u) (resp. anc(u)) denote the number of regular employees who are further down (resp. up) from u in the chain of superiority, including u himself in both counts. (In tree language, these are the descendants and the ancestors). Also, write n (u) for the size of the connected component of regular employees containing u.

Proposition 5.4 Let {X t } denote the trinomial-top-and-bottom-to-random Markov chain on the Connes-Kreimer Hopf algebra of rooted forests, with interpretation and notation as above. For each integer j ≥ 2, define the following functions on forests: ≈ f j (T ) := u∈T q desc(u) 1 q anc(u) 3 desc(u) j .

(The binomial coefficient is 0 if desc(u) < j.) Then Expectation ≈ f j (X t ) ≤ q jt 2 ≈ f j (X 0 ) max u∈X0:desc(u)≥j n (u) anc(u) -1 .

Definition 2. 3

 3 Let H be a graded connected Hopf algebra, and fix an integer a ≥ 2. A map T : H → H of the form T := d1,...,da α (d1,...,da) Proj d1 * • • • * Proj da is a non-negative convolution of projections on H n if i) for all weak-compositions D := (d 1 , . . . , d a ) of n (that is, d i ≥ 0 and d i = n), the coefficients α D are non-negative;

  Theorem 4.2 Work in the setup of Definition 3.1. Given a partition λ := (λ 1 , . . . , λ l ) and a weakcomposition D = (d 1 , . . . , d a ), let λ, D denote the number of set partitions B 1 | . . . |B a of {1, 2, . . . , l} such that, for each i ∈ {1, . . . a}, we have j∈Bi λ j = d i . (So λ, D is equal to the inner product p λ , h D of symmetric functions, hence the notation.) Then the eigenvalues of 1 βn T : H n → H n are

Acknowledgements

I would like to thank Thomas Lam and Nathan Williams for inspiring this project, and Nantel Bergeron, Persi Diaconis, Ian Grojnowski, Philippe Nadeau and Franco Saliola for many helpful discussions. The comments from the referees, especially the detailed pointers to the literature, are much appreciated.

Proposition 5.2 Let {X t } denote the top-or-bottom-to-random shuffle, with parameter q, of a deck of n distinct cards. Suppose the starting deck X 0 is in ascending order. Let Des(X) ⊆ {1, 2, . . . , n -1} and Peak(X) ⊆ {1, 2, . . . , n -2} denote the positions of the descents and peaks of X respectively. Then

Setting q = 1 in Theorem 5.1 gives the eigenvectors for the top-to-random operator Proj 1 * ι as

These are also the eigenvectors of Proj * m 1 * ι, the unordered version of top-m-to-random as in Example 3.3, with eigenvalue j m / n m . The reason is that, on a cocommutative Hopf algebra, the map Proj * m 1 * ι is a polynomial in Proj 1 * ι. Similarly, the E j in Theorem 5.1 are eigenvectors of any polynomial in q Proj 1 * ι+(1-q)ι * Proj 1 . In particular, they have eigenvalue q n-j 2 for the following map, corresponding to the trinomial-top-and-bottom-to-random shuffle of (Diaconis, Fill, and Pitman, 1992, Sec. 6, Ex 6):

(Here, q 1 + q 2 + q 3 = 1, and the previous q is q1 q1+q3 in terms of the new parameters.) To finish, here is an example away from the world of card-shuffling, to illustrate the diversity of Markov chains that this framework can analyse.

Example 5.3 We will study the trinomial-top-and-bottom-to-random Markov chain (of two paragraphs prior) on the Connes-Kreimer Hopf algebra of rooted forests. Take as state space basis the set of all rooted forests -that is, a disjoint union of trees, each of which has a distinguished root vertex. (The vertices are unlabelled, and the embedding of the tree in the plane is immaterial.) The degree of a forest is its number of vertices. The product of two trees is their disjoint union, and the coproduct of a tree T is the sum of T \S ⊗ S over all connected subtrees S of T which are either empty or contain the root of T . Hence ι * Proj 1 corresponds to removing a root of a forest, and Proj 1 * ι to removing a leaf. For a full definition of this algebra, see [START_REF] Connes | Hopf algebras, renormalization and noncommutative geometry[END_REF], second half of Sec. 2).

The Hopf-power Markov chain on this algebra was the subject of (Pang, 2014, Sec. 5.3). Adapting Theorem 5.3.8 there gives the following description of the trinomial-top-and-bottom-to-random chain:

Suppose a company has a forest structure, so all employees have at most one direct superior. All employees are either regular employees or VPs, and the superior of a VP is necessarily also a VP (so the VPs in each connected component of the company form a subtree containing the root).

Each month, each regular employee independently produces excellent work with probability q 3 , average work with probability q 2 , and subpar work with probability q 1 (where q 1 +q 2 +q 3 = 1.) For each employee who produced excellent work, one by one in a random order, the regular employee furthest up the chain