Lattice graphs and Schubert polynomials

Alain Lascoux, Hui Lin and Arthur L. B. Yang

Abstract. We define new planar combinatorial objects that we call lattice graphs. We generalize divided differences into operators, still satisfying braid relations, and operating on the space of lattice graphs. This allows us to interpret Schubert polynomials as sums of lattice graphs. By putting appropriate weights on lattice graphs, we recover the usual Schubert polynomials in two sets of variables.

Keywords: divided differences, Schubert polynomials, lattice graphs

1. Introduction

Schubert polynomials, defined in [12, 10, 13], were motivated by the geometry of flag manifolds, following the work of Bernstein-Gelfand-Gelfand [2] and Demazure [5]. They have been extensively studied by many authors [1, 3, 4, 6, 7, 8, 9, 17, 19, 20, 21]. More details can be found in [11, 18].

Let v = [v_{1}, v_{2}, …, v_{n}] be a permutation in the symmetric group 𝔖_{n} on n elements {1, 2, …, n}. Let s_{i} denote the simple transposition that interchanges i, i + 1. It is well known that s_{1}, s_{2}, …, s_{n−1} generate 𝔖_{n}, and satisfy the braid relations

s_{i}s_{j} = s_{j}s_{i} for |i − j| > 1,  (1.1)
s_{i}s_{i+1}s_{i} = s_{i+1}s_{i}s_{i+1}.  (1.2)

together with s_{i}^{2} = 1. For v ∈ 𝔖_{n}, for i = 1, …, n, let c_{i}(v) = #{j : i < j and v_{i} > v_{j}}. Then c(v) = [c_{1}(v), c_{2}(v), …, c_{n}(v)] is called the code of v, and ℓ(v) = ∑_{i=1}^{n} c_{i}(v) is the length of v, i.e., the number of inversions of v. A decomposition v = s_{r_{1}}s_{r_{2}} ⋯ s_{r_{p}} is reduced iff p = ℓ(v). We rather use the reduced word r_{1}r_{2} ⋯ r_{p}. Let R(v) denote the set of all reduced words of a permutation v. The maximal permutation v_{0} of 𝔖_{n} is [n, n − 1, …, 1]. One may check that

(s_{n−1} ⋯ s_{1})(s_{n−1} ⋯ s_{2}) ⋯ (s_{n−1}s_{n−2})(s_{n−1})

is a reduced decomposition of v_{0} (we add parentheses in order to distinguish canonical factors). The following lemma is straightforward:

Lemma 1.1 Given a permutation v ∈ 𝔖_{n}, let c = [c_{1}, c_{2}, …, c_{n}] be its code, then the concatenation of right factors of the factors of

(s_{n−1} ⋯ s_{1})(s_{n−1} ⋯ s_{2}) ⋯ (s_{n−1})( ) ,

of respective lengths c_{1}, c_{2}, …, c_{n}, is a reduced decomposition of v.

For example, v = [3, 1, 6, 2, 5, 4] has code c(v) = [2, 0, 3, 0, 1, 0], and the above decomposition is v = (s_{2}s_{1})( )(s_{5}s_{4}s_{3})( )(s_{5})( ).

Let ℤ[a_{1}, a_{2}, …, a_{n}] denote the ring of polynomials in n commutative variables with coefficients in ℤ. For any 1 ⩽ i ⩽ n − 1, the simple divided difference ∂_{i} is the operator:

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

Divided differences satisfy the braid relations

∂_{i}∂_{j} = ∂_{j}∂_{i} for |i − j| > 1,  (1.3)
∂_{i}∂_{i+1}∂_{i} = ∂_{i+1}∂_{i}∂_{i+1}.  (1.4)

together with ∂_{i}^{2} = 0. Thanks to these relations, one can define ∂_{v} by taking any reduced word r_{1}r_{2} ⋯ r_{p} and putting ∂_{v} = ∂_{r_{1}}∂_{r_{2}} ⋯ ∂_{r_{p}}. When r_{1}r_{2} ⋯ r_{p} is not reduced, then ∂_{r_{1}}∂_{r_{2}} ⋯ ∂_{r_{p}} = 0. We do not follow the conventions of Lascoux-Schützenberger and write divided differences or permutations on the left of the operand.

Divided differences satisfy Leibnitz formulas, as easily seen from the definition:

∂_{i}(fg) = (∂_{i}f)g + f^{s_{i}}(∂_{i}g) = (∂_{i}g)f + g^{s_{i}}(∂_{i}f),  (1.5)

where f and g are polynomials. In particular, symmetric functions in x_{i}, x_{i+1} are scalars for ∂_{i}, i.e.

g = g^{s_{i}} ⟹ ∂_{i}(fg) = g(∂_{i}f).

Schubert polynomials in two sets of commutative variables 𝔸 and 𝔹 have been defined in [10], starting from a top element X_{v_{0}}(𝔸, 𝔹), and using the action of the symmetry group 𝔖_{n} on 𝔸 only.

Definition 1.2

\{ \begin{matrix}X_{v_{0}}(𝔸, 𝔹) = & ∏_{1⩽i,j⩽n, i+j⩽n}(a_{i} − b_{j}) \\ X_{v}(𝔸, 𝔹) = & ∂_{v^{−1}v_{0}}X_{v_{0}}(𝔸, 𝔹) \end{matrix}

The preceding definition implies the recursion

∂_{i}X_{v}(𝔸, 𝔹) = X_{vs_{i}}(𝔸, 𝔹), if v_{i} > v_{i+1}.  (1.6)

We also need the definition of compatible sequences [3]:

Definition 1.3 For any sequence r = (r_{1} … r_{p}), a p-tuple cp = (cp_{1}, …, cp_{p}) of positive integers is r-compatible if

cp_{1} ⩽ cp_{2} ⩽ ⋯ ⩽ cp_{p},
cp_{j} ⩽ r_{j}, and if r_{j} < r_{j+1}, then cp_{j} < cp_{j+1},
for any j : 1 ⩽ j ⩽ p.

2. Lattice Graphs

Definition 2.1 A lattice graph is a collection of length 1 vertical edges in the ℕ × ℕ lattice. The edge from (i, j) to (i, j + 1) is denoted [i, j](we use the South-East quadrant). Beware that, for us, i = 1, 2, … is the column index and j is the row index; the origin is (1, 1).

[figure: [1,2]; [1,1]; [2,5]; [2,4]; [3,3]; [4,5]]

Figure 2.1 A lattice graph restricting ℕ × ℕ to a domain where all edges appear.

We shall also use three other equivalent representations of lattice graphs.

The first one is a sequence of strictly decreasing words on 1, 2, 3, … that we call column word, by reading upwards the columns from left to right, and replacing the edge [i, j] by j. Void columns must be written as [ ]. Figure 2.1 gives [[2, 1], [5, 4], [3], [5], [ ]].

The second one is a word in commutative biletters i^{j} (we say biword), replacing each edge [i, j] by (j −i+1)^{i}. The number j −i+1 is called label of the edge [i, j]. Our lattice graph, with edges [1, 1], [1, 2], [2, 4], [2, 5], [3, 3], [4, 5] gives the biletters 1^{1}, 2^{1}, 3^{2}, 4^{2}, 1^{3}, 2^{4}. However, we shall write biwords using the decreasing lexicographic order (ordering first the labels, then the exponents) as a list of biletters. Figure 2.1 gives [4^{2}, 3^{2}, 2^{4}, 2^{1}, 1^{3}, 1^{1}].

The third one is a 0-1 matrix A = (a_{ij}), where i, j ∈ ℕ. a_{ji} = 1 if edge [i, j] belongs to lattice graph otherwise a_{ji} = 0. Figure 2.1 gives a lower triangular 0-1 matrix

(\begin{matrix}1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{matrix})  (2.7)

We shall label diagonals downwards, the 1-diagonal being the main diagonal.

Given s, for any k we say that two edges [s, k] and [s + 1, k + 1] are s-paired. Paired edges lie in the same diagonal.

We shall define new operators on lattice graphs, that we still call simple transpositions (denoted by σ) and divided differences (denoted by ∂) as follows (formulating them in terms of biwords):

Definition 2.2 Given a biword w = [w_{1}, w_{2}, …, w_{m}], where w_{1}, w_{2}, …, w_{m} are biletters, then its image under the simple transposition σ_{r} is

σ_{r}(w) = [w_{1}^{σ_{r}}, w_{2}^{σ_{r}}, …, w_{m}^{σ_{r}}],

where for w_{s} = (j − i + 1)^{i},

w_{s}^{σ_{r}} = \{ \begin{matrix}(j − i + 1)^{r+1}, & if i = r \\ (j − i + 1)^{r}, & if i = r + 1 \\ (j − i + 1)^{i}, & otherwise \end{matrix}

From the above definition, we see that σ_{r} acts only on exponents.

Equivalently, σ_{r} acts on a column word [ …, y^{r}, y^{r+1}, …], where y^{r} = [a_{1}, …, a_{m}] and y^{r+1} = [b_{1}, …, b_{n}], as follows:

σ_{r}[ …, y^{r}, y^{r+1}, …] = [ …, [b_{1} − 1, …, b_{n} − 1], [a_{1} + 1, …, a_{m} + 1], …].

Definition 2.3 Given a biword lexicographic ordered w = [w_{1}, w_{2}, …, w_{m}], then the action of the divided difference ∂_{r} on it is

∂_{r}(w) = ∑_{i=1}^{m} ϵ_{r}(w_{i}) W_{i},  (2.8)

where

ϵ_{r}(w_{i}) = \{ \begin{matrix}1, & if the exponent of w_{i} is r \\ −1, & if the exponent of w_{i} is r + 1 \\ 0, & otherwise, \end{matrix}

and W_{i} = [w_{1}, …, w_{i−1}, w_{i+1}^{σ_{r}}, …, w_{m}^{σ_{r}}].

Paired edges will give twice the same lattice graph with different signs, so that we do not need to write them in summation (2.8).

Figure 2.2 shows an example of the action of ∂_{2} in terms of lattice graphs, column words and biwords:

\begin{matrix}[figure: [2,6]; [2,5]; [2,3]; [3,4]; [3,3]] & →^{∂_{2}} & − & [figure: [2,6]; [2,5]; [2,3]; [3,4]] & + & [figure: [2,6]; [2,3]; [2,2]; [3,4]] & + & [figure: [2,3]; [2,2]; [3,4]; [3,6]] \\ [[ ],[6,5,3],[4,3]] & →^{∂_{2}} & − & [[ ],[6,5,3],[4]] & + & [[ ],[6,3,2],[4]] & + & [[ ],[3,2],[6,4]] \\ [5^{2},4^{2},2^{3},2^{2},1^{3}] & →^{∂_{2}} & − & [5^{2},4^{2},2^{3},2^{2}] & + & [5^{2},2^{3},2^{2},1^{2}] & + & [4^{3},2^{3},2^{2},1^{2}] \end{matrix}

Figure 2.2 Action of a divided difference

Given a 0-1 matrix, choosing a submatrix made of 2 consecutive columns and a finite number of adjacent diagonals, we read the diagonals downwards and thus obtain a word in letters {00, 01, 10, 11}. For example the first two columns and first five diagonals of the above matrix (2.7) give the word 10 10 01 01 00.

In this representation, we define a R-move to be a transformation of the type

00 11 ⋯ 11 10 → 01 11 ⋯ 11 00,

with only occurrences of 11 in the middle block. This is clearly an invertible operation.

Notice that one R-move involves three main elements i, θ and m, where R-move acts on the i-th column and (i + 1)-th column, and shifts one edge in the (θ + m)-diagonal to the θ-diagonal. We shall denote such a R-move by R_{i,θ,m}. Explicitly, given a lattice graph D and i, θ, m ⩾ 1, if the word obtained by restricting D to i, i + 1 columns and θ, θ + 1, …, θ + m diagonals is of type 00 11 ⋯ 11 10, then R-move moves the edge [i, i + θ + m − 1] to [i + 1, θ + i], it can be rewritten as

R_{i,θ,m}(D) = D ∪ {[i + 1, θ + i]} \ {[i, i + θ + m − 1]};

otherwise, we set R_{i,θ,m}(D) = D.

3. Braid Relations

We will give some properties of transpositions and divided differences on lattice graphs in this section.

Proposition 3.1 The operators σ satisfy the braid relations :

σ_{i}^{2} = 1,  (3.9)
σ_{i}σ_{j} = σ_{j}σ_{i}, if |i − j| ≠ 1  (3.10)
σ_{i}σ_{i+1}σ_{i} = σ_{i+1}σ_{i}σ_{i+1}  (3.11)

Proof. It is easy to check the first two relations. As for the third relation, the two operators σ_{i}, σ_{i+1} act only on the columns i, i + 1 and i + 2 of the lattice graph. We can take i = 1 and restrict to lattice graphs with columns 1, 2, 3. Let

y^{1} = [a_{1}, …, a_{k}], y^{2} = [b_{1}, …, b_{m}], y^{3} = [c_{1}, …, c_{n}].

We now compare σ_{1}σ_{2}σ_{1} and σ_{2}σ_{1}σ_{2}:

σ_{1}σ_{2}σ_{1}[y^{1}, y^{2}, y^{3}]

= σ_{1}σ_{2}[[b_{1} − 1, …, b_{m} − 1], [a_{1} + 1, …, a_{k} + 1], [c_{1}, …, c_{n}]]
= σ_{1}[[b_{1} − 1, …, b_{m} − 1], [c_{1} − 1, …, c_{n} − 1], [a_{1} + 2, …, a_{k} + 2]]
= [[c_{1} − 2, …, c_{n} − 2], [b_{1}, …, b_{m}], [a_{1} + 2, …, a_{k} + 2]]

In the same way,

σ_{2}σ_{1}σ_{2}[y^{1}, y^{2}, y^{3}] = [[c_{1} − 2, …, c_{n} − 2], [b_{1}, …, b_{m}], [a_{1} + 2, …, a_{k} + 2]].

Therefore we have σ_{1}σ_{2}σ_{1} = σ_{2}σ_{1}σ_{2}.

Proposition 3.2

∂_{i}^{2} = 0,  (3.12)
∂_{i}∂_{j} = ∂_{j}∂_{i}, if |i − j| ≠ 1  (3.13)
∂_{i}∂_{i+1}∂_{i} = ∂_{i+1}∂_{i}∂_{i+1}  (3.14)

Proof. We can take i = 1 as in Proposition 3.1 and a biword with three columns lexicographic ordered is [w_{1}, w_{2}, …, w_{m}]. We now check the first relation:

∂_{1}^{2}([w_{1}, w_{2}, …, w_{m}]) = ∂_{1} (∑_{h=1}^{m} ϵ_{1}(w_{h})[w_{1}, …, w_{h−1}, w_{h+1}^{σ_{1}}, …, w_{m}^{σ_{1}}])

= ∑_{h=1}^{m} ϵ_{1}(w_{h}) ∑_{j>h} ϵ_{1}(w_{j}^{σ_{1}})[w_{1}, …, w_{h−1}, w_{h+1}^{σ_{1}}, …, w_{j−1}^{σ_{1}}, w_{j+1}^{σ_{1}^{2}}, …, w_{m}^{σ_{1}^{2}}] +

∑_{h=1}^{m} ϵ_{1}(w_{h}) ∑_{j<h} ϵ_{1}(w_{j})[w_{1}, …, w_{j−1}, w_{j+1}^{σ_{1}}, …, w_{h−1}^{σ_{1}}, w_{h+1}^{σ_{1}^{2}}, …, w_{m}^{σ_{1}^{2}}]

= 0.

The second relation is immediate.

Let us now compute the image of the biword under ∂_{1}∂_{2}∂_{1}:

∂_{1}∂_{2}∂_{1}([w_{1}, …, w_{m}]) = ∂_{1}∂_{2} (∑_{h=1}^{m} ϵ_{1}(w_{h})[w_{1}, …, w_{h−1}, w_{h+1}^{σ_{1}}, …, w_{m}^{σ_{1}}])

= ∂_{1} (∑_{h=1}^{m} ∑_{j<h} ϵ_{1}(w_{h})ϵ_{2}(w_{j})[w_{1}, …, w_{j−1}, w_{j+1}^{σ_{2}}, …, w_{h−1}^{σ_{2}}, w_{h+1}^{σ_{1}σ_{2}}, …, w_{m}^{σ_{1}σ_{2}}])

+ ∂_{1} (∑_{h=1}^{m} ∑_{j>h} ϵ_{1}(w_{h})ϵ_{2}(w_{j}^{σ_{1}})[w_{1}, …, w_{h−1}, w_{h+1}^{σ_{1}}, …, w_{j−1}^{σ_{1}}, w_{j+1}^{σ_{1}σ_{2}}, …, w_{m}^{σ_{1}σ_{2}}]) .

Using (3.9), the sum decomposes into six summands:

M_{1} = ∑_{h=1}^{m} ∑_{j<h} ∑_{j<k<h} ϵ_{1}(w_{h})ϵ_{2}(w_{j})ϵ_{1}(w_{k}^{σ_{2}})

[w_{1}, …, w_{j−1}, w_{j+1}^{σ_{2}}, …, w_{k−1}^{σ_{2}}, w_{k+1}^{σ_{2}σ_{1}}, …, w_{h−1}^{σ_{2}σ_{1}}, w_{h+1}^{σ_{1}σ_{2}σ_{1}}, …, w_{m}^{σ_{1}σ_{2}σ_{1}}],

M_{2} = ∑_{h=1}^{m} ∑_{j<h} ∑_{j<h<k} ϵ_{1}(w_{h})ϵ_{2}(w_{j})ϵ_{1}(w_{k}^{σ_{1}σ_{2}})

[w_{1}, …, w_{j−1}, w_{j+1}^{σ_{2}}, …, w_{h−1}^{σ_{2}}, w_{h+1}^{σ_{1}σ_{2}}, …, w_{k−1}^{σ_{1}σ_{2}}, w_{k+1}^{σ_{1}σ_{2}σ_{1}}, …, w_{m}^{σ_{1}σ_{2}σ_{1}}],

M_{3} = ∑_{h=1}^{m} ∑_{j<h} ∑_{k<j<h} ϵ_{1}(w_{h})ϵ_{2}(w_{j})ϵ_{1}(w_{k})

[w_{1}, …, w_{k−1}, w_{k+1}^{σ_{1}}, …, w_{j−1}^{σ_{1}}, w_{j+1}^{σ_{2}σ_{1}}, …, w_{h−1}^{σ_{2}σ_{1}}, w_{h+1}^{σ_{1}σ_{2}σ_{1}}, …, w_{m}^{σ_{1}σ_{2}σ_{1}}],

M_{4} = ∑_{h=1}^{m} ∑_{j>h} ∑_{k>j} ϵ_{1}(w_{h})ϵ_{2}(w_{j}^{σ_{1}})ϵ_{1}(w_{k}^{σ_{1}σ_{2}})

[w_{1}, …, w_{h−1}, w_{h+1}^{σ_{1}}, …, w_{j−1}^{σ_{1}}, w_{j+1}^{σ_{1}σ_{2}}, …, w_{k−1}^{σ_{1}σ_{2}}, w_{k+1}^{σ_{1}σ_{2}σ_{1}}, …, w_{m}^{σ_{1}σ_{2}σ_{1}}],

M_{5} = ∑_{h=1}^{m} ∑_{j>h} ∑_{h<k<j} ϵ_{1}(w_{h})ϵ_{2}(w_{j}^{σ_{1}})ϵ_{1}(w_{k}^{σ_{1}})

[w_{1}, …, w_{h−1}, w_{h+1}^{σ_{1}}, …, w_{k−1}^{σ_{1}}, w_{k+1}, …, w_{j−1}, w_{j+1}^{σ_{1}σ_{2}σ_{1}}, …, w_{m}^{σ_{1}σ_{2}σ_{1}}],

M_{6} = ∑_{h=1}^{m} ∑_{j>h} ∑_{k<h} ϵ_{1}(w_{h})ϵ_{2}(w_{j}^{σ_{1}})ϵ_{1}(w_{k})

[w_{1}, …, w_{k−1}, w_{k+1}^{σ_{1}}, …, w_{h−1}^{σ_{1}}, w_{h+1}, …, w_{j−1}, w_{j+1}^{σ_{1}σ_{2}σ_{1}}, …, w_{m}^{σ_{1}σ_{2}σ_{1}}]. The image under ∂_{2}∂_{1}∂_{2} gives also a sum of six summands:

N_{1} = ∑_{h=1}^{m} ∑_{j>h} ∑_{k>j} ϵ_{2}(w_{h})ϵ_{1}(w_{j}^{σ_{2}})ϵ_{2}(w_{k}^{σ_{2}σ_{1}})

[w_{1}, …, w_{h−1}, w_{h+1}^{σ_{2}}, …, w_{j−1}^{σ_{2}}, w_{j+1}^{σ_{2}σ_{1}}, …, w_{k−1}^{σ_{2}σ_{1}}, w_{k+1}^{σ_{2}σ_{1}σ_{2}}, …, w_{m}^{σ_{2}σ_{1}σ_{2}}],

N_{2} = ∑_{h=1}^{m} ∑_{j<h} ∑_{k<j} ϵ_{2}(w_{h})ϵ_{1}(w_{j})ϵ_{2}(w_{k})

[w_{1}, …, w_{k−1}, w_{k+1}^{σ_{2}}, …, w_{j−1}^{σ_{2}}, w_{j+1}^{σ_{1}σ_{2}}, …, w_{h−1}^{σ_{1}σ_{2}}, w_{h+1}^{σ_{2}σ_{1}σ_{2}}, …, w_{m}^{σ_{2}σ_{1}σ_{2}}],

N_{3} = ∑_{h=1}^{m} ∑_{j<h} ∑_{k>h} ϵ_{2}(w_{h})ϵ_{1}(w_{j})ϵ_{2}(w_{k}^{σ_{2}σ_{1}})

[w_{1}, …, w_{j−1}, w_{j+1}^{σ_{1}}, …, w_{h−1}^{σ_{1}}, w_{h+1}^{σ_{2}σ_{1}}, …, w_{k−1}^{σ_{2}σ_{1}}, w_{k+1}^{σ_{2}σ_{1}σ_{2}}, …, w_{m}^{σ_{2}σ_{1}σ_{2}}],

N_{4} = ∑_{h=1}^{m} ∑_{j<h} ∑_{j<k<h} ϵ_{2}(w_{h})ϵ_{1}(w_{j})ϵ_{2}(w_{k}^{σ_{1}})

[w_{1}, …, w_{j−1}, w_{j+1}^{σ_{1}}, …, w_{k−1}^{σ_{1}}, w_{k+1}^{σ_{1}σ_{2}}, …, w_{h−1}^{σ_{2}σ_{1}}, w_{h+1}^{σ_{2}σ_{1}σ_{2}}, …, w_{m}^{σ_{2}σ_{1}σ_{2}}],

N_{5} = ∑_{h=1}^{m} ∑_{j>h} ∑_{h<k<j} ϵ_{2}(w_{h})ϵ_{1}(w_{j}^{σ_{2}})ϵ_{2}(w_{k}^{σ_{2}})

[w_{1}, …, w_{h−1}, w_{h+1}^{σ_{2}}, …, w_{k−1}^{σ_{2}}, w_{k+1}, …, w_{j−1}, w_{j+1}^{σ_{2}σ_{1}σ_{2}}, …, w_{m}^{σ_{2}σ_{1}σ_{2}}],

N_{6} = ∑_{h=1}^{m} ∑_{j>h} ∑_{k<h} ϵ_{2}(w_{h})ϵ_{1}(w_{j}^{σ_{2}})ϵ_{2}(w_{k})

[w_{1}, …, w_{k−1}, w_{k+1}^{σ_{2}}, …, w_{h−1}^{σ_{2}}, w_{h+1}, …, w_{j−1}, w_{j+1}^{σ_{2}σ_{1}σ_{2}}, …, w_{m}^{σ_{2}σ_{1}σ_{2}}].

Thanks to (3.10) and

ϵ_{1}(w^{σ_{1}σ_{2}}) = ϵ_{2}(w), ϵ_{2}(w^{σ_{2}σ_{1}}) = ϵ_{1}(w),
ϵ_{1}(w^{σ_{1}}) = −ϵ_{1}(w), ϵ_{2}(w^{σ_{2}}) = −ϵ_{2}(w),

we get M_{k} = N_{k}, for 1 ⩽ k ⩽ 4 and M_{5} + M_{6} = 0, N_{5} + N_{6} = 0. Therefore ∂_{1}∂_{2}∂_{1} = ∂_{2}∂_{1}∂_{2}.

Similar computations give the following relations of the same type:

∂_{i}σ_{i} + σ_{i}∂_{i} = 0,  (3.15)
∂_{i}σ_{i+1}σ_{i} = σ_{i+1}σ_{i}∂_{i+1}, ∂_{i+1}σ_{i}σ_{i+1} = σ_{i}σ_{i+1}∂_{i}  (3.16)
∂_{i}σ_{i+1}∂_{i} = ∂_{i+1}∂_{i}σ_{i+1} + σ_{i+1}∂_{i}∂_{i+1},  (3.17)
∂_{i+1}σ_{i}∂_{i+1} = ∂_{i}∂_{i+1}σ_{i} + σ_{i}∂_{i+1}∂_{i}.  (3.18)

These relations, together with Proposition 3.1 and 3.2, allow to define a “twisted action” of the symmetric group, lifting the action on polynomials used by Lascoux-Leclerc-Thibon [16].

Proposition 3.3 Let q ∈ ℂ, for any i, define T_{i} : σ_{i} + q∂_{i}. Then

T_{i}^{2} = 1,  (3.19)
T_{i}T_{j} = T_{j}T_{i}, if |i − j| ≠ 1  (3.20)
T_{i}T_{i+1}T_{i} = T_{i+1}T_{i}T_{i}.  (3.21)

Proof. (3.19) is an immediate result of (3.9), (3.12) and (3.15).

(3.20) is evident owing to (3.10), (3.13) and σ_{i}∂_{j} = ∂_{j}σ_{i}.

(3.21) comes from (3.11), (3.14), (3.16), (3.17), and (3.18).

4. Schubert Polynomials and Lattice Graphs

In this section, we define Schubert polynomials in terms of lattice graphs. Our definition is different from the combinatorial description of Schubert polynomials in terms of tableaux ([14], [19]), of reduced decompositions ([3]), of rc-graphs ([1]), though connected to the preceding descriptions.

Let L be the ℤ-module with basis the lattice graphs. Schubert polynomials 𝕃_{v}, v ∈ 𝔖_{n}, will now be defined as elements of the space L as follows:

The top element 𝕃_{v_{0}} is the lattice graph corresponding to the column word [[n − 1, …, 2, 1], ⋯, [n − 1], [ ]], and for any v ∈ 𝔖_{n},

𝕃_{v} = ∂_{v^{−1}v_{0}}𝕃_{v_{0}}.  (4.22)

Given a lattice graph, whose edges [i, j] are such that i ⩽ j, we say that it is reduced if the underlying word obtained by erasing the brackets in the column word is reduced. Denote by L^{v} the set of all the lattice graphs which give a reduced decomposition of v.

Lemma 4.1 Given any permutation v, any reduced lattice graph D ∈ L^{v}, and i, θ, m ⩾ 1, then R_{i,θ,m}(D) ∈ L^{v}.

Proof. If R_{i,θ,m}(D) = D, the lemma holds.

Otherwise, R_{i,θ,m}(D) = D ∪ {[i + 1, θ + i]} \ {[i, i + θ + m − 1]}. Let η = i + θ + m. Restricting D to i, i + 1 two columns and the diagonals between θ-diagonal and (θ + m)-diagonal, the column word is

[[η − 1, η − 2, …, η − m], [η − 1, η − 2, …, η − m + 1]].

The corresponding column word for R_{i,θ,m}(D) is

[[η − 2, η − 3, …, η − m], [η − 1, η − 2, …, η − m + 1, η − m]].

It is straightforward, thanks to the braid relations (1.1), that the underlying permutations are the same.

Lemma 4.1 shows that R-moves , or their inverses, preserve the underlying permutation.

Theorem 4.2 For each permutation v ∈ 𝔖_{n}, we have

𝕃_{v} = ∑_{D∈L^{v}} D.  (4.23)

Proof. We use decreasing induction on the length of permutations. When v = v_{0}, L^{v_{0}} contains only the reduced lattice graph D_{0} = L̂(v_{0}) = 𝕃_{v_{0}} and the statement is evident.

If v ≠ v_{0}, let π = vs_{r} and ℓ(π) = ℓ(v) + 1. We know that 𝕃_{v} = ∂_{r}𝕃_{π}, and by induction , that Theorem 4.2 holds for 𝕃_{π}.

Given any reduced lattice graph D in L^{π}, we denote the biword corresponding to the unpaired edges of r-th column and (r + 1)-th column by [w_{1}, w_{2}, …, w_{n}] (ignoring the other edges). Let D_{i} be the lattice graph which is obtained from D by replacing [w_{1}, w_{2}, …, w_{n}] with [w_{1}, …, w_{i−1}, w_{i+1}^{σ_{r}}, …, w_{n}^{σ_{r}}]. (2.8) can be rewritten in terms of lattice graphs as

∂_{r}D = ∑_{i=1}^{n} ϵ_{r}(w_{i})D_{i}.  (4.24)

We shall also need the underlying set {∂_{r}D} = {D_{i}}.

We decompose L^{π} into two sets L_{0}^{π} and L_{1}^{π} as follows:

L_{0}^{π} = {D ∈ L^{π} : [r, r] ∉ D}, L_{1}^{π} = L^{π} − L_{0}^{π}.  (4.25)

Given D ∈ L_{1}^{π}, let f(r, D) be the minimal integer such that [r, f(r, D)] ∈ D and [r, f(r, D) + 1] ∉ D. Let t^{D} be the maximal index such that all the labels of w_{t^{D}}, …, w_{n} are smaller than, or equal to, f(r, D) − r + 1.

Lemma 4.3 With L_{1}^{π}, t^{D} and D_{i} defined as above, we have

L^{v} = ⋃_{D∈L_{1}^{π}} ⋃_{i=t^{D}}^{n} D_{i}.  (4.26)

Proof. For i : t^{D} ⩽ i ⩽ n, it’s clear that ϵ_{r}(w_{i}) = 1, and that there exist α, β_{1}, …, β_{s} satisfying

[w_{i}, w_{i+1}, …, w_{n}] = [[α, α − 1, …, r], [β_{s}, β_{s−1}, …, β_{1}]].

The subword [w_{i+1}^{σ_{r}}, w_{i+2}^{σ_{r}}, …, w_{n}^{σ_{r}}] must appear in D_{i}, and in terms of the definition 2.3,

[w_{i+1}^{σ_{r}}, w_{i+2}^{σ_{r}}, …, w_{n}^{σ_{r}}] = [[β_{s} − 1, β_{s−1} − 1, …, β_{1} − 1], [α, α − 1, …, r + 1]].

The braid relations (1.1) entail

[w_{i}, w_{i+1}, …, w_{n}] s_{r} = [w_{i+1}^{σ_{r}}, w_{i+2}^{σ_{r}}, …, w_{n}^{σ_{r}}] .

Therefore, D_{i} ∈ L^{v}.

On the other hand, for every lattice graph D′ ∈ L^{v}, let h(r, D′) be the minimal number such that neither [r, h(r, D′)] nor [r +1, h(r, D′)+1] belongs to D′. Among those edges with labels less than h(r, D′) − r + 1, all the unpaired edges constitute a set E which lie in column r + 1. Otherwise it would contradict the fact that ℓ(v s_{r}) = ℓ(v) + 1. Given D′, we define D by replacing all the edges in E by their images under σ_{r}, and adding a new edge [r, h(r, D′)]. Suppose that the biword corresponding to the unpaired edges of r-th column and r + 1-column in D is [w_{1}, w_{2}, …, w_{n}], and that the biletter corresponding to the edge [r, h(r, D′)] is w_{i′}, then D′ = D_{i′}.

Lemma 4.4 Given π, r and the decomposition (4.25) of L^{π}, let D_{i} and t^{D} be defined as above, then we have

∑_{D∈L_{1}^{π}} ∑_{i=1}^{t^{D}−1} ϵ_{r}(w_{i})D_{i} = 0,  (4.27)

∂_{r} ∑_{D∈L_{0}^{π}} D = 0.  (4.28)

Proof. We shall show that if a lattice graph appears in (4.27) or (4.28), then it appears twice, with different signs. Then we describe an involution which allows us to eliminate these pairs.

Here we shall use 0-1 matrices instead of lattice graphs. Denote by 𝟋 the flip operation on a word in the alphabet {00, 01, 10, 11} which exchanges 01 and 10, and fixes 00 and 11. We define now a transformation Θ on words. Given any word w = xz_{1}z_{2} ⋯ z_{k}y, its image under Θ is

Θ(w) = y^{𝟋}z_{1}^{𝟋}z_{2}^{𝟋} ⋯ z_{k}^{𝟋}x^{𝟋}.  (4.29)

It is clear that Θ is an involution on words in the alphabet {00, 01, 10, 11}.

We shall consider only words of the type

01 11 ⋯ 11 01 11 ⋯ 11 01 11 ⋯ 11 00,  (4.30)

where only 11 and 01 appears in the middle block, and their images under Θ

00 11 ⋯ 11 10 11 ⋯ 11 10 11 ⋯ 11 10 .  (4.31)

We apply the above involution to prove (4.27). Given D ∈ L_{1}^{π}, we restrict D to r and r + 1 columns. For i, 1 ⩽ i ⩽ t^{D} − 1:

If w_{i} corresponds to the edge [r, η], its diagonal number is η − r + 1 and word is 10. By definition of t^{D}, we can find upwards the first diagonal whose word is 00. Let ξ be its label. Reading the successive columns from the ξdiagonal to the (η − r + 1)-diagonal, we get a word u which is of type (4.31), because 01 can’t appear(otherwise D is not reduced). Then we apply Θ to u, and obtain a new lattice graph D′. In fact, the action of Θ in that case is a sequence of R-moves which changes [r, η] to [r + 1, r + ξ], and it doesn’t change the edge [r, r], so D′ ∈ L_{1}^{π}. The action of ∂_{r} on the edge [r, η] of D and on the edge [r + 1, r + ξ] of D′ give the same lattice graph, but with different signs.

Otherwise, w_{i} corresponds to the edge [r + 1, η′] which lies in the (η′ − r)−diagonal and the diagonal word is 01. We can find downwards the first diagonal whose word is 00. Let ξ′ be its label. Reading the successive columns from the ξ′-diagonal to the (η′ − r)-diagonal, we get a word u′ of type (4.30). By applying Θ in a similar manner, we can find a pair of lattice graphs plus the corresponding edges, and eliminate the two lattice graphs which appear in (4.27).

Relation (4.28) is also proven by using Θ, which allows us to eliminate lattice graphs by pairs.

The following lemma is an immediate consequence of the above two:

Lemma 4.5 Given two permutations π and v such that π = vs_{r} and ℓ(π) = ℓ(v) + 1, then

∂_{r}L^{π} = L^{v}.

Thus we finish the proof of Theorem 4.2.

We weight each edge [i, j] in the lattice by a_{i} − b_{j−i+1}. Take the weight of D as the product of the weight of all edges [i, j] ∈ D, denoted by ω(D). Then the action of divided difference on lattice graphs is compatible with the action of divided difference on monomials. The following theorem is immediate:

Theorem 4.6 With the weight function ω, for any permutation v we have

X_{v}(𝔸, 𝔹) = ∑_{D∈L^{v}} ω(D).  (4.32)

There is an obvious bijection between column words of lattice graphs L^{v} and RC-words of permutation v. From this bijection one can deduce that:

Theorem 4.7

X_{v}(𝔸, 𝔹) = ∑_{r∈R(v)} ∑_{cp∈C(r)} ∏_{j=1}^{p}(a_{cp_{j}} − b_{r_{j}−cp_{j}+1}).  (4.33)

The case of this theorem on the Schubert polynomials over one set of variables has been studied by Bergeron-Billey [1] and Fomin-Stanley [6].

For the other combinatorial construction of Schubert polynomial, we refer the reader to Lascoux-Schützenberger [15], Fomin-Kirillov [7], Kohnert [8, 9], Lenart [17].

5. Acknowledgements

This work was done under the auspices of the Key Laboratory of Pure Mathematics and Combinatorics of the Ministry of Education of China, and the 973 Project on Mathematical Mechanization of the Ministry of Science and Technology of China. We thank Professor Axel Kohnert in particular for providing some references. Special thanks are given to Professor William Y. C. Chen for his giving us a chance to study symmetric functions and Schubert polynomials.

References

[1] N. Bergeron and S. Billey, RC-graphs and Schubert polynomials, Experimental Math. 2 (1993), 257-269.

[2] I. N. Bernstein, I. M. Gelfand, and S. I. Gelfand, Schubert celles and cohomology of the spaces G/P, Russian Math. Surveys 28 (1973), 1-26.

[3] S. Billey, W. Jockusch and R. Stanley, Some combinatorial properties of Schubert polynomials, J. Alg. Comb. 2 (1993), 345-374.

[4] W. Y. C. Chen, B. Li, and J. D. Louck, The flagged double Schur function, J. Alg. Combin., 15 (2002), 7-26.

[5] M. Demazure, Désingularisation des variétés de Schubert généralisées, Ann. Sci. École Norm. Sup. (4) 7 (1974), 53-58.

[6] S. Fomin and R. Stanley, Schubert polynomials and the NilCoxeter algebra, Adv. Math. 103 (1994), 196-207.

[7] S. Fomin and A. N. Kirillov, Yang-Baxter equation, symmetric functions, and Schubert polynomials, Discrete Math. 153 (1996), 123-143.

[8] A. Kohnert, Weintrauben, Polynome, Tableaux, Bayreuth. Math. Schrift. 38 (1991), 1-97.

[9] A. Kohnert, Multiplication of a Schubert polynomial by a Schur polynomial, Ann. Comb. 1 (1997), 367-375.

[10] A. Lascoux, Classes de Chern des variétés de drapeaux, Comptes Rendus 295 (1982), 393-398.

[11] A. Lascoux, Symmetric Functions and Combinatorial Operators on Polynomials, CBMS Regional Conference Series in Mathematics, 99, AMS, 2003.

[12] A. Lascoux and M. P. Schützenberger, Polynômes de Schubert, C.R. Acad. Sci. Paris 294 (1982), 447-450.

[13] A. Lascoux and M. P. Schützenberger, Structure de Hopf de l’anneau de cohomologie et de l’anneau de Grothendieck d’une varit de drapeaux. C.R. Acad. Sci. Paris 295 (1982), 629-633.

[14] A. Lascoux and M. P. Schützenberger, Tableaux and noncommutative Schubert polynomials, Funct. Anal. Appl. 23 (1989), 63-64.

[15] A. Lascoux and M. P. Schützenberger, Fonctorialite des polynomes de Schubert, Contermporary Mathematics Volume 88, (1989), 585-598.

[16] A. Lascoux, B. Leclerc and J.-Y. Thibon, Twisted action of the symmetric group on the cohomology of a flag manifold. Parameter spaces (Warsaw, 1994), 111-124, Banach Center Publ., 36, Polish Acad. Sci., Warsaw, 1996.

[17] C. Lenart, A unified approach to combinatorial formulas for Schubert polynomials, J. Alg. Comb., to appear.

[18] I. G. Macdonald, Notes on Schubert Polynomials, Publications du LACIM 6, Université du Québec, à Montréal(1991).

[19] V. Reiner and M. Shimozono, Plactification, J. Alg. Combin. 4 (1995), 331-351.

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

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