# This script will prove that certain universal regular tessellations are
# infinite.

# Run with gap -o 2g infiniteUniversalRegularTessellationProofs.g
# It takes about half an hour for it to finish.

# Gives a finite representation of the symmetry group of a universal regular
# tessellation of type {p, q, r} and cusp modulus a + bu
SymmetriesUniversalRegularTessellation := function(p, q, r, a, b)

    local F, P, Q, R, rels;
    F := FreeGroup(3);;
    P := F.1;; Q := F.2;; R := F.3;;

    rels := [ P^p, Q^q, R^r, (P*Q)^2, (Q*R)^2, (P*Q*R)^2,
              (Q*R^(r/2+1))^a * (R*Q*R^(r/2))^b];;

    return F/rels;
end;;

# Gives the n-th derived subgroup of G
IteratedDerivedSubgroup := function(G, n)
    if n = 0 then
        return G;
    fi;
    return DerivedSubgroup(IteratedDerivedSubgroup(G, n - 1));
end;;

# Gives all subgroups with index n of a group G
MySubgroups := function(G, n)
    local subGroups;

    subGroups := LowIndexSubgroupsFpGroup(G,n);

    return Filtered(subGroups, H -> (Index(G,H) = n));
end;;

# Proof that G is infinite.
# Given G, it takes the n-th derived subgroup G^(n) (n = numDerivedSubgroup),
# then takes subgroups H of G with given index and considers epimorphisms
# into the simple group Q. It checks whether there is an epimorphism with
# infinite kernel K by applying the Newman criterion for prime newmanOrder
# or by checking that the Abelianization contains Z.
MyIsInfinite := function(G, numDerivedSubgroup, index, Q, newmanOrder)

    local H1, H2, hom, K, A;
    H1 := IteratedDerivedSubgroup(G, numDerivedSubgroup);

    for H2 in MySubgroups(H1, index) do
        for hom in GQuotients(H2, Q) do
            K := Kernel(hom);;
            A := AbelianInvariants(K);;
            if newmanOrder = 0 then
                if 0 in A then
                    return true;
                fi;
            else
                if newmanOrder in A then
                    if NewmanInfinityCriterion(K, newmanOrder) = true then
                        return true;
                    fi;
                fi;
            fi;
        od;
    od;

    return fail;
end;;

# Proof that the universal regular tessellation of type {p, q, r} and cusp
# modulus z = a + bu is infinite invoking the above functions. See MyIsInfinite
# explaining the remaining parameters.
#
# The method will print its result.

PrintInfinityProof := function(p, q, r, a, b,
                       numDerivedSubgroup, index, Q, newmanOrder)
    local G;    

    G := SymmetriesUniversalRegularTessellation(p, q, r, a, b);
    
    if MyIsInfinite(G, numDerivedSubgroup, index, Q, newmanOrder) = true then
        Print("U {",p,",",q,",",r,"} z= ",a,"+",b,"u  is infinite\n");
    else
        Print("Failure!!!!!!!!!\n");
    fi;
end;;

# The list of cases we want to prove!

PrintInfinityProof(4, 3, 6, 2, 2,
                   3, 1, TrivialGroup(), 0);

PrintInfinityProof(4, 3, 6, 3, 0,
                   3, 1, TrivialGroup(), 0);

PrintInfinityProof(4, 3, 6, 3, 1,
                   1, 1, PSL(3, 3), 0);

PrintInfinityProof(4, 3, 6, 3, 2,
                   0, 2, PSL(2, 19), 5);

PrintInfinityProof(4, 3, 6, 4, 0,
                   0, 8, AlternatingGroup(5), 0);

PrintInfinityProof(4, 3, 6, 4, 1,
                   1, 3, PSL(2, 7), 0);

PrintInfinityProof(4, 3, 6, 5, 0,
                   1, 3, AlternatingGroup(5), 0);

PrintInfinityProof(5, 3, 6, 2, 2,
                   1, 1, AlternatingGroup(7), 0);

PrintInfinityProof(5, 3, 6, 3, 0,
                   0, 6, AlternatingGroup(5), 0);

PrintInfinityProof(5, 3, 6, 3, 1,
                   1, 26, PSL(2, 11), 0);

PrintInfinityProof(5, 3, 6, 3, 2,
                   0, 20, TrivialGroup(), 0);

PrintInfinityProof(5, 3, 6, 4, 0,
                   1, 5, PSL(2, 13), 0);

PrintInfinityProof(5, 3, 6, 4, 1,
                   1, 10, PSL(2, 7), 3);

PrintInfinityProof(5, 3, 6, 5, 0,
                   0, 1, PSL(2, 25), 0);

PrintInfinityProof(3, 4, 4, 4, 3,
                   1, 15, PSp(4,3), 0);

PrintInfinityProof(3, 4, 4, 5, 1,
                   2, 1, PSL(2, 25), 0);