ALTERNATING FORMULAS FOR K-THEORETIC QUIVER POLYNOMIALS

EZRA MILLER

Abstract. The main theorem here is the K-theoretic analogue of the cohomological ‘stable double component formula’ for quiver polynomials in [KMS03]. This K-theoretic version is still in terms of lacing diagrams, but nonminimal diagrams contribute terms of higher degree. The motivating consequence is a conjecture of Buch on the sign-alternation of the coefficients appearing in his expansion of quiver K-polynomials in terms of stable Grothendieck polynomials for partitions [Buc02a].

Introduction

The study of combinatorial formulas for the degeneracy loci of quivers of vector bundles with arbitrary ranks was initiated by Buch and Fulton [BF99]. In their paper they studied the case of a sequence E_{0} → E_{1} → ⋯ → E_{n} of vector bundles over a fixed base. Their Main Theorem implies that given an integer array r = (r_{ij})_{i≤j}, the cohomology class of the locus Ω_{r} in the base where E_{i} → E_{j} has rank at most r_{ij} can be expressed, under suitably general conditions, as an integer sum of products of Schur polynomials evaluated on the Chern classes of the bundles E_{i}. After giving an explicit algorithmic—but nonpositive—expression for the quiver coefficients appearing in the sum, they also conjectured a positive combinatorial formula for them. This conjecture was proved in [KMS03] (for a natural choice of an array of rectangular tableaux) by way of three other positive combinatorial formulas for the quiver polynomials.

The cohomological ideas of [BF99] were extended to K-theory in [Buc02a], where the class KQ_{r} of the structure sheaf of the degeneracy locus Ω_{r} is expressed as an integer sum of products of stable double Grothendieck polynomials for Grassmannian permutations. Buch proved an algorithmic combinatorial formula for the coefficients in this expansion of KQ_{r} [Buc02a, Theorem 4.1], and conjectured that the signs of these coefficients alternate in a simple manner [Buc02a, Conjecture 4.2].

The purpose of this paper is to prove Buch’s conjecture (Theorem 18) by way of combinatorial formulas for KQ_{r}. The starting point is a formula from [KMS03] that expresses a ‘doubled’ version of the Laurent polynomial KQ_{r} as a ratio of two Grothendieck polynomials (Definition 1). Consequently, the arguments and results in this paper do not require any geometry of degeneracy loci or K-theory. For an introduction to those geometric perspectives, see [Buc02a].

The main result here is Theorem 13, which gives a K-theoretic extension of the stable double component formula that appeared in [KMS03, Theorem 6.20]. That formula from [KMS03] was cohomological, and was stated as a sum over lacing diagrams (graphical representations of sequences of partial permutations) that are minimal. In Theorem 13, nonminimal diagrams contribute terms of higher degree. The word ‘stable’ refers to the limit in Theorem 13 obtained by adding a large constant m to all of the ranks r_{ij}. When specialized to the ordinary (non-doubled) Laurent polynomial KQ_{r}, Theorem 13 holds without taking limits, and Buch’s conjecture follows using a sign-alternation theorem of Lascoux [Las01, Theorem 4] (see Section 6).

Date: 10 June 2004.

The author was partly supported by the National Science Foundation, grant DMS-0304789.

The proof of Theorem 13 generalizes a procedure suggested by [KMS03] (see Remark 6.21 there), and carried out in [Yon03], for constructing pipe dreams associated to given lacing diagrams. This technique is combined with those developed in [KM03b] for dealing with nonreduced subwords of reduced expressions for permutations. The K-theory analogue of a formula [KMS03, Theorem 5.5] for quiver polynomials in terms of the pipe dreams of Fomin and Kirillov [FK96] enters along the way (Theorem 3).

Buch [Buc03] independently arrived at the main results and definitions here (and more) by applying general techniques of Fomin and Kirillov [FK96, FK94]. A special case of the sign conjecture and K-component formula already appeared in [BKTY03].

Organization. A notion of double quiver K-polynomial is identified via a ratio formula in Section 1, in analogy with the way (cohomological) double quiver polynomials arise in [KMS03]. The ‘pipe formula’ for quiver K-polynomials is proved in Section 2, after background on nonreduced pipe dreams and Demazure products. The condition on nonminimal lacing diagrams that turns out to make them occur with sign ±1 in the K-component formula is defined in Section 3. Rank stability of these nonminimal lacing diagrams, proved in Section 4, leads to the the stable K-component formula in Section 5, after reviewing basics regarding Grothendieck polynomials and their stable limits. Finally, Buch’s sign alternation conjecture is derived in Section 6.

1. Double quiver K-polynomials

A k×ℓ partial permutation is a k×ℓ matrix w whose entries are either 0 or 1, with at most one nonzero entry in each row or column. Each such matrix w can be completed to a permutation matrix—that is, with exactly one 1 in each row and column—having w as its upper-left k×ℓ corner. Viewing permutations as lying in the union S_{∞} = ⋃_{m} S_{m} of all symmetric groups S_{m}, there is a unique completion w̃ of w that has minimal length l(w̃). For any partial permutation w, we write q = w(p) if the entry w_{pq} at (p, q)—that is, in row p and column q—equals 1. If v is a permutation matrix, then the assignment p ↦ v(p) defines a permutation in S_{∞}.

Let z = z_{1}, z_{2}, … and ż = ż_{1}, ż_{2}, … be alphabets. Writing a given polynomial f in these two alphabets over the integers ℤ as a polynomial in z_{i} and z_{i+1} with coefficients that are polynomials in the other variables, the i^{th} Demazure operator \overline{∂}_{i} sends f to

\overline{∂}_{i}f = \frac{z_{i+1}f(z_{i}, z_{i+1}) − z_{i}f(z_{i+1}, z_{i})}{z_{i+1} − z_{i}}.

Let w_{0}^{m} be the permutation of maximal length in S_{m}, and write s_{i} ∈ S_{∞} for the transposition switching i and i + 1. Following [LS82], the double Grothendieck polynomial for a permutation v ∈ S_{m} is defined from the “top” double Grothendieck polynomial G_{w_{0}^{m}}(z/ż) = ∏_{i+j≤m}(1 − z_{i}/ż_{j}) by the recursion

G_{vs_{i}}(z/ż) = \overline{∂}_{i}G_{v}(z/ż)

whenever vs_{i} is lower in Bruhat order than v. This definition is independent of the choice of m [LS82]. If w is a partial permutation, then set G_{w}(z/ż) = Gw̃(z/ż). The notation here differs from [FK94], where their polynomial 𝔏\begin{matrix}(−1) \\ w \end{matrix}(y, x) is obtained from G_{w}(z/ż) by replacing z_{i} with 1 − x_{i} and ż_{i}^{−1} with 1 − y_{i}.

The permutation matrices v of central importance here are those defined as follows. Fix a positive integer d and an expression d = ∑_{j=0}^{n} r_{j} of d as a sum of n+1 “ranks” r_{j}. Endow each d × d permutation matrix v with a block decomposition in which the j^{th} block row from the top has height r_{j}, and the i^{th} block column from the right has width r_{i}. Thus each d × d permutation matrix v is composed of (n + 1)^{2} blocks B_{ij}, each of size r_{j} × r_{i} and lying at the intersection of block column i and block row j. The matrix v is a Zelevinsky permutation if B_{ij} has all zero entries whenever i ≥ j +2, and the nonzero entries of v proceed from northwest to southeast within every block row and within every block column (so v has no 1 entry that is northeast of another within the same block row or block column).

For each Zelevinsky permutation v, there is a rank array r = (r_{ij})_{i≤j} such that v equals the Zelevinsky permutation v(r) associated to r as in the original construction from [KMS03, Proposition 1.6]. Indeed, it can be checked that the following suffices: define r_{ij} to be the number of nonzero entries of v in the union of all blocks B_{pq} for which i ≥ p and j ≤ q (that is, blocks B_{pq} weakly southeast of B_{ij}). In particular, r_{ii} = r_{i}, and the number of nonzero entries in the block B_{j+1,j} of v is r_{j,j+1}. Pictures and examples can be found in [KMS03, Section 1.2], but see also Example 4, below.

Double Grothendieck polynomials for Zelevinsky permutations v(r) are naturally written as G_{v(r)}(x/y^{∘}), using two alphabets z = x and ż = y^{∘} each of which is an ordered sequence of n + 1 alphabets of sizes r_{0}, …, r_{n} and r_{n}, …, r_{0}, respectively:

x = x^{0}, …, x^{n} and y^{∘} = y^{n}, …, y^{0},
where x^{j} = x_{1}^{j}, …, x_{r_{j}}^{j} and y^{j} = y_{1}^{j}, …, y_{r_{j}}^{j}.

It is convenient to think of the x variables as labeling the rows of the d × d grid (from top to bottom, in the above ordering on the x variables), while the y^{∘} variables label its columns (from left to right, in the above ordering on the y^{∘} variables). See [KMS03, Section 2.2] for pictures and examples. Most partial permutations w that occur in the sequel will have size r_{j−1} × r_{j} for some j ∈ {1, …, n}; in that case we usually consider G_{w}(x^{j−1}/y^{j}), so z = x^{j−1} and ż = y^{j}.

Among all d × d Zelevinsky permutations with block decompositions determined by d = ∑_{j=0}^{n} r_{j}, there is a unique one v(Hom) whose rank array r(Hom) is maximal, in the sense that r_{ij}(Hom) ≥ r_{ij} for all other d × d Zelevinsky permutations v(r).

Definition 1. The double quiver K-polynomial is the ratio

KQ_{r}(x/y^{∘}) = \frac{G_{v(r)}(x/y^{∘})}{G_{v(Hom)}(x/y^{∘})}

of double Grothendieck polynomials for v(r) and v(Hom).

The “ordinary” specialization of the polynomial KQ_{r}(x/y^{∘}) appears in the Ktheoretic ratio formula [KMS03, Theorem 2.7]. It will follow from Theorem 3, below, that G_{v(Hom)}(x/y^{∘}) divides G_{v(r)}(x/y^{∘}), so the right hand side of Definition 1 is actually a (Laurent) polynomial rather than simply a rational function.

2. Nonreduced pipe dreams

A k×ℓ pipe dream is a subset of the k×ℓ grid, identified as the set of crosses in a tiling of the k×ℓ grid by crosses and elbow joints [figure] , as in the following diagrams:

[figure: + + + +  + + + + +; =; + + + + + + + + + +; =]

The square tile boundaries are omitted from the tilings forming the newtworks of pipes on right sides of these equalities. Pipe dreams are special cases of diagrams introduced by Fomin and Kirillov [FK96]; for more background, see [KM03a, Section 1.4].

A pipe dream P yields a word in the Coxeter generators s_{1}, s_{2}, s_{3}, … of S_{∞} by reading the antidiagonal indices of the crosses in P along rows, right to left, starting from the top row and proceeding downward [BB93, FK96]. The Demazure product δ(P) is obtained (as in [KM03b, Definition 3.1]) by omitting adjacent transpositions that decrease length. More precisely, δ(P) is obtained by multiplying the word of P using the idempotence relation s_{i}^{2} = s_{i} along with the usual braid relations s_{i}s_{i+1}s_{i} = s_{i+1}s_{i}s_{i+1} and s_{i}s_{j} = s_{j}s_{i} for |i − j| ≥ 2. Up to signs, this amounts to taking the product of the word of P in the degenerate Hecke algebra [FK96]. Let

P(w) = {pipe dreams P | δ(P) = w̃}

for a k×ℓ partial permutation w be the set of pipe dreams whose Demazure product is the minimal completion of w to a permutation w̃ ∈ S_{∞}. Every pipe dream in P(w) fits inside the k×ℓ rectangle, and is to be considered as a pipe dream of size k×ℓ. The subset of P(w) consisting of reduced pipe dreams (or rc-graphs [BB93]), where no pair of pipes crosses more than once, is denoted by RP(w).

Here is the observation that will make the limiting arguments in [KMS03, Section 6] for reduced pipe dreams work on nonreduced pipe dreams (see Proposition 5, below).

Lemma 2. Suppose that P ∈ P(w). Then the crossing tiles in P lie in the union of all reduced pipe dreams for w.

Proof. The statement is obvious if P is reduced, so suppose otherwise. Then some pipe dream P′ ∈ P(w) be can be obtained by deleting a single crossing tile from P. By induction, each crossing tile in P′ lies in some reduced pipe dream for w. On the other hand, a second pipe dream P′′ ∈ P(w) can be obtained from P by deleting a different crossing tile (using [KM03b, Theorem 3.7], for example). Induction shows that each crossing tile in P′′, including the tile P ∖ P′, lies in a reduced pipe dream for w. □

The exponential reverse monomial associated to a d × d pipe dream P is

(1 − x̃/ỹ)^{P} = ∏_{+ ∈ P}(1 − x̃_{+}/ỹ_{+}),

where the variable x̃_{+} sits at the left end of the row containing after reversing each of the x alphabets before Definition 1, and the variable ỹ_{+} sits atop the column containing after reversing each of the y alphabets there (see Example 4).

Fix d = r_{0} + ⋯ + r_{n} as in Section 1, and let D_{Hom} be the Ferrers shape of all locations strictly above the block superantidiagonal (as in [KMS03, Definition 1.10]). The region corresponding to D_{Hom} in the d × d grid is filled with crossing tiles in every reduced pipe dream for every d × d Zelevinksy permutation v (to deduce this one needs only that v is devoid of nonzero entries in that region). By Lemma 2, every nonreduced pipe dream P ∈ P(v) contains D_{Hom}, as well. (In [KMS03], the crossing tiles in D_{Hom} ⊆ P are the ∗ entries of P, but it is necessary here to consider all of the crosses in P, including those in D_{Hom}, to make the meaning of δ(P) clear.)

All of the crossing tiles in every pipe dream P ∈ P(v) lie above the main antidiagonal (this holds for any permutation v ∈ S_{d}, since the other crosses correspond to Coxeter generators that lie outside of S_{d}). Hence the “interesting” crossing tiles in each pipe dream P ∈ P(v) all lie in the block antidiagonal and the block superantidiagonal. In particular, any pipe dream P ∈ P(v) with no crossing tiles in its antidiagonal blocks has its “interesting” crosses confined to the block superantidiagonal. These kinds of pipe dreams P ∈ P(v(r)) will be central to the next section.

Here is the K-theoretic analogue of the reversed version [KMS03, Proposition 6.9] of the pipe formula for cohomological quiver polynomials [KMS03, Theorem 5.5].

Theorem 3 (Pipe formula). The double quiver K-polynomial is the alternating sum

KQ_{r}(x/y^{∘}) = ∑_{δ(P)=v(r)}(−1)^{|P |−l(v(r))}(1 − x̃/ỹ)^{P ∖D_{Hom}}

of exponential reverse monomials associated to pipe dreams P ∖D_{Hom} for P ∈ P(v(r)). The exponent on −1 is the number crosses in P minus the length l(v(r)) of v(r).

Proof. The formula of Fomin and Kirillov [FK94, Theorem 2.3 and p. 190] (or see [KM03b, Theorem 4.1 and Corollary 5.4]) implies that for any permutation w, the Grothendieck polynomial for w can be expressed as the alternating sum

G_{w}(z/ż) = ∑_{δ(P)=w}(−1)^{|P |−l(w)}(1 − z/ż)^{P} ,

where (1 − z/ż)^{P} = ∏_{+∈P} (1 − z_{+}/ż_{+}) is the product of the factors (1 − z_{p}/ż_{q}) such that P has a crossing tile at (p, q). On the other hand, it follows immediately from the isobaric divided difference recursion that G_{w}(z/ż) is symmetric in z_{p} and z_{p+1} if w(p) < w(p+1)—that is, if w has no descent at p, or equivalently, if the nonzero entry of w at (p, w(p)) is northwest of (p + 1, w(p + 1)). Applying the same logic to w^{−1}, we find that G_{w}(z/ż) is symmetric in ż_{q} and ż_{q+1} whenever (w^{−1}(q), q) is northwest of (w^{−1}(q + 1), q + 1). Consequently, the northwest-to-southeast progression of nonzero entries in block rows and columns implies that the double Grothendieck polynomial for any Zelevinsky permutation is symmetric in each of its 2n + 2 alphabets. The ratio in Definition 1 now gives the desired result via the Fomin–Kirillov formula, after using the symmetry in the 2n + 2 alphabets to reverse each one. □

Example 4. Let d = 8 = 1 + 3 + 3 + 1 and consider the Zelevinsky permutation v = 52361487 at left below. The pipe dream P below has Demazure product δ(P) = v.

[figure: v =; \begin{matrix}5 & · & · & · & · & × & · & · & · \\ 2 & · & × & · & · & · & · & · & · \\ 3 & · & · & × & · & · & · & · & · \\ 6 & · & · & · & · & · & × & · & · \\ 1 & × & · & · & · & · & · & · & · \\ 4 & · & · & · & × & · & · & · & · \\ 8 & · & · & · & · & · & · & · & × \\ 7 & · & · & · & · & · & · & × & · \end{matrix}; ,  P =; =; \begin{aligned}& y_{1}^{3} & y_{3}^{2} & y_{2}^{2} & y_{1}^{2} & y_{3}^{1} & y_{2}^{1} & y_{1}^{1} & y_{1}^{0} \\ x_{1}^{0} & + & + & + & + & · & · & + & · \\ x_{3}^{1} & + & · & · & · & · & · & · & · \\ x_{2}^{1} & + & · & · & · & + & · & · & · \\ x_{1}^{1} & + & + & · & · & · & · & · & · \\ x_{3}^{2} & · & · & · & · & · & · & · & · \\ x_{2}^{2} & · & · & · & · & · & · & · & · \\ x_{1}^{2} & · & · & · & · & · & · & · & · \\ x_{1}^{3} & · & · & · & · & · & · & · & · \end{aligned}]

Indeed, the transposition s_{7} from the cross at (3, 5) is canceled by the idempotence relation from the word associated to P, so δ(P) = s_{7}s_{4}s_{3}s_{2}s_{1}s_{2}s_{3}s_{5}s_{4} = v. The exponential reverse monomial associated to P ∖ D_{Hom}, which uses the given labeling of the rows and columns by variables, is

(1 − x̃/ỹ)^{P ∖D_{Hom}} = (1 − \frac{x_{1}^{0}}{y_{1}^{1}} )(1 − \frac{x_{2}^{1}}{y_{3}^{1}} )(1 − \frac{x_{1}^{1}}{y_{3}^{2}} ).

The summand in Theorem 3 corresponding to P contributes the negative of this product, since l(v) = 9 but P has 10 crosses.

Let m+r be the rank array obtained from r by adding the nonnegative integer m to each entry of r. Let x_{m+r} be a list of finite alphabets of sizes m + r_{0}, …, m + r_{n}, and let the alphabets in y^{∘}_{m+r} have sizes m + r_{n}, …, m + r_{0}. This notation agrees with that in [KMS03, Section 4.4]. Denote by D_{Hom}(m) the unique reduced pipe dream for the Zelevinsky permutation v(m + r(Hom)) in S_{d+m(n+1)} associated to the maximal irreducible rank array.

Proposition 5. There is a fixed integer ℓ, independent of m, such that for every pipe dream P ∈ P(v(m + r)) with at least one cross in an antidiagonal block, setting the last ℓ variables to 1 in every finite alphabet from the lists x_{m+r} and y^{∘}_{m+r} kills the exponential reverse monomial (1 − x̃/ỹ)^{P ∖D_{Hom}(m)}.

Proof. The result is immediate from Lemma 2 and [KMS03, Proposition 6.10], the latter being the analogue for reduced pipe dreams and ‘ordinary’ (as opposed to exponential) monomials. □

3. Nonminimal lacing diagrams

Suppose that w = (w_{1}, …, w_{n}) is a list of partial permutations in which w_{j} has size r_{j−1} × r_{j}. The list w can be identified with the (nonembedded) graph in the plane called its lacing diagram in [KMS03, Section 3.1], based on diagrams of Abeasis and Del Fra [AD80]. The vertex set of the graph consists of r_{j} bottom-justified dots in column j for j = 0, …, n, with an edge connecting the dot at height α (from the bottom) in column j − 1 with the dot at height β in column j if and only if the entry of w_{j} at (α, β) is 1. A lace is a connected component of a lacing diagram. For example, here is the lacing diagram associated to a partial permutation list:

⟷ ([\begin{matrix}1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}],[\begin{matrix}0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{matrix}],[\begin{matrix}1 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{matrix}])

The goal of this section is to define what it means for a rank array to equal the Demazure product δ(w) of a lacing diagram w. That δ(w) is a rank array rather than a minimal lacing diagram is in analogy with Demazure products of lists of simple reflections, which are permutations rather than reduced decompositions. Usually δ(w) will not equal the rank array of w itself. In analogy with Demazure products of reduced words, however, the Demazure product of a minimal lacing diagram will equal its own rank array.

Definition 6. Suppose P_{1}, …, P_{n} are pipe dreams of sizes r_{0} × r_{1}, …, r_{n−1} × r_{n}, and set d = r_{0} + ⋯ + r_{n}. Denote by P (P_{1}, …, P_{n}) the d × d pipe dream in which every block strictly above the block superantidiagonal is filled with crossing tiles, and the superantidiagonal r_{j−1} × r_{j} block in block row j − 1 is the pipe dream P_{j}.

Given a k×ℓ pipe dream P, let P̌ be the k×ℓ pipe dream that results after rotating P through 180^{∘}. Also, if m ∈ ℕ, write m + P_{j} for the k × (ℓ + m) pipe dream that results by shifting all the crosses in P_{j} to the right by m.

Proposition 7. Fix a lacing diagram w = (w_{1}, …, w_{n}). The Demazure product of P (P_{1}, …, P_{n}) is independent of P_{1}, …, P_{n}, as long as P̌_{j} ∈ P(w_{j}) for all j = 1, …, n.

Proof. First consider an arbitrary pipe dream P. Instead of the usual word for P, consider the word in s_{1}, s_{2}, s_{3}, … gotten by reading the antidiagonal indices of the crosses in P from top to bottom in each column, starting in the right column and proceeding leftward. The results of [FK96] imply that using the idempotence and Coxeter relations to multiply this word again yields the Demazure product δ(P).

We need P (P_{1}, …, P_{n}) and P (P′_{1}, …, P′_{n}) to have equal Demazure products whenever δ(P̌_{j}) = δ(P̌′_{j}) for all j. It follows from the definitions that δ(P̌_{j}) = δ(P̌′_{j}) if and only if δ(P_{j}) = δ(P_{j}), and this latter equality is equivalent to δ(m + P_{j}) = δ(m + P′_{j}) for all m ∈ ℕ.

Reading right to left in each row as usual, by associativity of Demazure products we only need the corresponding block rows of P = P (P_{1}, …, P_{n}) and P′ = P (P′_{1}, …, P′_{n}) to have equal Demazure products. Suppose that block row j − 1 in the the Ferrers shape D_{Hom} has m columns, and let v_{j} be the Demazure product of this block row. Applying the first paragraph to corresponding block rows of P and P′, we find that the Demazure products of block row j − 1 in P and P′ are obtained by using the idempotence and Coxeter relations to multiply δ(m + P_{j})v_{j} and δ(m + P′_{j})v_{j}. □

Definition 8. Fix a lacing diagram w. If, for some (and hence, by Proposition 7, every) sequence P_{1}, …, P_{n} of pipe dreams satisfying P̌_{j} ∈ P(w_{j}) for all j, the Demazure product of P (P_{1}, …, P_{n}) is a Zelevinsky permutation v(r), then we write δ(w) = r and call the rank array r the Demazure product of the lacing diagram w.

Example 9. For the lacing diagram w below, the pipe dreams P_{j} satisfy P̌_{j} ∈ P(w_{j}).

w  \begin{aligned}& & · & · & + \\ & \begin{matrix}· & · & · \\ · & · & · \\ + & · & + \end{matrix} & & P_{1} \\ · ; · ; · & P_{2} \\ P_{3} \end{aligned}  \begin{matrix}\begin{matrix}+ & + & + & + & · & · & + & · \\ + & · & · & · & · & · & · & · \\ + & · & · & · & · & · & · & · \\ + & + & · & + & · & · & · & · \\ · & · & · & · & · & · & · & · \\ · & · & · & · & · & · & · & · \\ · & · & · & · & · & · & · & · \\ · & · & · & · & · & · & · & · \end{matrix} & = & [figure] \\ P = P (P_{1}, P_{2}, P_{3}) \end{matrix}

The Demazure product δ(P) of the pipe dream P = P (P_{1}, P_{2}, P_{3}) at right above equals the Zelevinsky permutation v from Example 4. If r is the rank array satisfying v = v(r), then we conclude that δ(w) = r. Observe that although P_{1}, P_{2}, and P_{3} are all reduced pipe dreams, the pipe dream P is not reduced, so w is not minimal. Thus the lacing diagram w will give rise to a higher degree summand in Theorem 13, below.

4. Rank stability of lacing diagrams

Next we show that lacing diagrams with Demazure product r are stable, in the appropriate sense, under uniformly increasing ranks obtained by replacing r with m + r. The results and methods in this section rely on certain parts of [KMS03], namely Proposition 5.7 (which is actually [BB93, Theorem 3.7]) and Section 5.3. That material describes the elementary combinatorics behind the transition from v(r) to v(1 + r) [KMS03, Lemma 5.11], and the resulting effect on reduced pipe dreams of the form P (P_{1}, …, P_{n}) [KMS03, Propositions 5.7 and 5.15]. To avoid excessive use of the word ‘block’ in what follows, we use ‘horizontal strip j’ as a synonym for ‘block row j’.

Lemma 10. If P (P_{1}, …, P_{n}) ∈ P(v(1 + r)) and each P̌_{j} is the top pipe dream for a (1 + r_{j−1}) × (1 + r_{j}) partial permutation w_{j}, then all crossing tiles of P_{j} lie in the southwest r_{j−1} × r_{j} rectangle of the superantidiagonal block in horizontal strip j − 1.

Thus the superantidiagonal block in the Lemma is supposed to have a blank row above and a blank column to the right of the southwest r_{j−1}×r_{j} rectangle in question.

Proof. No reduced pipe dream for v(1+r) has a crossing tile on the main superantidiagonal, by [KMS03, Proposition 5.15]. Lemma 2 implies that the same is true of P. It follows that w_{j} = 1 + w′_{j} for some r_{j−1} × r_{j} partial permutation w′_{j}. Consequently, the left column of P̌_{j} has no crossing tiles, and shifting all crossing tiles in P̌_{j} one unit to the left results in the top pipe dream for w′_{j}. This top pipe dream fits inside the rectangle of size r_{j−1} × r_{j}. □

Suppose P = P (P_{1}, …, P_{n}) is a pipe dream in which

(SW)

P_{j} has size (1 + r_{j−1}) × (1 + r_{j}), but every in P_{j} lies in the
southwest r_{j−1} × r_{j} rectangle.

Write P′_{j} for the r_{j−1} × r_{j} pipe dream consisting of the southwest rectangle of P_{j}, and then write P′ = P (P′_{1}, …, P′_{n}). Thus P has block sizes consistent with ranks 1 + r (so the i^{th} antidiagonal block is square of size 1 + r_{ii}), while P′ has block sizes consistent with ranks r (so the i^{th} antidiagonal block is square of size r_{ii}). The construction can also be reversed to create P having been given the pipe dream called P′.

For a pipe dream P, as in [KM03b, Theorem 4.4] say that P simplifies to D ⊆ P if D is the lexicographically first subword of P with Demazure product δ(P). Equivalently, if P_{≤m} is the length m initial string of simple reflections in P, the simplification D is gotten by omitting the m^{th} reflection from P for all m such that δ(P_{≤m−1}) = δ(P_{≤m}).

Given a reduced pipe dream D, an elbow tile is absorbable [KM03b, Section 4] if the two pipes passing through it intersect in a crossing tile to its northeast. It follows from the definitions that a pipe dream P simplifies to D if and only if P is obtained from D by changing (at will) some of its absorbable elbow tiles into crossing tiles.

Lemma 11. Suppose D = (D_{1}, …, D_{n}) satisfies the (SW) condition. Then D is a reduced pipe dream for v(1 + r) if and only if D′ = (D′_{1}, …, D′_{n}) is a reduced pipe dream for v(r). In this case, the absorbable elbow tiles in horizontal strip j − 1 of D′ are in bijection with the absorbable elbow tiles in the southwest r_{j−1} × r_{j} rectangle of the superantidiagonal block in horizontal strip j − 1 of D.

Proof. The first claim is a straightforward consequence of [KMS03, Proposition 5.15]. The second claim follows because the corresponding pairs of pipes in D and D′ pass through corresponding elbow tiles. The rest of the proof makes this statement precise.

Given a nonzero entry of the Zelevinsky permutation v(1 + r), exactly one of the following three conditions must hold: (i) the entry lies in the northwest corner of some superantidiagonal block; (ii) the entry lies in the southeast corner of the whole matrix; or (iii) there is a corresponding nonzero entry in v(r). This means that the pipes in D′ are in bijection with those pipes in D corresponding to nonzero entries of v(1 + r) that do not satisfy (i) or (ii). Furthermore, it is easily checked that the pipes in D of type (i) or (ii) can only intersect a superantidiagonal block in its top row or rightmost column. Hence to say

the two pipes passing through an elbow tile in the southwest r_{j−1} × r_{j} rectangle of the superantidiagonal block in horizontal strip j − 1 of D correspond to the pipes passing through the corresponding elbow in D′

actually makes sense. That this claim is true follows from [KMS03, Proposition 5.15], and it immediately proves the lemma. □

In [KMS03, Corollary 5.16] it was proved that the set of lacing diagrams obtained from reduced pipe dreams for v(r) is in canonical bijection with the set of (automatically minimal) lacing diagrams obtained from reduced pipe dreams for v(1 + r). Here is the extension to nonreduced pipe dreams, via nonminimal lacing diagrams. For notation, given m ∈ ℕ and a k×ℓ partial permutation w, define the (m+k)×(m+ℓ) partial permutation m + w to fix 1, …, m and act on {m + 1, …, m + k} just as w acts on {1, …, k}. For a list w = (w_{1}, …, w_{n}) of partial permutations, set m+w = (m+w_{1}, …, m+w_{n}). This notation agrees with that in [KMS03, Section 4.4].

Proposition 12. For each array r, let L(r) = {w | δ(w) = r} be the set of lacing diagrams w with Demazure product r. Then L(r) and L(m+r) are in canonical bijection:

L(m + r) = {m + w | w ∈ L(r)}.

Proof. It suffices to prove the case m = 1, so suppose w ∈ L(1 + r). Let P = P (P_{1}, …, P_{n}) be the pipe dream in P(v(1 + r)) for which each P̌_{j} is the top pipe dream in RP(w_{j}). Then P simplifies to a reduced pipe dream D ∈ RP(v(1 + r)). By Lemma 10 there is a corresponding pipe dream D′ ∈ RP(v(r)), constructed via the procedure after Lemma 10. On the other hand, the pipe dream P′ constructed from P results by changing back into crossing tiles those elbow tiles in D′ that correspond to the tiles deleted from P to get D. Lemma 11 says that P′ has Demazure product v(r). Defining w′ by the equality 1 + w′ = w, which can be done by Lemma 10, it follows that w′ ∈ L(r).

In summary, we have constructed P′ from P via the intermediate steps

P ∈ P(v(1 + r)) ⇝ D ∈ RP(v(1 + r)) ⇝ D′ ∈ RP(v(r)) ⇝ P′ ∈ P(v(r)),

where the first and third steps are simplification and “unsimplification”. Consequently, L(1 + r) ⊆ {1 + w′ | w′ ∈ L(r)}. But the arguments justifying these steps are all reversible, so the reverse containment holds, as well. □

5. Stable double component formula

The main result in this paper, namely Theorem 13, involves stable double Grothendieck polynomials Ĝ_{w}(z/ż) for k×ℓ partial permutations w [FK94], which we recall presently. Suppose that the argument of a Laurent polynomial G is naturally a pair of alphabets z and ż of sizes k and ℓ, respectively. In this section and the next, the convention is that if G(z/ż) is written, but z or ż has fewer than the required number of letters, then the rest of the letters are assumed to equal 1. For example, the notation KQ_{m+r}(x_{r}/y^{∘}_{r}) indicates that all variables in x_{m+r} ∖ x_{r} and y^{∘}_{m+r} ∖ y^{∘}_{r} (see the paragraph preceding Proposition 5) are to be set equal to 1.

Under this convention, let w be a k×ℓ partial permutation, and write G_{m+w}(z_{k}/ż_{ℓ}) for each m ≥ 0 to mean the Laurent polynomial G_{m+w} applied to alphabets z_{k} and ż_{ℓ} of fixed sizes k and ℓ. As m gets large, these Laurent polynomials eventually stabilize, allowing the notation Ĝ_{w}(z/ż) = lim_{m→∞} G_{m+w}(z_{k}/ż_{ℓ}) for the stable double Grothendieck polynomial.

Given a lacing diagram w with r_{j} dots in column j, for j = 0, …, n denote by

G_{w}(x/y^{∘}) = G_{w_{1}}(x^{0}/y^{1}) ⋯ G_{w_{n}}(x^{n−1}/y^{n})

the product of double Grothendieck polynomials taken over partial permutations in the list w = (w_{1}, …, w_{n}). Add hats over every G for the stable Grothendieck case.

Here now is the main result, the K-theoretic analogue of the (cohomological) component formula for stable double quiver polynomials [KMS03, Theorem 6.20]. For notation, recall the set L(r) = {w | δ(w) = r} from Proposition 12, define the length of the lacing diagram w to be the sum l(w) = ∑_{i=1}^{n} l(w̃_{i}) of the lengths of the minimal extensions of w_{1}, …, w_{n} to permutations, and set d(r) = l(v(r)) − l(v(Hom)). (Thus d(r) is the “expected codimension” of the locus Ω_{r} from the introduction, and d(r) can be described equivalently as ∑_{i<j}(r_{i,j−1} −r_{ij})(r_{i+1,j} −r_{ij}), or as l(v(r)) − |D_{Hom}|.)

Theorem 13. The limit of the double quiver K-polynomials KQ_{m+r}(x_{r}/y^{∘}_{r}) for m approaching ∞ exists and equals the alternating sum

G_{r}(x/y^{∘}) := lim_{m→∞} KQ_{m+r}(x_{r}/y^{∘}_{r}) = ∑_{w∈L(r)}(−1)^{l(w)−d(r)}Ĝ_{w}(x/y^{∘})

of products of stable double Grothendieck polynomials. The limit polynomial G_{r}(x/y^{∘}) is symmetric separately in each of the 2n + 2 finite alphabets x^{0}, …, x^{n}, y^{n}, …, y^{0}.

Definition 14. G_{r}(x/y^{∘}) is called the stable double quiver K-polynomial.

As we shall see in Corollary 17 and the comments after it, the Laurent polynomial G_{r}(x/y^{∘}) is not a new object: it is obtained from Buch’s power series P_{r} [Buc02a, Section 4] by substituting 1−x_{i} for x_{i} and 1−y_{j}^{−1} for y_{j} in each polynomial G_{μ_{k}} there.

Proof. Define KQ_{m+r}(x/y^{∘})_{ℓ} by setting the last ℓ variables to 1 in every finite alphabet from the lists x_{m+r} and y^{∘}_{m+r}. Similarly, for each lacing diagram w, define G_{m+w}(x/y^{∘})_{ℓ} by setting the same variables to 1 in G_{m+w}(x/y^{∘}). Because of the nature of the limit in question, and the defining properties of stable Grothendieck polynomials, it suffices to prove that for all m ≥ 0 and some fixed ℓ independent of m,

KQ_{m+r}(x/y^{∘})_{ℓ} = ∑_{w∈L(r)}(−1)^{l(w)−d(r)}G_{m+w}(x/y^{∘})_{ℓ}.

Fix ℓ as in Proposition 5, and apply Theorem 3 to m + r instead of r. Setting the last ℓ variables in each alphabet to 1 on the right hand side there kills all summands corresponding to pipe dreams P that are not expressible as P (P_{1}, …, P_{n}) for some list of pipe dreams P_{j} of sizes (m + r_{j−1}) × (m + r_{j}); this is the content of Proposition 5. What remains on the right side of Theorem 3 is a sum of terms having the form (−1)^{|P |−l(v(m+r))}(1−x̃/ỹ)_{ℓ}^{P ∖D_{Hom}(m)} for pipe dreams P = P (P_{1}, …, P_{n}) in P(v(m+r)). If P_{j} ∈ P(m + w_{j}) for each j, then this term equals the product

(−1)^{l(w)−d(r)} ∏_{i=1}^{n}(−1)^{|P_{j}|−l(w̃_{j})}(1 − x̃^{j−1}/ỹ^{j})_{ℓ}^{P_{j}} (∗)

for w = (w_{1}, …, w_{n}). The signs in (∗) are correct because |P | − l(v(m + r)) = ∑_{j} |P_{j}| − d(m + r), and d(m + r) = d(r). To make sense of (1 − x̃^{j−1}/ỹ^{j})^{P_{j}}, identify P_{j} with the d × d pipe dream consisting of just P_{j} on the j^{th} superantidiagonal block.

For each lacing diagram w ∈ L(r), let P_{w}(m + r) be the set of pipe dreams P (P_{1}, …, P_{n}) ∈ P(v(m + r)) such that P̌_{j} ∈ P(m + w_{j}) for all j. Summing the products in (∗) over pipe dreams P ∈ P_{w}(m + r) yields (−1)^{l(w)−d(r)}G_{m+w}(x/y^{∘})_{ℓ} by [FK94, Theorem 2.3 and p. 190] (see also [KM03b, Section 5]). Summing over w ∈ L(r) completes the proof, by Proposition 12. □

Remark 15. Theorem 13 implies that G_{m+r}(x_{r}/y^{∘}_{r}) = G_{r}(x/y^{∘}), in analogy with the (defining) stability properties of stable double Grothendieck polynomials.

Remark 16. Theorem 13 gives an explicit combinatorial formula, but the characterization of the Demazure product δ(w) of a lacing diagram via Zelevinsky permutations would be more satisfying if it were intrinsic. That is, it would be better to identify those partial permutation lists that fit stripwise into a pipe dream with Demazure product v(r) using the language of lacing diagrams, without referring to Zelevinsky permutations or pipe dreams. Such an intrinsic method appears in [BFR03].

6. Sign alternation

A permutation μ ∈ S_{∞} is Grassmannian if it has at most one descent—that is, at most one index p such that μ(p) > μ(p + 1). A crucial property of arbitrary stable double Grothendieck polynomials, proved in [Buc02b, Theorem 6.13], is that every such polynomial Ĝ_{w}(z/ż) has a unique expression

Ĝ_{w}(z/ż) = ∑_{Grassmannian μ} α_{w}^{μ}Ĝ_{μ}(z/ż)

as a sum of stable Grothendieck polynomials Ĝ_{μ} for Grassmannian permutations. If \underline{μ} = (μ_{1}, …, μ_{n}) is a sequence of partial permutations such that the minimal completions μ̃_{1}, …, μ̃_{n} are Grassmannian, then let us call \underline{μ} a Grassmannian lacing diagram.

Corollary 17. If α\underline{μ} ; w = ∏_{i=1}^{n} α_{w_{i}}^{μ_{i}} for lacing diagrams w and Grassmannian \underline{μ}, then

G_{r}(x/y^{∘}) = ∑_{\underline{μ}} c\underline{μ}(r)Ĝ\underline{μ}(x/y^{∘})
for the constants  c\underline{μ}(r) = ∑_{w∈L(r)}(−1)^{l(w)−d(r)}α\underline{μ} ; w,

where the first sum above is over all Grassmannian lacing diagrams \underline{μ}.

Proof. Expand the right hand side of Theorem 13 using Ĝ_{w} = ∑_{μ} α_{w}^{μ}Ĝ_{μ}. □

Let G_{r}(x/x^{∘}) be the specialization of the stable double quiver K-polynomial obtained by setting y^{j} = x^{j} for j = 0, …, n. Independently from Corollary 17, it follows from [Buc02a, Theorem 4.1] that the (ordinary) stable quiver K-polynomial

G_{r}(x/x^{∘}) = ∑_{\underline{μ}} c\underline{μ}(r)Ĝ\underline{μ}(x/x^{∘})

is a sum of products of stable double Grothendieck polynomials Ĝ_{μ_{j}}(x^{j−1}/x^{j}) for Grassmannian permutations μ̃_{j}, with uniquely determined integer coefficients c\underline{μ}(r). That these coefficients are the same as in Corollary 17 follows from the fact that the right side above determines the same element in the n^{th} tensor power of Buch’s bialgebra Γ [Buc02b, Buc02a] as does the right side of the top formula in Corollary 17.

In addition to proving the expansion of Ĝ_{w} as a sum of terms α_{w}^{μ}Ĝ_{μ}, Buch showed in [Buc02b, Theorem 6.13] that the coefficients α_{w}^{μ} can only be nonzero if l(μ) ≥ l(w), and he conjectured that the sign of α_{w}^{μ} equals (−1)^{l(μ)−l(w)}. This was proved by Lascoux [Las01, Theorem 4] as part of his extension of “transition” from Schubert polynomials to Grothendieck polynomials. Since, as shown in [Buc02a, Section 5], the coefficients α_{w}^{μ} are special cases of the coefficients c\underline{μ}(r), Lascoux’s result is evidence for the following more general statement that was surmised by Buch (prior to [Las01]).

Theorem 18 ([Buc02a, Conjecture 4.2]). The coefficients c\underline{μ}(r) alternate in sign; that is, (−1)^{l(\underline{μ})−d(r)}c\underline{μ}(r) ≥ 0 is a nonnegative integer.

Proof. By [Las01, Theorem 4] the sign of α\underline{μ} ; w is (−1)^{l(\underline{μ})−l(w)}. Thus the sign of c\underline{μ}(r) is (−1)^{l(w)−d(r)}(−1)^{l(\underline{μ})−l(w)} = (−1)^{l(\underline{μ})−d(r)}, by the second formula in Corollary 17. □

References

[AD80] S. Abeasis and A. Del Fra, Degenerations for the representations of a quiver of type A_{m}, Boll. Un. Mat. Ital. Suppl. (1980) no. 2, 157–171.

[BB93] Nantel Bergeron and Sara Billey, RC-graphs and Schubert polynomials, Experimental Math. 2 (1993), no. 4, 257–269.

[BF99] Anders Skovsted Buch and William Fulton, Chern class formulas for quiver varieties, Invent. Math. 135 (1999), no. 3, 665–687.

[BFR03] Anders S. Buch, László M. Fehér, and Richárd Rimányi, Positivity of quiver coefficients through Thom polynomials, preprint, 2003. arXiv:math.AG/0311203

[BKTY03] Anders S. Buch, Andrew Kresch, Harry Tamvakis, and Alexander Yong, Grothendieck polynomials and quiver formulas, 2003.

[Buc02a] Anders S. Buch, Grothendieck classes of quiver varieties, Duke Math. J. 115 (2002), no. 1, 75–103.

[Buc02b] Anders S. Buch, A Littlewood–Richardson rule for the K-theory of Grassmannians, Acta Math. 189 (2002), 37–78.

[Buc03] Anders S. Buch, Alternating signs of quiver coefficients, preprint, 2003.

[FK94] Sergey Fomin and Anatol N. Kirillov, Grothendieck polynomials and the Yang–Baxter equation, 1994, Proceedings of the Sixth Conference in Formal Power Series and Algebraic Combinatorics, DIMACS, pp. 183–190.

[FK96] Sergey Fomin and Anatol N. Kirillov, The Yang-Baxter equation, symmetric functions, and Schubert polynomials, Discrete Math. 153 (1996), no. 1–3, 123–143, Proceedings of the 5th Conference on Formal Power Series and Algebraic Combinatorics (Florence, 1993).

[KM03a] Allen Knutson and Ezra Miller, Gröbner geometry of Schubert polynomials, to appear in Ann. of Math (2), 2003.

[KM03b] Allen Knutson and Ezra Miller, Subword complexes in Coxeter groups, to appear in Adv. in Math., 2003. arXiv:math.AG/0309259

[KMS03] Allen Knutson, Ezra Miller, and Mark Shimozono, Four positive formulae for type A quiver polynomials, preprint, 2003. arXiv:math.AG/0308142

[Las01] A. Lascoux, Transition on Grothendieck polynomials, Physics and combinatorics, 2000 (Nagoya), 164–179, World Sci. Publishing, River Edge, NJ, 2001.

[LS82] Alain Lascoux and Marcel-Paul Schützenberger, Structure de Hopf de l’anneau de cohomologie et de l’anneau de Grothendieck d’une variété de drapeaux, C. R. Acad. Sci. Paris Sér. I Math. 295 (1982), no. 11, 629–633.

[Yon03] Alexander Yong, On combinatorics of quiver component formulas, preprint, 2003.

University of Minnesota, Minneapolis, Minnesota

E-mail address: ezra@math.umn.edu