######################################################################## ## #A murphy.g Andrew Mathas mathas@maths.usyd.edu.au ## #Y Copyright (C) December 1996 Imperial College #Y May 1998 University of Sydney ## ## These programs allow calculations with the Murphy basis of the Hecke ## algebra of type A. They require CHEVIE 3.4 or better (together with ## some functions from the package Specht). ## ## Multiplication of Murphy basis elements is done using the Garnir ## tableaux as described in Murphy's paper 'The representations of Hecke ## algebras of type A', J. Algebra 173 (1995), 97-121. This also lets us ## convert from the T-basis to the Murphy basis since ## T_w = M([[1],...[n]], [[1],...,[n]]) * T_w. ## (We use "M" for the Murphy basis since X is a shorthand for the ## Indeterminate() function.) ## ## As with the T-basis, Murphy basis records have parallel list components ## .elm and .coeff which in our case point to the standard tableaux pairs ## and the corresponding coefficients. The .elm list is an ordered list of ## lists of the form [ mu, s, t ] where mu, s and t are all integers and ## H.partition[ mu ] is the associated partition ## H.tableaux[ mu][ s and t ] are records describing s and t (these ## records are described in the function init() below). ## ## Throughout memory considerations are thrown to the wind as we cache ## many of the more horrible expansions as we go along in order to save ## time when we next need them. ## ## There are a number of utility functions below, mainly for converting ## between (standard) tableaux and right coset representatives; however ## the bulk of the functions for working with the Murphy basis are pushed ## into the HeckeAlgebraOps record using CHEVIE's CreateHeckeBasis. ## ######################################################################## #RequirePackage("chevie"); if not IsBound(HeckeAlgebraOps) then ## we'd better read hecke.g ReadChv("prg/hecke"); fi; if not IsBound( CHEVIE.MurphySpechtModules ) then RequirePackage("specht"); CHEVIE.MurphySpechtModules:=false; Print("\n# Type M:=Basis(H,\"Murphy\"); to access the Murphy basis.\n", "\n# Set CHEVIE.MurphySpechtModules:=true to work just inside", "\n# the Specht modules. This will make calculations with the", "\n# Murphy basis inside Specht modules much faster but will also", "\n# mean that T-basis to to Murphy-basis conversions will not work,", "\n# even if CHEVIE.MurphySpechtModules is set to false later.\n\n"); fi; ######################################################################## ## Given a permuation in Sym(n) return the corresponding CoxeterWord ## (we assume that does indeed belong to W=Sym(n) (certainly it belongs ## in some symmetric group). CoxeterWordSymmPerm:=function(x) local w, i; w:=[]; while x<>() do i:=1; while i^x<(i+1)^x do i:=i+1; od; Add(w,i); x:=(i,i+1)*x; od; return w; end; ## Return the CoxeterGroup permutation corresponding to the symmetric group ## permutation . CoxeterPermSymmPerm:=function(W,x) return PermCoxeterWord(W,CoxeterWordSymmPerm(x)); end; ## Given two standard tableau and - which are assuming to be of ## the same shape - return the permuation w such that =w. MappingPermTableaux:=function(s,t) return MappingPermListList(Flat(s),Flat(t)); end; ## Given a standard tableau for the Hecke algebra return ## the permatution w, as a CoxeterGroup permutation, such that t=t^mu*w. CoxeterPermTableau:=function(H,t) if IsList(t) then t:=HeckeAlgebraOps.Murphy.Tableau(H,t); fi; if not IsBound(t.wd) then t.wd:=PermCoxeterWord (CoxeterGroup(H), CoxeterWordSymmPerm( MappingPermTableaux(H.tableaux[t.mu][1].tab, t.tab))); fi; return t.wd; end; ## Given a standard tableau for the Hecke algebra return ## the permatution w, as a CoxeterGroup word, such that t=t^mu*w. ## (we never use this function; it's included for completeness). CoxeterWordTableau:=function(H,t) if IsList(t) then t:=HeckeAlgebraOps.Murphy.Tableau(H,t); fi; if not IsBound(t.wd) then t.wd:=PermCoxeterWord (CoxeterGroup(H), CoxeterWordSymmPerm( MappingPermTableaux(H.tableaux[t.mu][1].tab, t.tab))); fi; return CoxeterWord(CoxeterGroup(H), t.wd); end; #F Returns a string of the form "l1,l2,...,lk" for the list [l1,l2,..,lk]" ## which contains no spaces, and has first element 1. TightStringList:=function(list) local s, l; if list=[] then return ""; fi; s:=String(list[1]); for l in [2..Length(list)] do Add(s,','); Append(s,String(list[l])); od; return s; end; #F returns a `tight' string for the tableau StringTableau:=function(t) local tab, p; tab:="[["; for p in t.tab do tab:=Concatenation(tab, TightStringList(p), "],["); od; tab:=tab{[1..Length(tab)-2]}; Append( tab, "]" ); return tab; end; ######################################################################## ## Finally the Murphy basis code proper: ## We pass a record to CreateHeckeBasis() to add the Murphy basis operations ## to HeckeAlgebraOps.Murphy (we could do this directly ourselves but this ## way we have access to any operations which are added to HeckeEltOps in ## the future). ## The functions passed to CreateHeckeBasis can be accessed via ## HeckeAlgebraOps.Murphy.() CreateHeckeBasis("Murphy", rec( ## Adds various record components to which are used by ## the Murphy basis functions. init() is called the first time that ## the Murphy basis is used. init:=function(H) local s, mu, ind; if IsBound(H.partitions) then return; fi; if CartanType(CoxeterGroup(H))[1][1]<>"A" then Error("the Murphy basis is implemented only for type A"); fi; Append(ReadIndent, " "); InfoRead1("#I", ReadIndent, "Initializing Murphy basis...\n"); ## H.partitions = [ partitions ]; H.partitions:=Partitions( CoxeterGroup(H).semisimpleRank+1 ); ## H.tableaux = [ # partitions ][ rec( tab = actual tableau ## ind = index H.tableaux[mu] ## mu = partition index in H.partition ## wd = associated word in S_n (as a ## CoxeterGroup permuation) ## s = sXt ( s an index=integer ) ## Garnir = [..] will hold the Garnir ## expansions ) ] ## We add only tab, mu, and ind now; the rest are done on the fly. H.tableaux:=[]; for mu in [1..Length(H.partitions)] do H.tableaux[mu]:=[]; ind:=1; for s in StandardTableaux(H.partitions[mu]) do Add(H.tableaux[mu], rec(tab:=s, mu:=mu, ind:=ind, Garnir:=[]) ); ind:=ind+1; od; H.tableaux[mu][1].wd:=(); od; ## T-basis to Murphy-basis conversions; store as calculated, elements ## cross-indexed in H.TMBasisElts. Start with identity element. H.TwToMurphy:=[ HeckeAlgebraOps.Murphy.MakeBasisElt(H,[[[1,1,1]],[H.unit]]) ]; H.TMBasisElts:=[ () ]; InfoRead1("#I",ReadIndent,"...done\n"); ReadIndent:=ReadIndent{[1..Length(ReadIndent)-2]}; end, ## rewrite Murphy basis in terms of the T-basis T:=function(M) local m, H; H:=Hecke(M); ## since HeckeEltOps.\+ normalizes I don't see why it is necessary ## to normalize here but it is... return HeckeEltOps.Normalize(Sum([1..Length(M.elm)], m->M.coeff[m]*HeckeAlgebraOps.Murphy.sXt( H, H.tableaux[M.elm[m][1]][M.elm[m][2]], H.tableaux[M.elm[m][1]][M.elm[m][3]] ))); end, ## rewrite T-basis in terms of the Murphy-basis Murphy:=function(h) local w, H; H:=Hecke(h); if CHEVIE.MurphySpechtModules then Print("\n# WARNING: because CHEVIE.MurphySpechtModules=true the answer", "\n# this function returns will almost certainly be incorrect.\n\n"); fi; return Sum([1..Length(h.elm)], w->h.coeff[w]*HeckeAlgebraOps.Murphy.TwToMurphy(H,h.elm[w]) ); end, ## This function recursively expands T_w into a linear combination of ## Murphy basis elements (using Garnir expansions). Note that we know ## how to write 1 in terms of the Murphy basis. ## As we go along we cache the expansion of T_w in the list H.TwToMurphy ## which is indexed by the parallel list H.TMBasisElts (actually, we ## maintain this as a set -- costly in terms of speed???). TwToMurphy:=function(H,w) local wpos, Mw,W; wpos:=Position(H.TMBasisElts,w); if wpos=false then W:=CoxeterGroup(H); w:=CoxeterWord(W,w); Mw:=HeckeAlgebraOps.Murphy.TwToMurphy(H, PermCoxeterWord (W,w{[1..Length(w)-1]})) * Basis(H,"T")(w[Length(w)]); ## resynchronise TwToMurphy and TMBasisElts AddSet(H.TMBasisElts, w); wpos:=Position(H.TMBasisElts, w); for w in [Length(H.TwToMurphy), Length(H.TwToMurphy)-1..wpos] do H.TwToMurphy[w+1]:=H.TwToMurphy[w]; od; H.TwToMurphy[wpos]:=Mw; fi; return ShallowCopy(H.TwToMurphy[wpos]); end, ## The command Basis(H,"Murphy")(,) gets redirected to this function ## which will return a record which corresponds to the Murphy basis element ## M_{,}. Note that we use MakeBasisEltRec() to create the actual ## basis element. MakeBasisElt:=function(H,tabs)local s, t; if Length(tabs)<>2 then Error("usage, M(, )"); elif tabs[2]=[] or not IsList(tabs[2][1]) then ## assume tabs[1]= and tabs[2]= return HeckeAlgebraOps.MakeBasisEltRec(H,"Murphy",tabs[1],tabs[2]); fi; s:=tabs[1]; t:=tabs[2]; if IsList(s) and IsList(t) then s:=HeckeAlgebraOps.Murphy.Tableau(H, s); t:=HeckeAlgebraOps.Murphy.Tableau(H, t); fi; if not ( IsBound(s.mu) and IsBound(t.mu) ) or s.mu<>t.mu then Error(" and must have the same shape"); fi; return HeckeAlgebraOps.MakeBasisEltRec(H,"Murphy", [[s.mu, s.ind, t.ind]] , [H.unit]); end, ## printing is done by calling String() String:=function(h) local H,i,j,coeff,s,needsbrackets,res; H:=Hecke(h); if h.elm=[] then return "0"; fi; res:=""; for i in [1..Length(h.elm)] do coeff:=String(h.coeff[i]); needsbrackets:=false; for j in [2..Length(coeff)] do if (coeff[j]='+' or coeff[j]='-') and coeff[j-1]<>'^' then needsbrackets:=true;fi; od; if needsbrackets then coeff:=Concatenation("(",coeff,")"); elif coeff="1" then coeff:=""; elif coeff="-1" then coeff:="-"; fi; if CHEVIE.PrintHecke<>"GAP" and i>1 then Append(res,"\n"); fi; if Position(coeff,'-')<>1 and i>1 then Append(res,"+");fi; Append(res,String(coeff)); if CHEVIE.PrintHecke="GAP" then Append(res,"*");fi; res:=Concatenation(res,"M(", StringTableau( H.tableaux[h.elm[i][1]][h.elm[i][2]] ), ", ", StringTableau( H.tableaux[h.elm[i][1]][h.elm[i][3]] ), ")"); od; return String(res); end, ## given a tableau return the basis element x_mu*T_ Xt:=function(H, t) local row, J, WJ; if not IsBound(t.1) then if t.ind=1 then J:=[]; # -> generating set for Sym() for row in t.tab do Append(J, row{[1..Length(row)-1]}); od; WJ:=List(CoxeterWords(ReflectionSubgroup(CoxeterGroup(H),J)), i->PermCoxeterWord(CoxeterGroup(H),i)); t.1:=HeckeAlgebraOps.MakeBasisEltRec(H,"T",WJ,[1..Length(WJ)]*0+1); else t.1:=ShallowCopy( HeckeAlgebraOps.Murphy.Xt(H, H.tableaux[t.mu][1]) ); t.1.elm:=t.1.elm*CoxeterPermTableau(H,t); fi; fi; return ShallowCopy(t.1); end, ## return the basis element .(.ind) = T_^* x_mu T_. sXt:=function(H,s,t) if s.ind=1 then return HeckeAlgebraOps.Murphy.Xt(H,t); elif t.ind=1 then return AlphaInvolution(HeckeAlgebraOps.Murphy.Xt(H,s)); elif not IsBound(t.(s.ind)) then t.(s.ind):=Basis(H,"T")(CoxeterPermTableau(H, s)^-1) * HeckeAlgebraOps.Murphy.Xt(H,t); fi; return ShallowCopy( t.(s.ind) ); end, ## given a tableau return the corresponding element of .tableau ## (a "CoxeterGroup tableau"?) Tableau:=function(H, tab) local mu, i, s; mu:=Position(H.partitions, List(tab, Length) ); if mu<>false then for s in [1..Length(H.tableaux[mu])] do if tab=H.tableaux[mu][s].tab then return H.tableaux[mu][s]; fi; od; fi; Error(" must be a standard tableau for S(", CoxeterGroup(H).semisimpleRank+1,")"); end, ## returns the position of the integer in the tableau record . PositionInTableau:=function(t,i) local j, row, col; for row in [1..Length(t.tab)] do col:=Position(t.tab[row], i); if col<>false then return [row,col]; fi; od; Error(i, " is not contained in the tableau "); end, ## HeckeEltOps gives control of \* to Hecke(basis)Ops.prod if it exists ## As we know how to multiply the Murphy basis we seize the reigns here prod:=function(H, m, h) local W,mh,a,q,w,mw,r,mr,s,t,tr,i,one,two; if h.basis="Murphy" and m.basis<>"Murphy" then return AlphaInvolution( AlphaInvolution(h)*AlphaInvolution(m) ); fi; if h.basis<>"T" then h:=Basis(H,"T")(h); fi; W:=CoxeterGroup(H); q:=H.parameter[1]; # will return this value; set to zero first mh:=HeckeAlgebraOps.MakeBasisEltRec(H,"Murphy",[],[]); for a in [1..Length(h.elm)] do w:=CoxeterWord(W,h.elm[a]); mw:=ShallowCopy(m); for r in w do mr:=HeckeAlgebraOps.MakeBasisEltRec(H,"Murphy",[],[]); for i in [1..Length(mw.elm)] do t:=H.tableaux[ mw.elm[i][1] ][ mw.elm[i][3] ]; ## we are interested in the two nodes, =r and =r+1, ## which are swapped by the transposition r=(r,r+1). here are ## their coordinates as lists [row, column] one:=HeckeAlgebraOps.Murphy.PositionInTableau(t, r); two:=HeckeAlgebraOps.Murphy.PositionInTableau(t, r+1); if one[1]=two[1] then ## same row Add(mr.coeff, q*mw.coeff[i]); Add(mr.elm, mw.elm[i]); elif one[2]<>two[2] then ## different column; t*r still standard tr:=Copy(t.tab); tr[one[1]][one[2]]:=r+1; tr[two[1]][two[2]]:=r; tr:=HeckeAlgebraOps.Murphy.Tableau(H,tr); if one[1] is a Hecke algebra record ## =(r,c) is the coordinate where the tableau becomes ## non-standard; ie. if (r,c)=x then (r+1,c)=x+1 and we want ## to expand *(x,x+1). We are actually expanding ## M_{,} * T_{(r,r+1)} ## where we know that *(r,r+1) is not standard. Once we know how ## to express M_{1,}*T_r in the Murphy basis we store this as ## t.Garnir[r] for future reference. GarnirExpansion:=function(H,node,s,t) local W,a,b,g,J,K,w,tab,coeff,d,tnu, row,col,h; row:=node[1]; col:=node[2]; ## row and column of node to be moved. if not IsBound( t.Garnir[t.tab[row][col]] ) then W:=CoxeterGroup(H); ## a typical situation here is ## 1 2 7 ## = 3 5 8 with =[2,2]; ## 4 6 9 ## thus, we want to expand the tableau ## 1 2 7 ## t' = 3 6 8 = *(5,6) [note that 5 occupies position [2,2] in ] ## 4 5 9 ## into a linear combination of standard tableaux. To do this we first ## pretend that we started with ## 1 2 3 ## g = 4 7 8 ## 5 6 9 ## (that is we put the numbers in order upto, but not including [row,col] ## and then enter them in order starting from the next row down, filling ## up the nodes around and then continuing on. ie. what Murphy ## called a Garnir-tableau). g:=Copy(H.tableaux[t.mu][1].tab); a:=g[row][col]; ## first numnber being moved; above a=5 and b=8 b:=g[row+1][col]; ## last number being moved g[row]{[col..Length(g[row])]}:=[a+col..b]; g[row+1]{[1..col]}:=[a..a+col-1]; ## w is the permutation such that t=g*w => T_t = T_g*T_w w:=CoxeterWordSymmPerm( MappingPermTableaux(g,t.tab) * (t.tab[row][col],t.tab[row+1][col]) ); ## next we note that, by an astute look at right coset sums, ## 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 1 2 3 ## (*) 4 5 6 + 4 5 7 + 4 5 8 + 4 6 7 + 4 6 8 + ... + 4 7 8 = h * 4 ## 7 8 9 6 8 9 6 7 9 5 8 9 5 7 9 5 6 9 5 6 7 8 ## 9 ## Because of our choice of g all of the LH tableaux are standard, except ## the last (which is g), and the object on the RHS. We'll worry about ## and the RHS later; first we spin out the LH tableaux. tab:=[]; coeff:=[]; for J in Combinations([a..b],col) do if J<>[a..a+col-1] then g[row+1]{[1..col]}:=J; g[row]{[col..Length(g[row])]}:=Difference([a..b],J); ## note that we set =t^mu below; this is because we later ## have to multiply by T_s^* Add(tab, [ t.mu, 1, HeckeAlgebraOps.Murphy.Tableau(H,g).ind ] ); Add(coeff, -1); fi; od; t.Garnir[ t.tab[row][col] ]:=HeckeEltOps.Normalize( HeckeAlgebraOps.MakeBasisEltRec(H,"Murphy",tab,coeff) ); ## Next, if CHEVIE.MurphySpechtModules=false (in which case we ## just work in the Specht module), we look after the right hand term ## in (*) above. In general it won't correspond to a partition but we ## can find a partition and a in such that ## T_d=T_ if CHEVIE.MurphySpechtModules=false then ## First we set equal to the the new tableau on the right in (*); ## above, :=[[1,2,3],[4],[5,6,7,8],[9]]. tab:=g{[1..row-1]}; if col>1 then Add(tab,g[row]{[1..col-1]}); fi; Add(tab, [a..b]); if col more sensibly (our would become ## [[5,6,7,8],[1,2,3],[4],[9]] ), Sort(tab, function(x,y) if Length(x)=Length(y) then return x[1]Length(y); fi; end); ## which gives us the (shape of the) new tableau tnu:=H.tableaux[ Position(H.partitions, List(tab,Length)) ][1]; ## and finally we have . The point is that tab = T_d^-1*tnu*T_d. d:=CoxeterPermSymmPerm(W, MappingPermTableaux(tnu.tab,tab)); ## is now under control, but we still need to compute ## from (*). The point here is that we are essentially writing ## $H.I = \bigcup H.d = \bigcup d' I$ ## where H and I are two sugroups and d and d' run over coset ## representatives of H and I. (Note that at this point g=t^mu.) J:=g[row]{[1..Length(g[row])-1]}; Append(J, g[row+1]{[1..Length(g[row+1])-1]}); K:=Difference(J,[a-1,b]); h:=List(ReducedRightCosetRepresentatives( ReflectionSubgroup(W,W.rootInclusion{J}), ReflectionSubgroup(W,W.rootInclusion{K}) ), coeff->coeff^-1); h:=HeckeAlgebraOps.MakeBasisEltRec(H,"T",h,[1..Length(h)]*0+1); ## the multiplication below is quite costly; but it is only done ## once as we store the result in t.Garnir. t.Garnir[t.tab[row][col]] := t.Garnir[t.tab[row][col]] + h * Basis(H,"T")(d)^-1 * Basis(H,"Murphy")(tnu.tab,tnu.tab) * Basis(H,"T")(d); fi; ## end of if CHEVIE.MurphySpechtModules=false ## Next we worry about the element above (remember t=g*w); this is ## actually a bit sneaky because although the Garnir expansion of ## contained only standard tableaux this is not true of the Garnir ## expansion of ; hence the multiplication below is usually recursive. t.Garnir[t.tab[row][col]]:= t.Garnir[t.tab[row][col]] * Basis(H,"T")(w); fi; ## end of if IsBound( t.Garnir[t.tab[row][col]] ) ## Finally we have to put back into the equation. If we are working ## in just the Specht module is almost irrelevant; but in general it ## affects tnu in strange ways (hence it might be better to cache the ## full expansion rather than just the right hand side). return Basis(H,"T")(CoxeterPermTableau(H,s)^-1)*t.Garnir[t.tab[row][col]]; end, ## This is the anti-isomorphism of the Hecke algebra given by T_i -> T_i; ## on the Murphy basis we have M_{s,t} -> M_{t,s} (also called * by many) AlphaInvolution:=function(h) local t; h:=ShallowCopy(h); h.elm:=List(h.elm, t->[t[1],t[3],t[2]]); return h; end )); ## end of CreateHeckeBasis