# Schubert Polynomials#

See Wikipedia article Schubert_polynomial and SymmetricFunctions.com. Schubert polynomials are representatives of cohomology classes in flag varieties. In $$n$$ variables, they are indexed by permutations $$w \in S_n$$. They also form a basis for the coinvariant ring of the $$S_n$$ action on $$\ZZ[x_1, x_2, \ldots, x_n]$$.

EXAMPLES:

sage: X = SchubertPolynomialRing(ZZ)
sage: w = [1,2,5,4,3];  # a list representing an element of S_5
sage: X(w)
X[1, 2, 5, 4, 3]

>>> from sage.all import *
>>> X = SchubertPolynomialRing(ZZ)
>>> w = [Integer(1),Integer(2),Integer(5),Integer(4),Integer(3)];  # a list representing an element of S_5
>>> X(w)
X[1, 2, 5, 4, 3]


This can be expanded in terms of polynomial variables:

sage: X(w).expand()
x0^2*x1 + x0*x1^2 + x0^2*x2 + 2*x0*x1*x2 + x1^2*x2
+ x0*x2^2 + x1*x2^2 + x0^2*x3 + x0*x1*x3 + x1^2*x3
+ x0*x2*x3 + x1*x2*x3 + x2^2*x3

>>> from sage.all import *
>>> X(w).expand()
x0^2*x1 + x0*x1^2 + x0^2*x2 + 2*x0*x1*x2 + x1^2*x2
+ x0*x2^2 + x1*x2^2 + x0^2*x3 + x0*x1*x3 + x1^2*x3
+ x0*x2*x3 + x1*x2*x3 + x2^2*x3


We can also convert back from polynomial variables. For example, the longest permutation is a single term. In $$S_5$$, this is the element (in one line notation) $$w_0 = 54321$$:

sage: w0 = [5,4,3,2,1]
sage: R.<x0, x1, x2, x3, x4> = PolynomialRing(ZZ)
sage: Sw0 = X(x0^4*x1^3*x2^2*x3);  Sw0
X[5, 4, 3, 2, 1]

>>> from sage.all import *
>>> w0 = [Integer(5),Integer(4),Integer(3),Integer(2),Integer(1)]
>>> R = PolynomialRing(ZZ, names=('x0', 'x1', 'x2', 'x3', 'x4',)); (x0, x1, x2, x3, x4,) = R._first_ngens(5)
>>> Sw0 = X(x0**Integer(4)*x1**Integer(3)*x2**Integer(2)*x3);  Sw0
X[5, 4, 3, 2, 1]


The polynomials also have the property that if the indexing permutation $$w$$ is multiplied by a simple transposition $$s_i = (i, i+1)$$ such that the length of $$w$$ is more than the length of $$ws_i$$, then the Schubert polynomial of the permutation $$ws_i$$ is computed by applying the divided difference operator divided_difference() to the polynomial indexed by $$w$$. For example, applying the divided difference operator $$\partial_2$$ to the Schubert polynomial $$\mathfrak{S}_{w_0}$$:

sage: Sw0.divided_difference(2)
X[5, 3, 4, 2, 1]

>>> from sage.all import *
>>> Sw0.divided_difference(Integer(2))
X[5, 3, 4, 2, 1]


We can also check the properties listed in Wikipedia article Schubert_polynomial:

sage: X([1,2,3,4,5])  # the identity in one-line notation
X[1]
sage: X([1,3,2,4,5]).expand()  # the transposition swapping 2 and 3
x0 + x1
sage: X([2,4,5,3,1]).expand()
x0^2*x1^2*x2*x3 + x0^2*x1*x2^2*x3 + x0*x1^2*x2^2*x3

sage: w = [4,5,1,2,3]
sage: s = SymmetricFunctions(QQ).schur()
sage: s[3,3].expand(2)
x0^3*x1^3
sage: X(w).expand()
x0^3*x1^3

>>> from sage.all import *
>>> X([Integer(1),Integer(2),Integer(3),Integer(4),Integer(5)])  # the identity in one-line notation
X[1]
>>> X([Integer(1),Integer(3),Integer(2),Integer(4),Integer(5)]).expand()  # the transposition swapping 2 and 3
x0 + x1
>>> X([Integer(2),Integer(4),Integer(5),Integer(3),Integer(1)]).expand()
x0^2*x1^2*x2*x3 + x0^2*x1*x2^2*x3 + x0*x1^2*x2^2*x3

>>> w = [Integer(4),Integer(5),Integer(1),Integer(2),Integer(3)]
>>> s = SymmetricFunctions(QQ).schur()
>>> s[Integer(3),Integer(3)].expand(Integer(2))
x0^3*x1^3
>>> X(w).expand()
x0^3*x1^3

sage.combinat.schubert_polynomial.SchubertPolynomialRing(R)[source]#

Return the Schubert polynomial ring over R on the X basis.

This is the basis made of the Schubert polynomials.

EXAMPLES:

sage: X = SchubertPolynomialRing(ZZ); X
Schubert polynomial ring with X basis over Integer Ring
sage: TestSuite(X).run()
sage: X(1)
X[1]
sage: X([1,2,3])*X([2,1,3])
X[2, 1]
sage: X([2,1,3])*X([2,1,3])
X[3, 1, 2]
sage: X([2,1,3])+X([3,1,2,4])
X[2, 1] + X[3, 1, 2]
sage: a = X([2,1,3])+X([3,1,2,4])
sage: a^2
X[3, 1, 2] + 2*X[4, 1, 2, 3] + X[5, 1, 2, 3, 4]

>>> from sage.all import *
>>> X = SchubertPolynomialRing(ZZ); X
Schubert polynomial ring with X basis over Integer Ring
>>> TestSuite(X).run()
>>> X(Integer(1))
X[1]
>>> X([Integer(1),Integer(2),Integer(3)])*X([Integer(2),Integer(1),Integer(3)])
X[2, 1]
>>> X([Integer(2),Integer(1),Integer(3)])*X([Integer(2),Integer(1),Integer(3)])
X[3, 1, 2]
>>> X([Integer(2),Integer(1),Integer(3)])+X([Integer(3),Integer(1),Integer(2),Integer(4)])
X[2, 1] + X[3, 1, 2]
>>> a = X([Integer(2),Integer(1),Integer(3)])+X([Integer(3),Integer(1),Integer(2),Integer(4)])
>>> a**Integer(2)
X[3, 1, 2] + 2*X[4, 1, 2, 3] + X[5, 1, 2, 3, 4]

class sage.combinat.schubert_polynomial.SchubertPolynomialRing_xbasis(R)[source]#

EXAMPLES:

sage: X = SchubertPolynomialRing(QQ)
True

>>> from sage.all import *
>>> X = SchubertPolynomialRing(QQ)
True

Element[source]#
one_basis()[source]#

Return the index of the unit of this algebra.

EXAMPLES:

sage: X = SchubertPolynomialRing(QQ)
sage: X.one()  # indirect doctest
X[1]

>>> from sage.all import *
>>> X = SchubertPolynomialRing(QQ)
>>> X.one()  # indirect doctest
X[1]

product_on_basis(left, right)[source]#

EXAMPLES:

sage: p1 = Permutation([3,2,1])
sage: p2 = Permutation([2,1,3])
sage: X = SchubertPolynomialRing(QQ)
sage: X.product_on_basis(p1,p2)
X[4, 2, 1, 3]

>>> from sage.all import *
>>> p1 = Permutation([Integer(3),Integer(2),Integer(1)])
>>> p2 = Permutation([Integer(2),Integer(1),Integer(3)])
>>> X = SchubertPolynomialRing(QQ)
>>> X.product_on_basis(p1,p2)
X[4, 2, 1, 3]

some_elements()[source]#

Return some elements.

EXAMPLES:

sage: X = SchubertPolynomialRing(QQ)
sage: X.some_elements()
[X[1], X[1] + 2*X[2, 1], -X[3, 2, 1] + X[4, 2, 1, 3]]

>>> from sage.all import *
>>> X = SchubertPolynomialRing(QQ)
>>> X.some_elements()
[X[1], X[1] + 2*X[2, 1], -X[3, 2, 1] + X[4, 2, 1, 3]]

class sage.combinat.schubert_polynomial.SchubertPolynomial_class[source]#
divided_difference(i, algorithm='sage')[source]#

Return the i-th divided difference operator, applied to self.

Here, i can be either a permutation or a positive integer.

INPUT:

• i – permutation or positive integer

• algorithm – (default: 'sage') either 'sage' or 'symmetrica'; this determines which software is called for the computation

OUTPUT:

The result of applying the i-th divided difference operator to self.

If $$i$$ is a positive integer, then the $$i$$-th divided difference operator $$\delta_i$$ is the linear operator sending each polynomial $$f = f(x_1, x_2, \ldots, x_n)$$ (in $$n \geq i+1$$ variables) to the polynomial

$\frac{f - f_i}{x_i - x_{i+1}}, \qquad \text{ where } f_i = f(x_1, x_2, ..., x_{i-1}, x_{i+1}, x_i, x_{i+1}, ..., x_n) .$

If $$\sigma$$ is a permutation in the $$n$$-th symmetric group, then the $$\sigma$$-th divided difference operator $$\delta_\sigma$$ is the composition $$\delta_{i_1} \delta_{i_2} \cdots \delta_{i_k}$$, where $$\sigma = s_{i_1} \circ s_{i_2} \circ \cdots \circ s_{i_k}$$ is any reduced expression for $$\sigma$$ (the precise choice of reduced expression is immaterial).

Note

The expand() method results in a polynomial in $$n$$ variables named x0, x1, ..., x(n-1) rather than $$x_1, x_2, \ldots, x_n$$. The variable named xi corresponds to $$x_{i+1}$$. Thus, self.divided_difference(i) involves the variables x(i-1) and xi getting switched (in the numerator).

EXAMPLES:

sage: X = SchubertPolynomialRing(ZZ)
sage: a = X([3,2,1])
sage: a.divided_difference(1)
X[2, 3, 1]
sage: a.divided_difference([3,2,1])
X[1]
sage: a.divided_difference(5)
0

>>> from sage.all import *
>>> X = SchubertPolynomialRing(ZZ)
>>> a = X([Integer(3),Integer(2),Integer(1)])
>>> a.divided_difference(Integer(1))
X[2, 3, 1]
>>> a.divided_difference([Integer(3),Integer(2),Integer(1)])
X[1]
>>> a.divided_difference(Integer(5))
0


Any divided difference of $$0$$ is $$0$$:

sage: X.zero().divided_difference(2)
0

>>> from sage.all import *
>>> X.zero().divided_difference(Integer(2))
0


This is compatible when a permutation is given as input:

sage: a = X([3,2,4,1])
sage: a.divided_difference([2,3,1])
0
sage: a.divided_difference(1).divided_difference(2)
0

>>> from sage.all import *
>>> a = X([Integer(3),Integer(2),Integer(4),Integer(1)])
>>> a.divided_difference([Integer(2),Integer(3),Integer(1)])
0
>>> a.divided_difference(Integer(1)).divided_difference(Integer(2))
0

sage: a = X([4,3,2,1])
sage: a.divided_difference([2,3,1])
X[3, 2, 4, 1]
sage: a.divided_difference(1).divided_difference(2)
X[3, 2, 4, 1]
sage: a.divided_difference([4,1,3,2])
X[1, 4, 2, 3]
sage: b = X([4, 1, 3, 2])
sage: b.divided_difference(1).divided_difference(2)
X[1, 3, 4, 2]
sage: b.divided_difference(1).divided_difference(2).divided_difference(3)
X[1, 3, 2]
sage: b.divided_difference(1).divided_difference(2).divided_difference(3).divided_difference(2)
X[1]
sage: b.divided_difference(1).divided_difference(2).divided_difference(3).divided_difference(3)
0
sage: b.divided_difference(1).divided_difference(2).divided_difference(1)
0

>>> from sage.all import *
>>> a = X([Integer(4),Integer(3),Integer(2),Integer(1)])
>>> a.divided_difference([Integer(2),Integer(3),Integer(1)])
X[3, 2, 4, 1]
>>> a.divided_difference(Integer(1)).divided_difference(Integer(2))
X[3, 2, 4, 1]
>>> a.divided_difference([Integer(4),Integer(1),Integer(3),Integer(2)])
X[1, 4, 2, 3]
>>> b = X([Integer(4), Integer(1), Integer(3), Integer(2)])
>>> b.divided_difference(Integer(1)).divided_difference(Integer(2))
X[1, 3, 4, 2]
>>> b.divided_difference(Integer(1)).divided_difference(Integer(2)).divided_difference(Integer(3))
X[1, 3, 2]
>>> b.divided_difference(Integer(1)).divided_difference(Integer(2)).divided_difference(Integer(3)).divided_difference(Integer(2))
X[1]
>>> b.divided_difference(Integer(1)).divided_difference(Integer(2)).divided_difference(Integer(3)).divided_difference(Integer(3))
0
>>> b.divided_difference(Integer(1)).divided_difference(Integer(2)).divided_difference(Integer(1))
0

expand()[source]#

EXAMPLES:

sage: X = SchubertPolynomialRing(ZZ)
sage: X([2,1,3]).expand()
x0
sage: [X(p).expand() for p in Permutations(3)]
[1, x0 + x1, x0, x0*x1, x0^2, x0^2*x1]

>>> from sage.all import *
>>> X = SchubertPolynomialRing(ZZ)
>>> X([Integer(2),Integer(1),Integer(3)]).expand()
x0
>>> [X(p).expand() for p in Permutations(Integer(3))]
[1, x0 + x1, x0, x0*x1, x0^2, x0^2*x1]

multiply_variable(i)[source]#

Return the Schubert polynomial obtained by multiplying self by the variable $$x_i$$.

EXAMPLES:

sage: X = SchubertPolynomialRing(ZZ)
sage: a = X([3,2,4,1])
sage: a.multiply_variable(0)
X[4, 2, 3, 1]
sage: a.multiply_variable(1)
X[3, 4, 2, 1]
sage: a.multiply_variable(2)
X[3, 2, 5, 1, 4] - X[3, 4, 2, 1] - X[4, 2, 3, 1]
sage: a.multiply_variable(3)
X[3, 2, 4, 5, 1]

>>> from sage.all import *
>>> X = SchubertPolynomialRing(ZZ)
>>> a = X([Integer(3),Integer(2),Integer(4),Integer(1)])
>>> a.multiply_variable(Integer(0))
X[4, 2, 3, 1]
>>> a.multiply_variable(Integer(1))
X[3, 4, 2, 1]
>>> a.multiply_variable(Integer(2))
X[3, 2, 5, 1, 4] - X[3, 4, 2, 1] - X[4, 2, 3, 1]
>>> a.multiply_variable(Integer(3))
X[3, 2, 4, 5, 1]

scalar_product(x)[source]#

Return the standard scalar product of self and x.

EXAMPLES:

sage: X = SchubertPolynomialRing(ZZ)
sage: a = X([3,2,4,1])
sage: a.scalar_product(a)
0
sage: b = X([4,3,2,1])
sage: b.scalar_product(a)
X[1, 3, 4, 6, 2, 5]
sage: Permutation([1, 3, 4, 6, 2, 5, 7]).to_lehmer_code()
[0, 1, 1, 2, 0, 0, 0]
sage: s = SymmetricFunctions(ZZ).schur()
sage: c = s([2,1,1])
sage: b.scalar_product(a).expand()
x0^2*x1*x2 + x0*x1^2*x2 + x0*x1*x2^2 + x0^2*x1*x3 + x0*x1^2*x3
+ x0^2*x2*x3 + 3*x0*x1*x2*x3 + x1^2*x2*x3 + x0*x2^2*x3 + x1*x2^2*x3
+ x0*x1*x3^2 + x0*x2*x3^2 + x1*x2*x3^2
sage: c.expand(4)
x0^2*x1*x2 + x0*x1^2*x2 + x0*x1*x2^2 + x0^2*x1*x3 + x0*x1^2*x3
+ x0^2*x2*x3 + 3*x0*x1*x2*x3 + x1^2*x2*x3 + x0*x2^2*x3 + x1*x2^2*x3
+ x0*x1*x3^2 + x0*x2*x3^2 + x1*x2*x3^2

>>> from sage.all import *
>>> X = SchubertPolynomialRing(ZZ)
>>> a = X([Integer(3),Integer(2),Integer(4),Integer(1)])
>>> a.scalar_product(a)
0
>>> b = X([Integer(4),Integer(3),Integer(2),Integer(1)])
>>> b.scalar_product(a)
X[1, 3, 4, 6, 2, 5]
>>> Permutation([Integer(1), Integer(3), Integer(4), Integer(6), Integer(2), Integer(5), Integer(7)]).to_lehmer_code()
[0, 1, 1, 2, 0, 0, 0]
>>> s = SymmetricFunctions(ZZ).schur()
>>> c = s([Integer(2),Integer(1),Integer(1)])
>>> b.scalar_product(a).expand()
x0^2*x1*x2 + x0*x1^2*x2 + x0*x1*x2^2 + x0^2*x1*x3 + x0*x1^2*x3
+ x0^2*x2*x3 + 3*x0*x1*x2*x3 + x1^2*x2*x3 + x0*x2^2*x3 + x1*x2^2*x3
+ x0*x1*x3^2 + x0*x2*x3^2 + x1*x2*x3^2
>>> c.expand(Integer(4))
x0^2*x1*x2 + x0*x1^2*x2 + x0*x1*x2^2 + x0^2*x1*x3 + x0*x1^2*x3
+ x0^2*x2*x3 + 3*x0*x1*x2*x3 + x1^2*x2*x3 + x0*x2^2*x3 + x1*x2^2*x3
+ x0*x1*x3^2 + x0*x2*x3^2 + x1*x2*x3^2