Last update: 28 June 2013
Let so that
For each permutation the Schubert polynomial is defined to be
where as usual is the longest element of
(4.2) Let Then
From (2.7) we have
by (1.6). Hence is equal to if and is zero otherwise.
(i) That is clear from the definition (4.1). Also by (2.11) we have
(ii) The operator lowers degrees by Hence is homogeneous of degree If now is such that then by (2.1) is a linear combination of monomials such that if and
so that Hence the linear span of the monomials is mapped into itself by each and hence by each Hence for each
(iii) is symmetrical in and if and only if that is to say if and only if which by (4.2) is equivalent to
(iv) is symmetrical in by (iii) above, but does not contain hence does not contain any of
Remark. We shall show later (4.17) that the coefficients in (4.3)(ii) are always non-negative integers.
(4.4) For we have
By (4.3), is a homogeneous symmetric polynomial of degree in hence is equal to for some integer But by (4.2) and (4.3)(i), hence
(4.5) (Stability) Let and let be the embedding. Then
We may assume that Let be the longest element of then where is the longest element of and hence
(because hence and so on.)
From (4.5) it follows that is a well-defined polynomial for each permutation
If and we denote by the permutation
in We have then
where is the identity element of
We shall make use of the following fact: if is a polynomial in and for all then is a constant. For for some and is symmetric in because
To prove (4.6) we proceed by induction on If then and both sides of (4.6) are equal to Let
By the remark above, it is enough to show that for each
Suppose first that Then
because by (4.2). Hence we have if and if then
which is zero by the inductive hypothesis.
Likewise, if we have
and so again by the inductive hypothesis.
Finally, if we have because
and therefore kills and moreover, because Hence and the proof is complete.
For certain classes of permutations there are explicit formulas for We consider first the case where is dominant, of shape (so that the diagram of coincides with the diagram of
(4.7) If is dominant of shape then
We use descending induction on where The result is true for by (4.3)(i), since is dominant of shape
Suppose and is dominant of shape Then and Let be the largest integer such that for and let Then is dominant of length and where is the vector whose component is and all other components zero. Hence we have
Conversely, every monomial (where is a partition) occurs as a Schubert polynomial, namely as where is the permutation with code
Suppose next that is Grassmannian, with descent at
(4.8) If is Grassmannian of shape then is the Schur function where is the unique descent of and
We may assume that (by (4.3)(i), Then and the code of is
so that Let be the longest element of Then
is dominant of shape where and Hence
by (4.2), (4.7) and (2.11).
Conversely, every Schur function (where is a partition of length occurs as a Schubert polynomial, namely as where is the permutation with code
More generally, let be vexillary with shape (where and flag (Chapter I). Then is a multi-Schur function (Chapter III), namely
where for each
The idea is to convert systematically into a dominant permutation. Recall ((1.23), (1.24)) that if and for some then and
As in Chapter I let
where (and each and let
Consider first the terms equal to in the sequence They occupy the positions We shall use to move them all to the left until they occupy the first positions, by multiplying on the right by
Let In the code of the first entries will be equal to the shape of is
and it follows from the description (1.38) of vexillary codes that the terms equal to in the sequence will occupy the positions The next step is to move those to the left until they occupy the positions by multiplying on the right by
Let the code of starts off with entries to then entries equal to the shape of is
and the terms equal to in the sequence will occupy the positions
We continue in this way; at the stage we define where
and has shape
where by (1.36). Notice also that
Finally we reach which is dominant with shape (and code)
and therefore, since
by (4.2). Now by (4.6) and (3.5') we have
where Hence by repeated use of (3.10) we obtain
by virtue of (3.6). If we now operate with we shall obtain in the same way
and so finally
Remarks. 1. As in Chapter I, let
be the conjugate partition, so that
by (1.41), where is the flag of Thus
2. The result (4.9) admits a converse. If as above, every non-zero multi-Schur function that satisfies the conditions of the duality theorem (3.8''), namely
is the Schubert polynomial of a vexillary permutation, namely the permutation with shape and flag This follows from (1.38) and (4.9), since the conditions (1) on the flag coincide with those of (1.37). (The conditions (1.36), namely
ensure that the multi-Schur function does not vanish indentically.)
Let denote the additive subgroup of spanned by the monomials
(4.11) The Schubert polynomials form a of
By (4.3) each lies in If
is a linear dependence relation, then by homogeneity we have
for each and by operating on (1) with we see that Hence the are linearly independent and hence form a of It follows that each monomial can be expressed in the form
with rational coefficients by operating on (2) with we have and hence the are integers.
From (4.11) it follows that
(4.12) The form a of
Let be a monomial in Then for sufficiently large hence is a linear combination of the
For each let denote the set of all permutations such that or equivalently such that the code of has length
(4.13) The form a of
By (4.3)(iii) we have
Let be the of the If choose by (4.12) we can write as a linear combination of Schubert polynomials, say
where there is at least one term with and Hence for some we have and since we obtain from (1) a nontrivial linear dependence relation among the Schubert polynomials, contradicting (4.12). Hence which proves (4.13).
Let be the homomorphism defined by In other words, is the constant term of for each polynomial The expression of in terms of Schubert polynomials is then
By (4.13) and linearity, it is only necessary to verify this formula when is a Schubert polynomial and then it follows from (4.2) and (4.3)(ii) that is equal to when and is zero otherwise.
(4.15) Let be a homogeneous linear polynomial, and let be a permutation. Then
where is the transposition that interchanges and and the sum is over all pairs such that
The polynomial is homogeneous of degree and hence by (4.14) we have
summed over of length Now by (2.13)
summed over such that It follows that if and is zero otherwise.
summed over transpositions such that where or according as or
(4.15'') (Monk's formula) summed over transpositions such that and
Remark. As pointed out by A. Lascoux, Monk's formula (4.15'') (which is the counterpart of Pieri's formula in the theory of Schur functions) characterizes the algebra of Schubert polynomials.
We shall apply (4.15') in the following situation. Suppose that is the last descent of so that and Choose the largest such that and let Then from (4.15') applied to we have
summed over all permutations where and Hence and for
Let us arrange the permutations of a given length in reverse lexicographical ordering, so that if then precedes if and only if for some we have
For this ordering there is a first element, namely the permutation
We have proved
(4.16) For each permutation the Schubert polynomial can be expressed in the form
where is the last descent of and each in the sum precedes in the reverse lexicographical ordering.
From (4.16) we deduce immediately that
(4.17) For each permutation is a polynomial in with positive integral coefficients.
For we may assume, as inductive hypothesis, that (4.17) is true for all permutations such that either or and precedes in the reverse lexicographical ordering; and then (4.16) shows that the result is true for (The permutation has code hence is dominant with Schubert polynomial by (4.7)·)
Now fix integers such that and let so that By (4.12) we can express uniquely in the form
summed over and
(4.19) The coefficients in (4.18) are non-negative integers.
We proceed by induction on Suppose first that and that so that Then there exists such that From (4.18) we conclude that hence is equal to and therefore we have and By the inductive hypothesis, we conclude that if
It remains to consider the case Let be the homomorphism for which if and if From (4.18) we have
Let be the last descent of If then and hence so that is equal to if and is zero otherwise. If we deduce from (4.16) that
Let be a "diagram", which for present purposes means any finite non empty set of lattice points in the positive quadrant Choose a point which is rightmost in its row, and suppose that not all the points directly above belong to If is the largest integer less than such that let denote the diagram obtained from by replacing by We can then repeat the process on by choosing the rightmost element in some row, and obtain a diagram and so on. Let denote the set of all diagrams (including itself) obtainable from by a sequence of such moves.
Next, we associate with each diagram a monomial
where is the number of elements of in the row, i.e., the number of such that
With this notation established, Kohnert's algorithm states that
(4.20) For each permutation we have
where is the diagram (1.20) of
Example. If consists of the diagrams
A proof of a related algorithm by N. Bergeron is given in the Appendix to this chapter. The present status of (4.20) is that it is true for vexillary [Koh1990], but open in general.
Let and let Then
is independent of because if is symmetrical in and and in particular if does not contain
The operator is called the shift operator. For example, we have
so that by (4.4)
(4.22) For all permutations
where is the permutation
For each let be the longest element of and let Then if we have
Now is the cycle and hence
and therefore by (2.7) we have
(4.23) Let and Then
Since this follows from (3.10).
(4.24) We have
By (4.12) it is enough to show that for all permutations and this follows from (4.22) and (4.2).
For each let be the homomorphism defined by
(4.25) Let be the longest element of Then
By linearity we may assume that where Since by (3.5'), we have
by (4.23), and hence
which is equal to by (2.16')·
A transition is an equation of the form
where and are permutations and is a set of permutations. It exists only for certain values of depending on An example is (4.16), in which is the last descent of
By (4.15') we have
summed over transpositions such that where is the sign of So for to hold there must be exactly one such that
Consider the graphs and of and They differ only in rows and
By (1.10) the relation (1) above is equivalent to where is the open region indicated in the diagram. Moreover, is the only integer such that and and this will be the case if and only if is empty. Since it follows that
(4.26) There is a transition if and only if
From (4.26) it follows that if exists we must have i.e., must be a descent of Hence
where (resp. is the first (resp. last) descent of (In terms of the code is the first descent of the sequence and is the largest such that In general, not all descents of will give rise to transitions, but the last descent always does, by (4.16).
Consider next the set of permutations that feature in Each is of the form with and Again by (1.10), this means that
is empty, where is the open region indicated in the diagram above.
The element of for which is maximal is called the leader of Thus is the leader if and only if
Remark (4.28). The set will be empty if and only if there is no such that We can always avoid this possibility by replacing by If is not empty, then is a bijection of onto
The condition (4.26) is stable under reflection in the main diagonal, which interchanges and Hence
(4.29) The transition exists if and only if exists, where Moreover we have
so that is the relation
We may notice directly one corollary of (4.29). Let
be the number of monomials in each counted with its multiplicity. (By (4.17), is a positive sum of monomials.) If is a transition, we have
and also, by (4.29)
From these two relations it follows, by induction on and on the integer that
or in other words that and each contain the same number of monomials. So if Kohnert's algorithm (4.20) is true, we should have
Doubtless the combinatorialists will seek a "bijective" proof of this fact.
Let be a transition and let Consider again the graphs of and
Let denote respectively the number of points of (or equivalently in the open regions of (The regions marked with a zero contain no graph points.) Then we have
and if In particular, for all
is the number of positive integers such that hence is equal to Similarly for the other assertions.
Suppose first that i.e (by (4.27)) that is the leader of Then from (4.31) we have and Hence in this case and therefore
If on the other hand there are two possibilities:
In both cases it follows that is of the form where is a raising operator and Hence (for the dominance partial ordering on partitions), and we have proved
(4.32) If is a transition, we have for all with equality if and only if is the leader of
Recall (1.26) that for any permutation we have
Hence for we have
by (4.29) and (4.32). Moreover, at least one of the inequalities is strict unless is the leader of and is the leader (in the notation of (4.29)). In the notation of the diagram preceding (4.27) this means that
and hence, as in the proof of (4.26), that
(4.34) If is a transition with vexillary, then is either empty or consists of one vexillary permutation.
Suppose that is not empty, and let By (1.27) we have and hence all the inequalities in (4.33) are equalities. Thus is vexillary, and by the remarks above it is the only member of
(4.35) Let be a transition with Then
As before, let with and let We have to show that
We distinguish three cases:
The maximal transition for is Let us temporarily write to mean that
(4.36) Suppose that
is a chain of maximal transitions in which none of the is Grassmannian. Then
For any permutation let Also let denote the last nonzero term in the sequence i.e. Recall that is Grassmannian if and only if it has only one descent, that is to say if and only if
From (4.35) we have
for and from (4.31) we have
where Hence and therefore
Moreover, if we must have and hence by (1)
It follows that the points are all distinct. Since they all satisfy and we have as required.
In what follows we shall when necessary replace a permutation by in order to ensure that at each stage the set is not empty (4.28). Observe that this replacement does not change the bound in (4.36).
The rooted tree of a permutation defined as follows:
|(i)||if is vexillary, then|
|(ii)||if is not vexillary, take the maximal transition for|
where (If is empty, replace by as explained above.) To obtain join by an edge to each and attach to each its tree
By (4.36), is a finite tree, and by construction all its endpoints are vexillary permutations of length It follows from (4.28) that is a bijection of onto Thus depends (up to isomorphism) only on the diagonal equivalence class (Chapter I) of the permutation
Recall that is the homomorphism defined by if and if
(4.37) Let be the set of endpoints of Then if we have
If is vexillary we have by (4.4), since If is not vexillary, it follows from the maximal transition above that
since The result now follows by induction on
Let be partitions and let be Grassmannian permutations of shapes respectively. Let so that by (4.6) and (4.8)
where and Hence if we have
and so by (4.37)
where is the set of endpoints of the tree Here the integer can be arbitrarily large, because we can replace by for any positive integer Consequently we have
where is the set of endpoints of the tree and (resp. is Grassmannian of shape (resp.
The same argument evidently applies to the product of any number of Schur functions. If are partitions, let be a Grassmannian permutation of shape for each (so that and let Then
where is the set of endpoints of the tree
In particular, suppose that each is one-part partition, say so that the left-hand side of (4.38') becomes Correspondingly, each is a cycle of length namely Now [Mac1979, Ch.I, §6] the coefficient of a Schur function in is the Kostka number Hence we have
(4.39) is the number of endpoints of shape in the tree of
Schubert polynomials for
This is a typed excerpt of the book Notes on Schubert Polynomials by I. G. Macdonald.