Tensor algebras, words, and invariants of polynomials in non-commutative variables

Tensor algebras, words, and invariants of polynomials in non-commutative variables Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) November 24, 2009 Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 1 / 31 Commutative starting point Let Vbe a k-vector space with basis {x1,x2,...,xn}. Then the symmetric algebra S(V) on Vover k S(V) = k⊕V⊕S2(V)⊕S3(V)⊕··· ≃k[x1,x2,...,xn]. Let Gbe a finite subgroup of GL(V). The invariant algebra of Gis S(V)G=k⊕VG⊕S2(V)G⊕S3(V)G⊕··· ≃k[x1,x2,...,xn]G and its Hilbert-Poincar´e series is P(S(V)G) = X d≥0 dim(Sd(V)G)qd. Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 2 / 31 Commutative starting point Let Vbe a k-vector space with basis {x1,x2,...,xn}. Then the symmetric algebra S(V) on Vover k S(V) = k⊕V⊕S2(V)⊕S3(V)⊕··· ≃k[x1,x2,...,xn]. Let Gbe a finite subgroup of GL(V). The invariant algebra of Gis S(V)G=k⊕VG⊕S2(V)G⊕S3(V)G⊕··· ≃k[x1,x2,...,xn]G and its Hilbert-Poincar´e series is P(S(V)G) = X d≥0 dim(Sd(V)G)qd. Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 2 / 31 Commutative starting point Theorem (Molien, Noether, Sheppard-Todd-Chevalley) V finite dimensional k-vector space G finite subroup of GL(V) i) If char k = 0, then P(S(V)G) = 1 |G|X g∈G 1 det(I−gq). ii) As a k-algebra, S(V)Gis finitely generated. iii) If char k = 0, then S(V)Gis a free commutative k-algebra (with a homogeneous free generating set) if and only if G is generated by pseudo-reflections. Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 3 / 31 Direction: Non-Commutative world The tensor algebra T(V) on Vover k T(V) = k⊕V⊕V⊗2⊕V⊗3⊕··· ≃khx1,x2,...,xni, where Td(V) = V⊗d=V⊗V⊗···⊗V≃khx1,x2,...,xnid. The invariant algebra of Gis T(V)G=k⊕VG⊕(V⊗2)G⊕(V⊗3)G⊕··· ≃khx1,x2,...,xniG and its Hilbert-Poincar´e series is P(T(V)G) = X d≥0 dim((V⊗d)G)qd. Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 4 / 31 Direction: Non-Commutative world The tensor algebra T(V) on Vover k T(V) = k⊕V⊕V⊗2⊕V⊗3⊕··· ≃khx1,x2,...,xni, where Td(V) = V⊗d=V⊗V⊗···⊗V≃khx1,x2,...,xnid. The invariant algebra of Gis T(V)G=k⊕VG⊕(V⊗2)G⊕(V⊗3)G⊕··· ≃khx1,x2,...,xniG and its Hilbert-Poincar´e series is P(T(V)G) = X d≥0 dim((V⊗d)G)qd. Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 4 / 31 Direction: Non-Commutative world Theorem (Dick-Formaneck, Kharchenko, Lane) V finite dimensional k-vector space G finite subroup of GL(V) i) If char k = 0, then P(T(V)G) = 1 |G|X g∈G 1 1−Tr(g)q. ii) As a k-algebra, T(V)Gfinitely generated ⇐⇒ G is scalar. iii) T(V)Gis a free associative k-algebra (with a homogeneous free generating set). Is there a finite description of the dimensions and generators of T(V)Gwhen Gis not scalar? Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 5 / 31 Direction: Non-Commutative world Theorem (Dick-Formaneck, Kharchenko, Lane) V finite dimensional k-vector space G finite subroup of GL(V) i) If char k = 0, then P(T(V)G) = 1 |G|X g∈G 1 1−Tr(g)q. ii) As a k-algebra, T(V)Gfinitely generated ⇐⇒ G is scalar. iii) T(V)Gis a free associative k-algebra (with a homogeneous free generating set). Is there a finite description of the dimensions and generators of T(V)Gwhen Gis not scalar? Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 5 / 31 Some Examples Let V=L{x1,x2,...,xn} ≃ V(n−1,1) ⊕V(n)with the permutation action on the variables. Then T(V)≃khx1,x2,...,xni and T(V)Sn= symmetric functions in non-commutative variables. Let V=L{y1,y2,...,yn−1} ≃ V(n−1,1) where yk=xk−xk+1 Then T(V)≃khy1,y2,...,yn−1i Poincar`e series counted by oscillating tableaux (see talk by Goupil) Let V=L{x1,x2}acting on the Dihedral group generated by elements rn=s2=1=rsrs acts on the two elements x1,x2. T(V) = khx1,x2i Poincar`e series counted by ??? Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 6 / 31 Cayley graph of S3 Γ(S3,{(12),(132)}) : Cayley graph of S3 Γ(S3,{(12),(132)}): (1) (123) (132) (12) (23) (13) Anouk Bergeron-Brlek (Joint work with C. Hohlweg and M. Zabrocki) ()Words and polynomial invariants of finite groups in non-commutative variablesNovember 17, 2009 8 / 35 Path: e= (1)−→(132)−→(123)−→(1)−→(12)−→(1)−→(132)−→(23) Word: bbbaabadoes cross the identity Path: e= (1)−→(132)−→(23)−→(12)−→(13)−→(123) Word: babbadoes not cross the identity Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 9 / 31 Cayley graph of S3 Γ(S3,{(12),(132)}) : Cayley graph of S3 Γ(S3,{(12),(132)}): (1) (123) (132) (12) (23) (13) Anouk Bergeron-Brlek (Joint work with C. Hohlweg and M. Zabrocki) ()Words and polynomial invariants of finite groups in non-commutative variablesNovember 17, 2009 8 / 35 Path: e= (1)−→(132)−→(123)−→(1)−→(12)−→(1)−→(132)−→(23) Word: bbbaabadoes cross the identity Path: e= (1)−→(132)−→(23)−→(12)−→(13)−→(123) Word: babbadoes not cross the identity Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 9 / 31 Cayley graph of S3 Γ(S3,{(12),(132)}) : Cayley graph of S3 Γ(S3,{(12),(132)}): (1) (123) (132) (12) (23) (13) Anouk Bergeron-Brlek (Joint work with C. Hohlweg and M. Zabrocki) ()Words and polynomial invariants of finite groups in non-commutative variablesNovember 17, 2009 8 / 35 Path: e= (1)−→(132)−→(123)−→(1)−→(12)−→(1)−→(132)−→(23) Word: bbbaabadoes cross the identity Path: e= (1)−→(132)−→(23)−→(12)−→(13)−→(123) Word: babbadoes not cross the identity Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 9 / 31 Cayley graph of S3 Γ(S3,{(12),(132)}) : Cayley graph of S3 Γ(S3,{(12),(132)}): (1) (123) (132) (12) (23) (13) Anouk Bergeron-Brlek (Joint work with C. Hohlweg and M. Zabrocki) ()Words and polynomial invariants of finite groups in non-commutative variablesNovember 17, 2009 8 / 35 Path: e= (1)−→(132)−→(123)−→(1)−→(12)−→(1)−→(132)−→(23) Word: bbbaabadoes cross the identity Path: e= (1)−→(132)−→(23)−→(12)−→(13)−→(123) Word: babbadoes not cross the identity Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 9 / 31 Partitions and Tableaux Apartition λof a positive integer nis λ1≥λ2≥. . . ≥λ`>0 such that n=|λ|=λ1+λ2+. . . +λ`.The partitions of 3 are (1,1,1) (2,1) (3) Atableau of shape λ`n, is a filling of λwith values in {1,2,...,n}. A tableau is standard if its entries form an increasing sequence along each line and each column. STabnis the set of standard tableau with nboxes. STab3=(3 2 1,2 1 3 ,3 1 2 ,1 2 3 ) Robinson-Schensted correspondence σ←→ (P(σ),Q(σ)) P(σ)insertion tableau and Q(σ)recording tableau. Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 10 / 31 Partitions and Tableaux Apartition λof a positive integer nis λ1≥λ2≥. . . ≥λ`>0 such that n=|λ|=λ1+λ2+. . . +λ`.The partitions of 3 are (1,1,1) (2,1) (3) Atableau of shape λ`n, is a filling of λwith values in {1,2,...,n}. A tableau is standard if its entries form an increasing sequence along each line and each column. STabnis the set of standard tableau with nboxes. STab3=(3 2 1,2 1 3 ,3 1 2 ,1 2 3 ) Robinson-Schensted correspondence σ←→ (P(σ),Q(σ)) P(σ)insertion tableau and Q(σ)recording tableau. Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 10 / 31 Partitions and Tableaux Apartition λof a positive integer nis λ1≥λ2≥. . . ≥λ`>0 such that n=|λ|=λ1+λ2+. . . +λ`.The partitions of 3 are (1,1,1) (2,1) (3) Atableau of shape λ`n, is a filling of λwith values in {1,2,...,n}. A tableau is standard if its entries form an increasing sequence along each line and each column. STabnis the set of standard tableau with nboxes. STab3=(3 2 1,2 1 3 ,3 1 2 ,1 2 3 ) Robinson-Schensted correspondence σ←→ (P(σ),Q(σ)) P(σ)insertion tableau and Q(σ)recording tableau. Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 10 / 31 General Theorem for Sn {Vλ}λ`nforms a complete system of irreducible Sn-modules. Theorem The dimension of Td(V(n−1,1))Snis equal to the number of words of length d which reduce to e in the Cayley graph Γ(Sn,{(12),(132),...,(1 n··· 432)}). dim(T4(V(2,1))S3) = number of words of length 4 which reduce to ein Cayley graph of S3 Γ(S3,{(12),(132)}): (1) (123) (132) (12) (23) (13) Anouk Bergeron-Brlek (Joint work with C. Hohlweg and M. Zabrocki) ()Words and polynomial invariants of finite groups in non-commutative variablesNovember 17, 2009 8 / 35 =|{aaaa,abab,baba}| Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 11 / 31 Free generators for T(V(n−1,1))Sn Proposition The number of free generators of T(V(n−1,1))Snas an algebra are counted by the words in Γ(Sn,{(12),(132), . . . , (1 n··· 432)})which reduce to the identity without crossing it . The free generators of T(V(2,1))S3are counted by aa bbb abab baba abbba baabb bbaab abaaab abbabb baaaba babbab bbabba ··· 1 1 2 3 5 ··· the Fibonacci numbers. Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 12 / 31 Free generators for T(V(n−1,1))Sn Proposition The number of free generators of T(V(n−1,1))Snas an algebra are counted by the words in Γ(Sn,{(12),(132), . . . , (1 n··· 432)})which reduce to the identity without crossing it . The free generators of T(V(2,1))S3are counted by aa bbb abab baba abbba baabb bbaab abaaab abbabb baaaba babbab bbabba ··· 1 1 2 3 5 ··· the Fibonacci numbers. Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 12 / 31 Key Lemma Lemma The coefficient of e in d{1}d= ((12) + (132) + . . . + (1 n··· 432))dis equal to the number of words of length d which reduce to e in Γ(Sn,{(12),(132),...,(1 n··· 432)}). Consider Γ(S3,{(12),(132)}) and let a= (12) and b= (132). Then d{1}4= (a+b)4=3e+ 2 (12) + 3 (23) + 3 (123) + 2 (132) + 3 (13) Cayley graph of S3 Γ(S3,{(12),(132)}): (1) (123) (132) (12) (23) (13) Anouk Bergeron-Brlek (Joint work with C. Hohlweg and M. Zabrocki) ()Words and polynomial invariants of finite groups in non-commutative variablesNovember 17, 2009 8 / 35 Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 16 / 31 Key Lemma Lemma The coefficient of e in d{1}d= ((12) + (132) + . . . + (1 n··· 432))dis equal to the number of words of length d which reduce to e in Γ(Sn,{(12),(132),...,(1 n··· 432)}). Consider Γ(S3,{(12),(132)}) and let a= (12) and b= (132). Then d{1}4= (a+b)4=3e+ 2 (12) + 3 (23) + 3 (123) + 2 (132) + 3 (13) Cayley graph of S3 Γ(S3,{(12),(132)}): (1) (123) (132) (12) (23) (13) Anouk Bergeron-Brlek (Joint work with C. Hohlweg and M. Zabrocki) ()Words and polynomial invariants of finite groups in non-commutative variablesNovember 17, 2009 8 / 35 Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 16 / 31 More generally: Multiplicity of Vλin (V(n−1,1))⊗d Theorem Let λ`n. The multiplicity of V λin (V(n−1,1))⊗dis X t∈STabn sh(t)=λ |w(σt,d; Γ)|, where w(σt,d; Γ) is the set of words of length d which reduce to σtin Γ = Γ(Sn,{(12),(132),...,(1 n··· 432)})and σt∈Snis such that Q(σt) = t. In particular, the multiplicity of the trivial is |w(e,d; Γ)|. Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 17 / 31 Decomposition of the S3-module (V(2,1))⊗4 Consider Γ = Γ(S3,{(12),(132)}) and set a= (12) and b= (132). Decomposition of the S3-module (V(2,1))⊗4 Consider Γ=Γ(S3,{(12),(132)}) and set a= (12) and b= (132). e(123) (132) (12) (23) (13) ! RS 123 3 1 2 2 1 3 2 1 3 3 1 2 3 2 1 V(3) :|w(σ1 2 3 ,4; Γ)|=|{aaaa,abab,baba}| =3 Anouk Bergeron-Brlek (Joint work with C. Hohlweg and M. Zabrocki) ()Words and polynomial invariants of finite groups in non-commutative variablesNovember 17, 2009 17 / 35 Decomposition of the S3-module (V(2,1))⊗4 Consider Γ=Γ(S3,{(12),(132)}) and set a= (12) and b= (132). e(123) (132) (12) (23) (13) ! RS 123 3 1 2 2 1 3 2 1 3 3 1 2 3 2 1 Anouk Bergeron-Brlek (Joint work with C. Hohlweg and M. Zabrocki) ()Words and polynomial invariants of finite groups in non-commutative variablesNovember 17, 2009 17 / 35 V(3) :|w(σ1 2 3 ,4; Γ)|=|{aaaa,abab,baba}| = 3 V(2,1) :|w(σ3 1 2 ,4; Γ)|+|w(σ2 1 3 ,4; Γ)|=|{aaba,baaa,bbab}| +|{abbb,bbba}| = 5 V(1,1,1) :|w(σ3 2 1 ,4; Γ)|=|{aaab,abaa,babb}| = 3 (V(2,1))⊗4= 3 V(3) ⊕5V(2,1) ⊕3V(1,1,1) Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 18 / 31 Decomposition of the S3-module (V(2,1))⊗4 Consider Γ = Γ(S3,{(12),(132)}) and set a= (12) and b= (132). Decomposition of the S3-module (V(2,1))⊗4 Consider Γ=Γ(S3,{(12),(132)}) and set a= (12) and b= (132). e(123) (132) (12) (23) (13) ! RS 123 3 1 2 2 1 3 2 1 3 3 1 2 3 2 1 V(3) :|w(σ1 2 3 ,4; Γ)|=|{aaaa,abab,baba}| =3 Anouk Bergeron-Brlek (Joint work with C. Hohlweg and M. Zabrocki) ()Words and polynomial invariants of finite groups in non-commutative variablesNovember 17, 2009 17 / 35 Decomposition of the S3-module (V(2,1))⊗4 Consider Γ=Γ(S3,{(12),(132)}) and set a= (12) and b= (132). e(123) (132) (12) (23) (13) ! RS 123 3 1 2 2 1 3 2 1 3 3 1 2 3 2 1 Anouk Bergeron-Brlek (Joint work with C. Hohlweg and M. Zabrocki) ()Words and polynomial invariants of finite groups in non-commutative variablesNovember 17, 2009 17 / 35 V(3) :|w(σ1 2 3 ,4; Γ)|=|{aaaa,abab,baba}| = 3 V(2,1) :|w(σ3 1 2 ,4; Γ)|+|w(σ2 1 3 ,4; Γ)|=|{aaba,baaa,bbab}| +|{abbb,bbba}| = 5 V(1,1,1) :|w(σ3 2 1 ,4; Γ)|=|{aaab,abaa,babb}| = 3 (V(2,1))⊗4= 3 V(3) ⊕5V(2,1) ⊕3V(1,1,1) Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 18 / 31 Decomposition of the S3-module (V(2,1))⊗4 Consider Γ = Γ(S3,{(12),(132)}) and set a= (12) and b= (132). Decomposition of the S3-module (V(2,1))⊗4 Consider Γ=Γ(S3,{(12),(132)}) and set a= (12) and b= (132). e(123) (132) (12) (23) (13) ! RS 123 3 1 2 2 1 3 2 1 3 3 1 2 3 2 1 V(3) :|w(σ1 2 3 ,4; Γ)|=|{aaaa,abab,baba}| =3 Anouk Bergeron-Brlek (Joint work with C. Hohlweg and M. Zabrocki) ()Words and polynomial invariants of finite groups in non-commutative variablesNovember 17, 2009 17 / 35 Decomposition of the S3-module (V(2,1))⊗4 Consider Γ=Γ(S3,{(12),(132)}) and set a= (12) and b= (132). e(123) (132) (12) (23) (13) ! RS 123 3 1 2 2 1 3 2 1 3 3 1 2 3 2 1 Anouk Bergeron-Brlek (Joint work with C. Hohlweg and M. Zabrocki) ()Words and polynomial invariants of finite groups in non-commutative variablesNovember 17, 2009 17 / 35 V(3) :|w(σ1 2 3 ,4; Γ)|=|{aaaa,abab,baba}| = 3 V(2,1) :|w(σ3 1 2 ,4; Γ)|+|w(σ2 1 3 ,4; Γ)|=|{aaba,baaa,bbab}| +|{abbb,bbba}| = 5 V(1,1,1) :|w(σ3 2 1 ,4; Γ)|=|{aaab,abaa,babb}| = 3 (V(2,1))⊗4= 3 V(3) ⊕5V(2,1) ⊕3V(1,1,1) Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 18 / 31 Decomposition of the S3-module (V(2,1))⊗4 Consider Γ = Γ(S3,{(12),(132)}) and set a= (12) and b= (132). Decomposition of the S3-module (V(2,1))⊗4 Consider Γ=Γ(S3,{(12),(132)}) and set a= (12) and b= (132). e(123) (132) (12) (23) (13) ! RS 123 3 1 2 2 1 3 2 1 3 3 1 2 3 2 1 V(3) :|w(σ1 2 3 ,4; Γ)|=|{aaaa,abab,baba}| =3 Anouk Bergeron-Brlek (Joint work with C. Hohlweg and M. Zabrocki) ()Words and polynomial invariants of finite groups in non-commutative variablesNovember 17, 2009 17 / 35 Decomposition of the S3-module (V(2,1))⊗4 Consider Γ=Γ(S3,{(12),(132)}) and set a= (12) and b= (132). e(123) (132) (12) (23) (13) ! RS 123 3 1 2 2 1 3 2 1 3 3 1 2 3 2 1 Anouk Bergeron-Brlek (Joint work with C. Hohlweg and M. Zabrocki) ()Words and polynomial invariants of finite groups in non-commutative variablesNovember 17, 2009 17 / 35 V(3) :|w(σ1 2 3 ,4; Γ)|=|{aaaa,abab,baba}| = 3 V(2,1) :|w(σ3 1 2 ,4; Γ)|+|w(σ2 1 3 ,4; Γ)|=|{aaba,baaa,bbab}| +|{abbb,bbba}| = 5 V(1,1,1) :|w(σ3 2 1 ,4; Γ)|=|{aaab,abaa,babb}| = 3 (V(2,1))⊗4= 3 V(3) ⊕5V(2,1) ⊕3V(1,1,1) Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 18 / 31 Decomposition of the S3-module (V(2,1))⊗4 Consider Γ = Γ(S3,{(12),(132)}) and set a= (12) and b= (132). Decomposition of the S3-module (V(2,1))⊗4 Consider Γ=Γ(S3,{(12),(132)}) and set a= (12) and b= (132). e(123) (132) (12) (23) (13) ! RS 123 3 1 2 2 1 3 2 1 3 3 1 2 3 2 1 V(3) :|w(σ1 2 3 ,4; Γ)|=|{aaaa,abab,baba}| =3 Anouk Bergeron-Brlek (Joint work with C. Hohlweg and M. Zabrocki) ()Words and polynomial invariants of finite groups in non-commutative variablesNovember 17, 2009 17 / 35 Decomposition of the S3-module (V(2,1))⊗4 Consider Γ=Γ(S3,{(12),(132)}) and set a= (12) and b= (132). e(123) (132) (12) (23) (13) ! RS 123 3 1 2 2 1 3 2 1 3 3 1 2 3 2 1 Anouk Bergeron-Brlek (Joint work with C. Hohlweg and M. Zabrocki) ()Words and polynomial invariants of finite groups in non-commutative variablesNovember 17, 2009 17 / 35 V(3) :|w(σ1 2 3 ,4; Γ)|=|{aaaa,abab,baba}| = 3 V(2,1) :|w(σ3 1 2 ,4; Γ)|+|w(σ2 1 3 ,4; Γ)|=|{aaba,baaa,bbab}| +|{abbb,bbba}| = 5 V(1,1,1) :|w(σ3 2 1 ,4; Γ)|=|{aaab,abaa,babb}| = 3 (V(2,1))⊗4= 3 V(3) ⊕5V(2,1) ⊕3V(1,1,1) Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 18 / 31 Kronecker coefficients in general This idea can be used much more generally than I am considering here. All we need is an embedding of the algebra of representations inside of a group algebra with non-negative integer coefficients and we get for free a combinatorial interpretation of Kronecker coefficients. We already have the descent algebra where the representation ring indexed by ribbon shapes lie (and in particular hooks). Example: Combinatorial interpretation for Kronecker products with hook shapes. s(n−k,1k)∗s(n−`,1`)=X (σ,τ) sλ(Q(στ)) where the sum is over (σ, τ) such that Des(σ) = {1,2,...,k}and Des(τ) = {1,2, . . . , `}and στ is an involution. Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 19 / 31 Kronecker coefficients in general This idea can be used much more generally than I am considering here. All we need is an embedding of the algebra of representations inside of a group algebra with non-negative integer coefficients and we get for free a combinatorial interpretation of Kronecker coefficients. We already have the descent algebra where the representation ring indexed by ribbon shapes lie (and in particular hooks). Example: Combinatorial interpretation for Kronecker products with hook shapes. s(n−k,1k)∗s(n−`,1`)=X (σ,τ) sλ(Q(στ)) where the sum is over (σ, τ) such that Des(σ) = {1,2,...,k}and Des(τ) = {1,2, . . . , `}and στ is an involution. Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 19 / 31 Applications Let [n] = {1,2, . . . n}. A set partition of [n], denoted by A`[n], is a family A1,A2,...,Ak⊆[n] such that A1∪A2∪. . . ∪Ak= [n]. A set partition Ais splitable if A=B◦C, where Band Care non empty and B◦C=({B1∪(C1+n),...,Bk∪(Ck+n),(Ck+1 +n),...,(C`+n)}if k≤` {B1∪(C1+n),...,B`∪(C`+n),B`+1,...,Bk}if k> `. The set partitions of [3] are {{1},{2},{3}} nonsplitable {{1},{2,3}} nonsplitable {{1,2},{3}} ={{1}}◦{{1},{2}} {{1,3},{2}} ={{1},{2}}◦{{1}} {{1,2,3}} ={{1}}◦{{1}}◦{{1}} Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 21 / 31 Invariant algebra T(V(n)⊕V(n−1,1))Sn≃QhXniSn T(V(n)⊕V(n−1,1))Sn≃QhXniSnis the algebra of Symmetric polynomials in non-commutative variables (Wolf, Rosas and Sagan) QhXniSn=L{mA(Xn)|Aset partition with at most nparts} QhXniSnfreely generated by {mA(Xn)|Anon-splitable set partition with at most nparts }(Wolf) Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 22 / 31 Invariant algebra T(V(n)⊕V(n−1,1))Sn≃QhXniSn Corollary The dimension of ((V(n)⊕V(n−1,1))⊗d)Sn≃QhXniSn dis equal to the number of words of length d which reduce to the identity in Γ(Sn,{e,(12),(132), . . . , (1 n··· 432)}). Basis for Qhx1,x2,x3iS3 3: m{{1},{2},{3}} =x1x2x3+x2x1x3+x1x3x2+x2x3x1+x3x1x2+x3x2x1, m{{1,2},{3}} =x1x1x2+x1x1x3+x2x2x1+x2x2x3+x3x3x1+x3x3x2, m{{1,3},{2}} =x1x2x1+x1x3x1+x2x1x2+x2x3x2+x3x1x3+x3x2x3, m{{1},{2,3}} =x1x2x2+x1x3x3+x2x1x1+x2x3x3+x3x1x1+x3x2x2, m{{1,2,3}} =x1x1x1+x2x2x2+x3x3x3. Words of length 3 which reduce to the identity in Γ(S3,{e,(12),(132)}): {bbb,aae,aea,eaa,eee}. Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 23 / 31 Invariant algebra T(V(n)⊕V(n−1,1))Sn≃QhXniSn Corollary The dimension of ((V(n)⊕V(n−1,1))⊗d)Sn≃QhXniSn dis equal to the number of words of length d which reduce to the identity in Γ(Sn,{e,(12),(132), . . . , (1 n··· 432)}). Basis for Qhx1,x2,x3iS3 3: m{{1},{2},{3}} =x1x2x3+x2x1x3+x1x3x2+x2x3x1+x3x1x2+x3x2x1, m{{1,2},{3}} =x1x1x2+x1x1x3+x2x2x1+x2x2x3+x3x3x1+x3x3x2, m{{1,3},{2}} =x1x2x1+x1x3x1+x2x1x2+x2x3x2+x3x1x3+x3x2x3, m{{1},{2,3}} =x1x2x2+x1x3x3+x2x1x1+x2x3x3+x3x1x1+x3x2x2, m{{1,2,3}} =x1x1x1+x2x2x2+x3x3x3. Words of length 3 which reduce to the identity in Γ(S3,{e,(12),(132)}): {bbb,aae,aea,eaa,eee}. Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 23 / 31 Invariant algebra T(V(n)⊕V(n−1,1))Sn≃QhXniSn Corollary The dimension of ((V(n)⊕V(n−1,1))⊗d)Sn≃QhXniSn dis equal to the number of words of length d which reduce to the identity in Γ(Sn,{e,(12),(132), . . . , (1 n··· 432)}). Basis for Qhx1,x2,x3iS3 3: m{{1},{2},{3}} =x1x2x3+x2x1x3+x1x3x2+x2x3x1+x3x1x2+x3x2x1, m{{1,2},{3}} =x1x1x2+x1x1x3+x2x2x1+x2x2x3+x3x3x1+x3x3x2, m{{1,3},{2}} =x1x2x1+x1x3x1+x2x1x2+x2x3x2+x3x1x3+x3x2x3, m{{1},{2,3}} =x1x2x2+x1x3x3+x2x1x1+x2x3x3+x3x1x1+x3x2x2, m{{1,2,3}} =x1x1x1+x2x2x2+x3x3x3. Words of length 3 which reduce to the identity in Γ(S3,{e,(12),(132)}): {bbb,aae,aea,eaa,eee}. Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 23 / 31 Free generators for T(V(n)⊕V(n−1,1))Sn Proposition The number of free generators of T(V(n)⊕V(n−1,1))Snas an algebra are counted by the words which reduce to the identity without crossing it in Γ(Sn,{e,(12),(132), . . . , (1 n··· 432)}). The free generators of T(V(3) ⊕V(2,1))S3are counted by eaa bbb aea abab baba bebb bbeb aeea abbbabeaba baabb baeba bbaab babea aebab beebb abeab bebeb abaeb bbeeb aeeea . . . 1 1 2 5 13 ··· the odd indexed Fibonacci numbers. Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 24 / 31 Free generators for T(V(n)⊕V(n−1,1))Sn Proposition The number of free generators of T(V(n)⊕V(n−1,1))Snas an algebra are counted by the words which reduce to the identity without crossing it in Γ(Sn,{e,(12),(132), . . . , (1 n··· 432)}). The free generators of T(V(3) ⊕V(2,1))S3are counted by eaa bbb aea abab baba bebb bbeb aeea abbbabeaba baabb baeba bbaab babea aebab beebb abeab bebeb abaeb bbeeb aeeea . . . 1 1 2 5 13 ··· the odd indexed Fibonacci numbers. Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 24 / 31 Free generators for T(V(n)⊕V(n−1,1))Sn Proposition The number of free generators of T(V(n)⊕V(n−1,1))Snas an algebra are counted by the words which reduce to the identity without crossing it in Γ(Sn,{e,(12),(132), . . . , (1 n··· 432)}). The free generators of T(V(3) ⊕V(2,1))S3are counted by eaa bbb aea abab baba bebb bbeb aeea abbbabeaba baabb baeba bbaab babea aebab beebb abeab bebeb abaeb bbeeb aeeea . . . 1 1 2 5 13 ··· the odd indexed Fibonacci numbers. Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 24 / 31 Link between set partitions and words in Cayley graph Corollary The number of set partitions of [d]into at most n parts equals the number of words of length d which reduce to the identity in Γ(Sn,{e,(12),(132), . . . , (1 n··· 432)}). Corollary The number of nonsplitable set partitions of [d]into at most n parts equals the number of words of length d which reduce to the identity without crossing it in Γ(Sn,{e,(12),(132), . . . , (1 n··· 432)}). Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 25 / 31 Link between set partitions and words in Cayley graph Corollary The number of set partitions of [d]into at most n parts equals the number of words of length d which reduce to the identity in Γ(Sn,{e,(12),(132), . . . , (1 n··· 432)}). Corollary The number of nonsplitable set partitions of [d]into at most n parts equals the number of words of length d which reduce to the identity without crossing it in Γ(Sn,{e,(12),(132), . . . , (1 n··· 432)}). Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 25 / 31 Surjective algebra morphism from Q ⊂ ZDmto ZIrr(Dm) Dm={e,r,r2,...,rm−1,s,rs,r2s,...,rm−1s}. For m= 2keven, Q=L{e,rk,rs,rk+1s,r1−is+ri,r−i+ri+1s}1≤i≤k−1. Proposition Qis a subalgebra of ZDmand there is a surjective algebra morphism θ:Q −→ ZIrr(Dm) θ(e) = id θ(rs) =  θ(rk) = γ θ(rk+1s) = γ θ(r1−is+ri) = θ(r−i+ri+1s) = χi Mike Zabrocki (Joint work with A. Bergeron-Brlek and C. Hohlweg) ()Tensor algebras, words, and invariants of polynomials in non-commutative variablesNovember 24, 2009 31 / 31