Symmetric Functions in Non-Commuting Variables¶
AUTHORS:
- Travis Scrimshaw (08-04-2013): Initial version
-
sage.combinat.ncsym.ncsym.
SymmetricFunctionsNonCommutingVariables
¶ Symmetric functions in non-commutative variables.
The ring of symmetric functions in non-commutative variables, which is not to be confused with the
non-commutative symmetric functions
, is the ring of all bounded-degree noncommutative power series in countably many indeterminates (i.e., elements in \(R \langle \langle x_1, x_2, x_3, \ldots \rangle \rangle\) of bounded degree) which are invariant with respect to the action of the symmetric group \(S_{\infty}\) on the indices of the indeterminates. It can be regarded as a direct limit over all \(n \to \infty\) of rings of \(S_n\)-invariant polynomials in \(n\) non-commuting variables (that is, \(S_n\)-invariant elements of \(R\langle x_1, x_2, \ldots, x_n \rangle\)).This ring is implemented as a Hopf algebra whose basis elements are indexed by set partitions.
Let \(A = \{A_1, A_2, \ldots, A_r\}\) be a set partition of the integers \([k] := \{ 1, 2, \ldots, k \}\). This partition \(A\) determines an equivalence relation \(\sim_A\) on \([k]\), which has \(c \sim_A d\) if and only if \(c\) and \(d\) are in the same part \(A_j\) of \(A\). The monomial basis element \(\mathbf{m}_A\) indexed by \(A\) is the sum of monomials \(x_{i_1} x_{i_2} \cdots x_{i_k}\) such that \(i_c = i_d\) if and only if \(c \sim_A d\).
The \(k\)-th graded component of the ring of symmetric functions in non-commutative variables has its dimension equal to the number of set partitions of \([k]\). (If we work, instead, with finitely many – say, \(n\) – variables, then its dimension is equal to the number of set partitions of \([k]\) where the number of parts is at most \(n\).)
Note
All set partitions are considered standard (i.e., set partitions of \([n]\) for some \(n\)) unless otherwise stated.
REFERENCES:
[BZ05] N. Bergeron, M. Zabrocki. The Hopf algebra of symmetric functions and quasisymmetric functions in non-commutative variables are free and cofree. (2005). Arxiv math/0509265v3. [BHRZ06] N. Bergeron, C. Hohlweg, M. Rosas, M. Zabrocki. Grothendieck bialgebras, partition lattices, and symmetric functions in noncommutative variables. Electronic Journal of Combinatorics. 13 (2006). [RS06] M. Rosas, B. Sagan. Symmetric functions in noncommuting variables. Trans. Amer. Math. Soc. 358 (2006). no. 1, 215-232. Arxiv math/0208168. [BRRZ08] N. Bergeron, C. Reutenauer, M. Rosas, M. Zabrocki. Invariants and coinvariants of the symmetric group in noncommuting variables. Canad. J. Math. 60 (2008). 266-296. Arxiv math/0502082 [BT13] N. Bergeron, N. Thiem. A supercharacter table decomposition via power-sum symmetric functions. Int. J. Algebra Comput. 23, 763 (2013). doi:10.1142/S0218196713400171. Arxiv 1112.4901. EXAMPLES:
We begin by first creating the ring of \(NCSym\) and the bases that are analogues of the usual symmetric functions:
sage: NCSym = SymmetricFunctionsNonCommutingVariables(QQ) sage: m = NCSym.m() sage: e = NCSym.e() sage: h = NCSym.h() sage: p = NCSym.p() sage: m Symmetric functions in non-commuting variables over the Rational Field in the monomial basis
The basis is indexed by set partitions, so we create a few elements and convert them between these bases:
sage: elt = m(SetPartition([[1,3],[2]])) - 2*m(SetPartition([[1],[2]])); elt -2*m{{1}, {2}} + m{{1, 3}, {2}} sage: e(elt) 1/2*e{{1}, {2, 3}} - 2*e{{1, 2}} + 1/2*e{{1, 2}, {3}} - 1/2*e{{1, 2, 3}} - 1/2*e{{1, 3}, {2}} sage: h(elt) -4*h{{1}, {2}} - 2*h{{1}, {2}, {3}} + 1/2*h{{1}, {2, 3}} + 2*h{{1, 2}} + 1/2*h{{1, 2}, {3}} - 1/2*h{{1, 2, 3}} + 3/2*h{{1, 3}, {2}} sage: p(elt) -2*p{{1}, {2}} + 2*p{{1, 2}} - p{{1, 2, 3}} + p{{1, 3}, {2}} sage: m(p(elt)) -2*m{{1}, {2}} + m{{1, 3}, {2}} sage: elt = p(SetPartition([[1,3],[2]])) - 4*p(SetPartition([[1],[2]])) + 2; elt 2*p{} - 4*p{{1}, {2}} + p{{1, 3}, {2}} sage: e(elt) 2*e{} - 4*e{{1}, {2}} + e{{1}, {2}, {3}} - e{{1, 3}, {2}} sage: m(elt) 2*m{} - 4*m{{1}, {2}} - 4*m{{1, 2}} + m{{1, 2, 3}} + m{{1, 3}, {2}} sage: h(elt) 2*h{} - 4*h{{1}, {2}} - h{{1}, {2}, {3}} + h{{1, 3}, {2}} sage: p(m(elt)) 2*p{} - 4*p{{1}, {2}} + p{{1, 3}, {2}}
There is also a shorthand for creating elements. We note that we must use
p[[]]
to create the empty set partition due to python’s syntax.sage: eltm = m[[1,3],[2]] - 3*m[[1],[2]]; eltm -3*m{{1}, {2}} + m{{1, 3}, {2}} sage: elte = e[[1,3],[2]]; elte e{{1, 3}, {2}} sage: elth = h[[1,3],[2,4]]; elth h{{1, 3}, {2, 4}} sage: eltp = p[[1,3],[2,4]] + 2*p[[1]] - 4*p[[]]; eltp -4*p{} + 2*p{{1}} + p{{1, 3}, {2, 4}}
There is also a natural projection to the usual symmetric functions by letting the variables commute. This projection map preserves the product and coproduct structure. We check that Theorem 2.1 of [RS06] holds:
sage: Sym = SymmetricFunctions(QQ) sage: Sm = Sym.m() sage: Se = Sym.e() sage: Sh = Sym.h() sage: Sp = Sym.p() sage: eltm.to_symmetric_function() -6*m[1, 1] + m[2, 1] sage: Sm(p(eltm).to_symmetric_function()) -6*m[1, 1] + m[2, 1] sage: elte.to_symmetric_function() 2*e[2, 1] sage: Se(h(elte).to_symmetric_function()) 2*e[2, 1] sage: elth.to_symmetric_function() 4*h[2, 2] sage: Sh(m(elth).to_symmetric_function()) 4*h[2, 2] sage: eltp.to_symmetric_function() -4*p[] + 2*p[1] + p[2, 2] sage: Sp(e(eltp).to_symmetric_function()) -4*p[] + 2*p[1] + p[2, 2]
-
sage.combinat.ncsym.ncsym.
matchings
(A, B)¶ Iterate through all matchings of the sets \(A\) and \(B\).
EXAMPLES:
sage: from sage.combinat.ncsym.ncsym import matchings sage: list(matchings([1, 2, 3], [-1, -2])) [[[1], [2], [3], [-1], [-2]], [[1], [2], [3, -1], [-2]], [[1], [2], [3, -2], [-1]], [[1], [2, -1], [3], [-2]], [[1], [2, -1], [3, -2]], [[1], [2, -2], [3], [-1]], [[1], [2, -2], [3, -1]], [[1, -1], [2], [3], [-2]], [[1, -1], [2], [3, -2]], [[1, -1], [2, -2], [3]], [[1, -2], [2], [3], [-1]], [[1, -2], [2], [3, -1]], [[1, -2], [2, -1], [3]]]
-
sage.combinat.ncsym.ncsym.
nesting
(la, nu)¶ Return the nesting number of
la
inside ofnu
.If we consider a set partition \(A\) as a set of arcs \(i - j\) where \(i\) and \(j\) are in the same part of \(A\). Define
\[\operatorname{nst}_{\lambda}^{\nu} = \#\{ i < j < k < l \mid i - l \in \nu, j - k \in \lambda \},\]and this corresponds to the number of arcs of \(\lambda\) strictly contained inside of \(\nu\).
EXAMPLES:
sage: from sage.combinat.ncsym.ncsym import nesting sage: nu = SetPartition([[1,4], [2], [3]]) sage: mu = SetPartition([[1,4], [2,3]]) sage: nesting(set(mu).difference(nu), nu) 1
sage: lst = list(SetPartitions(4)) sage: d = {} sage: for i, nu in enumerate(lst): ....: for mu in nu.coarsenings(): ....: if set(nu.arcs()).issubset(mu.arcs()): ....: d[i, lst.index(mu)] = nesting(set(mu).difference(nu), nu) sage: matrix(d) [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 1 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0] [0 0 0 0 0 0 0 0 0 0 0 0 0 0 0]