// **************** Coxeter group functions **************** forward GetWord; // Input C, g; C is a Coxeter group, g is a group element. Output a reduced expression for g // as a sequence of integers where i corresponds to s_i forward PushPiRight; // Input g, We; g an extended affine Weyl group element of the form , where pi^k in Pi and h in W_a, // We a structure for the extended affine Weyl group. Output h' as a list, where h'pi^k = g = pi^k h. forward YesPi; // Input h, We or , We; h an element of WeAG, k an integer. // Output <0,h> or if is input. forward WeLeftDescentSet; // Input e, We; e an extended affine Weyl group element. // Output the left descent set of e as a set of integers. forward WeRightDescentSet; // Similar to WeLeftDescentSet. forward MinCosetFactorRight; // Input g, J, We; g an element of WeAG, J a subset of 1..Wen. // Output a tuple such that g2 is a minimal right coset rep and g1*g2 = g. forward MinCosetFactorLeft; // Input g, J, We; g an element of WeAG, J a subset of 1..Wen. // Output a tuple such that g1 is a minimal left coset rep and g1*g2 = g. forward MinCosetFactorShort; // Input s, g, J, We; s an integer corresponding to a simple reflection, g in WeAG and g is a minimal left coset representative -- an element of WeAG^J, J a subset of 1..Wen. // Output g1,T such that g1 is a minimal left coset rep and s*g = g1*t, and t is the identity in which case // T is the empty set or t is a simple reflection in which case T is a one-element set containing the // integer corresponding to t. forward LeftShuffle; // Input e, IndType, We; e an element of an iterated product of Coxeter groups, // IndType a structure for an iterated product of Coxeter groups. // Output an element of the same form as e, factored so that as large as possible // an element is on the left. // WARNING : currently assumes that all groups in Indtype equal We forward WeIndLeftDescentSet; // Input e, IndType, We; e an element of an iterated product of Coxeter groups, // IndType a structure for an iterated product of Coxeter groups. // Output the left descent set of e as a list of integers. forward WeMult; // Input e1, e2, We; e1, e2 are extended affine Weyl group elements. // Output e1*e2 (in the form ). forward WeIndMult; // Input i, e2, IndType, We; i an integer corresponding to a simple reflection, e2 an IndType element. // Output s_i*e2. forward WeListMult; // Input elist, We; elist a list of extended affine Weyl group elements. // Output the product of the elements in elist. forward LengthDownOne; // Input e, We; e an extended affine Weyl group element. // Output the set of elements less than e in Bruhat order and of length 1 less than e. // If the option descent := true, then only returns those elements with right descent set // contained in {Wen}. forward AllDown; // Input e, We; e an extended affine Weyl group element. // Output the set of elements less than e in Bruhat order. forward CycleType; //returns the cycle type of a permutation group element g, in the form of a partition forward ListPerm; // Input g, We where g is an element of a symmetric group We or a more general group structure and output g as a permutation of 1 to n in the form of a list forward InverseZ; // Input a word w of an affine permutation in window notation, and output its inverse in window notation forward ListZPerm; // Input n, g or n, g, We where n is an integer and g is an element of W_a of type \tilde{A_n} expressed as a reduced word. Output g in window notation // **************** End Coxeter group functions **************** // *************** Permutation / Word functions ***************** forward Inverse; // Input a permutation w as a list. Output the inverse of w as a list. forward Relabel; // Input a list of integers w. Output the word obtained by relabeling so that entries are 1..n with the same relative order; entries further right are treated as being larger forward CochargeLabel; // Input w; w a list of integers. Output the cocharge labeling of Relabel(w). forward RotateWord; // Input w, r; w the cocharge labeling of a permutation, r an integer. Output the cocharge labeling resulting from rotating the word r times (one rotation removes the rightmost letter and brings it to the beginning of the word and adds 1 to the letter) forward ParenSwap; // Input w, i; w a semistandard word, i an integer. Output the result of the crystal reflection coming from looking at i and i+1 as right and left parentheses. // For example, // > ParenSwap([1,1,2,2,2,2],1); // [ 1, 1, 1, 1, 2, 2 ] // > ParenSwap([2,2,2,2,1,1],1); // [ 1, 1, 2, 2, 1, 1 ] forward RollIn; // Helper function for Standardize and UnStandardize forward RollOut; // Helper function for Standardize and UnStandardize forward Standardize; // Input w; w semistandard word. Output the standard word obtained by applying the standardization map of Lascoux and Schutzenberger forward UnStandardize; // Input w, mu; w a standard word, mu a partition. Output the semistandard word of content mu that is the inverse of the standardization map forward MyCatabolism; // Input w; w a standard word. Output the partition equal to catabolizability of the insertion tableau of w // ***************** End Permutation / Word functions ************ // *************** Tableau combinatorics ************************* forward MyRowInsert; // Input ~T, x. Update T to be the tableau obtained from T by row inserting the integer x forward PTab; // Input w. Output the insertion tableau of w as a list of lists forward QTab; // Input w. Output the recording tableau of w as a list of lists forward MyShape; // Input tableau T as a list of lists. Output the shape of T forward ToPartition; // Same as MyShape. forward EnsureTabNotMagma; // Input a tableau T as a list of lists or in Magma's format. Output this tableau as a list of lists forward EnsureTabMagma; // Input a tableau T as a list of lists or in Magma's format. Output this tableau in Magma's format forward SuperStandard; // Input mu, k; mu a partition, k an integer. Output the superstandard tableau of shape mu whose first row consists of only k, next row consists of k+1, etc. forward EasyUnStandardize; // Input w, mu; w a permutation as a list, mu a partition. Output the semistandard order with content mu and the same relative order as w (elements to the right considered larger) forward OuterCorners; // Input mu; mu a partition. Output the outer corners of mu as a list of , for r, c the row and column of the outer corner. forward CoCyclage; // Input T, i, j; T a tableau in Magma's format, i, j the position of an outer corner. Output the result of cocyclaging T at this outer corner forward Cyclage; // Input T, i, j; T a tableau in Magma's format, i, j the position of an outer corner. Output the result of cyclaging T at this outer corner forward Catabolism; // Helper function for RowCatable forward InitBlock; // Helper function for RowCatable forward RowCatable; // Input T; T a tableau in Magma's format. Output the row catabolizability of T as a partition. // ******************* End Tableau combinatorics ******************* // ****************** Miscellaneous ***************************** forward DKEGraph; // Input SH; SH a partition. Output a list of two things: First a list of permutations all with the same recording tableau T where T is of shape SH, second a list of |SH|-2 matrices that encode which permutations are related by a dual Knuth equivalence, i.e., the first matrix corresponds to DKEs on 1, 2, 3. forward Restrict; // Input w, n; w a permutation of length n in the form of a list. // Output the result of deleting the letter n from w. forward Induce; // Input w, k; w a permutation as a list, k an element of 1..#w. // Output the result of adding a k to the end of the word w and increasing // all letters greater than or equal to k by 1. forward RMult; // Input w, i; w a permutation as a list, i an integer corresponding to a simple reflection. // Output the result of right multiplying by s_i. // If the option nodescentR := true, then only multiply if length increases. forward LMult; // Similar to RMult. forward Subsequences; // Input an array x, returns a list of the subsequences of x forward modd; // Input k, n; k, n integers. Output the integer in 1..n congruent to k mod n // ************************ End Miscellaneous *********************** // **************************************************************************************************************** //P := Partitions(n); O := OrderedIntegerMonoid(); TabM := TableauMonoid(O); //Type for the extended Weyl group, pi generates the subgroup of length 0 elements. WeType := recformat; //Type for sequence of extended Weyl groups, producted over parabolic subgroups. IndElementType:= recformat; procedure InitWe(myname, ~We) WeAG := CoxeterGroup(myname); Wename := myname; Wen := #(Generators(WeAG)); WeS := [1..Wen]; Wepi := map WeS | [:i in [1..#(WeS)]]>; WeG := StandardParabolicSubgroup(WeAG, {1..(Wen)-1}); WeGfAG := homWeAG | [WeAG.i : i in [1..(Wen)-1]]>; WeRG, Wef := ReflectionGroup(WeG); end procedure; procedure InitInd(groups,parabolics,~IT); ITgroups := groups; ITparabolics := parabolics; ITng := #groups; end procedure; procedure ShrinkIndType(~IndType,k) if k ne IndTypeng then Remove(~(IndTypegroups),k); Remove(~(IndTypeparabolics),k); else Remove(~(IndTypeparabolics),k-1); Remove(~(IndTypegroups),k); end if; IndTypeng:=IndTypeng-1; end procedure; //name := "A~" cat IntegerToString(n-1); //We := rec; //InitWe(name, ~We); // **************************************************************************************************************** // **************************************************************************************************************** // **************** Coxeter group functions **************** function GetWord(C,g) return ElementToSequence(g); end function; //Given an element g of We, return an element x of W_a such that g=x*pi, //where pi is of length zero function PushPiRight(g,We) try x := GetWord(WeAG,g[2]); catch e x := g[2]; end try; Inv := map WeS | [:i in [1..#(WeS)]]>; pifun := map WeS | [:i in [1..#(WeS)]]>; //initialize to ID for j in [1..g[1]] do pifun := Inv * pifun; end for; return [pifun(s):s in x]; end function; function YesPi(e1, We) try temp := e1[2] in WeAG; catch e e1 := <0, e1>; end try; return e1; end function; function WeLeftDescentSet(e, We) //try // kemp := e[2] in WeAG; // catch e // return WeIndLeftDescentSet(e,We); // end try; temp := SetToIndexedSet(LeftDescentSet(WeAG,e[2])); Inv := map WeS | [:i in [1..#(WeS)]]>; pifun := map WeS | [:i in [1..#(WeS)]]>; //initialize to ID for j in [1..e[1]] do pifun := Inv * pifun; end for; return {pifun(i):i in temp}; end function; //This differs from WeLeftDescentSet because we're taking the convention of factoring //the length zero element on the left. function WeRightDescentSet(e, We) temp := SetToIndexedSet(RightDescentSet(WeAG,e[2])); return temp; end function; //returns a tuple such that g2 is a minimal right coset rep and g1*g2 = g //g assumed to be in WeAG function MinCosetFactorRight(g,J,We) g2 := g; g1 := Id(WeAG); while WeLeftDescentSet(g2,We) meet J ne {} do s := SetToIndexedSet(WeLeftDescentSet(g2,We) meet J)[1]; g2 := WeMult(WeAG.s,g2,We); g1 := WeMult(g1,WeAG.s,We); end while; return g1, g2; end function; //returns a tuple such that g1 is a minimal left coset rep and g1*g2 = g //g assumed to be in WeAG function MinCosetFactorLeft(g,J,We) g1 := g; g2 := Id(WeAG); while WeRightDescentSet(g1,We) meet J ne {} do s := SetToIndexedSet(WeRightDescentSet(g1,We) meet J)[1]; g1 := WeMult(g1,WeAG.s,We); g2 := WeMult(WeAG.s,g2,We); end while; return g1, g2; end function; //given s, g returns g1,t such that g1 is a minimal left coset rep and s*g = g1*t //g assumed to be in WeAG and mincoset of W_J, s is an integers corresponding to simple reflection //t is the empty set of contains one element that is a simple reflection function MinCosetFactorShort(s,g,J,We) t := SetToIndexedSet(WeRightDescentSet(WeMult(WeAG.s,g,We),We) meet J); if #t gt 1 then print "I proved this should never print!"; end if; if #t eq 0 then return WeMult(WeAG.s,g,We),t; end if; return WeMult(WeMult(WeAG.s,g,We),WeAG.(t[1]),We),t; end function; //Given e an IndType element, factor as large as possible an element on the left //return the factored form of such an element //WARNING : currently assumes that all groups in Indtype equal We function LeftShuffle(e,IndType,We) if IndTypeng eq 1 then return e; end if; J := IndTypeparabolics[IndTypeng-1]; g1,g2 := MinCosetFactorRight(e[#e],J,We); //print "printing g1,g2", g1,g2; e[#e-1] := WeMult(e[#e-1],g1,We); ShrinkIndType(~IndType,IndTypeng); return LeftShuffle([e[i]:i in [1..#e-1]],IndType,We) cat [g2]; end function; function WeIndLeftDescentSet(e,IndType,We) return WeLeftDescentSet(LeftShuffle(e,IndType,We)[1],We); end function; //return e1*e2 where ei is in W_e of the form function WeMult(e1, e2, We) e1 := YesPi(e1, We); e2 := YesPi(e2, We); //print "e1, e2, WeAG:", e1, e2, WeAG; w1 := GetWord(WeAG, e1[2]); //pifun is Wepi composed with itself e2[1] times pifun := map WeS | [:i in [1..#(WeS)]]>; //initialize to ID for j in [1..e2[1]] do pifun := Wepi * pifun; end for; //push e1[2] through the length 0 element of e2 l1 := #w1 eq 0 select Id(WeAG) else (&*[WeAG.pifun(i):i in w1]); //print "answer:", ; return ; end function; function WeIndMult(s, e2,IndType,We) if IndTypeng gt 1 then J := IndTypeparabolics[1]; else J := {}; end if; gg,t:=MinCosetFactorShort(s,e2[1],J,We); if #t eq 0 then e2[1] := gg; return e2; else ShrinkIndType(~IndType,1); return [gg] cat WeIndMult(t[1],[e2[i]:i in [2..#e2]],IndType,We); end if; end function; function WeListMult(elist, We) if #elist eq 0 then return Id(WeAG); else e := elist[1]; elist := [elist[i]:i in [2..#elist]]; return WeMult(e, WeListMult(elist, We), We); end if; end function; // function LengthDownOne(ine,We:descents:=false) singleelem := false; try mye:=ine[1]; temp := ine[2][2] in WeAG; catch e mye := ine; singleelem := true; end try; w:=GetWord(WeAG,mye[2]); out:={}; for i in [1..#w] do x:=Remove(w,i); nw:=&*([Id(WeAG)]cat[WeAG.k:k in x]); if Length(nw) eq #w-1 and (not descents or RightDescentSet(WeAG,nw) subset {Wen}) then g:=ine; if singleelem then g[2] := nw; else g[1][2]:=nw; end if; out:=out join {g}; end if; end for; return out; end function; function AllDown(ine,We) e:=ine[1]; w:=GetWord(WeAG,e[2]); out:={}; subs:=Subsequences(w); for x in subs do nw:=&*([Id(WeAG)]cat[WeAG.k:k in x]); g:=ine; g[1][2]:=nw; out:=out join {g}; end for; return out; end function; //returns the cycle type of a permutation group element g, in the form of a partition function CycleType(g) CS := CycleStructure(g); p := []; for c in CS do p:= p cat [c[1] : i in [1..c[2]]]; end for; return p; end function; //given an element of g, return g as a list of numbers from 1 to n function ListPerm(g,We) try G := WeG; catch e G := We; end try; L := GetWord(G,g); w := [1..Wen]; for s in L do nw := w; nw[s] := w[s+1]; nw[s+1] := w[s]; w := nw; end for; return Inverse(w); end function; function InverseZ(w) ww := [(w[i]-1) mod #w +1: i in [1..#w]]; pos := [Position(ww,k) : k in [1..#w]]; return [pos[i] + ww[pos[i]] - w[pos[i]]: i in [1..#w] ]; end function; //return a Z-permutation corresponding g in W_a of type A function ListZPerm(n,g,...) //if Wename[1] ne "A" then // return 0; //end if; if #g eq 2 then We:=g[2]; L := GetWord(We`AG,g[1]); else L:=g[1]; end if; w := [1..n]; for s in L do nw := w; if n gt s then nw[s] := w[s+1]; nw[s+1] := w[s]; else nw[n] := w[1] + n; nw[1] := w[n] - n; end if; w := nw; end for; return w; end function; // **************** End Coxeter group functions **************** // *************** Permutation / Word functions ***************** function Inverse(w) return [Position(w,k) : k in [1..#w]]; end function; //Given a word with integer entries, relabel so that entries are 1..n //with the same relative order //entries further right are treated as being larger function Relabel(w:inverse:=false) nw := w; for i in [1..#w] do x, p := Min(w); nw[p] := i; w[p] := 9999999; end for; if inverse then return Inverse(nw); else return nw; end if; end function; function CochargeLabel(w:tab := false,start:=0) if tab then w:=EnsureTabNotMagma(w); w := &cat(Reverse(w)); end if; w:=Relabel(w:inverse:=true); nw:=[0:i in [1..#w]]; c:=start; for i in [1..(#w-1)] do nw[w[i]]:=c; if w[i] gt w[i+1] then c:=c+1; end if; end for; nw[w[#w]]:=c; if tab then return PTab(nw); else return nw; end if; end function; function RotateWord(w,r) for i in [1..r] do Insert(~w,1,w[#w]+1); Remove(~w,#w); end for; return w; end function; // Looks at only i and i+1 as right and left parentheses, matches parentheses and then swaps the leftover function ParenSwap(w,i) savew:=w; w:=[x eq i or x eq i + 1 select x else -99:x in w]; change:=true; while change do change:=false; posi1:=0; for k in [1..#w] do if w[k] eq i+1 then posi1:=k; end if; if w[k] eq i and posi1 ne 0 then w[k]:=-99; w[posi1]:=-99; change:=true; posi1:=0; end if; end for; end while; ni1:=#[x:x in w|x eq i+1]; count:=1; for k in [1..#w] do if w[k] ne -99 then if count gt ni1 then savew[k]:=i+1; else savew[k]:=i; end if; count+:=1; end if; end for; return savew; end function; function RollIn(w,m) for i in [m-1..1 by -1] do w:=ParenSwap(w,i); end for; return w; end function; function RollOut(w) m:=Min(w); M:=Max(w); for i in [m..M-1] do w:=ParenSwap(w,i); end for; return w; end function; function Standardize(w) while #w ne #{x:x in w} do m:=#[x:x in w|x eq 1]; count:=1; for i in [1..#w] do if w[i] eq 1 then w[i]:=count; count+:=1; else w[i]+:=m-1; end if; end for; content:=[#[x:x in w|x eq i]:i in [-100..100]]; x,y:=Max(content); w:=RollIn(w,y-101); end while; return w; end function; function UnStandardize(w,mu:maxmu:=false) if maxmu then mu:=[0:i in [1..#w]]; end if; r:=1; while &+([0]cat[mu[i]:i in [1..r-1]]) lt #w do T:=RSKCorrespondence(O!w); m:=InitBlock(T); content:=[#[x:x in w|x eq i]:i in [1..m]]; m:=Position([x eq 1:x in content],false); if m eq 0 then newm:=#content; else newm:=m-1; end if; if maxmu then mu[r]:=Min(newm,#w-&+([0]cat[mu[i]:i in [1..r-1]])); end if; if newm lt mu[r] then print "Not mu catabolizable"; return 0; end if; count:=1; for i in [1..#w] do if w[i] le mu[r] then w[i]:=1; else w[i]-:=mu[r]-1; end if; end for; print "before rollout w",w; w:=RollOut(w); print "after rollout w",w; r+:=1; end while; return w; end function; function MyCatabolism(w) mu:=[0:i in [1..#w]]; w:=CochargeLabel(w); while #w ne 0 do x:=w[#w]; k:=Position(mu,x); Remove(~w,#w); if k eq 0 then Insert(~w,1,x+1); else mu[k]:=mu[k]+1; end if; end while; return ConjugatePartition(mu); end function; // ***************** End Permutation / Word functions ************ // *************** Tableau combinatorics ************************* procedure MyRowInsert(~T, x) r := 1; while r in [1..#T] do c := 1; while c in [1..#(T[r])] do if T[r][c] gt x then y := T[r][c]; T[r][c] := x; x:= y; c:= 999998; end if; c +:= 1; end while; if c ne 999999 then Append(~T[r],x); r := 999998; end if; r+:=1; end while; if r ne 999999 then Append(~T,[x]); end if; end procedure; function PTab(w) T := []; for x in w do MyRowInsert(~T,x); end for; return T; end function; function QTab(w) return PTab(Relabel(w:inverse:=true)); end function; function MyShape(T) return [#x : x in T]; end function; function ToPartition(T) return [#x : x in T]; end function; function EnsureTabNotMagma(T) try temp := T in TabM; catch e temp:= false; end try; if temp then T:=PTab(ElementToSequence(RowWord(T))); end if; return T; end function; function EnsureTabMagma(T) try temp:= T in TabM; catch e try T:=Tableau([O! arow : arow in T]); catch e T := Tableau([O![99999]]); end try; end try; return T; end function; function SuperStandard(mu, k) return [[i+k-1: x in [1..mu[i]] ]: i in [1..#mu]]; end function; function EasyUnStandardize(w,mu) nn := &+mu; nw := [0:i in [1..nn]]; iw := Inverse(w); s := &cat(SuperStandard(mu,0)); for i in [1..nn] do nw[iw[i]] := s[i]; end for; return nw; end function; function OuterCorners(S) x:=[S[i] ne S[i+1]:i in [1..((#S)-1)]]cat [true]; return [ : r in [1..#S] | x[r]]; end function; function CoCyclage(T,i,j) T,k:=InverseRowInsert(T,i,j); tT:=Conjugate(T); return Conjugate(RowInsert(tT,k)); end function; function Cyclage(T,i,j:whatelement:=false) tT:=Conjugate(T); T,k:=InverseRowInsert(tT,j,i); T:=Conjugate(T); if whatelement then return ; else return RowInsert(T,k); end if; end function; function Catabolism(T,mu) w:=ElementToSequence(RowWord(T)); c:=#mu; r:=&+[Shape(T)[i]:i in [c+1..(#Shape(T))]]; w:=[w[modd(i,#w)]:i in [r+1..(r+#w)]]; //print "w",w; P,Q := RSKCorrespondence(O!w); return P; end function; function InitBlock(T) r:=ElementToSequence(Row(T,1)); k:=Position([r[i] eq i:i in [1..#r]],false); if k eq 0 then return #r; else return k-1; end if; end function; function RowCatable(T) mu:=[]; Append(~mu,InitBlock(T)); t:=Weight(T); while mu[#mu] ne t do T:=Catabolism(T,[Shape(T)[1]]); Append(~mu,InitBlock(T)); end while; nmu:=[mu[1]] cat [mu[i+1]-mu[i]:i in [1..((#mu)-1)]]; return nmu; end function; // ******************* End Tableau combinatorics ******************* // ****************** Miscellaneous ***************************** function DKEGraph(SH) nn := &+SH; Qs := StandardTableaux(SH); Rw := [ElementToSequence(RowWord(x)) : x in Qs]; Rwi := [Inverse(x) : x in Rw]; des := [{k : k in [1..(#x-1)] | x[k] gt x[k+1]} : x in Rwi]; out := []; for s in [2..(nn-1)] do M := Matrix([[0 : x in [1..#Qs]] : y in [1..#Qs]]); for r,c in [1..#Qs] do if #({s-1,s} meet des[r]) eq 1 then x1 := Rwi[r]; if Rwi[r][s+1] eq Sort([Rwi[r][j] : j in [s-1..s+1]])[2] then x1[s-1] := x1[s]; x1[s] := Rwi[r][s-1]; else x1[s] := x1[s+1]; x1[s+1] := Rwi[r][s]; end if; M[r][Position(Rwi,x1)] := 1; end if; end for; Append(~out,M); end for; return ; end function; //removes the nth letter of the word w function Restrict(w,n) w:=[w[i]:i in [1..#w]]; return Remove(w,Position(w,n)); end function; //adds a k to the end of the word w and increases all letters greater than or equal //to k by one function Induce (w,k) for i in [1..#w] do if w[i] ge k then w[i]:=w[i]+1; end if; end for; Append(~w,k); return w; end function; //right multiplies by the simple reflection s //if nodescentR is true then only multiply if length increases function RMult (w,s:nodescentR:=true) if nodescentR and w[s] gt w[s+1] then return w; else nw:=w; nw[s]:=w[s+1]; nw[s+1]:=w[s]; return nw; end if; end function; //left multiplies by the simple reflection s //if nodescentL is true then only multiply if length increases function LMult (w,s:nodescentL:=true) return Inverse(RMult(Inverse(w),s:nodescentR:=nodescentL)); end function; //returns a list of all subsequences of a sequence function Subsequences(list) subsets := [v: v in KSpace(GF(2),#list)]; return [ [list[i] : i in [1..#list]| s[i] eq 1] : s in subsets]; end function; function modd(k,n) return ((k-1) mod n) +1; end function; // ************************ End Miscellaneous ***********************