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 of nu.

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]