Add tests for homomorphisms

[ChrisJefferson]

A common mistake is for people to define ActionHomomorphisms which are not valid.

It isn't reasonable for us to test every ActionHomomorphism, but we could provide helper functions we can at least point people at. It might be possible in some cases where code fails to then run these to see if we can tell why it failed. There are two functions here, one that does a random check if 10,000 elements, and one that checks the full group (which will of course only work for small, finite, G and Omega).

I've had these pieces of code lying around for a while, I'm curious if anyone has any comments, before I polish them up and make a PR:

FullTestActionHomomorphism := function(G, Omega, act)
    local p1,p2,j;

    p1 := One(G);
    for j in Omega do
        if act(j,p1) <> j then
            Error("Identity: act(",j,",",p1, "<>",j);
        fi;
    od;

    for p1 in G do
        for j in Omega do
            if not(act(j,p1) in Omega) then
                Error("Closure: act(",j,",",p1, "not in Omega");
            fi;
        od;
    od;

    for p1 in G do
        for p2 in G do
            for j in Omega do
                if act(act(j,p1),p2) <> act(j,p1*p2) then
                    Error("Homomorphism: act(act(",j,",",p1,"),",p2,") != act(",j,",",p1*p2,"))");
                fi;
            od;
        od;
    od;
end;

RandomTestActionHomomorphism := function(G, Omega, act)
    local p1,p2,j, loop;

    p1 := One(G);
    for loop in [1..10000] do
        j := Random(Omega);
        if act(j,p1) <> j then
            Error("Identity: act(",j,",",p1, "<>",j);
        fi;
    od;

    for loop in [1..10000] do
        p1 := Random(G);
        p2 := Random(Omega);
        if not(act(j,p1) in Omega) then
            Error("act(Closure: ",j,",",p1, "not in Omega");
        fi;
    od;

    for loop in [1..10000] do
        p1 := Random(G);
        p2 := Random(G);
        j := Random(Omega);
        if act(act(j,p1),p2) <> act(j,p1*p2) then
            Error("Homomorphism: act(act(",j,",",p1,"),",p2,") != act(",j,",",p1*p2,"))");
        fi;
    od;
end;

FullTestActionHomomorphism(SymmetricGroup(4), Arrangements([1..4], 4), OnTuples);
RandomTestActionHomomorphism(SymmetricGroup(4), Arrangements([1..4], 4), OnTuples);
FullTestActionHomomorphism(SymmetricGroup(4), Combinations([1..4], 3), OnSets);
RandomTestActionHomomorphism(SymmetricGroup(4), Combinations([1..4], 3), OnSets);

[hulpke]

I agree that illegal actions are an recurring issue of "errors between keyboard and chair".

There is already TestIdentityAction that is used to map one point under the identity and catches situations of actions that are not well-defined. One could add more. The main problem I see is what tests to do in which situations, so that the tests do not impact performance.

• Actions might be a low-level call to convert from an intractable group to a permutation group
• Actions can be very expensive (say when acting on subgroups) and we don't want to do this for generic testing
• How many tests would be plausible to do. Basically you want to do a far less if the routine is called within extra code. So maybe do it based on an assertion level >1.
• Random might rely on a NiceMonomorphism that uses an action. Probably use PseudoRandom.

One cheap test would be for a fail in `Permutation (either image not found, or not a valid permutation and not throw an error about a list access a[fail] being illegal, but that an image wasn't found and that could mean that an action was ill defined.