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. OverQQ
(or any other \(\QQ\)-algebra), this Hopf algebraPsi
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 theComplete
basis as having a prefixH
instead of the defaultS
: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 theComplete
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()
andcoeff_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()
andcoeff_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 theImmaculate
basis was introduced in [BBSSZ2012]. TheQuasisymmetric_Schur
were defined in [QSCHUR] and the dual basis is implemented here asdualQuasisymmetric_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