MITOSIS RECURSION FOR COEFFICIENTS OF SCHUBERT POLYNOMIALS

EZRA MILLER

Abstract. Mitosis is a rule introduced in [KM02a] for manipulating subsets of the n × n grid. It provides an algorithm that lists the rc-graphs [FK96, BB93] for a permutation w ∈ S_{n} by downward induction on weak Bruhat order, thereby generating the coefficients of Schubert polynomials [LS82] inductively. This note provides a short and purely combinatorial proof of these properties of mitosis.

1. Introduction

It has been a goal for some years, ever since Kohnert made his conjecture in [Koh91], to find inductive combinatorial rules on diagrams in the n × n grid that yield the coefficients of Schubert polynomials [LS82], when counted properly. The mitosis rule was offered in [KM02a] as a solution to this problem, but the proof was long, and involved some notions that strayed rather far from the elementary combinatorics of permutations. The purpose of this note is to bring mitosis entirely into the realm of combinatorics, by giving a short combinatorial proof of the fact (Theorem 14) that mitosis lists rc-graphs [FK96, BB93] recursively by induction on weak order in S_{n}, starting from the unique rc-graph for the long permutation w_{0}.

More precisely, the proof here of Theorem 14, and the resulting diagrammatic recursion for the coefficients of Schubert polynomials in Corollary 15, rests only on the formula of Billey, Jockusch, and Stanley (Theorem 4), the characterization of Schubert polynomials by divided differences (Definition 3), and elementary combinatorial properties of rc-graphs (Lemmas 5, 9, and 12 plus Proposition 13). Mitosis serves as a geometrically motivated improvement on Kohnert’s rule [Koh91, Mac91, Win99], its advantages being the short combinatorial proof here and consistency with double Schubert polynomials as in [KM02a].

The plan of the paper is as follows. In the next two sections we review the definition of the set RC(w) of rc-graphs for a permutation w ∈ S_{n}, the BJS formula, and the mitosis algorithm on pipe dreams (subsets of the n × n grid). Section 4 provides an involution on RC(w) that is crucial for the proof of the main theorem and corollary in Section 5. The final section, which concerns the mitosis poset and is logically independent of the other sections, reviews for the reader’s convenience two definitions and a conjecture from [KM02a, Section 2.2], because of their relevance in this combinatorial setting.

2. Pipe dreams and rc-graphs

Consider a square grid ℤ_{>0} × ℤ_{>0} extending infinitely south and east, with the box in row i and column j labeled (i, j), as in an ∞ × ∞ matrix. If each box in the grid is covered with a square tile containing either or [figure] , then one can think of the tiled grid as a network of pipes.

Date: 3 February 2002.

The author was supported by the Sloan Foundation and NSF.

Definition 1. A pipe dream is a finite subset of ℤ_{>0} ×ℤ_{>0}, identified as the set of crosses in a tiling by crosses and elbow joints [figure] . A pipe dream is an rc-graph if each pair of pipes crosses at most once. The set RC(w) of rc-graphs for the permutation w ∈ S_{n} is the set of rc-graphs D such that the pipe entering row i exits from column w(i).

Although we always draw crossing tiles as some sort of cross (either ‘+’ or ‘ ’, the former with the square tile boundary and the latter without), we often leave the elbow tiles blank or denote them by dots, to make the diagrams easier to parse. Viewing n as fixed, we shall be interested in pipe dreams contained in the pipe dream D_{0} that has crosses in the triangular region strictly above the main antidiagonal (in spots (i, j) with i + j ≤ n) and elbow joints elsewhere in the square grid [n] × [n] of size n. Note that D_{0} is the unique rc-graph for the long permutation w_{0} = n … 321 in S_{n}.

Example 2. The pipe dream D in Fig. 1 for n = 8 is an rc-graph for the permutation w = 13865742 ∈ S_{8}. For clarity, we omit the square tile boundaries as well as the wavy

D = + + + +  + + + + + + + + + +  = [figure: 1 2 3 4 5 6 7 8; 1; 3; 8; 6; 5; 7; 4; 2]

Figure 1. An rc-graph for w = 13865742 ∈ S_{8}

“sea” of elbows [figure] below the main antidiagonal in the right pipe dream. □

Since we need a statement of the BJS formula, we recall here the definition of Schubert polynomials of Lascoux and Schützenberger via divided differences.

Definition 3 ([LS82]). The i^{th} divided difference operator ∂_{i} takes each polynomial f ∈ ℤ[x_{1}, …, x_{n}] to

∂_{i}f(x_{1}, …, x_{n}) = \frac{f(x_{1}, …, x_{n}) − f(x_{1}, …, x_{i−1}, x_{i+1}, x_{i}, x_{i+2}, …, x_{n})}{x_{i} − x_{i+1}}.

The Schubert polynomial for w ∈ S_{n} is defined by the recursion

𝔖_{ws_{i}}(x_{1}, …, x_{n}) = ∂_{i}𝔖_{w}(x_{1}, …, x_{n})

whenever length(ws_{i}) < length(w), and the initial condition 𝔖_{w_{0}}(x_{1}, …, x_{n}) = ∏_{i=1}^{n} x_{i}^{n−i}.

Theorem 4 ([BJS93, FS94]). 𝔖_{w}(x_{1}, …, x_{n}) = ∑_{D∈RC(w)} x^{D}, where x^{D} = ∏_{(i,j)∈D} x_{i}.

The next lemma, which will be applied in Section 5, gives a criterion for when removing a ‘+’ from a pipe dream D ∈ RC(w) leaves a pipe dream in RC(ws_{i}). Specifically, it concerns the removal of a cross at (i, j) from configurations that look like

\begin{aligned}& 1 & ⋯ & j \\ i & & & & … \\ i+1 & & & [figure] \end{aligned} = \begin{aligned}& 1 & & & ⋯ & & & j \\ i & + & + & + & + & + & + & + & + & … \\ i+1 & + & + & + & + & + & + & + & · \end{aligned}

at the left end of rows i and i + 1 in D.

Lemma 5. Let D ∈ RC(w) and j be a fixed column index with (i+1, j) ∉ D, but (i, p) ∈ D for all p ≤ j, and (i + 1, p) ∈ D for all p < j. Then length(ws_{i}) < length(w), and if D′ = D ∖ (i, j) then D′ ∈ RC(ws_{i}).

Proof. Removing (i, j) only switches the exit points of the two pipes starting in rows i and i + 1, so the pipe starting in row k of D′ exits out of column ws_{i}(k) for each k. No pair of pipes can cross twice in D′ because there are length(ws_{i}) crossings.

3. Mitosis algorithm

Given a pipe dream in [n] × [n], define

(1)  start_{i}(D) = column index of leftmost elbow in row i
= min({j | (i, j) ∉ D} ∪ {n + 1}),

so the i^{th} row of D is filled solidly with crosses in the region to the left of start_{i}(D). Let

J_{i}(D) = {columns j strictly to the left of start_{i}(D) | (i + 1, j) has no cross in D}.

For p ∈ J_{i}(D), construct the offspring D_{p} as follows. First delete the cross at (i, p) from D. Then take all crosses in row i of J_{i}(D) that are to the left of column p, and move each one down to the empty box below it in row i + 1.

Definition 6. The i^{th} mitosis operator sends a pipe dream D to

mitosis_{i}(D) = {D_{p} | p ∈ J_{i}(D)}.

Write mitosis_{i}(P) = ⋃_{D∈P} mitosis_{i}(P) whenever P is a set of pipe dreams.

Observe that all of the action takes place in rows i and i+1, and mitosis_{i}(D) is an empty set whenever J_{i}(D) is empty.

Example 7. The pipe dream D at left is the rc-graph for w = 13865742 from Example 2:

{3 \atop 4} \begin{aligned}+ & + & + \\ & + & & + \\ + & + & + & + \\ & & + \\ + \\ + & + \\ + \\ & & & ↑ \\ start & 3 \end{aligned}  ⟼ \{ \begin{matrix}& + & & + & + \\ & + & & & & + \\ & + & + & + \\ & & + \\ + \\ + & + \\ + \end{matrix}  , + + + +  + + + + + + + + +  , \begin{matrix}& + & & + & + \\ & + & & & & + \\ & & + \\ + & + & + \\ + \\ + & + \\ + \end{matrix}  \}

The set of three pipe dreams on the right is obtained by applying mitosis_{3}, since J_{3}(D) consists of columns 1, 2, and 4. The offspring are ordered as in Proposition 10, below. □

In Proposition 10 we shall present another, more sequential way of writing down the mitosis offspring of a pipe dream. It uses a device invented by Bergeron and Billey.

Definition 8 ([BB93]). A chutable rectangle is a connected 2 × k rectangle C inside a pipe dream D such that k ≥ 2 and all but the following 3 locations in C are crosses: the northwest, southwest, and southeast corners. Applying a chute move to D is accomplished by placing a ‘+’ in the southwest corner of a chutable rectangle C and removing the ‘+’ from the northeast corner of the same C.

Heuristically, a chute move therefore looks like:

\begin{aligned}& & & & & & & & ... \\ & · & + & + & … & + & + & + \\ & · & + & + & & + & + & · \\ ... \end{aligned} ⇝^{chute}  \begin{aligned}& & & & & & & & ... \\ & · & + & + & … & + & + & · \\ & + & + & + & & + & + & · \\ ... \end{aligned}

The following basic fact about chute moves was discovered by Bergeron and Billey [BB93].

Lemma 9. The set RC(w) of rc-graphs for w is closed under chute moves.

Proof. If two pipe intersect at the ‘+’ in the northeast corner of a chutable rectangle C, then chuting that ‘+’ only changes the crossing point of the two pipes to the southwest corner of C. No other pipes are affected.

Proposition 10. Let D be a pipe dream, and suppose j is the smallest column index such that (i+1, j) ∉ D and (i, p) ∈ D for all p ≤ j. Then D_{p} ∈ mitosis_{i}(D) is obtained from D by

1. removing (i, j), and then

2. performing chute moves from row i to row i + 1, each one as far left as possible, so that (i, p) is the last ‘+’ removed.

Proof. Immediate from Definitions 6 and 8.

4. Intron mutation

Definition 11. Let D be a pipe dream and i a fixed row index. Order the boxes in rows i and i + 1 of D as in the following diagram:

1 2 3 4 ⋯
i  1 3 5 7 …
i+1 2 4 6 8

An intron^{1} in these two adjacent rows is a 2 × k rectangle C such that 1. the first and last boxes in C (the northwest and southeast corners) are elbows; and 2. no elbow in C is northeast or southwest of another elbow (but due north or due south

is okay). If C satisfies the following extra condition, then C is called a maximal intron:

3. the elbow with largest index before C (if there is one) resides in row i + 1, and the elbow with smallest index after C (if there is one) resides in row i.

Lemma 12. Given an intron C in an rc-graph, there is a unique intron τ(C) such that 1. the sets of columns with exactly two crosses are the same in C and τ(C), and

2. the number c_{i} of crosses in row i of C equals the number c_{i+1} of crosses in row i + 1

of τ(C), and conversely. The involution τ, called intron mutation, is always accomplished by a sequence of chute moves or inverse chute moves (because C is part of an rc-graph). □

Proof. First assume c_{i} > c_{i+1} and work by induction on c = c_{i} − c_{i+1}. If c = 0 there is nothing to prove. If c > 0 then consider the leftmost ‘+’ in row i of C that has an elbow under it in row i + 1. Moving left from the column containing this ‘+’ , there must be a column encountered that does not have crosses in both of rows i and i + 1, because the northwest entry of C is an elbow. We claim that the first such column without two crosses has no crosses at all. Indeed, the row i entry in this column must be an elbow by construction; the row i + 1 entry cannot be a cross because the pipes crossing there would also cross at the original ‘+’ . This means we can chute the original ‘+’ into this first column with no crosses, and proceed by induction.

1For the origin of this term, see [KM02a, Section 3.5].

Flip the argument 180^{∘} if c_{i} < c_{i+1}, so the chute move becomes an inverse chute.

For example, here is an intron mutation accomplished by chuting the crosses in columns 4, 6, and then 7 of row i; the zigzag shapes formed by the dots in these introns are typical.

[figure: 4  6 7; i; i+1]  =  \begin{aligned}& & & & 4 & & 6 & 7 \\ i & · & · & + & + & + & + & + & + \\ i+1 & + & · & + & · & + & · & · & · \end{aligned}
τ ↓  τ ↓
[figure: i; i+1]  =  \begin{matrix}i & · & · & + & · & + & · & · & + \\ i+1 & + & + & + & + & + & + & · & · \end{matrix}

Proposition 13. For each i there is an involution τ_{i} : RC(w) → RC(w) such that τ_{i}^{2} = 1, and for all D ∈ RC(w):

1. τ_{i}D agrees with D outside rows i and i + 1.

2. start_{i}(τ_{i}D) = start_{i}(D), and τ_{i}D agrees with D strictly west of this column.

3. ℓ_{i}^{i}(τ_{i}D) = ℓ_{i+1}^{i}(D), where ℓ_{r}^{i}(−) is the number of crosses in row r that are east of or in column start_{i}(−).

Proof. Let D ∈ RC(w). Consider the union of all columns in rows i and i + 1 of D that are east of or coincide with column start_{i}(D). Since the first and last boxes in this region (numbered as in Definition 11) are elbows, this region breaks uniquely into a disjoint union of 2×k rectangles, each of which is either a maximal intron or completely filled with crosses. Indeed, this follows from (1) and Definition 11. Applying intron mutation to each maximal intron therein leaves a pipe dream that breaks up uniquely into maximal introns and solid crosses in the same way. Therefore the lemma comes down to verifying that intron mutation preserves the property of being in RC(w), which comes from Lemmas 9 and 12.

5. Mitosis theorem

Theorem 14. If length(ws_{i}) < length(w), then the set RC(ws_{i}) of rc-graphs for ws_{i} is the disjoint union · ⋃_{D∈RC(w)} mitosis_{i}(D). Therefore

(2)  RC(w) = mitosis_{i_{k}} ⋯ mitosis_{i_{1}}(D_{0})

if s_{i_{1}} ⋯ s_{i_{k}} is a reduced expression for w_{0}w.

Proof. Use the description of mitosis in Proposition 10 along with Lemmas 5 and 9 to conclude that mitosis_{i}(D) consists of rc-graphs for ws_{i} whenever D ∈ RC(w). It follows directly from the definitions that mitosis_{i}(D) ∩ mitosis_{i}(D′) = ∅ if D ≠ D′ are rc-graphs for w. Thus it suffices to prove that mitosis_{i}(RC(w)) has the same cardinality as RC(ws_{i}).

Fix D ∈ RC(w), write x^{D} = ∏_{(i,j)∈D} x_{i}, and let J = |J_{i}(D)| be the number of mitosis offspring of D. The monomial x^{D} is a product x_{i}^{J}x^{D′}, where D′ is the pipe dream (not an rc-graph) obtained from D by erasing the crosses in row i of J_{i}(D). Definition 6 implies that

(3)  ∑_{E∈mitosis_{i}(D)} x^{E} = ∑_{d=1}^{J} x_{i}^{J−d}x_{i+1}^{d−1} · x^{D′} = ∂_{i}(x_{i}^{J}) · x^{D′}.

If τ_{i}D = D, then x^{D′} is symmetric in x_{i} and x_{i+1} by Proposition 13, so that

∂_{i}(x_{i}^{J}) · x^{D′} = ∂_{i}(x_{i}^{J} · x^{D′}) = ∂_{i}(x^{D})

in this case. On the other hand, if τ_{i}D ≠ D, then letting s_{i} act on polynomials by switching x_{i} and x_{i+1}, Proposition 13 implies that adding the sums in (3) for D and τ_{i}D yields

∂_{i}(x_{i}^{J}) · (x^{D′} + s_{i}x^{D′}) = ∂_{i}(x_{i}^{J}(x^{D′} + s_{i}x^{D′})) = ∂_{i}(x^{D} + x^{τ_{i}D}).

Pairing off the elements of RC(w) not fixed by τ_{i}, we therefore conclude that

∑_{E∈mitosis_{i}(RC(w))} x^{E} = ∂_{i}( ∑_{D∈RC(w)} x^{D}) = ∂_{i}(𝔖_{w}(x)) = 𝔖_{ws_{i}}(x) = ∑_{E∈RC(ws_{i})} x^{E}

by Theorem 4 and the recursion for 𝔖_{w}(x) := 𝔖_{w}(x_{1}, …, x_{n}) as in Definition 3. Plugging in 1, …, 1 for x = x_{1}, …, x_{n} implies that |mitosis_{i}(RC(w))| = |RC(ws_{i})|, as desired.

Finally we come to the generation of Schubert coefficients by induction on weak Bruhat order via mitosis. For notation, if v = s_{i_{1}} ⋯ s_{i_{k}} is a reduced expression, set mitosis_{v} = mitosis_{i_{k}} ⋯ mitosis_{i_{1}}.

Corollary 15. For any permutation w ∈ S_{n} we have

𝔖_{w}(x_{1}, …, x_{n}) = ∑_{D∈mitosis_{v}(D_{0})} x^{D}  for v = w_{0}w,

where RC(w_{0}) = {D_{0}}, and x^{D} = ∏_{(i,j)∈D} x_{i} for any pipe dream D.

Proof. Theorem 14 and Theorem 4.

6. Mitosis poset

The next definition generalizes to arbitrary n the poset of rc-graphs for n = 3 in Fig. 2.

Definition 16 ([KM02a, Definition 2.2.4]). Theorem 14 defines a partial order, namely

D′ ≺ D if D′ ∈ mitosis_{i}(D) for some i,

making the set RC_{n} = ⋃_{w∈S_{n}} RC(w) of rc-graphs for all of S_{n} into the mitosis poset.

The poset RC_{n}, which is ranked by length = cardinality, fibers over the weak Bruhat order on S_{n}, with the preimage of w ∈ S_{n} being RC(w). A reduced expression for w_{0}w can be thought of as the edge labels on a decreasing path beginning at w_{0} and ending at w in the weak Bruhat order on S_{n}. The preimage in RC_{n} of such a path is a tree having RC(w) among its leaves (two rc-graphs cannot share an offspring by the disjointness of the union in Theorem 14).

Definition 17. A path decreasing from w_{0} to w in the weak order is poptotic if the leaves of its preimage in RC_{n} are precisely RC(w).

In other words, a path is poptotic if every rc-graph lying over its interior has at least one offspring. For example, the right hand path in Fig. 2 from 321 to 123 is poptotic because only one rc-graph appears at each stage, while the left path is apoptotic^{2} because the first rc-graph for 132 has no offspring under mitosis_{2}.

Poptotic paths from w_{0} to w always exist. Indeed, the lexicographically first reduced expression for w_{0}w (in which s_{1} > s_{2} > ⋯ > s_{n−1}) always corresponds to a poptotic path. In particular, the lex first path from w_{0} to id_{n} passes through permutations with exactly one rc-graph (each is a dominant permutation, whose unqiue rc-graph is a Young diagram).

2The word ‘apoptosis’ refers in biology to programmed cell death, where some cell in a multicellular organism commits suicide for the greater good of the organism. Thus apoptotic indicates that some rc-graph dies along the path without offspring, while poptotic indicates that all rc-graphs survive with offspring.

321

+ + +

s^{2}⧸  ⧹^{s^{1}}

s^{1}/ \^{s}^{1}_{132 ^{+}  +}^{312 ^{+ +}}  |^{s}^{2}_{^{+}  213}^{^{+ +}  231}

s_{2}⧹  ⧸_{s_{1}}

123

Figure 2. Hasse diagram for RC_{3}

Example 18. The three pipe dreams on the right in Example 7 are all rc-graphs for v = 13685742 = w · s_{3}, where w = 13865742 as in Example 2. Setting i = 4 and inspecting the inversions of v, we find that length(vs_{4}) < length(v). On the other hand, mitosis_{4} kills the first two of the three rc-graphs, whereas the last has two offspring. Thus any path from w_{0} to vs_{4} ending with (…, v, vs_{4}) is necessarily apoptotic.

Note that the lex first reduced expression for w_{0}v, which corresponds to a poptotic path from w_{0} to v as mentioned above, equals s_{2}s_{1}s_{3}s_{5}s_{4}s_{3}s_{2}s_{1}s_{7}s_{6}s_{5}s_{4}s_{3}s_{2}s_{1}, while the lex first reduced expression for w_{0}vs_{4} equals s_{2}s_{1}s_{3}s_{2}s_{5}s_{4}s_{3}s_{2}s_{1}s_{7}s_{6}s_{5}s_{4}s_{3}s_{2}s_{1} (the s_{2} in the fourth slot is new). □

Whether or not a path from w_{0} to w is poptotic, breadth-first search on the preimage tree (ordering the mitosis offspring as in Proposition 10) yields a total order on RC(w). It can be shown that poptotic total orders by breadth-first search are linear extensions of the partial order on rc-graphs determined by chute operations.

Define the simplicial complex L_{w} with vertex set [n] × [n] to have as its facets the complements of the rc-graphs for w:

facets(L_{w}) = {([n] × [n]) ∖ D | D ∈ RC(w)}.

This is an example of a ‘subword complex’ [KM02a, KM02b], and is hence shellable by [KM02a, Theorem A.4]. Through heuristic arguments, computer calculations in small symmetric groups, we are convinced of the following.

Conjecture 19. Poptotic orders on RC(w) by breadth-first search yield shellings of L_{w}.

To emphasize: shellability is not in question, because shellings of L_{w} appear in [KM02a, Theorem A.4 and Section 3.9]. The conjecture would just give more intuitive shellings than those known. It is conceivable that all of the apoptotic total orders are shellings, too, although this seems less likely.

Acknowledgements. The author is grateful to Allen Knutson, Cristian Lenart, Vic Reiner, and Anne Schilling for motivation and inspiration. Mitosis was discovered in part because of a superb AMS meeting on Modern Schubert Calculus organized by Frank Sottile and Nantel Bergeron (the latter also supplied L^{A}TEXmacros for drawing pipe dreams).

References

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

[BJS93] Sara C. Billey, William Jockusch, and Richard P. Stanley, Some combinatorial properties of Schubert polynomials, J. Algebraic Combin. 2 (1993), no. 4, 345–374.

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

[FS94] Sergey Fomin and Richard P. Stanley, Schubert polynomials and the nil-Coxeter algebra, Adv. Math. 103 (1994), no. 2, 196–207.

[KM02a] Allen Knutson and Ezra Miller, Gröbner geometry of Schubert polynomials, Preprint, available at http://www-math.mit.edu/˜ ezra, 2002, submitted.

[KM02b] Allen Knutson and Ezra Miller, Subword complexes in Coxeter groups, preprint available at http://www-math.mit.edu/˜ ezra, 2002.

[Koh91] Axel Kohnert, Weintrauben, Polynome, Tableaux, Bayreuth. Math. Schr. (1991), no. 38, 1–97, Dissertation, Universität Bayreuth, Bayreuth, 1990.

[LS82] Alain Lascoux and Marcel-Paul Schützenberger, Polynômes de Schubert, C. R. Acad. Sci. Paris Sér. I Math. 294 (1982), no. 13, 447–450.

[Mac91] I. G. Macdonald, Notes on Schubert polynomials, Publications du LACIM, Universitè du Québec à Montréal, 1991.

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

Mathematics Department, MIT, Cambridge, Massachusetts

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