Symmetric Functions in Noncommuting Variables

Mercedes H. Rosas Departamento de Matemáticas Universidad Simón Bolívar, Apdo. Postal 89000 Caracas, VENEZUELA mrosas@ma.usb.ve and Bruce E. Sagan Department of Mathematics Michigan State University East Lansing, MI 48824-1027, USA sagan@math.msu.edu www.math.msu.edu/˜ sagan

0. History

1. Symmetric Functions Defined

2. Basis Change

3. MacMahon Symmetric Functions

4. Schur Symmetric Functions

5. Open Problems 0. History

1936  M. C. Wolf
1969  G M. Bergman & P. M. Cohn
1972  P. Doubilet
1981  M.-P. Schützenberger

& A. Lascoux

1995  I. M. Gelfand, D. Krob,

A. Lascoux, B. Leclerc, V. Retakh, & J.-I. Thibon

1998  S. Fomin & C. Greene
2000 & 2001  D. Gebhard & BES
2001 & 2002  MHR
2003  MHR & BES
2003  MHR & C. Reutenhauer

1. Symmetric Functions (SFs) Defined

Let ℚ[[x]]and ℚ⟨⟨x⟩⟩ be the algebras of formal power series in commuting and noncommuting variables x = {x_{1}, x_{2}, …}, respectively. Any g ∈ 𝔖_{m} (symmetric group) acts on f in either algebra by

gf(x_{1}, x_{2}, …) = f(x_{g1}, x_{g2}, …)

where gi = i for i > m. Then f is symmetric if it is invariant under all g in all 𝔖_{m}. Let Λ(x) and Π(x) be the subalgebras of ℚ[[x]] and ℚ⟨⟨x⟩⟩, respectively, of symmetric power series of bounded degree.

Bases for Λ[x] are indexed by integer partitions λ = (λ_{1}, λ_{2}, …, λ_{l}) ⊢ n. The monomial SFs are

m_{λ} = ∑(monomials of exponent λ ).

Define power sum and elementary SFs by

p_{n} = x_{1}^{n} + x_{2}^{n} + ⋯
e_{n} = ∑(square-free monomials of degree n  )

and multiplicativity.

Ex. For λ = (3, 3, 1) we have

m_{(3,3,1)} = x_{1}^{3}x_{2}^{3}x_{3} + x_{1}^{3}x_{2}x_{3}^{3} + x_{1}x_{2}^{3}x_{3}^{3} + ⋯
p_{(3,3,1)} = (x_{1}^{3} + x_{2}^{3} + ⋯)^{2}(x_{1} + x_{2} + ⋯)
e_{(3,3,1)} = (x_{1}x_{2}x_{3} + x_{1}x_{2}x_{4} + ⋯)^{2}(x_{1} + x_{2} + ⋯)

Bases for Π[x] are indexed by set partitions π = B_{1}/B_{2}/ … /B_{l} ⊢ [n] where [n] = {1, …, n}. Define

m_{π} = ∑ x_{i_{1}}x_{i_{2}} ⋯ x_{i_{n}} where

i_{j} = i_{k} iff j, k are in the same block of π.

p_{π} = ∑ x_{i_{1}}x_{i_{2}} ⋯ x_{i_{n}} where

i_{j} = i_{k} if j, k are in the same block of π.

e_{π} = ∑ x_{i_{1}}x_{i_{2}} ⋯ x_{i_{n}} where

i_{j} ≠ i_{k} if j, k are in the same block of π.

Ex. For π = 13/2 we have

m_{13/2} = x_{1}x_{2}x_{1} + x_{2}x_{1}x_{2} + x_{1}x_{3}x_{1} + ⋯,
p_{13/2} = x_{1}x_{2}x_{1} + x_{2}x_{1}x_{2} + ⋯ + x_{1}^{3} + x_{2}^{3} + ⋯
e_{13/2} = x_{1}x_{1}x_{2} + x_{1}x_{2}x_{2} + x_{1}x_{3}x_{2} + ⋯

For λ = (λ_{1}, …, λ_{l}) = (1^{c_{1}}, 2^{c_{2}}, …, n^{c_{n}}) let

λ!= λ_{1}!λ_{2}! ⋯ λ_{l}! and λ^{!}= c_{1}!c_{2}! ⋯ c_{n}!

The type of set partition π is the integer partition

λ(π) = (|B_{1}|, |B_{2}|, …, |B_{l}|).

Theorem 1 Let ρ : ℚ⟨⟨x⟩⟩ → ℚ[[x]] be the forgetful map and λ(π) = λ. Then

ρ(m_{π}) = λ^{!}m_{λ},
ρ(p_{π}) = p_{λ},
ρ(e_{π}) = λ!e_{λ}.

In the commuting case, the complete homogeneous SFs are defined by multiplicativity and

h_{n} = _{λ⊢n}^{∑} m_{λ}.

Ex. For λ = (3, 3, 1) we have

h_{(3,3,1)} = (x_{1}^{3} + x_{1}^{2}x_{2} + x_{1}x_{2}x_{3} + ⋯)^{2}(x_{1} + x_{2} + ⋯).

For noncommuting variables, define

h_{π} = _{L}^{∑} m_{σ}

where the sum is over all linear orderings L of the elements in each block of σ ∧ π.

Ex. For π = 13/2 we have

h_{13/2} = m_{1/2/3} + m_{12/3} + 2m_{13/2} + m_{1/23} + 2m_{123} .

Theorem 2 Applying the forgetful map gives

ρ(h_{π}) = π!h_{λ(π)}.

2. Basis Change

Let Π_{n} be the lattice of all π ⊢ [n] ordered by refinement, i.e., if π = B_{1}/ … /B_{k} and σ = C_{1}/ … /C_{l} then π ≤ σ if each B_{i} is contained in some C_{j}.

Ex. We have

[figure: Π_{3} =; 1/2/3; 12/3; 13/2; 1/23; 123]

Let π ∧ σ be the greatest lower bound or meet of π and σ. Also let ˆ0 = 1/2/ … /n and μ denote the minimum and Möbius function of Π_{n}, respectively.

Theorem 3 (Doubilet) We have

\begin{aligned}(1) p_{π} & = & _{σ≥π}^{∑} m_{σ}, \\ (2) m_{π} & = & _{σ≥π}^{∑} μ(π, σ)p_{σ}, \\ (3) e_{π} & = & _{σ∧π=ˆ0}^{∑} m_{σ}, \\ (4) m_{π} & = & _{σ≥π}^{∑} \frac{μ(π, σ)}{μ(ˆ0, σ)} _{τ≤σ}^{∑} μ(τ, σ)e_{τ}. \end{aligned}

Proof (1) & (3) follow directly from the definitions.

(2) & (4) now follow by Möbius inversion.

3. MacMahon Symmetric Functions

Given variable sets ẋ = {ẋ_{1}, ẋ_{2}, …}, ẍ = {ẍ_{1}, ẍ_{2}, …}, …, x^{(n)} = {x_{1}^{(n)}, x_{2}^{(n)}, …}, we let g ∈ S_{m} act on a f(ẋ, ẍ, …, x^{(n)}) ∈ ℚ[[ẋ, ẍ, …, x^{(n)}]] diagonally:

gf(ẋ_{1}, ẍ_{1}, …, ẋ_{2}, ẍ_{2}, …) = f(ẋ_{g1}, ẍ_{g1}, …, ẋ_{g2}, ẍ_{g2}, …).

The monomial

ẋ_{1}^{a_{1}}ẍ_{1}^{b_{1}} ⋯ x_{1}^{(n)c_{1}} ẋ_{2}^{a_{2}}ẍ_{2}^{b_{2}} ⋯ x_{2}^{(n)c_{2}} ⋯

has multiexponent

\begin{aligned}λ⃗ & = & \{λ^{1}, λ^{2}, …\} \\ & := & \{[a_{1}, b_{1}, …, c_{1}], [a_{2}, b_{2}, …, c_{2}], …\} \end{aligned}

as well as multidegree

\begin{aligned}m⃗ & = & [m_{1}, m_{2}, …, m_{n}] \\ & := & [a_{1}, b_{1}, …, c_{1}] + [a_{2}, b_{2}, …, c_{2}] + ⋯ \end{aligned}

and we write λ⃗ ⊢ m⃗.

Ex. For ẋ_{1}^{2} ẍ_{1}ẋ_{2}^{3} we have

λ⃗ = {[2, 1], [3, 0]}  and m⃗ = [2, 1] + [3, 0] = [5, 1].

The algebra of MacMahon symmetric functions, M, is the set of all elements in ℚ[[ẋ, ẍ, …, x^{(n)}]] which are symmetric and of bounded multidegree. Bases for M are indexed by vector partitions λ⃗.

Define the monomial MacMahon SF by mλ⃗ = sum of all monomials with multiexponent λ⃗ . Define power sum & elementary MacMahon SFs by

p_{[a,b,...,c]} = ẋ_{1}^{a}ẍ_{1}^{b} ⋯ x_{1}^{(n)c} + ẋ_{2}^{a}ẍ_{2}^{b} ⋯ x_{2}^{(n)c} ⋯
e_{[a,b,...,c]} = ∑(multidegree [a, b, …, c] dottings

of squarefree monomials) ,

h_{[a,b,...,c]} = ∑(multidegree [a, b, …, c] dottings

of all monomials) ,

and multiplicativity. (In h, repetitions of a variable are considered distinct, leading to multiplicities.)

Ex. For λ⃗ = {[2, 1], [3, 0]} we have

m_{{[2,1],[3,0]}} = ẋ_{1}^{2} ẍ_{1}ẋ_{2}^{3} + ẋ_{1}^{3}ẋ_{2}^{2} ẍ_{2} + ⋯
p_{{[2,1],[3,0]}} = (ẋ_{1}^{2} ẍ_{1} + ẋ_{2}^{2} ẍ_{2} + ⋯)(ẋ_{1}^{3} + ẋ_{2}^{3} + ⋯)
e_{{[2,1],[3,0]}} = (ẋ_{1} ẋ_{2} ẍ_{3} + ẋ_{1} ẍ_{2} ẋ_{3} + ẍ_{1} ẋ_{2} ẋ_{3} + ⋯)
(ẋ_{1} ẋ_{2} ẋ_{3} + ẋ_{1} ẋ_{2} ẋ_{4} + ⋯)
h_{{[2,1],[3,0]}} = (3ẋ_{1}^{2} ẍ_{1} + ẋ_{1}^{2} ẍ_{2} + 2ẋ_{1} ẍ_{1} ẋ_{2} + ⋯)
(ẋ_{1}^{3} + ẋ_{1}^{2} ẋ_{2} + ẋ_{1} ẋ2ẋ_{3} + ⋯)

Let ⟨·⟩ denote vector space span and consider

M_{[1^{n}]} = ⟨mλ⃗ : all λ⃗ ⊢ [1^{n}] ⟩ .

Ex. For n = 3 we have

\begin{matrix}M_{[1,1,1]} = ⟨m_{\{[1,1,1]\}} , m_{\{[1,1,0],[0,0,1]\}} , m_{\{[1,0,1],[0,1,0]\}} , \\ m_{\{[0,1,1],[1,0,0]\}} , m_{\{[1,0,0],[0,1,0],[0,0,1]\}} ⟩. \end{matrix}

Theorem 4 (Rosas) The map

Φ : _{n≥0}^{⨁} M_{[1^{n}]} → Π(x)

given by linearly extending

ẋ_{i}ẍ_{j} ⋯ x_{k}^{(n)} ↦^{Φ} x_{i}x_{j} ⋯ x_{k}

is an isomorphism of vector spaces. In fact

b_{{λ^{1},λ^{2},...,λ^{l}}} ↦^{Φ} b_{B_{1}/B_{2}/.../B_{l}}

where b = m, p, e or h and λ^{i} is the characteristic vector of B_{i}.

Ex. m_{{[1,0,1],[0,1,0]}} ↦^{Φ} m_{13/2} since

\begin{matrix}ẋ_{1} x^{...}_{1} ẍ_{2} + ẋ_{2} x^{...}_{2} ẍ_{1} + ẋ_{1} x^{...}_{1} ẍ_{3} + ⋯ \\ ↦^{Φ} x_{1}x_{2}x_{1} + x_{2}x_{1}x_{2} + x_{1}x_{3}x_{1} + ⋯ \end{matrix}

4. Schur Symmetric Functions

A partition λ = (λ_{1}, λ_{2}, …, λ_{l}) has a shape, also denoted λ, consisting of l left-justified rows with λ_{i} dots in row i.

Ex. Partition λ = (3, 3, 2, 1) has shape

λ = \begin{matrix}• & • & • \\ • & • & • \\ • & • \\ • \end{matrix} .

A (semistandard) Young tableau T of shape λ, written λ(T) = λ, is obtained by replacing each dot of the shape of λ with a positive integer so that rows weakly increase and columns strictly increase.

Ex. A Young tableau of shape (3, 3, 2, 1) is

T = 1 1 3 2 2 5 3 6 5 .

The Schur function, s_{λ}, is

s_{λ} = _{λ(T)=λ}^{∑} M_{T} where M_{T} = _{i∈T}^{∏} x_{i}.

Ex. If λ = (2, 1) then

\begin{aligned}T & : & 1 1 2 & , & 1 2 2 & , & … & , & 1 2 3 & , & 1 3 2 & , & … \\ s_{(2,1)} & = & x_{1}^{2}x_{2} & + & x_{1}x_{2}^{2} & + & ⋯ & + & x_{1}x_{2}x_{3} & + & x_{1}x_{2}x_{3} & + & ⋯ \end{aligned}

If λ, m⃗ ⊢ d then a dotted Young tableau Ṫ of shape λ and multidegree m⃗ is obtained from T by putting one dot on m_{1} elements of T, two dots on m_{2} elements of T, etc. The corresponding MacMahon Schur function is

Sm⃗ ; λ = _{λ(Ṫ)=λ}^{∑} MṪ where MṪ = _{i^{(j)}∈T}^{∏} x_{i}^{(j)} .

Ex. If λ = (2, 1) and m⃗ = [1, 1, 1] then

\begin{aligned}Ṫ & : & ˙1 ¨1 ; 2^{...} & , & ¨1 ˙1 ; 2^{...} & , & … & , & 1^{...} ¨1 ; ˙2 & , & … \\ S_{(2,1)}^{[1,1,1]} & = & ẋ_{1} ẍ_{1} x^{...}_{2} & + & ẋ_{1} ẍ_{1} x^{...}_{2} & + & ⋯ & + & ẍ_{1} x^{...}_{1} ẋ_{2} & + & ⋯ \end{aligned}

The MacMahon Schur functions have many of the same properties as do the regular Schur functions, such as a Robinson-Schensted-Knuth correspondence.

Theorem 5 (Jacobi-Trudi Determinant) Given a partition λ = (λ_{1}, λ_{2}, …, λ_{l}), we have

s_{λ} = |h_{λ_{i}−i+j} |.

The analogue of this theorem for MacMahon symmetric functions is as follows.

Theorem 6 (R-S) Given a partition λ and vector m⃗ with λ, m⃗ ⊢ n, we have

Sm⃗ ; λ = T m⃗ |_{q⃗ ⊢λ_{i}−i+j}^{∑} hq⃗ |

where T m⃗ extracts the terms of multidegree m⃗ from the determinant.

Note that when m⃗ has only one component, then this reduces to the ordinary Jacobi-Trudi Theorem. And when m⃗ = [1^{n}] then this gives a noncommuting variable analogue.

Ex. Consider λ = (2, 1). If m⃗ = [3], then

s_{(2,1)}^{[3]} = T^{[3]} | \begin{matrix}_{q⃗ ⊢2}^{∑} hq⃗ & _{q⃗ ⊢3}^{∑} hq⃗ \\ _{q⃗ ⊢0}^{∑} hq⃗ & _{q⃗ ⊢1}^{∑} hq⃗ \end{matrix} |
= h_{[2]}h_{[1]} − h_{[3]}h_{[0]}
= h_{(2,1)} − h_{3}

as normal. Now if m⃗ = [1, 1, 1], then

s_{(2,1)}^{[1,1,1]} = T^{[1,1,1]} | \begin{matrix}_{q⃗ ⊢2}^{∑} hq⃗ & _{q⃗ ⊢3}^{∑} hq⃗ \\ _{q⃗ ⊢0}^{∑} hq⃗ & _{q⃗ ⊢1}^{∑} hq⃗ \end{matrix} |
= T^{[1,1,1]} {(h_{[1,1,0]} + h_{[1,0,1]} + h_{[0,1,1]} )
·(h_{[1,0,0]} + h_{[0,1,0]} + h_{[0,0,1]} )
−h_{[1,1,1]} h_{[0,0,0]} }
= h_{[1,1,0]} h_{[0,0,1]} + h_{[1,0,1]} h_{[0,1,0]}
+h_{[0,1,1]} h_{[1,0,0]} − h_{[1,1,1]} .

5. Open Problems

A. What is the analogue of the quotient of alternants definition of a Schur function for the S_{λ}^{[1^{n}]}?

B. We have only defined S_{λ}^{[1^{n}]} for λ an integer partition. Is there some way to define noncommuting variable functions S_{π}^{[1^{n}]} for all set partitions π?

C. What does all this have to do with representation theory?

D. Can one make further progress on the (3+1)- free conjecture of Stanley and Stembridge using symmetric functions in noncommuting variables?