# Non-Commutative Symmetric Functions¶

class sage.combinat.ncsf_qsym.ncsf.NonCommutativeSymmetricFunctions(R)

The abstract algebra of non-commutative symmetric functions

We construct the abstract algebra of non-commutative symmetric functions over the rational numbers:

sage: NCSF = NonCommutativeSymmetricFunctions(QQ)
sage: NCSF
Non-Commutative Symmetric Functions over the Rational Field
sage: S = NCSF.complete()
sage: R = NCSF.ribbon()
sage: S[2,1]*R[1,2]
S[2, 1, 1, 2] - S[2, 1, 3]


NCSF is the unique free (non-commutative!) graded connected algebra, with one generator in each degree:

sage: NCSF.category()
Join of Category of graded hopf algebras over Rational Field and Category of monoids with realizations and Category of coalgebras over Rational Field with realizations
sage: [S[i].degree() for i in range(10)]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]


We use the Sage standard renaming idiom to get shorter outputs:

sage: NCSF.rename("NCSF")
sage: NCSF
NCSF


NCSF has many representations as a concrete algebra. Each of them has a distinguished basis, and its elements are expanded in this basis. Here is the Psi representation:

sage: Psi = NCSF.Psi()
sage: Psi
NCSF in the Psi basis


Elements of Psi are linear combinations of such compositions:

sage: Psi.an_element()
2*Psi[] + 2*Psi[1] + 3*Psi[1, 1]


The basis itself is accessible through:

sage: Psi.basis()
Lazy family (Term map from Compositions of non-negative integers...
sage: Psi.basis().keys()
Compositions of non-negative integers


To construct an element one can therefore do:

sage: Psi.basis()[Composition([2,1,3])]
Psi[2, 1, 3]


As this is rather cumbersome, the following abuses of notation are allowed:

sage: Psi[Composition([2, 1, 3])]
Psi[2, 1, 3]
sage: Psi[[2, 1, 3]]
Psi[2, 1, 3]
sage: Psi[2, 1, 3]
Psi[2, 1, 3]


or even:

sage: Psi[(i for i in [2, 1, 3])]
Psi[2, 1, 3]


Unfortunately, due to a limitation in Python syntax, one cannot use:

sage: Psi[]       # not implemented


Instead, you can use:

sage: Psi[[]]
Psi[]


Now, we can construct linear combinations of basis elements:

sage: Psi[2,1,3] + 2 * (Psi[4] + Psi[2,1])
2*Psi[2, 1] + Psi[2, 1, 3] + 2*Psi[4]


Algebra structure

To start with, Psi is a graded algebra, the grading being induced by the size of compositions. Due to this, the one is the basis element indexed by the empty composition:

sage: Psi.one()
Psi[]
sage: S.one()
S[]
sage: R.one()
R[]


As we have seen above, the Psi basis is multiplicative; that is multiplication is induced by linearity from the concatenation of compositions:

sage: Psi[1,3] * Psi[2,1]
Psi[1, 3, 2, 1]
sage: (Psi.one() + 2 * Psi[1,3]) * Psi[2, 4]
2*Psi[1, 3, 2, 4] + Psi[2, 4]


Hopf algebra structure

Psi is further endowed with a coalgebra algebra structure (in fact, it is, up to isomorphism, the unique free algebra on primitive elements). The coproduct is an algebra morphism, and therefore determined by its values on the generators; those are primitive:

sage: Psi[1].coproduct()
Psi[] # Psi[1] + Psi[1] # Psi[]
sage: Psi[2].coproduct()
Psi[] # Psi[2] + Psi[2] # Psi[]


The coproduct being cocommutative on the generators is cocommutative everywhere:

sage: Psi[1,2].coproduct()
Psi[] # Psi[1, 2] + Psi[1] # Psi[2] + Psi[1, 2] # Psi[] + Psi[2] # Psi[1]


The antipode is an anti-algebra morphism; in the Psi basis, it sends the generators to their opposite:

sage: Psi[3].antipode()
-Psi[3]
sage: Psi[1,3,2].antipode()
-Psi[2, 3, 1]
sage: Psi[1,3,2].coproduct().apply_multilinear_morphism(lambda be,ga: Psi(be)*Psi(ga).antipode())
0


The counit is defined by sending all elements of positive degree to zero:

sage: S[3].degree(), S[3,1,2].degree(), S.one().degree()
(3, 6, 0)
sage: S[3].counit()
0
sage: S[3,1,2].counit()
0
sage: S.one().counit()
1
sage: (S[3] - 2*S[3,1,2] + 7).counit()
7
sage: (R[3] - 2*R[3,1,2] + 7).counit()
7


Other concrete representations

TODO: demonstrate how to customize the basis names

NCSF admits many other concrete realizations:

sage: Phi        = NCSF.Phi()
sage: ribbon     = NCSF.ribbon()
sage: complete   = NCSF.complete()
sage: elementary = NCSF.elementary()


To change from one basis to another, one simply does:

sage: Phi(Psi[1])
Phi[1]
sage: Phi(Psi[3])
-1/4*Phi[1, 2] + 1/4*Phi[2, 1] + Phi[3]


In general, one can mix up different basis in computations:

sage: Phi[1] * Psi[1]
Phi[1, 1]


Some of the changes of basis are easy to guess:

sage: ribbon(complete[1,3,2])
R[1, 3, 2] + R[1, 5] + R[4, 2] + R[6]


This is the sum of all fatter compositions. Using the usual Moebius function for the boolean lattice, the inverse change of basis is given by the alternating sum of all fatter compositions:

sage: complete(ribbon[1,3,2])
S[1, 3, 2] - S[1, 5] - S[4, 2] + S[6]


The analogue of the elementary basis is the sum over all finer compositions than the ‘complement’ of the composition in the ribbon basis:

sage: Composition([1,3,2]).complement()
[2, 1, 2, 1]
sage: ribbon(elementary([1,3,2]))
R[1, 1, 1, 1, 1, 1] + R[1, 1, 1, 2, 1] + R[2, 1, 1, 1, 1] + R[2, 1, 2, 1]


By mobius inversion on the composition poset, the ribbon basis is then the alternating sum over all compositions fatter than the complement composition in the elementary basis:

sage: elementary(ribbon[2,1,2,1])
L[1, 3, 2] - L[1, 5] - L[4, 2] + L[6]


TODO: explain the other changes of bases!

Here is how to fetch the conversion morphisms:

sage: f = complete.coerce_map_from(elementary); f
Generic morphism:
From: NCSF in the Elementary basis
To:   NCSF in the Complete basis
sage: g = elementary.coerce_map_from(complete); g
Generic morphism:
From: NCSF in the Complete basis
To:   NCSF in the Elementary basis
sage: f.category()
Category of hom sets in Category of modules with basis over Rational Field
sage: f(elementary[1,2,2])
S[1, 1, 1, 1, 1] - S[1, 1, 1, 2] - S[1, 2, 1, 1] + S[1, 2, 2]
sage: g(complete[1,2,2])
L[1, 1, 1, 1, 1] - L[1, 1, 1, 2] - L[1, 2, 1, 1] + L[1, 2, 2]
sage: h = f*g; h
Composite map:
From: NCSF in the Complete basis
To:   NCSF in the Complete basis
Defn:   Generic morphism:
From: NCSF in the Complete basis
To:   NCSF in the Elementary basis
then
Generic morphism:
From: NCSF in the Elementary basis
To:   NCSF in the Complete basis
sage: h(complete[1,3,2])
S[1, 3, 2]


We revert back to the original name from our custom short name NCSF:

sage: NCSF
NCSF
sage: NCSF.rename()
sage: NCSF
Non-Commutative Symmetric Functions over the Rational Field


TESTS:

sage: TestSuite(Phi).run()
sage: TestSuite(Psi).run()
sage: TestSuite(complete).run()

TODO:
• Bases: monomial, fundamental, forgotten, quasi_schur_dual

simple() ? (<=> simple modules of HS_n; to be discussed with Florent)

• Multiplication in:
• fundamental and monomial (cf. Lenny’s code)
• ribbon (from Mike’s code)
• Coproducts (most done by coercions)

• some_elements in all bases

• Systematic coercion checks (in AlgebrasWithBasis().Abstract())

class Bases(parent_with_realization)

Category of bases of non-commutative symmetric functions.

EXAMPLES:

sage: N = NonCommutativeSymmetricFunctions(QQ)
sage: N.Bases()
Category of bases of Non-Commutative Symmetric Functions over the Rational Field
sage: R = N.Ribbon()
sage: R in N.Bases()
True

ElementMethods

alias of Bases.ElementMethods

ParentMethods

alias of Bases.ParentMethods

super_categories()

Returns the super categories of the category of bases of the non-commutative symmetric functions.

OUTPUT:

• list

TESTS:

sage: N = NonCommutativeSymmetricFunctions(QQ)
sage: N.Bases().super_categories()
[Category of bases of Non-Commutative Symmetric Functions or Quasisymmetric functions over the Rational Field,
Category of realizations of graded modules with internal product over Rational Field]

class NonCommutativeSymmetricFunctions.Complete(NCSF)

The Hopf algebra of non-commutative symmetric functions in the Complete basis.

EXAMPLES:

sage: NCSF = NonCommutativeSymmetricFunctions(QQ)
sage: S = NCSF.Complete(); S
Non-Commutative Symmetric Functions over the Rational Field in the Complete basis
sage: S.an_element()
2*S[] + 2*S[1] + 3*S[1, 1]


The following are aliases for this basis:

sage: NCSF.complete()
Non-Commutative Symmetric Functions over the Rational Field in the Complete basis
sage: NCSF.S()
Non-Commutative Symmetric Functions over the Rational Field in the Complete basis

dual()

Returns the dual basis to the complete basis of non-commutative symmetric functions. This is the Monomial basis of quasi-symmetric functions.

OUTPUT:

• The Monomial basis of quasi-symmetric functions.

EXAMPLES:

sage: S = NonCommutativeSymmetricFunctions(QQ).S()
sage: S.dual()
Quasisymmetric functions over the Rational Field in the Monomial basis

internal_product_on_basis(I, J)

The internal product of two non-commutative symmetric complete functions.

INPUT:

• I, J – compositions

OUTPUT:

• The internal product of the complete non-commutative symmetric function basis elements indexed by I and J, expressed in the complete basis.

EXAMPLES:

sage: N = NonCommutativeSymmetricFunctions(QQ)
sage: S = N.complete()
sage: S.internal_product_on_basis([2,2],[1,2,1])
2*S[1, 1, 1, 1] + S[1, 1, 2] + S[2, 1, 1]
sage: S.internal_product_on_basis([2,2],[1,2])
0

to_symmetric_function_on_basis(I)

The commutative image of a complete non-commutative symmetric function basis element. This is obtained by sorting the composition.

INPUT:

• I – a composition

OUTPUT:

• The commutative image of the complete basis element indexed by I. The result is the complete symmetric function indexed by the partition obtained by sorting I.

EXAMPLES:

sage: S=NonCommutativeSymmetricFunctions(QQ).S()
sage: S.to_symmetric_function_on_basis([2,1,3])
h[3, 2, 1]
sage: S.to_symmetric_function_on_basis([])
h[]

class NonCommutativeSymmetricFunctions.Elementary(NCSF)

The Hopf algebra of non-commutative symmetric functions in the Elementary basis.

EXAMPLES:

sage: NCSF = NonCommutativeSymmetricFunctions(QQ)
sage: L = NCSF.Elementary(); L
Non-Commutative Symmetric Functions over the Rational Field in the Elementary basis
sage: L.an_element()
2*L[] + 2*L[1] + 3*L[1, 1]


The following are aliases for this basis:

sage: NCSF.elementary()
Non-Commutative Symmetric Functions over the Rational Field in the Elementary basis
sage: NCSF.L()
Non-Commutative Symmetric Functions over the Rational Field in the Elementary basis

class NonCommutativeSymmetricFunctions.Immaculate(NCSF)

The immaculate basis of the non-commutative symmetric functions. This basis first appears in Berg, Bergeron, Saliola, Serrano and Zabrocki’s “A lift of the Schur and Hall-Littlewood bases to non-commutative symmetric functions” arXiv:1208.5191.

EXAMPLES:

sage: NCSF = NonCommutativeSymmetricFunctions(QQ)
sage: I = NCSF.I()
sage: I([1,3,2])*I([1])
I[1, 3, 2, 1] + I[1, 3, 3] + I[1, 4, 2] + I[2, 3, 2]
sage: I([1])*I([1,3,2])
I[1, 1, 3, 2] - I[2, 2, 1, 2] - I[2, 2, 2, 1] - I[2, 2, 3] - I[3, 2, 2]
sage: I([1,3])*I([1,1])
I[1, 3, 1, 1] + I[1, 4, 1] + I[2, 3, 1] + I[2, 4]
sage: I([3,1])*I([2,1])
I[3, 1, 2, 1] + I[3, 2, 1, 1] + I[3, 2, 2] + I[3, 3, 1] + I[4, 1, 1, 1] + I[4, 1, 2] + 2*I[4, 2, 1] + I[4, 3] + I[5, 1, 1] + I[5, 2]
sage: R = NCSF.ribbon()
sage: I(R[1,3,1])
I[1, 3, 1] + I[2, 2, 1] + I[2, 3] + I[3, 1, 1] + I[3, 2]
sage: R(I(R([2,1,3])))
R[2, 1, 3]

class NonCommutativeSymmetricFunctions.Monomial(NCSF)

Basis from ‘Noncommutative Analogs of Monomial Symmetric Functions, Cauchy Identity, and Hall Scalar Product’ Lenny Tevlin arXiv:0712.2201v1 [math.CO]

TESTS:

sage: NCSF = NonCommutativeSymmetricFunctions(QQ)
sage: nM = NCSF.monomial(); nM
Non-Commutative Symmetric Functions over the Rational Field in the Monomial basis
sage: nM([1,1])*nM([2])
3*nM[1, 1, 2] + nM[1, 3] + nM[2, 2]
sage: R = NCSF.ribbon()
sage: nM(R[1,3,1])
11*nM[1, 1, 1, 1, 1] + 8*nM[1, 1, 2, 1] + 8*nM[1, 2, 1, 1] + 5*nM[1, 3, 1] + 8*nM[2, 1, 1, 1] + 5*nM[2, 2, 1] + 5*nM[3, 1, 1] + 2*nM[4, 1]

class NonCommutativeSymmetricFunctions.MultiplicativeBases(parent_with_realization)

Category of multiplicative bases of non-commutative symmetric functions.

EXAMPLES:

sage: N = NonCommutativeSymmetricFunctions(QQ)
sage: N.MultiplicativeBases()
Category of multiplicative bases of Non-Commutative Symmetric Functions over the Rational Field


The complete basis is a multiplicative basis, but the ribbon basis is not:

sage: N.Complete() in N.MultiplicativeBases()
True
sage: N.Ribbon() in N.MultiplicativeBases()
False

ParentMethods

alias of MultiplicativeBases.ParentMethods

super_categories()

Returns the super categories of the category of multiplicative bases of the non-commutative symmetric functions.

OUTPUT:

• list

TESTS:

sage: N = NonCommutativeSymmetricFunctions(QQ)
sage: N.MultiplicativeBases().super_categories()
[Category of bases of Non-Commutative Symmetric Functions over the Rational Field]

class NonCommutativeSymmetricFunctions.MultiplicativeBasesOnGroupLikeElements(parent_with_realization)

Category of multiplicative bases on group like elements of non-commutative symmetric functions.

EXAMPLES:

sage: N = NonCommutativeSymmetricFunctions(QQ)
sage: N.MultiplicativeBasesOnGroupLikeElements()
Category of multiplicative bases on group like elements of Non-Commutative Symmetric Functions over the Rational Field


The complete basis is a multiplicative basis, but the ribbon basis is not:

sage: N.Complete() in N.MultiplicativeBasesOnGroupLikeElements()
True
sage: N.Ribbon() in N.MultiplicativeBasesOnGroupLikeElements()
False

ParentMethods

alias of MultiplicativeBasesOnGroupLikeElements.ParentMethods

super_categories()

Returns the super categories of the category of multiplicative bases of group-like elements of the non-commutative symmetric functions.

OUTPUT:

• list

TESTS:

sage: N = NonCommutativeSymmetricFunctions(QQ)
sage: N.MultiplicativeBasesOnGroupLikeElements().super_categories()
[Category of multiplicative bases of Non-Commutative Symmetric Functions over the Rational Field]

class NonCommutativeSymmetricFunctions.MultiplicativeBasesOnPrimitiveElements(parent_with_realization)

Category of multiplicative bases of the non-commutative symmetric functions whose generators are primitive elements.

An element is primitive if $$\Delta(x) = x \otimes 1 + 1 \otimes x$$, where $$\Delta$$ is the coproduct of the non-commutative symmetric functions.

From this one can compute the coproduct and the antipode of any element, since they are respectively algebra morphisms and anti-morphisms. See antipode_on_generators() and coproduct_on_generators().

Todo

this could be generalized to any free algebra.

EXAMPLES:

sage: N = NonCommutativeSymmetricFunctions(QQ)
sage: N.MultiplicativeBasesOnPrimitiveElements()
Category of multiplicative bases on primitive elements of Non-Commutative Symmetric Functions over the Rational Field


The Phi and Psi bases are a multiplicative basis whose generators are primitive elements, but the complete and ribbon bases are not:

sage: N.Phi() in N.MultiplicativeBasesOnPrimitiveElements()
True
sage: N.Psi() in N.MultiplicativeBasesOnPrimitiveElements()
True
sage: N.Complete() in N.MultiplicativeBasesOnPrimitiveElements()
False
sage: N.Ribbon() in N.MultiplicativeBasesOnPrimitiveElements()
False

ParentMethods

alias of MultiplicativeBasesOnPrimitiveElements.ParentMethods

super_categories()

Returns the super categories of the category of multiplicative bases of primitive elements of the non-commutative symmetric functions.

OUTPUT:

• list

TESTS:

sage: N = NonCommutativeSymmetricFunctions(QQ)
sage: N.MultiplicativeBasesOnPrimitiveElements().super_categories()
[Category of multiplicative bases of Non-Commutative Symmetric Functions over the Rational Field]

class NonCommutativeSymmetricFunctions.Phi(NCSF)

The Hopf algebra of non-commutative symmetric functions in the Phi basis.

EXAMPLES:

sage: NCSF = NonCommutativeSymmetricFunctions(QQ)
sage: Phi = NCSF.Phi(); Phi
Non-Commutative Symmetric Functions over the Rational Field in the Phi basis
sage: Phi.an_element()
2*Phi[] + 2*Phi[1] + 3*Phi[1, 1]

class NonCommutativeSymmetricFunctions.Psi(NCSF)

The Hopf algebra of non-commutative symmetric functions in the Psi basis.

EXAMPLES:

sage: NCSF = NonCommutativeSymmetricFunctions(QQ)
sage: Psi = NCSF.Psi(); Psi
Non-Commutative Symmetric Functions over the Rational Field in the Psi basis
sage: Psi.an_element()
2*Psi[] + 2*Psi[1] + 3*Psi[1, 1]

class NonCommutativeSymmetricFunctions.Ribbon(NCSF)

The Hopf algebra of non-commutative symmetric functions in the Ribbon basis.

EXAMPLES:

sage: NCSF = NonCommutativeSymmetricFunctions(QQ)
sage: R = NCSF.Ribbon(); R
Non-Commutative Symmetric Functions over the Rational Field in the Ribbon basis
sage: R.an_element()
2*R[] + 2*R[1] + 3*R[1, 1]


The following are aliases for this basis:

sage: NCSF.ribbon()
Non-Commutative Symmetric Functions over the Rational Field in the Ribbon basis
sage: NCSF.R()
Non-Commutative Symmetric Functions over the Rational Field in the Ribbon basis

dual()

Returns the dual basis to the ribbon basis of the non-commutative symmetric functions. This is the Fundamental basis of the quasi-symmetric functions.

OUTPUT:

• The fundamental basis of the quasi-symmetric functions.

EXAMPLES:

sage: R=NonCommutativeSymmetricFunctions(QQ).ribbon()
sage: R.dual()
Quasisymmetric functions over the Rational Field in the Fundamental basis

product_on_basis(I, J)

Returns the product of two ribbon basis elements of the non-commutative symmetric functions.

INPUT:

• I, J – compositions

OUTPUT:

• The product of the ribbon functions indexed by I and J.

EXAMPLES:

sage: R = NonCommutativeSymmetricFunctions(QQ).ribbon()
sage: R[1,2,1] * R[3,1]
R[1, 2, 1, 3, 1] + R[1, 2, 4, 1]
sage: ( R[1,2] + R[3] ) * ( R[3,1] + R[1,2,1] )
R[1, 2, 1, 2, 1] + R[1, 2, 3, 1] + R[1, 3, 2, 1] + R[1, 5, 1] + R[3, 1, 2, 1] + R[3, 3, 1] + R[4, 2, 1] + R[6, 1]


TESTS:

sage: R[[]] * R[3,1]
R[3, 1]
sage: R[1,2,1] * R[[]]
R[1, 2, 1]
sage: R.product_on_basis(Composition([2,1]), Composition([1]))
R[2, 1, 1] + R[2, 2]

to_symmetric_function_on_basis(I)

Returns the commutative image of a ribbon basis element of the non-commutative symmetric functions.

INPUT:

• I – a composition

OUTPUT:

• The commutative image of the ribbon basis element indexed by I. This will be expressed as a symmetric function in the Schur basis.

EXAMPLES:

sage: R=NonCommutativeSymmetricFunctions(QQ).R()
sage: R.to_symmetric_function_on_basis(Composition([3,1,1]))
s[3, 1, 1]
sage: R.to_symmetric_function_on_basis(Composition([4,2,1]))
s[4, 2, 1] + s[5, 1, 1] + s[5, 2]
sage: R.to_symmetric_function_on_basis(Composition([]))
s[]

NonCommutativeSymmetricFunctions.a_realization()

Gives a realization of the algebra of non-commutative symmetric functions. This particular realization is the complete basis of non-commutative symmetric functions.

OUTPUT:

• The realization of the non-commutative symmetric functions in the complete basis.

EXAMPLES:

sage: NonCommutativeSymmetricFunctions(ZZ).a_realization()
Non-Commutative Symmetric Functions over the Integer Ring in the Complete basis

NonCommutativeSymmetricFunctions.dual()

This function returns the dual to the non-commutative symmetric functions.

OUTPUT:

• The dual of the non-commutative symmetric functions over a ring. This is the algebra of quasi-symmetric functions over the ring.

EXAMPLES:

sage: NCSF = NonCommutativeSymmetricFunctions(QQ)
sage: NCSF.dual()
Quasisymmetric functions over the Rational Field


#### Previous topic

Generic code for bases

#### Next topic

Quasisymmetric functions