Séminaire Lotharingien de Combinatoire 74 (2015), Article B74a

COMBINATORIAL RULES FOR THREE BASES OF POLYNOMIALS

COLLEEN ROSS AND ALEXANDER YONG

In memory of Alain Lascoux, who inspired this paper one night in Osaka

Abstract. We present combinatorial rules (one theorem and two conjectures) concerning three bases of ℤ[x_{1}, x_{2}, ….]. First, we prove a “splitting” rule for the basis of Key polynomials [Demazure, Bull. Sci. Math. 98 (1974), 163–172], thereby establishing a new positivity theorem about them. Second, we introduce an extension of Kohnert’s [Bayreuth. Math. Schriften 38 (1990), 1–97] ”moves” to conjecture the first combinatorial rule for a certain deformation [Lascoux, in: Physics and Combinatorics, World Scientific Publishing, 2001, pp. 164–179] of the Key polynomials. Third, we use the same extension to conjecture a new rule for the Grothendieck polynomials [Lascoux and Schützenberger, C. R. Acad. Sci. Paris Sér. I Math. 295 (1982), 629–633].

1. Introduction

1.1. Overview. This paper contributes to the study of certain bases of the ring of polynomials Pol = ℤ[x_{1}, x_{2}, …] that are defined by symmetrizing operators. Our two main sources on this subject, and the specific perspective we pursue, are A. Lascoux’s books [12, 14].

The Schur basis of the ring Λ of symmetric polynomials is central to algebraic combinatorics in at least two ways. These polynomials have fundamental applications outside of the theory of symmetric functions, specifically to representation theory of the symmetric group and of the general linear group, and to Schubert calculus, see, e.g., [20]. Moreover, understanding combinatorial descriptions of the Schur polynomials has led to a rich theory of Young tableaux. In particular, the problem of how to multiply two Schur polynomials, and expand the result back in the Schur basis, is important in the aforementioned applications. This problem is solved by the Littlewood–Richardson rule.

Now, since the ring of symmetric polynomials is a subring of Pol, one considers the following basic question [14]:

How does one lift properties of Λ (and its Schur basis) to the entirety of Pol? A number of bases, that may be considered natural lifts of the Schur basis, are considered in [12, 14]. These include the Schubert, Grothendieck, Macdonald, and Key polynomials; we will also consider a deformation of the Key polynomials defined by A. Lascoux [11]. These are lifts of the Schur basis in the sense that a certain subset in each of these families is precisely the Schur basis, or otherwise deforms the elements of the Schur basis. In fact, like the Schur polynomials, each of these families have applications to representation theory and geometry.

Now, one would like to find combinatorial descriptions for the polynomials in each of these families. Indeed, such descriptions exist. Yet at present, there is no analogue of the Littlewood–Richardson rule. That is, for each basis, one desires a combinatorial description of how to multiply and expand in the basis so that one recovers a Littlewood– Richardson rule in the special case of Schur polynomials. For instance, for the case of Schubert polynomials, and more generally, the case of Grothendieck polynomials, this is a longstanding open problem in combinatorial Schubert calculus, cf. [20].

There is a close tie between Littlewood–Richardson rules and the Young tableau description of Schur polynomials. Therefore, by analogy, one would like to find alternative combinatorial descriptions of the aforementioned bases of Pol. The hope is that such alternatives might shed light on finding corresponding generalizations of the Littlewood– Richardson rule.

Our work consists of a new combinatorial description for three of the aforementioned bases of polynomials. We give one theorem and two conjectures, which we summarize as follows:

First, we prove a “splitting” rule for the basis of Key polynomials {κ_{α} | α ∈ ℤ_{≥0}^{∞}}, thereby establishing a new positivity theorem about these polynomials. This family was introduced in [5] and first studied combinatorially in [15, 16]. Combinatorial rules for their monomial expansion are known, see, e.g., [15, 16, 21, 8]. Our rule refines the rule of [21, Theorem 5(1)]. Our rule is also analogous to the splitting rule [4, Corollary 3] for the basis of Schubert polynomials {𝔖_{w} | w ∈ S_{∞}}.

Second, we investigate the aforementioned basis of polynomials {Ω_{α} | α ∈ ℤ_{≥0}^{∞}} defined by A. Lascoux [11] that deforms the Key basis. By extending the Kohnert moves of [10] we conjecturally give the first combinatorial rule for the Ω-polynomials.

Third, in [10], the Kohnert moves were used to conjecture the first combinatorial rule for Schubert polynomials (a proof was later presented in [24]). Similarly, we use the extended Kohnert moves to give a conjecture for the basis of Grothendieck polynomials {𝔊_{w} | w ∈ S_{∞}} [17]. This rule has a significantly different appearance than earlier (proved) rules, such as those in [7, 11, 3, 19].

1.2. Splitting Key polynomials. Let S_{∞} be the group of permutations of ℕ with finitely many non-fixed points. This group acts on Pol by permuting the variables. Let s_{i} be the simple transposition interchanging x_{i} and x_{i+1}. The divided difference operator acts on Pol by

∂_{i} = \frac{1 − s_{i}}{x_{i} − x_{i+1}} .

Define the Demazure operator by setting

π_{i}(f) = ∂_{i}(x_{i} · f), for f ∈ Pol.

Let α = (α_{1}, α_{2}, …) ∈ ℤ_{≥0}^{∞} and assume throughout that |α| = ∑_{i} α_{i} < ∞. Define the Key polynomial κ_{α} to be

x^{α} := x_{1}^{α_{1}}x_{2}^{α_{2}} ⋯, if α is weakly decreasing.

Otherwise, set

κ_{α} = π_{i}(κα̂) where α̂ = (…, α_{i+1}, α_{i}, …) and α_{i+1} > α_{i}.

(The π_{i}’s, and ∂_{i}’s also, are well-known to satisfy the braid relations for S_{n}, and so the κ_{α}’s are independent of the order in which the π_{i}’s are applied.) Since the leading term (under the pure reverse lexicographic order) of κ_{α} is x^{α}, the Key polynomials form a ℤ-basis of Pol.

The Key polynomials lift the Schur polynomials: when

(1.1)  α = (α_{1}, α_{2}, …, α_{t}, 0, 0, 0, …), where α_{1} ≤ α_{2} ≤ ⋯ ≤ α_{t},

then

(1.2)  κ_{α} = s_{(α_{t},...,α_{2},α_{1})}(x_{1}, …, x_{t}).

A descent of α is an index i such that α_{i} ≥ α_{i+1}; a strict descent is an index i such that α_{i} > α_{i+1}. Fix descents d_{1} < d_{2} < ⋯ < d_{k} of α containing all strict descents of α. Since π_{i} is a symmetrizing operator, κ_{α} is separately symmetric in each collection

X_{1} = {x_{1}, x_{2}, …, x_{d_{1}}}, X_{2} = {x_{d_{1}+1}, x_{d_{1}+2}, …, x_{d_{2}}}, …, X_{k} = {x_{d_{k−1}+1}, x_{d_{k−1}+2}, …, x_{d_{k}}}.

(The variables x_{d_{k}+1}, x_{d_{k}+2}, … do not appear in κ_{α}.) Therefore, there is a unique expansion

(1.3)  κ_{α}(X) = ∑_{λ^{1},...,λ^{k}} E_{λ^{1},...,λ^{k}}^{α} s_{λ^{1}}(X_{1}) ⋯ s_{λ^{k}}(X_{k}),

where each λ^{i} is a partition. A priori, one only knows that E_{λ^{1},...,λ^{k}}^{α} ∈ ℤ.

The Rothe diagram of a permutation w ∈ S_{n} is

Rothe(w) = {(x, y) | y < w(x) and x < w^{−1}(y)} ⊂ [n] × [n]

(indexed so that the southwest corner is labeled (1, 1)). The code of w, denoted by code(w) ∈ ℤ_{≥0}^{n} counts the number of boxes in columns of Rothe(w) (from left to right). Given α ∈ ℤ_{≥0}^{∞}, there is a unique w[α] ∈ S_{∞} such that code(w[α]) = α (up to trailing 0’s); see, e.g., [20, Proposition 2.1.2]. We will need a special tableau coming from [23, Section 4]:

The tableau T [α]: Given w[α], i_{1} < i_{2} < ⋯ < i_{a} in the first column of T [α] are given by having i_{j} be the largest descent position smaller than i_{j+1} in the permutation ws_{i_{a}}s_{i_{a−1}} ⋯ s_{i_{j+1}}. The next column of T [α] is similarly determined, starting from ws_{i_{a}} ⋯ s_{i_{1}}, etc.

An increasing tableau T of shape λ is a filling with strictly increasing rows and columns. (In fact, T [α] is an increasing tableau.) Let row(T) be the reading word of T, obtained by reading the entries of T along rows, from right to left, and from top to bottom. Let min(T) be the smallest label in T. Finally, given a reduced word a = a_{1}a_{2} … a_{m}, let EGLS(a) be the output of the Edelman–Greene correspondence (see Section 2.1).

The following result shows that E_{λ^{1},...,λ^{k}}^{α} ∈ ℤ_{≥0}. It is analogous to one on Schubert polynomials [4, Corollary 3] (which our proof uses).

Theorem 1.1. The number E_{λ^{1},...,λ^{k}}^{α} counts sequences of increasing tableaux (T_{1}, T_{2}, …, T_{k}), where

• T_{i} is of shape λ^{i};

• min T_{1} > 0, min T_{2} > d_{1}, min T_{3} > d_{2}, …, min T_{k} > d_{k−1};

• row(T_{1}) · row(T_{2}) ⋯ row(T_{k}) is a reduced word of w[α] such that

EGLS(row(T_{1}) · row(T_{2}) ⋯ row(T_{k})) = T [α].

When d_{j} = j for all j ≥ 1, Theorem 1.1 specializes to an instance of the monomial expansion formula [21, Theorem 5(1)] for κ_{α} (restated as Theorem 2.5 below). Also, when (1.1) holds, k = 1, d_{1} = t, and thus Theorem 1.1 gives (1.2).

Example 1.2. The (strict) descents of α = (1, 3, 0, 2, 2, 1) are d_{1} = 2, d_{2} = 5, and

κ_{1,3,0,2,2,1} = s_{3,2}(x_{1}, x_{2})s_{2,1,1}(x_{3}, x_{4}, x_{5}) + s_{3,2}(x_{1}, x_{2})s_{2,1}(x_{3}, x_{4}, x_{5})s_{1}(x_{6}) + s_{3,1}(x_{1}, x_{2})s_{2,2}(x_{3}, x_{4}, x_{5})s_{1}(x_{6}) + s_{3,1}(x_{1}, x_{2})s_{2,2,1}(x_{3}, x_{4}, x_{5})

exhibits the claimed non-negativity of Theorem 1.1.

Also, w[α] = 2516743 (one line notation) and

T [α] = 1 3 4 2 5 4 6 5 6 .

Thus,

E_{(3,2),(2,1,1),∅}^{(1,3,0,2,2,1)} = E_{(3,2),(2,1),(1)}^{(1,3,0,2,2,1)} = E_{(3,1),(2,2),(1)}^{(1,3,0,2,2,1)} = E_{(3,1),(2,2,1),∅}^{(1,3,0,2,2,1)} = 1

are respectively witnessed by

( \begin{matrix}1 & 3 & 4 \\ 2 & 5 \end{matrix} , 4 6 5 6 , ∅) , ( \begin{matrix}1 & 3 & 4 \\ 2 & 5 \end{matrix} , 4 6 5 , 6 ) , ( \begin{matrix}1 & 3 & 4 \\ 2 \end{matrix} , 4 5 5 6 , 6 ) , and ( \begin{matrix}1 & 3 & 4 \\ 2 \end{matrix} , 4 5 5 6 6 , ∅) .

For example, for the leftmost sequence, EGLS(43152 · 6456 · ∅) = T [α] holds. □

1.3. The Ω polynomials. A. Lascoux [11] defines Ω_{α} for α = (α_{1}, α_{2}, …) ∈ ℤ_{≥0}^{∞} by replacing π_{i} in the definition of the Key polynomials with the operator defined by

π̃_{i}(f) = ∂_{i}(x_{i}(1 − x_{i+1})f).

(These operators can also be seen to satisfy the braid relations; cf. [14, Chapter 1.4].)

The initial condition is Ω_{α} = x^{α}(= κ_{α}), if α is weakly decreasing. The Ω polynomials deform the Key polynomials. While at present there is no known geometric or representation theoretic interpretation of the Ω polynomials, as is pointed out in loc. cit., many of the known relationships between the Key and Schubert basis extend to ones between the Ω and Grothendieck basis (the latter family is formally recalled in the next subsection).

The skyline diagram of α is Skyline(α) = {(i, y) : 1 ≤ y ≤ α_{i}} ⊂ ℕ^{2}. Graphically, it is a collection of columns, the i-th column having height α_{i}. For instance,

Skyline(1, 3, 0, 2, 2, 1) = (\begin{matrix}. & + & . & . & . & . \\ . & + & . & + & + & . \\ + & + & . & + & + & + \end{matrix})

Beginning with Skyline(α), Kohnert’s rule [10] generates diagrams D by sequentially moving any + at the top of its column to the rightmost open position in its row and to its left. (The result of such a move need not be the skyline of any γ ∈ ℤ_{≥0}^{∞}.) Let x^{D} = ∏_{i} x_{i}^{d_{i}} be the column weight, where d_{i} is the number of +’s in column i of D. If the same D results from a different sequence of moves, it only counts once. Kohnert’s theorem states κ_{α} = ∑ x^{D}, where the sum is over all such D. Extending this, we introduce:

The K-Kohnert rule: Each + either moves as in Kohnert’s rule, or stays in place and moves. That is, in the latter case, we mark the original position with a “g”, and we place a + in the rightmost open position in its row and to the left of the original position. The g’s are unmovable, but a given + treats g in the same way as other +’s when deciding if it can move, and to where. Diagrams with the same occupied positions but different arrangements of +’s and g’s are counted separately.

Example 1.3. Below, we give all K-Kohnert moves one step from D:

D = (\begin{matrix}+ & . & g & + & . \\ . & + & + & + & + \end{matrix}) ↦ (\begin{matrix}+ & . & g & + & . \\ + & . & + & + & + \end{matrix}) , (\begin{matrix}+ & . & g & + & . \\ + & g & + & + & + \end{matrix}) , (\begin{matrix}+ & + & g & . & . \\ . & + & + & + & + \end{matrix}) ,

(\begin{matrix}+ & + & g & g & . \\ . & + & + & + & + \end{matrix}) , (\begin{matrix}+ & . & g & + & . \\ + & + & + & + & . \end{matrix}) , (\begin{matrix}+ & . & g & + & . \\ + & + & + & + & g \end{matrix}) .

Let

J_{α}^{(β)} = ∑ β^{#(g’s appearing in D )}x^{D}.

Conjecture 1.4. J_{α}^{(−1)} = Ω_{α}.

Conjecture 1.4 has been checked by computer, for a wide range of cases up to α being of size 12, leaving us convinced. Clearly, J_{α}^{(0)} = κ_{α}, by Kohnert’s theorem.

Example 1.5. Let α = (1, 0, 2). Then the diagrams contributing to J_{(1,0,2)} are:

Skyline(1, 0, 2) = (\begin{matrix}. & . & + \\ + & . & + \end{matrix}) , (\begin{matrix}. & + & . \\ + & . & + \end{matrix}) , (\begin{matrix}+ & . & . \\ + & . & + \end{matrix}) , (\begin{matrix}+ & . & . \\ + & + & . \end{matrix}) , (\begin{matrix}. & + & . \\ + & + & . \end{matrix});

(\begin{matrix}+ & g & . \\ + & . & + \end{matrix}) , (\begin{matrix}+ & g & . \\ + & + & . \end{matrix}) , (\begin{matrix}+ & . & . \\ + & + & g \end{matrix}) , (\begin{matrix}. & + & . \\ + & + & g \end{matrix}) , (\begin{matrix}. & + & g \\ + & . & + \end{matrix}) , (\begin{matrix}+ & . & g \\ + & . & + \end{matrix}); (\begin{matrix}+ & g & . \\ + & + & g \end{matrix}); (\begin{matrix}+ & g & g \\ + & . & + \end{matrix}) .

Thus,

J_{(1,0,2)} = (x_{1}x_{3}^{2} + x_{1}x_{2}x_{3} + x_{1}^{2}x_{3} + x_{1}^{2}x_{2} + x_{1}x_{2}^{2})

− (x_{1}^{2}x_{2}x_{3} + x_{1}^{2}x_{2}^{2} + x_{1}^{2}x_{2}x_{3} + x_{1}x_{2}^{2}x_{3} + x_{1}x_{2}x_{3}^{2} + x_{1}^{2}x_{3}^{2}) + (x_{1}^{2}x_{2}^{2}x_{3} + x_{1}^{2}x_{2}x_{3}^{2}).

The lowest degree homogeneous component of Ω_{α} is κ_{α}. Hence any f ∈ Pol is a possibly infinite linear combination of the Ω_{α}’s. Finiteness is asserted in [14, Chapter 5]. We show in Section 4.2 that the J_{α}’s also form a (finite) basis.

1.4. Grothendieck polynomials. The Grothendieck polynomial [17] is defined using the isobaric divided difference operator whose action on f ∈ Pol is given by

π_{i}(f) = ∂_{i}((1 − x_{i+1})f).

(Once again, these operators are known to satisfy the braid relations.) Declare 𝔊_{w_{0}}(X) = x_{1}^{n−1}x_{2}^{n−2} ⋯ x_{n−1} where w_{0} is the long element in S_{n}. Set 𝔊_{w}(X) = π_{i}(𝔊_{ws_{i}}) if i is an ascent of w. The Grothendieck polynomials are known to lift {s_{λ}} to Pol.

One has 𝔊_{w} = 𝔖_{w} + (higher degree terms) . We now state A. Kohnert’s conjecture [10] for 𝔖_{w}. Starting with Rothe(w), Kohnert’s rule generates diagrams D by applying the same rules as described for his rule for κ_{α}. Then 𝔖_{w} = ∑ x^{D}; the sum is over all such D.

Analogously, we define

K_{w}^{(β)} = ∑_{D} β^{#(g’s appearing in D)}x^{D}

where the sum is over all diagrams D generated by the K-Kohnert rule. For example, if w = 3142, the diagrams contributing to K_{w}^{(β)} are

Rothe(3142) = (\begin{matrix}. & . & . & . \\ . & . & . & . \\ + & . & + & . \\ + & . & . & . \end{matrix}) , (\begin{matrix}. & . & . & . \\ . & . & . & . \\ + & + & . & . \\ + & . & . & . \end{matrix}) , (\begin{matrix}. & . & . & . \\ . & . & . & . \\ + & + & g & . \\ + & . & . & . \end{matrix}) .

Hence, correspondingly, K_{3142}^{(−1)} = (x_{1}^{2}x_{3} + x_{1}^{2}x_{2}) − (x_{1}^{2}x_{2}x_{3}).

Conjecture 1.6. K_{w}^{(−1)} = 𝔊_{w}.

Note that K_{w}^{(0)} = 𝔖_{w} is precisely Kohnert’s conjecture. Conjecture 1.6 has been checked by computer for n ≤ 7, and extensively for larger n. While Kohnert’s rule for 𝔖_{w} is handy, it remains mysterious, even after [24]. Conjectures 1.4 and 1.6 represent a return to Kohnert’s conjecture (albeit after introducing a parameter β).

2. Proof of Theorem 1.1

2.1. Reduced word combinatorics. Given w ∈ S_{n}, let

a = (a_{1}, a_{2}, …, a_{ℓ(w)}) and i = (i_{1}, i_{2}, …, i_{ℓ(w)}).

In connection to [1], we say the pair (a, i) is a stable compatible pair for w if s_{a_{1}} ⋯ s_{a_{ℓ(w)}} is a reduced word for w and the following two conditions on i hold:

(cs.1) 1 ≤ i_{1} ≤ i_{2} ≤ ⋯ ≤ i_{ℓ(w)} < n; (cs.2) a_{j} < a_{j+1} ⟹ i_{j} < i_{j+1}.

We will identify w with a and the associated reduced word.

The Edelman–Greene correspondence [6] (the same basic construction is used in [17]) is a bijection

EGLS : (a, i) ↦ (T, U),

where

• T is an increasing tableau such that row(T) is a reduced word for a;

• U is a semistandard tableau whose multiset of labels contains precisely those in i, and which has the same shape as T.

EGLS (column) insertion: We insert a from left to right, starting with a_{1}. When we reach step j of this process, we initially insert a_{j} into the leftmost column (of what will be T). If there are no labels strictly larger than a_{j}, we place a_{j} at the bottom of that column. If a_{j} +t for t > 2 appears, we bump this a_{j} + t to the next column to the right, replacing it with a_{j}. The same holds if a_{j} + 1 appears but not a_{j}. Finally, if both a_{j} + 1 and a_{j} already appear, we insert a_{j} + 1 into the next column to the right. Since a is assumed to be reduced, the above enumerates all possibilities. Finally at step j a new box is created at a corner; in what will be U we place i_{j} .

Mildly abusing terminology, let EGLS(a) = T.

We will need another standard notion in the subject. Two reduced words a and a′ for the same permutation are in the same Coxeter–Knuth class if EGLS(a) = EGLS(a′) = T. This T represents the class. The equivalence relation ∼ on reduced words is defined by the symmetric and transitive closure of the relations:

(2.1)  Ai(i + 1)iB ∼ A(i + 1)i(i + 1)B,
AacbB ∼ AcabB,
AbacB ∼ AbcaB,

where a < b < c. In particular, it is true that a ∼ row(EGLS(a)).

2.2. Formulas for Schubert polynomials. A stable compatible pair (a, i) is a compatible pair for w if in addition to (cs.1) and (cs.2) the following holds:

(cs.3) i_{j} ≤ a_{j}.

Let Compatible(w) be the set of compatible sequences for w. A rule of [1] states that

(2.2)  𝔖_{w}(X) = ∑_{(a,i)∈Compatible(w)} x^{i}.

A descent of w is an index j such that w(j) > w(j + 1). Let Descents(w) be the set of descents of w. The following is [4, Corollary 3].

Theorem 2.1. Let w ∈ S_{n} and suppose that Descents(w) ⊆ {d_{1} < d_{2} < ⋯ < d_{k}}. Then

(2.3)  𝔖_{w}(X) = ∑_{λ^{1},...,λ^{k}} c_{λ^{1},...,λ^{k}}^{w}s_{λ^{1}}(X_{1}) ⋯ s_{λ^{k}}(X_{k}),

where c_{λ^{1},...,λ^{k}}^{w} counts the number of tuples of increasing tableaux (T_{1}, …, T_{k}) satisfying the following properties:

(i) T_{i} has shape λ^{i}; (ii) min T_{1} > 0, min T_{2} > d_{1}, …, min T_{k} > d_{k−1}; (iii) row(T_{1}) ⋯ row(T_{k}) is a reduced word of w.

Assume for the remainder of the proof that

(2.4)  Descents(w) ⊆ {d_{1} < d_{2} < ⋯ < d_{k}}.

Let

Tuples(w) = {[(T_{1}, U_{1}), (T_{2}, U_{2}), …, (T_{k}, U_{k})]},

where the T_{i}’s satisfy (i), (ii), and (iii) from Theorem 2.1, and each U_{i} is a semistandard tableau of shape λ^{i} using the labels d_{i−1} + 1, d_{i−1} + 2, …, d_{i} (d_{0} = 0).

2.3. “Splitting” the EGLS correspondence. Assuming (2.4) we define

                       Φ : Compatible(w) → Tuples(w).

Description of Φ (using EGLS): Uniquely split (a, i) ∈ Compatible as follows:

(2.5)  ((a^{(1)}, i^{(1)}), (a^{(2)}, i^{(2)}), …, (a^{(k)}, i^{(k)})) ,

where • a = a^{(1)} ⋯ a^{(k)} and i = i^{(1)} ⋯ i^{(k)} (“⋯ ” means concatenation);

• the entries of i^{(j)} are contained in the set {d_{j−1} + 1, d_{j−1} + 2, …, d_{j}}. Now define

Φ((a, i)) := (EGLS(a^{(1)}, i^{(1)}), …, EGLS(a^{(k)}, i^{(k)})) .

Proposition 2.2. The map Φ : Compatible(w) → Tuples(w) is well-defined and a bijection.

Proof.Φ is well-defined: The condition (i) just says that T_{j} and U_{j} have the same shape, which is true by the description of EGLS. For (ii), the splitting says that each label in i^{(j)} is strictly bigger than d_{j−1}. Now, by (cs.3), each label in a^{(j)} is strictly bigger than d_{j−1} as well. By the definition of EGLS, the set of labels appearing in T_{j} is the same as that of a^{(j)}; hence (ii) holds. Lastly, row(T_{j}) is a reduced word for a^{(j)}. Then (iii) is clear.

Φ is a bijection: Since EGLS is a bijective correspondence, clearly Φ is an injection. Consider the weight function on Compatible(w) that assigns (a, i) weight x^{i} and assigns [(T_{1}, U_{1}), …, (T_{k}, U_{k})] the weight x^{U_{1}} ⋯ x^{U_{k}}, where x^{U_{i}} is the usual monomial associated to the tableau U_{i}. Then clearly Φ is a weight-preserving map (since EGLS is similarly weight-preserving). Hence the surjectivity of Φ holds by (2.2) and Theorem 2.1. □

See [18, Section 5] for a proof of Theorem 2.1 which is close to the study of the split EGLS correspondence (the argument constructs certain crystal operators).

2.4. The tableau T [α]. Recall that w[α] ∈ S_{∞} satisfies code(w[α]) = α. Let ≺ be the pure reverse lexicographic total ordering on monomials. The Schubert polynomial 𝔖_{w[α]} has leading term x^{α} (with respect to ≺). The same is true of κ_{α} (see [21, Corollary 7]), so

(2.6)  𝔖_{w[α]} = κ_{α} + linear combination of other Key polynomials.

Given an increasing tableau U, the nil left Key K_{−}^{0}(U) is defined by [16] (cf. [21, p. 111– 114]). Let sort(α) be the partition obtained by rearranging α into weakly decreasing order. Also let content(T) be the usual content vector of a semistandard tableau T. The following is a result of A. Lascoux and M.-P. Schützenberger (cf. [21, Theorem 4]):

Theorem 2.3.

𝔖_{w}(X) = ∑ κ_{content(K_{−}^{0}(U))},

where the sum is over all increasing tableaux U of shape sort(α) with row(U) = w.

Thus, by (2.6) combined with Theorem 2.3 there exists a unique increasing tableau U[α] of shape sort(α) with row(U[α]) = w[α] and such that α = content(K_{−}^{0}(U[α])).

Let F_{w} = lim_{k→∞} 𝔖_{1^{k}×w} be the stable Schubert polynomial associated to w. This is a symmetric polynomial in infinitely many variables. So therefore one has an expansion

(2.7)  F_{w} = ∑_{λ} a_{w,λ}s_{λ},

where the a_{w,λ} ∈ ℤ_{≥0} count increasing tableaux A of shape λ with row(A) = w. We mention that (2.3) is derived from (2.7) in [4]; thereby, (2.7) may be seen as a specialization of (2.3).

In [23, Theorem 4.1], it is shown that a_{w,μ′(w)} = 1 for a certain explicitly described “maximal” μ′(w). Moreover a simple description of the witnessing tableau A[α] is given. Straightforwardly, μ′(w[α]) = sort(α). Then T [α] is precisely the witnessing tableau A[α] for a_{w[α],λ(w[α])} (after accounting for the fact that the conventions in [23] use F_{w[α]} for what we call F_{w[α]^{−1}}). We leave the details to the reader.

Finally, since the expansion of Theorem 2.3 refines (2.7) (see, e.g., [21]), we have

(2.8)  T [α] = A[α] = U[α].

So, T [α] is an increasing tableau of shape sort[α] with the properties that row(T [α]) = w[α] and content(K_{−}(T [α])) = α.

2.5. Conclusion of the proof of Theorem 1.1: From the definition of Rothe(w[α]), we deduce the following fact.

Lemma 2.4. The descents of w[α] are contained in the set of descents d_{1} < d_{2} < ⋯ < d_{k} of α.

By Lemma 2.4 combined with Theorem 2.1, we obtain

(2.9)  𝔖_{w[α]}(X) = ∑_{(a,i)} x^{i} = ∑_{λ^{1},...,λ^{k}} c_{λ^{1},...,λ^{k}}^{w[α]}s_{λ^{1}}(X_{1}) ⋯ s_{λ^{k}}(X_{k}).

We recall the following formula [21, Theorem 5].

Theorem 2.5. Fix an increasing tableau T with content(K_{−}^{0}(T)) = α. Then

κ_{α} = ∑_{(a,i)} x^{i},

where the sum is over compatible sequences (a, i) satisfying (cs.1), (cs.2), (cs.3), and EGLS(a) = T.

In view of (2.8) and the properties about T [α] stated immediately after that equation, we may set T = T [α] in Theorem 2.5 to obtain a monomial expansion formula for κ_{α} in terms of compatible pairs. Thus, our theorem statement is that κ_{α} is precisely equal to a prescribed subset of the summands of (2.9).

Thus to complete the proof, restrict Φ to those (a, i) ∈ Compatible(w[α]) such that EGLS(a) = T [α]. Consider Φ(a, i) = [(T_{1}, U_{1}), …, (T_{k}, U_{k})]. Since a^{(i)} ∼ row(T_{i}), by (2.1) we see

(2.10)  row(T_{1}) ⋯ row(T_{k}) ∼ a^{(1)} ⋯ a^{(k)} = a.

However, since we have assumed EGLS(a) = T [α], it follows that

(2.11)  EGLS(row(T_{1}) ⋯ row(T_{k})) = T [α],

The other two requirements on (T_{1}, …, T_{k}) hold since Φ is well-defined (Proposition 2.2). The desired conditions on (U_{1}, …, U_{k}) follow from the well-definedness of Φ and Lemma 2.4.

Conversely, suppose [(T_{1}, U_{1}), …, (T_{k}, U_{k})] has (T_{1}, …, T_{k}) satisfying Theorem 1.1’s conditions. Since Φ is a bijection (Proposition 2.2), we have

Φ^{−1}([(T_{1}, U_{1}), …, (T_{k}, U_{k})]) = (a, i) ∈ Compatible(w[α]).

Also, by (2.10), a ∼ row(T_{1}) ⋯ row(T_{k}). Now, we assumed that (2.11) holds. Hence, EGLS(a) = T [α] as desired. □

3. Additional remarks

3.1. Comments on Theorem 1.1. Since the κ_{α}’s specialize non-symmetric Macdonald polynomials (see, e.g., [8, Section 5.3]), can one extend Theorem 1.1 in that direction?

Theorem 1.1 implies that the Key module of [21, Section 5] should have an action of GL(d_{1}) × GL(d_{2} − d_{1}) × ⋯ × GL(d_{k} − d_{k−1}) such that the character is κ_{α}.

V. Reiner suggests a variation of Theorem 1.1 using plactic theory. The derivation should be similar, using formulas from [22]. However we are missing the analogue of [4, Corollary 4]; cf. [9, Sections 7, 8]. Theorem 1.1 naturally generalizes to Grothendieck polynomials, using [3, 2]; details may appear elsewhere.

3.2. J_{α}’s form a (finite) basis of Pol. Clearly, J_{α}(X) = x^{α} + ∑_{β≺α} c_{β}x^{β}. One decomposes f ∈ Pol into a possibly infinite sum of J_{α}’s,

(3.1)  f = ∑_{α} g_{α}J_{α}.

That is, find the ≺ largest monomial x^{θ_{0}} appearing in f^{(0)} := f (say with coefficient c_{θ_{0}}) and let f^{(1)} := f − c_{θ_{0}} · J_{θ_{t}}. Thus f^{(1)} only contains monomials strictly smaller in the ≺ ordering. Now repeat, defining f^{(t+1)} := f^{(t)} − c_{θ_{t}}J_{θ_{t}} where x^{θ_{t}} is the ≺-largest monomial appearing in f^{(t)}, etc. Since J_{α} is not homogeneous, each step t potentially introduces ≺-smaller monomials but of higher degree. However, we claim the following.

Proposition 3.1. The expansion (3.1)is finite.

Proof.By the K-Kohnert rule, each β that appears in J_{α} is contained in the smallest rectangle R that contains α. So the above procedure only involves the finitely many diagrams contained in R for one of the finitely many initial α ∈ ℤ_{≥0}^{∞} such that x^{α} is in f. □

3.3. More on the interplay of Grothendieck and the Ω polynomials. M. Shimozono has suggested that the expansion of 𝔊_{w} in Ω_{α}’s should alternate in sign, by degree. An explicit rule exhibiting this has been conjectured by V. Reiner and the second author.

Acknowledgements

AY thanks Jim Haglund, Alain Lascoux, Vic Reiner and Mark Shimozono for inspiring discussions and correspondence. AY also thanks Oliver Pechenik and Luis Serrano for helpful comments. We thank the anonymous referee for helpful suggestions concerning the presentation. This project was initiated during a summer undergraduate research experience at UIUC supported by NSF grant DMS 0901331. AY also was supported by NSF grant DMS 1201595 and a Helen Corley Petit endowment at UIUC.

References

[1] S. Billey, W. Jockush and R. Stanley, Some Combinatorial Properties of Schubert Polynomials, J. Algebraic Combin. 2 (1993), 345–374.

[2] A. Buch, A. Kresch, M. Shimozono, H. Tamvakis and A. Yong, Stable Grothendieck polynomials and Ktheoretic factor sequences, Math. Ann. 340 (2008), 359–382.

[3] A. S. Buch, A. Kresch, H. Tamvakis and A. Yong, Grothendieck polynomials and quiver formulas, Amer. J. Math. 127 (2005), 551–567.

[4] , Schubert polynomials and quiver formulas, Duke Math J. 122 (2004), 125–143.

[5] M. Demazure, Une nouvelle formule des caractères, Bull. Sci. Math. 98 (1974), 163–172.

[6] P. Edelman and C. Greene, Balanced tableaux, Adv. Math. 63 (1987), 42–99.

[7] S. Fomin and A. N. Kirillov, Grothendieck polynomials and the Yang–Baxter equation, Proc. 6th Intern. Conf. on Formal Power Series and Algebraic Combinatorics, DIMACS, 1994, pp. 183–190.

[8] J. Haglund, M. Haiman and N. Loehr, A combinatorial formula for non-symmetric Macdonald polynomials, Amer. J. Math. 103 (2008), 359–383.

[9] A. Knutson, E. Miller and M. Shimozono, Four positive formulae for type A quiver polynomials, Invent. Math. 166 (2006), 229–325.

[10] A. Kohnert, Weintrauben, Polynome, Tableaux, Bayreuth. Math. Schriften 38 (1990), 1–97.

[11] A. Lascoux, Transition on Grothendieck polynomials, Physics and Combinatorics, 2000 (Nagoya), World Scientific Publishing, River Edge, 2001, pp. 164–179.

[12] , Symmetric Functions and Combinatorial Operators on Polynomials, CBMS Regional Conference Series in Mathematics, American Mathematical Society, Providence, R.I., 2003. xii+268 pp.

[13] , Schubert & Grothendieck: un bilan bidécennal, Sém. Lothar. Combin. 50 (2003/04), Art. B50i, 32 pp.

[14]  , Polynomials, 2013. http://phalanstere.univ-mlv.fr/~al/ARTICLES/CoursYGKM.pdf.

[15] A. Lascoux and M.-P. Schützenberger, Keys and standard bases, in “Tableaux and Invariant Theory”, IMA Volumes in Math and its Applications (D. Stanton, Ed.), Vol. 19, Southend on Sea, UK, 1990, pp. 125–144.

[16] , Tableaux and non-commutative Schubert polynomials, Funct. Anal. Appl. 23 (1989), 63–64.

[17] , 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), 629–633.

[18] C. Lenart, A unified approach to combinatorial formulas for Schubert polynomials, J. Algebraic Combin. 20 (2004), 263–299.

[19] C. Lenart, S. Robinson and F. Sottile, Grothendieck polynomials via permutation patterns and chains in the Bruhat order, Amer. J. Math. 128 (2006), 805–848.

[20] L. Manivel, Symmetric functions, Schubert polynomials and degeneracy loci, American Mathematical Society, Providence, R.I., 2001.

[21] V. Reiner and M. Shimozono, Key polynomials and a flagged Littlewood–Richardson rule, J. Combin. Theory. Ser. A. 70 (1995), 107–143.

[22] , Plactification, J. Algebraic Combin. 4 (1995), 331–351.

[23] R. P. Stanley, On the number of reduced decompositions of elements of Coxeter groups, Europ. J. Combin. 5 (1984), 359–372.

[24] R. Winkel, Diagram rules for the generation of Schubert polynomials, J. Combin. Theory Ser. A 86 (1999), 14–48.

Department of Industrial Engineering and Management Sciences, Northwestern University, Evanston, IL 60208

  E-mail address: ColleenRoss2012@u.northwestern.edu

Department of Mathematics, University of Illinois at Urbana-Champaign, Urbana, IL 61801

  E-mail address: ayong@illinois.edu