Descent Algebras

AUTHORS:

  • Travis Scrimshaw (2013-07-28): Initial version
sage.combinat.descent_algebra.DescentAlgebra

Solomon’s descent algebra.

The descent algebra \(\Sigma_n\) over a ring \(R\) is a subalgebra of the symmetric group algebra \(R S_n\). (The product in the latter algebra is defined by \((pq)(i) = q(p(i))\) for any two permutations \(p\) and \(q\) in \(S_n\) and every \(i \in \{ 1, 2, \ldots, n \}\). The algebra \(\Sigma_n\) inherits this product.)

There are three bases currently implemented for \(\Sigma_n\):

  • the standard basis \(D_S\) of (sums of) descent classes, indexed by subsets \(S\) of \(\{1, 2, \ldots, n-1\}\),
  • the subset basis \(B_p\), indexed by compositions \(p\) of \(n\),
  • the idempotent basis \(I_p\), indexed by compositions \(p\) of \(n\), which is used to construct the mutually orthogonal idempotents of the symmetric group algebra.

The idempotent basis is only defined when \(R\) is a \(\QQ\)-algebra.

We follow the notations and conventions in [GR1989], apart from the order of multiplication being different from the one used in that article. Schocker’s exposition [Sch2004], in turn, uses the same order of multiplication as we are, but has different notations for the bases.

INPUT:

  • R – the base ring
  • n – a nonnegative integer

REFERENCES:

EXAMPLES:

sage: DA = DescentAlgebra(QQ, 4)
sage: D = DA.D(); D
Descent algebra of 4 over Rational Field in the standard basis
sage: B = DA.B(); B
Descent algebra of 4 over Rational Field in the subset basis
sage: I = DA.I(); I
Descent algebra of 4 over Rational Field in the idempotent basis
sage: basis_B = B.basis()
sage: elt = basis_B[Composition([1,2,1])] + 4*basis_B[Composition([1,3])]; elt
B[1, 2, 1] + 4*B[1, 3]
sage: D(elt)
5*D{} + 5*D{1} + D{1, 3} + D{3}
sage: I(elt)
7/6*I[1, 1, 1, 1] + 2*I[1, 1, 2] + 3*I[1, 2, 1] + 4*I[1, 3]

As syntactic sugar, one can use the notation D[i,...,l] to construct elements of the basis; note that for the empty set one must use D[[]] due to Python’s syntax:

sage: D[[]] + D[2] + 2*D[1,2]
D{} + 2*D{1, 2} + D{2}

The same syntax works for the other bases:

sage: I[1,2,1] + 3*I[4] + 2*I[3,1]
I[1, 2, 1] + 2*I[3, 1] + 3*I[4]
sage.combinat.descent_algebra.DescentAlgebraBases

The category of bases of a descent algebra.