Using Schubert basis to compute with multivariate polynomials (Q1364323)

In the spirit of Alain Lascoux, the authors propose the use of Schubert polynomials for (certain) computations with polynomials in several variables. The idea comes from situations like doing computations with symmetric functions: There, computations are (usually) not done with monomials, but with a basis adapted to the specific problem that we are dealing with, such as Schur functions, for example. Most of the paper is devoted to survey the background and basic facts about Schubert polynomials. When we regard the complete ring of polynomials in \(x_1,x_2,\dots,x_n\) as a ring over the ring of symmetric polynomials in \(x_1,x_2,\dots,x_n\), then the Schubert polynomials indexed by permutations in \(S_n\) (the symmetric group on \(n\) elements) constitute a linear basis. Similarly, the ring of polynomials in \(x_1,x_2,\dots,x_n\) with coefficients that are polynomials in \(y_1,y_2,\dots,y_n\) has as a linear basis the double Schubert polynomials. In order to use Schubert polynomials efficiently for computations in such rings, one of the first things we need is a rule for multiplying Schubert polynomials. No general formula for multiplying Schubert polynomials has been found yet (in contrast to Schur functions, where we have the Littlewood-Richardson rule). At least, at the very basic level, there is Monk's formula for the multiplication of a Schubert polynomial in \(x_1,x_2,\dots,x_n\) by one of the variables. However, this formula (possibly) involves Schubert polynomials which are indexed by permutations in \(S_{n+1}\) (and not just \(S_n\)). The authors show how to modify the formula so that one obtains, within the ring of polynomials in \(x_1,x_2,\dots,x_n\), regarded as a ring over the symmetric polynomials, expansions consisting of Schubert polynomials indexed by permutations in \(S_n\). A ``Monk's formula'' for double Schubert polynomials is proved as well.