// 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<S | JacobsonRadical(S)>;
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, SimpleModule(xs, q)> : 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<M | S>);
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<TrivialModule(Sym(n), GF(p)) | 0>; 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<M -> 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<M -> 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          := [<ks[i], quo<Ks[i] | Is[i-1]>> : i in [2..#phis]];
    return isInjective, kHs, isSurjective, [<ks[i], Ks[i]> : i in [1..#phis]];
end function;

function PhiHomologyInDegreesIdentified(p, n, ks);
    isInjective, kHs, isSurjective := PhiHomologyInDegrees(p, n, ks);
    return isInjective, [<kH[1], SocleLayersLabelledSummandsTwoRow(kH[2]), Dimension(kH[2])> : 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, <k+s, k, k-t, kHs>);
    end for;
    return R;
end function;

function PhiSurjectives(p, n, t);
    fs := [<k, PhiMap(p, n, k, k-t)> : k in [t..2*t-1]];
    ts := [<p[1], Image(p[2]) eq Codomain(p[2])> : 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          := [<ks[i], quo<Ks[i] | Is[i-1]>> : i in [2..#phis]];
    return <isInjective, kHs, isSurjective, Rs>;
end function;

function PhiHomologyRestrictedIdentified(p, n, t, s, a);
    ks := Reverse([a+t*j : j in [0..(n-a) div t]]);
    return <ks, PhiHomologyRestrictedInDegrees(p, n, ks, s)>;
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<Sn | [Sn! (2*j-1,2*j) : j in [1..l]]>;
    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<Mk | I, v>;
    return K, I, Ie, K eq Ie, K eq sub<Mk | v>;   
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, CheckHomology(t, n, k)> : 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);