// MAGMA Code to check conjectures in 'The multistep homology of the simplex and // representations of symmetric groups', April 2018, Mark Wildon. // ---------------------------------------------------------------------------- // Specht modules and simple modules: sometimes necessary to specify the group // as a particular Sn. function SpechtModuleForGroup(xs, q, Sn); X := SymmetricRepresentation(xs, Sn.1 : Al := "Specht"); Y := SymmetricRepresentation(xs, Sn.2 : Al := "Specht"); d := NumberOfRows(X); G := GeneralLinearGroup(d, GF(q)); f := hom< Sn -> G | [G! X, G! Y]>; return GModule(f), f; end function; function SpechtModule(xs, p); n := &+ xs; Sn := SymmetricGroup(n); return SpechtModuleForGroup(xs,p,Sn); end function; function SimpleModuleForGroup(xs, p, G); S := SpechtModuleForGroup(xs, p, G); return quo; end function; function SimpleModule(xs, p); return SimpleModuleForGroup(xs, p, Sym(&+ xs)); end function; // ---------------------------------------------------------------------------- // Label composition factors of a two-row Young module (or anything else with only // two-row simple modules) by the p-regular labels. IdentifySimple uses a list of // pairs [<2-row label, simple module>], denoted Ds. function LabelledSimpleTwoRowModules(n, q); b, p := IsPrimePower(q); if p eq 2 then if IsEven(n) then m := n div 2 - 1; else m := (n-1) div 2; end if; else m := n div 2; end if; ps := [[n]] cat [[n-k,k] : k in [1..m]]; return [ : xs in ps]; end function; function IdentifySimple(Ds, U) ps := [p : p in Ds | IsIsomorphic(U, p[2])]; return ps[1][1]; end function; // ---------------------------------------------------------------------------- // Socle layers function SocleLayersBottomToTop(M); if Dimension(M) eq 0 then return []; end if; S := Socle(M); return [IndecomposableSummands(S)] cat SocleLayersBottomToTop(quo); end function; function SocleLayers(M); return Reverse(SocleLayersBottomToTop(M)); end function; function SocleLayersLabelledUsing(Ds, M); Ls := SocleLayers(M); return [[IdentifySimple(Ds, U) : U in L] : L in Ls]; end function; function SocleLayersLabelled(M); F := Field(M); n := Degree(Group(M)); Ds := LabelledSimpleTwoRowModules(n, #F); return SocleLayersLabelledUsing(Ds, M); end function; function SocleLayersLabelledSummandsTwoRow(M); return [SocleLayersLabelled(N) : N in IndecomposableSummands(M)]; end function; function SocleLayersLabelledSummandsTwoRowMany(Ms); if Ms eq [] then return []; end if; F := Field(Ms[1]); n := Degree(Group(Ms[1])); Ds := LabelledSimpleTwoRowModules(n, #F); return [[SocleLayersLabelledUsing(Ds, N) : N in IndecomposableSummands(M)] : M in Ms]; end function; // ---------------------------------------------------------------------------- // Young Permutation Modules function TwoRowYoungSubgroup(n, k); if k eq 0 or k eq n then return Sym(n); end if; return YoungSubgroup([k,n-k]); end function; function TwoRowYoungPermutationModule(p, n, k); if k lt 0 then M := sub; return M; end if; return PermutationModule(Sym(n), TwoRowYoungSubgroup(n,k), GF(p)); end function; function DecomposeTwoRowYoungPermutationModule(p, n, k); return SocleLayersLabelledSummandsTwoRow(TwoRowYoungPermutationModule(p, n, k)); end function; // ---------------------------------------------------------------------------- // It seems that when MAGMA creates a permutation module M = F(H \ G), the i-th // basis vector M.i is M.1^g for g in a deterministically chosen transversal of // H \ G. The next function checks this for a given module and transversal. function CheckTransversal(M, gs); f := GModuleAction(M); checkRightSize := Dimension(M) eq #gs; checkConsistent := &and [M.1^f(gs[i]) eq M.i : i in [1..#gs]]; return checkRightSize and checkConsistent; end function; function CheckTransversalWithError(M, gs); if not CheckTransversal(M, gs) then error "Transversal not consistent with permutation basis"; else return true; end if; end function; // ---------------------------------------------------------------------------- // Construction of Phi maps from paper: often necessary to use a specific copy of // the module, so compatible with later compositions etc. function PhiMapGivenModules(M, k, N, l); Sn := Group(M); n := Degree(Sn); H := TwoRowYoungSubgroup(n, k); gs := Transversal(Sn, H); b := CheckTransversalWithError(M, gs); if l lt 0 then return hom N | [M.i -> N! 0 : i in [1..Binomial(n,k)]]>; end if; K := TwoRowYoungSubgroup(n, l); ks := Transversal(H, H meet K); f := GModuleAction(N); w := &+ [N.1^f(k) : k in ks]; return hom N | [M.i -> w^f(gs[i]) : i in [1..Binomial(n,k)]]>; end function; function PhiMap(p, n, k, l); M := TwoRowYoungPermutationModule(p, n, k); N := TwoRowYoungPermutationModule(p, n, l); return PhiMapGivenModules(M, k, N, l); end function; // Given a list of degrees, return all phi maps (lowering degree), greatest degree first function PhiMaps(p, n, ks); ksInc := Sort(ks); Ms := [TwoRowYoungPermutationModule(p, n, k) : k in ksInc]; phis := [PhiMapGivenModules(Ms[i+1], ksInc[i+1], Ms[i], ksInc[i]) : i in [1..#ksInc-1]]; return Reverse(Ms), Reverse(phis), Reverse(ksInc); end function; // ---------------------------------------------------------------------------- // All homology modules for given degrees: when p=2 should be ... k+t, k, k-t, ... // for general primes ... k + s, k, k - t, ... where s+t carries in base p. function PhiHomologyInDegrees(p, n, ks); Ms, phis, ks := PhiMaps(p, n, ks); // can put ks in any order here, but when back from PhiMaps will be decreasing, as l-to-r reading isSurjective := Image(phis[#phis]) eq Codomain(phis[#phis]); isInjective := Dimension(Kernel(phis[1])) eq 0; Ks := [Kernel(phis[i]) : i in [1..#phis]]; Is := [Image(phis[i]) : i in [1..#phis]]; kHs := [> : i in [2..#phis]]; return isInjective, kHs, isSurjective, [ : i in [1..#phis]]; end function; function PhiHomologyInDegreesIdentified(p, n, ks); isInjective, kHs, isSurjective := PhiHomologyInDegrees(p, n, ks); return isInjective, [ : kH in kHs], isSurjective; end function; function PhiHomologyIdentified(p, n, t, a); ks := [a + j * t : j in [0..(n-a) div t]]; return PhiHomologyInDegreesIdentified(p, n, ks); end function; // ---------------------------------------------------------------------------- // Homology modules for two-step sequence ... a + 2s + t, a + s + t, a + s, a // (see Section 7 of paper) function TwoStepDegrees(n, s, t, a); function f(j); if IsEven(j) then return a + (s+t)*(j div 2); else return a + (s+t)*((j-1) div 2) + s; end if; end function; jE := (n-a) div (s+t); if f(2*jE) + s gt n then jM := 2*jE; else jM := 2*jE+1; end if; return [f(j) : j in [0..jM]]; // NB these are in increasing order end function; function PhiHomologyTwoStepIdentified(p, n, s, t, a); ks := TwoStepDegrees(n, s, t, a); return PhiHomologyInDegreesIdentified(p, n, ks); end function; function PhiHomologyAllTwoStepsIdentified(p, n, s, t); R := [* *]; for k in [t..n-s] do isInjective, kHs, isSurjective := PhiHomologyInDegreesIdentified(p, n, [k+s, k, k-t]); Append(~R, ); end for; return R; end function; function PhiSurjectives(p, n, t); fs := [ : k in [t..2*t-1]]; ts := [ : p in fs]; return ts; end function; // ---------------------------------------------------------------------------- // Homology modules after restriction to kernels (Section 7 of paper): phisR are // the maps stepping down s degrees: their kernels are the modules in the chain // complex for restricted homology. function PhiHomologyRestrictedInDegrees(p, n, ks, s); Ms, phis, ks := PhiMaps(p, n, ks); Ns := [TwoRowYoungPermutationModule(p, n, k-s) : k in ks]; phisR := [PhiMapGivenModules(Ms[i], ks[i], Ns[i], ks[i]-s) : i in [1..#ks]]; Rs := [Kernel(phisR[i]) : i in [1..#ks]]; isSurjective := phis[#phis](Rs[#ks-1]) eq Rs[#ks]; isInjective := Dimension(Kernel(phis[1]) meet Rs[1]) eq 0; Ks := [Kernel(phis[i]) meet Rs[i] : i in [1..#phis]]; Is := [phis[i](Rs[i]) : i in [1..#phis]]; kHs := [> : i in [2..#phis]]; return ; end function; function PhiHomologyRestrictedIdentified(p, n, t, s, a); ks := Reverse([a+t*j : j in [0..(n-a) div t]]); return ; end function; // ---------------------------------------------------------------------------- // Generators v_k for two-step boundary map kernels and check for base case in // Theorem 1.1. function SubsetsToVector(M, Ys); Sn := Group(M); n := Degree(Sn); k := #Ys[1]; H := TwoRowYoungSubgroup(n, k); gs := Transversal(Sn, H); b := CheckTransversalWithError(M, gs); X := {1..k}; function f(Y); js := [j : j in [1..#gs] | X^gs[j] eq Y]; if js eq [] then Y; error "SubsetsToVector: set not found!"; end if; j := js[1]; v := M! 0; v[j] := 1; return v; end function; return &+ [f(Y) : Y in Ys]; end function; function VGenGenerator(M, k, l); Sn := Group(M); Y := {2*j : j in {1..k}}; G := sub; Ys := [Y^g : g in G]; return SubsetsToVector(M, Ys), Ys; end function; function VGenerator(M, k); return VGenGenerator(M, k, k-1); end function; function HomologyIsVGenGenerated(t, n, k); l := k-t+1; Ms, phis := PhiMaps(2, n, [k+t, k, k-t]); Mkp := Ms[1]; Mk := Ms[2]; Mkm := Ms[3]; phip := phis[1]; phi := phis[2]; K := Kernel(phi); I := Image(phip); v := VGenGenerator(Mk, k, l); Ie := sub; return K, I, Ie, K eq Ie, K eq sub; end function; function CheckHomology(t, n, k); K, I, Ie, check := HomologyIsVGenGenerated(t, n, k); return check; end function; // Check is run at the end of this file // ---------------------------------------------------------------------------- // Example 1.4 checking: e.g. use SocleLayersLabelledSummandsTwoRow(M4) to see // the Loewy layers for the summands Y^{(6)} + Y^{(4,2)} in M^{(4,2)} = F_2\Omega_4 Ms, phisM6 := PhiMaps(2, 6, [6,5,4,3,2,1,0]); M6 := Ms[1]; M5 := Ms[2]; M4 := Ms[3]; M3 := Ms[4]; M2 := Ms[5]; M1 := Ms[6]; M0 := Ms[7]; Ns, phisN6 := PhiMaps(4, 6, [6,5,4,3,2,1,0]); N6 := Ns[1]; N5 := Ns[2]; N4 := Ns[3]; N3 := Ns[4]; N2 := Ns[5]; N1 := Ns[6]; N0 := Ns[7]; // ---------------------------------------------------------------------------- // Checking conjectures in Section 7 of paper /* Conjecture 7.2 and related function CheckHomologyAll(t, n); return [ : k in [0..n div 2]]; end function; CheckHomologyAll(4,8); CheckHomologyAll(4,9); CheckHomologyAll(4,10); CheckHomologyAll(4,11); CheckHomologyAll(4,12); CheckHomologyAll(4,13); CheckHomologyAll(4,14); CheckHomologyAll(4,15); CheckHomologyAll(4,16); CheckHomologyAll(8,16); */ // Kernel may not be generated by symmetrized v, even when the homology is zero // HomologyIsVGenGenerated(2,8,4); HomologyIsVGenGenerated(2,10,4); // Shows that for t not a two-power homology module may not be generated by symmetrized v // HomologyIsVGenGenerated(3,10,5); /* Conjectures 7.3, 7.4 PhiHomologyRestrictedIdentified(2,6,2,1,0); PhiHomologyRestrictedIdentified(2,6,2,1,1); PhiHomologyRestrictedIdentified(2,7,2,1,0); PhiHomologyRestrictedIdentified(2,7,2,1,1); PhiHomologyRestrictedIdentified(2,8,2,1,0); PhiHomologyRestrictedIdentified(2,8,2,1,1); PhiHomologyRestrictedIdentified(2,8,2,1,1); PhiHomologyRestrictedIdentified(2,9,2,1,0); PhiHomologyRestrictedIdentified(2,9,2,1,1); PhiHomologyRestrictedIdentified(2,10,2,1,0) PhiHomologyRestrictedIdentified(2,10,2,1,1); PhiHomologyRestrictedIdentified(2,11,2,1,0); PhiHomologyRestrictedIdentified(2,12,2,1,0); PhiHomologyRestrictedIdentified(2,11,2,1,1); PhiHomologyRestrictedIdentified(2,12,2,1,1); PhiHomologyRestrictedIdentified(2,3,1,2,0); PhiHomologyRestrictedIdentified(2,4,1,2,0); PhiHomologyRestrictedIdentified(2,5,1,2,0); PhiHomologyRestrictedIdentified(2,6,1,2,0); PhiHomologyRestrictedIdentified(2,7,1,2,0); PhiHomologyRestrictedIdentified(2,8,1,2,0); PhiHomologyRestrictedIdentified(2,9,1,2,0); PhiHomologyRestrictedIdentified(2,10,1,2,0); PhiHomologyRestrictedIdentified(2,11,1,2,0); PhiHomologyRestrictedIdentified(2,12,1,2,0); */ /* Conjectures 7.5, 7.6 PhiHomologyAllTwoStepsIdentified(3,3,1,2); PhiHomologyAllTwoStepsIdentified(3,4,1,2); PhiHomologyAllTwoStepsIdentified(3,5,1,2); PhiHomologyAllTwoStepsIdentified(3,6,1,2); PhiHomologyAllTwoStepsIdentified(3,7,1,2); PhiHomologyAllTwoStepsIdentified(3,8,1,2); PhiHomologyAllTwoStepsIdentified(3,9,1,2); PhiHomologyAllTwoStepsIdentified(3,10,1,2); PhiHomologyAllTwoStepsIdentified(3,11,1,2); PhiHomologyAllTwoStepsIdentified(3,12,1,2); PhiHomologyAllTwoStepsIdentified(3,3,2,1); PhiHomologyAllTwoStepsIdentified(3,4,2,1); PhiHomologyAllTwoStepsIdentified(3,5,2,1); PhiHomologyAllTwoStepsIdentified(3,6,2,1); PhiHomologyAllTwoStepsIdentified(3,7,2,1); PhiHomologyAllTwoStepsIdentified(3,8,2,1); PhiHomologyAllTwoStepsIdentified(3,9,2,1); PhiHomologyAllTwoStepsIdentified(3,10,2,1); PhiHomologyAllTwoStepsIdentified(3,11,2,1); PhiHomologyAllTwoStepsIdentified(3,12,2,1); PhiHomologyAllTwoStepsIdentified(5,3,1,4); PhiHomologyAllTwoStepsIdentified(5,4,1,4); PhiHomologyAllTwoStepsIdentified(5,5,1,4); PhiHomologyAllTwoStepsIdentified(5,6,1,4); PhiHomologyAllTwoStepsIdentified(5,7,1,4); PhiHomologyAllTwoStepsIdentified(5,8,1,4); PhiHomologyAllTwoStepsIdentified(5,9,1,4); PhiHomologyAllTwoStepsIdentified(5,10,1,4); PhiHomologyAllTwoStepsIdentified(5,11,1,4); PhiHomologyAllTwoStepsIdentified(5,12,1,4); PhiHomologyAllTwoStepsIdentified(5,3,4,1); PhiHomologyAllTwoStepsIdentified(5,4,4,1); PhiHomologyAllTwoStepsIdentified(5,5,4,1); PhiHomologyAllTwoStepsIdentified(5,6,4,1); PhiHomologyAllTwoStepsIdentified(5,7,4,1); PhiHomologyAllTwoStepsIdentified(5,8,4,1); PhiHomologyAllTwoStepsIdentified(5,9,4,1); PhiHomologyAllTwoStepsIdentified(5,10,4,1); PhiHomologyAllTwoStepsIdentified(5,11,4,1); PhiHomologyAllTwoStepsIdentified(5,12,4,1); */ // Checking base cases in Theorem 1.1: this is the only logically essential part of the // paper requiring a check by computer algebra print "Checking base cases (n,k) = (6,3), (7,3), (8,3), (8,4), (9,4), (10,5) in Theorem 1.1"; CheckHomology(2,6,3); CheckHomology(2,7,3); CheckHomology(2,8,3); CheckHomology(2,8,4); CheckHomology(2,9,4); CheckHomology(2,10,5);