INTERPOLATION

Alain Lascoux

The original problem of interpolation is: how to reconstruct a one-variable function knowing its values at a finite number of points?

Of course, we know that this is possible only in the case of polynomials, of degreee strictly less than the number of interpolation points. In the general case, we shall have only an approximation of the function.

Another way to formulate the problem is the following:

we favor a linear space V of functions. Given f, one wants a function p(f) in V which is as ”near” to f as possible.

The functional p should satisfy :

• Linearity: λf + μg → p(λf + μg) = λp(f) + μp(g), λ,μ ∈ ℂ

• Idempotence: p^{2} = p

How do we input f ? In general, by the values L_{0}(f), …,L_{n}(f) of linear functionals L_{0}, …,L_{n} at f.

Forthesolutiontobepossibleandunique,onesupposesthattherestriction of the L_{i} to V are linearly independent (which amounts to say that the L_{i} are a basis of the space dual to V; in particular, n + 1 = dim(V)).

Now we can reformulate our interpolation problem this way :

Given f, find g in V such that

L_{0}(f) = L_{0}(g), …,L_{n}(f) = L_{n}(g) .

Other problem: find a basis {g_{i}} of V adapted to the L_{i}, for example, such that the matrix | L_{j}(g_{i}) | is the identity matrix.

Symmetrically, one can start from a basis of the space V and look for the associated functionals. We shall give examples of these different points of view.

Lagrange Interpolation

The simplest spaces of functions are the space of polynomials in one variable. Take for example V = Pol(n) := space of polynomials in x of degree ≤ n.

At the same time, the simplest linear functionals are taking the value in a fixed set of points 𝔸, with cardinal (𝔸) = n + 1.

The looked for interpolation polynomial g is the (unique) polynomial g of degree ≤ n such that

(Lgr1)  a ∈ 𝔸 ⇒ g(a) = f(a)

Denote by R(𝔸,𝔹) the product ∏_{a∈𝔸,b∈𝔹}(a − b), and by 𝔸 \ 𝔹 the set difference.

One remarks that for every a ∈ 𝔸 the polynomial R(x,𝔸 \ a) vanishes in all the points of 𝔸 other than a. It is clear that by linear combination of these n + 1 polynomials of degree n, one can express any element of V, and thus these polynomials constitute the basis adapted to the functionals L_{a} : f → L_{a}(f) := f(a), modulo normalisation.

In other words, one has Lagrange formula (J. Ecole Polyt., II,p.277 ) :

(Lgr2)  g(x) = ∑_{a∈𝔸} f(a)\frac{R(x,𝔸 \ a)}{R(a,𝔸 \ a)} .

The application f → g is a projector on the space Pol(n) of polynomials of degree n. This projector is no other than the “Remainder modulo R(x,𝔸)” since it is the identity on Pol(n) and since it vanishes on every multiple of R(x,𝔸) (and thus its values on every polynomial is well determined).

Lagrange interpolation allows decomposition of rational fractions : dividing both members of (Lgr2) by R(x,𝔸) one gets the equivalent form :

(Lgr3)  \frac{g(x)}{R(x,𝔸)} = ∑_{a∈𝔸} \frac{f(a)}{(x − a)R(a,𝔸 \ a)} .

Indeed, in the the preceeding formula, the “variable” x plays a role symmetrical to the “interpolation points a ∈ 𝔸”, i.e. it can be written as a summation on the alphabet 𝔸 ∪ {x}.

One is therefore led to replace (Lgr3) by the following operator on one-variable functions :

f → ∑_{a∈𝔸} f(a)/R(a,𝔸 \ a) ∈ 𝔖𝔶𝔪(𝔸) ,

where 𝔖𝔶𝔪(𝔸) is the ring of symmetric functions in 𝔸.

This is not our last transformation of Lagrange formula. One notices that the starting space does not need to be restricted to functions of one variable, but can be taken to be 𝔖𝔶𝔪(1|n), the space of functions of n + 1 variables which are symmetrical in the last n ones. Put a total order on the alphabet 𝔸 = {a_{1},a_{2}, …,a_{n+1}}. Since last century at least, one knows that functions f(a_{1}; a_{2}, …,a_{n+1}), symmetrical in a_{2}, …,a_{n+1}, can be expressed as functions of a_{1} only, with coefficients in the ring of functions which are symmetrical in all the variables, that is 𝔖𝔶𝔪(𝔸); on another hand, the preceeding operator commutes with multiplication by every element of 𝔖𝔶𝔪(𝔸), one can thus extend it to the space 𝔖𝔶𝔪(1|n), considered as a module over the ring 𝔖𝔶𝔪(𝔸) generated by the powers of a_{1}.

Thus , Lagrange operator is the symmetrization operator:

(Lgr4) 𝔖𝔶𝔪(1|n) ∋ f → ∑ f(a,𝔸\a) / R(a,𝔸\a) := L_{𝔸}(f) ∈ 𝔖𝔶𝔪(𝔸) .

Since powers of a_{1} generate 𝔖𝔶𝔪(a_{1}|a_{2}, …,a_{n+1}) as a 𝔖𝔶𝔪(𝔸)-module, it suffices to determine the values L_{A}(a_{1}^{k}), k ≥ 0 to characterize Lagrange operator (we shall see later that {a_{1}^{0}, …,a_{1}^{n}} is a basis). One can refer to Euler, who knew that

(Lgr5)  ∀k ≥ 0, ∑ a^{k}/R(a,𝔸 \ a) = S_{k−n}(𝔸) ,

where the S_{k}(𝔸) are the complete functions of 𝔸, i.e. the sum of all monomials in 𝔸 of a given degree.

Indeed, taking the generating function of the powers of a_{1}, that is 1/(1 − za_{1}), one could compute that

(Lgr5′)  ∑_{a∈𝔸} \frac{1}{(1 − za)R(a,𝔸 \ a)} = \frac{z^{n}}{∏(1 − za)} .

In fact, the computation of the image by Lagrange operator of the function 1/(1−zx) can be avoided, by having recourse to the alphabet 𝔹 = 𝔸∪{1/z}. Identity Lagr5’ can be written, up to the coefficient \frac{1}{z} :

(Lgr5”) \frac{1}{R(1/z,𝔸)} + ∑_{a} \frac{1}{R(a,𝔸 \ a) R(a,1/z)} = ∑_{b∈𝔹} \frac{1}{R(b,𝔹 \ b)} = 0 ,

nullity being forced by the fact that the summation must be a polynomial of negative degree.

More generally, given two alphabets 𝔸,𝔹, with 𝔸 of cardinal n + 1, by linearity from (Lgr5′), one has

(Lgr6)  L_{𝔸}(\frac{∏_{b∈𝔹}(1 − zb)}{1 − za_{1}}) = \frac{z^{n} ∏(1 − zb)}{∏(1 − za)} ,

i.e. , for every r, writing x for a_{1},

(Lgr6′)  L_{𝔸}(S_{r}(x − 𝔹)) = S_{r−n}(𝔸 − 𝔹) .

Lagrange operator, as given in (Lgr4), sends one-variable polynomials of degree < n to 0. In the general case, this is the operator which expresses the remainder in the usual Lagrange formula. It can also be interpreted in terms of the Euclidean division of polynomials, but this time it gives the quotient and not the remainder.

Indeed, let 𝔹 be any alphabet, m an integer (which does not need to be the cardinal of 𝔹), 𝔸 be another alphabet of cardinal n, x a variable. Using the Lagrange operator associated to the alphabet {x,𝔸}, one can rewrite (Lgr6’) as

(Lgr7) S_{m}(x − 𝔹)/R(x,𝔸) − ∑_{a} \frac{S_{m}(a − 𝔹)}{(x − a)R(a,𝔸 \ a)} = S_{m−n}(x + 𝔸 − 𝔹) ,

which can be considered as a division (Lgr7′)

S_{m}(x − 𝔹) = ∑_{a} \frac{S_{m}(a − 𝔹)R(x,𝔸 \ a)}{R(a,𝔸 \ a)} + S_{m−n}(x + 𝔸 − 𝔹) · R(x,𝔸) ,

showing that S_{m−n}(x + 𝔸 − 𝔹) is the quotient in the Euclidean division, and that the remainder is equal to L_{𝔸}(S_{m}(a_{1} − 𝔹) R(x,𝔸\a_{1})).

The Lagrange interpolation on an alphabet 𝔸 of cardinal n+1 is givenbyanoperatorL_{𝔸} from𝔖𝔶𝔪(1|n)to𝔖𝔶𝔪(n+1),characterized by the properties

• it is 𝔖𝔶𝔪(𝔸)-linear

• it sends a_{1}^{0}, …,a_{1}^{n−1} to 0 and a_{1}^{n} to 1 .

Symmetric Functions

For efficient recursions, one needs to consider symmetric functions as ”functors” on alphabets. This essentially means that instead of defining complete functions as coefficients in the expansion of a rational series ∏_{a∈𝔸} 1/(1 − za), we can take arbitrary families {S_{k}}_{k≥0} of elements of a commutative ring, with the only restriction that S_{0} = 1. Indeed, to any formal series f = ∑_{k≥0} z^{k}S_{k}, Littlewood [ch. 6.4] associated the infinite Hankel matrix 𝕊(f) = (S_{j−i})_{j,i≥0} , putting S_{i} = 0 if i < 0 , and defined skew Schur functions to be the minors of this matrix.

More precisely, given I = (i_{1}, …,i_{n}) ∈ ℤ^{n}, J = (j_{1}, …,j_{n}) ∈ ℤ^{n} he defined S_{J/I} to be the minor of 𝕊(f) taken on rows i_{1} + 1,i_{2} + 2, …,i_{n} + n and columns j_{1} + 1, …,j_{n} + n (the minor is 0 if one of these numbers is < 0). When I = 0^{n} , one writes S_{J} instead of S_{J/0^{n}}.

In other words,

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

The case of a rational series f = ∏_{b∈𝔹}(1 − zb)/ ∏_{a∈𝔸}(1 − za) for two alphabets 𝔸 and 𝔹 corresponds by definition to the Schur functions of a difference of alphabets (“super Schur functions”), i.e. the coefficients of f are the complete functions S_{j}(𝔸−𝔹) . Let us denote 𝕊(𝔸−𝔹) the corresponding Hankel matrix. This case covers in fact the case of general formal power series, since when the cardinal of 𝔸 or 𝔹 is infinite, the S_{k}(𝔸) (resp. S_{k}(𝔹)) are algebraically independent.

Now, addition of alphabets corresponds to multiplication of generating series or multiplication of the associated Hankel matrices, and formal substraction corresponds to division of series or multiplication by the inverse of the Hankel matrix. In other words

A − 𝔹 + ℂ ⇔ 𝕊(𝔸 − 𝔹 + ℂ) = 𝕊(𝔸) 𝕊(𝔹)^{−1} 𝕊(ℂ)

⇔ \frac{∏(1 − zb)}{∏(1 − za) ∏(1 − zc)} = \frac{1}{∏(1 − za)} ∏(1 − zb)\frac{1}{∏(1 − zc)}

More explicitely,

(Sf2)  S_{k}(𝔸 − 𝔹 + ℂ) = ∑_{i,j,h:i+j+h=k} S_{i}(𝔸)S_{j}(−𝔹)S_{h}(ℂ)

Erasing a common factor in the numerator and denominator of a rational function corresponds to writing (𝔸 + ℂ) − (𝔹 + ℂ) = 𝔸 − 𝔹.

Let us remark that, 𝔸 being finite of cardinal n, then the (−1)^{k}S_{k}(−𝔸) are the elementary symmetric functions in 𝔸, the S_{k}(x − 𝔸), k < n, are the truncations of the polynomial R(x,𝔸), while S_{n}(x,𝔸) = R(x,𝔸), and for k > n,

S_{k}(−𝔸) = 0 , S_{k}(x − 𝔸) = x^{k−n} S_{n}(x − 𝔸) .

General identities on minors imply identities on Schur functions.

For example, given two matrices M,N, with dimensions such that their product MN exists, Binet & Cauchy found a simple expression for the minors of MN (using the above conventions for indexing: I,J ∈ ℕ^{n}, H runs over all partitions in ℕ^{n} ):

[MN]_{I,J} = ∑_{H} [M]_{I,H} [N]_{H,J} .

For Schur functions, this imply

(Sf3)  S_{J/I}(𝔸 ± 𝔹) = ∑_{H} S_{H/I}(𝔸) S_{J/H}(±𝔹) .

Similarly, the correspondence, due to Jacobi, between the minors of a matrix and those of its inverse reads

(Sf4)  S_{J/I}(𝔸 − 𝔹) = (−1)^{|J/I|}S_{J /I}(𝔹 − 𝔸) ,

for a pair of partitions I,J and their conjugates J , I , where |J| stands for j_{1} + ⋯ + j_{n} and |J/I| for j_{1} + ⋯ + j_{n} − i_{1} − ⋯ − i_{n} (see the appendix or [Mcd1]).

Given a finite alphabet 𝔸 of cardinal n, one can also have recourse to the alphabet of its inverses 𝔸^{⋆} := {1/a}_{a∈𝔸}.

The relation S_{k}(−𝔸^{⋆}) = S_{n−k}(−𝔸) /S_{n}(−𝔸) extends to

(Sf5)  S_{I}(−𝔸^{⋆}) = S_{n^{r}/I}(−𝔸) S_{n}(−𝔸)^{r} ,

I partition with parts ≤ n, r sufficiently big so that I ⊆ n^{r}

WestillneedtoenlargethedefinitionofaSchurfunction,thistimeallowing to play with different alphabets at the same time. In [L1], geometry imposed to take flags of alphabets (i.e. 𝔸_{1} ⊆ 𝔸_{2} ⊆ 𝔸_{3} ⊆ ⋯), but the methods used thereby extend without pain, though not using the graphical display of partitions (Ferrers’ diagrams) rendered in [L1] the involution 𝔸 → −𝔸 more difficult to state.

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

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

In the case where the alphabets are repeated, we indicate by a comma 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} = 𝔻.

These functions are now sufficiently general to allow easy inductions, thanks to the following transformation lemma.

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

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

Proof. — In other words, one does not change the value of a multi-Schur function S_{J} by replacing in row h the difference 𝔸 − 𝔹 by 𝔸 − 𝔹 − 𝔻_{n−h}. Indeed, thanks to the expansion (Sf2) :

S_{j}(𝔸−𝔹−𝔻_{h}) = S_{j}(𝔸−𝔹)+S_{1}(−𝔻_{h}) S_{j−1}(𝔸−𝔹)+⋯+S_{h}(−𝔻_{h}) S_{j−h}(𝔸−𝔹),

the sum terminating because the S_{k}(−𝔻_{h}) are null for k > h, we see that the determinant has been transformed by multiplication by a triangular matrix with 1’s in the diagonal, and therefore has kept its value

For example, taking D_{0} = ∅, 𝔻_{1} = {x}, 𝔻_{2} = {y,z}, one has

( \begin{matrix}S_{i}(𝔸_{1} − y − z) & S_{j+1}(𝔸_{2} − y − z) & S_{h+2}(𝔸_{3} − y − z) \\ S_{i−1}(𝔸_{1} − x) & S_{j}(𝔸_{2} − x) & S_{h+1}(𝔸_{3} − x) \\ S_{i−2}(𝔸_{1}) & S_{j−1}(𝔸_{2}) & S_{h}(𝔸_{3}) \end{matrix} ) =

= ( \begin{matrix}1 & −y − z & yz \\ 0 & 1 & −x \\ 0 & 0 & 1 \end{matrix} ) · ( \begin{matrix}S_{i}(𝔸_{1}) & S_{j+1}(𝔸_{2}) & S_{h+2}(𝔸_{3}) \\ S_{i−1}(𝔸_{1}) & S_{j}(𝔸_{2}) & S_{h+1}(𝔸_{3}) \\ S_{i−2}(𝔸_{1}) & S_{j−1}(𝔸_{2}) & S_{h}(𝔸_{3}) \end{matrix} )

and the determinant of the left matrix is equal to S_{ijh}(𝔸_{1},𝔸_{2},𝔸_{3}). This lemma implies many factorization properties, e.g. for r ≥ 0,

(Sf8)  S_{J}(𝔸 − 𝔹 − x) x^{r} = S_{J,r}(𝔸 − 𝔹,x)

since taking 𝔻_{1} = 𝔻_{2} = ⋯ = {x} factorizes the determinant S_{J,r}(𝔸−𝔹,x). More generally, for an alphabet 𝔻 of cardinal ≤ r and J ∈ ℕ^{r}, one has

(Sf9)  S_{I}(𝔸 − 𝔹 − 𝔻) S_{J}(𝔻) = S_{I,J}(𝔸 − 𝔹, 𝔻) .

Monomials themselves can be written as Schur functions. For an infinite alphabet 𝔸, let 𝔸_{n} be the initial sub-alphabet 𝔸_{n} := {a_{1}, …,a_{n}}. Let I = (i_{1}, …,i_{n}) ∈ ℕ^{n}, and write a^{I} for a_{1}^{i_{1}} ⋯ a_{n}^{i_{n}}, I^{ω} for (i_{n}, …,i_{1}). Then one has

(Sf10)  a^{I} = S_{I^{ω}}(𝔸_{n}, …,𝔸_{1}) ,

as one can see by subtracting 0,𝔸_{1}, …,𝔸_{n−1} in the successive rows, from the bottom.

For example,

a^{742} = S_{247}(𝔸_{3},𝔸_{2},𝔸_{1}) = det | \begin{matrix}S_{2}(𝔸_{3}) & S_{5}(𝔸_{2}) & S_{9}(𝔸_{1}) \\ S_{1}(𝔸_{3}) & S_{4}(𝔸_{2}) & S_{8}(𝔸_{1}) \\ S_{0}(𝔸_{3}) & S_{3}(𝔸_{2}) & S_{7}(𝔸_{1}) \end{matrix} | =

= det | \begin{matrix}a_{3}^{2} & 0 & 0 \\ a_{2} + a_{3} & a_{2}^{4} & 0 \\ 1 & S_{3}(a_{1} + a_{2}) & a_{1}^{7} \end{matrix} | .

Any other ordering of the alphabet will lead to another determinantal expression of a monomial :

a^{742} = S_{742}(a_{3} + a_{2} + a_{1}, a_{3} + a_{2}, a_{3}) .

From the above, we see that monomials in 𝔸_{n} can be expressed as linear combinations (with coefficients in 𝔖𝔶𝔪(𝔸_{n})) of monomials a^{J} : J ≤ (n − 1, …,1,0), or monomials a^{I} : I ≤ (0,1, …,n − 1). Indeed,

(Sf11) a^{H} = S_{H}(𝔸_{n}, …,a_{n} + a_{n−1},a_{n}) = S_{H}(𝔸_{n}, …,𝔸_{n} − 𝔸_{n−2},𝔸_{n} − 𝔸_{n−1}) .

Column k is of degree 1 in the variables a_{1}, …,a_{k−1}, and thus only monomials a^{J} : J ≤ (n − 1, …,1,0) appear in the expansion of the determinant.

The resultant R(𝔸,𝔹) is of fundamental importance in interpolation theory, in elimination theory, in the theory of symmetric functions, in other words in premodern or postmodern algebra.

There are many determinantal expressions of it, which all are related to the fact that it is a special Schur function.

Indeed, let 𝔸, 𝔹 be of respective cardinals m, n. Then

(Sf12) R(𝔸,𝔹) = S_{n^{m}}(𝔸 − 𝔹) = (−1)^{mn}S_{m^{n}}(𝔹 − 𝔸) = S_{n^{m},0^{n}}(𝔸,𝔹) .

Proof. — Take any a in 𝔸. Then S_{n^{m}}(𝔸 − 𝔹) = S_{n,n^{m−1}}(𝔸 − 𝔹,𝔸 − a − 𝔹) according to (Sf7), subtracting a in all the columns except the first one (instead of subtracting in rows). Now subtract {𝔸\a} in the first row of the new determinant. It factorizes into S_{n}(a − 𝔹) S_{n^{m−1}}({𝔸\a} − 𝔹), which proves the result by induction on m. (Sf9) gives the last expression where 𝔸 and 𝔹 have been separated.

Multi-Schur functions, being defined as determinants, are bound to technics of minors.

For example, one can use Laplace’s expansion along a subfamily of rows or columns. Let I ∈ ℕ^{m}, J ∈ ℕ^{n}. Given H ∈ ℕ^{n}, denote H^{ω} + J := (j_{1} + h_{n}, …,j_{n} + h_{1}). Then

(Sf13)  S_{I,J}(𝔸,𝔹) = ∑_{H}(−1)^{|H|}S_{I/H}(𝔸) S_{J+H^{ω}}(𝔹) ,

sum on all partitions H ∈ ℕ^{n}, H ⊆ m^{n}.

In particular, for n = 1, one has

(Sf14)  S_{I,j}(𝔸,𝔹) = ∑_{0≤h≤m}(−1)^{h}S_{I/1^{h}}(𝔸) S_{j+h}(𝔹) .

The fundamental involution 𝔸 → −𝔸, which in the case (Sf4) of a Schur function S_{J/I}(𝔸) expresses it as a determinant of elementary functions S_{k}(−𝔸), does not allow in general to exchange the role of complete and elementary symmetric functions in a multi-Schur function. In [L1] are given conditionsforhavingtwodeterminantalexpressionsofamulti-Schurfunction (see also [Mcd2]). We skip this point at the moment, and shall handle it later more easily with Schubert polynomials.

Complete functions in the difference of two alphabets 𝔸, 𝔹, are defined by the generating function

∑ z^{r}S_{r}(𝔸 − 𝔹) := ∏_{a∈𝔸,b∈𝔹}(1 − zb)/(1 − za) .

Multi-Schur functions are determinants in complete functions S_{r}(𝔸^{j} − 𝔹^{j}), with alphabets A^{j}, 𝔹^{j} fixed in each column of the determinant.

Symmetrizing operators

Divided differences ∂_{μ} have been introduced by Newton to solve the interpolation problem in one variable. We shall also need the isobaric divided differences π_{μ}.

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

(So1)  \{ \begin{matrix}∂_{i} & = \frac{1}{(a_{i} − a_{i+1})}(1 + σ_{i}) \\ π_{i} & = \frac{1}{(1 − a_{i+1}/a_{i})}(1 + σ_{i}) = a_{i}∂_{i} \end{matrix}

More explicitely, ∂_{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)}:

(So2)  \{ \begin{matrix}f ∂_{i} & = \frac{f(… a_{i},a_{i+1} …) − f(… a_{i+1},a_{i} …)}{a_{i} − a_{i+1}} \\ f π_{i} & = \frac{a_{i} f(… a_{i},a_{i+1} …) − a_{i+1} f(… a_{i+1},a_{i} …)}{a_{i} − a_{i+1}} \end{matrix}

One has to complete (So1) by the values for μ = identity which are

∂_{id} = 1 , π_{id} = 1

.

Both families of operators {σ_{i}}, {∂_{i}}, {π_{i}} separately satisfy the Moore/Coxeter relations (writing {D_{i}} in each of these three cases) :

(So3)  D_{i}D_{j} = D_{j}D_{i} if |i − j| ≥ 2 ,

(So4)  D_{i}D_{i+1}D_{i} = D_{i+1}D_{i}D_{i+1} .

Relations (So3) and (So4) imply that ∂_{μ},π_{μ} can be written as the product of elementary operators ∂_{i}, π_{i} corresponding to any reduced decomposition of μ (i.e. any decomposition μ = σ_{i} ⋯ σ_{j} of minimal length gives ∂_{μ} = ∂_{i} ⋯ ∂_{j}, π_{μ} = π_{i} ⋯ π_{j}).

One can notice that

(So5)  \{ \begin{matrix}∂_{i}∂_{i} & = 0 \\ π_{i}π_{i} & = π_{i} & . \end{matrix}

In [L-S ?] , one characterizes more general operators D_{i} of the type

f → D_{i}(f) = P (a_{i},a_{i+1}) f + Q(a_{i},a_{i+1}) f^{σ_{i}} ,

(where P and Q are rational functions of two variables) satisfying Moore-Coxeter relations. It happens that they must also satisfy an Hecke relation (with constants q and r)

(So6)  D_{i}D_{i} = qD_{i} + r .

In other words, these operators D_{i} furnish a representation of the Hecke algebra of the symmetric group as an algebra of operators on the ring of polynomials.

The most useful of these operators is, apart from the two degenerate cases ∂_{i} and π_{i},

D_{i} := c_{1}∂_{i} + c_{2}π_{i} + c_{3}σ_{i} ,

with constants c_{1},c_{2},c_{3}.

Let 𝔸 be of cardinal n, and ω be the maximal permutation of 𝔖(A), i.e. ω sends a_{1}, …,a_{n} onto a_{n}, …,a_{1}. Then the operators ∂_{ω} and π_{ω} have the following global expression (that we shall prove at the end of the section), apart from being (in different ways) the products of the ∂_{i}, resp. π_{i}:

(So7 f ∂_{ω} = ∑_{μ∈𝔖(A)} (f/Δ)^{μ} ,

(So8) f π_{ω} = ∑_{μ∈𝔖(A)} (fρ/Δ)^{μ} ,

where Δ is the Vandermonde : Δ = ∏_{i<j}(a_{i} − a_{j}) and ρ the monomial a_{1}^{n}a_{2}^{n−1} ⋯ a_{n+1}^{0} (which corresponds to half the sum of positive roots, in the theory of classical groups).

Divided differences satisfy a Leibniz formula, as easily seen from the definition:

(So9)  fg∂_{i} = f (g∂_{i}) + f∂_{i} g^{σ_{i}}

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

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

Divided differences have a simple action on complete functions: let 𝔹 be any alphabet and 𝔸_{i} denotes {a_{1}, …,a_{i}} for any i less than the cardinal of 𝔸. Then

(So10)  (\frac{R(1,𝔹)}{R(1,𝔸_{i})}) ∂_{i} = \frac{R(1,𝔹)}{R(1,𝔸_{i+1})} ,

(So11)  (\frac{R(1,𝔹)}{R(1,𝔸_{i})}) π_{i} = \frac{R(1,𝔹)}{R(1,𝔸_{i+1})} ,

because, writing 1/R(1,𝔸_{i}) = (1−a_{i+1})/R(1,𝔸_{i+1}), and using the fact that R(1,𝔸_{i+1}) is a scalar for both ∂_{i} and π_{i}, one is reduced to check that

(1 − a_{i+1}) ∂_{i} = 1 = (1 − a_{i+1}) π_{i} .

More explicitely, (So10) and (So11) can be written

(So12)  (S_{k}(𝔸_{i} − 𝔹)) ∂_{i} = S_{k−1}(𝔸_{i+1} − 𝔹) ,

and

(So13)  (S_{k}(𝔸_{i} − 𝔹)) π_{i} = S_{k}(𝔸_{i+1} − 𝔹)

Divided differences have a simple action on (multi)-Schur functions, in the case that they operate only on the elements of one row or one column : take S_{jk...l}(𝔸_{i} − 𝔹_{1},𝔸_{p} − 𝔹_{2}, …,𝔸_{r} − 𝔹_{q}), and suppose that all the indices of the 𝔸, apart from, say the first, column are different from i. Then all columns are scalars for ∂_{i} and π_{i}, apart from the first one, and from (So12) and (So13) one gets that the images of the preceeding function under ∂_{i} and π_{i} are respectively

(So14)  S_{j−1 k...l}(𝔸_{i+1} − 𝔹_{1},𝔸_{p} − 𝔹_{2}, …,𝔸_{r} − 𝔹_{q})

(So15)  S_{jk...l}(𝔸_{i+1} − 𝔹_{1},𝔸_{p} − 𝔹_{2}, …,𝔸_{r} − 𝔹_{q}) .

Let us look now at the action of

∂_{ω} = (∂_{n−1})(∂_{n−2}∂_{n−1}) ⋯ (∂_{1} ⋯ ∂_{n−1}) .

Writing any monomial in 𝔸_{n} as a Schur function S_{I}(𝔸_{n}, …,𝔸_{2},𝔸_{1}), we see that at each step of applying the ∂_{i}, only one column of the determinant is not symmetrical in a_{i},a_{i+1}, and thus that the action increases alphabets and decreases degree; the final step gives a Schur function S_{J}(𝔸).

For example, a_{4}^{2}a_{3}^{5}a_{2}^{6}a_{1}^{9} = S_{2569}(𝔸_{4},𝔸_{3},𝔸_{2},𝔸_{1}) . Our expression of ∂_{ω} is ∂_{4321} = (∂_{3}) (∂_{2}∂_{3}) (∂_{1}∂_{2}∂_{3}).

Under ∂_{3} the monomial becomes S_{2469}(𝔸_{4},𝔸_{4},𝔸_{2},𝔸_{1}), then under ∂_{2}∂_{3}, S_{2449}(𝔸_{4},𝔸_{4},𝔸_{4},𝔸_{1}) and finaly, under ∂_{1}, ∂_{2}, ∂_{3},

S_{2446}(𝔸_{4},𝔸_{4},𝔸_{4},𝔸_{4}) = S_{2446}(𝔸) .

Now, the image of a monomial under the operator (So7) is an alternating sum of monomials, divided by the Vandermonde, which is Jacobi-Trudi expression of the same Schur function, and thus ∂_{ω} coïncides with (So7), because the images of any monomial under both operators are the same. An identical proof works for π_{ω}, this time the indices being preserved.

A simpler proof of the validity of (So7) consists first in noticing that both operators (∂_{ω} and the summation) are 𝔖𝔶𝔪(𝔸)-linear. Therefore, we need only to check their action on a generating set, which from (Sf11) can be taken as the monomials {a^{J} : J ≤ ρ}. Now all these monomials are sent to 0 by both operators, except for a^{ρ} which is sent to 1 by f ⟶ ∑ ±f^{μ}/Δ(𝔸), and to S_{0...0} = 1 by ∂_{ω}

Multi-Schur functions can be obtained with the help of ∂_{ω}. For example, let {𝔹^{1},𝔹^{2}, …,𝔹^{n}} be n finite alphabets of respective cardinals i_{1},i_{2}, …,i_{n}; we denote this sequence by I, and put J = i_{1} − 0,i_{2} − 1, …,i_{n} − (n − 1). Then

(So16)  R(a_{n},𝔹^{1}) ⋯ R(a_{1},𝔹^{n}) ∂_{ω} = S_{J}(𝔸_{n} − 𝔹^{1}, …,𝔸_{n} − 𝔹^{n}) .

Proof. — Write R(a_{n},𝔹^{1}) ⋯ R(a_{1},𝔹^{n}) as S_{I}(𝔸_{n} − 𝔹^{1}, …,𝔸_{1} − 𝔹^{n}), according to (Sf7) : the determinant becomes triangular after subtraction of {0,𝔸_{1}, …,𝔸_{n−1}}, because in the upper part we are left with elementary symmetric functions of degree strictly higher than the cardinals of the alphabets involved. Now, the action of (∂_{n−1})(∂_{n−2}∂_{n−1}) ⋯ (∂_{1} ⋯ ∂_{n−1}) consists, thanks to (So14), in transforming all the 𝔸_{i} into 𝔸_{n} while decreasing the indices

The Schur function S_{I}(𝔸 − 𝔹) can be obtained by a double sommation on 𝔖(𝔸) and 𝔖(𝔹) as stated by Sergeev-Pragacz formula [].

For every permutation μ ∈ 𝔖(𝔸), there exist a divided difference ∂_{μ} and an isobaric divided difference π_{μ}. The maximum divided difference ∂_{ω} is the operator

f ⟶ ∑ ±f^{μ}/Δ(𝔸) .

The ring 𝔖𝔶𝔪(1 | n)

We already used the fact that the ring

𝔖𝔶𝔪(1|n) = 𝔖𝔶𝔪(a_{1}) ⊗_{ℤ} 𝔖𝔶𝔪(a_{2}, …,a_{n+1})

withcoefficientsinℤisaℤ-freemodulewithbasis{S_{I}(𝔸−a_{1}) a_{1}^{k},I partition ∈ ℕ^{n},k ∈ ℕ}. One of the essential properties of Lagrange operator is its compatibility with Schur functions as shown by the following lemma :

LEMMA (P r1). — Let 𝔸 be of cardinal n + 1 and L_{𝔸} the corresponding Lagrange operator. Then

1) L_{𝔸} is equal to the product ∂_{1} ⋯ ∂_{n} (acting on its left).

2) ∀I ∈ ℤ^{n},I ≥ −(0 1 ⋯ n −1), ∀k ≥ 0,

L_{𝔸}(S_{I}(𝔸 − a_{1}) a_{1}^{k}) = S_{I k−n}(𝔸) .

Proof. — Writing the product S_{I}(𝔸−a_{1})a_{1}^{k} as the Schur function S_{I,k}(𝔸,a_{1}), we are reduced to compute the image of powers of a_{1} under L_{𝔸}, and thus, thanks to (Lgr5) and (So12), we obtain the required determinant of complete functions of 𝔸.

Now, since S_{I,k}(𝔸,a_{1}) is a ℤ-basis, the powers of a_{1} are a generating set for 𝔖𝔶𝔪(1|n) as a 𝔖𝔶𝔪(𝔸)-module. The formulas (Lgr6′) and (So12) show that the 𝔖𝔶𝔪(𝔸)-linear operators L_{𝔸} and ∂_{1} ⋯ ∂_{n} coincide

The interest of taking I ≥ −(0 1 ⋯ n −1) instead of I ∈ ℕ^{n} will appear later.

It was already clear in the preceeding proof that an essential property of 𝔖y𝔪(1|n) is to be a 𝔖𝔶𝔪(𝔸)-module. Indeed, the ℤ-basis S_{I}(𝔸 − a_{1})a_{1}^{k} = S_{I,k}(𝔸,a_{1}) can be written in terms of powers of a_{1} only (with coefficients in 𝔖𝔶𝔪(𝔸)); moreover, because the elementary symmetric functions of the alphabet {𝔸\a_{1}} vanish in degree > n, one has

a_{1}^{k} = S_{k}(a_{1}) = S_{k}(𝔸 + (a_{1} − 𝔸)) = ∑_{0}^{n} S_{k−i}(𝔸) S_{i}(a_{1} − 𝔸) .

Thus, {a_{1}^{0}, …,a^{n}} is a generating system for our ring as a module over 𝔖𝔶𝔪(𝔸). To prove that it is a basis, i.e. that every element of 𝔖𝔶𝔪(1|n) can be uniquely written

f = c_{0}a_{1}^{0} + ⋯ + c_{n}a_{1}^{n} ,

with coefficients c_{i} in 𝔖𝔶𝔪(𝔸), (in other words, the module is free), we shall first define on it a quadratic form with values in 𝔖𝔶𝔪(𝔸). Definition(P r2). — ∀P ,Q ∈ 𝔖𝔶𝔪(1|n), set (P | Q) := L_{𝔸}(P Q).

PROPOSITION (P r3). —

1)𝔖𝔶𝔪(1|n) is a 𝔖𝔶𝔪(𝔸)-free module of basis {1,a_{1}, …,a_{1}^{n}}, as well as basis {S_{n}(a_{1} − 𝔸), …,S_{0}(a_{1} − 𝔸)}.

2) The quadratic form is non-degenerate, i.e there does not exist P ≠ 0 such that for all Q in 𝔖𝔶𝔪(𝔸) (P,Q)=0. The two above bases are adjoint, i.e., for 0 ≤ h,k ≤ n, (a_{1}^{k},S_{n−h}(a_{1} − 𝔸))= 1 or 0 according that k = h or not.

3) Every element f of 𝔖𝔶𝔪(1|n) can be written

f = ∑_{0}^{n} L_{𝔸}(fS_{k}(a_{1} − 𝔸)) a_{1}^{n−k} ,

f = ∑_{0}^{n} L_{𝔸}(fa_{1}^{n−k}) S_{k}(a_{1} − 𝔸) .

Proof. — We have to write

S_{h}(a_{1} − 𝔸) a_{1}^{k} = (−1)^{h}S_{1^{h}}(𝔸 − a_{1}) a_{1}^{k} = (−1)^{h}S_{1^{h},k}(𝔸,a_{1}) .

Now the image under L_{𝔸} = ∂_{1} ⋯ ∂_{n} is (−1)^{h}S_{1^{h},k−n}(𝔸,𝔸).

The indices in the first row of this determinant are 1,2, …,h,k − n + h. They are all different and non negative only when k − n + h = 0, i.e. only when the determinant is obtained from the determinant expressing S_{0^{h+1}}(𝔸) = 1 by permuting columns.

Therefore the square matrix with entries the L_{𝔸}(S_{i}(a_{1} − 𝔸)a_{1}^{k}) is the identity matrix, which proves that the quadratic form is non-degenerate and that a_{1}^{0}, …,a_{1}^{n} are linearly independent, with adjoint basis S_{n}(a_{1} − 𝔸), …,S_{0}(a_{1} − 𝔸). This pair of adjoint bases allows now to expand in two different ways any element of the module by taking scalar products

The ring 𝔖𝔶𝔪(1|n) can be identified with the equivariant cohomology ring of a relative projective space of dimension n, and the operator L_{𝔸} to the Gysin morphism from 𝔖𝔶𝔪(1|n) to the cohomology of the base (identified with 𝔖𝔶𝔪(𝔸)). The variable a_{1} is the first Chern class of the tautological line bundle, (1+a_{2}) ⋯ (1+a_{n+1}) is the total Chern class of the tautological kernel (see [Fu1])

The ring 𝔖𝔶𝔪(1|n) is a free module over 𝔖𝔶𝔪(𝔸), with basis {1,a_{1}, … a_{1}^{n}}, and an explicit adjoint basis with respect to the scalar product

(f,g) := L_{𝔸}(fg) .

The ring 𝔖𝔶𝔪(r | m)

Lagrange operator can be expressed as a summation on subsets of cardinal 1 of a given alphabet 𝔸. Its generalization is straightforward : sum on subsets of cardinal r.

Let r,m be two posiive integers,𝔸 an alphabet of card. n = r + m. Then the operator

(Gr1) 𝔖𝔶𝔪(r) ⊗ 𝔖𝔶𝔪(m) ∋ f → ∑_{𝔸′,card(𝔸′)=r} f(𝔸′ , 𝔸 \ 𝔸′)/R(𝔸′ , 𝔸 \ 𝔸′)

may be called the Sylvester operator of order r. Indeed, Sylvester expressed the discriminant of a polynomial, or the greatest common divisor of two polynomials using this operator.

The alphabet being totally ordered, Sylvester operator can also be expressed through divided differences. Denote ∂_{r|m} the product

(Gr2)  ∂_{r|m} := (∂_{r} ⋯ ∂_{n−1})(∂_{r−1} ⋯ ∂_{n−2}) ⋯ (∂_{1} ⋯ ∂_{m−1})

It is the divided difference indexed by the permutation

μ = (r+1) ⋯ n, 1 ⋯ r .

Let 𝔖𝔶𝔪(r|m) denote the ring of functions in r + m variables, which are symmetrical in the first r ones, and symmetrical separately in the last m ones. When identifying the variables to the elements of 𝔸_{r} := {a_{1}, ⋯,a_{r}} and 𝔸 \ 𝔸_{r}, we shall also write 𝔖𝔶𝔪_{r|m}(𝔸).

PROPOSITION (Gr3). —

1) Sylvester operator is equal to ∂_{r|m}.

2) Sylvester operator is 𝔖𝔶𝔪(𝔸)-linear and is the only 𝔖𝔶𝔪(𝔸)-linear operator sending the S_{J}(𝔸_{r}), J partition such that J ⊂ m^{r}, to zero and S_{m^{r}}(𝔸_{r}) to 1.

3) It sends products of Schur functions to Schur functions, i.e. for every I ∈ ℕ^{m}, J ∈ ℕ^{r}, one has

(S_{I}(𝔸 − 𝔸_{r}) · S_{J}(𝔸_{r}))∂_{r|m} = S_{(IJ)−(0^{m}m^{r})}(𝔸) ,

where IJ − 0^{m}m^{r} means I_{1} − 0, …,I_{m} − 0,J_{1} − m, …,J_{r} − m.

Proof. — Thanks to (Sf9) one writes S_{J}(𝔸_{r})S_{I}(𝔸 − 𝔸_{r}) as S_{J,I}(𝔸,𝔸 − 𝔸_{r}). The expansion of this determinant is a linear combination of S_{H}(−𝔸_{r}), H partition : H ≤ r^{m}.

Therefore, when taking coefficients in 𝔖𝔶𝔪(𝔸), one can express any element of 𝔖𝔶𝔪(r|m) as a combination of the S_{J}(𝔸_{r}), with partitions J contained in m^{r}.

Now one remarks that Sylvester operator and ∂_{r|m} are both 𝔖𝔶𝔪(𝔸)- linear, and that they decrease degree by rm. Thus they send all S_{J}(𝔸_{r}), J partition : J ⊂ m^{r}, to zero, and they send S_{m^{r}}(𝔸_{r}) to constants. We check below that the image of Schur functions in 𝔸_{r} by ∂_{r|m}, and we get in this case S_{0...0} = 1. As for Sylvester summation, we can as well compute the sum

∑_{𝔸′} \frac{R(𝔸′,𝔸 \ 𝔸_{r})}{R(𝔸′,𝔸 \ 𝔸′)}

because R(𝔸′,𝔸 \ 𝔸_{r}) has leading term S_{m^{r}}(𝔸′). Now, clearly in this summation there is only the term 𝔸′ = 𝔸_{r} which is non zero (and equal to 1).

The two operators, coïnciding on a generating set, are equal, and this proves 1) and 2). We shall check later that the generating set is linearly independent, and thus that 𝔖𝔶𝔪(r|m) is a free module of dimension rm over 𝔖𝔶𝔪(𝔸).

As for the last point, one writes (once more!) S_{I}(𝔸 − 𝔸_{r})S_{J}(A_{r}) = S_{I,J}(𝔸,𝔸_{r}). However, the action of the divided difference ∂_{r} on this Schur function is not straightforward, because ∂_{r} acts non trivially on the r last columns of the determinant, and one would have to use Leibniz formula. Fortunately, one can overcome this by taking other products of divided differences. Let us take numerical values to follow more easily the computation, say r = 3, m = 2, IJ = 12467. Instead of starting with S_{12, 467}(𝔸,𝔸_{3}), we take S_{12479}(𝔸,𝔸,𝔸_{3},𝔸_{2},𝔸_{1}) which gives under ∂_{2}∂_{1}∂_{2} the preceeding function.

Now we have to compute the image of S_{12479}(𝔸,𝔸,𝔸_{3},𝔸_{2},𝔸_{1}) under (∂_{2}∂_{1}∂_{2}) (∂_{3}∂_{4}∂_{2}∂_{3}∂_{1}∂_{2}), acting on the left. But, thanks to the braid relations, this operator can be written (∂_{3}∂_{4})(∂_{2}∂_{3}∂_{4})(∂_{1}∂_{2}∂_{3}∂_{4}).

This sequence of operators is such that at each step of the computation of the image of S_{12479}(𝔸,𝔸,𝔸_{3},𝔸_{2},𝔸_{1}), there is only one column which is transformed (in which case, the transformation amounts to S_{k}(𝔸_{i}) ⟶ S_{k−1}(A_{i+1)}) and finally we get the Schur function S_{12233}(𝔸,𝔸,𝔸,𝔸,𝔸) as required

Of course, we could have proved the preceeding proposition by mere expansions of determinants (as we did in [L1], [L2]), but using divided differences avoids the subtilities of determinantal calculus which have been lost since the time of Sylvester.

We did not give full details here, because with Schubert polynomials, we shall not even need determinants at all.

Having seen that we have to use the structure of 𝔖𝔶𝔪(r|m) as a free 𝔖𝔶𝔪(𝔸)-module, we define on it a quadratic form with the help of Sylvester operator :

(Gr4)  𝔖𝔶𝔪(r|m) ∋ f,g ⇒ (f,g) := fg ∂_{r|m} ∈ 𝔖𝔶𝔪(𝔸) .

PROPOSITION (Gr5). —

1)𝔖𝔶𝔪(r|m) is a free 𝔖𝔶𝔪(𝔸)-module with the two basis {S_{I}(𝔸_{r})} and {S_{I}(𝔸_{r} − 𝔸}, where I runs over all partitions I : 0 ⊆ I ⊆ m^{r}.

2) The quadratic form is non degenerate, and the two bases {S_{I}(𝔸_{r})} and {S_{I}(𝔸_{r} − 𝔸} are adjoint with respect to it. More precisely, one has (S_{I}(𝔸_{r} − 𝔸) · S_{J}(𝔸_{r})) ∂_{r|m} = 1 or 0 according that I = (m− J_{r} … m− J_{1}) or not.

3) Every element f of 𝔖𝔶𝔪(r|m) can be written

f = ∑_{I⊆m^{r}} f S_{I}(𝔸 − 𝔸_{r})∂_{r|m} S_{I}(𝔸_{r}) .

Proof. — The proof is the same as in the case of 𝔖𝔶𝔪(1|m). We have to compute all the S_{K}(𝔸 − 𝔸_{r}) S_{J}(𝔸_{r}) ∂_{r|m}.

Now, proposition (Gr3) gives them as a determinant of complete functions in 𝔸, with respective indices in the first row

K_{1},K_{2} + 1, …,K_{m} + m − 1,J_{1},J_{2} + 1, …,J_{r} + r − 1 .

Using the hypothesis that 0 ⊆ K ⊆ r^{m} and 0 ⊆ J ⊆ m^{r}, we see that these n integers belongs to the set {0,1, … n − 1}. Therefore, for every partition J, there exists one and only one partition K such that the determinant has all its columns distinct, and no column with all indices negative. In this case, the determinant is obtained from S_{0...0} = 1 by a permutation of columns. The conjugate of the partition K gives us the partition I specified by the theorem (we have taken S_{K}(𝔸 − 𝔸_{r}) instead of S_{I}(𝔸_{r} − 𝔸)).

Thus the matrix |S_{I}(𝔸_{r} − 𝔸)S_{J}(𝔸_{r}) ∂_{r|m}| is the identity matrix, which proves that the quadratic form is non degenerate and that the two sets are bases of the module.

Having two adjoint bases, we can now expand any element of 𝔖𝔶𝔪(r|m) by computing scalar products

We have seen in the preceeding section that computing in the ring 𝔖𝔶𝔪(1|m) was related to finding the first remainder in the Euclidean division. Similarly, we can use 𝔖𝔶𝔪(r|m) to express the remainder of degree r < n − 1. This gives some determinantal expressions of the remainder, as well as expressions using Sylvester operator as a summation on subsets of given cardinal.

The ring 𝔖𝔶𝔪(r|m) can be identified with the (equivariant) cohomology ring of a relative Grassmann variety and 𝔖𝔶𝔪(𝔸) to the cohomology ring of the base. The variables a_{1}, …,a_{r} are the Chern roots of the tautological quotient bundle . The operator ∂_{r|m} is the Gysin morphism. The Schur functions S_{I}(𝔸_{r}) are representatives of the Schubert subvarieties of the Grassamanniann. When computing modulo the ideal generated by symmetric polynomials without constant term, the quadratic form ∂_{r|m}(f,g) becomes the intersection form. It was already well known at the end of the 19th century that Schubert varieties in complementary degree intersect in 0 point or 1 point, and that the matrix representing the intersection form is the identity matrix.

The ring 𝔖𝔶𝔪(r|m) is a free module over 𝔖𝔶𝔪(𝔸), with basis S_{I}(a_{1}, …,a_{r}), and adjoint basis S_{I}(a_{r+1}, …,a_{r+m}), where the partition I runs over all partitions I ≤ r^{m}.

Rational interpolation

The resultant R(𝔸,𝔹) plays a fundamental role in the summations generalising Lagrange interpolation, as well as in invariant theory or elimination theory. It can be itself expressed through summations implying other resultants, and we shall only present the following ”exchange lemma”.

LEMMA Rt1. — Let 𝔸,𝔹,ℂ be three alphabets of respective cardinals m+n, n, m. Then one has the following identity

∑_{𝔸′+𝔸′′=𝔸} \frac{R(𝔸′,𝔹′)}{R(𝔸′,ℂ) R(𝔸′,𝔸′′)} = \frac{R(𝔹,ℂ)}{R(𝔸,ℂ)} ,

sum on all disjoint decompositions of 𝔸 in 𝔸′ + 𝔸′′, card(𝔸′) = m, card(𝔸′′) = n, as well as the identity

∑_{𝔸′+𝔸′′=𝔸} \frac{R(𝔸′,𝔹′) R(𝔸”,ℂ)}{R(𝔸′,𝔸′′)} = R(𝔹,ℂ) .

Proof. — The two identities are equivalent up to multiplication by R(𝔸,ℂ) = R(𝔸′,ℂ)R(𝔸′′,ℂ).

The product of the two resultants can be written as the Schur function:

R(𝔸′,𝔹) R(𝔸′′,ℂ) = S_{m^{n},n^{m}}(𝔸 − ℂ,𝔸′ − 𝔹) .

UsingthefactorisationofSylvesteroperatorf ⟶ ∑ f(𝔸′,𝔸′′)/R(𝔸′,𝔸′′) as a product of divided differences, one obtains

∑ R(𝔸′,𝔹) R(𝔸′′,ℂ)/R(𝔸′,𝔸′′) = S_{m^{n},0^{m}}(𝔸 − ℂ,𝔸 − 𝔹)

Writing 𝔸 − ℂ = (𝔸 − 𝔹) + (𝔹 − ℂ), one develops

S_{m^{n}0^{m}}(𝔸 − ℂ,𝔸 − 𝔹) = ∑_{I} S_{I 0^{m}}(𝔸 − 𝔹) S_{m^{n}/I}(𝔹 − ℂ) .

All the S_{I0^{m}}, I ⊆ m^{n}, are null (having at least two identical columns), except for I = 0^{n}; therefore

∑ R(𝔸′,𝔹) R(𝔸′′,ℂ)/R(𝔸′,𝔸′′) = S_{m^{n}}(𝔹 − ℂ) = R(𝔹,ℂ)

A consequence of this exchange property is the determination of the numerator and denominator of a rational function knowing sufficiently many of its values (Cauchy(1841) , Rosenhain (1846)):

THEOREM Rt2. — Let P et Q be two unitary polynomials of respective degrees n,m, and f = P/Q. Let 𝔸 be an alphabet of cardinal m + n + 1. Then, if 𝔸 is generic enough,

f(x) = \frac{∑_{𝔸′,card=n} R(x,𝔸′) ∏_{a′∈𝔸′} f(a′) / R(𝔸′,𝔸\𝔸′)}{∑_{𝔸′,card=m} R(x,𝔸′) ∏_{a′∈𝔸′} f(a′) / R(𝔸′,𝔸\𝔸′)}

Proof.—WriteP (x) = R(x,𝔹),card(𝔹) = n,Q(x) = R(x,ℂ),card(ℂ) = m. The rational function f is therefore equal to

f = R(x,𝔹)/R(x,ℂ) = (−1)^{mn}R(x + ℂ,𝔹)/R(x + 𝔹,ℂ)

Using the preceeding lemma for the pair of alphabets (x + 𝔹,ℂ), one has

\frac{R(x + 𝔹,ℂ)}{R(𝔸,ℂ)} = ∑_{card(𝔸′)=m,𝔸′′=𝔸−𝔸′} \frac{R(𝔸′,x + 𝔹)}{R(𝔸′,ℂ)R(𝔸′,𝔸′′)} =

= ∑_{𝔸′} \frac{R(𝔸′,x)}{R(𝔸′,𝔸′′)} \frac{R(𝔸′,𝔹)}{R(𝔸′,ℂ)} = ∑_{𝔸′} ∏_{a′} f(a′)\frac{R(𝔸′,x)}{R(𝔸′,𝔸′′)}

and similarly for the numerator.

Since we have introduced the extra factor R(𝔹,ℂ), we must have a genericity condition which ensures that it is non zero

One can also give a determinantal form to the preceeding computation ( with z = 1/x) :

PROPOSITION Rt3. — Let f(z) = P (z)/Q(z) be a rational function, d^{o}(P) ≤ n, d^{o}(Q) ≤ m, and 𝔸 be an alphabet of cardinal m + n + 1. Then one has the identity

𝔸 \{ | \begin{matrix}⋮ & ⋮ & & ⋮ & ⋮ & & ⋮ & ⋮ \\ 1 & a & ⋯ & a^{n} & a^{m}f(a) & ⋯ & af(a) & f(a) \\ ⋮ & ⋮ & & ⋮ & ⋮ & & ⋮ & ⋮ \\ Q(z) & zQ(z) & ⋯ & z^{n}Q(z) & z^{m}P (z) & ⋯ & zP (z) & P (z) \end{matrix} | = 0

Proof. — Multiply the row by the corresponding factor Q(a). The new determinant is an alternating function in a_{1}, …,a_{m+n+1},z of degree ≤ n+m in each letter. Being divisible by the Vandermonde in 𝔸 + z, it must be null

The expansion of the preceeding determinant is of the type

For example, for f(z) = (1 + 2z)(1 + 3z)/(1 + z) and 𝔸 = {0,1,2,3}, one has the determinant

| \begin{matrix}1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 6 & 6 \\ 1 & 2 & 4 & 70/3 & 35/3 \\ 1 & 3 & 9 & 105/2 & 35/2 \\ Q & zQ & z^{2}Q & zP & P \end{matrix} |

the nullity of which is equivalent to

(1 + z)P = (1 + 2z)(1 + 3z)Q .

One can take a different view of rational interpolation: instead of finding the numerator and denominator of a rational function from sufficiently many of its values, one looks for a rational approximation of an analytic function

f(z) = 1 + zf_{1} + z^{2}f_{2} + z^{3}f_{3} + ⋯,

i.e. one looks for a rational function g(z) = ∏(1 − zb)/ ∏(1 − za), whose development in the neighbourhood of z = 0 coincide with the development of f up to a certain power of z.

In other words, the first coefficients of f are equal to the complete functions S_{j}(𝔸 − 𝔹), and one has to find back the rational function g(z) from its development in the neighbourhood of z = 0.

Puting x = 1/z, card(𝔸) = m, card(𝔹) = n, one can write g(z) = x^{m−n}R(x,𝔹)/R(x,𝔸), and transform this expression by multiplying both numerator and denominator by the factor R(𝔸,𝔹) :

g(1/x) = ±x^{m−n}R(𝔸 + x,𝔹) / R(𝔹 + x,𝔸)

In other terms, the rational function is the quotient of two resultants. This is fortunate, because resultants can be written as special Schur functions and one has many determinantal expressions of them.

This gives without computation many expressions that one could find in the flourishing 19th century litterature.

For example Sylvester gives

(Rt4)  ±x^{n−m}g(1/x) = S_{n^{m+1}}(𝔸 + x − 𝔹)/S_{m^{n+1}}(𝔸 − 𝔹 − x) ,

while Jacobi proposes

(Rt5) ±x^{n−m}g(1/x) = S_{n,n^{m}}(𝔸 + x − 𝔹,𝔸 − 𝔹)/S_{m^{n+1},0}(𝔸 − 𝔹,x)

One could also exchange the rôles of 𝔸 and 𝔹, or transforms the determinants by linear combination of rows and columns.

For example, for m = 3, n = 2, writing ℂ for 𝔸 − 𝔹, one has

−g(x)/x = | \begin{matrix}S_{2}(x + ℂ) & S_{3}(x + ℂ) & S_{4}(x + ℂ) & S_{5}(x + ℂ) \\ S_{1}(x + ℂ) & S_{2}(x + ℂ) & S_{3}(x + ℂ) & S_{4}(x + ℂ) \\ S_{0}(x + ℂ) & S_{1}(x + ℂ) & S_{2}(x + ℂ) & S_{3}(x + ℂ) \\ 0 & S_{0}(x + ℂ) & S_{1}(x + ℂ) & S_{2}(x + ℂ) \end{matrix} | /

/ | \begin{matrix}S_{3}(ℂ − x) & S_{4}(ℂ − x) & S_{5}(ℂ − x) \\ S_{2}(ℂ − x) & S_{3}(ℂ − x) & S_{4}(ℂ − x) \\ S_{1}(ℂ − x) & S_{2}(ℂ − x) & S_{3}(ℂ − x) \end{matrix} |

= | \begin{matrix}S_{2}(x + ℂ) & S_{3}(ℂ) & S_{4}(ℂ) & S_{5}(ℂ) \\ S_{1}(x + ℂ) & S_{2}(ℂ) & S_{3}(ℂ) & S_{4}(ℂ) \\ S_{0}(x + ℂ) & S_{1}(ℂ) & S_{2}(ℂ) & S_{3}(ℂ) \\ 0 & S_{0}(ℂ) & S_{1}(ℂ) & S_{2}(ℂ) \end{matrix} | / | \begin{matrix}S_{3}(ℂ) & S_{4}(ℂ) & S_{5}(ℂ) & x^{3} \\ S_{2}(ℂ) & S_{3}(ℂ) & S_{4}(ℂ) & x^{2} \\ S_{1}(ℂ) & S_{2}(ℂ) & S_{3}(ℂ) & x^{1} \\ S_{0}(ℂ) & S_{1}(ℂ) & S_{2}(ℂ) & x^{0} \end{matrix} |

The above expressions degenerate when the extra factor R(𝔸,𝔹) = S_{n^{m}}(𝔸 − 𝔹) is null, i.e. when the determinant

| \begin{matrix}f_{n} & ⋯ & f_{m+n−1} \\ ⋮ & & ⋮ \\ f_{m−n+1} & ⋯ & f_{m} \end{matrix} |

is null.

Qestions of convergence and algorithms to compute by recursion the different determinants corresponding to variable m and n have been studied by Padé in his thesis, and have generated a numerous litterature which has not much relations with our algebraic manipulations.

Rational interpolation mostly reduces to using different determinantal expressions of the resultant R(𝔸,𝔹) coming from the fact that it is a special Schur function.

Newton interpolation

Newton’s approach to interpolation is different from Lagrange’s. Interpolation points are totally ordered, and adding a new interpolation point has the effect of adding an extra term to the interpolation polynomial. As for Lagrange interpolation, we have to interpret Newton’s interpolation as an identity on polynomials.

Given an infinite totally ordered alphabet 𝔸, recall that 𝔸_{n} is the subinitial alphabet 𝔸_{n} := {a_{1}, …,a_{n}}. Because {1, R(x,𝔸_{1}), R(x,𝔸_{2}), …} is a linear basis of polynomials (triangulary equivalent to {1,x,x^{2}, …}), we can expand any polynomial f(x) in this basis :

(Ni1) f(x) = f(a_{1}) + f^{∂}R(x,𝔸_{1}) + f^{∂∂}R(x,𝔸_{2}) + f^{∂∂∂}R(x,𝔸_{3}) + ⋯,

the coefficients f,f^{∂},f^{∂∂}, … being uniquely determined.

Taking x = a_{1}, x = a_{2}, x = a_{3}, …, we can easily identify the first of them :

f^{∂} = (f(a_{1}) − f(a_{2}))/(a_{1} − a_{2}) ,

f^{∂∂} = (f(a_{1})−f(a_{2}))/(a_{1}−a_{2})(a_{2}−a_{3})−(f(a_{1})−f(a_{3}))/(a_{1}−a_{3})(a_{2}−a_{3}), …

and infer that f^{∂...∂} is the image of f(a_{1}) under a product of successive divided differences ∂_{1},∂_{2},∂_{3}, … acting on their left.

Thus one is led to Newtons’s formula : (Ni2) f(x) = f(a_{1}) + f∂_{1} R(x,𝔸_{1}) + f∂_{1}∂_{2} R(x,𝔸_{2}) + f∂_{1}∂_{2}∂_{3} R(x,𝔸_{3}) + ⋯

It is sufficient to prove this formula for a linear basis of polynomials, for example the polynomials 1, R(x,𝔹_{1}), R(x − 𝔹_{2}), … associated to another infinite alphabet 𝔹. Because the action of divided differences on complete functions is easy, remembering that R(x,𝔹_{k}) can be written S_{k}(x − 𝔹_{k}), we have to prove all the identities, for k = 0,1,2 …

(Ni3) S_{k}(x − 𝔹_{k}) = S_{k}(𝔸_{1} − 𝔹_{k}) + S_{k−1}(𝔸_{2} − 𝔹_{k}) R(x,𝔸_{1})
+S_{k−2}(𝔸_{3} − 𝔹_{k}) R(x,𝔸_{2}) + ⋯ + S_{0}(𝔸_{k} − 𝔹_{k})R(x,𝔸_{k})

But now, we could have taken any 𝔹 to have a linear basis of polynomials, for example 𝔹 = 𝔸.

In this case every S_{k−j+1}(𝔸_{j} −𝔸_{k}), j < k, is null, because it is, up to a sign, the k − j + 1 elementary symmetric function of an alphabet (= 𝔸_{k} \ 𝔸_{j}) of cardinal k−j. The above summation reduces to R(x−𝔸_{k}) = S_{0}()R(x−𝔸_{k})

Newton’s formula is closely connected with a discrete analog of the Wronskian, and could be checked using it.

Indeed, given n one variable-functions f_{i}, we define their 𝔸-Wronskian to be

(Ni4)  W_{𝔸}(f_{1}, …,f_{n}) := det | f_{i}∂_{1} ⋯ ∂_{j−1} |_{1≤i,j≤n}

LEMMA (Ni5). — The 𝔸-Wronskian of n functions f_{1}, …,f_{n} is equal to the quotient det |f_{i}(a_{j})| / Δ(𝔸).

It is also equal to the determinant

det |f_{i} ∂_{1} ⋯ ∂_{j−1}π_{j} ⋯ π_{n−1}| .

Proof. — Replace each f(a_{j}) by its Newton’s expansion: f(a_{j}) = f(a_{1}) + ⋯ + f∂_{1} ⋯ ∂_{j−1} R(a_{j},𝔸_{j−1}). Then we see that the determinant has rows equal to linear combinations of the rows of the Wronskian,

row_{j} = row_{1} + row_{2} R(a_{j},𝔸_{1}) + ⋯ + row_{j} R(a_{j},𝔸_{j−1}) .

Therefore, the two determinants coincide, up to the factor

R(a_{2},𝔸_{1})R(a_{3},𝔸_{2}) ⋯ R(a_{n},𝔸_{n−1}) = Δ(𝔸) .

Because det|f_{i}(a_{j})|/Δ(𝔸) is a symmetric function, one does not change the value of the Wronskian by taking its image under

π_{ω} = (π_{n−1})(π_{n−2}π_{n−1}) ⋯ (π_{1} ⋯ π_{n−1}) .

Now, the Wronskian has been written as a determinant such that the entries in the successive rows are symmetric functions of 𝔸_{1}, 𝔸_{2}, …,𝔸_{n} respectively. The operator π_{n−1} operates non trivially only on row n−1, then the operator π_{n−2}π_{n−1} operates on row n − 2 of the new determinant, and finally the image of the Wronskian under π_{ω} is the determinant where each of the operators (π_{n−1}), (π_{n−2}π_{n−1}), … (π_{1} ⋯ π_{n−1}) have been applied to the appropriate row. The entries of the final determinant are now symmetric functions in 𝔸

In the special case where all the functions f_{j} are powers of a variable, we see that the Wronskian interpolates between the expression of a Schur function as a determinant of complete functions, and as a quotient of determinant of powers by the Vandermonde. For example, with 𝔸 of cardinal 3, one has

W_{𝔸}(x^{2},x^{5},x^{9}) = | \begin{matrix}S_{2}(𝔸_{1}) & S_{5}(𝔸_{1}) & S_{9}(𝔸_{1}) \\ S_{1}(𝔸_{2}) & S_{4}(𝔸_{2}) & S_{8}(𝔸_{2}) \\ S_{0}(𝔸_{3}) & S_{3}(𝔸_{3}) & S_{7}(𝔸_{3}) \end{matrix} | = | \begin{matrix}a_{1}^{2} & a_{1}^{5} & a_{1}^{9} \\ a_{2}^{2} & a_{2}^{5} & a_{2}^{9} \\ a_{3}^{2} & a_{3}^{5} & a_{3}^{9} \end{matrix} | / Δ(𝔸) =

| \begin{matrix}a_{1}^{2}π_{1}π_{2} & a_{1}^{5}π_{1}π_{2} & a_{1}^{9}π_{1}π_{2} \\ S_{1}(𝔸_{2})π_{2} & S_{4}(𝔸_{2})π_{2} & S_{8}(𝔸_{2})π_{2} \\ S_{0}(𝔸_{3}) & S_{3}(𝔸_{3}) & S_{7}(𝔸_{3}) \end{matrix} | = | \begin{matrix}S_{2}(𝔸) & S_{5}(𝔸) & S_{9}(𝔸) \\ S_{1}(𝔸) & S_{4}(𝔸) & S_{8}(𝔸) \\ S_{0}(𝔸) & S_{3}(𝔸) & S_{7}(𝔸) \end{matrix} |

Given {a_{1},a_{2}, …}, Newton interpolation develops any polynomial f(x) in the basis {(x − a_{1}) ⋯ (x − a_{k})}; the coefficients are obtained by applying divided differences on f.

Newton interpolation in several variables

A linear basis of the ring of polynomials in an alphabet 𝔸 allows to expand any polynomial in 𝔸, as we did for polynomials in one variable. It is reasonable to ask that this basis contains Newton’s polynomials R(a_{1},𝔹_{k}), and has simple vanishing properties.

One may also start from the images of a polynomial in 𝔸 under divided differences, evaluated in a second alphabet 𝔹. It is easy to see that the divided differences ∂_{μ}, for all permutations μ, are linearly independent, and therefore there exist universal coefficients in 𝔸,𝔹 which generalize Newton’s polynomials, and allow the expansion of any polynomial f in terms of its images under all the divided differences.

We shall define recursively these polynomials. Let ℕ^{∞} denote the linear space of infinite integral vectors with only a finite numbers of non zero components. To each I ∈ ℕ^{∞}, M.P. Schützenberger and I have attached a Schubert polynomial Y_{I}.

We first define dominant Schubert polynomials corresponding to dominant weights. For K ∈ ℕ^{∞}, K weakly decreasing, i.e. K = k_{1} ≥ k_{2} ≥ k_{3} ≥ ⋯ 0 0 ⋯, let Y_{K} be

(Nis1)  Y_{K} := ∏_{(i,j)} (a_{i} − b_{j}) ,

product on all points (i,j) of the Ferrers’ diagram of K.

For example

Y_{221100...} = \begin{matrix}(a_{1} − b_{2}) & (a_{2} − b_{2}) \\ (a_{1} − b_{1}) & (a_{2} − b_{1}) & (a_{3} − b_{1}) & (a_{4} − b_{1}) \end{matrix} ,

where the above planar display stands for the product of its entries. Definition. — Schubert polynomials are all the non-zero images of dominant Schubert polynomials under divided differences.

We index Schubert polynomials according to the following reordering rules:

given p ≥ 0 and I ∈ ℕ^{∞}, write i,j for the p and p + 1-th components of I. Then,

i > j ⇒ Y_{...i j...} ∂_{p} = Y_{...j i−1...}

On the other hand, the nullity ∂_{p}^{2} = 0 implies that

i ≤ j ⇒ Y_{...i j...} ∂_{p} = 0 .

Note that the same Y_{I} can be obtained in several manners from dominants Y_{K}.We shall skip for the moment the proof that braid relations imply that the polynomials Y_{I} are uniquely determined by the above recursions (see also exercice ?).

When K is decreasing, the dominant Schubert polynomial Y_{K} can be written as a Schur function. Indeed, thanks to (Sf7), for K = k_{1} ≥ k_{2} ≥ ⋯ ≥ k_{n} ≥ 00 …, writing K^{ω} = k_{n} … k_{1}, one has

(Nis2)  Y_{K} = S_{K^{ω}}(𝔸_{n} − 𝔹_{k_{n}}, …,𝔸_{1} − 𝔹_{k_{1}}) .

For example,

Y_{22110...} = S_{1122}(𝔸_{4} − 𝔹_{1},𝔸_{3} − 𝔹_{1},𝔸_{2} − 𝔹_{2},𝔸_{1} − 𝔹_{2}) =

= | \begin{matrix}S_{1}(𝔸_{4} − 𝔹_{1}) & S_{2}(𝔸_{3} − 𝔹_{1}) & S_{4}(𝔸_{2} − 𝔹_{2}) & S_{5}(𝔸_{1} − 𝔹_{2}) \\ S_{0}(𝔸_{4} − 𝔹_{1}) & S_{1}(𝔸_{3} − 𝔹_{1}) & S_{3}(𝔸_{2} − 𝔹_{2}) & S_{4}(𝔸_{1} − 𝔹_{2}) \\ 0 & S_{0}(𝔸_{3} − 𝔹_{1}) & S_{2}(𝔸_{2} − 𝔹_{2}) & S_{3}(𝔸_{1} − 𝔹_{2}) \\ 0 & 0 & S_{1}(𝔸_{2} − 𝔹_{2}) & S_{2}(𝔸_{1} − 𝔹_{2}) \end{matrix} | .

In particular, Y_{00...} = 1.

It is clear that all specializations Y_{K}(𝔸,𝔸), K ≠ 0 decreasing, are null. We shall need more generally that all Y_{I}(𝔸,𝔸) are null, apart from Y_{00...}. Stronger vanishing properties will be proved in the next sections (see also exercice ?).

We also need that the Y_{I} are linearly independent, this coming from the fact that their leading monomial (for the lexicographic order from the right) is equal to a^{I} = a_{1}^{I_{1}} a_{2}^{I_{2}} a_{3}^{I_{3}} ⋯

For I ∈ ℕ^{n}, write I = Jk, J ∈ ℕ^{n−1}, k = I_{n}, and define recursively ∂_{[I]} as the product

∂_{n} ⋯ ∂_{n+k−1} ∂_{[J]} .

It is clear by induction on n that ∂_{[I]} sends Y_{I0...} to Y_{00...} and all other Schubert polynomials to 0 or another Schubert polynomial ≠ Y_{00...}, because the action of a simple divided difference consists into reordering the subscript or annihilating the polynomial.

For example,

I = 412 ⇒ ∂_{[412]} = ∂_{3}∂_{4} ∂_{[41]} = (∂_{3}∂_{4})(∂_{2})(∂_{1}∂_{2}∂_{3}∂_{4}) .
Y_{412} ∂_{[412]} = Y_{412} ∂_{3}∂_{4}∂_{[41]} = Y_{41000} ∂_{[41]} = Y_{00...}

and more generally,

Y_{ijh}∂_{[412]} = Y_{ijh} ∂_{3}∂_{4}∂_{[41]} = Y_{ij00 h−2} ∂_{[41]} or 0 if h < 2,
= Y_{i 0 j−1 0 h−2} ∂_{1}∂_{2}∂_{3}∂_{4} or 0 if j = 0
Y_{0 i−1 j−1 0 h−2} ∂_{2}∂_{3}∂_{4} = Y_{0 j−1 i−2 0 h−2} ∂_{3}∂_{4} or 0 if i ≤ j or i < 2

= Y_{0 j−1 0 i−3 h−2} ∂_{4} = Y_{0 j−1 0 h−2 i−4} or 0 if i < 4 or i − 3 ≤ h − 2 .

Finally, the image of Y_{ijh} is a Schubert polynomial iff

i ≥ 4, j ≥ 1, h ≥ 2, i ≥ h + 2, i ≥ j + 1 and 0 otherwise .

It is remarkable that the above simple properties are sufficient to obtain the multi-variables generalisation of Newton’s formula.

THEOREM (Nis3). — Let 𝔸 and 𝔹 be two infinite alphabets. Then for any polynomial f(𝔸) in Pol(𝔸) , one has

f(𝔸) = ∑_{I} f∂_{[I]}(𝔹) Y_{I}(𝔸,𝔹) ,

where ∂_{[I]} is the divided difference (acting only on 𝔸) which sends Y_{I} onto Y_{00...} = 1, and where the sum is over all I ∈ ℕ^{∞}.

Proof. — It is sufficient to check the theorem on a linear basis of the polynomials in 𝔸, which can involve the elements of 𝔹 which are scalars for the divided differences in 𝔸. Thus we choose the Y_{J}(𝔸,𝔹) as a linear basis. Now images of Y_{I} under divided differences are either 0 or other Schubert polynomials, which specialize to 0 when 𝔸 = 𝔹, except for Y_{00...}. Thus, Newton’s formula, in the case of the polynomial f(𝔸) = Y_{J} reduces to the irrefutable identity

Y_{J}(𝔸,𝔹) = Y_{00...} Y_{J}(𝔸,𝔹)

For example, writing f∂ ⋯ ∂ for f∂ ⋯ ∂ (𝔹), and Y_{I} for Y_{I}(𝔸,𝔹), the interpolation of f := a_{1}^{3}a_{2} is

f = f Y_{0,0,0,0} + f∂_{2} Y_{0,1,0,0} + f∂_{1} Y_{1,0,0,0} + f∂_{1}∂_{2} Y_{2,0,0,0} + f∂_{2}∂_{1} Y_{1,1,0,0} +f∂_{1}∂_{2}∂_{3} Y_{3,0,0,0} + f∂_{2}∂_{1}∂_{2} Y_{2,1,0,0}f∂_{2}∂_{1}∂_{2}∂_{3} Y_{3,1,0,0} ,

that is

a_{1}^{3}a_{2} = b_{1}^{3}b_{2} Y_{0,0,0,0}+b_{1}^{3} Y_{0,1,0,0}+(b_{1}^{2}+b_{1}b_{2}+b_{2}^{2}) Y_{1,0,0,0}+(b_{1}^{2}+b_{1}b_{2}+b_{1}b_{3}) Y_{2,0,0,0}

+(b_{1}^{2} + b_{1}b_{2} + b_{2}^{2}) Y_{1,1,0,0} + b_{1} Y_{3,0,0,0} + (b_{1} + b_{2} + b_{3}) Y_{2,1,0,0} + Y_{3,1,0,0} .

The generalization of Lagrange interpolation to functions of several variables is no more complicated. Fix n sufficiently big (the ”order of interpolation”), and let X_{ω} be the polynomial

X_{ω}(𝔸,𝔹) := Y_{n−1cdots210} = ∏_{i+j≤n}(a_{i} − b_{j}) .

The vanishing properties that we need are this time :

LEMMA (Nis4). — For any μ ∈ 𝔖(n), all the X_{ω}(𝔸,𝔸^{μ}) are null, except for μ = ω = (n, …,1), in which case

X_{ω}(𝔸,𝔸^{ω}) = Δ(𝔸) := ∏_{i<j≤n}(a_{i} − a_{j}) .

Proof. — If X_{ω}(𝔸,𝔸^{μ}) ≠ 0, then b_{1} has to be specialized to a_{n}; this leaves only the value a_{n−1} for b_{2}, &c.

THEOREM (Nis5). — Let 𝔸 be an infinite alphabet, f(a_{1},a_{2}, …) a polynomial in 𝔸, and n ∈ ℕ be such that all the exponents I of the monomials appearing in f are (componentwise) majorized by (n − 1, …,1,0). Let 𝔹 be an alphabet of cardinal n. Then

f(𝔸) = ∑_{μ∈𝔖(𝔹)} f(𝔹^{μ}) X_{ω}(𝔸,𝔹^{ωμ})/Δ(𝔹^{μ}) .

Proof.—Foranypermutationν ∈ 𝔖(𝔹),thespecialization{a_{1}, …,a_{n}} = 𝔹^{ν} reduces the theorem to the identity

f(𝔹^{ν}) = f(𝔹^{ν}) X_{ω}(𝔹^{ν}, 𝔹^{ων} /Δ(𝔹^{ν}) .

These n! equations on f determine f and force the equality for general 𝔸

Forexample,forn = 3,onehasforallpolynomialsofthetypef = ∑_{I} c_{I}a^{I}, with I ≤ (2,1,0)

f(a_{1},a_{2},a_{3}) = \frac{1}{(b_{1} − b_{2})(b_{1} − b_{3})(b_{2} − b_{3})}(−f(b_{1},b_{2},b_{3})(b_{2}−a_{1})(b_{3}−a_{2})(b_{3}−a_{1})

+f(b_{1},b_{3},b_{2})(b_{3}−a_{1})(b_{2}−a_{2})(b_{2}−a_{1})−f(b_{3},b_{1},b_{2})(b_{1}−a_{1})(b_{2}−a_{2})(b_{2}−a_{1}) +f(b_{2},b_{1},b_{3})(b_{1}−a_{1})(b_{3}−a_{2})(b_{3}−a_{1})−f(b_{2},b_{3},b_{1})(b_{3}−a_{1})(b_{1}−a_{2})(b_{1}−a_{1})

+f(b_{3},b_{2},b_{1})(b_{2} − a_{1})(b_{1} − a_{2})(b_{1} − a_{1}))

Dominantpolynomialsarecertainproductsofthetype∏(a_{i}−b_{j}). Their images Y_{I}(𝔸,𝔹), I ∈ ℕ^{∞}, are called Schubert polynomials. The vanishing properties Y_{I}(𝔸,𝔸) = 0, for I ≠ 0, imply that any polynomial f(𝔸) decomposes onto the Schubert basis, the coefficients being the images of f under divided differences.

Interpolation of symmetric functions

One can use Newton’s formula to interpolate symmetric functions. Let f(𝔸_{n}) be a function symmetrical in {a_{1}, …,a_{n}}. According to the preceeding theorem, one can write this function

(Isf1)  f(𝔸_{n}) = ∑_{I} c_{I}Y_{I} .

I claim that all the I corresponding to non zero coefficients c_{I} are of the type

I = 0 ≤ i_{1} ≤ i_{2} ⋯ ≤ i_{n} 0 0 …

Indeed, f(𝔸_{n}) depending only on a_{1}, …,a_{n} is annihilated by all ∂_{k}, with k > n. Similarly, being symmetrical in a_{1}, …,a_{n}, it is also annihilated by ∂_{1}, …,∂_{n−1}.

Therefore, all the Schubert polynomials appearing on the right side must be annihilated by the same divided differences, because otherwise we would have a sum of Schubert polynomials equal to 0. This is equivalent to say that I can have only the decrease … i_{n} 0 …

Let us take for example a symmetric function of two variables, say Y_{25}(𝔸,ℂ), where ℂ is another infinite alphabet. Write Y_{I}Y_{J} for the product Y_{I}(𝔹,ℂ)Y_{J}(𝔸,𝔹). Then formula (Isf1) reads

Y_{25}(𝔸,ℂ) = Y_{25}Y_{00} + Y_{204}Y_{01} + Y_{014}Y_{11} + Y_{2003}Y_{02} + Y_{0103}Y_{12} + Y_{20002}Y_{03} + Y_{0003}Y_{22} + Y_{01002}Y_{13} + Y_{200001}Y_{04} +Y_{00002}Y_{23}+Y_{010001}Y_{14}+Y_{200000}Y_{05}+Y_{000001}Y_{24}+Y_{010000}Y_{15}+Y_{000000}Y_{25}.

In the case 𝔹 = 0, the above expansion expresses the Schubert polynomial Y_{25}(𝔸,ℂ) as a linear combination of all the Schur functions S_{I}(a_{1} + a_{2}) = Y_{I}(𝔸,0), I ⊆ 25.

The symmetrical Schubert polynomials Y_{I}(𝔸,𝔹) are a natural generalization of Schur functions : the leading term of Y_{I}(𝔸,𝔹) (i.e. term of higher degree in 𝔸) is the Schur function S_{I}(𝔸_{n}) = Y_{I}(𝔸,0), and can be written as determinants.

Indeed,letI = i_{1} ≤ ⋯ ≤ i_{n},andK = I^{ω}+ρ := i_{n}+n−1, …, i_{2}+1,i_{1}+0. Then, still writing 𝔹_{k} for {b_{1}, …,b_{k}}, one has, according to (Sf11)

Y_{K} = R(a_{n},𝔹_{k_{1}}) ⋯ R(a_{1},𝔹_{k_{n}}) = S_{K^{ω}}(𝔸_{n} − 𝔹_{k_{1}}, …,𝔸_{1} − 𝔹_{k_{n}}) .

The image of Y_{K} under ∂_{ω}, with ω = n ⋯ 1, is by definition Y_{I}, but thanks to (So16), it is also equal to

(Isf2)  Y_{I} = S_{I}(𝔸_{n} − 𝔹_{k_{1}}, …,𝔸_{n} − 𝔹_{k_{n}}) ,

the leading term being evidently the Schur function S_{I}(𝔸_{n}). It is a special case of the determinant used in [L1].

Expression (So7) shows that ∂_{ω}(Y_{K}) can be written as the quotient

(Isf3)  Y_{I} = |R(a,𝔹_{k_{1}}), …, R(a,𝔹_{k_{n}})|_{a∈𝔸_{n}} / Δ(𝔸_{n}) ,

i.e.

(Isf4)  Y_{I} = ∑_{μ} (−1)^{ℓ(μ)}(R(a_{1},𝔹_{k_{1}}) ⋯ R(a_{n},𝔹_{k_{n}}))^{μ} / Δ(𝔸_{n}) .

If I has repeated components, one can reduce the preceeding summation to a subset of the symmetric group.

For example, for any m ≥ 0, let r = m + n − 1; then

Y_{0^{n−1}m} = Y_{r 00...}∂_{1} ⋯ ∂_{n−1} = L_{𝔸_{n}}(R(a_{1},𝔹_{r})) .

Now Leibniz formula expresses the image of R(a_{1},𝔹_{r}) as a summation of products ∏(a_{i} − b_{j}).

This can be visualized as follows. A string of boxes, some of them occupied by a •, means a product of linear factors according to the following recepee : ” in an empty box at position j, put the factor a_{i} − b_{j}, where i − 1 is equal to the number of dots on the left of the box. Finally erase the •’s.”

For example,

• • • = (a_{1} − b_{1})(a_{1} − b_{2}) (a_{3} − b_{5}) (a_{4} − b_{7}) .

Now Y_{r} is equal to a string of r boxes. Its image under ∂_{1} is equal to the sum of all strings with one dot,

Y_{0 r−1} = ∑ … • ….

The next step, using ∂_{2}, puts one dot in a box right of the existing dot, and thus Y_{0 0 r−2} is the sum of all strings of length r with two dots :

Y_{00 r−2} = ∑ … • … • ….

Finally, Y_{0^{n−1}m} is equal to the sum of all strings of r boxes with n − 1 dots. In other words, (Isf5) Y_{0^{n−1}m} = ∑(a_{1}−b_{1}) ⋯ (a_{1}−b_{i}) (a_{2}−b_{i+2}) ⋯ (a_{2}−b_{j}) ⋯ (a_{n}−b_{h}) ⋯ (a_{n}−b_{r}).

Suppressing the void boxes, one could also write this summation as attached to a diagram of m boxes, with shifts in the indices of the b’s given by the contents of the boxes. For more general diagrams, with 𝔹 = {0,1,2, …}, this construction is due to Biedenharn-Louck.

Indeed, ”Stirling interpolation” 𝔹 = ℕ := {0,1,2, …} of symmetric functions involves the specialisation of Schubert polynomials Y_{I}(𝔸,ℕ), I = i_{1} ≤ ⋯ ≤ i_{n}, which are the factorial Schur functions of Biedenharn and Louck.

In that case, R(a,ℕ_{n}) = a(a − 1) ⋯ (a − n + 1) may be considered as a polarization of the nth-power and may be conveniently represented by the symbol a^{[n]}. Identity (Isf3) reads now

(Isf6)  Y_{I}(𝔸,ℕ) = |a^{[k_{1}]}, …, a^{[k_{n}]}|_{a∈𝔸_{n}} / Δ(𝔸_{n}) ,

while (Isf5) becomes (Isf7) Y_{0^{n−1}m} = ∑(a_{1}) ⋯ (a_{1}−i) (a_{2}−i−2) ⋯ (a_{2}−j) ⋯ (a_{n}−h) ⋯ (a_{n}−r+1),

sum on all −1 ≤ i ≤ j ≤ ⋯ ≤ h ≤ r.

Expression (Isf6) proves that factorial Schur functions can be characterized by their vanishing properties, as noticed by Okounkov. They are essential in the study of central elements in the universal envelopping algebra 𝔘(𝔊𝔩(𝔫)) (Olshanski, Okounkov,Nazarov, Molev).

One can add that factorial Schur functions can also be obtained as specializations of some Schubert polynomials in 𝔸 = {1,1,1 …} and 𝔹 = {0,0,0 …}, the variables being now the components of the index I (and thus taking only integral values, but this sufficient to determine them). This leads to the theory of binomial determinants, as a part of bijective combinatorics so notoriously illustrated by our friend Xavier Viennot.

The relevant properties of factorial Schur functions are now related to dimensions of representations of the linear groups or unitary groups, as functions of the components of highest weight vectors.

Some operations on symmetric functions can be explicited using Newton’s interpolation. Let us describe, for example, the uniform translation 𝔸 ⟶ 𝔸^{+} := {a_{1}+1,a_{2}+1, …, a_{n}+1}.Now,divideddifferencesareinvariantunder this translation, and (Isf1) becomes, for any J = j_{1} ≤ j2 ≤ ⋯ ≤ j_{n} 00 …, denoting Y_{J/I} the image of Y_{J} under ∂_{[I]} :

(Isf8)  Y_{J}(𝔸^{+}) = ∑_{I} Y_{J/I}({1, …,1},0, … 0) Y_{J}(𝔸,{0, …,0} .

Newton interpolation of functions symmetrical in a_{1}, …,a_{n}, uses only Schubert polynomials which are symmetrical in a_{1}, …,a_{n} (and have leading term a Schur function). In the case where the interpolation alphabet B is equal to {0,1,2, …}, these special Schubert polynomials are called factorial Schur functions.

The ring of polynomials as a free module over 𝔖𝔶𝔪

We have seen that any polynomial in 𝔸 can be uniquely expanded as a linear combination of Schubert polynomials. We skipped the proof of some simple properties of these polynomials. We are going to reinterpret Newton’s formula, and prove stronger properties that those left unproved.

First, we shall work with a finite alphabet 𝔸 of cardinal n. We shall describe the structure of the ring Pol(𝔸) := ℤ[𝔹][𝔸] of polynomials in 𝔸, with coefficients involving a second alphabet 𝔹 of the same cardinal, as a module over 𝔖𝔶𝔪(𝔸).

We define a quadratic form :

(Rp1)  Pol(𝔸) ∋ f,g ⇒ (f,g) := fg ∂_{ω} ,

where ∂_{ω} is the maximal divided difference relative to 𝔸.

LEMMA (Rp2). — 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 ω = σ_{i} μ. Then (f ∂_{i},g) = (f∂_{i} g ∂_{i})∂_{μ}. Because f ∂_{i} is a scalar for ∂_{i}, the preceeding 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}) .

The code of a permutation μ ∈ 𝔖(n) is the vector c[μ] = [c_{1}, …,c_{n}] such that c_{i} := card(j > i,μ_{j} < μ_{i}). It is immediate that μ ⟶ c[μ] is a bijection between 𝔖(n) and the vectors c ∈ ℕ^{n} such that c ≤ ρ := [n − 1, …,0,1] (i.e. c_{i} ≤ n − i, i = 1, …,n).

The maximal Schubert polynomial X_{ω}(𝔸,𝔹), that we choose to index by the permutation ω (:= n … 1) , is set to be

(Rp3)  X_{ω}(𝔸,𝔹) := ∏_{i+j≤n} (a_{i} − b_{j}) .

For any permutation μ ∈ 𝔖(n), one defines the Schubert polynomial X_{μ} by

(Rp4)  X_{μ}(𝔸,𝔹) := X_{ω}(𝔸,𝔹) ∂_{ωμ}

recalling that divided differences act only the a_{i}’s.

A permutation is sais to be dominant if its code I is dominant, i.e. weakly decreasing. In that case, it is easy to see that there exists at least one sequence of operations of the type

(⋯ j + 1 j ⋯) ⟶ (⋯ j j ⋯)

which leads from ρ to the code I. This means that there exists at least a chain

μ^{0} = ω, μ^{1}, …, μ^{r} = μ

of dominant permutations, together with a sequence of simple transpositions σ^{1}, …,σ^{r}, such that

X_{μ^{j−1}}∂_{σ^{j}} = X_{μ^{j}} , j = 1, …,r .

Supposing that X_{μ^{j−1}} is equal to the polynomial Y_{K} defined in (Nis1), with K = code(μ^{j−1}) = [k_{1}, …,k_{n}], let p be the integer such that σ^{j} = σ_{p}. Now, because k_{p} = k_{p+1} + 1, the polynomial Y_{K} is equal to a polynomial F symmetrical in a_{p},a_{p+1}, multiplied by a single factor (a_{p} − b_{m}), for some m. Thus the image of Y_{K} under ∂_{p} is equal to F, and finally X_{μ^{j}} = F is the dominant polynomial indexed by the code of μ^{j}.

The following property shows that the maximal Schubert polynomial is a ”reproducing kernel”, modulo the identification (that we note by ”≡”) of the symmetric functions in 𝔸 with the same symmetric functions in 𝔹.

PROPOSITION (Rp5). — For any element f ∈ Pol(𝔸), one has

(f(𝔸),X_{ω}(𝔸^{ω},𝔹)) ≡ f(𝔹) ,

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

Proof. — The formula is linear. Writing any monomial as a Schur function (according to (Sf10)) :

S_{ij...hk}(𝔸, 𝔸 − a_{1}, …, 𝔸 − a_{1} − ⋯ − a_{n−2}, 𝔸 − a_{1} − ⋯ − a_{n−1})

we see that the expansion of such a function involves only monomials a^{J} with J ≤ (n − 1, …,1,0) := ρ, as we already have noticed in section 2. In other words, any element of Pol(𝔸) can be written as a linear combination of monomials a^{J} : J ≤ ρ with coefficients in 𝔖𝔶𝔪(𝔸). On the other hand, the expansion of X_{ω}(𝔸^{ω},𝔹) involves only monomials a^{I}: I ≤ (0,1, …,n − 1). Therefore, the product f(𝔸)X_{ω}(𝔸^{ω},𝔹) involves only monomials a^{H}: H ≤ (n − 1, …,n − 1). Such a monomial has a non zero image under ∂_{ω} iff all the exponents are different, i.e. iff the exponent is a permutation of ρ; in this case, the determinant is obtained by permutations of columns from the determinant expressing S_{0...0}(𝔸) and thus is equal to ±1.

In any case, this image is independent of 𝔸. Consequently, taking 𝔸 = 𝔹 in the evaluation of the quadratic form (f(𝔸),X_{ω}(𝔸^{ω},𝔹)) has the only effect of replacing symmetric functions in 𝔸 by the same functions in 𝔹. On the other hand, in the second expression (So7) of the scalar product

(f(𝔸),X_{ω}(𝔸^{ω},𝔹)) = ∑_{μ}(−1)^{ℓ(μ)}f(𝔸^{μ})X_{ω}(𝔸^{ωμ},𝔹) / Δ(𝔸)

there remains only one term under the specialization 𝔸 = 𝔹, that is for μ = identity, the term f(𝔹)X_{ω}(𝔹^{ω},𝔹)/Δ(𝔹) = f(𝔹), as required

More generally, one can obtain divided differences by evaluating scalar products, as shown by the following proposition.

THEOREM (Rp6). — For any element f ∈ Pol(𝔸), any permutation μ, one has

(f(𝔸),X_{μω}(𝔸^{ω},𝔹)) ≡ f ∂_{μ^{−1}} (𝔹)

Proof. — One has

X_{μω}(𝔸^{ω},𝔹) = X_{ω}(𝔸,𝔹) ∂_{ωμω} ω = X_{ω}(𝔸,𝔹)ω (ω∂_{ωμω} ω) = X_{ω}(𝔸,𝔹) ω ∂_{μ} ,

and one can shift the divided difference ∂_{μ} to the left of ( ,) thanks to (Rp2). Now the formula becomes the preceeding one for the function f ∂_{μ^{−1}}

COROLLARY (Rp7). — The quadratic form ( ,) is non-degenerate. The space Pol(𝔸) is a free module over 𝔖𝔶𝔪 with the two adjoint bases {X_{ν}(𝔸,𝔹)} and {X_{νω}(𝔸^{ω},𝔹)}, for all permutations μ,ν in 𝔖𝔶𝔪(𝔸).

More precisely

(X_{ν}(𝔸,𝔹) , X_{μω}(𝔸^{ω},𝔹)) = δ_{μ,ν} .

Having the basis adjoint to the Schubert polynomials, one can now expand any polynomial f in Pol(𝔸) as a linear combination of Schubert polynomials :

(Rp8)  f(𝔸) ≡ ∑_{μ}(f , X_{μω}(𝔸^{ω},𝔹)) X_{μ}(𝔸,𝔹)

= ∑_{μ} f ∂_{μ^{−1}}(𝔹) X_{μ}(𝔸,𝔹) .

The preceeding formula uses the identification 𝔖𝔶𝔪(𝔸) = 𝔖𝔶𝔪(𝔹). When n is sufficiently big so that f belongs to the space generated by monomials a^{I}, I ≤ (n − 1, …,1,0), then the symmetric functions (f , X_{μω}(𝔸^{ω},𝔹)) are of degree 0 in 𝔸, and thus the formula is exact in that case and coincide with Newton’s interpolation.

One can use (Rp8) to develop a Schubert polynomial itself. The following formula is a generalization of the expansion of the resultant R(𝔸,𝔹) as a sum of products ±S_{I}(𝔸)S_{I′}(𝔹) due to Cauchy.

THEOREM (Rp9). — Let 𝔸,𝔹,ℂ be three alphabets of cardinal n, and let ζ ∈ 𝔖(n). Then

X_{ζ}(𝔸,ℂ) = ∑_{μ,η} X_{μ}(𝔸,𝔹) X_{η}(𝔹,ℂ) ,

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

Proof. — To have the non nullity of X_{ζ}∂_{η^{−1}} is the same as to require that the product (ζη^{−1})(η) be reduced. Taking into account that X_{ζ}(𝔸,ℂ) belong to the span of monomials in 𝔸 of degree ≤ ρ, the theorem follows from (Rp8)

All the operators that we have used are linear combinations of permutations, with coefficients which are rational functions of the a_{i}’s.

For example,

∂_{1} = \frac{1}{a_{1} − a_{2}} − σ_{1} \frac{1}{a_{1} − a_{2}}

∂_{1}∂_{2} = (\frac{1}{a_{1} − a_{2}} − σ_{1} \frac{1}{a_{1} − a_{2}} )(\frac{1}{a_{2} − a_{3}} − σ_{2} \frac{1}{a_{2} − a_{3}} )

= (1 − σ_{1})\frac{1}{(a_{1} − a_{2})(a_{2} − a_{3})} + (1 − σ_{2})\frac{1}{(a_{1} − a_{3})(a_{2} − a_{3})}

All the computations shown in these notes could be performed in the algebra of the symmetric group with rational coefficients in 𝔸. Let us call this algebra the algebra of divided differences, not to confuse it with the group algebra with constant coefficients. In it we have to use the commutations relations (P denoting the operation ”multiplication by P ”) :

\{ \begin{matrix}P ∂_{i} & = & (P ∂_{i}) + ∂_{i} P^{σ_{i}} \\ P σ_{i} & = & σ_{i} P^{σ_{i}} \end{matrix}

The next proposition shows that we already know how to pass from permutations to divided differences, and conversely.

PROPOSITION (Rp10). — Let 𝔸 = {a_{1}, …,a_{n}}, Δ := ∏_{i<j}(a_{i} − a_{j}). then for any μ ∈ 𝔖(𝔸), one has

\{ \begin{matrix}μ & = & ∑ν & ∂_{ν} & X_{ν^{−1}}(𝔸^{μ}𝔸) \\ ∂_{μ} & = & ∑ν & ν & X_{ωμ}(𝔸,𝔸^{ων}) \end{matrix}

Proof. — Newton’s interpolation (Rp8) states that for any polynomial f, any μ, one has

f(𝔸^{μ}) ≡ f∂_{ν}(𝔹) X_{ν^{−1}}(𝔸^{μ},𝔹) .

The left side can be interpreted as the operator f(𝔸) ⟶ f(𝔸^{μ}), that is μ, while the right side, where, of course, we can put 𝔸 = 𝔹 because it does not affect the left side, is the operator ∑ ∂_{ν}X_{ν^{−1}}(𝔸^{μ}𝔸). This is exactly the first part of the claim.

Similarly, (Rp6) states that f∂_{μ}, evaluated in B, is congruent to ∑ f(𝔸^{ν})X_{μ^{−1}ω}(𝔸^{ων},𝔹)/Δ(𝔸^{ν}), and this is, for 𝔸 = 𝔹, the second part of the claim, taking into account that

X_{ν}(𝔸,,𝔹) = (−1)^{ℓ(ν)}X_{ν^{−1}}(𝔹,𝔸) ,

the sign being swallowed by Δ(𝔸^{ν}) = (−1)^{ℓ(ν)}Δ(𝔸)

For example, for μ = σ_{1}σ_{2}, one has 𝔸^{σ_{1}σ_{2}} = {a_{3},a_{2},a_{1}} := 𝔸′ , and

σ_{1}σ_{2} = 1 + ∂_{1}X_{213}(𝔸′,𝔸) + ∂_{2}X_{132}(𝔸′,𝔸) + ∂_{1}∂_{2}X_{312}(𝔸′,𝔸)

= 1 + ∂_{1}(a_{3} − a_{1}) + ∂_{2}(a_{3} + a_{2} − a_{1} − a_{2}) + ∂_{1}∂_{2}(a_{3} − a_{1})(a_{3} − a_{2}) .

Symmetrically,

∂_{1}∂_{2}Δ = 1X_{213}(𝔸,𝔸^{ω})+σ_{1}X_{213}(𝔸,𝔸^{ωσ_{1}})+σ_{2}X_{213}(𝔸,𝔸^{ωσ_{2}})+σ_{1}σ_{2}X_{213}(𝔸,𝔸^{ωσ_{1}σ_{2}})

= 1(a_{1} − a_{3}) + σ_{1}(a_{1} − a_{3}) + σ_{2}(a_{1} − a_{2}) + σ_{1}σ_{2}(a_{1} − a_{2}) .

Without Schubert polynomials, it would have been more difficult to obtain (Rp10) in the algebra of divided differences (cf. [KK ?]).

Forexample,tocompute∂_{μ},onehastostartfromareduceddecomposition μ = σ_{i}σ_{j} ⋯ σ_{k}, and write accordingly

∂_{μ} = (1 − σ_{i})\frac{1}{a_{i} − a_{i+1}} + (1 − σ_{j})\frac{1}{a_{j} − a_{j+1}} + ⋯ + (1 − σ_{k})\frac{1}{a_{k} − a_{k+1}} .

Now, one has to push all the coefficients either on the right, or on the left according to one’s preferences, and sum all terms σ_{i}^{ε_{1}}σ_{j}^{ε_{2}} ⋯, ε ∈ {0,1}, which are decompositions of the same permutation.

With this method, it is not appearant that the entries of the inverse matrix which expresses the μ in terms of the ∂_{ν} are the same, up to multiplication by Δ and twist of indices. As a by-product however, one gets a relation between Schubert polynomials and the Ehresmann-Bruhat order on the symmetric group.

This order is defined by : ν ≤ μ iff, given an arbitrary reduced decomposition of μ, μ = σ_{i}σ_{j} ⋯, then there exists at least one choice of ε such that σ_{i}^{ε_{1}}σ_{j}^{ε_{2}} ⋯ = ν.

In other words, we have just observed that in the expansion of ∂_{μ} = (1 − σ_{i})\frac{1}{a_{i}−a_{i+1}} + (1 − σ_{j})\frac{1}{a_{j}−a_{j+1}} + ⋯, and of μ = (1 + ∂_{i}(x_{i+1} − x_{i}))(1 + ∂_{j}(x_{j+1} − x_{j}) ⋯, only permutations ν ≤ μ appear.

Comparing with (Rp10), one obtains the implication ⇐ of the following lemma :

LEMMA (Rp11). — For any pair of permutations ν, μ, one has the equivalence

ν ≤ μ ⇔ X_{ν^{−1}}(𝔸^{μ},𝔸) ≠ 0 .

Given two alphabets 𝔸, 𝔹 of cardinal n, the ring K[𝔸], with K = ℤ[𝔸],isafree-moduleover𝔖𝔶𝔪(𝔸).ItsSchubertbasisX_{μ}(𝔸,𝔹) is in bijection with permutations μ in 𝔖(n). The adjoint basis, with respect to the scalar product (f,g) := fg∂_{ω}, is {X_{μω}(𝔸^{ω},𝔹)}.

References

Faa De BRUNO, Théorie de l’élimination, Thèse, Paris (1856). A.L. CAUCHY, Mémoire sur les fonctions alternées et les sommes alternées, Exercices d’analyse et de phys. math. (1841) 151-159. W.Y.C CHEN, J.D. LOUCK, Interpolation for symmetric functions, Adv. in M., 117, (1996) 147-156. W.Y.C CHEN, J.D. LOUCK, The factorial Schur fuunction, preprint C.G.JACOBI,Deeliminationevariabiliseduabusaequationibusalgebraicis, Crelle J., 15 (1836) 101-124. C.G. JACOBI, De functionibus alternantibus earumque divisione .. Crelle J. , (1841) 360-371. C.G. JACOBI, Über die Darstellung einer reihe gegebener werthe durch eine gebrochene rationale function, Crelle J., 30, (1845) 127-156 A.LASCOUX, Puissances extèrieures, déterminants et cycles de Schubert, Bull. Soc. Math. Fr 102 (1974) 161-179 A.LASCOUX,FonctionsdeSchuretGrassmanniennes,ComptesRendus281 (1975) 813 et 851. A.LASCOUX, Classes de Chern d’un produit tensoriel, Comptes Rendus 286 (1978) 385. A.LASCOUX, Classes de Chern des variétés de drapeaux, Comptes Rendus 295 (1982) 393 A.LASCOUX , Inversion des Matrices de Hankel, Linear Algebra and Appl. 129 (1990) 77-102. A.LASCOUX, Polynômes de Schubert, une approche historique, in Colloque de Combinatoire de Montréal (1992), Discrete Maths 139 (1995) 303-317. A.LASCOUX & M.P.SCHÜTZENBERGER, Polynômes de Schubert, Comptes Rendus 294 (1982) 447. A.LASCOUX & M.P.SCHÜTZENBERGER, Structure de Hopfde l’anneau de cohomologie et de l’anneau de Grothendieck d’une variété de drapeaux, Comptes Rendus 295 (1982) 629. A.LASCOUX & M.P.SCHÜTZENBERGER, Symmetry and Flag manifolds, in Invariant Theory, Springer L.N. 996 (1983) 118-144. m A.LASCOUX & M.P.SCHÜTZENBERGER, Interpolation de Newton à plusieurs variables, Séminaire d’Algèbre M.P.Malliavin 1983-84, Springer L.N. 1146 (1985) 161-37.A.LASCOUX&M.P.SCHÜTZENBERGER,FormulaireraisonnédeFonc-tions symétriques, publié par l’Université Paris7 (1985). A.LASCOUX & M.P.SCHÜTZENBERGER, Symmetrization operators on polynomial rings, Funct.Anal.21 (1987) 77-78. A.LASCOUX & M.P.SCHÜTZENBERGER, Algèbre desdifférences divisées, Discrete Maths 99 (1992) 165-179. I.G. MACDONALD, Notes on Schubert Polynomials, Publications du LACIM, Montréal (1991). I.G. MACDONALD, Schur functions: Thèmes et variations, Pub. IRMA, 28^{e} Séminaire Lotharingien de Combinatoire, Strasbourg (1992) 5-39. L.M. MILNE-THOMSON, The caculus of finite differences, MacMillan and Co, London (1933). I. NEWTON, Philosophiae Naturalis Principiae Mathematica, Liber III, London (1687) 481-83. G. ROSENHAIN, Neue Darstellung der Resultante der Elimination von z aus zwei algebraische Gleichungen, Crelle J. 30 (1845) 157-165. J.J. SYLVESTER, On a theory of the syzygetic relations of two rational integral functions, comprising an application to the theory of Sturm’s functions, and that of the greatest algebraical common measure, Phil. Trans. Royal Soc. London CXLIII (1853) 407-458. J.J. SYLVESTER, On a generalization of the Lagrangian theorem of interpolation, Philosophical Magazine, 6 (1853) 374-376.