Non-Commutative Symmetric Functions

sage.combinat.ncsf_qsym.ncsf.NonCommutativeSymmetricFunctions

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 hopf algebras over Rational Field
    and Category of graded 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\) (Psi) representation:

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

Elements of Psi are linear combinations of basis elements indexed by 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. 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 structure. 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 algebra and coalgebra structures on Psi combine to form a bialgebra structure, which cooperates with the grading to form a connected graded bialgebra. Thus, as any connected graded bialgebra, Psi is a Hopf algebra. Over QQ (or any other \(\QQ\)-algebra), this Hopf algebra Psi is isomorphic to the tensor algebra of its space of primitive elements.

The antipode is an anti-algebra morphism; in the Psi basis, it sends the generators to their opposites and changes their sign if they are of odd degree:

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

It is possible to change the prefix used to display the basis elements using the method print_options(). Say that for instance one wanted to display the Complete basis as having a prefix H instead of the default S:

sage: H = NCSF.complete()
sage: H.an_element()
2*S[] + 2*S[1] + 3*S[1, 1]
sage: H.print_options(prefix='H')
sage: H.an_element()
2*H[] + 2*H[1] + 3*H[1, 1]
sage: H.print_options(prefix='S') #restore to 'S'

Concrete representations

NCSF admits the concrete realizations defined in [NCSF1]:

sage: Phi        = NCSF.Phi()
sage: Psi        = NCSF.Psi()
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 bases 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 Möbius 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 Möbius inversion on the composition poset, the ribbon basis element corresponding to a composition \(I\) is then the alternating sum over all compositions fatter than the complement composition of \(I\) in the elementary basis:

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

The \(\Phi\) (Phi) and \(\Psi\) bases are computed by changing to and from the Complete basis. The expansion of \(\Psi\) basis is given in Proposition 4.5 of [NCSF1] by the formulae

\[S^I = \sum_{J \geq I} \frac{1}{\pi_u(J,I)} \Psi^J\]

and

\[\Psi^I = \sum_{J \geq I} (-1)^{\ell(J)-\ell(I)} lp(J,I) S^J\]

where the coefficients \(\pi_u(J,I)\) and \(lp(J,I)\) are coefficients in the methods coeff_pi() and coeff_lp() respectively. For example:

sage: Psi(complete[3])
1/6*Psi[1, 1, 1] + 1/3*Psi[1, 2] + 1/6*Psi[2, 1] + 1/3*Psi[3]
sage: complete(Psi[3])
S[1, 1, 1] - 2*S[1, 2] - S[2, 1] + 3*S[3]

The Phi basis is another analogue of the power sum basis from the algebra of symmetric functions and the expansion in the Complete basis is given in Proposition 4.9 of [NCSF1] by the formulae

\[S^I = \sum_{J \geq I} \frac{1}{sp(J,I)} \Phi^J\]

and

\[\Phi^I = \sum_{J \geq I} (-1)^{\ell(J)-\ell(I)} \frac{\prod_i I_i}{\ell(J,I)} S^J\]

where the coefficients \(sp(J,I)\) and \(\ell(J,I)\) are coefficients in the methods coeff_sp() and coeff_ell() respectively. For example:

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

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 homsets of unital magmas and right modules over Rational Field and
  left modules 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]

Additional concrete representations

NCSF has some additional bases which appear in the literature:

sage: Monomial                 = NCSF.Monomial()
sage: Immaculate               = NCSF.Immaculate()
sage: dualQuasisymmetric_Schur = NCSF.dualQuasisymmetric_Schur()

The Monomial basis was introduced in [Tev2007] and the Immaculate basis was introduced in [BBSSZ2012]. The Quasisymmetric_Schur were defined in [QSCHUR] and the dual basis is implemented here as dualQuasisymmetric_Schur. Refer to the documentation for the use and definition of these bases.

Todo

  • implement fundamental, forgotten, and simple (coming from the simple modules of HS_n) bases.

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