OPERATORS ON POLYNOMIALS

Alain Lascoux

Contents

Chapter 1. Symmetric Functions 1 1.1. Elementary symmetric functions 1 1.2. Matrix Generating Functions 2 1.3. Schur Functions 3 1.4. Resultant 6 1.5. Padé Approximants 7 1.6. Cauchy Formulas 9 1.7. λ-rings 10 Exercises 13

Chapter 2. Symmetrization Operators 19 2.1. Divided Differences 19 2.2. Braid Relations 21 2.3. Yang-Baxter Graphs 23 2.4. Maximal Symmetrizers 26 2.5. Yang-Baxter elements and Orthogonality 27 2.6. Special Yang-Baxter elements 29 2.7. Young Idempotents 31 2.8. Lagrange Interpolation 33 2.9. Newton Interpolation 35 Exercises 37

Chapter 3. The Ring of Polynomials modulo 𝔖𝔶𝔪_{+} 43 3.1. The Coinvariant Ring of 𝔖_{n} 44 3.2. Young’s Natural Representations 45 3.3. Yang-Baxter Bases 50 Exercises 55

Chapter 4. 𝔓𝔬𝔩(𝔸) as a free 𝔖𝔶𝔪(𝔸)-module 59 4.1. Quadratic Form on 𝔓𝔬𝔩 59 4.2. Kernel 60 4.3. Schubert by Isobaric Divided Differences 66 4.4. Action of 𝔖_{n} on Schubert Polynomials 67 4.5. Newton Interpolation in Several Variables 69 4.6. Yang-Baxter Bases of H^{0,0} 71

iv CONTENTS

4.7. Yang-Baxter Elements as Permutations 72 Exercises 74

Bibliography 79 Index 81

CHAPTER 1 Symmetric Functions

’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o

1.1. Elementary symmetric functions

An alphabet 𝔸 = {a_{1}, a_{2}, …} is a totally ordered set of indeterminates. One writes 𝔸 + 𝔹 for the disjoint union of two alphabets.

Taking an extra indeterminate z, one has three fundamental series (1.1.1)

λ_{z}(𝔸) := ∏_{a∈𝔸}(1 + za) , σ_{z}(𝔸) := ∏_{a∈𝔸} \frac{1}{1 − za} , Ψ_{z}(𝔸) := ∑_{i=1}^{∞} ∑_{a∈𝔸}z^{i}a^{i}/i ,

the expansion of which gives the elementary symmetric functions Λ^{i}(𝔸), the complete functions S^{i}(𝔸), and the power sums Ψ_{i}(𝔸) : (1.1.2)

λ_{z}(𝔸) = ∑ z^{i} Λ^{i}(𝔸) , σ_{z}(𝔸) = ∑ z^{i} S^{i}(𝔸) , Ψ_{z}(𝔸) = ∑_{i=1}^{∞} z^{i}Ψ_{i}(𝔸)/i .

Since log(1/(1 − a)) = ∑_{i>0} a^{i}/i, one has

(1.1.3)  σ_{z}(𝔸) = exp (Ψ_{z}(𝔸)) , Ψ_{z}(𝔸) = log (σ_{z}(𝔸)) .

Addition of alphabets implies product of generating series

(1.1.4) λ_{z}(𝔸 + 𝔹) = λ_{z}(𝔸) λ_{z}(𝔹) , σ_{z}(𝔸 + 𝔹) = σ_{z}(𝔸) σ_{z}(𝔹) .

At the level of the individual symmetric functions, (1.1.4) gives

(1.1.5)  Λ^{n}(𝔸 + 𝔹) = ∑_{i+j=n} Λ^{i}(𝔸)Λ^{j}(𝔹) ,
(1.1.6)  S^{n}(𝔸 + 𝔹) = ∑_{i+j=n} S^{i}(𝔸)S^{j}(𝔹) .

Since one can invert formal series beginning by 1, or take any power of them, one can extend (1.1.1) by setting :

(1.1.7) σ_{z}(𝔸 − 𝔹) := \frac{∏_{b∈𝔹}(1 − zb)}{∏_{a∈𝔸}(1 − za)} , σ_{z}(c 𝔸) = (σ_{z}(𝔸))^{c} , c ∈ ℂ .

When 𝔹 = 0, or 𝔸 = 0, one recovers the two series σ_{z}(𝔸) and σ_{z}(−𝔹) = λ_{−z}(𝔹).

Notice that the addition of alphabets satisfies the usual properties of addition : σ_{z}(−𝔸) is the inverse of σ_{z}(𝔸) because 𝔸 − 𝔸 = 0 and σ_{z}(0) = 1. Similarly, the identity (𝔸+ℂ)−(𝔹+ℂ) = 𝔸−𝔹 translates, at the level of generating series, the fact that

\frac{∏_{b}(1 − zb) ∏_{c}(1 − zc)}{∏_{a}(1 − za) ∏_{c}(1 − zc)} = \frac{∏_{b}(1 − zb)}{∏_{a}(1 − za)} ,

and nobody will deny that one may simplify a factor common to the numerator and denominator of a rational function !

Writing 𝔸 + 𝔹 for the disjoint union of alphabets forces us to consider a finite alphabet as the sum of its sub-alphabets of cardinality 1, i.e to identify 𝔸 and ∑_{a∈𝔸} a, and write

S^{k}(a_{1} + a_{2} + ⋯ + a_{n} − b_{1} − ⋯ − b_{m})

instead of S^{k}(𝔸 − 𝔹), when we shall need the letters composing the finite alphabets 𝔸 and 𝔹.

In particular, an indeterminate x has to be considered as an alphabet of cardinality 1. Very often, we shall use symmetric functions in 𝔸 + x or 𝔸 − x.

1.2. Matrix Generating Functions

Let z stand now for the infinite matrix with diagonal j −i = 1 filled with 1’s, all other entries being 0’s.

Since z^{k}, k ∈ ℕ, is the matrix with 1’s in the k-th diagonal above the main diagonal, and 0 outside of it, we see that now σ_{z}(𝔸) is a Toeplitz matrix (i.e. a matrix with constant values in each diagonal), that we shall denote by 𝕊(𝔸); similarly λ_{z}(𝔸) is a matrix denoted 𝕃(𝔸) :

(1.2.1)  𝕊(𝔸) = [S^{j−i}(𝔸)]_{i,j≥0} & 𝕃(𝔸) = [Λ^{j−i}(𝔸)]_{i,j≥0} .

𝕊(𝔸) = [\begin{matrix}S^{0}(𝔸) & S^{1}(𝔸) & S^{2}(𝔸) & S^{3}(𝔸) & ⋯ \\ S^{−1}(𝔸) & S^{0}(𝔸) & S^{1}(𝔸) & S^{2}(𝔸) & ⋯ \\ S^{−2}(𝔸) & S^{−1}(𝔸) & S^{0}(𝔸) & S^{1}(𝔸) & ⋯ \\ & ... & ... & ... \end{matrix}]

𝕃(𝔸) = [\begin{matrix}Λ^{0}(𝔸) & Λ^{1}(𝔸) & Λ^{2}(𝔸) & Λ^{3}(𝔸) & ⋯ \\ Λ^{−1}(𝔸) & Λ^{0}(𝔸) & Λ^{1}(𝔸) & Λ^{2}(𝔸) & ⋯ \\ Λ^{−2}(𝔸) & Λ^{−1}(𝔸) & Λ^{0}(𝔸) & Λ^{1}(𝔸) & ⋯ \\ & ... & ... & ... \end{matrix}] .

These matrices are upper triangular, but it is wiser to write entries S^{−k} rather than their value 0.

Addition or subtraction of alphabets still correspond to product of generating functions, whether z is an indeterminate or a matrix makes no difference :

(1.2.2) 𝕊(𝔸 ± 𝔹) = 𝕊(𝔸) 𝕊(𝔹)^{±1} & 𝕃(𝔸 ± 𝔹) = 𝕃(𝔸) 𝕃(𝔹)^{±1} .

Indeed, formulas (1.1.5) and (1.1.6) exactly tells that an entry of the matrix 𝕊(𝔸 ± 𝔹) (resp. 𝕃(𝔸 ± 𝔹)) is a sum of products of entries of 𝕊(𝔸 and 𝕊(±𝔹) (resp. 𝕃(𝔸 and 𝕃(±𝔹)) of appropriate indices.

1.3. Schur Functions

The advantage of matrices, compared to formal series, is that they have minors, that we shall index by (increasing) partitions, or more generally, by vectors with components in ℤ. More precisely, given I = (i_{1}, …, i_{n}) ∈ ℤ^{n}, J = (j_{1}, …, j_{n}) ∈ ℤ^{n} one defines the skew Schur function S_{J/I}(𝔸) to be the minor of 𝕊(𝔸) taken on rows i_{1} + 1, i_{2} + 2, …, i_{n} + n and columns j_{1} + 1, …, j_{n} + n (we define the minor to be 0 if one of these numbers is < 0). When I = 0^{n} , the minor is called a Schur function and one writes S_{J}(𝔸) instead of S_{J/0^{n}}(𝔸).

In other words,

(1.3.1)  S_{J/I}(𝔸) = | S^{j_{k}−i_{h}+k−h}(𝔸) |_{1≤h,k≤n} .

The expression of a Schur function as a determinant of complete functions is called the Jacobi-Trudi determinant (we shall see that there is also another expression in terms of elementary symmetric functions).

 One can enter a (decreasing) partition or a skew partition.
 Matrices are transposed along the antidiagonal,
 compared to the conventions in the course.
 ACE> SfJtMat([5,4,1]), SfJtMat([ [5,4,1],[2,1] ]);
                   [h5    h6    h7]   [h3    h5    h7]
                   [h3    h4    h5],  [h1    h3    h5]
                   [0     1     h1]   [0     0     h1]

One can visualize the Schur function S_{J/I} as being obtained from the initial minor of the same order, by shifting the columns by J, and the rows by I :

\begin{matrix}0 & 1 & 2 & −i_{1} \\ ^{−}1 & 0 & 1 & −i_{2} \\ ^{−}2 & ^{−}1 & 0 & −i_{3} \\ j_{1} & j_{2} & j_{3} \end{matrix} ⇒ \begin{matrix}0 + j_{1} − i_{1} & 1 + j_{2} − i_{1} & 2 + j_{3} − i_{1} \\ −1 + j_{1} − i_{2} & 0 + j_{2} − i_{2} & 1 + j_{3} − i_{2} \\ −2 + j_{1} − i_{3} & −1 + j_{2} − i_{3} & 0 + j_{3} − i_{3} \end{matrix} .

It is convenient to also use determinants in elementary symmetric functions :

(1.3.2)  Λ_{J/I}(𝔸) = | Λ^{j_{k}−i_{h}+k−h}(𝔸) |_{1≤h,k≤n} .

Of course, one must not forget that Λ^{i}(𝔸) = (−1)^{i}S^{i}(−𝔸), i ∈ ℤ, and thus the Λ_{J/I}(𝔸) are also skew Schur functions in ^{−}𝔸 (we shall see that they also are Schur functions in 𝔸, but indexed by “column lengths”).

To write easily a Schur function S_{J}(𝔸), one first writes the diagonal, then complete the columns, increasing or decreasing indices by 1 when moving up or down :

J = [1, 2, 4] ⇒ | \begin{matrix}S_{1}(𝔸) \\ S_{2}(𝔸) \\ S_{4}(𝔸) \end{matrix} | ⇒ |\begin{matrix}S_{1}(𝔸) & S_{3}(𝔸) & S_{6}(𝔸) \\ S_{0}(𝔸) & S_{2}(𝔸) & S_{5}(𝔸) \\ S_{−1}(𝔸) & S_{1}(𝔸) & S_{4}(𝔸) \end{matrix}| = S_{124}(𝔸)

One needs to enlarge the definition of a Schur function to be able to play with different alphabets at the same time.

Given n, two sets of alphabets {𝔸_{1}, 𝔸_{2}, …, 𝔸_{n}}, {𝔹_{1}, 𝔹_{2}, …, 𝔹_{n}}, and J ∈ ℕ^{n}, we define the multi-Schur function

(1.3.3) S_{J}(𝔸_{1} − 𝔹_{1}, …, 𝔸_{n} − 𝔹_{n}) := | S_{j_{k}+k−h}(𝔸_{k} − 𝔹_{k}) |_{1≤h,k≤n} .

In the case where the alphabets are repeated, we indicate by a semicolon the corresponding block separation : given H ∈ ℤ^{p}, K ∈ ℤ^{q}, then S_{H;K}(𝔸−𝔹; ℂ−𝔻) stands for the multi-Schur function with index the concatenation of H and K, and alphabets 𝔸_{1} = ⋯ = 𝔸_{p} = 𝔸, 𝔹_{1} = ⋯ = 𝔹_{p} = 𝔹, 𝔸_{p+1} = ⋯ = 𝔸_{p+q} = ℂ, 𝔹_{p+1} = ⋯ = 𝔹_{p+q} = 𝔻.

To write a multi-Schur function easily, one first fills the diagonal, then completes columns by keeping the same alphabet in each column :

S_{12; 4}(𝔸; 𝔹) ⇒ |\begin{matrix}S_{1}(𝔸) \\ & S_{2}(𝔸) \\ & & S_{4}(𝔹) \end{matrix}| ⇒ |\begin{matrix}S_{1}(𝔸) & S_{3}(𝔸) & S_{6}(𝔹) \\ S_{0}(𝔸) & S_{2}(𝔸) & S_{5}(𝔹) \\ S_{−1}(𝔸) & S_{1}(𝔸) & S_{4}(𝔹) \end{matrix}| .

Enter an increasing partition, and a list of alphabets
SchurDrap:=proc(pa,lA)   local n,i,j,ma; n:=nops(pa);
 transpose(array([seq(
 map(proc(x,i,ll) if (x>0) then s[x](op(i,ll)) elif (x=0)
  then 1 else 0 fi end,[seq(pa[i]-j+i,j=1..n)],i,lA),i=1..n)] ));
 end:
ACE> SchurDrap([1,3,5], [A1,A1, A2-A3]);
                    [s[1](A1)    s[4](A1)    s[7](A2 - A3)]
                    [   1        s[3](A1)    s[6](A2 - A3)]
                    [   0        s[2](A1)    s[5](A2 - A3)]

Far from being a complication compared to usual symmetric functions in an alphabet only, multi-Schur functions allow easier induction, because they can be easily transformed.

Notice that for any k ∈ ℕ, any 𝔸, any x, one has

S^{k}(𝔸 − x) = S^{k}(𝔸) − x S^{k−1}(𝔸) .

Now, if in the determinant expressing a multi-Schur function of order n, one replaces in row i, i < n, (denote it r_{i}) all the alphabets 𝔸_{k} − 𝔹_{k} by 𝔸_{k} − 𝔹_{k} − x, then r_{i} is transformed into r_{i} − xr_{i+1}, and the value of the determinant is unchanged.

Iterating the reasoning, given two indeterminates x, y, one can change in row i, i < n−1, all the alphabets 𝔸_{k} −𝔹_{k} by 𝔸_{k} −𝔹_{k} −x−y, and the value of the determinant is constant because the transformation has changed r_{i} into r_{i} − (x^{+}y) r_{i+1} + xy r_{i+2}. It is not difficult to give the general law, transforming rows by linear combination of rows below it^{1}. In final, the following “transformation lemma” tells which subtraction are possible in a multi-Schur function :

Lemma 1.3.1. Let S_{J}(𝔸_{1} − 𝔹_{1}, …, 𝔸_{n} − 𝔹_{n}) be a multi-Schur function, and 𝔻_{1}, 𝔻_{2}, …, 𝔻_{n−1} be a family of finite alphabets such that card(𝔻_{i}) ≤ n − i, 1 ≤ i ≤ n − 1. Then S_{J}(𝔸_{1} − 𝔹_{1}, …, 𝔸_{n} − 𝔹_{n}) is equal to the determinant

| S_{j_{k}+k−i}(𝔸_{k} − 𝔹_{k} − 𝔻_{i}) |_{1≤i,k≤n}

Proof. Indeed the transformation has consisted in changing row i into the linear combination

r_{i} + r_{i+1} S^{1}(^{−}𝔻_{i}) + r_{i+2} S^{2}(^{−}𝔻_{i}) + ⋯ + r_{n} S^{n−i}(^{−}𝔻_{i})

because, for any 𝔸, 𝔹, any j ∈ ℤ, one has

S_{j}(𝔸^{−}𝔹−𝔻_{i}) = S_{j}(𝔸^{−}𝔹)+S_{j−1}(𝔸^{−}𝔹)S^{1}(^{−}𝔻_{i})+⋯+S_{j−n+i}(𝔸^{−}𝔹)S^{n−i}(^{−}𝔻_{i}) .

□

Thanks to the lemma, we can transform the expression of S_{J}(𝔸^{−}x).

Lemma 1.3.2. Let J ∈ ℕ^{n}, k ∈ ℕ, 𝔸, 𝔹 be arbitrary and x be an indeterminate. Then

(1.3.4)  S_{J}(𝔸^{−}𝔹 − x) x^{k} = S_{j;k}(𝔸^{−}𝔹; x) .

Proof. In the determinant on the right, subtract x to all rows except the bottom one. Then the last column becomes

S^{k+n}(0) = 0, …, S^{k+1}(0) = 0, S^{k}(x) = x^{k} ,

1but remembering that the row index must not be greater than n. This is why one cannot subtract x in the last row, nor x + y in row r_{n−1}.

and the cofactor of the entry x^{k} is indeed S_{J}(𝔸^{−}𝔹 − x). □

1.4. Resultant

Schur functions indexed by rectangular partitions^{2} play a special role. They appear in many classical topics of 19th century mathematics: elimination theory, continued fractions, etc. In particular, they allow to express the resultant of two polynomials in x, and we shall give many applications of this fact.

Given two finite alphabets 𝔸 = {a}, 𝔹 = {b}, of respective cardinalities α, β, let the resultant of 𝔸, 𝔹 be

R(𝔸, 𝔹) := ∏_{a∈𝔸} ∏_{b∈𝔹}(a − b) .

Proposition 1.4.1. The resultant of two alphabets 𝔸, 𝔹 is equal to the Schur function

(1.4.1)  S_{β^{α}}(𝔸 − 𝔹) = (^{−}1)^{αβ}S_{α^{β}}(𝔹 − 𝔸) .

Proof. Choose a letter a ∈ 𝔸 and subtract (𝔸 − a) from the top row of the determinant expressing S_{β^{α}}(𝔸 − 𝔹). The determinant obtained is equal to the Schur function S_{β^{α−1};β}(𝔸^{−}𝔹; a^{−}𝔹) (up to symmetry with respect to the middle, compared to the usual conventions). Now, one can subtract a from all the columns, except the first one. The first row has become

S_{β}(a^{−}𝔹), S_{β+1}(^{−}𝔹) = 0, …, S_{β+α−1}(^{−}𝔹) = 0 ,

the zeroes being due to the fact^{3} that S^{k}(^{−}𝔹) = 0 for k > β. Therefore the new determinant factorizes into

S_{β}(a^{−}𝔹) S_{β^{α−1}}((𝔸^{−}a) − 𝔹) = ∏_{b∈𝔹}(a − b) S_{β^{α−1}}((𝔸^{−}a) − 𝔹) ,

and the result follows by induction on α.

2partitions with equal parts; we shall write m^{n}, or □ when m, n have been fixed.

3The elementary symmetric functions of a finite alphabet of degree higher than the cardinality are null.

For example, for α = 3, β = 5, one has

S_{555}(𝔸^{−}𝔹) = |\begin{matrix}S^{5}(𝔸^{−}𝔹) & S^{6}(𝔸^{−}𝔹) & S^{7}(𝔸^{−}𝔹) \\ S^{4}(𝔸^{−}𝔹) & S^{5}(𝔸^{−}𝔹) & S^{6}(𝔸^{−}𝔹) \\ S^{3}(𝔸^{−}𝔹) & S^{4}(𝔸^{−}𝔹) & S^{5}(𝔸^{−}𝔹) \end{matrix}| =

|\begin{matrix}S^{5}(a^{−}𝔹) & S^{6}(a^{−}𝔹) & S^{7}(a^{−}𝔹) \\ S^{4}(𝔸^{−}𝔹) & S^{5}(𝔸^{−}𝔹) & S^{6}(𝔸^{−}𝔹) \\ S^{3}(𝔸^{−}𝔹) & S^{4}(𝔸^{−}𝔹) & S^{5}(𝔸^{−}𝔹) \end{matrix}| = |\begin{matrix}S^{5}(a^{−}𝔹) & S^{6}(^{−}𝔹) & S^{7}(^{−}𝔹) \\ S^{4}(𝔸^{−}𝔹) & S^{5}(𝔸^{−}a^{−}𝔹) & S^{6}(𝔸^{−}a^{−}𝔹) \\ S^{3}(𝔸^{−}𝔹) & S^{4}(𝔸^{−}a^{−}𝔹) & S^{5}(𝔸^{−}a^{−}𝔹) \end{matrix}| .

The simplest case of a resultant is when 𝔸 has only one letter:

R(a, 𝔹) = ∏_{b∈𝔹}(a − b) = S^{β}(a − 𝔹) .

Note that

S^{β+i}(a − 𝔹) = a^{i} , S^{β}(a − 𝔹) , i ≥ 0 .

This is given by the generating function σ_{z}(a − 𝔹), but more simply, one can add i letters to 𝔹, and specialize them to 0.

1.5. Padé Approximants

Let us just give one application of rectangular Schur functions, the interpolation of functions in one variable f(z) by rational functions N(z)/D(z) of fixed degrees.

By “function”, we mean, following Lagrange, a formal series in z which is supposed to be the Taylor expansion of a function in the neighbourhood of 0, and hopefully, even farther.

Forgetting the word “interpolation”, and using alphabets, the problem we have to solve is the following :

given an alphabet 𝔼, and two positive integers α, β, find two finite alphabets 𝔸, 𝔹: |𝔸| = α, |𝔹| = β, such that

(1.5.1)  σ_{z}(𝔼) ≡ \frac{N(z)}{D(z)} = σ_{z}(𝔸 − 𝔹)  mod z^{α+β+1} .

In other words, we require that the two Taylor series coincide up to the highest possible degree, having α + β parameters at our disposal.

We could also say that we want to extract 𝔸, then 𝔹 from the first complete functions of 𝔸^{−}𝔹 (which are equal to those of 𝔼).

This problem was solved by Cauchy, Jacobi, &c., but this is Padé who made a systematic study of it and took the patent.

Having promised an application of resultants, I must force them to appear. Instead of writing

σ_{z}(𝔸 − 𝔹) = ∏_{b∈𝔹}(1 − zb)/ ∏_{a∈𝔸}(1 − za)

let us take x = 1/z and multiply numerator and denominator by R(𝔸, 𝔹). Then

\frac{N(z)}{D(z)} = ±x^{α−β} \frac{R(x, 𝔹)R(𝔸, 𝔹)}{R(x, 𝔸)R(𝔹, 𝔸)} = ±x^{α−β} \frac{R(x + 𝔸, 𝔹))}{R(x + 𝔹, 𝔸)} .

But now, our rational fraction has become the quotient of two resultants, and we can write it :

[β/α] = \frac{N(z)}{D(z)} = ±x^{α−β} S_{β^{α+1}}(𝔸 + x − 𝔹) S_{(β+1)^{α}}(𝔸 − 𝔹 − x)^{−1}.

The two determinants involve only, apart from x, the complete functions S^{1}(𝔸^{−}𝔹), …, S^{α+β}(𝔸^{−}𝔹), that is, exactly those which coincide with the coefficients of the series.

Therefore, we have solved the problem, and obtained

(1.5.2)  \frac{N(z)}{D(z)} = ±x^{α−β} S_{β^{α+1}}(𝔼 + x) S_{(β+1)^{α}}(𝔼 − x)^{−1} ,

Thanks to to the different expressions of the resultant, the Padé approximant can be written :

(1.5.3) (^{−}1)^{αβ+α+β} \frac{z^{β}S_{(α+1)^{β}}(𝔹^{−}𝔸 − \frac{1}{z})}{z^{α}S_{(β+1)^{α}}(𝔸^{−}𝔹 − \frac{1}{z})}

= (^{−}1)^{α} \frac{z^{β}S_{β^{α+1}}(𝔸^{−}𝔹 + \frac{1}{z})}{z^{α}S_{(β+1)^{α}}(𝔸^{−}𝔹 − \frac{1}{z})} = (^{−}1)^{αβ} \frac{z^{β}Λ_{(α+1)^{β}}(𝔸^{−}𝔹 + \frac{1}{z})}{z^{α}Λ_{(β+1)^{α}}(𝔹^{−}𝔸 + \frac{1}{z})}

Do not forget that, for any 𝔸, any x of rank 1, on has the decompositions S^{k}(𝔸^{+}x) = ∑_{i} x^{i}S^{k−i}(𝔸), S^{k}(𝔸^{−}x) = S^{k}(𝔸) − xS^{k−1}(𝔸), Λ^{k}(𝔸^{+}x) = Λ^{k}(𝔸)−xΛ^{k−1}(𝔸). This shows how to expand the preceding functions in terms of x.

In fact, using our favorite transformations on Schur functions, we can restrict 1/z to only one column and write :

(1.5.4) [β/α] = (^{−}1)^{α}z^{β−α} S_{β; β^{α}}(𝔸^{−}𝔹 + \frac{1}{z}; 𝔸^{−}𝔹) / S_{(β+1)^{α}; 0}(𝔸^{−}𝔹; \frac{1}{z})

These expressions can be found in the literature: (1.5.4) is due to Jacobi [7], while Sylvester [30, I n 57] gave the second expression of (1.5.3).

The explicit expansion of the numerator and the denominator of the Padé approximant, in terms of the Schur functions of 𝔸 − 𝔹, is (1.5.5)

[β/α] = \frac{S_{β^{α}} + zS_{1β^{α}} + z^{2}S_{2β^{α}} + ⋯ + z^{β}S_{ββ^{α}}}{S_{β^{α}} − zS_{β^{α−1},β+1} + z^{2}S_{β^{α−2},(β+1)^{2}} + ⋯ + (−z)^{α}S_{(β+1)^{α}}} .

For example, for β = 1, α = 1, one gets

[1/1] = \frac{S_{1} + zS_{11}}{S_{1} − zS_{2}} = 1 + zS^{1} + z^{2}S^{2} + z^{3}S^{22}/S^{1} + z^{4}S^{222}/S^{11} + ⋯,

for β = 1, α = 2,

[1/2] = \frac{S_{11} + zS_{111}}{S_{11} − zS_{12} + z^{2}S_{22}} = 1^{+}zS^{1}^{+}z^{2}S^{2}^{+}z^{3}S^{3}^{+}z^{4} \frac{S_{114}^{+}S_{15}^{−}S_{222}}{S_{11}} +⋯,

for β = 2, α = 1,

[2/1] = \frac{S_{2} + zS_{12} + z^{2}S_{22}}{S_{2} − zS_{3}} = 1 + zS^{1} + z^{2}S^{2} + z^{3}S^{3} + z^{4} \frac{S^{33}}{S^{2}} + ⋯

and for β = 2, α = 2,

\frac{S_{22} + zS_{122} + z^{2}S_{222}}{S_{22} − zS_{23} + z^{2}S_{33}} = 1+zS^{1}+z^{2}S^{2}+z^{3}S^{3}+z^{4}S^{4}+\frac{S^{144} − 2S^{234} + S^{333}}{S_{22}} +⋯

1.6. Cauchy Formulas

The resultant is a Schur function in a difference of alphabets, and consequently, a minor of a product of two matrices.

The Binet-Cauchy theorem for minors of the product of two matrices implies, in the case of the product

𝕊(𝔸 − 𝔹) = 𝕊(𝔸) 𝕊(^{−}𝔹) = 𝕊(𝔸) 𝕊(𝔹)^{−1}

the following expansion of skew-Schur functions:

(1.6.1) S_{J/I}(𝔸 + 𝔹) = ∑_{K} S_{J/K}(𝔸) S_{K/I}(^{−}𝔹)

= ∑_{K}(^{−}1)^{|K/I|}S_{J/K}(𝔸) S_{K^{∼}/I^{∼}}(𝔹) ,

sum over all partitions K.

Applying it to the resultant, one gets

R(𝔸, 𝔹) := ∏_{a∈𝔸, b∈𝔹}(a − b) = ∑_{I} S_{I}(𝔸)S_{□/I}(−𝔹)
(1.6.2)  = ∑_{I}(−1)^{|□/I|}S_{I}(𝔸)S_{□ ∼/I ∼}(𝔹) ,

where □ = β^{α}, α = card(𝔸), β = card(𝔹).

Taking inverse variables, and using the correspondence between the Schur functions in a_{1}, a_{2}, …, and those of 1/a_{1}, 1/a_{2}, …, one can give the following second form of Cauchy formula :

(1.6.3)  ∏_{a∈𝔸, b∈𝔹}(1 − ab) = σ_{1}(−𝔸𝔹) = ∑_{I}(−1)^{|I|}S_{I}(𝔸)S_{I^{∼}}(𝔹) .

Now, the cardinalities have disappeared, the formula is valid for any infinite 𝔸, 𝔹, i.e. for two formal series, and one can replace 𝔹 by −𝔹, thus obtaining the most common form of Cauchy formula :

(1.6.4)  ∏_{a∈𝔸, b∈𝔹}(1 − ab)^{−1} = σ_{1}(𝔸𝔹) = ∑_{I} S_{I}(𝔸)S_{I}(𝔹) .

Coding Schur functions by diagrams of partitions, one can visualize (1.6.2) and (1.6.4) by pairs of complementary diagrams^{4}, or pairs of identical diagrams, white diagrams coding Schur functions in 𝔸, black ones in 𝔹 :

∏_{a,b}(a^{−}b) = \begin{matrix}□ & □ \\ □ & □ \\ □ & □ \end{matrix} − \begin{matrix}□ \\ □ & □ \\ □ & □ \end{matrix} _{■} + \begin{matrix}□ \\ □ \\ □ & □ \end{matrix} _{■} _{■} + \begin{matrix}□ & □ \\ □ & □ \end{matrix} \begin{matrix}■ \\ ■ \end{matrix} − \begin{matrix}□ \\ □ \\ □ \end{matrix} _{■} _{■} _{■}

− _{□ □}^{□} _{■ ■}^{■} + _{□ □} \begin{matrix}■ & ■ \\ ■ & ■ \end{matrix} + \begin{matrix}□ \\ □ \end{matrix} _{■ ■ ■}^{■} − _{□} _{■ ■ ■}^{■ ■} + \begin{matrix}■ & ■ & ■ \\ ■ & ■ & ■ \end{matrix} ,

∏_{a,b}(1−ab)^{−1} = 1+_{□} _{■}+_{□} _{□} _{■} _{■}+ \begin{matrix}□ \\ □ \end{matrix} \begin{matrix}■ \\ ■ \end{matrix}+_{□} _{□} _{□} _{■} _{■} _{■}+ _{□ □}^{□} _{■ ■}^{■}+ \begin{matrix}□ \\ □ \\ □ \end{matrix} \begin{matrix}■ \\ ■ \\ ■ \end{matrix}+⋯

1.7. λ-rings

Schur functions are called Schur functions not because they were defined by Schur, but because it is considered that their true meaning appears in relation with representations of the linear group^{5}.

What we have already used in fact, is that Schur functions are functors, because we took as an argument formal expressions in alphabets like 𝔸 − 𝔹, (𝔸^{−}𝔹)(ℂ^{+}𝔻) instead of only sets of variables.

In fact, what we really want is to consider symmetric polynomials as operators. On what ? For the present, operating on polynomials will be enough. And since symmetric functions can be expressed as functions of power sums, it will be sufficient to define the functor power-sum Ψ_{i}, acting on polynomials in the following way :.

(1.7.1)  P = ∑_{α,u} α u ⇒ Ψ_{i}(P) = ∑_{α,u} α u^{i} ,

4we have taken 𝔸, 𝔹 of cardinalities 3, 2; the enumeration involves all pairs of partitions of complementary shape in the rectangle 3 × 2.

5But they also can be interpreted as Schubert cycles in the cohomology ring of Grassmann varieties, and it is a matter of taste to rate representation theory higher than geometry. In fact these two interpretations are closely related. As for concerns Schubert polynomials, the cohomological interpretation came also before representation considerations.

1.7. λ-RINGS 11

where α ∈ ℂ, and u is monom.

It is a little surprising that such a simple rule can be of interest at all, but in fact it really implies the full theory of symmetric polynomials. The non-trivial point is that Ψ_{i} acts differently on constants and variables.

Using the generating functions of complete functions or elementary symmetric functions in terms of power sums, one can rewrite :

P = ∑_{α,u} α u ↦ λ_{z}(P) = ∏(1 + zu)^{α} , (1.7.2)

P = ∑_{α,u} α u ↦ σ_{z}(P) = ∏(1 − zu)^{−α} . (1.7.3)

Explicitly, the action of the elementary functors on constants α and variables x is : (1.7.4)

\begin{cases}Ψ_{i}(α) = α , & S^{i}(α) = \binom{α+i−1}{i} , & Λ^{i}(α) = \binom{α}{i} \\ Ψ_{i}(x) = x^{i} , & S^{i}(x) = x^{i} , & Λ^{i}(x) = 0, i > 1, & Λ^{1}(x) = x \end{cases}

Of course, a constant can be variable, and a variable can be specialized to a constant. Thus, in the present case, the terminology “constant” and “variable” or “indeterminate” is confusing. What we have in our ring, on which operate Ψ_{i}, S^{i}, Λ^{i}, are two basic objects: the elements of binomial type α, which are invariant under all the Ψ_{i}, and the elements of rank 1 which are annihilated by all Λ^{i}, i > 1 (and different from 0).

Notice that an element which is of binomial type and of rank 1 must be equal to 1. This has the consequence that one cannot specialize “variables” in a way compatible with the action of power sums, apart from specializing to 1, or 0.

Of course, one can use λ-rings to prove an algebraic identity A = B, and then use any specialization of both members A, B.

For example, given the rank-1 elements x, y, ζ, α, β, γ, the n-th Legendre polynomial P_{n}(x) is the specialization of the following different elements :

P_{n}(x) = S^{n} ((y + y^{−1})/2)
= S^{n}((n^{+}1)x − n(ζ^{+}1)) 2^{−n}
= S^{n}((n^{+}1)b − nζ)
= Λ^{n}(n − (n^{+}1)c)
= Λ^{n}(na + nb) ,

12 1. SYMMETRIC FUNCTIONS

in

y = x + \sqrt{x^{2}^{−}1} , ζ = ^{−}1 , a = \frac{x^{+}1}{2} , b = \frac{x^{−}1}{2} , c = \frac{1^{−}x}{2} .

Let us just write the different expressions for n = 2, leaving as an exercise the general case.

S^{2}((y + y^{−1})/2) expands, thanks to Cauchy formula, into S_{2}(1/2)S_{2}(y + y^{−1}) + S_{1}1(1/2)S_{1}1(y + y^{−1})

= 3/8(y^{2} + 1 + 1/y^{2}) − 1/8y/y ,

S^{2}(3x − 2(ζ + 1)) = S^{2}(3x) − (3x)(2ζ + 2) + Λ^{2}(2ζ + 2)

= 1 − 6x + 4ζ + ζ^{2} − 6xζ + 6x^{2} ,

S^{2}(3b − 2ζ) = b^{2}S^{2}(3) − 6bζ + ζ^{2} = 6b^{2} − 6bζ + ζ^{2} , Λ^{2}(2 − 3c) = Λ^{2}(2) − 6c + c^{2}Λ^{2}(−3) = 1 − 6c + 6c^{2} , Λ^{2}(2a + 2b) = a^{2}Λ^{2}(2) + 4ab + b^{2}Λ^{2}(2) = a^{2} + 4ab + b^{2} ,

and all these functions specialize to P_{2}(x) = 3x^{2}/2 − x/2 .

’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o

Exercises

Ex. 1.1. Let 𝔸 be arbitrary, k be a positive integer. Express the product S^{k}(1 − z𝔸) σ_{z}(𝔸) in the basis of Schur functions. Solution. The product to decompose is made of two factors of different types. To make it more uniform, and easier to interpret, one introduces an alphabet 𝔹 of cardinality k, such that S^{i}(−𝔹) = S^{i}(−𝔸), i = 0, …, k. Then

S^{k}(1^{−}z𝔹) σ_{z}(𝔸) = σ_{z}(^{−}𝔹) σ_{z}(𝔸) = σ_{z}(𝔸^{−}𝔹)

= ∑ z^{n}S^{n}(𝔸^{−}𝔹) = ∑ z^{n}S_{n; 0^{k}}(𝔸; 𝔹) ,

using our favourite transformation of Schur functions.

The determinants S_{n; 0^{k}}(𝔸; 𝔹) involve, as for concerns 𝔹, only complete functions of degree ≤ k, but for those degrees, one can replace 𝔹 by 𝔸, and therefore the sum is

∑ z^{n}S_{n,0^{k}}(𝔸) = (^{−}1)^{k} ∑_{j} z^{j}S_{1^{k}, j−k}(𝔸) .

 Ex1:=proc(k,n)  local i,pol;
   pol:=1+convert([seq((-z)^i*e.i,i=1..k)],`+`);
   map(Tos,taylor(pol*(1+convert([seq(z^i*h.i,i=1..n)],`+`)),
                                        z, n+1),collect); end:
ACE>  Ex1(3,6);
   s[] -s[1,1,1,1]z^4 -s[2,1,1,1] z^5 -s[3,1,1,1] z^6 +s[]O(1)z^7

Ex. 1.2. Let I = [i_{1}, …, i_{r}] be a partition, n an integer : n ≥ i_{r}. Check that

S_{I; 0^{n}}(𝔸, 𝔹) = S_{I}(𝔸 − 𝔹) .

Solution. Since 𝔹 is of arbitrary cardinality, one cannot directly apply the transformation lemma of multi-Schur functions given in the course.

#  incr=increasing partition, lA=list of alphabets
MultiSchur:=proc(incr,lA)   local n,i,j,ma;
 n:=nops(incr);
 transpose(array([seq(
  map(proc(k,i,ll) if (k>0) then s[k](op(i,ll)) elif (k=0)
  then 1 else 0 fi end,[seq(incr[i]-j+i,j=1..n)],i,lA),i=1..n)]));
 end;
ExSchur2:=proc(pa,n) local i,v;    # pa=decreasing partition
  v:=[seq(pa[nops(pa)-i],i=0..nops(pa)-1) ,0$n];
  MultiSchur(v, [A1$nops(pa), A2$n])

end:
ACE> aa:=ExSchur2([2,1], 3);
      [s[1](A1)   s[3](A1)    s[2](A2)    s[3](A2)    s[4](A2)]
      [   1       s[2](A1)    s[1](A2)    s[2](A2)    s[3](A2)]
aa := [   0       s[1](A1)       1        s[1](A2)    s[2](A2)]
      [   0          1           0           1        s[1](A2)]
      [   0          0           0           0           1    ]
ACE> SfAExpand(det(aa));
s[2,1](A1)-s[1](A2)s[1,1](A1)-s[1](A2)s[2](A1)+s[1](A1)s[1,1](A2)
      + s[1](A1) s[2](A2) - s[2,1](A2)
ACE> SfAExpand(s[2,1](A1-A2));
s[2,1](A1)-s[1](A2)s[1,1](A1)-s[1](A2)s[2](A1)+s[1](A1)s[1,1](A2)
      + s[1](A1) s[2](A2) - s[2,1](A2)

However, the Laplace expansion of the determinant S_{I; 0^{n}}(𝔸, 𝔹) along the last n columns shows that, as a function of 𝔹, it belongs to the linear span of the products S^{j_{1}}(𝔹) ⋯ S^{j_{n}}(𝔹), which is also the linear span of Schur functions S_{J}(𝔹), J ∈ ℕ^{n}. Similarly, S_{I}(𝔸 − 𝔹) = ∑ ±S_{I/J^{∼}}(𝔸)S_{J}(𝔹), with the same limit on the number of parts of J because n ≥ i_{r}.

Now, a symmetric function which belongs to the linear span of S_{J}, J ∈ ℕ^{n}, is null (as a function of an arbitrary alphabet) iff it is null on alphabets of cardinality n.

We therefore have only to check the required identity for 𝔹 of cardinality n, in which case it is given by subtracting 𝔹 to the top rows of S_{I; 0^{n}}(𝔸, 𝔹).

Ex. 1.3. Let 𝔸 be arbitrary, x be a rank-1 element, m, n ∈ ℕ. Decompose the polynomial S_{m^{n}}(𝔸 + x) in the basis of polynomials {S^{k}(𝔸+x) : k = 0, 1, 2, …} (all polynomials considered as polynomials in x with coefficients in 𝔖𝔶𝔪(𝔸)). Solution. Subtract x to all the rows, except the last one. The entries of the last row are complete functions of 𝔸 + x, and the other rows are independent of x. Therefore, the expansion of this new determinant along its last row is the required decomposition.

Ex. 1.4. Express the coefficients of the Taylor expansion (in z) of the rational function

∏_{b∈𝔹}(1 − zb)/ ∏_{a∈𝔸}(1 − za)

in terms of the coefficients of the numerator and denominator.

Solution. The function is σ_{z}(𝔸^{−}𝔹) = ∑ z^{n}S^{n}(𝔸^{−}𝔹), but we want only to see the S^{i}(^{−}𝔸), S^{j}(^{−}𝔹). We have just to write

S^{n}(𝔸^{−}𝔹) = (^{−}1)^{n}S_{1^{n}}(^{−}𝔹 + 𝔸) = (^{−}1)^{n}S_{1^{n}; 0}(^{−}𝔹; ^{−}𝔸) ,

thanks to Ex. 1.2.

Ex. 1.5. Let 𝔸 be arbitrary, x be rank-1 element, and 𝔹 of cardinality 4 be such that

S_{4444}(𝔸 + x) = S_{444}(𝔸) S^{4}(𝔹 + x) .

Show that S_{4}(𝔹 − 𝔸) = 0. Solution. With the function S_{4}(𝔸 − 𝔹), one could have thought of writing it as S_{4;0000}(𝔸; 𝔹), but this is not the function that one has to study, and moreover the hypothesis that 𝔹 be of cardinality 4 is not necessary as we shall see.

The hypothesis is that

x^{4}S_{444}(𝔸)+x^{3}S_{1444}(𝔸)+x^{2}S_{2444}(𝔸)+xS_{3444}(𝔸)+S_{4444}(𝔸) = S_{4444}(𝔸+x)

= S_{444}(𝔸) S^{4}(𝔹+x) = S_{444}(𝔸)(x^{4}+x^{3}S_{1}(𝔹)+x^{2}S_{2}(𝔹)+xS_{3}(𝔹)+S_{4}(𝔹)) .

Expanding S_{4}(𝔹 − 𝔸) = S_{4}(𝔹) − S_{3}(𝔹)S_{1}(𝔸) + ⋯ + S_{1111}(𝔸), and replacing the complete functions of 𝔹 by their values in terms of 𝔸, one is asked to check the nullity of

S_{4444}(𝔸)−S_{3444}(𝔸)S_{1}(𝔸)+S_{2444}(𝔸)S_{11}(𝔸)−S_{1444}(𝔸)S_{111}(𝔸)+S_{444}(𝔸)S_{1111}(𝔸)

but it easier to interpret this sum writing the Schur functions as determinants in Λ^{i}(𝔸) (this just involves taking conjugate partitions) :

Λ_{4444}(𝔸)−Λ_{3444}(𝔸)Λ_{1}(𝔸)+Λ_{3344}(𝔸)Λ_{2}(𝔸)−Λ_{3334}(𝔸)Λ_{3}(𝔸)+Λ_{3333}(𝔸)Λ_{4}(𝔸)

Now, one sees that the sum is the Laplace expansion of the determinant Λ_{44440}(𝔸) = 0 along its last column.

Ex. 1.6. Given two finite alphabets 𝔸, 𝔹, and a partition I, write S_{I}(𝔸 + 𝔹) ∏_{a∈𝔸,b∈𝔹}(a − b) as a multi-Schur function. Solution. Let 𝔸, 𝔹 be of respective cardinality α, β, and let □ = β^{α}. Then, from Lemma (1.3.1), one gets

S_{I}(𝔸 + 𝔹) ∏(a − b) = S_{I ; □}(^{−}𝔹; 𝔸^{−}𝔹) = S_{I^{∼}; □^{∼}}(^{−}𝔸; 𝔹^{−}𝔸) .

Ex. 1.7. Let 𝔸 be of cardinality n, and I, J ∈ ℕ^{n}. Show that the determinant

|S_{j_{k}+k−h+i_{n−h+1}}(𝔸)|

factorizes into S_{J}(𝔸) S_{I}(𝔸). What can be said if n is not the cardinality of 𝔸 ?

For example, for n = 3, I = [1, 3, 3], J = [2, 4, 6], one has

\begin{matrix}0 & 1 & 2 & 3 \\ −1 & 0 & 1 & 3 \\ −2 & −1 & 0 & 1 \\ 2 & 4 & 6 \end{matrix} = |\begin{matrix}S_{5} & S_{8} & S_{11} \\ S_{4} & S_{7} & S_{10} \\ S_{1} & S_{4} & S_{7} \end{matrix}| = S_{133}(𝔸) S_{246}(𝔸) .

Solution.

ACE>  aa:= ProdSchur([2,6], [0,2]);
                                   [h4    h9]
                                   [h1    h6]
ACE>  factor(Toe_n(det(aa));
        e2^2  (- e2 + e1^2 ) (e1^4 - 3 e2 e1^2  + e2^2 )
  #  Preceding determinant is  s[ 84/20 ]. Take conjugate partitions
ACE> map(Toe_n, SfJtMat([[2$4,1$4],[1,1]], 'e'));
   [e1    e2    e4    e5    0     0     0     0 ]
   [1     e1    e3    e4    e5    0     0     0 ]
   [0     1     e2    e3    e4    e5    0     0 ]
   [0     0     e1    e2    e3    e4    e5    0 ]
   [0     0     0     1     e1    e2    e3    e4]
   [0     0     0     0     1     e1    e2    e3]
   [0     0     0     0     0     1     e1    e2]
   [0     0     0     0     0     0     1     e1]

Ex. 1.8. Compute the adjoint matrix of a Jacobi-Trudi matrix.

For example

ACE>       SfJtMat([5,4,1]), map(Tos, adj(SfJtMat([5,4,1])));
 [h5    h6    h7]   [    s[4,1]      -s[6, 1]       s[6,5]     ]
 [h3    h4    h5],  [-s[3,1]-s[4]  s[5,1] +s[6]  -s[5,5]-s[6,4]]
 [0     1     h1]   [     s[3]       -s[5]           s[5,4]    ]

Solution. The entries of the adjoint matrix are minors of the original matrix. In our case, they are minors of the Toeplitz matrix [S^{j−i}], since the Jacobi-Trudi matrix itself is so.

The required entries are therefore skew Schur functions, up to sign. The example should be written

[\begin{matrix}S_{56/11} & ^{−}S_{56/1} & S_{56} \\ S_{16/11} & ^{−}S_{16/1} & S_{16} \\ S_{14/11} & ^{−}S_{14/1} & S_{14} \end{matrix}]

and this gives the general pattern.

Ex. 1.9. Let 𝔸 be any alphabet, m, n be two integers. Check that the adjoint matrix of 𝕊_{m^{n}}(𝔸) is the matrix of the quadratic form Q(x, y) := S_{(m+1)^{n−1}}(𝔸 − x − y). Solution. Minors of S_{m^{n}}(𝔸) are skew Schur functions. The expansion of Q(x, y) also produces skew Schur functions that one has to check to be the same.

For example, the adjoint to 𝕊_{6666}(𝔸) is

[\begin{matrix}S_{666} & ^{−}S_{667} & S_{677} & ^{−}S_{777} \\ S_{666/001} & ^{−}S_{667/001} & S_{677/001} & ^{−}S_{777/001} \\ S_{666/011} & ^{−}S_{667/011} & S_{677/011} & ^{−}S_{777/011} \\ S_{666/111} & ^{−}S_{667/111} & S_{677/111} & ^{−}S_{777/111} \end{matrix}] = [\begin{matrix}S_{666} & ^{−}S_{667} & S_{677} & ^{−}S_{777} \\ ^{−}S_{566} & S_{567}^{+}S_{666} & ^{−}S_{667}^{−}S_{577} & S_{677} \\ S_{556} & ^{−}S_{566}^{−}S_{557} & S_{567}^{+}S_{666} & ^{−}S_{667} \\ ^{−}S_{555} & S_{556} & ^{−}S_{566} & S_{666} \end{matrix}]

Ex. 1.10. Let x_{1}, …, x_{n}, y be rank 1 elements. Compute ∑_{i} 1/(y− x_{i}). Solution. The sum is the logarithmic derivative of S^{n}(y − 𝕏) with respect to y (with 𝕏 = x_{1} + ⋯ + x_{n}). Therefore ∑_{i} 1/(y − x_{i}) = S^{n−1}(2y − 𝕏)/S^{n}(y − 𝕏).

Ex. 1.11. Let 𝔸 be arbitrary, x of rank 1, n, p ∈ ℕ. Show that

S^{n}(𝔸)−\binom{k}{1}S^{n}(𝔸−x)+\binom{k}{2}S^{n}(𝔸−2x)+⋯+(−1)^{k}\binom{k}{k}S^{n}(𝔸−kx) = x^{k}S^{n−k}(𝔸) .

Solution. Both sides are linear in S^{j}(𝔸); one may take 𝔸 = a of rank 1, in which case the identity is a^{n} − \binom{k}{1}a^{n−1}(a − x) + \binom{k}{2}a^{n−2}(a − x)^{2} + ⋯ = a^{n−k}(a − (a − x))^{k}

Ex. 1.12. Let 𝔸 be arbitrary, k, r, p be three integers, k < r. Show the nullity (⋆)

S_{k}(p𝔸)−\binom{r}{1}S_{k}((p^{−}1)𝔸)+\binom{r}{2}S_{k}((p^{−}2)𝔸)−⋯±\binom{r}{r}S_{k}((p^{−}r)𝔸) = 0 .

Solution. Take the matrix M = [S_{j−i}(𝔸)]_{1≤i,j≤r}. It is triangular, with a diagonal of 1’s. Cayley-Hamilton theorem implies, for any p, the nullity of the matrix ∑_{i}(−M)^{p−i}Λ^{i}(r), because the binomialsΛ^{i}(r) are the elementary symmetric functions in the eigenvalues of M.

The functions S_{k}(i𝔸), ∀i ∈ 𝔸, are entries of M^{i} whenever k < r, and therefore the LHS of (⋆) are entries of the above null matrix.

Ex. 1.13. Let 𝔸 be an alphabet. Grothendieck defined functions γ^{i}(𝔸) by the generating function

γ_{z}(𝔸) = ∑ z^{i} γ^{i}(𝔸) := λ_{z/(1−z)}(𝔸) .

Define accordingly the alphabet 𝔸^{⋄} by Λ^{i}(𝔸^{⋄}) = γ^{i}(𝔸), i ≥ 0.

Show that

\begin{aligned}Λ^{i}(𝔸^{⋄}) & = Λ^{i}(𝔸 + i − 1) \\ S^{i}(𝔸^{⋄}) & = S^{i}(𝔸 + 1 − i) \\ Ψ^{i}(𝔸^{⋄}) & = ∑_{j=0}^{i−1}(−1)^{j}\binom{i}{j} Ψ^{i−j}(𝔸) . \end{aligned}

Show that the transformation 𝔸 ↦ 𝔸^{⋄} satisfies (−𝔸)^{⋄} = −𝔸^{⋄}, (𝔸 + 𝔹)^{⋄} = 𝔸^{⋄} + 𝔹^{⋄}, but that in general, (𝔸𝔹)^{⋄} ≠ 𝔸^{⋄}𝔹^{⋄}. Solution. The compatibility of γ^{i}(𝔸) with the involution 𝔸 → ^{−}𝔸 is seen on the expression of S^{i}(𝔸^{⋄}). The compatibility with addition comes from the fact that generating functions multiply: γ_{z}(𝔸^{+}𝔹) = γ_{z}(𝔸)γ_{z}(𝔹).

For what concerns multiplication, one has for example the inequality

Ψ^{2}(𝔸^{⋄}𝔹^{⋄}) = Ψ^{2}(𝔸𝔹)−2Ψ^{1}(𝔸𝔹) ≠ (Ψ^{2}(𝔸)−2Ψ^{1}(𝔸))(Ψ^{2}(𝔹)−2Ψ^{1}(𝔹)) .

Ex. 1.14. Let ξ be such S^{n}(ξ) = 1/n!, n ∈ ℕ, and let x, y be rank-1 elements. The polynomials S^{n}(xξ − (n^{+}1)y), n ∈ ℕ are a basis a polynomials in x.

Express the powers of x in this basis. Solution. The formulas of change of basis are linear in S^{n}(ξ), and one may take any element 𝔸 instead of ξ, as long as the S^{n}(𝔸) are linearly independent. For example, with z of rank 1, then one has S^{n}(z − ny) = (z − y)^{n} and

S^{n}(z) = ((z^{−}y) + y)^{n} = ∑_{j} \binom{n}{n − j}y^{n−j}S^{j}(z^{−}jy) .

Replacing z by xξ − y, one gets

\frac{x^{n}}{n!} − \frac{yx^{n−1}}{(n^{−}1)!} = S^{n}(xξ^{−}y) = ∑_{j} \binom{n}{n − j}y^{n−j}S^{j}(z − (j^{+}1)y) ,

and therefore

\frac{x^{n}}{n!} = ∑_{j=0}^{n} \binom{n + 1}{n − j}y^{n−j}S^{j}(z − (j^{+}1)y) .

CHAPTER 2 Symmetrization Operators

’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o

2.1. Divided Differences

Divided differences ∂_{σ} were introduced by Newton to solve the interpolation problem in one variable. Apart from them, we shall also need isobaric divided differences π_{σ} and π̂_{i}.

In the case where σ is a simple transposition s_{i} exchanging a_{i} and a_{i+1}, writing then ∂_{i}, π_{i}, π̂_{i}, the operators (acting on their left) are : (2.1.1)

\{ \begin{matrix}∂_{i} & = & (a_{i} − a_{i+1})^{−1} (1 + s_{i}) & = & (1 − s_{i}) (a_{i} − a_{i+1})^{−1} \\ π_{i} & = & (1 − a_{i+1}/a_{i})^{−1} (1 + s_{i}) & = & a_{i}∂_{i} \\ π̂_{i} & = & (1 − s_{i}) (a_{i}/a_{i+1} − 1)^{−1} & = & π_{i} − 1 \end{matrix}

More explicitly, ∂_{i}, π_{i} and π̂_{i} are the operators on functions f(a_{1}, …, a_{n}) of several variables, acting only on the pair (a_{i}, a_{i+1)}:

(2.1.2)

\begin{cases}f ∂_{i} & = (f(… a_{i}, a_{i+1} …) − f(… a_{i+1}, a_{i} …)) (a_{i} − a_{i+1})^{−1} \\ f π_{i} & = (a_{i} f(… a_{i}, a_{i+1} …) − a_{i+1} f(… a_{i+1}, a_{i} …)) (a_{i} − a_{i+1})^{−1} \\ f π̂_{i} & = (f(… a_{i}, a_{i+1} …) − f(… a_{i+1}, a_{i} …)) a_{i+1}(a_{i} − a_{i+1})^{−1} \end{cases}

In a more compact manner, we can write: (2.1.3)

∂_{i} : f → f ∂_{i} := \frac{f − f^{s_{i}}}{a_{i} − a_{i+1}} & π_{i} : f → f π_{i} := \frac{a_{i}f − a_{i+1}f^{s_{i}}}{a_{i} − a_{i+1}} .

We shall check below that each of the families of operators {s_{i}}, {∂_{i}}, {π_{i}}, {π̂_{i}} separately satisfies the Moore/Coxeter braid relations (writing {D_{i}} in each of these three cases) :

(2.1.4) D_{i}D_{j} = D_{j}D_{i} if |i − j| ≥ 2 , D_{i}D_{i+1}D_{i} = D_{i+1}D_{i}D_{i+1} .

Notice that, as concerns squares, one has

(2.1.5)  ∂_{i}∂_{i} = 0 , π_{i}π_{i} = π_{i} , π̂_{i}π̂_{i} = −π̂_{i} , s_{i}s_{i} = 1 .

All these divided differences ∂_{i}, π_{i}, π̂_{i} are special cases of local rational operators of the type

(2.1.6)  D_{i} = P (a_{i}, a_{i+1})1 + Q(a_{i}, a_{i+1}) s_{i} ,

that is, of a linear combination of the two permutations 1, s_{i}, the coefficients P (x, y) and Q(x, y) being two rational functions of two variables independent of i.

In [17] [20], one determines the conditions on P and Q which ensure that the D_{i}’s satisfy braid relations and preserve polynomials. These operators happen to satisfy an Hecke relation, i.e. there exists constants q_{1}, q_{2} such that

(2.1.7)  (D_{i} − q_{1})(D_{i} − q_{2}) = 0 , ∀i ≥ 1 .

To represent the Hecke algebra, one usually takes

(2.1.8)  T_{i} = π_{i}(q_{1} + q_{2}) − q_{2} s_{i} , i ≥ 1.

It is convenient to display the symmetric group as its Cayley graph, called permutohedron, which describes how permutations are successively generated by products of simple transpositions, starting from the identity permutation. Paths in this oriented graph, starting from the identity, are called reduced decompositions, i.e. decompositions of permutations into products of simple transpositions of minimum length.

One can use the same graph to describe operators, the edges now being interpreted as simple divided differences, or isobaric divided differences instead of simple transpositions.

Here we show 𝔖_{3}, the edges being divided differences; on the figure on the right, we have written the images of a_{1}^{2}a_{2} under the operators displayed on the left permutohedron, to illustrate that the figure codes a family of operators on polynomials:

\begin{aligned}& 123 \\ ∂_{1} ⧸⧸ & & ⧹ ∂_{2} \\ 213 & & 132 \\ ∂_{2} | & & ∥ ∂_{1} \\ 231 & & 312 \\ ∂_{1} ⧹⧹ & & ⧸ ∂_{2} \\ & 321 \end{aligned}  \begin{aligned}& a_{1}^{2}a_{2} \\ ∂_{1} ⧸⧸ & & ⧹ ∂_{2} \\ a_{1}a_{2} & & a_{1}^{2} \\ ∂_{2} | & & ∥ ∂_{1} \\ a_{1} & & a_{1}^{+}a_{2} \\ ∂_{1} ⧹⧹ & & ⧸ ∂_{2} \\ & 1 \end{aligned}

Divided differences satisfy Leibnitz formulas^{1}, as easily seen from the definition:

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

In particular, symmetric functions in a_{i}, a_{i+1} are scalars for ∂_{i}, π_{i} and π̂_{i} :

(2.1.10)  g = g^{σ_{i}} ⇒ fg ∂_{i} = f∂_{i} g and fg π_{i} = fπ_{i} g .

When a_{i+1} tends towards a_{i}, the divided difference ∂_{i} becomes the usual derivative with respect to a_{i}. However, in that limit one loses the fact that symmetric functions in a_{i}, a_{i+1} commute with the operator, a property which greatly simplify computations. Indeed, to compute the image of a function under ∂_{i}, one will try to write it as a function in a_{i}, a_{i+1} as simple as possible, the complications being pushed to the coefficients (which are symmetrical in a_{i}, a_{i+1} and involve the other variables). Finite differences also give a discrete version of differential calculus on functions of one variable, but there is no invariant subring playing the role of symmetric functions. We shall illustrate in the sequel how the use of the symmetric group simplifies the computations with divided differences, and renders this discrete differential calculus simpler than the usual one^{2}.

2.2. Braid Relations

Let 𝔸_{i} = {a_{1}, …, a_{i}}, and let 𝔹 be a second alphabet invariant under the simple transposition s_{i} = (a_{i}, a_{i+1}).

Then one has

(2.2.1)  σ_{z}(𝔸_{i} − 𝔹) ∂_{i} = σ_{z}(𝔸_{i+1} − 𝔹) ,

because σ_{z}(𝔸_{i} − 𝔹) = (1 − za_{i+1}) σ_{z}(𝔸_{i+1} − 𝔹), and σ_{z}(𝔸_{i+1} − 𝔹) being invariant under s_{i}, commutes with ∂_{i}, and one is left with the computation of (1 − za_{i+1}) ∂_{i}.

The braid relations

D_{i}D_{i+1}D_{i} = D_{i+1}D_{i}D_{i+1}

involves only three consecutive variables, which can be taken to be a_{1}, a_{2}, a_{3} and thus, are statements about operators acting on the ring 𝔓𝔬𝔩(𝔸_{3}) := ℤ[a_{1}, a_{2}, a_{3}]. However, D_{1}, D_{2} commutes with symmetric functions in 𝔖𝔶𝔪(𝔸_{3}), and 𝔓𝔬𝔩(𝔸_{3}) must be seen as a module over 𝔖𝔶𝔪(𝔸_{3}). It is easy to see that it is generated by the monomials a_{1}^{i}a_{2}^{j}, with i = 0, 1, 2 and j = 0, 1.

1Notice that the two formulas are disymmetrical in f, g, and one has two expressions for the image of a product.

2Unfortunately, it was almost forgotten during three hundred years, its only application being more or less the original application of Newton to the interpolation of functions of one variable.

Now, ∂_{1}∂_{2}∂_{1} and ∂_{2}∂_{1}∂_{2} are operators on polynomials which decrease the degree by 3. They send all the elements of the generating set^{3} onto 0, except a_{1}^{2}a_{2} which is sent to a constant^{4}. One would have to check that the constant is the same (it is equal to 1) for ∂_{1}∂_{2}∂_{1} and ∂_{2}∂_{1}∂_{2}, to conclude that these operators be equal.

In fact, it is not more complicated to compute the image of any monomial. For example, take a_{1}^{5}a_{2}^{9}a_{3}^{2}, and write it as the Schur function

S_{2;9;5}(𝔸_{3}; 𝔸_{2}; 𝔸_{1}) .

The images of this determinant by the sequence ∂_{2}, ∂_{1}, ∂_{2} are easy to write, because at each step ∂_{i}, only one column is not invariant under s_{i}. In that case, the operation consists in increasing 𝔸_{i} to 𝔸_{i+1} and decreasing degrees in this column, thanks to (2.2.1). In the present case, one gets the sequence

S_{2;9;5}(𝔸_{3}; 𝔸_{2}; 𝔸_{1}) ⟶^{∂_{2}} S_{2;8;5}(𝔸_{3}; 𝔸_{3}; 𝔸_{1}) ⟶^{∂_{1}} S_{2;8;4}(𝔸_{3}; 𝔸_{3}; 𝔸_{2})

⟶^{∂_{2}} S_{2;8;3}(𝔸_{3}; 𝔸_{3}; 𝔸_{3}) = S_{283}(𝔸_{3}) = −S_{247}(𝔸_{3}) .

Starting with

S_{5;9;2}(𝔸_{3}; a_{3} + a_{2}; a_{3}) ,

and using ∂_{1}, ∂_{2}, ∂_{1}, one gets −S_{5;8;0}(𝔸_{3}; 𝔸_{3}; 𝔸_{3}), which is the same function.

The braid relations can be similarly checked for π_{i}, π̂_{i}, the commutations of D_{i} and D_{j} when |i − j| ≠ 1 being, of course, trivial.

In the course of proving the braid relations, we have obtained the classical expression of a Schur function as a quotient of two “alternants” :

Lemma 2.2.1. Let 𝔸 be of cardinality n, u = [u_{1}, …, u_{n}] ∈ ℕ^{n}, v = u^{≈} := [u_{n}, …, u_{1}]. Then

(2.2.2)  x^{u+ρ} ∂_{ω} = S_{v}(𝔸) = \frac{|a^{n−1+u_{1}} , ⋯, a^{0+u_{n}} |_{a∈𝔸}}{|a^{n−1} , ⋯, a^{0}|_{a∈𝔸}}

3In fact a 𝔖𝔶𝔪(𝔸_{3})-basis, the module is free.

4Different from 0, because both operators are not identically null.

2.3. Yang-Baxter Graphs

Let us first go back to the group algebra of 𝔖_{n}.

Instead of handling reduced decompositions, it is not much more complicated to take products of factors of the type s_{i} + c, with c ∈ ℚ.

However our fundamental braid relation s_{1}s_{2}s_{1} = s_{2}s_{1}s_{2} is not compatible with a uniform shift :

(1 + s_{1})(1 + s_{2})(1 + s_{1}) = 2 + 2s_{1} + s_{2} + s_{1}s_{2} + s_{2}s_{1} + s_{1}s_{2}s_{1} ≠ (1 + s_{2})(1 + s_{1})(1 + s_{2}) .

Indeed 2s_{1} + s_{2} is not symmetrical in s_{1}, s_{2}, and this implies that the elements (1+s_{1})(1+s_{2})(1+s_{1}) and (1+s_{2})(1+s_{1})(1+s_{2}) be different. To recover equality, one must use non constant shifts. For example,

(1 + s_{1})(\frac{1}{2} + s_{2})(1 + s_{1}) = (1 + s_{2})(\frac{1}{2} + s_{1})(1 + s_{2}) .

The general rule to ensure equality is due to Yang and Baxter. More precisely, we want to find the constraints on the constants α, …, γ′ which ensure the following identity :

(s_{1} + \frac{1}{α}) (s_{2} + \frac{1}{γ}) (s_{1} + \frac{1}{β}) = (s_{2} + \frac{1}{α′}) (s_{2} + \frac{1}{γ′}) (s_{1} + \frac{1}{β′}) .

We find that we must have α = β′, β = α′ to have equality for the terms of length 2. Now, to recover symmetry in the terms of length 1 :

\frac{1}{γ} (\frac{1}{α} + \frac{1}{β} ) s_{1} + \frac{1}{αβ} s_{2} ,

one must have

γ = α + β .

Of course, one can introduce parameters in the relation s_{i}s_{j} = s_{j}s_{i}, |i − j| ≠ 1, without destroying the commutation: (s_{i} + \frac{1}{α})(s_{j} + \frac{1}{β}) = (s_{j} + \frac{1}{β})(s_{i} + \frac{1}{α}).

Finally, the braid relations have become the Yang-Baxter relations

(s_{i} + \frac{1}{α}) (s_{i+1} + \frac{1}{α + β}) (s_{i} + \frac{1}{β}) = (s_{i+1} + \frac{1}{β}) (s_{i} + \frac{1}{α + β}) (s_{i+1} + \frac{1}{α}) (2.3.1)

(s_{i} + \frac{1}{α}) (s_{j} + \frac{1}{β}) = (s_{j} + \frac{1}{β}) (s_{i} + \frac{1}{α}) , |i − j| ≠ 1 (2.3.2)

Their graphical representation is easy to remember (taking i = 1) :

\begin{aligned}& [1 2 3] \\ s_{1} + \frac{1}{α} ⧸⧸ & & ⧹ s_{2} + \frac{1}{β} \\ [2 1 3] & & [1 3 2] \\ s_{2} + \frac{1}{α+β} | & & ∥ s_{1} + \frac{1}{α+β} \\ [2 3 1] & & [3 1 2] \\ s_{1} + \frac{1}{β} ⧹⧹ & & ⧸ s_{2} + \frac{1}{α} \\ & [3 2 1] \end{aligned}  \begin{aligned}& [1 2 3 4] \\ s_{1} + \frac{1}{α} ⧸⧸ & & ⧹ s_{3} + \frac{1}{β} \\ [2 1 3 4] & & [1 2 4 3] \\ s_{3} + \frac{1}{β} ⧹ & & ⧸⧸ s_{1} + \frac{1}{α} \\ & [2 1 4 3] \end{aligned}

Vertical edges wear a parameter which is the sum of the two on the opposite sides, other pairs of parallel edges have the same parameter.

In short, forgetting about the labelling of vertices, the index of the simple transpositions s_{i} being specified by the color of edges, one needs only write the parameters α used in the factors s_{i} + 1/α (beware that usually we are writing on edges the inverses of the parameters) :

(2.3.3) \begin{aligned}& • \\ α ⧸⧸ & & ⧹ β \\ • & & • \\ α + β | & & ∥ α + β \\ • & & • \\ β ⧹⧹ & & ⧸ α \\ & • \end{aligned}  \begin{aligned}& • \\ α ⧸⧸ & & ⧹ β \\ • & & • \\ β ⧹ & & ⧸⧸ α \\ & • \end{aligned}

The important constraint is that the parameter on a vertical edge is the sum of the parameters on the two opposite edges. Thus, instead of two parameters, one can take for 𝔖_{3} four independent parameters, keeping the trivial commutation relations for lozenges :

\begin{aligned}& • \\ α ⧸⧸ & & ⧹ γ \\ • & & • \\ γ + δ | & & ∥ α + β \\ • & & • \\ β ⧹⧹ & & ⧸ δ \\ & • \end{aligned}  \begin{aligned}& • \\ α ⧸⧸ & & ⧹ δ \\ • & & • \\ δ ⧹ & & ⧸⧸ α \\ & • \end{aligned}

With M.P. Schützenberger, in our last joint work, we called this relation Yin relation, and we solved the problem of labelling the edges of the permutohedron in such a way that all sub-hexagons satisfy the Yin relation, and that all lozenges commute [12].

Since braid relations connect any two reduced decompositions of the same permutation, if we can label edges of a permutohedron with parameters in such a way as to satisfy relations (2.3.1), (2.3.2), then all paths from the origin to a given permutation will give the same element in ℚ[𝔖_{n}].

To get a coherent choice of parameters for 𝔖_{n}, Yang [32] gave the following recipe, that we can interpret as enriching the permutohedron with a second labelling of vertices, and of edges, according to the following rule :

• choose an arbitrary system of “spectral parameters” [x_{1}, …, x_{n}].

• label each vertex, say σ, with [x_{σ_{1}}, …, x_{σ_{n}}]

• label the edge of color s_{i} connecting σ and σ s_{i} with x_{σ_{i+1}} −x_{σ_{i}} An edge s_{i} with parameter α must be interpreted as a factor (s_{i}+ \frac{1}{α})

and a path must be interpreted as the product of its edges.

In summary, given parameters [x_{1}, …, x_{n}] all different, then all paths in the labelled permutohedron, starting from the origin to a permutation σ, give in ℚ[𝔖_{n}] the same Yang-Baxter element that we shall denote Y_{σ} or Y_{σ}(x_{1}, …, x_{n}). We can formulate the preceding construction as follows :

Proposition 2.3.1. For any choice of distinct spectral parameters [x_{1}, …, x_{n}], there exists a Yang-Baxter basis which is a linear basis of ℚ[x_{1}, …, x_{n}](𝔖_{n}), satisfying the following relations which characterize it (together with normalization Y_{1} = 1) :

(2.3.4)  Y_{σ s_{i}} = Y_{σ} (s_{i} + \frac{1}{x_{σ_{i+1}} − x_{σ_{i}}} ) when ℓ(σs_{i}) > ℓ(σ) .

(2.3.5)  \begin{aligned}& [x_{1} x_{2} x_{3}] \\ s_{1} + \frac{1}{x_{2}−x_{1}} ⧸⧸ & & ⧹ s_{2} + \frac{1}{x_{3}−x_{2}} \\ [x_{2} x_{1} x_{3}] & & [x_{1} x_{3} x_{2}] \\ s_{2} + \frac{1}{x_{3}−x_{1}} | & & ∥ s_{1} + \frac{1}{x_{3}−x_{1}} \\ [x_{2} x_{3} x_{1}] & & [x_{3} x_{1} x_{2}] \\ s_{1} + \frac{1}{x_{3}−x_{2}} ⧹⧹ & & ⧸ s_{2} + \frac{1}{x_{2}−x_{1}} \\ & [x_{3} x_{2} x_{1}] \end{aligned}

Instead of labelling the edges with elements in the group algebra of 𝔖_{n}, one can use the different Hecke algebras generated by divided differences (we do not need the general Hecke algebra, but only the ones generated by ∂_{i} (resp. π_{i}, resp. π̂_{i}). A similar computation as for ℚ[𝔖_{n}] = H^{1,−1} gives :

Proposition 2.3.2. For any choice of distinct spectral parameters [x_{1}, …, x_{n}], there exists linear bases of H^{0,0}, of H^{1,0}, of H^{−1,0} which respectively satisfy, when ℓ(σs_{i}) > ℓ(σ) (starting with Y_{1} = 1) :

(2.3.6)  Y_{σ s_{i}} = Y_{σ} (∂_{i} + \frac{1}{x_{σ_{i+1}} − x_{σ_{i}}} )
(2.3.7)  Y_{σ s_{i}} = Y_{σ} (π_{i} + \frac{1}{x_{σ_{i+1}}/x_{σ_{i}} − 1})
(2.3.8)  Y_{σ s_{i}} = Y_{σ} (π̂_{i} + \frac{1}{1 − x_{σ_{i}}/x_{σ_{i+1}}} ) .

2.4. Maximal Symmetrizers

The operators D_{ω} corresponding to the maximal permutation ω are fundamental.

In fact, they all come from the projector onto the alternating 1dimensional representation of 𝔖_{n}, already used by Cauchy and Jacobi :

f → ∑_{σ∈𝔖_{n}} (^{−}1)^{ℓ(σ)} f^{σ} .

Indeed, writing Δ for the Vandermonde ∏_{1≤i<j≤n}(a_{i} − a_{j}), and a^{ρ} for a_{1}^{n−1}a_{2}^{n−2} ⋯ a_{n}^{0}, one has the following proposition.

Proposition 2.4.1. Given 𝔸 of cardinality n, the divided differences ∂_{ω}, π_{ω} and π̂_{ω} verify :

(2.4.1)  ∂_{ω} = ∑_{σ∈𝔖(𝔸)}(−1)^{ℓ(σ)}σ \frac{1}{Δ} ,

(2.4.2)  π_{ω} = a^{ρ} ∑_{σ∈𝔖(𝔸)}(−1)^{ℓ(σ)}σ \frac{1}{Δ} ,

(2.4.3)  π̂_{ω} = ∑_{σ∈𝔖(𝔸)}(−1)^{ℓ(σ)}σ \frac{(a^{ρ})^{ω}}{Δ} .

Proof. From the determinantal expression of monomials, one sees that (cf. Ex ?) the monomials x^{u} : u ≤ ρ are a generating set of ℤ[a_{1}, …, a_{n}] as a 𝔖_{n}(𝔸_{n}) module. For degree reasons, the two sides of 2.4.1 sends all these monomials to 0, except a^{ρ} which is sent to S_{0...0}(𝔸_{n}) = 1 by the LHS, and to ∑ ±(a^{ρ})^{σ}/Δ = 1 by the RHS. The two operators coincide.

Writing

π_{ω} = π_{n−1,...,1,n} π_{n−1} ⋯ π_{1} = π_{n−1,...,1,n} a_{n−1}∂_{n−1} ⋯ a_{2}∂_{2} a_{1}∂_{1} = π_{n−1,...,1,n} a_{n−1} ⋯ a_{2}a_{1} ∂_{n−1} ⋯ ∂_{1} = a_{n−1} ⋯ a_{2}a_{1} π_{n−1,...,1,n} ∂_{n−1} ⋯ ∂_{1} ,

and iterating, one sees that one can factor out on the left a^{ρ} and thus prove the second identity.

The third one is similarly obtained through the factorization

π̂_{ω} = π̂_{n−1} ⋯ π̂_{1} π̂_{1n...2} .
□

2.5. Yang-Baxter elements and Orthogonality

Back again to the group algebra of 𝔖_{n}, we introduce a quadratic form. Denote by g → g̃ the linear morphism on ℚ[𝔖_{n}] induced by σ → σ^{−1}, σ ∈ 𝔖_{n}, and by g ∩ ω the coefficient of ω in g. For any f, g ∈ Q[𝔖_{n}], let

(2.5.1)  (f , g) := f g̃ ∩ ω .

The linear basis of permutations is self-adjoint with respect to this form :

(2.5.2)  (σ , ωσ) = 1 & (σ , ν) = 0, ν ≠ ωσ .

The next proposition, due to [14], shows that the Yang-Baxter basis is also compatible with this quadratic form. Let Y_{σ} be a Yang-Baxter basis for the parameters [x_{1}, …, x_{n}], and Ŷ_{σ} be the Yang-Baxter basis for the reversed parameters [x_{n}, …, x_{1}].

Proposition 2.5.1. The Yang-Baxter basis {Y_{σ}} of ℚ[x_{1}, …, x_{n}][𝔖_{n}] is adjoint to the Yang-Baxter basis {Ŷ_{ωσ}}, i.e. one has

(2.5.3)  (Y_{σ} , Ŷ_{ωσ}) = 1 & (Y_{σ} , Ŷ_{ν}) = 0, ν ≠ ωσ .

Proof. The proposition is true for Ŷ_{1}, because only Y_{ω} has a term in ω. Suppose it is true for Ŷ_{ν}. We shall prove it for Ŷ_{νs_{i}}, ℓ(νs_{i}) > ℓ(ν). Indeed, Ŷ_{νs_{i}} = Ŷ_{ν}(s_{i} + α) for some α. Therefore

Y_{σ} (s_{i} + α)˜Ŷ_{ν} = (βY_{σ} + γY_{σs_{i}}) ˜ Ŷ_{ν} ,

for some constants β, γ. Therefore, one has just to consider the cases where σ = ων or σs_{i} = ων, and this is where one sees that one had to take reversed parameters for the second Yang-Baxter basis. □

For example, let us check that (Y_{231} , Ŷ_{321}) = 0, taking the parameters [0, α, γ = α + β]. Then there exists some constants δ, ϵ such that

Y_{231}Ŷ_{321} = (s_{1} + \frac{1}{α}) \underbrace{(s_{2} + \frac{1}{γ}) (s_{2} − \frac{1}{β})}_{δ(s_{2}− \frac{1}{β})+ϵ}(s_{1} − \frac{1}{γ})(s_{2} − \frac{1}{α}) .

The factor of ϵ cannot contain ω, and we can eliminate it. The triple (s_{1}+ \frac{1}{α})(s_{2}− \frac{1}{β})(s_{1}− \frac{1}{γ}) can be transformed into (s_{2}− \frac{1}{γ})(s_{1}− \frac{1}{β})(s_{2}+ \frac{1}{α}), but since (s_{2} + \frac{1}{α})(s_{2} − \frac{1}{α}) is a scalar, the remaining expression cannot either contain ω.

The explicit matrix of change of basis for 𝔖_{3}, between the Yang-Baxter basis and the basis of permutations, choosing the vector of parameters [0, a, a + b], is (each row gives the expansion of a Yang element) :

ACE> MatYang2Perm(3,[0,a,a+b]), inverse(%);

[ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ \frac{1}{b} & 1 & 0 & 0 & 0 & 0 \\ \frac{1}{a} & 0 & 1 & 0 & 0 & 0 \\ \frac{1}{(a+b)a} & \frac{1}{a} & \frac{1}{a+b} & 1 & 0 & 0 \\ \frac{1}{b(a+b)} & \frac{1}{a+b} & \frac{1}{b} & 0 & 1 & 0 \\ \frac{ab+1}{(a+b)ba} & \frac{1}{ab} & \frac{1}{ab} & \frac{1}{b} & \frac{1}{a} & 1 \end{matrix} ] , [ \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 \\ −\frac{1}{b} & 1 & 0 & 0 & 0 & 0 \\ −\frac{1}{a} & 0 & 1 & 0 & 0 & 0 \\ \frac{1}{ab} & −\frac{1}{a} & −\frac{1}{a+b} & 1 & 0 & 0 \\ \frac{1}{ab} & −\frac{1}{a+b} & \frac{1}{b} & 0 & 1 & 0 \\ −\frac{ab+1}{(a+b)ba} & \frac{1}{(a+b)a} & \frac{1}{b(a+b)} & −\frac{1}{b} & −\frac{1}{a} & 1 \end{matrix} ]

Apart from signs, these two matrices have the same entries, but distributed differently ! This is the visualization of the preceding proposition.

2.6. Special Yang-Baxter elements

Many interesting elements of the group algebra of 𝔖_{n} can be written in terms of Yang-Baxter elements, for different choices of parameters.

We shall specially use the two cases where [x_{1}, …, x_{n}] = [1, …, n] or [x_{1}, …, x_{n}] = [n, …, 1], denoting

□_{σ} := Y_{σ}(1, …, n) & ∇_{σ} := Y_{σ}(n, …, 1) , σ ∈ 𝔖_{n} .

Let us notice that proposition 2.5.1 implies :

Lemma 2.6.1. {□_{σ}} and {∇_{ωσ}} are two adjoint bases.

The elements □_{σ} and ∇_{σ} allow to write idempotents in the group algebra. Let us check for example that the sum of all permutations of 𝔖_{n} is equal to □_{ω} = Y_{ω}(1, …, n), with ω = maximal permutation = [n, …, 1].

Because we can start a path from the identity to ω by any simple transposition s_{i}, then □_{ω} is such that it has at least one expression with a left factor (s_{i} + 1). The two canonical reduced decompositions that we have encountered extends to two expressions of □_{ω}, which are :

□_{ω} = ((s_{1} + \frac{1}{1}))((s_{2} + \frac{1}{2})(s_{1} + \frac{1}{1})) ⋯ ((s_{n−1} + \frac{1}{n − 1}) ⋯ (s_{1} + 1))

= ((s_{n−1}+\frac{1}{1}) ⋯ (s_{1}+\frac{1}{n − 1})) ⋯ ((s_{n−1}+\frac{1}{1})(s_{n−2}+\frac{1}{2}))((s_{n−1}+\frac{1}{1}))

Suppose that we have noticed that

□_{321} = ∑_{σ∈𝔖_{3}} σ

We want to prove that the similar property holds for

□_{4321} = □_{321}(s_{3} + \frac{1}{3})(s_{2} + \frac{1}{2})(s_{1} + 1) .

We use the fact that (∑_{σ∈𝔖_{3}} σ) ν = ∑_{σ∈𝔖_{3}} σ if ν ∈ 𝔖_{3}. In other words, when multiplying ∑_{σ∈𝔖_{n}} σ by an expression involving only permutations in 𝔖_{n}, one can replace in this expression each permutation by 1.

Therefore

□_{321} \frac{1}{3} (s_{2} + \frac{1}{2})(s_{1} + 1) = □_{321} \frac{1}{3} (1 + \frac{1}{2})(1 + 1) = □_{321} .

Similarly

□_{321} s_{3} \frac{1}{2} (s_{1} + 1) = □_{321} s_{3} \frac{1}{2}(1 + 1) = □_{321} s_{3}

Finally

□_{321}(s_{3} + \frac{1}{3})(s_{2} + \frac{1}{2})(s_{1} + 1) = □_{321}(1 + s_{3} + s_{3}s_{2} + s_{3}s_{2}s_{1}) .

The right hand side is indeed equal to the sum of all permutations of 𝔖_{4}, because it describes how they are obtained from permutations of 𝔖_{3} by inserting 4 in all possible manners.

Such computations can be extended to symmetric groups of higher order, but clearly cost too much efforts to characterize the spaces of dimension 1 that are ∑ σ or ∑ ±σ.

First, we should use that □_{ω} and ∇_{ω} commute with symmetric functions in 𝔸. Secondly, we should test our statements on finite sets of polynomials. In the present case, we should use that there exists a basis of 𝔓𝔬𝔩(𝔸), as a 𝔖𝔶𝔪(𝔸)-module, which consists of polynomials^{5} having a least one partial symmetry in a_{i}, a_{i+1}, except for a polynomial in degree n(n^{−}1)/2.

Theorem 2.6.2. The elements □_{ω}/n! and ∇_{ω}/n! in ℚ[𝔖_{n}] are the two 1-dimensional idempotents of this algebra :

(2.6.1) ∇_{ω} = ∑_{σ∈𝔖_{n}}(−1)^{ℓ(σω)} σ = (^{−}1)^{n(n−1)/2}∂_{ω} Δ(𝔸)
(2.6.2) □_{ω} = ∑_{σ∈𝔖_{n}} σ =  Δ(𝔸) ∂_{ω} .

Proof. ∇_{ω}, as well as ∑ ±σ send a function invariant under s_{i} onto 0, because on can factor s_{i} − 1 on the left of both operators. There remain to check their action on the Vandermonde, for example. But each s_{i} acts by ^{−}1 on Δ(𝔸), therefore ∇_{ω} acts by multiplication by the scalar

(−1 − \frac{1}{1})(−1 − \frac{1}{2})(−1 − \frac{1}{1}) ⋯ (−1 − \frac{1}{n}) ⋯ (−1 − \frac{1}{1}) = ± n! ,

as well as ∑ ±σ. Therefore, (2.6.1) is verified. We leave it to the reader to adapt the reasoning to the proof of (2.6.2). □

5One can take Schubert polynomials, but they will be introduced later. Otherwise, from the basis x^{u} : u ≤ ρ, one easily generates another basis, triangularly equivalent, which have the required property.

2.7. Young Idempotents

We shall not prove statements in this section, but just illustrate how to reformulate Young’s constructions^{6} in terms of Yang-Baxter elements.

Given a composition of n (i.e. an integral vector v which sums to n), let 𝔖_{v} be the Young subgroup of type v, i.e. the diagonal subgroup

𝔖_{v} = 𝔖_{v_{1}} × 𝔖_{v_{2}} × 𝔖_{v_{3}} × ⋯

On denotes by ω_{v} the maximal element of 𝔖_{v}.

Two compositions are called conjugate if the partitions obtained by reordering them are so.

Pairs of conjugate compositions (I, J) are in bijection^{7} with 0^{−}1 matrices, with row-sums I and column-sums J. Such a matrix gives rise to a permutation ζ(I, J) obtained by numbering the non-zero entries from left to right and top to bottom, and reading columnwise . For example, for I = [3, 5, 2, 3] and J = [1, 4, 3, 1, 4], the matrix and the permutation are :

\begin{matrix}sums & 1 & 4 & 3 & 1 & 4 \\ 3 & · & 1 & 1 & · & 1 \\ 5 & 1 & 1 & 1 & 1 & 1 \\ 2 & · & 1 & · & · & 1 \\ 3 & · & 1 & 1 & · & 1 \end{matrix} ,

[\begin{matrix}· & 1 & 2 & · & 3 \\ 4 & 5 & 6 & 7 & 8 \\ · & 9 & · & · & 10 \\ · & 11 & 12 & · & 13 \end{matrix}] ↦ ζ(I, J) = [4, 1, 5, 9, 11, 2, 6, 12, 3, 8, 10, 13] .

Then, the lemma from which Young obtains his natural idempotents can be rewritten in the following way.

Proposition 2.7.1. Let I, J be two conjugate compositions. Then □_{ω_{I}} ℚ[𝔖_{n}] ∇_{ω_{J}} is a 1-dimensional module, and

□_{ω_{I}} · σ · ∇_{ω_{J}} ≠ 0 ⇔ σ = σ′ · ζ(I, J) · σ′′, σ′ ∈ 𝔖_{I}, σ′′ ∈ 𝔖_{J} , where the permutation ζ(I, J) associated to a pair of conjugate compositions has been defined above.

6Young first steps was to write relations in the group algebra, from which he deduced facts about representations. Using Yang-Baxter relations, we have for our part just to handle products of elements of the type s_{i} + 1/k. Young was using more general factors (sums of transpositions + a constant).

7The fact given u, v conjugate, there exists only one such matrix can also be interpreted as the fact that the scalar product (e_{u_{1}}e_{u_{2}} ⋯, h_{v_{1}}h_{v_{2}} ⋯) is equal to 1, or, equivalently, that there exists only one Schur function in common, with multiplicity 1, in the expansion of the two functions.

From this, Young deduces

Corollary 2.7.2. Given two conjugate compositions I, J, there exists non-zero constants c, c′ such that

e := c □_{ω_{I}}ζ(I, J)∇_{ω_{J}} ζ(I, J)^{−1}

be an idempotent, and

c′ ∑_{σ} σ e σ^{−1}

be the central idempotent corresponding to the shape obtained by reordering I.

The proof of proposition 2.7.1 mostly relies on the existence and unicity of a 0^{−}1 matrix with row and column sums I, J. However, it can be adapted to furnish the seemingly much more elaborate result :

Proposition 2.7.3. Let λ be a partition. Fill the successive columns of the diagram of λ (in the S-W corner) (resp. of the conjugate partition λ , in the N-E corner) with 1, …, n. Let ω′ and ω′′ the column readings of these two tableaux, and ν, η their row-reading. Let J be the increasing reordering of of λ, and I = λ .

Then, for every permutation σ greater^{8} than ω′ in the permutohedron, one has that □_{σ}∇_{η} ≠ 0 iff σ and ν belongs to the same double coset 𝔖_{I} ν 𝔖_{J}.

Moreover □_{ω′} ℚ[𝔖_{n}] ∇_{ω′′} is 1-dimensional, with basis □_{ν} ∇_{ω′′}, and □_{ν}∇_{η} is a quasi-idempotent, i.e.

□_{ν}∇_{η}□_{ν}∇_{η} = c □_{ν}∇_{η} , for some c ∈ ℤ, c ≠ 0 .

For example, for λ = [3, 2, 2], the objects appearing in the proposition are

3 6 2 5 1 4 7 → ν = [3625147], ω′ = [3216547] ,

2 4 7 1 3 6 5 → η := [2471365], ω′′ = [2143765] .

We shall only need, in the next chapter , the following related property :

Lemma 2.7.4. Let λ be a partition of n, V_{λ} be the irreducible representation of 𝔖_{n} of type λ, and I be a composition of n. Then the space V_{λ} □_{ω_{I}} is of dimension the multiplicity of the Schur function S_{λ} in the product of complete functions S^{I}. In particular, V_{λ} □_{ω_{I}} is of dimension 1 if I reorders into λ.

8That is, σ = ω′ η, with ℓ(σ) = ℓ(ω′) + ℓ(η).

It is remarkable that one needs only Yang-Baxter relations, together with the nullity (s_{i} + 1)(s_{i} − 1) = 0 to prove all the statements in this section. Instead of playing with reduced decompositions, we shall rather use the coinvariant ring of the symmetric group, to describe representations.

We obtain in Proposition 2.7.3 idempotents by taking Yang-Baxter elements corresponding to two systems of spectral parameters. As shown by Jucys [9], and developed by Cherednik, one can do better, and use a single system (the modified contents of a diagram), though it requires introducing some ϵ’s and taking limits. Otherwise, one has to replace the Yang-Baxter relation

(s_{1} + 1) (s_{2} + \frac{1}{ϵ}) (s_{1} + \frac{1}{ϵ − 1}) = (s_{2} + \frac{1}{ϵ − 1}) (s_{1} + \frac{1}{ϵ}) (s_{2} + 1)

by the new relation

(s_{1} + 1) (s_{2}s_{1} − s_{2} − 1) = (s_{2}s_{1} − s_{1} − 1) (s_{2} + 1) .

For example, for λ = [2, 2],

(s_{3} + 1)(s_{2}s_{1} − s_{1} − 1)(s_{3} − \frac{1}{2})(s_{2} − 1)(s_{3} + 1)

= (s_{3} + 1)(s_{1} + 1)(s_{2}s_{1} − s_{2} − 1)(s_{3} − \frac{1}{2})(s_{2} − 1)(s_{3} + 1)

is a Young idempotent.

2.8. Lagrange Interpolation

In the case of functions already presenting partial symmetries, one can reduce summations over the symmetric group to summations on cosets. The simplest case corresponds to the Lagrange interpolation, where the input function of n variables is symmetrical in the last n^{−}1 ones^{9}.

Given n′, n′′ : n′ + n′′ = n, write 𝔖𝔶𝔪(n′|n′′) for the ring of polynomials in x_{1}, …, x_{n} which are symmetrical in x_{i}, x_{i+1}, i ≠ n′.

Given 𝔸 of cardinality n, let the Lagrange operator L_{𝔸} be

𝔖𝔶𝔪(1|n^{−}1) ∋ f ⟶ ∑_{a∈𝔸}f(a, 𝔸^{−}a)/R(a, 𝔸^{−}a) ∈ 𝔖𝔶𝔪(𝔸_{n}) .

9Even, in the original case of Lagrange, the input function depends on a single variable only, i.e. is of degree 0 in the other variables, which is an easy way of respecting symmetry.

Theorem 2.8.1. Let 𝔸 = {a_{1}, …, a_{n}}, and let ∂_{1}, …, ∂_{n−1} be the divided differences relative to 𝔸. Then for any f ∈ 𝔖𝔶𝔪(1|n^{−}1), one has

(2.8.1)  L_{𝔸}(f) = f(a_{1}, a_{2}, …, a_{n}) ∂_{1} ⋯ ∂_{n−1} .

Proof. Both members of (2.8.1) commute with multiplication with symmetric functions in n variables. Since any symmetric function of 𝔸−a_{1} can be expanded into powers of a_{1} (with coefficients in 𝔖𝔶𝔪(𝔸_{n}), one has to check the theorem only on powers of a variable^{10}, say f = x_{1}^{k}. Rewriting

L_{𝔸}(x_{1}^{k}) = (∑_{a} ±Δ(𝔸 − a) a^{k}) /Δ(𝔸) ,

one recognizes the expression (2.2.2) of S_{0...0,k−n+1}(𝔸), but this is also the function that one obtains as a_{1}^{k}∂_{1} ⋯ ∂_{n−1}. □

Notice that, for functions of one variable only, we obtain by linearity

(2.8.2)  L_{𝔸}(f(x_{1})) = \frac{1}{Δ(𝔸)} |\begin{matrix}a_{1}^{0} & a_{1}^{1} & ⋯ & a_{1}^{n−2} & f(a_{1}) \\ ⋮ & ⋮ & & ⋮ & ⋮ \\ a_{n}^{0} & a_{n}^{1} & ⋯ & a_{n}^{n−2} & f(a_{n}) \end{matrix}| .

There are several ways of interpreting the Lagrange operator. For example, decomposing a rational fraction with simple poles is one of these ways. Indeed, in the case where all the elements of 𝔸 are distinct, given a polynomial f(x), one usually writes

(2.8.3)  \frac{f(x)}{R(x, 𝔸)} = g(x) + ∑_{a} \frac{f(a)}{(x − a)R(a, 𝔸^{−}a)} ,

where g(x) is the quotient in the division of f(x) by R(x, 𝔸). The sum coincides with L_{𝔸}(f(x_{1})/(x − x_{1})).

Multiplying both members by R(x, 𝔸), this becomes

(2.8.4)  f(x) = g(x) R(x, 𝔸) + ∑_{a} \frac{f(a)R(x, 𝔸 − a)}{R(a, 𝔸^{−}a)} .

Since the sum is a polynomial in x of degree ≤ m^{−}1, and since it specializes into f(a) for x = a, then Eq.2.8.4 is one way of writing the division of f(x) by R(x, 𝔸). But one can also introduce 𝔹 := 𝔸 + x, in which case Eq.2.8.2 becomes

(2.8.5)  ∑_{b} \frac{f(b)}{R(b, 𝔹 − b)} = g(x)

10In fact powers ≤ n^{−}1.

and this implies that the quotient can be written (identifying x with a_{n+1}) :

(2.8.6)  g(x) = f(a_{1}) ∂_{1} ⋯ ∂_{n} ,

expression which has the advantage to show that g(x) be a symmetric function ( of x, a_{1}, …, a_{n}). In more details, if f(x) = S^{N}(x − ℂ), then

(2.8.7)  g(x) = S^{N−n}(x + 𝔸 − 𝔹) .

2.9. Newton Interpolation

Everybody knows Taylor’s formula to recover a function in one variable, say a polynomial, knowing its successive derivatives in a point.

Newton, in the Principia, had a harder problem to solve. How to reconstruct a function (the position of a planet) knowing its values at different times ? He had the idea of normalizing differences of positions by the interval of time to which they correspond. That is, he computes

[i, i + 1] := (f(t_{i}) − f(t_{i+1}))/(t_{i} − t_{i+1}) ,

then

[i, i + 2] := ([i, i + 1] − [i + 1, i + 2])/(t_{i} − t_{i+2}) ,

and so on. The reader recognizes, of course, the divided differences f(t_{i})∂_{i}∂_{i+1}∂_{i+2} · · ·.

Having done so, Newton can write

(2.9.1) f(t) = f(t_{0}) + f^{∂} (t − t_{0}) + f^{∂∂} (t − t_{0})(t − t_{1})

+ f^{∂∂∂} (t − t_{0})(t − t_{1})(t − t_{2}) + ⋯

using the symbol f^{∂∂∂...} := f(t_{0})∂_{1}∂_{2}∂_{3} ⋯ to stress the fact that Newton’s formula is a discrete extension of Taylors’s formula (without division by factorials!).

Newton’s formula is linear in f(x). To prove it, it is sufficient to test it on powers of x, or equivalently, to test it on the single function (z − x)^{−1}. Let us go back to an alphabet 𝔸, instead of t_{0}, t_{1}, . . ..

Since f∂_{1} ⋯ ∂_{n−1} = (z^{−}a_{1})^{−1} ⋯ (z^{−}a_{n})^{−1}, one has to check that

(2.9.2) \frac{1}{z^{−}x} = \frac{1}{z^{−}a_{1}} + \frac{x^{−}a_{1}}{(z^{−}a_{1})(z^{−}a_{2})} + \frac{(x^{−}a_{1})(x^{−}a_{2})}{(z^{−}a_{1})(z^{−}a_{2})(z^{−}a_{3})} + ⋯

As we did for Lagrange interpolation, we include x in the set of interpolating points to see what happens. Let us do it twice, in consecutive places, i.e. let us look at the case where a_{n} = x, or a_{n+1} = x.

The equation becomes

\frac{1}{z^{−}x} = \frac{1}{z^{−}a_{1}} + ⋯ + \frac{(x^{−}a_{1}) ⋯ (x^{−}a_{n−1})}{⋯ (z^{−}a_{n−1})(z^{−}x)}
= \frac{1}{z^{−}a_{1}} + ⋯ + \frac{(x^{−}a_{1}) ⋯ (x^{−}a_{n−1})}{⋯ (z^{−}a_{n−1})(z^{−}a_{n})} + \frac{(x^{−}a_{1}) ⋯ (x^{−}a_{n})}{⋯ (z^{−}a_{n})(z^{−}x)} .

The difference is

\frac{(x^{−}a_{1}) ⋯ (x^{−}a_{n−1})}{⋯ (z^{−}a_{n−1})(z^{−}x)} − \frac{(x^{−}a_{1}) ⋯ (x^{−}a_{n−1})}{⋯ (z^{−}a_{n−1})(z^{−}a_{n})} − \frac{(x^{−}a_{1}) ⋯ (x^{−}a_{n})}{⋯ (z^{−}a_{n})(z^{−}x)} ,

which, indeed is null, and this proves (2.9.2), and therefore the Newton formula in general, by induction on n.

Interpolating (1 − zx)^{−1}, instead of (z − x)^{−1}, one gets a formula equivalent to (2.9.2) :

(2.9.3) \frac{1}{1^{−}zx} = \frac{1}{1^{−}za_{1}} + z \frac{x^{−}a_{1}}{(1^{−}za_{1})(1^{−}za_{2})} + ⋯ + z^{k} \frac{R(x, 𝔸_{k})}{R(1, z𝔸_{k+1})} + ⋯

that one often encounters with 𝔸 specialized. For example, one has

\frac{1}{1^{−}zx} = \frac{1}{1^{−}z} + z \frac{x^{−}1}{(1^{−}z)(1^{−}zq)} + ⋯ + z \frac{(x^{−}1) ⋯ (x^{−}q^{n−1})}{(1^{−}z) ⋯ (1^{−}zq^{n})} + ⋯

’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o

Exercises

Ex. 2.1. Extend Leibnitz formula to the following two cases (any i, n ∈ ℕ, any functions f_{j}):

f_{1} ⋯ f_{n} ∂_{i} & fg ∂_{1} ⋯ ∂_{n} .

Ex. 2.2. Given constants α, β, show that the operators D_{i} := π_{i} + α∂_{i} + βs_{i} satisfy the braid relations. Solution. Expanding a product D_{1}D_{2}D_{1} would imply 3^{3} terms involving non trivial relations between π_{i}, ∂_{i} and s_{i}.

One reduces the amount of computations by noticing that the images of isobaric divided differences under the uniform shift: a_{i} → a_{i+1}+ α still verify the braid relations. In other terms, π_{i} = \frac{a_{i}}{a_{i}−a_{i+1}} (1 + s_{i}) becomes

π_{i}^{+} = \frac{a_{i} + α}{a_{i} − a_{i+1}} (1 + s_{i}) = π_{i} + α∂_{i} ,

and therefore, after change of variables, one has just to check that the operators D_{i} := π_{i} + βs_{i} satisfy the braid relations. To check D_{1}D_{2}D_{1} = D_{2}D_{1}D_{2}, one can choose an appropriate basis of the ring of polynomials in a_{1}, a_{2}, a_{3} as a module over 𝔖𝔶𝔪(a_{1}, a_{2}, a_{3}). Let us take the basis a^{v}, with v = [v_{1}, v_{2}, v_{3}] ≤ [0, 1, 2], and compute the image of a^{012} as an example:

a^{012} ⟶^{D_{2}} βa^{021} ⟶^{D_{1}} β^{2}a^{201} − βa^{111} ⟶^{D_{2}} β^{3}a^{210} − (β + β^{2})a^{111} .

The image under D_{2}D_{1}D_{2} is seen to be identical, the checking for the other monomials is not more complicated !

Ex. 2.3. Let 𝔸 = {a_{1}, …, a_{n}}, x, y be two indeterminates. After Scott, Muir III p. 493, show that the following determinant

|\begin{matrix}a_{1} & x & ⋯ & x & 1 \\ y & a_{2} & ⋯ & x & 1 \\ ⋮ & & ... & ⋮ & ⋮ \\ y & y & ⋯ & a_{n} & 1 \\ 1 & 1 & ⋯ & 1 & 0 \end{matrix}|

is equal to (R(x, 𝔸) − R(y, 𝔸))/(x − y). Take the oportunity of computing the minor obtained by suppressing the last row and column. Solution. The minor is equal to

(^{−}1)^{n} S_{1;n−1}(x^{+}y; x^{+}y − 𝔸) .

Ex. 2.4. Let 𝔸 = {a_{1}, …, a_{n}}. Define δ_{i}, i = 1, …, n^{−}1, to be the operator

f → f δ_{i} = (f(… a_{i}, a_{i+1} …) − f(… qa_{i+1}, a_{i}/q …)) (a_{i} − qa_{i+1})^{−1} .

Show that the operators δ_{i} satisfy the braid relations.

Therefore, for any permutation σ ∈ 𝔖_{n}, there is an operator δ_{σ}. Give the image of any monomial under δ_{ω}. Solution. Taking the alphabet 𝔹 = {a_{1}, qa_{2}, …, q^{n−1}a_{n}}, one sees that δ_{i} is a divided difference relative to 𝔹, and there is nothing new to prove. Since ∂_{ω} sends any monomial to a Schur function, then δ_{ω} sends any monomial in 𝔹 (or 𝔸, up to a power of q) to a Schur function in 𝔹.

Ex. 2.5. Let p, q be two parameters. Show that the operators

δ_{i} := (1 + s_{i}) \frac{qa_{i} + p}{a_{i} − a_{i+1}}

satisfy the braid relations, then explicit the maximal operator δ_{ω}. Solution. Rewriting

δ_{i} = −(qa_{i+1} + p)∂_{i} + \frac{q(a_{i}^{+}a_{i+1}) + 2p}{a_{i} − a_{i+1}} ,

one can check δ_{1}δ_{2}δ_{1} = δ_{2}δ_{1}δ_{2}.

Beware that these operators do not preserve polynomials.

A better proof is to use conjugation by the Vandermonde Δ(𝔸). One has

Δ(𝔸)^{−1} δ_{i} Δ(𝔸) = (a_{i}^{−}a_{i+1})^{−1}δ_{i}(a_{i}^{−}a_{i+1}) = ∂_{i}(qa_{i} + p) .

Now, both Δ(𝔸)^{−1}δ_{1}δ_{2}δ_{1}Δ(𝔸) and Δ(𝔸)^{−1}δ_{2}δ_{1}δ_{2}Δ(𝔸) are equal to ∂_{321} (qa_{1}^{+}p)^{2}(qa_{2}^{+}p).

More generally, with n = |𝔸|, ω = [n, …, 1], one has

Δ(𝔸)^{−1}δ_{ω}Δ(𝔸) = ∂_{ω} ∏_{1≤i<j≤n}(qa_{i} + p)^{n−i} .

For example, the image of the monomial a_{1}^{2}a_{2} under δ_{321} is

Ψ_{12}(𝔸) \frac{(qa_{1} + p)^{2}(qa_{2} + p)}{(a_{1}^{−}a_{2})(a_{1}^{−}a_{3})(a_{2}^{−}a_{3})} ,

where Ψ_{12} is the monomial function of index [1, 2].

Ex. 2.6. Let 𝔸 = {a_{1}, …, a_{n}}, x be an indeterminate. Compute

(x − a_{1})(x + a_{2}) ⋯ (x + a_{n})(a_{1} + a_{2}) ⋯ (a_{1} + a_{n}) ∂_{1} ⋯ ∂_{n−1} .

Solution. The answer is

\begin{cases}(x − a_{1}) ⋯ (x − a_{n}) & n odd \\ −2 ∑ x^{2n−2j−1}Λ^{2j+1}(𝔸) & n even \end{cases} ,

and this is a special case of computation of Euler-Poincaré characteristic.

To be more precise, let χ be the Euler-Poincaré morphism :

𝔖𝔶𝔪(a_{1} | a_{2}, …, a_{n}) ∋ f ⟶^{χ} (a_{1}^{+}a_{2}) ⋯ (a_{1}^{+}a_{n}) f ∂_{1} ⋯ ∂_{n−1} ∈ 𝔖𝔶𝔪(𝔸) .

One finds that χ(1) = 1 when n is odd, and = 0 otherwise, that

χ(a_{1}(1^{−}a_{1})^{−1}) = ∑_{j≥1} \frac{1}{1^{−}z} S^{j}((1^{−}z)𝔸)|_{z=−1} = ∑_{H} S_{H}(𝔸)

sum over all hook partitions H, and that

χ((1^{+}a_{2}) ⋯ (1^{+}a_{n})) = (1^{+}a_{1})(1^{+}a_{2}) ⋯ (1^{+}a_{n}) χ((1^{+}a_{1})^{−1})

= \begin{cases}∑ Λ^{2j}(𝔸) & if n odd \\ − ∑ Λ^{2j+1}(𝔸) & if n even \end{cases} .

Writing

(x^{−}a_{1})(x^{+}a_{2}) ⋯ (x + a_{n}) = (x^{+}a_{1})(x^{+}a_{2}) ⋯ (x + a_{n})(2x(x^{+}a_{1})^{−1} − 1) ,

one concludes.

Ex. 2.7. Let 𝔸, 𝔹 be of the same cardinality n. Show that

1 − a_{1} ⋯ a_{n} = ∑_{j}(1 − a_{j}) ∏_{i:i≠j} \frac{b_{j}^{−}a_{i}}{b_{j}^{−}b_{i}} .

Solution. To recognize the Lagrange interpolation, one replaces the pair (𝔸, 𝔹) by the pair (𝕏 = {a_{1}b_{1}, …, a_{n}b_{n}}, 𝔹). The sum to compute is

∑_{j} b_{j}^{−1} R(b_{j}, 𝕏) R(b_{j}, 𝔹 − b_{j})^{−1} .

In other words, one has to compute L_{𝔹}(x^{i}), for ^{−}1 ≤ i ≤ n^{−}1. Only the two extreme terms contribute, (−1)^{n−1}(b_{1} ⋯ b_{n})^{−1} for the first one, 1 for the second.

Ex. 2.8. Let 𝔸, 𝔹 be of the same cardinality n, and ∂_{1}, …, ∂_{n−1} be the divided differences relative to 𝔹.

Show that

(1^{−}a_{1})(1+a_{n}+a_{n}a_{n−1}+…+a_{n} ⋯ a_{2}) = (b_{1}−b_{1}a_{1}) ⋯ (b_{1}−b_{n}a_{n})b_{1}^{−1} ∂_{1} ⋯ ∂_{n−1} .

Solution. Writing ∂_{𝔹} = ∂_{1} ⋯ ∂_{n−1}, one decomposes the right hand side into

(b_{1}−b_{1}a_{1}) ⋯ (b_{1}−b_{n−1}a_{n−1})∂_{𝔹}+−1/b_{1}(b_{1}−b_{1}a_{1}) ⋯ (b_{1}−b_{n−1}a_{n−1})(b_{n}a_{n})∂_{𝔹} .

The contribution of the first part is (b_{1}^{n−1} − b_{1}^{n−1}a_{1})∂_{𝔹} = 1 − a_{1}. For what concerns the second, define 𝔹′ = {b_{1}, …, b_{n−1}}. Using ∂_{𝔹} = ∂_{𝔹′}∂_{n−1}, and showing by induction that

1/b_{1}(b_{1} − b_{1}a_{1}) ⋯ (b_{1} − b_{n−1}a_{n−1})∂_{𝔹′}

is independent of 𝔹, one gets in total

(1 − a_{1}) + a_{n}(1 − a_{1})(1 + a_{n−1} + … + a_{n−1} ⋯ a_{2}) ,

which is the required identity.

Ex. 2.9. Let 𝔸 be a totally ordered set of n^{+}1 distinct complex numbers, and ∂_{1}, …, ∂_{n} be the divided differences associated to 𝔸. Let Γ be a simple curve enclosing 𝔸, f(z) be a function analytic in a disk containing 𝔸.

Show, after Hermite, that

f(a_{1})∂_{1} ⋯ ∂_{n} = \frac{1}{2π\sqrt{^{−}1}} ∫_{Γ} \frac{f(x)}{R(x, 𝔸)}dx .

Solution. It suffices to test both sides of the equation on the basis of polynomials

{S^{n}(x + a^{−}𝔸), a ∈ 𝔸} ∪ {S^{n+k+1}(x − 𝔸), k ≥ 0}

For the first polynomials, both members are equal to 1 (we assume known the residue of 1/(x − a)). For the second family, one has indeed

S^{k+1}(𝔸 − 𝔸) = 0 = residue of x^{k} .

Hermite’s expression may be used for Lagrange’s or Newton’s interpolation formulas.

Ex. 2.10. For any positive integer p, let ℕ =: {0, 1, …, p}. Define the Stirling numbers (of the second kind) to be the complete functions in ℕ_{p}, the (positive) Stirling numbers of the first kind to be the elementary symmetric functions of ℕ_{p}.

Show that, for any n ∈ ℕ, one has

x^{n} = S^{n−1}(ℕ_{1}) x + S^{n−2}(ℕ_{2}) x(x^{−}1) + S^{n−3}(ℕ_{3}) x(x^{−}1)(x^{−}2) + ⋯,
= ∑_{i,j}(^{−}1)^{i}x^{j−i}S^{n−j}(ℕ_{j})Λ^{i}(ℕ_{i−1}) ,

\frac{1}{z^{−}x} = \frac{1}{z} + \frac{x}{z(z^{−}1)} + \frac{x(x^{−}1)}{z(z^{−}1)(z^{−}2)} + ⋯ + \frac{S^{p}(x^{−}ℕ_{p−1})}{S^{p+1}(z^{−}ℕ_{p})} + ⋯

Solution. This is the Newton interpolation at integral points.

Ex. 2.11. Let x be an element of binomial type, n a positive integer. Following Naszadi, write x^{n} as a linear combination of Λ^{n}(x), Λ^{n}(x+

1), …, Λ^{n}(x + n^{−}1). Solution. The required decomposition is not given by the Newton interpolation at integral points (called Stirling interpolation), because the polynomials that we are given have the same degree in x.

One notices that the determinant

|\begin{matrix}x^{n} & Λ^{n}(x) & ⋯ & Λ^{n}(x + n^{−}1) \\ n^{n} & Λ^{n}(n) & ⋯ & Λ^{n}(2n^{−}1) \\ ⋮ & ⋮ & & ⋮ \\ 1^{n} & Λ^{n}(1) & ⋯ & Λ^{n}(n) \end{matrix}|

is null, because the space of polynomials in x, which are divisible by x and of degree ≤ n, is of dimension n. One rewrites the binomial coefficients in the determinant as complete functions of n + 1. For example, for n = 4, the determinant becomes

|\begin{matrix}x^{4} & Λ^{4}(x) & Λ^{4}(x^{+}1) & Λ^{4}(x^{+}2) & Λ^{4}(x^{+}3) \\ 4^{4} & S^{0}(5) & S^{1}(5) & S^{2}(5) & S^{3}(5) \\ 3^{4} & · & S^{0}(5) & S^{1}(5) & S^{2}(5) \\ 2^{4} & · & · & S^{0}(5) & S^{1}(5) \\ 1^{4} & · & · & · & S^{0}(5) \end{matrix}|

The expansion along the first column and the first row produces the required expression:

∑_{0≤i,j≤n−1} ±Λ^{n}(x + j) (n^{−}i)^{n}Λ^{i−j}(n^{+}1) = 0 .

Ex. 2.12. Let f(x) be a polynomial of degree n. After Carlitz, compute the determinant |f(q^{i+j})|_{0≤i,j≤n}.

Solution. Write f(x) = S^{n}(x − 𝔹) (supposing the polynomial to be exactly of degree n, we may normalize it). Using in each row of the determinant the Newton interpolation for the function f(q^{i}x) at points q^{0}, q^{1}, q^{2}, …, one transforms it into

|q^{ij}S^{n−j}(q^{i} + ⋯ + q^{i+j} − 𝔹)|_{0≤i,j≤n} ,

up to the factor Δ(q^{0}, …, q^{n}).

With q-integers [i] := 1 + q + ⋯ + q^{i−1}, the determinant may be rewritten|q^{ni}S^{n−j}([j + 1] − 𝔹/q^{i})|. Multiplying it by the inverse of the q-Pascal matrix [S^{n−j−i}([j+1])], which is no other than [S^{n−i−j}(−[n−

i])], one transforms the determinant into

|q^{ni}S^{n−j}(−𝔹/q^{i})| = |q^{i}S^{n−j}(−𝔹)| .

In the end, one gets

±S^{n}(−𝔹) ⋯ S^{0}(−𝔹)(Δ(q^{0}, …, q^{n}))^{2} .

Ex. 2.13. Let n ∈ ℕ, 𝔹_{k} = {b_{1}, …, b_{n}}, 0 ≤ k ≤ n. Write the interpolation of polynomials in x in the basis

{x^{n} = S^{n}(x − 𝔹_{0}), x^{n−1}(x^{−}b_{1}) = S^{n}(x^{−}𝔹_{1}), …, S^{n}(x^{−}𝔹_{n})} ,

knowing f(0) and the values c_{i} = f(b_{i}), 1 ≤ i ≤ n. Solution. This is the Newton interpolation for the function f(x)x^{−n} of the variable z = 1/x at the points 1/b_{i}, completing with the value f(0). For example, for n = 3, and g(x) of degree ≤ 2, one has

f(x)x^{−3} = g(x) = g(1/b_{1})+g∂_{1}(x^{−1}−b_{1}^{−1})+g∂_{1}∂_{2}(x^{−1}−b_{1}^{−1})(x^{−1}−b_{2}^{−1}) ,

and therefore, for f of degree ≤ 3,

f(x) = g(b_{1})x^{3} + g∂_{1} b_{1}^{−1}x^{2}(b_{1}^{−}x) + g∂_{1}∂_{2} b_{1}^{−1}b_{2}^{−1}x(b_{1}^{−}x)(b_{2}^{−}x)

+ f(0) b_{1}^{−1}b_{2}^{−1}b_{3}^{−1}(b_{1}^{−}x)(b_{2}^{−}x)(b_{3}^{−}x) ,

the last term being obtained by identification in x = 0.

CHAPTER 3 The Ring of Polynomials modulo 𝔖𝔶𝔪_{+}

’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o

As a linear space on which acts 𝔖_{n}, the group algebra H = ℚ[𝔖_{n}] is isomorphic to the linear span of x^{ρ} := x_{1}^{n−1}x_{2}^{n−2} ⋯ x_{n}^{0}, the correspondence exchanging σ and (x^{ρ})^{σ}.

If instead of ρ, one takes another weight λ = [λ_{1}, λ_{2}, …, λ_{n}], then the linear span 𝕍^{λ} of the orbit of x^{λ} is of dimension n!/dim(𝔖𝔱𝔞𝔟(λ)) = n!/α_{1}! α_{2}! ⋯, instead of n!, denoting by 𝔖𝔱𝔞𝔟(λ) the subgroup of §_{n} leaving λ invariant, and writing λ = 1^{α_{1}}2^{α_{2}} · · ·.

The H-spaces 𝕍^{λ} are called permutation representations. They are the easier to describe. However, these spaces can be in general decomposed into smaller spaces, and this is rather these smaller spaces of representations of the symmetric group that one wants to describe. This was first done by Alfred Young, using relations in the group algebra ℚ[𝔖_{n}].

Let us just assume from Young’s theory the existence of central idempotents indexed by partitions, and decomposing the identity in ℚ[𝔖_{n}] :

(3.0.4)  1 = ∑_{λ: |λ|=n} e_{λ} ,

each e_{λ} being obtained, as mentioned in Cor. 2.7.2, by taking any pair of conjugate compositions I, J, with I reordering to I, and generating a central element :

e_{λ} = c_{I,J} ∑_{σ} σ □_{I} ζ(I, J) ∇_{J} σ^{−1} ,

with c_{I,J} such that e_{λ}^{2} = e_{λ}.

44 3. THE RING OF POLYNOMIALS MODULO 𝔖𝔶𝔪_{+}

We refer to the relevant two pages in Macdonald’s book for what concerns the representations of the symmetric group. We shall show that, modulo the ideal generated by symmetric polynomials without constant term, some permutation modules become irreducible, and that conversely, every irreducible representation of 𝔖_{n} can be described in this manner. Orthonormal bases will be provided by Yang-Baxter relations. As a by-product, “straightening elements” or giving matrices of representation will be easy.

3.1. The Coinvariant Ring of 𝔖_{n}

Given n indeterminates x_{1}, …, x_{n}, let 𝔖𝔶𝔪_{+} be the ideal generated by symmetric polynomials without constant term, and let

ℭ𝔬ℑ𝔫𝔳 := ℚ[x_{1}, …, x_{n}]/𝔖𝔶𝔪_{+} .

This ring is called the coinvariant ring of 𝔖_{n}. As a 𝔖_{n}-space, it is isomorphic to the group algebra of 𝔖_{n}, as well as to the space of harmonic polynomials which appears in Haiman’s lectures.

Given any decomposition of x into two disjoint subsets x′, x′′, and any symmetric function f, then

(3.1.1)  f(x′) ≡ f(−x′′) ,

because in the expansion of f(x − x′′), there remains, modulo 𝔖𝔶𝔪_{+}, only the term of degree 0 in x.

As a consequence, x_{i}^{n} ≡ 0, S_{n−1,n−1}(x_{i} + x_{j}) ≡ 0 when i ≠ j, or more generally

(3.1.2)  S_{k^{r}}(x_{1} + ⋯ + x_{r}) ≡ 0 when k > n − r ,

because S_{k^{r}}(−x_{r+1} − ⋯ − x_{n}) = 0.

Writing monomials as Schur functions in flags of alphabets, and using nullities (3.1.2), one sees that ℭ𝔬ℑ𝔫𝔳 is generated by the monomials x^{u} : u ≤ ρ := [n^{−}1, …, 1, 0], as well as the monomials x^{v} : v ≤ [0, 1, …, n^{−}1].

Let us define a scalar product ( , ) :

(3.1.3)  (f , g) := fg ∂_{ω}|_{x_{1}=0=x_{2}=···} ,

using the maximal divided difference on x_{1}, …, x_{n}, followed by specialization in 0.

Since the target of ∂_{ω} is 𝔖𝔶𝔪, the scalar product consists in evaluating the image of the product of fg under ∂_{ω} in ℭ𝔬ℑ𝔫𝔳. Two homogeneous polynomials can have a non-zero scalar product only if they are of complementary degrees (i.e. the degree of their product is n(n^{−}1)/2).

Explicitly, the scalar product of two monomials x^{u}, x^{v} is

(3.1.4) (x^{u}, x^{v}) = (x^{u+v}, 1) = \begin{cases}(−1)^{ℓ(σ)} & if ∃ σ : u^{+}v & = [… 210]^{σ} \\ 0 & otherwise \end{cases}

In words, to evaluate the scalar product of two monomials, one has to test whether the vector u + v is a permutation of ρ, and if so, to keep the sign of the permutation.

The subspace of ℭ𝔬ℑ𝔫𝔳 of degree d being dual to the subspace of degree n(n^{−}1)/2, one has the following test for the vanishing of a class modulo 𝔖𝔶𝔪_{+}.

Lemma 3.1.1. Let f be an homogeneous polynomial of degree d, and d′ = n(n^{−}1)/2 − d. Then

(3.1.5)  f ≡ 0 mod 𝔖𝔶𝔪_{+} ⇔ (f, x^{v}) = 0 ∀v : |v| = d′ .

In the preceding lemma, one can of course restrict the test to the vectors v such that v ≤ ρ, or v ≤ ρ^{ω}.

3.2. Young’s Natural Representations

Let us look at orbits of monomials under the symmetric group. For example, let us start with 𝔖_{5} and x^{00033}. With s_{2}, s_{3}, s_{4}, we generate the five monomials written on the fol-

lowing graph :

(3.2.1)  [00033] ; ∥ ; [00303] ; ⧸  ⧹ ⧹ ⧹ ; [03003]  [00330] ; ⧹ ⧹ ⧹  ⧸ ; [03030]

I claim that relations (3.1.2) allow to express all other monomials in the orbit of x^{00033} in terms of these five monomials.

For example, the image of x^{03003} under s_{1} is x^{30003}, and one has

(3.2.2) x^{30003} +x^{03003} +x^{00303} +x^{00033} ≡ −x^{00003}x^{00003} = −x^{00006} ≡ 0 .

More complicated seems to reduce the image of the bottom element under s_{3}. However, one has

x^{03300} + x^{03030} + x^{03003} + x^{00330} + x^{00303} + x^{00033} ≡ 0 ,

because the left-hand side is a symmetric function of x_{2}, …, x_{5} and therefore, congruent to a function of degree 6 of x_{1}.

These type of relations results in fact from relations written by Young in the group algebra of 𝔖_{n}. For example, instead of (3.2.2), Young’s relations would give

x^{30003}(1 + τ_{12} + τ_{13} + τ_{14}) = 0 ,

where τ_{ij} is the transposition of i, j.

Another way of describing representations is through “straightening” of tableaux to render them standard by successive improvements [2, 3, 6], but it also results from Young’s computations.

We shall bypass straightening totally by using the scalar product on ℭ𝔬ℑ𝔫𝔳.

Let us eliminate tableaux as well.

Instead of starting from [00033], we start from the vector [01201] and we sort it (increasingly), using successive transpositions. This time we obtain :

(3.2.3)  Γ_{32} :=  [01201] ; ∥ ; [01021] ; ⧸  ⧹ ⧹ ⧹ ; [00121]  [01012] ; ⧹ ⧹ ⧹  ⧸ ; [00112]

and we have to stop because no other sorting is possible.

Evaluating the scalar products between the vertices of the two graphs, we get the matrix (0 are replaced by dots) :

[ \begin{matrix}1 & · & · & · & · \\ · & −1 & · & · & · \\ · & · & 1 & · & · \\ · & · & · & 1 & · \\ −1 & · & · & · & −1 \end{matrix} ] ,

which happens to be triangular, with a diagonal of ±1.

Since we knew that x^{03030}, x^{03003}, x^{00330}, x^{00303}, x^{00033} generates the space V_{00033}, then this proves that these five elements are linearly independent, and moreover this gives a dual space^{1} in complementary degree.

Instead of starting with a partition, one can take any composition and the corresponding monomials. For example, to the composition [2, 2, 3], one associates the monomials x^{00 22 444} and x^{01 01 012}, and generate a graph with 21 vertices, the matrix of scalar products being

1which is not closed under the action of the symmetric group; x^{01201} ℚ[𝔖_{n}] is of dimension 20, which is the dimension of the full space in degree 4.

[ \begin{matrix}− & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · \\ · & + & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · \\ · & · & + & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · \\ · & · & · & − & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · \\ · & · & · & · & − & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · \\ · & · & · & · & · & − & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · \\ + & · & · & · & · & · & + & · & · & · & · & · & · & · & · & · & · & · & · & · & · \\ · & · & · & · & · & · & · & + & · & · & · & · & · & · & · & · & · & · & · & · & · \\ · & · & · & · & · & · & · & · & + & · & · & · & · & · & · & · & · & · & · & · & · \\ · & · & · & · & · & · & · & · & · & + & · & · & · & · & · & · & · & · & · & · & · \\ · & · & − & · & · & · & · & · & · & · & − & · & · & · & · & · & · & · & · & · & · \\ · & · & · & · & · & · & · & · & · & · & · & − & · & · & · & · & · & · & · & · & · \\ − & · & · & · & · & · & · & · & · & · & · & · & − & · & · & · & · & · & · & · & · \\ · & · & · & · & · & · & · & · & · & · & · & · & · & − & · & · & · & · & · & · & · \\ − & · & + & · & · & · & · & · & · & · & · & · & · & · & + & · & · & · & · & · & · \\ · & + & · & · & − & · & · & · & · & · & · & · & · & · & · & + & · & · & · & · & · \\ · & · & + & · & · & · & · & · & · & · & · & · & · & · & · & · & + & · & · & · & · \\ · & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · & + & · & · & · \\ · & · & · & · & · & − & · & + & · & · & · & · & · & · & · & · & · & · & − & · & · \\ · & · & − & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · & · & − & · \\ · & · & · & + & · & + & · & · & · & · & · & − & · & · & · & · & · & · & · & · & + \end{matrix} ]

the rows being indexed by the monomials with the following exponents : [0022444, 0024244, 0202444, 0024424, 0042244, 0204244, 0042424, 0402244, 0204424, 0240244, 0402424, 4002244, 0240424, 0420244, 4002424, 0244024, 0420424, 4020244, 0424024, 4020424, 4024024]

For a general weight, we could proceed in the same way, but with the tools that we have introduced up to now, it is not too easy to handle relations modulo 𝔖𝔶𝔪_{+}, and to express any monomial in a chosen basis.

Let us see how to restrict relations to straightforward vanishing properties.

Given a composition λ = [λ_{1}, …, λ_{r}], let

(3.2.4)  μ(λ) := [0^{λ_{1}}, λ_{1}^{λ_{2}}, (λ_{1}^{+}λ_{2})^{λ_{3}}, …, (λ_{1}^{+} + ⋯^{+}λ_{r−1})^{λ_{r}}] ,

using exponents for repetitions, and

(3.2.5) ζ(λ) := [(0, 1, …, λ_{1}^{−}1), (0, 1, …, λ_{2}^{−}1), …, (0, 1, …, λ_{r}^{−}1)]

(parentheses have to be erased, they have been added to facilitate the comprehension).

For example, if λ = [4, 2, 2, 1], then μ = [0^{4}, 4^{2}, 6^{2}, 8^{1}] = [000044668], and ζ = [012301010].

We define the graph Γ_{λ} to be the graph with top element ζ(λ), and edges the simple transpositions which allow to sort ζ(λ) recursively.

For example, for λ = [3, 2, 1], the graph Γ_{321} is

[figure: 012.01.0; 012.001; 01.02.1.0; 01.02.01; 01.012.0; 0012.1.0; 01.002.1; 01.01.02; 0012.01; 00112.0; 01.0012; 001.02.1; 0011.02; 00012.1; 001.012; 00112]

s_{5} , =^{s_{4}} , − − −^{s_{3}} , = = =^{s_{2}}

Lemma 3.2.1. Given a partition λ, two conjugate compositions I, J such that λ be different from the reordering of I, given any permutations σ, σ′, then

x^{μ(λ)} σ ∇_{ω(J)} σ′ □_{ω(I)} = 0 .

Proof. The statement is equivalent to the nullities

(x^{u} ∇_{ω(J)} σ′ □_{ω(I)} , x^{v}) = 0 ,

for all monomials x^{u} in the orbit of x^{μ(λ)}, all monomials x^{v} of complementary degree. Transferring □_{ω(I)} on the right, it becomes ∇_{ω(I)}. However, the two conditions that x^{u} ∇_{ω(J)} ≢ 0 and x^{v} ∇_{ω(I)} ≢ 0 cannot be simultaneously realized^{2} and (x^{u} ∇_{ω(J)} σ, x^{v}∇_{ω(I)}) = 0. □

Denote W_{λ} the linear span (in ℭ𝔬ℑ𝔫𝔳) of the monomials in the orbit of x^{μ(λ)}. The preceding lemma proves that there is no component of type ≠ λ in W_{λ}.

2Let η be the partition obtained by reordering I. Then the non vanishing of x^{u}∇_{ω(J)} implies that η^{∼} ≥ λ^{∼}, with respect to the natural order on partitions.

But the non vanishing of x^{v}∇_{ω(I)} implies that |v| ≥ ℓ(ω(I)) = ℓ(ω(η) and this last condition means that η ≥ λ.

To prove that W_{λ} is irreducible (in char. 0), according to Lemma 2.7.4 we have to check that the subspace invariant under 𝔖(λ) be 1dimensional, which the same as requiring that the space W_{λ} □_{ω(λ)} be 1-dimensional. In fact, one will show that the span of x^{u}□_{ω(λ)} : |u| = |μ(λ)| is 1-dimensional, by proving the equivalent statement in complementary degree :

(3.2.6)  ⟨ x^{v} ∇_{ω(λ)} : |v| = |ζ(λ)| ⟩  is 1-dimensional.

Indeed, the image of any polynomial under ∇_{ω(λ)} is divisible by the product of Vandermonde determinants x^{ζ(λ)}∇_{ω(λ)}, the image of this element in ℭ𝔬ℑ𝔫𝔳 is ≠ 0 and this proves (3.2.6).

Given a composition J, and the two copies Γ_{J}(μ(J)) and Γ_{J}(ζ(J)) of the graph Γ_{J}, with top element μ(J), or ζ(J) respectively, let Q_{J} be the matrix of scalar products (x^{u}, x^{v}), u being a vertex of the first graph, v of the second one.

Taking a total order compatible with the graph, it is easy to check that Q is triangular, with a diagonal of ±1. This means that the two sets of monomials are “almost adjoint” bases of two spaces, and expressing an element in the first space is obtained by evaluating scalar products with the second basis.

In particular, to represent a permutation σ, one needs only evaluate the scalar products ((x^{u})^{σ} , x^{v}). The representation that one thus obtain is in fact Young’s natural representation^{3}

We summarize this construction in the next theorem.

Theorem 3.2.2. Let J be a composition of weight n, {u} the vertices of Γ_{J}(μ(J)), {v} the vertices of Γ_{J}(ζ(J)).

Let Q_{J} be the matrix [(x^{u}, x^{v})], and for any permutation σ ∈ 𝔖_{N}, Q_{J}^{σ} be the matrix [((x^{u})^{σ}, x^{v})].

Then

σ → Q_{J}^{−1} · Q_{J}^{σ}

is an irreducible representation of 𝔖_{n}, of type the reordering of J.

For example, for J = [2, 4], then μ(J) = [00 2222], ζ(J) = [01 0123], the images of the basis {u} under the permutation σ = [2, 3, 4, 5, 6, 1] is [022220], [202220], [220220], [002222], [222020], [020222], [022022], [200222], [202022] giving the following matrix of scalar products:

3One can recognize that the restriction of the scalar product to the monomials having exponents a permutation of μ(J), ζ(J) respectively, coincides with the bilinear form on tableaux resulting from Young’s construction.

Q_{24}^{[234561]} = [\begin{matrix}1 & −1 & 1 & 0 & −1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & −1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & −1 \\ −1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & −1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & −1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & −1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \end{matrix}]

from which follows the representation matrix

Q_{24}^{−1} Q_{24}^{[234561]} = [\begin{matrix}−1 & 1 & −1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & −1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & −1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & −1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ −1 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ −1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \end{matrix}]

ACE> Perm2RepNatural([4,2],[2,3,4,5,6,1],[4,2]):
# the sixth-power must be the identity
ACE> subs(0=`.`,evalm(%^6));
[1    .    .    .    .    .    .    .    .]
[.    1    .    .    .    .    .    .    .]
[.    .    1    .    .    .    .    .    .]
[.    .    .    1    .    .    .    .    .]
[.    .    .    .    1    .    .    .    .]
[.    .    .    .    .    1    .    .    .]
[.    .    .    .    .    .    1    .    .]
[.    .    .    .    .    .    .    1    .]
[.    .    .    .    .    .    .    .    1]

3.3. Yang-Baxter Bases

We have written graphs, but only used simple transpositions to label the edges. In chapter 2, we saw that Yang-Baxter relations are a more powerful tool than pure braid relations without parameters.

Let us take the graph Γ_{λ} corresponding to a (decreasing) partition, but this time we label the vertices differently, starting with

ξ(λ) := [(0, 1, …, λ_{1}^{−}1), (^{−}1, 0, …, λ_{1}^{−}2), …, (^{−}r^{+}1, …, λ_{r} − r)]

(we have written extra parentheses only to facilitate the comprehension).

We perform the same simple transpositions as for Γ_{λ}, but this time we record the differences of values of the two components exchanged, as we proceeded^{4} in (2.3.5) :

[…, v_{i}, v_{i+1}, …] → […, v_{i+1}, v_{i}, …] ⇒ label s_{i} + \frac{1}{v_{i} − v_{i+1}} .

[01201] ; ∥ ; [01021] ; ⧸  ⧹ ⧹ ⧹ ; [00121]  [01012] ; ⧹ ⧹ ⧹  ⧸ ; [00112]  \begin{aligned}& 0 1 2 \overline{1} 0 \\ ∥ & s_{3}+ \frac{1}{3} \\ & 0 1 \overline{1} 2 0 \\ ^{s_{2}+ \frac{1}{2}}⧸ & & ⧹ ⧹ ⧹^{s_{4}+ \frac{1}{2}} \\ 0 \overline{1} 1 2 0 & & 0 1 \overline{1} 0 2 \\ s_{4}+ \frac{1}{2}⧹ ⧹ ⧹ & & ⧸s_{2}+ \frac{1}{2} \\ & 0 \overline{1} 1 0 2 \end{aligned}

Initial Graph  Yang-Baxter Graph

Given λ, the Yang-Baxter graph of type λ is the graph isomorphic to Γ_{λ}, with edges labelled by elements s_{i} + 1/α determined by the initial vector of parameters ξ(λ), and with vertices labelled by permutations, starting with the identity permutation :

(3.3.1)  \begin{aligned}& 12345 \\ ∥ & s_{3}+ \frac{1}{3} \\ & 12435 \\ ^{s_{2}+ \frac{1}{2}}⧸ & & ⧹ ⧹ ⧹^{s_{4}+ \frac{1}{2}} \\ 14235 & & 12453 \\ s_{4}+ \frac{1}{2}⧹ ⧹ ⧹ & & ⧸s_{2}+ \frac{1}{2} \\ & 14253 \end{aligned}

The Yang-Baxter polynomials θ_{u} are the images of the monomial x^{μ(λ)} under this graph (from top to bottom), indexed by the vertices of the first graph (3.2.1). The adjoint Yang-Baxter polynomials θ̃_{v} are the images of x^{ζ(λ)} under the same graph, from bottom to top.

4The only difference is that now the labels of vertices of our Yang-Baxter graphs can be more general than permutations. In fact, for the same graph, we have to use several labellings, and one of them is with permutations. As for signs, either one chooses v_{i} − v_{i+1} or v_{i+1} − v_{i}, but of course uniformly!

For example, for λ = [3, 2], these two families of polynomials are obtained as images of x^{00033}, or x^{01201} respectively :

ACE> gg:=GrapheYB([3,2]):
ACE> op(3,gg);
   3   3    3   3        3   3    3   3        3   3        3   3
[x4  x5 , x3  x5  +1/3 x4  x5 , x3  x4  +1/2 x4  x5  +1/2 x3  x5 ,
      3   3         3   3         3   3
    x2  x5  + 1/2 x4  x5  + 1/2 x3  x5 ,
      3   3         3   3         3   3        3   3        3   3
    x2  x4  + 3/4 x4  x5  + 1/2 x2  x5  +1/2 x3  x4  +1/4 x3  x5 ]
# To get the adjoint basis, one has to take the conjugate
# partition or read the graph from bottom to top
ACE> op(4,GrapheYB([2,2,1]);
         2          2              2          2              2
[x3 x4 x5 , x3 x5 x4  +1/2 x3 x4 x5 , x2 x4 x5  +1/2 x3 x4 x5 ,
         2              2              2              2          2
 x2 x5 x4  +1/2 x2 x4 x5  +1/2 x3 x5 x4  +1/4 x3 x4 x5 , x2 x5 x3
                2               2               2               2
  + 1/2 x2 x3 x5  + 1/2 x4 x5 x3  + 1/3 x3 x4 x5  + 1/3 x2 x5 x4
                   2               2
     + 1/6 x2 x4 x5  + 1/6 x3 x5 x4 ]
# The polynomials have been obtained by using the following
# operators (acting on their left)
ACE> op(2,gg);
[[], s3 + 1/3, (s3 +1/3)(s4 +1/2), (s3 + 1/3)(s2 + 1/2),
    (s3 +1/3)(s4 +1/2)(s2 +1/2)]

There are many equivalent ways of labelling the vertices of Γ_{λ}, what is fundamental is the choice of parameters on the edges. Here are some other possible labels, with tableaux, with permutations constituting a final interval in the permutohedron, with products of Vandermonde determinants, writing Δ(123) for (x_{1} − x_{2})(x_{1} − x_{3})(x_{2} − x_{3}).

3 2 5 1 4 4 2 5 1 3_{4 3 5 1 2  5 2 4 1 3} 5 3 4 1 2 53142 53412_{54312 53421} 54321 Δ(123)Δ(45)

Δ(124)Δ(35)

Δ(134)Δ(25)  Δ(125)Δ(34)

Δ(135)Δ(24)

Each time, it suffices to define the top element, the graph finishes the job. The representation on products of Vandermonde determinants is called Specht representation is in fact due to Young.

Theorem 3.3.1. Given a partition λ, then the Yang-Baxter polynomials θ_{u} (indexed by the vertices of (3.2.1)) constitute a basis of an irreducible representation of type λ of the symmetric group. The Yang-Baxter polynomials θ̃_{v} (indexed by the vertices of (3.2.3)) are adjoint to it, up to signs.

Proof. Let us give the proof for λ = [3, 2], to avoid having to introduce too many notations to name the objects.

The Yang-Baxter polynomials are

θ_{00033} = x^{00033}

∥
θ_{00303} = x^{00033}(\frac{1}{3}^{+}s_{3})
⧸  ⧹ ⧹ ⧹
θ_{03003} = x^{00033}(\frac{1}{3}^{+}s_{3})(\frac{1}{2}^{+}s_{2})  θ_{00330} = x^{00033}(\frac{1}{3}^{+}s_{3})(\frac{1}{2}^{+}s_{4})
⧹ ⧹ ⧹  ⧸
θ_{03030} = x^{00033}(\frac{1}{3}^{+}s_{3})
(\frac{1}{2}^{+}s_{2})(\frac{1}{2}^{+}s_{4})

The adjoint polynomials are

x^{00112}(\frac{1}{2}^{+}s_{4})

(\frac{1}{2}^{+}s_{2})(\frac{1}{3}^{+}s_{3})
∥
x^{00112}(\frac{1}{2}^{+}s_{4})(\frac{1}{2}^{+}s_{2})
⧸  ⧹ ⧹ ⧹
x^{00112}(\frac{1}{2}^{+}s_{4})  x^{00112}(\frac{1}{2}^{+}s_{2})
⧹ ⧹ ⧹  ⧸
x^{00112}

First, the bottom monomial θ̃_{00112} = x^{00112} is orthogonal to x^{00033}, x^{00303}, x^{03003}, x^{00330}, therefore to all the elements of the Yang-Baxter basis, except θ_{03030}. Moreover, one has

(θ_{030303} , x^{00112}) = (x^{03030} , x^{00112}) = 1 .

Owing to this starting point, one pushes the orthogonality properties to all other θ̃_{v} by induction on length, exactly as in the proof of Proposition 2.5.1. □

# one checks that the two bases are adjoint by printing
# all pairs of polynomials with a non-zero scalar product

ACE> Flag(5):      # Fix the order the symmetric group
yang1:=op(3,GrapheYB([3,2])):  yang2:=op(4,GrapheYB([2,2,1])):
ACE> for pol1 in yang1 do for pol2 in yang2 do
scal:=SpScalarPol(pol1,pol2);if scal<>0 then print(pol1,pol2) fi
od: lprint(`-----------------------------------`); od:
  3   3              2              2          2              2
x4  x5 , 1/2 x4 x5 x3  +1/3 x3 x4 x5  +x2 x5 x3  +1/2 x2 x3 x5
                   2               2               2
     + 1/6 x3 x5 x4  + 1/3 x2 x5 x4  + 1/6 x2 x4 x5
-----------------------------------
  3   3         3   3
x3  x5  + 1/3 x4  x5 ,
                2               2           2               2
    1/2 x3 x5 x4  + 1/4 x3 x4 x5  + x2 x5 x4  + 1/2 x2 x4 x5
-----------------------------------
     3   3         3   3         3   3              2           2
   x3  x4  + 1/2 x4  x5  + 1/2 x3  x5 , 1/2 x3 x4 x5  + x2 x4 x5
-----------------------------------
         3   3         3   3     3   3          2               2
   1/2 x3  x5  + 1/2 x4  x5  + x2  x5 , x3 x5 x4  + 1/2 x3 x4 x5
-----------------------------------
      3   3        3   3        3   3    3   3        3   3        2
1/2 x3  x4  +3/4 x4  x5  +1/4 x3  x5  +x2  x4  +1/2 x2  x5 , x3x4x5
-----------------------------------

Exercises

Ex. 3.1. Given n, find the basis of ℭ𝔬ℑ𝔫𝔳 adjoint to the basis of monomials {x^{u} : u ≤ [0, 1, 2…. , n^{−}1]}.

Ex. 3.2. Let n be a positive integer, ω be the maximum element of 𝔖(x_{1}, …, x_{n}). Compute the image of

T odd = ((n^{−}1)x_{1} + ⋯ + 0x_{n})^{\binom{n}{2}}

under ∂_{ω}. Solution. The only monomials in the expansion of T odd which give a non-zero contribution are (x^{ρ})^{σ}, ρ = [n^{−}1, …, 0], σ ∈ 𝔖_{n}. Since the image of x^{ρ} under ∂_{ω} is 1, the image of T odd is the same as the image of

∑_{(I,σ):σ∈𝔖_{n}, I=σρ}(n − 1)^{i_{1}} ⋯ 0^{i_{n}} \frac{\binom{n}{2} !}{i_{1} ! ⋯ i_{n}!}x^{I} .

On the other hand,

∑(−1)^{ℓ(σ)}(n^{−}1)^{i_{1}} ⋯ 0^{i_{n}} = Δ(n^{−}1, …, 0) = (n^{−}1)! ⋯ 1! .

Therefore the image of T odd is \binom{n}{2} !.

Ex. 3.3. Knowing that, for n = 5, the graded characteristic of the space ℭ𝔬ℑ𝔫𝔳, in degree 4, is :

ACE> coeff(CharacterCoInv(5),q,4);
            s[3, 2] + s[4, 1] + s[2, 2, 1] + s[3, 1, 1]

show that the subspace generated by the permuted of the monomial x^{00022} is the sum of two irreducible representations of 𝔖_{5} of respective shapes [2, 3] and [1, 4].

As a check, the dimension of the space is indeed 5 + 4:

ACE> rank(WeightSpace([0,0,0,2,2]));
                             9
ACE> rank(WeightSpace([0,0,0,1,1]));
                             9
ACE> rank(WeightSpace([0,0,0,3,3]));
                             5

Ex. 3.4. To the composition [3, 2], we have associated a graph Γ_{32} with top element x^{00033} :

ACE> op(3,GrapheYB([3,2],vecteur));
[[0,0,0,3,3],[0,0,3,0,3],[0,0,3,3,0],[0,3,0,0,3],[0,3,0,3,0]]

Keeping the same edges, but taking the top element x^{22200}, we get the monomials of exponents

[2, 2, 2, 0, 0], [2, 2, 0, 2, 0], [2, 2, 0, 0, 2], [2, 0, 2, 2, 0], [2, 0, 2, 0, 2]

as new labels of the vertices. Show that these monomials are still a basis of the same space as when starting with x^{00033}, and find the matrix of change of basis. Solution. Thanks to (3.1.1), one has

x^{22200} = S_{222}(x_{1} + x_{2} + x_{3}) ≡ S_{33}(x_{4} + x_{5}) = x^{00033}

.

This congruence is preserved by the action of the symmetric group, and therefore the two sets of monomials coincide modulo 𝔖𝔶𝔪_{+} and are both bases of the same space.

We could have taken the graph with top element x^{00222}, but in that case the edges are not labelled by the same transpositions.

Ex. 3.5. Define the Jucys-Murphy elements ξ_{j} to be

ξ_{j} := τ_{1j} + τ_{2j} + ⋯ + τ_{j−1,j}

(sum over all transpositions τ_{ij}, i < j, putting ξ_{1} = 0.

Write the commutation rules between the simple transpositions and the Jucys-Murphy elements.

Show that x^{00033} (evaluated in ℭ𝔬ℑ𝔫𝔳) is an eigenvector for ξ_{1}, …, ξ_{5}.

ACE> SgaJucis(4,5);
               A[4,2,3,1,5]+A[1,4,3,2,5]+A[1,2,4,3,5]

Using the above commutation rules, show that the other Yang-Baxter polynomials labelling the vertices of Γ_{32} are also eigenvectors of ξ_{1}, …, ξ_{5}, with the following eigenvalues :

JucysOnPol:=proc(n,pol) local i,polX;
 Flag(n);
 polX:=ToX(pol);
# one has to reduce modulo the ideal, this is done by evaluating
# in the Schubert basis
 [seq(simplify(ToX(SgaOnPol(SgaJucis(i),pol))/polX), i=1..n)]
end:
ACE> for pol in op(3,GrapheYB([3,2])) do
                      print( JucysOnPol(5,pol),pol)   od:
                                 3   3
                 [0,1,2, -1,0], x4  x5

                       3   3     3   3
[0,1, -1, 2, 0], 1/3 x4  x5  + x3  x5
                3   3         3   3     3   3
[0,1, -1,0,2], 1/2 x4  x5  + 1/2 x3  x5  + x3  x4
                 3   3     3   3         3   3
[0,-1,1,2,0], 1/2 x4  x5  + x2  x5  + 1/2 x3  x5
[0, -1, 1, 0, 2],
3  3        3  3    3  3        3  3        3  3
1/2 x2 x5  +3/4 x4 x5  +x2 x4  +1/4 x3 x5  +1/2 x3 x4

CHAPTER 4 𝔓𝔬𝔩(𝔸) as a free 𝔖𝔶𝔪(𝔸)-module

’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o ’ ooo oo o

4.1. Quadratic Form on 𝔓𝔬𝔩

This time, we do not evaluate polynomials modulo the ideal 𝔖𝔶𝔪_{+}, we do not kill any symmetric function. We already saw in the second chapter that taking the “scalars” to be the symmetric functions in 𝔸 was a convenient way of computing with divided differences.

Our aim is to be able to manipulate polynomials in several variables as easily as symmetric polynomials. Many properties of symmetric functions come from the existence of a Cauchy kernel giving rise to a scalar product on 𝔖𝔶𝔪(𝔸), and to the distinguished basis of Schur functions.

This approach can be extended to the ring ℤ[𝔸] of polynomials in n indeterminates : 𝔸 = {a_{1}, a_{2}, …, a_{n}}. We shall consider ℤ[𝔸] as a module over 𝔖𝔶𝔪(𝔸), and to have more flexibility, we introduce a second alphabet 𝔹 = {b_{1}, b_{2}, …, b_{n}}, and denote by 𝔓𝔬𝔩(𝔸) the ring

𝔓𝔬𝔩(𝔸) = ℚ[𝔸, 𝔹]/(𝔖𝔶𝔪(𝔸) = 𝔖𝔶𝔪(𝔹)) ,

where the ideal (𝔖𝔶𝔪(𝔸) = 𝔖𝔶𝔪(𝔹)) is the ideal generated by all f(𝔸)−f(𝔹), f symmetrical. We shall consider 𝔓𝔬𝔩(𝔸) as a module over 𝔖𝔶𝔪(𝔸), which is now defined to be the ring of symmetric functions in 𝔸 with coefficients in 𝔹.

We have already used that 𝔓𝔬𝔩(𝔸) is a free 𝔖𝔶𝔪(𝔸)-module, with basis the monomials a^{I}, I ≤ ρ := [n^{−}1, …, 1, 0]. We shall now give a more precise description of this free module.

We still use the maximal divided difference of 𝔖(𝔸) to define a quadratic form :

(4.1.1)  𝔓𝔬𝔩(𝔸) ∋ f, g ⇒ (f , g) = (fg , 1) := fg ∂_{ω} ∈ 𝔖𝔶𝔪(𝔸)

# scalar product compatible with product of polynomials
ACE> SpScalarPol(x1^6*x3,x2^3, 3),
                          SpScalarPol(x1^6*x3*x2^3,1, 3);
                        s[4, 2, 1], s[4, 2, 1]

60 4. 𝔓𝔬𝔩(𝔸) AS A FREE 𝔖𝔶𝔪(𝔸)-MODULE

ACE> ToY(NcaOnPol(A[3,2,1], x1^6*x3*x2^3));
              Y[1, 2, 4, 0, 0, 0, 0] # increasing partitions

Divided differences are compatible with this quadratic form :

Lemma 4.1.1. The divided differences ∂_{i}, i = 1, …, n − 1, are selfadjoint with respect to ( , ). Therefore, for σ ∈ 𝔖(𝔸), ∂_{σ} is adjoint to ∂_{σ^{−1}}.

Moreover σ is adjoint to (−1)^{ℓ(σ)}σ^{−1}.

Proof. Given any i < n, factorize ω = s_{i} σ. Then (f ∂_{i}, g) = (f∂_{i} g ∂_{i})∂_{σ}. Because f ∂_{i} is a scalar for ∂_{i}, the preceding expression is equal to

((f∂_{i}) (g∂_{i})) ∂_{σ}

and the symmetry between f and g implies that it is also equal to (f , g∂_{i}). By product, one gets the assertion for every ∂_{σ}.

Similarly

(fσ , g) = f^{σ} g ∂_{ω} = f g^{σ^{−1}} σ∂_{ω} = (−1)^{ℓ(σ)}f g^{σ^{−1}} ∂_{ω} = (−1)^{ℓ(σ)}(f , gσ^{−1}) .

□

ACE> SpScalarPol(NcaOnPol(A[3,1,2], x1^6*x3^2), x2^4, 3);
       s[4, 3] + s[4, 2, 1] + s[5, 2] + s[5, 1, 1] + s[6, 1]
ACE> SpScalarPol(x1^6*x3^2, NcaOnPol(A[2,3,1],x2^4), 3);
      s[4, 3] + s[4, 2, 1] + s[5, 2] + s[5, 1, 1] + s[6, 1]

4.2. Kernel

Let

(4.2.1)  K_{n}(𝔸, 𝔹) := ∏_{1≤i<j≤n}(b_{i} − a_{j}) .

This function has fundamental and evident vanishing properties:

Lemma 4.2.1. For any permutation σ ∈ 𝔖_{n}, the specialization K_{n}(𝔸^{σ}, 𝔹)|_{𝔸=𝔹} vanishes, except the case K_{n}(𝔹, 𝔹) = Δ(𝔹).

Proof. To avoid vanishing, the letter a_{n} can only be specialized to b_{n}, because K_{n}(𝔸^{σ}, 𝔹) has the factor (a_{n}^{−}b_{1}) ⋯ (a_{n}^{−}b_{n−1}). Now the situation to examine is the same, but with a_{1}, …, a_{n−1}, and b_{1}, …, b_{n−1}. This proves by induction on n that the only non-zero specialization is a_{1} = b_{1}, …, a_{n} = b_{n}. □

The following proposition shows that K_{n}(𝔸, 𝔹) is a reproducing kernel, i.e. that it allows to obtain f(𝔹) from f(𝔸) by scalar product.

Proposition 4.2.2. For any f ∈ 𝔓𝔬𝔩(𝔸), one has

(4.2.2)  (f(𝔸) , K_{n}(𝔸, 𝔹)) ≡ f(𝔹)

(we have written ≡ instead of an equality to point out that we are identifying symmetric functions in 𝔸 with those of 𝔹). Proof. Any polynomial in 𝔸 can be written as a linear combination of a^{I}, I ≤ ρ = [n − 1, …, 1, 0], with coefficients in 𝔖𝔶𝔪(𝔸). However, a^{I} K_{n}(𝔸, 𝔹) is a linear combination of monomials a^{I+J}, I ≤ ρ, J ≤ [0, 1, … n^{−}1], that is, of monomials having an exponent I+J ≤ (n−1)^{n}. The image of such a monomial under ∂_{ω} is 0, except if all its exponents are different, and this is precisely the case where I +J is a permutation of ρ. In that case a^{I+J} ∂_{ω} = ±S_{0} = ±1.

Therefore, the image of each monomial a^{I+J} is independent of 𝔸, and one can specialize 𝔸 to 𝔹 in the expression

f(𝔸)K_{n}(𝔸, 𝔹) ∂_{ω} = ∑_{σ∈𝔖(𝔸)}(−1)^{ℓ(σ)}f(𝔸^{σ})K_{n}(𝔸^{σ}, 𝔹)\frac{1}{Δ(𝔸)}

However K_{n}(𝔹^{σ}, 𝔹) is 0 if σ is not the identity permutation, and the summation reduces to a single term

f(𝔹)K_{n}(𝔹, 𝔹)/Δ(𝔹) = f(𝔹) .
□

The next natural step, when one has a quadratic form, is to look for an orthonormal basis. We shall find one which is “almost” orthonormal: the matrix of scalar products is a ‘signed’ permutation matrix.

This basis is called the basis of Schubert polynomials. Schubert polynomials indexed by permutations in 𝔖_{n}, defined as follows, starting from a top element 𝕏_{ω}(𝔸, 𝔹) :

(4.2.3)  \{ \begin{matrix}𝕏_{ω}(𝔸, 𝔹) & := ∏_{1≤i,j≤n, i+j≤n} (a_{i} − b_{j}) \\ 𝕏_{σ}(𝔸, 𝔹) & = 𝕏_{ω}(𝔸, 𝔹) ∂_{ωσ} \end{matrix}

Notice that K_{n}(𝔸, 𝔹) = (−1)^{\binom{n}{2}} 𝕏_{ω}(𝔸^{ω}, 𝔹).

In fact, we have decomposed the resultant R(𝔸, 𝔹) into the three factors 𝕏_{ω}(𝔸, 𝔹), ±K_{n}(𝔸, 𝔹), and the diagonal ∏_{i}(a_{i}−b_{i}). Graphically, a box in position [i, j] standing for a factor (a_{i}^{−}b_{j}), this decomposition is

R(\{a_{1}, a_{2}, a_{3}\}, \{b_{1}, b_{2}, b_{3}, b_{4}\}) = \begin{matrix}♡ & ■ & ■ & ■ \\ □ & ♡ & ■ & ■ \\ □ & □ & ♡ & ■ \\ □ & □ & □ & ♡ \end{matrix} ,

the three factors being represented by □, ■ and ♡ respectively.

The preceding definition implies the recursions

(4.2.4)  𝕏_{σ}(𝔸, 𝔹)∂_{i} = 𝕏_{σs_{i}}(𝔸, 𝔹) if ℓ(σs_{i}) < ℓ(σ) .

(because ∂_{i}^{2} = 0, then 𝕏_{σ}(𝔸, 𝔹)∂_{i} = 0 if ℓ(σs_{i}) > ℓ(σ)).

For 𝔖_{3}, the Schubert polynomials are

(a_{1}−b_{1})(a_{1}−b_{2})(a_{2}−b_{1})
∂_{1} ⧸⧸  ⧹ ∂_{2}
(a_{1}−b_{1})(a_{2}−b_{1})  (a_{1}−b_{1})(a_{1}−b_{2})
∂_{2} |  ∥ ∂_{1}
(a_{1}−b_{1})  a_{1}+a_{2}−b_{1}−b_{2}
∂_{1} ⧹⧹  ⧸ ∂_{2}

1

and can be obtained with the ACE-function TableX(n), the variables being now x_{i}, y_{j} :

ACE> TableXX(3);
table([
    [3, 2, 1] = (-x2 + y1) (x1 - y2) (-x1 + y1)
    [1, 2, 3] = 1
    [1, 3, 2] = x2 - y2 + x1 - y1
    [3, 1, 2] = -(x1 - y2) (-x1 + y1)
    [2, 1, 3] = x1 - y1
    [2, 3, 1] = (-x2 + y1) (-x1 + y1)
    ])

One can also index Schubert polynomials by codes of permutations, instead of permutations. We write 𝕐_{J} = 𝕏_{σ} if J = [j_{1}, …, j_{n}] = code(σ). The recursion on Schubert polynomials is now written, starting from 𝕐_{ρ}(𝔸, 𝔹) = 𝕏_{ω}(𝔸, 𝔹) = ∏_{1≤i,j≤n, i+j≤n}(a_{i} − b_{j}),

(4.2.5)  𝕐_{J}(𝔸, 𝔹) ∂_{i} = 𝕐_{...,j_{i+1}, j_{i}−1,...} if j_{i} > j_{i+1} .

ACE> map(factor, TableYY(4));# computed with a different algorithm
table([
 [1,1,1,0] = -(-x3 + y1) (-x2 + y1) (-x1 + y1)
 [1,0,1,0] = (-x1 + y1) (y1 + y3 - x3 - x1 - x2 + y2)
 [2,2,1,0] = -(-x3 + y1) (-x2 + y2) (-x2 + y1) (-x1 + y2) (-x1 + y1)
 [1,2,1,0] = (-x3 + y1) (-x2 + y1) (-x1 + y1) (-x2 + y3 - x1 + y2)
                                                 2
 [0,1,1,0] = x3 x2 -x3 y2 +x3 x1 -x3 y1 -x2 y2 +y2  -y2 x1 +y2 y1+x2 x1

 - x2 y1 - y1 x1 + y1
[2,0,0,0] = (-x1 + y2) (-x1 + y1)
              2                                                     2
[0,2,0,0] = x2  -x2 y2 +x2 x1 -x2 y1 -y3 x2 +y3 y2 -y3 x1 +y3 y1 +x1
    - y1 x1 - y2 x1 + y2 y1
[3,0,1,0] = (-x1 + y2) (-x1 + y1) (y1 - x3 + y2 - x2) (-x1 + y3)
[2,0,1,0] = -(-x1 + y2) (-x1 + y1) (y1 - x3 + y2 - x2)
[0,1,0,0] = x2 - y2 + x1 - y1
[1,0,0,0] = x1 - y1
[0,0,1,0] = x3 - y3 + x2 - y2 + x1 - y1
[3,2,1,0] = (-x3 +y1) (-x2 +y2) (-x2 +y1) (-x1 +y3)(-x1+y2)(-x1+y1)
[3,1,0,0] = (-x2 + y1) (-x1 + y3) (-x1 + y2) (-x1 + y1)
[2,2,0,0] = (-x2 + y2) (-x2 + y1) (-x1 + y2) (-x1 + y1)
[3,0,0,0] = -(-x1 + y3) (-x1 + y2) (-x1 + y1)
[3,2,0,0] = -(-x2 + y2) (-x2 + y1) (-x1 + y3) (-x1 + y2) (-x1 + y1)
[2,1,1,0] = (-x3 + y1) (-x2 + y1) (-x1 + y2) (-x1 + y1)
[0,2,1,0] = -x3 x2 y1 -y2 y3 y1 +y3 x2 y1 -x3 x1 y2 -y3x2x1 +y3y1x1
-2 x2 y2 x1 +2 x2 y2 y1 -2 x2 y1 x1 +2 y2 y1 x1 +x3y3y2 +y3y2x1
                2       2    2
+y3 x2 y2 +x3 x1  -y2 x1  +y2  x1 -x3 x2 y2 +x3x2x1 -x3y3x2+x3y3y1
      2       2       2              2       2          2
+x3 x2  -y2 x2  +x2 y2  -x3 y3 x1 -y2  y1 -y2  y3 -y2 y1  -x3x1y1
                2    2       2          2       2       2    2
+x3 y2 y1 -y3 y1  +x2  x1 -x2  y1 +x2 y1  +x2 x1  -y1 x1  +y1  x1
[1,2,0,0] = -(-x2 + y1) (-x1 + y1) (-x2 + y3 - x1 + y2)
[2,1,0,0] = -(-x2 + y1) (-x1 + y2) (-x1 + y1)
[1,1,0,0] = (-x2 + y1) (-x1 + y1)
[3,1,1,0] = -(-x3 + y1) (-x2 + y1) (-x1 + y3) (-x1 + y2) (-x1 +y1)
[0,0,0,0] = 1                ])

Proposition (4.2.2) can be now be generalized, divided differences themselves can be evaluated with scalar products.

Theorem 4.2.3. For any f ∈ 𝔓𝔬𝔩(𝔸), any permutation σ ∈ 𝔖(n), one has

(4.2.6)  (f(𝔸) , (−1)^{ℓ(σω)}𝕏_{σω}(𝔸^{ω}, 𝔹)) ≡ f ∂_{σ^{−1}} (𝔹) .

Proof. One has

𝕏_{σω}(𝔸^{ω}, 𝔹) = 𝕏_{ω}(𝔸, 𝔹) ∂_{ωσω} ω

= 𝕏_{ω}(𝔸, 𝔹)ω (ω∂_{ωσω} ω) = 𝕏_{ω}(𝔸, 𝔹) ω (−1)^{ℓ(σ)}∂_{σ} ,

and one can shift the divided difference ∂_{σ} to the left of ( , ) thanks to Lemma (4.1.1). Now the formula results from proposition 4.2.2 for the function f ∂_{σ^{−1}}. □

The theorem shows a symmetry property of Schubert polynomials which is not evident from their definition with operators acting on 𝔸 only. Introducing ℂ, a third alphabet of cardinality n, take f(𝔸) = 𝕏_{ω}(𝔸, ℂ). Then (4.2.6) implies

(𝕏_{ω}(𝔸, ℂ) , (−1)^{ℓ(σω)}𝕏_{σω}(𝔸, 𝔹)ω) = 𝕏_{ωσ^{−1}}(𝔹, ℂ) .

On the other hand, putting ω on the left,

((^{−}1)^{ℓ(ω)}𝕏_{ω}(𝔸^{ω}, ℂ) , (−1)^{ℓ(σω)}𝕏_{σω}(𝔸, 𝔹)ω) = 𝕏_{σω}(ℂ, 𝔹) ,

because (^{−}1)^{ℓ(ω)}𝕏_{ω}(𝔸^{ω}, ℂ) is a reproducing kernel. Therefore, one has the symmetry :

(4.2.7)  𝕏_{σ}(𝔸, 𝔹) = (^{−}1)^{ℓ(σ)}𝕏_{σ^{−1}}(𝔹, 𝔸) .

Corollary 4.2.4. The quadratic form ( , ) is non-degenerate. The space 𝔓𝔬𝔩(𝔸) is a free module over 𝔖𝔶𝔪, with the two adjoint bases {𝕏_{σ}(𝔸, 𝔹)} and {(^{−}1)^{ℓ(σω)}𝕏_{σω}(𝔸^{ω}, 𝔹) : σ ∈ 𝔖(𝔸)}.

More precisely

(𝕏_{σ}(𝔸, 𝔹) , (^{−}1)^{ℓ(νω)}𝕏_{νω}(𝔸^{ω}, 𝔹)) = δ_{σ,ν} .

Any element of 𝔓𝔬𝔩(𝔸) expands into the basis of Schubert polynomials 𝕏_{σ}, σ ∈ 𝔖(𝔸), as follows :

\begin{aligned}f(𝔸) & ≡ ∑_{σ}(f , (^{−}1)^{ℓ(σω)}𝕏_{σω}(𝔸^{ω}, 𝔹))𝕏_{σ}(𝔸, 𝔹) \\ & ≡ ∑_{σ} f∂_{σ^{−1}}(𝔹) 𝕏_{σ}(𝔸, 𝔹) \end{aligned} ; (4.2.8)

One can view Schubert polynomials as a basis of 𝔓𝔬𝔩(𝔸) depending on parameters b_{1}, …, b_{n}, and let the parameters vary. Indeed, let ℂ = {c_{1}, …, c_{n}}. Then the following theorem shows that the matrix of change of bases has Schubert polynomials as entries :

Theorem 4.2.5. Let 𝔸, 𝔹, ℂ be three alphabets of cardinality ≥ n, and let ζ ∈ 𝔖(n). Then

(4.2.9)  𝕏_{ζ}(𝔸, ℂ) = ∑_{η,σ} 𝕏_{η}(𝔹, ℂ) 𝕏_{σ}(𝔸, 𝔹) ,

sum over all reduced factorizations ζ = ησ (i.e. factorizations such that ℓ(σ) + ℓ(η) = ℓ(ζ)).

Proof. One applies corollary(4.2.4) to the function f(𝔸) = 𝕏_{ζ}(𝔸, ℂ). Since f(𝔸) belongs to the span of monomials in 𝔸 of degree ≤ ρ, ≡ is in fact an equality. Moreover, to require non nullity of 𝕏_{ζ}∂_{η^{−1}} is the same as to require that the product (ζη^{−1})(η) be reduced. □

For example, for ζ = [2, 4, 1, 3], the expansion is

𝕏_{2413}(𝔸, ℂ) = \begin{matrix}𝕏_{2413}(𝔹, ℂ)𝕏_{1234}(𝔸, 𝔹) \\ −𝕏_{2143}(𝔹, ℂ)𝕏_{1324}(𝔸, 𝔹) \\ +𝕏_{1243}(𝔹, ℂ)𝕏_{2314}(𝔸, 𝔹) + 𝕏_{2134}(𝔹, ℂ)𝕏_{1423}(𝔸, 𝔹) \\ −𝕏_{1234}(𝔹, ℂ)𝕏_{2413}(𝔸, 𝔹) \end{matrix} .

The special case ζ = ω is worth of interest. It states that ∏_{i+j≤n}(a_{i}− c_{j}) is the sum of all products 𝕏_{ωσ^{−1}}(𝔹, ℂ) 𝕏_{σ}(𝔸, 𝔹), where 𝔹 has been chosen arbitrarily.

The Cauchy formula for symmetric functions gives the decomposition of R(𝔸, ℂ) in to a sum of product of Schur functions of complementary shapes. Thus, the case ζ = ω, 𝔹 = 0 of (4.2.9) is the non-symmetric version of it (Cauchy formula for Schubert polynomials [10]) :

𝕏_{ω}(𝔸, ℂ) = ∏_{i+j≤n}(a_{i} − c_{j}) = ∑_{σ} 𝕏_{ω σ^{−1}}(0, ℂ) 𝕏_{σ}(𝔸, 0)
(4.2.10)  = ∑_{σ}(^{−}1)^{ℓ(σ)}𝕏_{σ}(ℂ, 0) 𝕏_{σω}(𝔸, 0) .

In fact, in the case where the code of ζ is [γ^{α}, 0^{n−α}], and 𝔹 = 0, then one recovers the usual Cauchy formula for two alphabets of respective cardinalities α, γ :

(4.2.11)  𝕏_{ζ}(𝔸, ℂ) = ∏_{i≤α} ∏_{j≤γ}(a_{i} − c_{j}) = ∑_{σ} 𝕏_{η}(0, ℂ) 𝕏_{σ}(𝔸, 0) ,

sum over all reduced factorizations ζ = η σ. Taking the codes of η^{−1} and σ, one recognizes them to be (increasing) conjugate partitions.

# one expands the maximal Schubert polynomial (in x,b)
 in the basis of Schubert polynomials (in x,y)
#
ACE> ToXX( (x1-b2)*(x1-b1)*(x2-b1)):
# one puts the result in a table indexed by XX[],
# and one substitutes in the entries b1=x1,b2=x2
# to be able to use ToXX
ACE> subs(b1=x1,b2=x2,%)
ACE> map(ToXX,%, collect);
table(sparse, [
    [3, 2, 1] = XX[1]

    [2, 3, 1] = -XX[1, 3, 2]
    [3, 1, 2] = -XX[2, 1]
    [1, 3, 2] = XX[2, 3, 1]
    [2, 1]    = XX[3, 1, 2]
    [1]       = -XX[3, 2, 1]
    ])

Many properties of symmetric functions can be obtained using Schubert polynomials. In fact, the Schur function in a_{1}, …, a_{n}, indexed by the increasing partition J ∈ ℕ^{n}, coincides with the specialization 𝕐_{J}(𝔸, 0). This is clear from its definition as

𝕐_{J}(𝔸, 0) = a_{1}^{j_{n}+n−1} ⋯ a_{n}^{j_{1}+0} ∂_{n...1} = ∑_{σ∈𝔖_{n}}(a_{1}^{j_{n}+n−1} ⋯ a_{n}^{j_{1}+0})^{σ}/Δ(𝔸_{n}) .

4.3. Schubert by Isobaric Divided Differences

In this section and the next one, we shall specialize 𝔹 to 0 and write X_{σ}, Y_{J} for 𝕏_{σ}(𝔸, 0), 𝕐_{J}(𝔸, 0).

The divided differences π_{i} and π̂_{i} can be lifted to the free algebra, in a way compatible to the projection on 𝔓𝔩𝔞𝔠. Finding a way to define Schubert polynomials with these operators, instead of ∂_{i} almost certainly ensures to find easily a non-commutative version of Schubert polynomials.

In fact such a construction results easily from the commutation relations between π_{i} and x_{j}, j ≠ i, i^{+}1. Magyar [26] gave a geometrical construction which generalizes Bott-Samelson varieties and implies the following theorem^{1}.

In this section we specialize the second alphabet to 0, and index Schubert polynomials by codes.

Theorem 4.3.1. Given J ∈ ℕ^{n}, let k be minimum such that j_{k} = 0 (if it does not exist, replace J by J0). Let I = [j_{1} − 1, …, j_{k−1} − 1, j_{k+1}, …, j_{n}].

Then

(4.3.1)  Y_{J} = Y_{I} π_{n−1} ⋯ π_{k} x_{k−1} ⋯ x_{1}

Proof. x_{k−1} ⋯ x_{1} commutes with π_{n−1} ⋯ π_{k}, and therefore, because π_{n−1} ⋯ π_{k} = x_{n−1} ⋯ x_{k} ∂_{n−1} ⋯ ∂_{k}, one can factor on the right the divided differences :

Y_{I} π_{n−1} ⋯ π_{k} x_{k−1} ⋯ x_{1} = Y_{I}(x_{n−1} ⋯ x_{k})(x_{k−1} ⋯ x_{1})∂_{n−1} ⋯ ∂_{k}

1He does not use the same products of π_{i}, reducing them to take into account partial symmetries.

4.4. ACTION OF 𝔖_{n} ON SCHUBERT POLYNOMIALS 67

= Y_{I+1^{n−1}} ∂_{n−1} ⋯ ∂_{k} = Y_{J}

□

For example, the Schubert polynomial Y_{30302} is obtained by the following sequence of operations (image under products of π_{i} followed by multiplication by a factor x_{1} ⋯ x_{k}).

Y_{0}  x_{1}x_{2}
Y_{11} π_{2}π_{1}
Y_{011}  x_{1}x_{2}x_{3}
Y_{122} π_{3} x_{1}x_{2}
Y_{2302} π_{4}π_{3}π_{2} x_{1}
Y_{30302}

# The program can print the intermediate steps
ACE> RecY([3,0,3,0,2],see):
 Y[2,3,0,2]  Pi [4, 3, 2,  x1]
 Y[1,2,2]   Pi [3, x1*x2]
 Y[0,1,1]*x1*x2*x3
 Y[1,1]   Pi [2, 1]
 Y[0,0]*x1*x2
ACE> ToY(x2X(%));     # faster algorithm with x2X
                    Y[3, 0, 3, 0, 2, 0, 0]

4.4. Action of 𝔖_{n} on Schubert Polynomials

The divided difference ∂_{i} is equal to (1−s_{i})(x_{i}−x_{i+1})^{−1}. Conversely

(4.4.1)  s_{i} = ∂_{i} (x_{i+1} − x_{i}) + 1 .

Since the action of divided differences is straightforward, the action simple transpositions is a consequence of the formula (Monk formula) describing the product of a Schubert polynomial by a single variable :

(4.4.2)  X_{σ} x_{k} = ∑_{j>k} X_{σ τ_{kj}} − ∑_{i<k} X_{σ τ_{ik}} ,

sum over transpositions τ_{kj}, τ_{ik} such that ℓ(στ_{kj}) = ℓ(σ) + 1 = ℓ(στ_{ik}).

As a consequence, one has the following description of the action of a simple transposition on the Schubert basis.

Proposition 4.4.1. Let σ ∈ 𝔖_{n}, and k < n. If σ_{k} < σ_{k+1}, then X_{σ} is invariant under s_{i}. Otherwise, let η = σ s_{k}. Then

(4.4.3) X_{σ} s_{k} = −X_{σ} + ∑_{j>k+1} X_{η τ_{k+1,j}} − ∑_{i<k} X_{η τ_{i,k+1}}

− ∑_{j>k+1} X_{η τ_{kj}} + ∑_{i<k} X_{η τ_{ik}} ,

sum restricted to permutations of the same length as σ.

#simple transposition s_3 ; eta= [5,1,3,6,8,2,4,7]
ACE> SgaOnX(A[1,2,4,3],X[5,1,6,3,8,2,4,7]);
     - X[5,1,6,3,8,2,4,7] - X[6,1,3,5,8,2,4,7]
     + X[5,1,3,8,6,2,4,7] + X[5,1,3,7,8,2,4,6]
     + X[5,3,1,6,8,2,4,7] - X[5,1,4,6,8,2,3,7]

The properties of the representation of the symmetric group on the Schubert polynomials of a given degree have not yet been studied.

I shall just mention that it is easy to describe the subspace of ℭ𝔬ℑ𝔫𝔳 invariant under some □_{ω(J)}, that we needed to check that some representation was without multiplicity.

Lemma 4.4.2. • Let k < n. Then the subspace of the elements of ℭ𝔬ℑ𝔫𝔳 invariant under s_{k} has basis the Schubert polynomials X_{σ} such that σ_{k} < σ_{k+1}.

• Let J be a composition of n. The subspace of elements invariant under 𝔖_{J} has basis the Schubert polynomials X_{σ} such that σ be of minimal length in its coset σ 𝔖_{J}.

Proof. Let f = ∑ c_{σ}X_{σ}. Requiring that f be invariant under s_{k} is the same as requiring that f ∂_{k} = 0. However f ∂_{k} = ∑_{σ: ℓ(σs_{k})<ℓ(σ)} c_{σ}X_{σ_{k}}, and this sum can be null only if it is void. □

The second statement is a direct consequence of the first.

For example, for n = 5, we needed the subspace of polynomials of degree 6 invariant under 𝔖_{32}. We have to find the codes v such that v_{1} ≤ v_{2} ≤ v_{3}, v_{4} ≤ v_{5} = 0. There is only [2, 2, 2, 0, 0], as is confirmed by the computer.

# degree 6 is given by the 6+1-th element of the list.
ACE> map(Perm2Code,op(7,ListPerm(5,level)));
[  [4,0,2,0,0],[3,3,0,0,0],[0,3,2,1,0],[4,0,1,1,0],
   [3,0,2,1,0],[4,2,0,0,0],[2,2,2,0,0],[2,3,0,1,0],
   [3,2,0,1,0],[1,3,2,0,0],[4,1,0,1,0],[3,1,2,0,0],
   [4,1,1,0,0],[1,2,2,1,0],[1,3,1,1,0],[3,1,1,1,0],
   [2,3,1,0,0],[2,2,1,1,0],[2,1,2,1,0],[3,2,1,0,0]]

Corollary 4.4.3. Let J be a composition of n. Then the subspace of ℭ𝔬ℑ𝔫𝔳 of elements fixed by □_{ω_{J}} /|𝔖_{J}| is generated by the Schubert X_{σ} such that σ be of minimal length in its coset σ 𝔖_{J}. In particular, the subspace in degree |μ(J)| is 1-dimensional, and generated by Y_{μ(J)}, where μ(J) has been defined in (3.2.4).

Proof. Let f = ∑ c_{σ}X_{σ} be fixed by □_{ω_{J}} /|𝔖_{J}|. Then f is annihilated by all ∂_{i} with s_{i} ∈ 𝔖_{J}|, and all the Schubert polynomials in the expansion of f have the same property. This means that they are all invariant under 𝔖_{J}. □

From the enumeration of permutations of minimal length in their coset, one could deduce recursively the multiplicities^{2} of irreducible representations in ℭ𝔬ℑ𝔫𝔳.

For example, for 𝔖_{5}, the subspace of degree 5 of ℭ𝔬ℑ𝔫𝔳 is isomorphic to 𝕍_{221} ⊕ 2𝕍_{311} ⊕ 𝕍_{32}. Since 𝕍_{221} □_{21435}, 𝕍_{311} □_{21435}, 𝕍_{32} □_{21435}, are of respective dimensions 1, 1, 2, because S^{221} = S_{122} + S_{113} + 2S_{23} + ⋯, then one must have 1+2×1+1×2 = 5 Schubert polynomials invariant under □_{21435}/4. Indeed,

ACE> select(IsInvariant,op(6,ListPerm(5,level)),[2,2,1]);
[[1,5,3,4,2],[3,5,1,2,4],[3,4,1,5,2],[2,5,1,4,3],[2,4,3,5,1]]

4.5. Newton Interpolation in Several Variables

We have seen in (4.2.8) that, for 𝔸, 𝔹 of cardinality n, and any polynomial f of n variables, one has

f(𝔸) ≡ ∑_{σ∈𝔖_{n}} f∂_{σ^{−1}}(𝔹) 𝕏_{σ}(𝔸, 𝔹) ,

modulo 𝔖𝔶𝔪(𝔸) = 𝔖𝔶𝔪(𝔹).

Letting n tends towards infinity, one gets rid of the ideal, and one obtains the generalization of Newton’s formula to polynomials of several variables :

(4.5.1)  f(𝔸) = ∑_{σ∈𝔖_{∞}} f∂_{σ^{−1}}(𝔹) 𝕏_{σ}(𝔸, 𝔹) .

Erasing f, this should be interpreted as the decomposition of the identity in terms of divided differences, rather than an interpolation formula.

2But it is simpler to obtain them from the cocharge of tableaux, or by specializing a complete function in 1, q, q^{2}, …

More generally, for any permutation ζ, changing 𝔸 to 𝔸^{ζ}, and specializing 𝔹 to 𝔸, in (4.5.1), one obtains

(4.5.2)  ζ = ∑_{σ} ∂_{σ^{−1}} 𝕏_{σ}(𝔸^{ζ}, 𝔸) .

Conversely, given n and a sum D = ∑_{ζ∈𝔖_{n}} ζ c_{ζ}, the coefficients c_{σ} being rational functions of 𝔸, then it is easy to determine these coefficients by letting D act on K_{n}(𝔸, 𝔹). Indeed the vanishing properties of the kernel (4.2.1) imply that

(4.5.3)  (^{−}1)^{ℓ(ζ)}K_{n}(𝔸, 𝔹) D|_{𝔹=𝔸^{σ}} = c_{ζ} Δ(𝔸) .

This applies to divided differences :

(4.5.4)  (^{−}1)^{ℓ(σ)}K_{n}(𝔸, 𝔹) ∂_{σ}|_{𝔹=𝔸^{σ}} = c_{ζ} Δ(𝔸) .

However, Eq. 4.2.9 implies that the inverse of the matrix with entries 𝕏_{σ}(𝔸^{ζ}, 𝔸) has the same entries, up to sign and multiplication by Δ(𝔸).

This gives another expression of the expansion of divided differences in the basis of permutations :

Proposition 4.5.1. Let σ ∈ 𝔖_{n}. Let ∂_{σ} = ∑ ζ c_{ζ}^{σ} be the expression of ∂_{σ} in terms of permutations. Then (4.5.5)

(^{−}1)^{ℓ(ζ)} c_{ζ}^{σ} = (^{−}1)^{ℓ(ωσ)} 𝕏_{σ^{−1}ω}(𝔸^{ωζ}, 𝔸)\frac{1}{Δ(𝔸)} = 𝕏_{ωσ}(𝔸, 𝔸^{ωζ})\frac{1}{Δ(𝔸)} .

Proof. Let us replace, in formula (4.2.6):

(f(𝔸) , (^{−}1)^{ℓ(ωσ)}𝕏_{σ^{−1}ω}(𝔸^{ω}, 𝔹)) ≡ f ∂_{σ} (𝔹)

the scalar product by its expression (f, g) = ∑ ±(fg)^{σ}Δ(𝔸)^{−1}. It becomes

∑_{ζ} ±f(𝔸^{ζ})𝕏_{σ^{−1}ω}(𝔸^{ωζ}, 𝔸))\frac{1}{Δ} = f(𝔸)∂_{σ} ;

erasing f, which is irrelevant, one gets the proposition. □

Since K_{n}(𝔸, 𝔹) = (^{−}1)^{ℓ(ω)} 𝕏_{ω}(𝔸^{ω}, 𝔹) and since ω∂_{σ}ω = ∂_{ωσω}, the two expressions of ∂_{σ} involve specializations of Schubert polynomials, but not the same polynomials, as mentioned in [22]. One has in fact, for any pair of permutations,

(4.5.6)  (^{−}1)^{ℓ(σ)}𝕏_{σ}(𝔸, 𝔸^{ζ}) = 𝕏_{ωσω}(𝔸^{ω}, 𝔸^{ωζ}) .

4.6. YANG-BAXTER BASES OF H^{0,0} 71

4.6. Yang-Baxter Bases of H^{0,0}

Given n independent parameters x = {x_{1}, …, x_{n}}, invariant under 𝔖(𝔸), we have defined in (2.3.6) a Yang-Baxter basis of H^{0,0}, which is adjoint to the basis corresponding to the reversed parameters x_{n}, …, x_{1}.

Let us give the expansion of this basis in terms of the natural basis basis {∂_{σ}} of H^{0,0}.

To avoid denominators, we change definition (2.3.6), and take now, with Y_{1} = 1,

(4.6.1)  Y_{σs_{i}} = Y_{σ} (1 + (x_{σ_{i+1}}^{−}x_{σ_{i}}) ∂_{i}) , ℓ(σs_{i}) > ℓ(σ).

Let σ and i be such that ℓ(σ) < ℓ(σs_{i}). Suppose known the expansion

Y_{σ} = ∑_{ν} ∂_{ν} 𝕏_{ν}(x^{σ}, x) + ∂_{νs_{i}} 𝕏_{νs_{i}}(x^{σ}, x) ,

with ν : ℓ(ν) < ℓ(νs_{i}). Then its product by 1^{+}(x_{σ_{i+1}}^{−}x_{σ_{i}})∂_{i} is

∑_{ν} ∂_{ν} 𝕏_{ν}(x^{σ}, x) + ∂_{νs_{i}} (𝕏_{νs_{i}}(x^{σ}, x) + 𝕏_{ν}(x^{σ}, x)(x_{σ_{i+1}}^{−}x_{σ_{i}})) ,

and the identities

𝕏_{ν}(x^{σs_{i}}, x) & 𝕏_{νs_{i}}(x^{σs_{i}}, x) = 𝕏_{νs_{i}}(x^{σ}, x)+𝕏_{ν}(x^{σ}, x)(x_{σ_{i+1}}^{−}x_{σ_{i}})

give a similar expansion for Y_{σs_{i}} and prove the following theorem.

Theorem 4.6.1. The matrix of change of basis between {Y_{σ}} and {∂_{σ}Δ(x)}, and its inverse, have entries which are specializations of Schubert polynomials :

(4.6.2)  Y_{σ} = ∑_{ν≤σ} ∂_{ν} 𝕏_{ν}(x^{σ}, x) ,
(4.6.3)  ∂_{ν} Δ(x) = ∑ Y_{σ} 𝕏_{ων}(x, x^{ωσ}) .

Notice that recursions on Schubert polynomials provided by divided differences are easier to understand than recursions on Yang-Baxter coefficients, because two sets of variables are easier to handle than one set!

ACE> NcaYang([3,2,1]);
  A[1,2,3] +(-x2+x1)(-x3+x1)A[2,3,1] +(x3-x1)A[1,3,2]
  -(-x2+x1)(-x3+x2)(-x3+x1)A[3,2,1]+(x3-x1)A[2,1,3]
       +(-x3+x1)(-x3+x2)A[3,1,2]
# The coefficients are all the specializations of Schubert
#  polynomials in y1=x3, y2=x2, y3=x1
ACE> TableXX(3,[3,2,1]);

      # specializes the y.i into a permutation of the x.i
table([
    [1, 2, 3] = 1
    [2, 3, 1] = (-x3 + x1) (-x3 + x2)
    [1, 3, 2] = -x3 + x1
    [3, 2, 1] = (-x2 + x1) (-x3 + x2) (-x3 + x1)
    [2, 1, 3] = -x3 + x1
    [3, 1, 2] = (-x2 + x1) (-x3 + x1)
    ])

4.7. Yang-Baxter Elements as Permutations

We have obtained Schubert polynomials in the expression of divided differences in the basis of permutations (4.5.5), or, conversely, of permutations in the basis of divided differences.

We obtained them again in Theorem 4.6.1, this time while developing Yang-Baxter elements. In fact, one passes from the expression of a permutation σ to the expression of Y_{σ} by just changing formally x into 𝔸 in Eq. (4.6.2).

The rules were different in the two cases, the symmetric group acting on the variables a_{i}, but not on the variables x_{i}.

This formal change between the two formulas may be interpreted as developing products like (1^{+}∂_{1}(a_{2}^{−}a_{1}))(1^{+}∂_{2}(a_{3}^{−}a_{1})) ⋯, ignoring the fact that the ∂_{i}’s act on the variables a_{j}.

Let us show one way why Yang-Baxter elements can be identified as permutations.

Sums of permutations in 𝔖(𝔸), or of divided differences, can be characterized by their action on the single element K(𝔸, 𝔹).

For what concerns Yang-Baxter elements, one has to make them act on

K(𝔸, x) := ∏_{1≤i<j≤n}(a_{i} − x_{j}) = 𝕏(𝔸, x^{ω}) ,

the x_{j} being the spectral parameters, and the a_{i} being the variables on which act divided differences.

Let us see an example of the action of successive Yang-Baxter elements in the case n = 4, indicating the successive images of K(𝔸, x), and below the permutation of spectral parameters.

\frac{\begin{matrix}a_{1}−x_{2} \\ a_{1}−x_{3} & a_{2}−x_{3} \\ a_{1}−x_{4} & a_{2}−x_{4} & a_{3}−x_{4} \end{matrix}}{[x_{1}, x_{2}, x_{3}, x_{4}]}⟶^{1+∂_{2}(x_{3}−x_{2})} \frac{\begin{matrix}a_{1}−x_{2} \\ a_{1}−x_{3} & a_{2}−x_{2} \\ a_{1}−x_{4} & a_{2}−x_{4} & a_{3}−x_{4} \end{matrix}}{[x_{1}, x_{3}, x_{2}, x_{4}]}⟶^{1+∂_{1}(x_{3}−x_{1})} \frac{\begin{matrix}a_{1}−x_{2} \\ a_{1}−x_{1} & a_{2}−x_{2} \\ a_{1}−x_{4} & a_{2}−x_{4} & a_{3}−x_{4} \end{matrix}}{[x_{3}, x_{1}, x_{2}, x_{4}]}

⟶^{1+∂_{3}(x_{4}−x_{2})} \frac{\begin{matrix}a_{1}−x_{2} \\ a_{1}−x_{1} & a_{2}−x_{2} \\ a_{1}−x_{4} & a_{2}−x_{4} & a_{3}−x_{4} \end{matrix}}{[x_{3}, x_{1}, x_{4}, x_{2}]} ⟶^{1+∂_{2}(x_{4}−x_{1})} \frac{\begin{matrix}a_{1}−x_{2} \\ a_{1}−x_{1} & a_{2}−x_{2} \\ a_{1}−x_{4} & a_{2}−x_{1} & a_{3}−x_{4} \end{matrix}}{[x_{3}, x_{1}, x_{4}, x_{2}]}

We notice that, at each step involving ∂_{i}, the polynomial to transform is the product of a polynomial symmetrical in a_{i}, a_{i+1} by a linear factor (a_{i}^{−}x), that we indicate by a double box. Its image under (1^{+}(x′^{−}x′′)∂_{i}) is (a_{i}^{−}x′′), because, by chance, one also has that x = x′. Therefore, all the images are products of factors (a^{−}x). More precisely, they are equal to 𝕏_{ω}(𝔸, x^{ωσ}), the Yang-Baxter elements (in 𝔸) act as permutations on x.

It is not difficult to extend the computation to any 𝔖_{n}, The combinatorial property to observe, and prove by induction on length, is the following one.

Lemma 4.7.1. For any σ, the diagram representing 𝕏_{ω}(𝔸, x^{ω}) Y_{σ}(x) is such that for any j : 1 ≤ j ≤ n^{−}1, its j-th column is equal to

∏_{k∈{σ_{j+1},...,σ_{n}}} (a_{j} − x_{k}) .

The preceding result translates into the following algebraic statement, which states that the Yang-Baxter elements act by permutation.

Theorem 4.7.2. The image of 𝕏_{ω}(𝔸, x^{ω}) under the Yang-Baxter element Y_{σ}(x) is

𝕏_{ω}(𝔸, x^{σω}) .

Exercises

Ex. 4.1. Let 𝔸 = {a_{1}, …, a_{n}}. Write the Vandermonde Δ(𝔸) := ∏_{i<j}(a_{i} − a_{j}) in terms of simple Schubert polynomials X_{σ}(𝔸) and X_{σ}(𝔸^{ω}) (with ω maximal element of 𝔖(𝔸)). Write in a similar manner the product ∏_{i<j}(a_{i} + a_{j}). Solution. Δ(𝔸) = 𝕏_{ω}(𝔸, 𝔸^{ω}), and therefore, according to (4.2.9), it expands into

Δ(𝔸) = ∑_{σ∈𝔖(𝔸)}(−1)^{ℓ(σ)}X_{σω}(𝔸)X_{σ}(𝔸^{ω}) .

Similarly,

S_{1...n−1}(𝔸) = ∏_{i<j}(a_{i} + a_{j}) = ∑_{σ∈𝔖(𝔸)}X_{σω}(𝔸)X_{σ}(𝔸^{ω}) .

Thus, the sum ∏_{i<j}(a_{i} − a_{j}) + ∏_{i<j}(a_{i} + a_{j}) involves permutations of even length, and the difference involves permutations of odd length. These expressions may be used to describe invariants of the alternating group.

Ex. 4.2. Let 𝔸 = {a_{1}, …, a_{4}}. For any σ ∈ 𝔖(𝔸), compute the image under ∂_{σ} of (x − a_{2})^{−1}(x − a_{3})^{−2}(x − a_{4})^{−3}. Solution. Multiplying by the symmetrical factor ∏_{a∈𝔸}(x^{−}a)^{3}, one has to compute the image of

(x^{−}a_{1})^{3}(x^{−}a_{2})^{2}(x^{−}a_{3}) = 𝕏_{4321}(𝔸, 𝔹) ,

with 𝔹 = {x, x, x, x}, and therefore one gets 𝕏_{ωσ}(𝔸, 𝔹)R(x, 𝔸)^{−3}.

Ex. 4.3. Let 𝔸^{+} be the shifted alphabet

𝔸^{+} = {a_{1}^{+}1, a_{2}^{+}1, a_{3}^{+}1, …}

Expand the Schubert polynomials X_{σ}(𝔸^{+}) in the basis X_{ν}(𝔸). Comment the case where σ is a Grassmannian permutation, i.e. a permutation with only one descent.

Ex. 4.4. Given 𝔸 finite, 𝔹 infinite, given a partition J, expand the Schur function S_{J}(𝔸) in terms of the Schubert polynomials 𝕏_{σ}(𝔸, 𝔹).

ACE> CLG_n(3);
#one fixes the number of variables x_i when expanding symm functions
ACE> NewtonInterp(Tox_n(s[2,1]),5): # Newton, using the group S_5
ACE> map(factor,%);
XX[1, 3, 5, 2, 4] + (y2+y1) (y3+y1) (y3+y2) XX[1, 2, 3, 4, 5]
     + (y2 + y1) XX[1, 2, 5, 3, 4]
     + (y2 + y1) (y3 + y1 + y4 + y2) XX[1, 2, 4, 3, 5]
     + (y3 + y1 + y4 + y2) XX[1, 3, 4, 2, 5]

Ex. 4.5. Denote [i] the q-integer [i] := 1 + q + ⋯ + q^{i−1}. Fix two parameters α, β and for any indeterminate x, any k ∈ ℕ, define its modified k-power x^{<k>} by

x^{<k>} := (x − α)(x − qα − [1]β) ⋯ (x − q^{k−1}α − [k^{−}1]β) .

Given K = [k_{1}, …, k_{n}] ∈ ℕ^{n}, and x_{1}, …, x_{n}, compute the quotient of the determinant |x_{i}^{<k_{j}>}| by the Vandermonde in x_{1}, …, x_{n}. Solution. Each factor x−q^{k}α−[k]β may be rewritten (x^{−}γ)−q^{k}(α^{−}γ), with γ = β(1 − q)^{−1}. Therefore, the required quotient is obtained from a q-factorial Schur function under an easy modification.

Ex. 4.6. Denote by Y_{J}^{+k} a Schubert polynomial

𝕐_{J}({a_{1+k}, a_{2+k}, …}, 𝔹) .

For any n, k ∈ ℕ, factorize the triangular matrix [Y_{0^{j−i}, k−j}^{+i−1}]_{0≤i,j≤n−1} into a product of matrices, each depending only upon a single b_{i} ∈ 𝔹 (and upon 𝔸; one puts Y_{0^{j−i}r} = 0 when j < i). Solution. The matrix is the commutative product of

[\begin{matrix}a_{1}^{−}b & 1 & 0 \\ 0 & ... & ... \\ & & & 1 \\ & & & a_{n}^{−}b \end{matrix}] , b ∈ \{b_{1}, …, b_{k}\} ,

as can be checked by induction on k, using the relations

Y_{0^{m−1}j} = Y_{0^{m−2}j} + (a_{m} − b_{j+m−1}) Y_{0^{m−1}j−1} .

Ex. 4.7. Let m, n ∈ ℕ. Let I be the family of partitions contained in n^{n}, S be set of permutations σ such that Y_{0^{m},n^{n}}∂_{σ} ≠ 0. For each increasing partition I ≤ n^{n}, denote by Y_{[I]} the Schubert polynomial in 𝔸, 𝔹 of index [0^{m}, i_{1}, …, i_{n}].

Compute the inverse of the matrix [Y_{[I]}∂_{σ}]_{I∈Ii,σ∈S}. Solution. The required inverse is the matrix obtained by replacing each Schubert polynomial Y_{ν} by ±Y_{ν^{−1}}, each entry of the product of the two matrices being obtained by the Cauchy formula (4.2.9).

For example, for m= 0, n = 2, the following two matrices are inverse from each other :

[\begin{matrix}1 & Y_{01} & Y_{02} & Y_{11} & Y_{12} & Y_{22} \\ 0 & 1 & Y_{001} & Y_{1} & Y_{101} & Y_{201} \\ 0 & 0 & 1 & 0 & Y_{1} & Y_{2} \\ 0 & 0 & 0 & 1 & Y_{001} & Y_{011} \\ 0 & 0 & 0 & 0 & 1 & Y_{01} \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}] , [\begin{matrix}1 & −Y_{01} & Y_{011} & Y_{200} & −Y_{201} & Y_{22} \\ 0 & 1 & −Y_{001} & −Y_{1} & Y_{101} & −Y_{12} \\ 0 & 0 & 1 & 0 & −Y_{1} & Y_{11} \\ 0 & 0 & 0 & 1 & −Y_{001} & Y_{02} \\ 0 & 0 & 0 & 0 & 1 & −Y_{01} \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix}]

Of course, the same method gives the inverse of a matrix where, instead of using the family Y_{[I]}, I ∈ I, one takes a permutation ζ and all the Schubert polynomials X_{η}, where η runs over all permutations lower than ζ in the permutohedron.

Notice also that the above pair of matrices looks more mysterious when specializing 𝔹 to {1, q, q^{2}, …} (factorial skew Schur functions), or even when 𝔹 = 0. This exercise generalizes Ex. ??, where we used only complete functions.

Ex. 4.8. Develop 𝕏_{σ}(𝔸, {b, 0, 0, …}) in terms of powers of b. Comment the case where σ is a Grassmannian permutation. Solution.

For general 𝔸, 𝔹, we have 𝕏_{σ}(𝔸, 𝔹) = ∑(−1)^{ℓ(ν)}X_{ν}(𝔹)X_{η}(𝔸), sum over reduced factorizations ν^{−1}η of σ. But

∑_{ν∈𝔖_{n}}(−1)^{ℓ(ν)}X_{ν}({b, 0, 0, …})u_{ν} = (1 − bu_{n−1}) ⋯ (1 − bu_{1}) .

Taking ζ = σ^{−1}, the two functions above may be written in terms of divided differences:

(−1)^{ℓ(σ)} = 𝕏_{ζ}({b, 0, 0, …}, 𝔸) = 𝕏_{ζ}(1 − ∂_{1}b) ⋯ (1 − ∂_{n−1}b)

the right-hand side being evaluated in (0, 𝔸).

In the Grassmannian case, J being the code of σ, one has

𝕏_{σ}(𝔸, {b, 0, 0, …}) = S_{J}(𝔸 − b) ,

and the expansion of S_{J}(𝔸 − b) produces a sum over all partitions obtained from J by removal of a vertical strip. This property is more generally true for a vexillary permutation, though defining vertical and horizontal strips require some work, compared to the case of a partition.

For example, 𝕏_{1475236}(𝔸, 𝔹) = 𝕐_{0242}(𝔸, 𝔹) = 𝕐_{033011}(𝔹, 𝔸), and

𝕐_{033011}(1 − ∂_{1}b) ⋯ (1 − ∂_{6}b) = \begin{matrix}𝕐_{033011} \\ −b𝕐_{030211} − b𝕐_{033010} \\ +b^{2}𝕐_{030111} + b^{2}𝕐_{030210} \\ −b^{3}𝕐_{030110} \end{matrix}

which by inversion of permutation, gives

\begin{matrix}𝕐_{0242} \\ −b𝕐_{0142} − b𝕐_{0232} \\ +b^{2}𝕐_{0141} + b^{2}𝕐_{0132} \\ −b^{3}𝕐_{0131} \end{matrix} .

Ex. 4.9. Given a positive integer n, and 𝔸 of cardinality n, write the linear morphism on the ring of polynomials in 𝔸, as a free-module over 𝔖𝔶𝔪(𝔸), induced by 𝕏_{σ}(𝔸, 0) → 𝕏_{σ^{−1}}(𝔸, 0), σ ∈ 𝔖_{n}, without using the Schubert basis.

Adding a second alphabet 𝔹, do the same for the linear morphism induced by 𝕏_{σ}(𝔸, 0) → 𝕏_{σ}(𝔸, 𝔹). Solution.

It is better to introduce another alphabet {x_{1}, …, x_{n}}, apart from 𝔸 = {a_{1}, …, a_{n}}, 𝔹 = {b_{1}, …, b_{n}}. Let us assume that divided differences act on the x_{i}’s only, and write Θ for the specialization of x_{1}, …, x_{n} to 0.

Then, a direct consequence of the Cauchy kernel is that

𝕏_{σ}(x_{1}, …, x_{4}; 0) \begin{matrix}1 + ∂_{3}b_{1} \\ 1 + ∂_{2}b_{1} & 1 + ∂_{3}b_{2} \\ 1 + ∂_{1}b_{1} & 1 + ∂_{2}b_{2} & 1 + ∂_{3}b_{3} \end{matrix} Θ = 𝕏_{σ^{−1}}(𝔹, 0) ,

where the array is a product of divided differences acting on its left, which is read by successive rows, from top to bottom (it could also be read by columns downwards, from left to right). The reader will agree that n = 4 be general enough.

Similarly, and more generally,

𝕏_{σ}(x_{1}, …, x_{4}; 0) \begin{matrix}1 + ∂_{3}(a_{3}^{−}b_{1}) \\ 1 + ∂_{2}(a_{2}^{−}b_{1}) & 1 + ∂_{3}(a_{2}^{−}b_{2}) \\ 1 + ∂_{1}(a_{1}^{−}b_{1}) & 1 + ∂_{2}(a_{1}^{−}b_{2}) & 1 + ∂_{3}(a_{1}^{−}b_{3}) \end{matrix} Θ = 𝕏_{σ}(𝔸, 𝔹) .

Therefore, the two triangles of operators, followed by the specialization Θ, constitute an answer.

Bibliography

[1] C. Carré, A. Lascoux, B. Leclerc. Turbo straightening, Int J. of Algebra and Comp. (1992) 275-290.

[2] J. Désarmenien. An algorithm for the Rota straightening formula, Discrete M. 30 (1980) 51–68.

[3] J. Désarmenien, J. King, G.C. Rota. Invariant Theory, Young bitableaux and combinatorics, Adv. in M. 27 (1978) 63–92.

[4] W. Fulton and J. Harris, Representation theory, A first course, Graduate Texts in Mathematics 129, Springer-Verlag, New York, 1991.

[5] W. Fulton, Young Tableaux, London M.S. Student Text 35, Cambridge University Text (1997).

[6] H. Garnir, Théorie de la représentation des groupes symétriques, Mémoires de la Soc. Royale des Sc. de Liège 10 (1950).

[7] C.G. Jacobi. Über die Darstellung einer reihe gegebener werthe durch eine gebrochene rationale function, Crelle J., 30, (Werke III, 479–511), (1845) 127– 156

[8] G. James, A. Kerber. The representation theory of the symmetric group, Encyclopedia of Maths, vol 16 Addison-Wesley (1981).

[9] A. Jucys, Symmetric polynomials and the center of the symmetric group rings, Rep. Math. Phys. 5 (1974) 107–112.

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

[11] A. Lascoux, Cyclic permutations on words, tableaux and harmonic polynomials, Proceedings of the Hyderabad Conference on Algebraic Groups (Hyderabad, 1989), Manoj Prakashan, Madras, 1991, 323-347.

[12] A. Lascoux. Potentiel Yin sur le groupe symétrique, Séminaire Lotharingien de Combinatoire 38 (1996)

[13] A. Lascoux. Young’s natural idempotents as polynomials, Annals of Combinatorics 1 (1997) 91–98.

[14] A. Lascoux, B. Leclerc and J.Y. Thibon. Flag Varieties and the Yang-Baxter Equation , Letters in Math. Phys., 40 (1997) 75–90.

[15] A. Lascoux & M.P. Schützenberger. Polynômes de Schubert, Comptes Rendus 294 (1982) 447–450.

[16] A. Lascoux & M.P. Schützenberger. Structure de Hopf de l’anneau de cohomologie et de l’anneau de Grothendieck d’une variété de drapeaux, Comptes Rendus 295 629–633.

[17] A. Lascoux & M.P. Schützenberger. Symmetry and Flag manifolds, Invariant Theory, Springer L.N., 996 (1983) 118–144.

[18] A. Lascoux & M.P. Schützenberger. Schubert polynomials and the Littlewood-Richardson rule, Letters in Math.Phys, 10 (1985) 111–124.

[19] A. Lascoux & M.P. Schützenberger. Fonctorialité des polynômes de Schubert, in Invariant Theory, Contemporary Maths, 88 (1989) 585–598.

[20] A. Lascoux & M.P. Schützenberger. Symmetrization operators on polynomial rings, Funk. Anal. 21 (1987) 77–78.

[21] A. Lascoux & M.P. Schützenberger. Tableaux and non commutative Schubert Polynomials, Funk.Anal 23(1989) 63–64.

[22] A. Lascoux & M.P. Schützenberger. Algèbre des différences divisées, Discrete Maths, 99 (1992) 165–179.

[23] A. Lascoux & M.P. Schützenberger. Treillis et bases des groupes de Coxeter, Electronic Journal of Combinatorics 3 (1996) R27.

[24] D.E. Littlewood, The Theory of Group Characters and Matrix Representations of Groups, Oxford University Press, New York 1940.

[25] I. G. Macdonald. Symmetric functions and Hall polynomials. Oxford University Press, Oxford, 2nd edition (1995).

[26] P. Magyar. Schubert polynomials and Bott-Samelson varieties, Commentarii Mathematici Helvetici 73 (1998), 603-636.

[27] A. Okounkov, A. Vershik, A new approach to representation theory of symmetric groups, Selecta Math., 2 (1996) 581–605.

[28] H. Padé. Sur la représentation approchée d’une fonction par des fractions rationnelles, Annales Sci. E.N.S. (3)9(1982) 1–93.

[29] D.E. Rutherford, Substitutional Analysis, Edinburgh, at the University Press, 1948.

[30] J.J. Sylvester. A theory of the syzygetic relations of two rational integral functions, Phil. Trans. Royal Soc. London vol CXLIII, Part III (1853) 407–548.

[31] H. Weyl, The classical groups, their invariants and their representations, Princeton University Press, Princeton, 1946.

[32] C.N. Yang, Some exact results for the many-body problem in one dimension with repulsive delta-function interaction, Phys. Rev. Lett. 19 (1967), 1312– 1315.

[33] A. Young. The Collected Papers of Alfred Young, University of Toronto Press

Index

Binet-Cauchy formula, 9 Braid relations, 19

Cauchy formula, 9 Cauchy-Schubert Formula, 65 Cayley Graph, 20 Cayley-Hamilton theorem, 17 Central Idempotent, 32 Complete function, 1 Conjugate Compositions, 31

Divided difference, 19

Elementary symmetric function, 1 Euler-Poincaré characteristic, 39

Grothendieck, 17

Hecke relation, Hecke algebra, 20 Hermite, 40

Isobaric divided difference, 19

Jacobi-Trudi determinant, 3 Jacobi-Trudi matrix, 16

Lagrange Interpolation, Operator, 33 Lambda-ring, 10 Legendre polynomial, 11

Moore/Coxeter relations, 19 Multi-Schur function, 4, 15 Multi-Schur: transformation, 5 Multivariate Newton Interpolation, 69

Natural Idempotents, 31 Newton divided differences, 19 Newton Interpolation, 35 Non-symmetric Kernel, 60 Padé approximant, 7 Permutation Representation, 43 Permutohedron, 20 Power sum, 1

Rectangular Schur function, 6 Reduced decomposition, 20 Reproducing Kernel, 60 Residue, 40 Resultant, 6

Schur function, skew Schur function,

3 Spectral Parameters, 25 Stirling numbers, 40 Straightening, 46

Yang-Baxter Bases of H^{0,0}, 71

Yang-Baxter Bases of Hecke algebras,

26 Yang-Baxter Graph, Relations, 23 Yang-Baxter Polynomial, 51 Yin Relation, 25