The “Young” and “reverse” dichotomy of polynomials
Abstract.
A “flip-and-reversal” involution arising in the study of quasisymmetric Schur functions provides a passage between what we term “Young” and “reverse” variants of bases of polynomials or quasisymmetric functions. Building on this perspective, which has found recent application in the study of -analogues of combinatorial Hopf algebras and generalizations of dual immaculate functions, we develop and explore Young analogues of well-known bases for polynomials. We prove several combinatorial formulas for the Young analogue of the key polynomials, show that they form the generating functions for left keys, and provide a representation-theoretic interpretation of Young key polynomials as traces on certain modules. We also give combinatorial formulas for the Young analogues of Schubert polynomials, including their crystal graph structure. We moreover determine the intersections of (reverse) bases and their Young counterparts, further clarifying their relationships to one another.
Key words and phrases:
Key polynomials, quasisymmetric Schur polynomials, Young quasisymmetric Schur polynomials2010 Mathematics Subject Classification:
Primary 05E051. Introduction
Tableau models provide an indispensable framework for giving explicit positive combinatorial formulas for important families of polynomials and their relationships to one another. The celebrated Schur polynomials, which form a basis for the ring of symmetric polynomials in variables, are famously realized as the weight generating functions of semistandard Young tableaux: tableaux of partition shape whose entries weakly increase from left to right in each row and strictly increase from bottom to top in each column. In fact, this definition may be reversed and Schur polynomials may alternatively be realized as the weight generating functions of semistandard reverse tableaux, whose entries weakly decrease from left to right along rows rows and strictly decrease from bottom to top in each column.
is a subring of the ring of quasisymmetric polynomials. Basis elements of are indexed by compositions (sequences of positive integers) with at most parts. The semistandard reverse tableau model used in naturally extends to produce tableaux of composition shape. The diagram of a composition , written in French notation, is the diagram consisting of left-justified rows of boxes whose row from the bottom contains boxes. A tableau (of shape ) is a filling of with positive integers. A reverse composition tableau is a tableau with entries no larger than , so that entries weakly decrease from left to right along rows.
Imposing different choices of further restrictions on the entries produces collections of reverse composition tableaux whose weight generating functions are, for example, the quasisymmetric Schur polynomial [HLMvW11], the fundamental quasisymmetric polynomial [Ges84], or the monomial quasisymmetric polynomial [Ges84] corresponding to . On the other hand, certain other bases of are naturally described instead by restrictions of Young composition tableaux, where entries weakly increase from left to right along rows. Examples include the dual immaculate polynomials [BBS+14], the Young quasisymmetric Schur polynomials [LMvW13], and the extended Schur polynomials [AS19].
Extending further, reverse fillings provide a combinatorial framework that naturally generalizes the model of reverse composition tableaux to the ring of polynomials in variables. Basis elements of are indexed by weak compositions: sequences of nonnegative integers. The diagram of a weak composition is the diagram in having boxes in row , left-justified. A filling (of shape ) is an assignment of positive integers, no larger than , to the boxes of . A reverse filling is a filling in which entries weakly decrease from left to right along each row.
By imposing further restrictions on the entries, one can obtain a set of reverse fillings of whose weight generating function is, for example, the key polynomial [RS95], the quasi-key polynomial [AS18b], the Demazure atom [Mas09], or the fundamental slide polynomial [Sea20] corresponding to . At present, the majority of well-studied bases for are described in terms of reverse fillings, i.e., with decreasing rows.
As noted earlier, Schur polynomials may be realized in terms of either semistandard Young tableaux or semistandard reverse tableaux. This coincidence can be understood in terms of an involution on tableaux whose entries are at most , namely, replacing each entry with . This bijectively maps semistandard Young tableaux to semistandard reverse tableaux and vice versa. While this map is weight-reversing rather than preserving, the fact that Schur polynomials are symmetric means that the multiset of weights of semistandard Young tableaux is equal to the multiset of weights of semistandard reverse tableaux.
This map inspires a closely-related flip-and-reverse map on composition tableaux, defined by reversing the order of the rows (reverse) and replacing every entry with (flip). This weight-reversing map changes decreasing rows to increasing rows and vice versa. As is the case for Schur polynomials, the flip-and-reverse map preserves both the monomial and fundamental bases of . However, bases of are not preserved in general. In particular, the reverse composition tableaux that generate the quasisymmetric Schur polynomial corresponding to are mapped to precisely the Young composition tableaux that generate the Young quasisymmetric Schur polynomial corresponding to , the composition obtained by reading in reverse. Typically a Young quasisymmetric Schur polynomial is not also a quasisymmetric Schur polynomial; we characterize their coincidences in Section 2.
The flip-and-reverse map extends naturally to fillings of weak composition diagrams, giving two parallel constructions of bases for , one (reverse) defined by reverse fillings and one (Young) defined by Young fillings, i.e., fillings in which entries increase from left to right along rows. The fillings obtained by applying the flip-and-reverse map to those reverse fillings that generate a particular basis of generate a Young analogue of that basis.
Young analogues of the quasi-key and fundamental slide bases and a reverse analogue of the dual immaculate functions were introduced in [MS20] and properties of these bases were developed including a number of useful applications. In particular, these analogues were used to extend a result of [AHM18] on positive expansions of dual immaculate functions to the full polynomial ring, to establish properties of stable limits of these polynomials and their expansions, and to uncover a previously-unknown connection between dual immaculate functions and Demazure atoms. These results necessitated repeated passage between reverse and Young analogues. In particular, reverse analogues were needed to study stable limits for a polynomial ring analogue of the dual immaculate functions, whereas Young analogues were needed to connect to established results in from [AHM18]. In a similar vein, Young analogues of pre-existing reverse bases of were applied in the study of -analogues of combinatorial Hopf algebras [Li15] and skew variants of quasisymmetric bases [MN15] to take advantage of classical combinatorics in concerning Schur functions and Young tableaux. This type of relabelling is also used in [PR21] (there called “shifting”) to simplify arguments relating to the equivariant cohomology of Springer fibers for .
We are motivated by the utility of the flip-and-reverse perspective to explore and develop further Young analogues of bases of and establish structural results. The Young analogue of the key polynomials is of particular interest and forms a primary focus. In fact, this Young basis has already found application: this variant of the key polynomials is used in [HRS18] to obtain the Hilbert series of a generalization of the coinvariant algebra. In Section 3 we establish a connection with left and right keys of semistandard Young tableaux, proving in Theorem 3.18 that the Young key polynomials are in fact a generating function for semistandard Young tableaux whose left key is greater than a fixed key. We establish an analogous result for the Young analogue of the Demazure atom basis. We also provide a representation-theoretic construction for the Young key polynomials as traces of the action of a diagonal matrix on certain modules. Moreover, in addition to the Young skyline filling model arising from the flip-and-reverse map, we detail several other constructions and interpretations of the Young key polynomials and Young atoms, including divided difference operators, crystal graphs, and compatible sequences.
In Section 4 we provide a new formula for the expansion of a key polynomial into fundamental slide polynomials as well as a new combinatorial construction of the fundamental particle basis for polynomials [Sea20] in terms of flag-compatible sequences. We describe Young analogues for additional families of polynomials, classify which of these Young bases expand positively in one another, and explain different behaviour exhibited by Young and reverse versions including stable limits and embedding into larger polynomial rings. We also completely determine the intersection of the Young and reverse versions of all bases we consider. As a result, we find that when the Young and reverse versions of such a basis of extend a given basis of or , the intersection of the Young and reverse basis of is exactly the original basis. For example, we show that the intersection of the Young key polynomials and the key polynomials is exactly the Schur polynomials, and the intersection of the fundamental slide and Young fundamental slide polynomials is exactly the fundamental quasisymmetric polynomials.
Finally in Section 5, we introduce a Young analogue of the famous Schubert polynomials, extending this perspective further. We describe how to generate the Young Schubert polynomials using pipe dreams and divided difference operators and detail how Young Schubert polynomials expand into Young key polynomials. Interestingly, unlike the case for Young analogues of other polynomial bases, there is no basis of consisting of Young Schubert polynomials. We also describe the crystal graph structure for Young Schubert polynomials (analogous to the crystal graph structure for Young key polynomials), as Demazure subcrystals of the crystal on reduced factorizations introduced in [MS16], using methods that were developed on a flipped and reversed version of this crystal in [AS18a].
2. Background
Throughout the following, we denote permutations in one-line notation and allow the transposition to act on the right by swapping the entries in the th and th positions. For a weak composition , let denote the partition obtained by recording the entries of in weakly decreasing order. We refer to assignments of integers to diagrams of compositions as tableaux and assignments of integers to diagrams of weak compositions as fillings. For any tableau or filling , the weight denotes the weak composition whose th entry is the number of occurrences of in .
2.1. Quasisymmetric polynomials
Let be a composition with at most parts. The fundamental quasisymmetric polynomial was originally introduced through the enumeration of -partitions [Ges84]. Although there are several different ways to generate the fundamental quasisymmetric polynomials, we describe them as generating functions for certain tableau-like objects which we call fundamental reverse composition tableaux to align with other definitions to follow. Fundamental reverse composition tableaux are those reverse composition tableaux (i.e., entries decrease from left to right in each row) satisfying the additional condition that if , then every entry in row is strictly smaller than every entry in row . It is straightforward to check that this definition is equivalent to the definition of the fundamental quasisymmetric polynomials as generating functions of ribbon tableaux (see for example [Hua16, Section 4.1]).
In this way, is the sum of all monomials , where ranges over fundamental reverse composition tableaux of shape and largest entry at most .
Example 2.1.
We have , as witnessed by the following fundamental reverse composition tableaux.
The monomial quasisymmetric polynomial is the generating function of what we call monomial reverse composition tableaux, which are those fundamental reverse composition tableaux in which all entries in the same row are equal.
Example 2.2.
We have , as witnessed by the following monomial reverse composition tableaux.
One may also define fundamental Young composition tableaux and monomial Young composition tableaux, by replacing the decreasing row condition with the corresponding increasing row condition in the definitions of fundamental (respectively, monomial) reverse composition tableaux. One could then define Young fundamental quasisymmetric polynomials and Young monomial quasisymmetric polynomials to be the generating functions of fundamental (respectively, monomial) Young composition tableaux. In this case, however, the polynomials remain the same.
Proposition 2.3.
The generating function of the fundamental Young composition tableaux of shape is and the generating function of the monomial Young composition tableaux of shape is .
Proof.
By definition, the monomial reverse composition tableaux are exactly the monomial Young composition tableaux. Since every entry in any row of a fundamental reverse composition tableaux is strictly smaller than any entry in the row above, reversing the entries of every row is a weight-preserving bijection between fundamental reverse composition tableaux and fundamental Young composition tableaux of the same shape. ∎
We turn our attention to the quasisymmetric Schur polynomials and the Young quasisymmetric Schur polynomials , where we will see a distinction between the reverse and the Young models. To define quasisymmetric Schur polynomials, we first define triples in reverse composition tableaux. These are collections of three boxes in with two adjacent in a row and either (Type A) the third box above the right box with the lower row weakly longer, or (Type B) the third box below the left box with the higher row strictly longer. A triple of either type is said to be an inversion triple if it is not the case that .
Define the semistandard reverse composition tableaux for to be the fillings of satisfying the following conditions.
-
(1)
Entries in each row weakly decrease from left to right.
-
(2)
Entries strictly increase from bottom to top in the first column.
-
(3)
All type A and type B triples are inversion triples.
Then is the generating function of [HLMvW11].
Example 2.4.
We have , as witnessed by the semistandard reverse composition tableaux in Figure 2.
A Young triple is a collection of three boxes with two adjacent in a row such that either (Type I) the third box is below the right box and the higher row is weakly longer, or (Type II) the third box is above the left box and the lower row is strictly longer (Figure 3). A Young triple of either type is said to be a Young inversion triple if it is not the case that .
Define the Young semistandard reverse composition tableaux for to be the fillings of satisfying the following conditions.
-
(1)
Entries in each row weakly increase from left to right.
-
(2)
Entries strictly increase from bottom to top in the first column.
-
(3)
All type I and type II Young triples are Young inversion triples.
Then the Young quasisymmetric Schur polynomial is the generating function of [LMvW13].
Remark 2.5.
Young quasisymmetric Schur polynomials are most often defined in terms of a single triple condition; e.g [LMvW13], [AHM18]. While this is more compact, it does not extend appropriately to define a Young analogue of key polynomials. The proof that these definitions are equivalent is analogous to the corresponding proof for reverse composition tableaux given in [HLMvW11].
Example 2.6.
We have , as witnessed by the semistandard Young composition tableaux in Figure 4.
Notice that ; indeed, they have a different number of terms. However, quasisymmetric Schur and Young quasisymmetric Schur polynomials are related by the following formula.
Proposition 2.7.
[LMvW13] Let be a composition with at most parts. Then
Remark 2.8.
As mentioned in the introduction, the flip-and-reverse map on composition tableaux which reverses the order of the rows and exchanges entries is a weight-reversing bijection between and , implying Proposition 2.7. In particular, reversing the order of the rows ensures the increasing first column condition is preserved.
To illustrate this, we compute the Young quasisymmetric Schur polynomial ; compare this to the computation of in Example 2.4.
Example 2.9.
We have , as witnessed by the semistandard Young composition tableaux in Figure 5.
Notice this involution preserves monomial and fundamental quasisymmetric polynomials: and .
Proposition 2.10.
For example, , whereas
A remarkable property of the quasisymmetric Schur and Young quasisymmetric Schur polynomials is that they both positively refine Schur polynomials:
Proposition 2.11.
[LMvW13]
Remark 2.12.
As noted in the introduction, Schur polynomials may be described in terms of either decreasing or increasing semistandard tableaux. Therefore Schur polynomials and “Young Schur polynomials” are the same (provided we consider a partition and its reversal to be the same), so from this perspective it makes sense that Schur polynomials expand positively into both the quasisymmetric Schur and Young quasisymmetric Schur bases. Similarly, the fact that both quasisymmetric Schur and Young quasisymmetric Schur polynomials expand positively in fundamental quasisymmetric polynomials (Proposition 2.10) makes sense due to the fact that fundamental quasisymmetric polynomials may also be described in terms of either increasing or decreasing tableaux (Proposition 2.3), and thus are the same as “Young fundamental quasisymmetric polynomials”.
Typically a Young quasisymmetric Schur polynomial is not equal to any quasisymmetric Schur polynomial. However, we can classify their coincidences. We delay the proof to the appendix.
Theorem 2.13.
if and only if and either has all parts the same, or all parts of are or , or and consecutive parts of differ by at most .
2.2. Key polynomials and Demazure atoms
We now shift our attention to the ring of all polynomials in variables. This ring possesses a variety of bases important in geometry and representation theory. A principal example is the basis of key polynomials, which are characters of (type A) Demazure modules [Dem74, LS90, RS95] and which also arise as specializations of nonsymmetric Macdonald polynomials. Closely related is the basis of Demazure atoms, originally introduced as standard bases in [LS90]. Demazure atoms were shown in [Mas09] to also be a specialization of nonsymmetric Macdonald polynomials. They are equal to the smallest non-intersecting pieces of type Demazure characters and can be obtained through a truncated application of divided difference operators. Intuitively, one can build the Demazure atoms by starting with a monomial and partially symmetrizing, keeping only the monomials not appearing in the previous iteration of this process.
2.2.1. Semi-skyline fillings
Both key polynomials and Demazure atoms are defined in terms of reverse fillings that are often referred to as semi-skyline fillings. To define the key polynomial corresponding to a weak composition of length , first note that the definition of type A and B triples extends verbatim from composition diagrams to weak composition diagrams. We need to include a basement column, an extra th column in the diagram: for our purposes the basement entry of row is . Basement entries do not contribute to the weight of a filling. Define the key fillings for to be the fillings of (note the reversal) satisfying the following conditions.
-
(1)
Entries in each row, including basement entries, weakly decrease from left to right.
-
(2)
Entries do not repeat in any column.
-
(3)
All type A and type B triples, including triples containing basement entries, are inversion triples.
We use the following as definitional for key polynomials.
Theorem 2.14.
For example, we have , which is computed using the elements of shown in Figure 6 below.
The definition of the Demazure atoms in terms of semi-skyline fillings comes from specializing the diagram fillings used to generate the nonsymmetric Macdonald polynomials [HHL08]. Define the atom fillings for to be the fillings of (no basement) satisfying the following conditions.
-
(1)
Entries weakly decrease from left to right in each row.
-
(2)
Entries do not repeat in any column.
-
(3)
The first entry of each row is equal to its row index.
-
(4)
All type A and type B triples are inversion triples.
We use the following as definitional for Demazure atoms.
Theorem 2.15.
[Mas09] Let be a weak composition of length . Then
2.2.2. Left and right keys
The eponymous formula for the key polynomial is given in terms of right keys. A semistandard Young tableau (or ) is a tableau of partition shape such that entries weakly increase along rows and strictly increase up columns. For a partition , let denote the set of all of shape , and the subset of whose entries are at most . A semistandard Young tableau is a key if the entries appearing in the th column of are a subset of the entries appearing in the column of , for all . For a weak composition , define to be the unique key of weight . For any semistandard Young tableau , there are two keys of the same shape as associated to , called the right key of , denoted , and the left key of , denoted
We now describe procedures for computing right and left keys, which will be illustrated in Example 2.17 below. There are several different methods for computing keys (see, for example [Mas09], [Wil13]) but we use the classical method presented in [RS95] as it involves several tools we will need later. Two words and in are said to be Knuth-equivalent, written , if one can be obtained from the other by a series of the following local moves:
for words and and letters .
Define the column word factorization of a word to be the decomposition of into subwords by starting a new subword between every weak ascent. Then the column form of (denoted ) is the composition whose parts are the lengths of the subwords appearing in the column word factorization. Let be the shape of the obtained when Schensted insertion (see, e.g., [Ful97, Sag13, Sta99]) is applied to . The word is said to be column-frank if is a rearrangement of the nonzero parts of , where denotes the conjugate shape of obtained by reflecting the diagram of across the line . Let . Then the right key (resp. left key) of is the key of shape whose column is equal to the last (resp. first) subword in any column-frank word which is Knuth equivalent to the column word of (obtained by reading the entries of down columns from left to right) and whose last (resp. first) subword has length .
Notice the difference in the construction of left and right keys. The weight of the left key is usually not a reversal of the weight of the right key; the subtle connection between left and right keys is explored in Section 3.3, wherein we also define polynomials naturally associated to left keys.
Theorem 2.16.
where if each entry of is weakly smaller than the corresponding entry of .
Example 2.17.
Let . Then , which is a tableau of shape . The nine tableaux whose right keys are smaller than or equal to are
To illustrate the process of finding right (and left) keys, let be the last tableau in the list above. Then . The words that are Knuth-equivalent to (listed with vertical bars indicating the column word factorizations) are . The column form of the first three words is a rearrangement of , the shape of , so these three words are column-frank. The fourth is not column-frank so we ignore it. Looking at the rightmost subword in each column-frank word, the first of these words tells us that the column of of length consists of a single , and the second (or third) word tells us that the columns of of length each contain a and a .
Thus . Similarly, via leftmost subwords, we obtain .
One may also use right keys to define the Demazure atoms. Given a weak composition of length , the Demazure atom can also be given by
| (2.1) |
From this construction and Theorem 2.16, it is apparent that key polynomials expand positively in Demazure atoms. In particular,
| (2.2) |
where if and only if and the permutation such that is less than or equal to the permutation such that in the Bruhat order.
2.2.3. Divided differences and crystal graphs
Key polynomials can be defined in terms of divided difference operators. Given a positive integer , where , define an operator on by
where exchanges and . Now define another operator on by
For a permutation , define , where is any reduced word for . (This definition is independent of the choice of reduced word because the satisfy the commutation and braid relations for the symmetric group.) Recall that is the rearrangement of the entries of into decreasing order. For a weak composition let be the minimal length permutation that sends to acting on the right. Then the key polynomial is given by
Example 2.18.
Let . Then the minimal length permutation taking to is . We compute
Demazure atoms can also be described in terms of divided difference operators. In particular, let . Then (see [Mas09])
The action of the divided difference operators can be realised in terms of Demazure crystals. A crystal graph is a directed and colored graph whose edges are defined by Kashiwara operators [Kas91, Kas93, Kas95] and . See [HK02] for a detailed introduction to the theory of quantum groups and crystal bases and [BS17] for a more combinatorial exploration of crystals.
For a partition , the type highest weight crystal of highest weight has vertices indexed by . The character of is
which is equal to the Schur polynomial , reflecting the fact that Schur polynomials are characters for irreducible highest weight modules for . See Figure 7 below for when , in which the arrows index the Kashiwara operators and . Precise definitions of the can be found in e.g. [BS17]; in particular we note that if there is no -arrow emanating from vertex , and the are defined by if , and otherwise.
A Demazure crystal is a subset of whose character is a key polynomial [Lit95, Kas93], obtained by a truncated action of the Kashiwara operators. Specifically, given a subset of , define operators for by
Given a permutation with reduced word , define
where is the highest weight element in , i.e., for all . If and in , then the crystal operator is also defined in . The character of a Demazure crystal is defined as
which is equal to when is of shortest length such that [Lit95, Kas93]. The repeated actions of the starting with precisely mirrors the repeated action of the divided difference operators starting with the monomial .
Example 2.19.
Let . Then the shortest length such that is . Therefore, the crystal graph for is the subgraph of consisting of all vertices that can be obtained from the highest weight by first applying a sequence of ’s and then a sequence of ’s. In Figure 7, these are the tableaux of weight , , , (the leftmost such) and . Hence .
2.2.4. Compatible Sequences
Key polynomials can also be constructed using compatible sequences as follows. Let be a word in the alphabet . A word is -compatible if
-
(1)
,
-
(2)
whenever for all , and
-
(3)
for all (flag condition).
Theorem 2.20.
[RS95] Let be a weak composition of length . Then
where is the weak composition whose entry counts the incidences of in .
Example 2.21.
Let . We have , and . The set of words Knuth-equivalent to is . Reversing these gives the set We compute the set of compatible sequences for each of these:
| Word | Compatible sequences |
|---|---|
| 22323 | 11223 |
| 22233 | 22233 12233 11233 11133 11123 11122 |
| 23223 | 12223 |
| 23232 | |
| 22332 | 11222 |
Observe there are compatible sequences, each having the weight of a monomial of . In Proposition 4.1, we interpret the fundamental slide expansion of a key polynomial in terms of Knuth equivalence classes.
3. Young key polynomials
We now introduce the Young key polynomial basis for polynomials. This basis has proved useful in computing the Hilbert series of a generalization of the coinvariant algebra, specifically, in constructing a Gröbner basis for the ideal [HRS18]. However, the combinatorial and representation-theoretic properties of the Young key polynomials have not, to our knowledge, been explored previously, nor has the connection to the overall flip-and-reverse perspective. We begin by providing a combinatorial description of the Young key polynomial basis analogous to that of the Young version of the quasisymmetric Schur polynomials.
Note that the definition of Young triples extends verbatim to weak composition diagrams. As in the definition of key polynomials, we append a basement column to diagrams. Given a weak composition of length , define the Young key fillings for to be the fillings of (note the reversal) with entries from satisfying the following conditions.
-
(1)
Entries in each row, including basement entries, weakly increase from left to right.
-
(2)
Entries do not repeat in any column.
-
(3)
All type I and type II Young triples, including triples using basement entries, are Young inversion triples.
Define the Young key polynomial by
where only the non-basement entries contribute to the weight.
For example, we have , which is computed by the elements of shown in Figure 9.
Note that the definition immediately implies that
| (3.1) |
Proposition 3.1.
The Young key polynomials are a basis for , containing the Schur polynomials. In particular, if is decreasing then
where is with trailing zeros removed.
Proof.
The Young key polynomials are equinumerous with the key polynomials. Any polynomial can be expressed as a linear combination of key polynomials (since key polynomials are a basis of ), and thus as a linear combination of Young key polynomials by (3.1). Hence the Young key polynomials are a basis of .
In this way, both the key and Young key polynomials extend the Schur polynomials to . This is in fact their only coincidence.
Theorem 3.2.
The polynomials that are both key polynomials and Young key polynomials are exactly the Schur polynomials.
Proof.
Suppose is a Schur polynomial in variables. Then
where (respectively, ) denotes with zeros prepended (respectively, appended).
For the converse, note that for any weak composition , the key polynomial has the monomial as a term; this follows from the divided difference definition. But the only Young key polynomial containing as a term is itself, which is a Schur polynomial. So if is not a Schur polynomial it cannot be equal to any Young key polynomial. ∎
We also define a Young analogue of the Demazure atoms. Let be a weak composition of length . Define the Young atom fillings for to be the fillings of (no basement) with entries from satisfying the following conditions.
-
(1)
Entries weakly increase from left to right in each row.
-
(2)
Entries do not repeat in any column.
-
(3)
All type I and type II Young triples are Young inversion triples.
-
(4)
The first entry of each row is equal to its row index.
Define the Young atom by
The definition immediately implies that Similar to Proposition 3.1, the Young atoms form a basis of . We can establish the coincidences between Demazure atoms and Young atoms, as we did in Theorem 3.2 for keys and Young keys. Note the condition for coincidence is less restrictive than that for coincidence of quasisymmetric Schur and Young quasisymmetric Schur polynomials (Theorem 2.13), due to elements of and necessarily having identical first column.
Theorem 3.3.
The polynomials that are both Demazure atoms and Young atoms are precisely the such that for all .
Proof.
First we show that if then . Suppose , where is the largest part of . Then since entries cannot repeat in any column for either or , has terms where some has degree , but cannot have any such term. Hence if , the longest row(s) in and must have the same length. By a similar argument, the next-longest rows must then have the same length, etc. Thus if , then must be a rearrangement of .
Now suppose rearranges . Let be such that all entries in the th row (for each ) are equal to , and suppose there exists with the same weight as . By definition, the first entry in each row of is . Because the rows of rearrange those of , the number of boxes in each column of is the same as that for each column of . It follows that the set of entries in each column of must be the same as that in the corresponding column of , since has instances of each entry , and entries cannot repeat in any column of or .
Now consider the entries in the second column of , which are a subset of the entries in the first column for both and . None of these entries can go in a row above the row that contains that entry in the first column, else the two copies of that entry must violate one of the triple conditions. Nor can they go in a row below, since entries must decrease along each row. So each entry must go immediately adjacent to the same entry in the first column of . Continuing thus, we obtain , so in particular .
Now suppose for some . Let be such that all entries in each row are , and let be obtained by changing the rightmost in to . Since , this new is not in the first column, and is at least two columns to the right of any other , so no properties are affected by this change and . But there is no with weight equal to : in rows and above, entries in must agree with entries in , and then there is nowhere the new could be placed in . Hence . A similar argument shows that if , then .
Conversely, it is straightforward to observe that if for all , then both and are equal to the single monomial . ∎
3.1. Compatible sequences
The Young key polynomials may also be described in terms of compatible sequences. For a word in define the flip of to be the word in obtained by replacing each entry with . Also define the flip-reverse of , denoted , to be the word , or equivalently .
Example 3.4.
If and , then and .
Let be an . Define the right-to-left column reading word to be the word obtained by reading the entries in each column of from top to bottom starting with the rightmost column and moving from right to left.
Lemma 3.5.
Let be a weak composition. Then .
Proof.
First of all, and have the same shape. To see this, note that the height of the column of is equal to the number of entries in such that . This number is the same for and .
This also shows that for any given column, the entries of that column in are the flips of the entries of that column in . Hence when the word for is reversed, the column breaks line up and the word in each column is the flip-reverse of the word in that column of . The statement follows. ∎
Example 3.6.
Let . We have
Here is and is , which is indeed equal to (column-breaks included for emphasis).
The following lemma is fairly well-known [Ful97, Appendix A.1]; we include a proof here for completeness and to illustrate the flip-and-reverse procedure.
Lemma 3.7.
Let be words in . Then if and only if .
Proof.
It is enough to show this for the case that and are related by a single Knuth move. For a letter in , let denote . Suppose contains the sequence where . Then one may perform a Knuth move to obtain . In we have where . Then one may perform a Knuth move to obtain the word , which is indeed . Now suppose contains the sequence where . Then one may perform a Knuth move to obtain . In we have where . Then one may perform a Knuth move to obtain the word , which is indeed .
Therefore, whenever . The converse direction is immediate from the fact that is an involution. ∎
Proposition 3.8.
Let be a weak composition. Then is Knuth-equivalent to .
Proof.
It suffices to show that the word inserts to .
Suppose is a key. Let be a word that contains the entries in the leftmost column of and let be the key obtained by removing the leftmost column of . We will show that inserting the entries of into in order from largest to smallest yields another key, namely with the column whose entries are the entries of adjoined on the left. This is the key and the conclusion then follows by induction, the base case where is empty being trivial.
We will establish that insertion of the th entry of causes (a copy of) the th entry of to be bumped from the first into the second row, the nd entry of to be bumped from the 2nd to the 3rd row, etc, culminating in the first entry of arriving at the end of the th row. This is clearly true for , as the largest entry of is weakly larger than any entry of (due to the key condition) so it is inserted at the end of the first row. Suppose this is true for all entries up to the th entry of . Now, when the th entry of is inserted, it bumps (a copy of) the th entry of from row , since there is no entry in the tableau such that by the key condition. Then the th entry of must bump (a copy of) the nd entry of (which is in row by the inductive hypothesis), since again there is no entry in the tableau such that by the key condition. Continuing thus, is eventually bumped into row , and comes to rest at the end of row since it is weakly larger than any other entry in the tableau.
Hence the insertion process results in a new entry in each row . There is a unique such semistandard Young tableau, and by the key condition each entry (or a copy of this entry) must appear as the first entry of row for every . Therefore the result is with the column determined by appended, as required. ∎
We now give a formula for Young key polynomials in terms of compatible sequences.
Theorem 3.9.
Let be a weak composition of length . Then
Proof.
The set of words Knuth-equivalent to is equal to the set of words Knuth-equivalent to by Proposition 3.8, which is equal to the set of words Knuth-equivalent to by Lemma 3.5. Then by Lemma 3.7, the flip-reverses of the words in form the set of words Knuth-equivalent to . Since , we have . By Theorem 2.20, is generated by the compatible sequences for , and thus also generated by the compatible sequences for . Since , the compatible sequences for generate , i.e.,
Finally, flipping each compatible sequence in the formula above yields . ∎
Example 3.10.
Let . Then ; its column word is . The set of words Knuth-equivalent to is . We compute the set of compatible sequences for the flips of each of these words.
| Word | flip | Compatible sequences | Flips of Compatible sequences |
|---|---|---|---|
| 22121 | 22323 | 11223 | 33221 |
| 22211 | 22233 | 11122 11123 11133 | 33322 33321 33311 |
| 11233 12233 22233 | 33211 32211 22211 | ||
| 21221 | 23223 | 12223 | 32221 |
| 21212 | 23232 | ||
| 22112 | 22332 | 11222 | 33222 |
The corresponding monomials indeed sum up to ; compare this example to Example 2.21 computing in terms of compatible sequences.
3.2. Divided differences and Demazure crystals
Young key polynomials may also be described in terms of divided difference operators. Given a weak composition , let be the rearrangement of into increasing order. Let be the permutation of shortest length rearranging to . For define an operator
and for a permutation , define , where is any reduced word for .
Lemma 3.11.
Let be a polynomial in . We have
where is the polynomial obtained by exchanging variables .
Proof.
By linearity, it suffices to show this is true for a monomial , where is a weak composition of length . We compute
and
as required. ∎
Lemma 3.12.
is well-defined.
Proof.
Since the ’s satisfy the commutativity and braid relations of , it follows from Lemma 3.11 that the ’s also do. ∎
Theorem 3.13.
Let be a weak composition of length . Then
Proof.
First observe that if is the minimal length permutation sending to , then is the minimal length permutation sending to , i.e., is .
Therefore, by Lemma 3.11 and the fact that , we have
Example 3.14.
Let . Then the minimal length permutation taking to is . We compute
Recall the Demazure crystal structure for key polynomials described in Section 2.2.3. The Young key polynomials may be realized as characters of crystals that are obtained via Demazure truncations beginning from the lowest weight of the crystal rather than the highest. For a subset of , define
Theorem 3.15.
Let be a weak composition of length and let be of shortest length such that . Then the Young key polynomial is the character of the subcrystal of obtained by
where is a reduced word for and is the lowest weight element of .
Proof.
Recall that the shortest permutation sending to is . Performing the Lusztig involution [Lus10] on exchanges each with and with , and reverses the weight of each vertex. Hence, applying a Demazure truncation with from the highest weight of yields with variables reversed, which is equal to by (3.1). The statement follows. ∎
Observe that the repeated actions of the starting with precisely mirrors the repeated action of the divided difference operators starting with the monomial .
Example 3.16.
Let , and recall from Figure 7. The shortest-length such that is . Therefore, the crystal graph for is the subgraph of consisting of all vertices that can be obtained from the lowest weight by first applying a sequence of ’s and then a sequence of ’s. Hence .
3.3. Young key polynomials as generators for left keys
Recall Theorem 2.16 states that a key polynomial can be described as the generating function for the set of all with bounded right key. In this section we provide an analogous description of Young key polynomials as well as the corresponding description of Young Demazure atoms.
Given a semistandard Young tableau , let denote the filling obtained by flipping all entries in and reversing the order of the resulting column entries. Compare this to the definition of applied to a word at the beginning of Section 3.1. It is a straightforward observation that when is a key, is the key whose entries in each column are the flip-reverses of the entries in the corresponding column of . (However, if is not a key then is not necessarily even a semistandard Young tableau.)
We need to establish a weight-reversing bijection between semistandard Young tableaux with a given right key and semistandard Young tableaux with left key . This is done in the following lemma, which can also be understood in terms of the evacuation operation on semistandard Young tableaux. Recall that a word is Knuth equivalent to a semistandard Young tableau if and only if Schensted insertion of the word produces the tableau .
Lemma 3.17.
Let be a semistandard Young tableau. Then the left key of the tableau obtained via Schensted insertion of is .
Proof.
Let have shape and let be the semistandard Young tableau obtained by Schensted insertion of . Consider any column index . Consider any word that is Knuth equivalent to , has column form a rearrangement of , and whose rightmost maximal decreasing subsequence has length . Then the entries in column of are the entries of the rightmost maximal decreasing subsequence of . Now, the column form of is the reversal of the column form of (thus also a rearrangement of ), and Lemma 3.7 implies that is Knuth equivalent to . Therefore the leftmost maximal decreasing subsequence of is the flip-reverse of the rightmost maximal decreasing subsequence of , and hence the entries in the the column of the left key of are precisely the flip-reverses of the entries in the column of the right key of . ∎
Theorem 3.18.
The Young Demazure atoms and Young key polynomials are generated by the left keys of semistandard Young tableaux as follows:
where means entrywise comparison and .
Proof.
Consider the first expansion. Recall that and that (by Equation 2.1) is generated by the set of all semistandard Young tableaux whose right key equals . It is therefore enough to exhibit a weight-reversing bijection between the set of all semistandard Young tableaux whose right key equals and the set of all semistandard Young tableaux whose left key is .
We know from Lemma 3.17 that if is a semistandard Young tableau such that , then the semistandard Young tableau obtained via Schensted insertion of has . This process is clearly invertible, hence bijective, and the application of to ensures it is weight-reversing.
For the second expansion, we recall that and that by Theorem 2.16 is generated by the set of all semistandard Young tableaux whose right key is less than or equal to . It is straightforward to check that if , then the semistandard Young tableau obtained via Schensted insertion of has . The second expansion then follows by applying the same argument used to prove the first expansion. ∎
Example 3.19.
Let , which has right key . We have . Schensted insertion of produces the semistandard Young tableau which indeed has left key .
3.4. Row-frank words
Our next aim is to realize Young key polynomials as traces on modules. For this, we first adapt a formula of [LS90] expressing key polynomials in terms of row-frank words. The first condition below is equivalent to the condition of being row-frank; see [RS95] for details. The standardization of a semistandard Young tableau , denoted , is the standard Young tableau obtained by replacing the ’s in from left to right by , the ’s by , and so on, where equals the number of times the entry appears in . Given a word in positive integers, its row-word factorization is , where each row-word is a weakly increasing subsequence of maximal length.
For a weak composition , let be the set of all words with each having letters, satisfying the following conditions.
-
(1)
The word maps to a pair under the column insertion described in [RS95].
-
(2)
No letter of exceeds .
Theorem 3.20.
[LS90] The key polynomials are generated using words in as follows:
We now provide the analogue of this generating function for Young key polynomials. For a weak composition , let be the set of all words with each having letters, satisfying the following conditions.
-
(1)
The word maps to a pair under column insertion.
-
(2)
For each letter of , we have .
Example 3.21.
We have
and
where the vertical bars denote the row word factorization (including empty row-words).
Theorem 3.22.
The Young key polynomials are generated using the words in as follows:
Proof.
Consider a word in and let . Then satisfies condition (1) for by construction. Consider a letter in . By definition, . The flip of appears in the row-word of , and implies . So satisfies both the conditions to be in the set . Since flipping and reversing is an invertible process, we have that the words in are exactly the flip-reverses of the words in . Then since the monomials appearing in are the flips of those appearing in , it follows from Theorem 3.20 that generates . ∎
3.5. Young key polynomials as traces on modules
In [RS95], generalized flagged Schur modules and key modules are defined. The key polynomials are realized as traces on key modules, which are a special case of generalized flagged Schur modules. In this section we modify the Reiner-Shimozono approach to construct modules so that the Young key polynomials are realised as traces on these modules.
As in [RS95], a diagram is a finite subset of the Cartesian product of the positive integers with itself, where every element of in is thought of as being a box. A filling of shape is a map assigning a positive integer to each box in (note this is called a tableau of shape in [RS95]).
Let be a field of characteristic , and let be the vector space over with basis the set of all fillings of shape whose largest entry does not exceed . Fix an order on the boxes of , and identify the filling with the tensor product , where is the th standard basis vector. Then an action of on is defined by letting act on each as usual and extending this action linearly.
The row group (respectively column group ) is the set of all permutations of the boxes of which fixes the rows (resp. columns) in which the boxes appear. These groups act on by permuting the positions of the entries within a filling. As in [RS95], define
where is the filling obtained by acting first by and then by .
Define the Young generalized flagged Schur module for an arbitrary diagram (with at least the maximum row index of ) to be the subspace of spanned by the set as runs over all fillings of shape whose entries in row are not smaller than . It is straightforward that is a -module, where is the Borel subgroup of consisting of lower-triangular matrices.
Remark 3.23.
The construction of the generalized flagged Schur module described in [RS95] is similar, but serves to illustrate an important difference in the behaviors of Young and reverse families of polynomials. In [RS95] is defined to be the vector space with basis consisting of all fillings of shape , with no restriction on the size of the entries. In this way, is a -module. Then is spanned by the set as runs over all fillings of shape whose entries in row are not larger than , which is finite even though is infinite-dimensional. In this way, is a module for the opposite Borel subgroup consisting of upper-triangular elements of . The dependence on in the Young case is reflected in the fact that appending zeros to a weak composition does not change the corresponding key polynomial, but does change the Young key polynomial.
Example 3.24.
Let . Then if , applying elements of the row group to yields the following:
where the coefficients are because there are two distinct permutations yielding each ordering of . It is easy to see that for any filling with repeated entries in any column, we have , hence only the first and fifth fillings above contribute to . Applying the column group to each of these and summing the resulting fillings yields
Define the key module for the weak composition to be the -module .
Theorem 3.25.
[RS95] For in let be the filling of shape obtained by placing in row . Then is a basis for the key module .
We now describe the variation on the Reiner-Shimozono construction that needed to describe the Young key polynomials as characters. Let be a weak composition of length , and define the Young key module for the weak composition to be the -module . Here we may drop from the notation, since is determined by the weak composition .
Corollary 3.26.
For in , let be the filling of shape obtained by placing in row . Then is a basis for the Young key module .
Proof.
The flip-and-reverse map on fillings extends linearly to an involution , hence an isomorphism, on . Moreover, sends a filling whose entries are at least their row index to a filling whose entries are at most their row index, and vice versa. In particular, by the proof of Theorem 3.22, carries to the basis of given by Theorem 3.25.
Therefore, is a linearly independent set, since any linear dependence in this set would imply, via , a linear dependence in the linearly independent set . Similarly is spanning: suppose . Then , hence is in the span of the spanning set of , and applying again yields as a linear combination of . ∎
Remark 3.27.
The order in which entries of are placed in row does not matter, since fillings with any given ordering of in each row appear in due to the action of the row group. In Example 3.29, we represent by the filling with entries increasing from left to right in each row, which agrees with the choices of representatives for key modules in [RS95].
Let be the diagonal matrix whose diagonal entries are . We immediately obtain the following (compare to Corollary 14 in [RS95]).
Corollary 3.28.
The Young key polynomial is the trace of acting on the Young key module .
Example 3.29.
The Young key module has basis for the following fillings .
4. Other polynomial families and intersections
In this section, we provide a new formula in terms of Knuth equivalence for the fundamental slide expansion of a key polynomial, and interpret compatible sequences in terms of the fundamental particle basis, introduced in [Sea20] as a common refinement of the fundamental slide and Demazure atom bases. As we did for Young key polynomials and Young atoms, we also determine the intersections of further reverse bases and their Young analogues.
4.1. The fundamental and monomial slide bases
For a weak composition , define the fundamental fillings for [Sea20] to be the (reverse) fillings of satisfying the following conditions.
-
(1)
Entries weakly decrease from left to right in each row.
-
(2)
No entry in row is greater than .
-
(3)
If a box with label is in a lower row than a box with label , then .
The fundamental slide polynomial [AS17] is the generating function of :
For example, , computed by below.
The monomial slide basis can also be described using reverse fillings. Given a weak composition , the monomial fillings [Sea20] are the subset of for which all entries in the same row are equal. The monomial slide polynomial [AS17] is
For example, .
Various formulas have been given [AS18b], [Ass17], [MPS19] for the fundamental slide expansion of a key polynomial. Here we provide another, more in keeping with the theme of the previous section.
Proposition 4.1.
where is the weak composition associated to the compatible sequence for whose entries are maximum possible. (If has no compatible sequences, we declare .)
Proof.
We need to establish ; the statement then follows from Theorem 2.20. The compatible sequence for a word whose entries are maximum possible is found as follows. First, partition into (weakly) decreasing runs . Let denote the rightmost (i.e. smallest) entry of in the run . We proceed right-to-left, at each step replacing every entry in a run with a certain number . To begin, replace every element in with , i.e., we set . Proceeding leftwards, replace every entry in with . This process is a variant of the construction of the weak descent composition of a word in [Ass17], [MS20].
Every compatible sequence for can be obtained from the maximal one by decrementing parts as long as we still have whenever . In exactly the same way, every fundamental filling for can be obtained from the filling that has every entry equal to its row index by decrementing entries as long as entries in a given row remain strictly larger than entries in any lower row. This gives a weight-preserving bijection between the compatible sequences for and the fundamental fillings for . ∎
For example, suppose . Then the partition into weakly decreasing runs gives . We replace each entry in the last run with , obtaining . Next, we replace each entry in the next run with , obtaining . Finally, we replace each entry in the first run with , obtaining . The largest compatible sequence for is thus .
Example 4.2.
From the table in Figure 8, we compute . The only compatible sequence for is , so .
This yields a formula for the Young fundamental slide expansion of Young key polynomials, proved similarly to Theorem 3.9.
Proposition 4.3.
4.2. Quasi-key polynomials and fundamental particles
For a weak composition , define the quasi-key fillings to be the (reverse) fillings of satisfying the following conditions.
-
(1)
Entries weakly decrease from left to right in each row.
-
(2)
No entry in row is greater than .
-
(3)
Entries strictly increase up the first column, and entries in any column are distinct.
-
(4)
All type A and type B triples are inversion triples.
The quasi-key polynomial is
Quasi-key polynomials were first defined in [AS18b] as a lift of the quasisymmetric Schur functions to a basis of . The above formula is due to [MPS19]. For example, we have which is computed by the quasi-key fillings shown in Figure 11 below.
The set of fillings generating Demazure atoms is exactly the subset of consisting of those fillings whose entries in the leftmost column are equal to their row index. For example, , which is computed by those fillings in Figure 11 whose leftmost column entries are and .
Finally, define the particle fillings to be the subset of consisting of those fillings such that whenever , all entries in row are strictly smaller than all entries in row . Then the fundamental particle [Sea20] is defined to be
For example, , by the 1st, 2nd, and 4th fillings in Figure 11.
We give a new formula for in terms of compatible sequences. Let be the set of the partial sums of the entries in with duplicate entries (obtained when an entry of is ) removed. Then we say that a compatible sequence for the word formed by writing instances of consecutively is -flag compatible if for all , the letter in position of is equal to the row index of the nonzero entry in .
Theorem 4.4.
Let be a weak composition of length , Then
Proof.
The statement follows from the fact that the -flag compatible sequences correspond to via the following bijection. Let be an -flag compatible sequence and let be the subword of corresponding to the subword . Construct the row of a by writing in weakly decreasing order. Conditions (1),(2), and (3) in the definition of a are satisfied by construction. Condition (4) is satisfied since the entries in a given row are all smaller than all of the entries in any higher row. The flag condition guarantees that these fillings are in , and further, the fact that the entries in a given row are all smaller than all of the entries in any higher row implies these fillings are in . To obtain an -flag compatible sequence from an element of , record the entries in each row from right to left (to force them to be weakly increasing), reading rows from bottom to top. ∎
Figure 12 below shows how the bases discussed here expand into one another. An arrow indicates that the basis at the tail expands positively in the basis at the head. This figure is taken from that in [Sea20].
4.3. Young bases and intersections
Young analogues may be defined for all the families described above. Indeed, Young analogues of the fundamental slide polynomials and the quasi-key polynomials were introduced and utilized in [MS20]. In addition to the Young key polynomials and Young Demazure atoms studied in Section 3, Young analogues of the monomial slide polynomials and fundamental particles may be defined similarly, and these families can be shown (by utilizing Lemma 4.6 below) to exhibit positive expansions in Figure 13 analogous to those shown in Figure 12.
Remark 4.5.
Lemma 4.6.
Let be a weak composition of length , and let denote the set of all possible fillings of with entries from , one entry per box. Define by letting be the filling obtained by moving all boxes in row to row and replacing every entry with , for all . Then the following statements are true.
-
(1)
The map is an involution.
-
(2)
If has weight then has weight .
-
(3)
The relative order of entries in row of is the reverse of the relative order of entries in row of .
-
(4)
The relative order of entries in any column of is the same as the relative order of entries in the same column of .
-
(5)
A triple of boxes in is an inversion triple if and only if the image of those boxes is a Young inversion triple in .
Proof.
The first four properties are immediate from the definition of . Since the relative order of entries in the boxes of a triple in is the reverse of the relative order of entries in the images of those boxes in , it follows from the definition of inversion triples and Young inversion triples that the image of an inversion triple (of type A, respectively B) in must be a Young inversion triple (of type I, respectively II) in . Likewise, the images of non-inversion triples in are Young non-inversion triples in . ∎
Given a weak composition of length , define the Young fundamental fillings of to be the fillings of with entries from satisfying the following conditions.
-
(1)
Entries weakly increase from left to right in each row
-
(2)
No entry in row is less than
-
(3)
If a box with label is in a lower row than a box with label , then .
In particular, is the image of under . The Young fundamental slide polynomial [MS20] is the generating function of :
For example, we have , which is computed by the elements of shown below.
For a weak composition of length , define the Young monomial fillings to be the subset of for which all entries in any row are equal. Define the Young monomial slide polynomial to be the generating function of :
For example, we have .
Proposition 4.7.
The Young fundamental slide and the Young monomial slide bases of contain (respectively) the fundamental quasisymmetric and monomial quasisymmetric bases of quasisymmetric polynomials in variables. Specifically, if is a weak composition of length such that all zero entries are to the right of all nonzero entries, then
where is the composition obtained by deleting all parts of .
Proof.
This is shown in [MS20] for Young fundamental slides. For monomial slides, since all nonzero entries of occur before all zero entries, the flag condition on is always satisfied whenever the other conditions are satisfied. Hence the are exactly the monomial Young composition tableaux (Proposition 2.3). ∎
Theorem 4.8.
The polynomials in that are both a fundamental (respectively, monomial) slide polynomial and a Young fundamental (respectively, monomial) slide polynomial are exactly the fundamental (respectively, monomial) quasisymmetric polynomials in variables.
In other words, and .
Proof.
We prove this in the fundamental case; the monomial case is completely analogous. First, let be a composition of length . Then
For the other direction, let be a fundamental slide polynomial that is not equal to for any composition . This implies has a zero entry to the right of a nonzero entry ([AS17]). Let be the earliest such zero entry, so is nonzero. Let denote the weak composition obtained by exchanging the entries and . Then and . However, if a Young fundamental slide polynomial contains , it must also contain . Hence is not equal to any Young fundamental slide polynomial. ∎
For a weak composition of length , define the Young quasi-key fillings to be the (Young) fillings of obtained by applying to . Specifically, these are the fillings such that entries increase along rows, entries are at least their row index, entries strictly increase up the first column and entries in any column are distinct, and all type I and II Young triples are Young inversion triples. These generate the Young quasi-key polynomial [MS20]. Unsurprisingly, the conditions governing the intersections of quasi-key and Young quasi-key polynomials are similar to those governing the intersections of the quasisymmetric bases that they extend (Theorem 2.13).
Theorem 4.9.
The polynomials that are both quasi-key and Young quasi-key polynomials are precisely the such that is a number of equal parts followed by zeros, or a sequence of ’s and ’s followed by zeros, or has no zero parts and consecutive parts differ by at most .
Proof.
For any , the polynomial contains the monomial , realised by whose entries in row are all . Suppose a quasi-key polynomial contains , realised by some . Suppose has a zero entry preceding a nonzero entry, e.g., but is nonzero. Create by changing the rightmost in to an . Since we change the rightmost , entries of still decrease along rows, and since no other ’s exist in , entries still strictly increase up the first column of and do not repeat in any column of , and the relative order of the entries in any triple in remains unchanged. Hence , but there is no element of that has this weight since all entries of are already minimal possible. Therefore for any .
It follows that for to be equal to , must consist of an interval of nonzero entries, followed by zero entries. But then by [MS20]. The quasi-key polynomials that are quasisymmetric are exactly the quasisymmetric Schur polynomials: where is an interval of zero entries followed by an interval of nonzero entries [AS18]. Then, by Theorem 2.13, is equal to exactly when has all parts the same, or all parts of are or , or (so has no zero parts) and consecutive parts differ by at most . ∎
Similarly, define the Young particle fillings to be the image of under . These Young fillings, which are the such that any entry in a lower row is strictly smaller than any entry in a higher row, generate the Young fundamental particle .
Theorem 4.10.
The polynomials that are both fundamental particles and Young fundamental particles are precisely the such that has no zero part adjacent to a part of size at least .
Proof.
The (respectively, ) obey all the conditions on (respectively ), hence the same argument used in the proof of Theorem 3.3 shows that if then .
If and for some , then let such that all entries in each row are . Let also be obtained by changing the rightmost to . Then there is no with the same weight as , since the entries in above row must agree with those in above row , and then there is nowhere the new could be placed in . Hence . A similar argument shows that if and then .
Straightforwardly, if has no zero part next to a part of size at least . ∎
Remark 4.11.
While the Young and reverse analogues of a given basis have similar definitions, they have important structural differences. Unlike the reverse families, for each family of Young polynomials, the basis of Young polynomials of does not embed into . For example, is not a Young fundamental slide polynomial in . Because of this, we cannot use the typical definition of a weak composition as an infinite sequence of nonnegative integers (almost all zero); the number of entries in the sequence matters and the value of must be specified.
Remark 4.12.
Stable limits are obtained for all families in the top row of Figure 12 by prepending zeros to the weak composition ; they are equal to the appropriate quasisymmetric function for ([Sea20, Theorem D]). While stable limits for the Young analogues of these families can be defined (by appending zeros to the weak composition ), they are not equal to the quasisymmetric functions for , except in the case that all nonzero entries of are to the left of all zero entries of . A polynomial satisfying this condition is in fact already quasisymmetric, and indeed limits to the expected quasisymmetric function.
For example, the stable limit of the Young fundamental slide polynomial (which is equal to ) is the (Young) fundamental quasisymmetric function . However, the stable limit of is not .
5. Young Schubert polynomials
Schubert polynomials were first introduced in [LS82] to represent Schubert classes in the cohomology of the flag manifold. Schubert polynomials are typically indexed by permutations. However, every permutation corresponds to a weak composition called a Lehmer code, which may also be used to index the Schubert polynomial. For each there is a -basis for consisting of Schubert polynomials, however unlike the previously-discussed bases of , the indexing compositions of the Schubert basis elements are not compositions of length but of arbitrary length. It is a long-standing open problem to find a positive combinatorial formula for the structure constants of the Schubert basis. See [Mac91, Man98] for more details about the geometry, algebra, and combinatorics of Schubert polynomials.
We will take the combinatorial “pipe dreams” model introduced in [BB93] as our definition of Schubert polynomials. Consider a permutation . The Lehmer code of is the weak composition of length whose term equals the number of pairs with such that . For example, if then . A (reduced) pipe dream is a tiling of the first quadrant of with elbows and crosses so that any two of the resulting strands (called pipes) cross at most once. The associated permutation can be read from the diagram by following the pipes from the -axis to the -axis. Let denote the set of pipe dreams for . The five pipe dreams in are shown in Figure 14.
5 4 3 2 1 1 2 3 4 5 5 4 3 2 1 1 2 3 4 5 5 4 3 2 1 1 2 3 4 5 5 4 3 2 1 1 2 3 4 5 5 4 3 2 1 1 2 3 4 5
Let . The Schubert polynomial is given by
where is the weak composition whose term counts the crosses in the row of .
For example, by Figure 14 the Schubert polynomial indexed by the permutation is
Let denote the set of reduced words for a permutation . Every Schubert polynomial can be written as a positive sum of key polynomials according to the following theorem.
Theorem 5.1 ([RS95, LS89]).
where the sum is over semistandard Young tableaux , and is the left nil key of , obtained via a modification of Knuth equivalence called nilplactic equivalence.
5.1. Young pipe dreams
Towards giving a combinatorial construction of the Young analogue of Schubert polynomials, we define a Young analogue of pipe dreams. Relabel the row indices (on the -axis) with as the bottom row, as the second row, and so on. Then read the “reversal” of the permutation by following the pipes from the -axis to the -axis. This reversal is the permutation read from right to left (in one-line notation), which we denote . This new diagram is called the Young pipe dream corresponding to the permutation obtained by reading the pipes in this manner, and the set of all Young pipe dreams for a permutation is denoted . Let the Young Lehmer code of a permutation , denoted , be the weak composition of length whose term is the number of pairs with such that . The Young weight of a Young pipe dream is the weak composition whose part is the number of crosses in the row from the top.
1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5
Let . Then the Young Schubert polynomial is given by
For example, the Young Schubert polynomial associated to the permutation can be calculated by reading the Young weights of the Young pipe dreams in Figure 15 as follows:
It is straightforward to check that . It follows that
| (5.1) |
Remark 5.2.
Schubert polynomials have a well-known stability property, namely, for , , where is the embedding in which acts on the first letters. The same is not true for Young Schubert polynomials, for example but . Analogous to Remark 4.11, a Young Schubert polynomial in is not a Young Schubert polynomial in . Similarly, the stable limit of a Schubert polynomial (on prepending zeros to the Lehmer code) exists, and was shown in [Mac91] to be a Stanley symmetric function. Analogous to Remark 4.12, there is no corresponding stable limit for Young Schubert polynomials.
Remark 5.3.
The analogue of Remark 4.5 fails in this case: despite the fact that Schubert polynomials form a basis for , no collection of Young Schubert polynomials forms a basis for . This is due to the fact that the exponent of in a monomial in a Young Schubert polynomial is bounded by . For Schubert polynomials this “staircase” condition goes the opposite way: the exponent of is bounded by when the indexing permutation is in . Hence, by increasing as needed, one can find a Schubert polynomial in containing any given monomial in .
Remark 5.4.
For completeness, we note that no polynomial is both a Schubert and a Young Schubert polynomial. All Schubert polynomials have at least one monomial divisible by , but no Young Schubert polynomials do.
A permutation is said to be vexillary if for every sequence of indices, one never has . That is, is vexillary if and only if avoids the pattern . For vexillary, we have [LS90]
Thus the Young Schubert polynomials indexed by permutations whose reversal is vexillary are the Young key polynomials indexed by Young Lehmer codes of -avoiding permutations.
Theorem 5.1 and (3.1) yield the following formula for writing any Young Schubert polynomial as a positive sum of Young key polynomials.
Other combinatorial descriptions of Schubert polynomials can similarly be translated into descriptions of Young Schubert polynomials.
Schubert polynomials were initially defined in terms of divided difference operators so that
where is the longest permutation of an -element set and . There is a natural way to describe Young Schubert polynomials in terms of divided difference operators, which we establish below. For , let be the permutation . It is straightforward to see that in one-line notation, is obtained from by reversing the entries of and replacing each entry with , e.g. .
Lemma 5.5.
Let be a reduced word for . Then .
Proof.
We induct on the length of . If has length , then and the statement holds. Now suppose the statement holds for all of length , for some . Suppose has an ascent in position , i.e. . Then has length , and is obtained by exchanging the th and th entries of . We have ; we need to show . But is equal to by the inductive hypothesis, and therefore is obtained from by exchanging the entries in the th and th positions. This permutation is exactly . ∎
Lemma 5.6.
Let be a polynomial in , and let be defined as in Lemma 3.11. Then .
Proof.
We show that ; after which repeated iteration establishes the result. To see this, consider the monomial where . (The case where is similar and if then .)
We are now ready to establish a divided difference formula for . The power of appearing in the formula below is due solely to the fact that since we begin with , we apply to a polynomial whose power of is smaller than its power of in each monomial. The power of could be defined away by replacing the denominator with in the definition of .
Theorem 5.7.
Let . Then
Proof.
Let be a reduced word for . Combining Lemmas 5.5 and 5.6, we have
Recall that , and in particular . Note also that , that , and that . We therefore have
Example 5.8.
Let . Then and we have
Compare this to , which is equal to .
5.2. Demazure crystal structure
We use the recently developed crystal structure for Stanley symmetric functions [MS16] and the Demazure crystal structure for Schubert polynomials [AS18a] to generate the Demazure crystal structure for Young Schubert polynomials.
Let . Following [MS16], a reduced factorization for is a partition of a reduced word for into blocks (possibly empty) of consecutive entries such that entries decrease from left to right within each block; let denote the set of all reduced factorisations of with blocks. In [MS16], a crystal structure is defined on . Precise definitions of the and operators may be found in [MS16, Section 3.2]. See Figure 16 for the crystal structure on , with arrows labelled. For our purposes, we need to define the weight of to be the weak composition of length given by (as opposed to used in [MS16]). In particular we define to begin with zeros, e.g., for , we have , and .
Let be the position of the rightmost descent in . Define the reduced factorisations with Young cutoff for , denoted , to be those elements of such that the smallest entry in the block from the left is at least . See Figure 16, in which the elements of are bolded. Compare this to the reduced factorisations with cutoff defined in [AS18a].
Theorem 5.9.
The Young Schubert polynomial is equal to . Moreover, is a union of Demazure crystals, under the convention that we begin with the lowest weight rather than the highest and use the operators.
Proof.
In [AS18a], a crystal structure isomorphic to that of [MS16] is obtained by reversing each reduced factorisation for (thus obtaining reduced factorisations for partitioned into increasing blocks), and exchanging the roles of with and with . Restricting this isomorphism to gives the set of reduced factorisations with cutoff for , of which the weight generating function is [AS18a]. Since this isomorphism is weight-reversing, it follows from (5.1) that the weight generating function of is . By [AS18a, Theorem 5.11], reduced factorisations with cutoff have a Demazure crystal structure, and the isomorphism implies is a union of Demazure truncations of the components of , starting with the lowest weight. ∎
The Demazure crystal structure provides another method for expanding Young Schubert polynomials in Young key polynomials, cf. [AS18a, Corollary 5.12].
Example 5.10.
Figure 16 demonstrates that , where is the bolded Demazure truncation of the left component and is the bolded Demazure truncation of the right component.
Acknowledgements
We thank Sami Assaf and Anne Schilling for suggesting a connection with the Demazure crystal structure for Schubert polynomials, and Martha Precup and Brendon Rhoades for pointing out further recent appearances of the Young/reverse dichotomy for polynomials and tableaux. We also thank Vic Reiner for pointing out a connection to evacuation in Section 3.
References
- [AHM18] E. Allen, J. Hallam, and S. Mason. Dual immaculate quasisymmetric functions expand positively into Young quasisymmetric Schur functions. J. Combin. Theory Ser. A, 157:70–108, 2018.
- [AS17] S. Assaf and D. Searles. Schubert polynomials, slide polynomials, Stanley symmetric functions and quasi-Yamanouchi pipe dreams. Adv. Math., 306:89–122, 2017.
- [AS18a] S. Assaf and A. Schilling. A Demazure crystal construction for Schubert polynomials. Algebraic Combinatorics, 1(2):225–247, 2018.
- [AS18b] S. Assaf and D. Searles. Kohnert tableaux and a lifting of quasi-Schur functions. J. Combin. Theory Ser. A, 156:85–118, 2018.
- [AS19] S. Assaf and D. Searles. Kohnert polynomials. Experiment. Math., to appear, 2019. 27 pages.
- [Ass17] S. Assaf. Combinatorial models for Schubert polynomials. arXiv:1703.00088, 2017.
- [BB93] N. Bergeron and S. Billey. Rc-graphs and schubert polynomials. Experimental Math, 2(4):257–269, 1993.
- [BBS+14] C. Berg, N. Bergeron, F. Saliola, L. Serrano, and M. Zabrocki. A lift of the Schur and Hall-Littlewood bases to non-commutative symmetric functions. Canad. J. Math., 66(3):525–565, 2014.
- [BS17] D. Bump and A. Schilling. Crystal Bases: Representations and Combinatorics. World Scientific, 2017.
- [Dem74] M. Demazure. Une nouvelle formule des caractères. Bull. Sci. Math. (2), 98(3):163–172, 1974.
- [Ful97] W. Fulton. Young tableaux, volume 35 of London Mathematical Society Student Texts. Cambridge University Press, Cambridge, 1997. With applications to representation theory and geometry.
- [Ges84] I.M. Gessel. Multipartite p-partitions and inner products of skew Schur functions. Contemp. Math, 34:289–301, 1984.
- [HHL08] J. Haglund, M. Haiman, and N. Loehr. A combinatorial formula for nonsymmetric Macdonald polynomials. Amer. J. Math., 130(2):359–383, 2008.
- [HK02] J. Hong and S.-J. Kang. Introduction to quantum groups and crystal bases, volume 42 of Graduate Studies in Mathematics. American Mathematical Society, Providence, RI, 2002.
- [HLMvW11] J. Haglund, K. Luoto, S. Mason, and S. van Willigenburg. Quasisymmetric Schur functions. J. Combin. Theory Ser. A, 118(2):463–490, 2011.
- [HRS18] J. Haglund, B. Rhoades, and M. Shimozono. Ordered set partitions, generalized coinvariant algebras, and the delta conjecture. Adv. Math., 329:851–915, 2018.
- [Hua16] J. Huang. A tableau approach to the representation theory of 0-Hecke algebras. Ann. Comb., 20(4):831–868, 2016.
- [Kas91] M. Kashiwara. Crystallizing the q-analogue of universal enveloping algebras. Commun. Math. Phys., 133:249–260, 1991.
- [Kas93] M. Kashiwara. The crystal base and Littelmann’s refined Demazure character formula. Duke Math. J., 71(3):839–858, 1993.
- [Kas95] Masaki Kashiwara. On crystal bases. In Representations of groups (Banff, AB, 1994), volume 16 of CMS Conf. Proc., pages 155–197. Amer. Math. Soc., Providence, RI, 1995.
- [Li15] Y. Li. On q-symmetric functions and q-quasisymmetric functions. Journal of Algebraic Combinatorics, 41(2):323–364, 2015.
- [Lit95] P. Littelmann. Crystal graphs and Young tableaux. J. Algebra, 175(1):65–87, 1995.
- [LMvW13] K. Luoto, S. Mykytiuk, and S. van Willigenburg. An introduction to quasisymmetric Schur functions: Hopf algebras, quasisymmetric functions, and Young composition tableaux. Springer Briefs in Mathematics. Springer, New York, 2013.
- [LS82] A. Lascoux and M.-P. Schützenberger. Polynômes de Schubert. C. R. Acad. Sci. Paris Sér. I Math., 294(13):447–450, 1982.
- [LS89] A. Lascoux and M.-P. Schützenberger. Tableaux and non-commutative Schubert polynomials. Funct. Anal. Appl., 23:63–64, 1989.
- [LS90] A. Lascoux and M.-P. Schützenberger. Keys & standard bases. In Invariant theory and tableaux (Minneapolis, MN, 1988), volume 19 of IMA Vol. Math. Appl., pages 125–144. Springer, New York, 1990.
- [Lus10] G. Lusztig. Introduction to quantum groups. Springer Science & Business Media, 2010.
- [Mac91] I. G. Macdonald. Schubert polynomials. In Surveys in combinatorics, 1991 (Guildford, 1991), volume 166 of London Math. Soc. Lecture Note Ser., pages 73–99. Cambridge Univ. Press, Cambridge, 1991.
- [Man98] L. Manivel. Fonctions symétriques, polynômes de Schubert et lieux de dégénérescence, volume 3 of Cours Spécialisés [Specialized Courses]. Société Mathématique de France, Paris, 1998.
- [Mas09] S. Mason. An explicit construction of type A Demazure atoms. J. Algebraic Comb., 29(3):295–313, 2009.
- [MN15] S. Mason and E. Niese. Skew row-strict quasisymmetric schur functions. Journal of Algebraic Combinatorics, pages 1–29, 2015.
- [MPS19] C. Monical, O. Pechenik, and D. Searles. Polynomials from combinatorial -theory. Canad. J. Math., to appear, 2019. 35 pages, arXiv:1806.03802.
- [MS16] J. Morse and A. Schilling. Crystal approach to affine Schubert calculus. Int. Math. Res. Not., 2016(8):2239–2294, 2016.
- [MS20] S. Mason and D. Searles. Lifting the dual immaculate functions, 2020.
- [PR21] M. Precup and E. Richmond. An equivariant basis for the cohomology of Springer fibers, 2021.
- [RS95] V. Reiner and M. Shimozono. Key polynomials and a flagged Littlewood-Richardson rule. Journal of Combinatorial Theory, Series A, 70(1):107–143, 1995.
- [Sag13] Bruce E Sagan. The symmetric group: representations, combinatorial algorithms, and symmetric functions, volume 203. Springer Science & Business Media, 2013.
- [Sea20] D. Searles. Polynomial bases: positivity and Schur multiplication. Transactions of the American Mathematical Society, 373:819–847, 2020.
- [Sta99] R. P. Stanley. Enumerative combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.
- [Wil13] M. Willis. A direct way to find the right key of a semistandard Young tableau. Ann. Comb., 17(2):393–400, 2013.
Appendix A Intersections of polynomial families
In this appendix we determine the polynomials that are both quasisymmetric Schur and Young quasisymmetric Schur polynomials. Throughout, let be the length of and the number of variables.
Lemma A.1.
If , then .
Proof.
By the same argument in the proof of Theorem 3.3, if , then must be a rearrangement of . Therefore suppose rearranges and the length of (and thus of ) is . Let be such that the entries in each row are all . Suppose has the same weight as . Since the first column of must increase strictly from top to bottom, and we must use all entries through in , the first entry in each row of is forced to be . By the same argument in the proof of Theorem 3.3, the set of entries in each column of must be the same as that in the corresponding column of .
Suppose , and let be the largest index such that . Consider rows down to , where the row lengths are identical in and . Since entries of must decrease along rows, the ’s can only go in the th row of , and thus completely fill the th row of . By the same reasoning, all ’s must go in row of , and so forth down to (and including) row . Now, if , it is impossible to place many ’s in row of , but ’s cannot go in any lower row of since entries must decrease along rows, and cannot go in any higher row of since all boxes above row are occupied, so we cannot construct of the same weight as . So assume . Then we must place many ’s in the first boxes of the th row. The next entry placed in this row (in column ) is some . Since the column sets of and must agree and each column set of is a subset of the previous one, there must be an in column of . Since all boxes weakly above row in this column are occupied by entries at least , must be strictly below row in this column. But then these two copies of must violate one of the triple conditions in . It follows that if , then there is no with the same weight as , and thus . ∎
Therefore, the question reduces to determining when .
Lemma A.2.
Let be a composition of length . If there are such that
-
(1)
and there is no such that , or
-
(2)
and there is no such that
then .
Proof.
For (1), create by letting all entries be equal to their row index, except the last entry of row is . The condition that there is no such that ensures does not violate the triple condition (B). Then . One cannot create with weight equal to that of . The first column of must contain the entries through from bottom to top, i.e., the first entry of each row is the row index. Then since entries must increase along rows of , all ’s must be in row , ’s in row , etc, but then one cannot place ’s in row , since its length is . Hence . The proof of (2) is similar, starting by creating whose entries in each row are equal to their row index, except the last entry of row is . ∎
It follows from Lemma A.2 that the only where could possibly be equal to are those such that for each , .
Lemma A.3.
Let be a composition of length and . If or for some , then .
Proof.
Suppose . Construct by letting all entries be equal to their row index in the first rows, except the last entry of row is , and then all entries of each row for are . Since , the triple condition (II) is not violated. Now attempt to construct with weight equal to that of . All ’s must go in row , then all ’s in row , down to and including row . The sole must be the first entry in row , since all boxes above row are occupied. The ’s can’t all fit in row , so necessarily the first entry in row must be if all ’s are to be placed. This means all ’s must be placed in row or row . Since , they cannot all be placed in row ; at least one must be in row , immediately following the entry . But then the in row , column , the in row , column , and the in row , column violate the triple condition (B).
For satisfying , a similar argument works by letting be such that entries are equal to to their row index in the first rows, then all entries of each row for are , except the last entry of row is . ∎
Proof of Theorem 2.13: It follows from Lemmas A.2 and A.3 that the only where could possibly be equal to are those whose parts are all the same, those whose parts are all or , or (only when ) those whose consecutive parts differ by at most one.
If all parts of are the same, then and are both equal to the Schur function by Proposition 2.11).
If all parts of are or , define a map on tableaux of shape by swapping the entries in each row of length , and then reordering the rows so the first column is increasing from top to bottom. We will show that restricts to a bijection between and . First we observe maps each to a tableau of shape : if a row of length is above a row of length in , then the entry in the row of length must be larger than both entries of the row of length , the first due to the increasing first column, and the second due to the triple condition (II). If a row of length is below a row of length , then the entry in the row of length must be smaller that both entries of the row of length , due to the increasing first column and the fact that entries increase along rows. Hence re-ordering occurs only amongst rows of length that do not have a row of length between them. In particular, re-ordering never exchanges a row of length and a row of length .
Next we show that if , then has no repeated entries in any column. Suppose there are two instances of the same entry in . The in column cannot be strictly above the in column because entries increase along rows and strictly increase up the first column. Also, the in column 2 cannot be strictly below the in column 1, or these two instances of would violate one of the triple conditions. Therefore, the ’s must be in the same row of , and so cannot be in the same column of .
Now we show . By definition, entries decrease along rows of and increase up the first column. First consider type B triples in , in which case the lower row in the triple has length . All entries above a given row of length in are strictly larger than that entry, since entries increase along rows and up the first column. So the same is true in , and the type B triple rule is satisfied. Now consider type A triples in . Then both rows in the triple have length . If these rows are not swapped under , then in the second entry in the higher row is larger than the second entry in the lower row. Combining this with the triple condition in and the increasing first column, both entries of the higher row must be strictly larger than both entries of the lower row in . This implies the same is true in , hence the type A triple rule is satisfied. If they are swapped, we have
where and . Note that , since , but also , so the triple involving in satisfies the type A triple rule. Hence the map sends to . A similar argument shows sends to and that is the identity when restricted to either or , so is a bijection. Since is also weight-preserving, this implies .
Finally if consecutive parts of differ by at most one and , the only element of and is the tableau whose entries in each row are all , and thus . We proceed by induction on the number of columns of . Suppose ; certainly in the first column the entry in each row must be . Suppose this is true for the first columns. Consider the boxes in column from highest to lowest. If the highest box is in the top row (i.e., row ) then it must have entry by the increasing row condition. If it is in row , then row must be one box shorter than row (since is highest in its column and consecutive parts of differ by at most one), and the box in row , column must have entry (by assumption). Then cannot have entry greater than or the triple condition (II) is violated, so must have entry by the increasing row condition and the fact that (by assumption) the box immediately left of has entry .
Now suppose the highest boxes in column have entry equal to their row index, and suppose the th highest box is in row . If every row above row has a box in column , then by assumption these boxes all have entry equal to their row index, and then must have entry since its entry is at least , and entries cannot repeat in a column. Otherwise, consider the lowest row above row that does not have a box in column . Since consecutive parts of differ by at most one, the rightmost box in row must be in column , and thus by assumption it has entry . Then must have entry strictly smaller than , otherwise triple condition (II) is violated by , the box immediately left of (which has entry ), and the rightmost box in row . But since was the lowest row above row without a box in column , there are boxes in rows and column with entry equal to their row index. Therefore, since entries cannot repeat in a column, the entry in must be . It follows that all boxes in column have entry equal to their row index, and then that all boxes in have entry equal to their row index. A similar argument shows that is also the only element of . ∎