############################################################################################ ############################################################################################ ############################################################################################ ## # ## Branching # ## Version 2.0 # ## # ## for Computing Constituents and Multiplicities of Restriction # ## and Induction of Characters of the Symmetric Groups # ## # ## # ## Developed by: Vahid Dabbaghian-Abdoly # ## Department of Mathematics, # ## Simon Fraser University, # ## Burnaby, BC Canada. # ## E-mail: vdabbagh@sfu.ca # ## Web Page: www.sfu.ca/~vdabbagh # ## # ############################################################################################ ############################################################################################ ## ## BRANCHING is for computing constituents and multiplicities of restriction and induction of ## characters of symmetric groups. ## ## BRANCHING works with GAP4.3 (and higher versions). ## ## ## INTRODUCTION ############################################################################################## ## ## We know that the number of irreducible characters of a group is equal to the number of ## conjugacy classes, which in the case of $S_n$, the symmetric group on $n$ elements, is ## the number of partitions of $n$. Therefore the irreducible characters of $S_n$ have been ## lablled by partitions of $n$. ## ## Suppose $\lambda$ is a partition of $n$. The Branching Theorem shows the constituents of ## restriction of $\lambda$ to $S_{n-1}$ and induction of $\lambda$ to $S_{n+1}$. Therefore ## using that recursively, we can find constituents of restriction and induction of $\lambda$ ## to $S_{n-r}$ and $S_{n+r}$ for $r >= 1$, respectively. ## ## SUBPARTITION ## ============================================================================================ ## ## IsSubpartition( lambda, mu ); ## ## For partitions $\mu$ and $\lambda$, this program returns true" if each part of $\mu$ is less ## than or equal to the corresponding part in $\lambda$. ## ## MULTIPLICITY OF CONSTITUENTS ## ============================================================================================ ## ## MultiplicityOfConstituent( lambda, mu ); ## ## If $\lambda$ is a partition of $n$ and $\mu$ is a partition of $m$ for $m <= n$. This program ## returns the multiplicity of the constituent corresponding to $\mu$ in the restriction of the ## irreducible character of $S_n$, corresponding to $\lambda$, to $S_m$. ## ## Example: ## ======== ## gap> lambda := [11,9,7,5,2];; ## gap> mu := [10,7,4];; ## gap> IsSubpartition( lambda, mu ); ## true ## gap> MultiplicityOfConstituent( lambda, mu ); ## 1411410 ## ## BRANCHING ## ============================================================================================ ## ## Branching( lambda, m ); ## ## If $\lambda$ is a partition of $n$ then $\lambda$ is corresponding to an irreducible character ## $\chi$ of $S_n$. This function returns constituents and multiplicities of restriction or ## induction of $\chi$ to $S_m$ for $m < n$ or $m > n$, respectively. ## ## Example: ## ======== ## gap> lambda := [9,6,6,4];; #lambda is a partition of 25# ## gap> Branching( lambda, 18 ); ## [ [ 50, [ 5, 5, 4,4 ] ], [ 70, [ 5, 5, 5, 3 ] ], [ 70, [ 6, 4, 4, 4 ] ], ## [ 280, [ 6, 5, 4, 3 ] ], [ 210, [ 6, 5, 5, 2 ] ], [ 105, [ 6, 6, 3, 3 ] ], ## [ 210, [ 6, 6, 4, 2 ] ], [ 140, [ 6, 6, 5, 1 ] ], [ 35, [ 6, 6, 6 ] ], ## [ 210, [ 7, 4, 4, 3 ] ], [ 231, [ 7, 5, 3, 3 ] ], [ 420, [ 7, 5, 4, 2 ] ], ## [ 210, [ 7, 5, 5, 1 ] ], [ 189, [ 7, 6, 3, 2 ] ], [ 210, [ 7, 6, 4, 1 ] ], ## [ 105, [ 7, 6, 5 ] ], [ 147, [ 8, 4, 3, 3 ] ], [ 210, [ 8, 4, 4, 2 ] ], ## [ 280, [ 8, 5, 3, 2 ] ], [ 280, [ 8, 5, 4, 1 ] ], [ 105, [ 8, 5, 5 ] ], ## [ 63, [ 8, 6, 2, 2 ] ], [ 133, [ 8, 6, 3, 1 ] ], [ 105, [ 8, 6, 4 ] ], ## [ 21, [ 9, 3, 3, 3 ] ], [ 91, [ 9, 4, 3, 2 ] ], [ 70, [ 9, 4, 4, 1 ] ], ## [ 49, [ 9, 5, 2, 2 ] ], [ 99, [ 9, 5, 3, 1 ] ], [ 70, [ 9, 5, 4 ] ], ## [ 28, [ 9, 6, 2, 1 ] ], [ 34, [ 9, 6, 3 ] ] ] ## ## gap> lambda := [23,20,17,11,8];; #lambda is a partition of 79# ## gap> Branching( lambda, 82 ); ## [ [ 1, [ 23, 20, 17, 11, 8, 1, 1, 1 ] ], [ 2, [ 23, 20, 17, 11, 8, 2, 1 ] ], ## [ 1, [ 23, 20, 17, 11, 8, 3 ] ], [ 3, [ 23, 20, 17, 11, 9, 1, 1 ] ], ## [ 3, [ 23, 20, 17, 11, 9, 2 ] ], [ 3, [ 23, 20, 17, 11, 10, 1 ] ], ## [ 1, [ 23, 20, 17, 11, 11 ] ], [ 3, [ 23, 20, 17, 12, 8, 1, 1 ] ], ## [ 3, [ 23, 20, 17, 12, 8, 2 ] ], [ 6, [ 23, 20, 17, 12, 9, 1 ] ], ## [ 3, [ 23, 20, 17, 12, 10 ] ], [ 3, [ 23, 20, 17, 13, 8, 1 ] ], ## [ 3, [ 23, 20, 17, 13, 9 ] ], [ 1, [ 23, 20, 17, 14, 8 ] ], ## [ 3, [ 23, 20, 18, 11, 8, 1, 1 ] ], [ 3, [ 23, 20, 18, 11, 8, 2 ] ], ## [ 6, [ 23, 20, 18, 11, 9, 1 ] ], [ 3, [ 23, 20, 18, 11, 10 ] ], ## [ 6, [ 23, 20, 18, 12, 8, 1 ] ], [ 6, [ 23, 20, 18, 12, 9 ] ], ## [ 3, [ 23, 20, 18, 13, 8 ] ], [ 3, [ 23, 20, 19, 11, 8, 1 ] ], ## [ 3, [ 23, 20, 19, 11, 9 ] ], [ 3, [ 23, 20, 19, 12, 8 ] ], ## [ 1, [ 23, 20, 20, 11, 8 ] ], [ 3, [ 23, 21, 17, 11, 8, 1, 1 ] ], ## [ 3, [ 23, 21, 17, 11, 8, 2 ] ], [ 6, [ 23, 21, 17, 11, 9, 1 ] ], ## [ 3, [ 23, 21, 17, 11, 10 ] ], [ 6, [ 23, 21, 17, 12, 8, 1 ] ], ## [ 6, [ 23, 21, 17, 12, 9 ] ], [ 3, [ 23, 21, 17, 13, 8 ] ], ## [ 6, [ 23, 21, 18, 11, 8, 1 ] ], [ 6, [ 23, 21, 18, 11, 9 ] ], ## [ 6, [ 23, 21, 18, 12, 8 ] ], [ 3, [ 23, 21, 19, 11, 8 ] ], ## [ 3, [ 23, 22, 17, 11, 8, 1 ] ], [ 3, [ 23, 22, 17, 11, 9 ] ], ## [ 3, [ 23, 22, 17, 12, 8 ] ], [ 3, [ 23, 22, 18, 11, 8 ] ], ## [ 1, [ 23, 23, 17, 11, 8 ] ], [ 3, [ 24, 20, 17, 11, 8, 1, 1 ] ], ## [ 3, [ 24, 20, 17, 11, 8, 2 ] ], [ 6, [ 24, 20, 17, 11, 9, 1 ] ], ## [ 3, [ 24, 20, 17, 11, 10 ] ], [ 6, [ 24, 20, 17, 12, 8, 1 ] ], ## [ 6, [ 24, 20, 17, 12, 9 ] ], [ 3, [ 24, 20, 17, 13, 8 ] ], ## [ 6, [ 24, 20, 18, 11, 8, 1 ] ], [ 6, [ 24, 20, 18, 11, 9 ] ], ## [ 6, [ 24, 20, 18, 12, 8 ] ], [ 3, [ 24, 20, 19, 11, 8 ] ], ## [ 6, [ 24, 21, 17, 11, 8, 1 ] ], [ 6, [ 24, 21, 17, 11, 9 ] ], ## [ 6, [ 24, 21, 17, 12, 8 ] ], [ 6, [ 24, 21, 18, 11, 8 ] ], ## [ 3, [ 24, 22, 17, 11, 8 ] ], [ 3, [ 25, 20, 17, 11, 8, 1 ] ], ## [ 3, [ 25, 20, 17, 11, 9 ] ], [ 3, [ 25, 20, 17, 12, 8 ] ], ## [ 3, [ 25, 20, 18, 11, 8 ] ], [ 3, [ 25, 21, 17, 11, 8 ] ], ## [ 1, [ 26, 20, 17, 11, 8 ] ] ] ## ## HOOK FORMULA ## ============================================================================================ ## ## HookFormula( lambda ); ## ## returns the degree of the irreducible character corresponding to a partition $\lambda$. ## ## Example: ## ======== ## gap> lambda := [9,6,6,4];; ## gap> HookFormula( lambda ); ## 12748164000 ## ## PARTITIONS FOR A CHARACTER DEGREE ## ============================================================================================ ## ## PartitionsOfDegree( deg , n ); ## ## lists partitions of irreducible characters of degree "deg" of $S_n$. ## ## Example: ## ======== ## gap> PartitionsOfDegree( 12748164000, 25 ); ## [ [ 4, 4, 4, 4, 3, 3, 1, 1, 1 ], [ 9, 3, 2, 2, 2, 2, 2, 1, 1, 1 ], ## [ 9, 6, 6, 4 ], [ 10, 7, 2, 1, 1, 1, 1, 1, 1 ] ] ## ############################################################################################ ############################################################################################ ############################################################################################ DeclareGlobalFunction( "Branching" ); DeclareGlobalFunction( "BranchingDown" ); DeclareGlobalFunction( "HookFormula" ); DeclareGlobalFunction( "PartitionsOfDegree" ); DeclareGlobalFunction( "IsSubpartition" ); DeclareGlobalFunction( "MultiplicityOfConstituent" ); ############################################################################################ ############################################################################################ ################################### A Main Function ######################################## ## The inputs of this function are a partition $\lambda$ of $n$ and a positive integer $m$ ## This program returns a list of partitions of $m$ with thier multiplicities corresponding ## to constituents of the restriction or induction of $\lambda$ to $m$. This function call ## is expensive if $m$ is a large number. ## In this program the following programs and subroutines are called. ## 1. IsSubpartition ## 2. MultiplicityOfConstituent ############################################################################################ InstallGlobalFunction( Branching, function( lambda, m ) local P, p, M; M := [ ]; P := Partitions( m ); if Sum( lambda ) >= m then for p in P do if IsSubpartition( lambda, p ) = true then Add( M, [ MultiplicityOfConstituent( lambda, p ), p ] ); fi; od; else for p in P do if IsSubpartition( p, lambda ) = true then Add( M, [ MultiplicityOfConstituent( p, lambda ), p ] ); fi; od; fi; return M; end ); ############################################################################################ ############################################################################################ ################################### A Main Function ######################################## ## If $\lambda$ is a partition of $n$ and $\mu$ is a partition of $m$ for $m <= n$. It ## returns the multiplicity of the constituent corresponding to $\mu$ in the restriction ## of the irreducible character of $S_n$, corresponding to $\lambda$, to $S_m$. ## In this program the following programs and subroutines are called. ## 1. IsSubpartition, ## 2. MultiplicityOfConstituent, ## 3. BranchingDown. ############################################################################################ InstallGlobalFunction( MultiplicityOfConstituent, function( lambda, mu ) local sl, sm, r, L, l, b, f, M, N, i, k, t, S, j, m, u, lambdah, muh, cho; M := [ ]; u := 0; S := [ ]; if IsSubpartition( lambda, mu ) = true then sl := Sum( lambda ); sm := Sum( mu ); r := sl-sm; if Length( lambda ) > 1 and Length (mu ) > 1 and lambda[2] <= mu[1] then lambdah := List( [2..Length( lambda )], i -> lambda[i] ); muh := List( [2..Length( mu )], i -> mu[i] ); k := Sum( lambdah ); t := Sum( muh ); cho := Factorial( r )/( Factorial(k-t) * Factorial( r-k+t ) ); return cho * MultiplicityOfConstituent( lambdah, muh ); fi; L := [[ lambda, 1 ]]; for i in [ 1..r ] do for l in L do b := BranchingDown( l[1] ); if Length( b ) = 1 and IsInt( b[1] ) then b := [ b ]; fi; f := Filtered( b,i -> IsSubpartition ( i, mu ) = true ); Append( M, List( f, i -> [ i, l[2] ] ) ); od; N := List( M, i -> i[1] ); N := Set( N ); for j in [1..Length( N )] do for m in [1..Length( M )] do if N[j] = M[m][1] then u := u + M[m][2]; fi; od; Add( S, [ N[j], u ] ); u := 0; od; L := S; S := [ ]; M := [ ]; od; else Error("second argument is not a subpartition of the first argument"); fi; return L[1][2]; end ); ############################################################################################ ############################################################################################ ##################################### A Utility Function ################################### ## If $\lambda$ is a partition of $n$, this program returns the restriction of $\lambda$ to ## $n-1$. ## InstallGlobalFunction( BranchingDown, function( lambda ) local M, n, lt, t, i, j, s, r; M := [ ]; t := Length( lambda ); if t = 1 then return [ lambda[1]-1 ]; fi; for j in [1..t] do lt := [ ]; Append( lt, List( [1..j-1], r-> lambda[r] ) ); s := 0; for i in [j..t-1] do n := lambda; if i = j and n[j] > n[j+1] then Add( lt, n[i]-1 ); s := 1; else Add( lt, n[i] ); fi; od; if n[t] > 1 and s = 0 then Add( lt, n[t]-1 ); else if n[t] = 1 and j = t then; else Add( lt, n[t] ); fi; fi; if s = 1 or j = t then Add( M, lt ); fi; od; return M; end); ############################################################################################ ############################################################################################ ################################### A Main Function ######################################## ## This program returns the degree of $\lambda$. ############################################################################################ InstallGlobalFunction( HookFormula, function( lambda ) local P, theta, s, t, i, j, f; P :=[ ]; theta := AssociatedPartition( lambda ); t := Length( lambda ); s := Length( theta ); for i in [1..t] do for j in [1..s] do Add( P, lambda[i] + theta[j]-j-i+1 ); od; od; f := Filtered( P, i-> i > 0 ); return Factorial( Sum( lambda) ) / Product( f ); end); ############################################################################################ ############################################################################################ ################################### A Main Function ######################################## ## This program finds the partitions of $n$ of degree $d$. It returns fail if $n$ ## has no partition of degree $d$. ############################################################################################ InstallGlobalFunction( PartitionsOfDegree, function( d, n ) local p, f; p := Partitions( n ); f := Filtered( p, i -> HookFormula( i ) = d ); return f; end); ############################################################################################ ############################################################################################ ################################### A Main Function ######################################## ## This program returns true" if $\mu$ is a subpartition of $\lambda$. ############################################################################################ InstallGlobalFunction( IsSubpartition, function( lambda, mu ) local l, m, i; l := Length( lambda ); m := Length( mu ); for i in [1..l-1] do if lambda[i] < lambda[i+1] then return Error("the first argument is not a partition"); fi; od; for i in [1..m-1] do if mu[i] < mu[i+1] then return Error("the second argument is not a partition"); fi; od; if m > l then return false; fi; for i in [1..m] do if mu[i] > lambda[i] then return false; fi; od; return true; end );