present.gi

#############################################################################
##
#W present.gi       Alnuth - ALgebraic NUmber THeory         Bjoern Assmann
##

#############################################################################
##
#F GeneratorLatticeTF( rels )
##
## rels is a sublattice of Z^n.
## this function compute a minimal generatorset of Z^n/rels
## which is torsion-free
##
GeneratorLatticeTF := function( rels )
    local n, normal,i,gens;

    n := Length( rels[1] );
    normal:=NormalFormIntMat(rels,13);
    for i in [1..Length( normal.normal )] do
        if normal.normal[i][i] <> 1 then
            break;
        fi;
    od;
    if i = Length( normal.normal ) then
        i := i+1;
    fi;
    #gens := IdentityMat( n );
    #gens := gens{[i..n]};
    #gens := gens * normal.coltrans^-1;    

    gens := (normal.coltrans^-1);
    gens := gens{[i..n]};
    return gens;
end;

#############################################################################
##
#F CPCSOfTFGroupByFieldElements( F, gens )
##
## computes a constructive polycyclic sequence for gens
##
CPCSOfTFGroupByFieldElements := function( F, gens )
    local rels, exps, newGens, e, newRels;

    rels := RelationLatticeTF( F, gens );
    if rels = [] then
        return  rec( gens:=gens,  
                     relord:=List([1..Length(gens)], x -> 0));
    fi;
    exps := GeneratorLatticeTF(rels); 
    newGens := [];
    for e in exps do
        Add( newGens, MappedVector( e, gens ));
    od;
    newRels := List( [1..Length(newGens)], x -> 0);
    return rec( gens:=newGens,  relord:=newRels);
end;

#############################################################################
##
#F ExpVectorOfTFGroupByFieldElements( F, CPCS, elm )
##
## torsion free group !!
##
ExpVectorOfTFGroupByFieldElements := function( F, CPCS, elm )
    local elms, rels, v, m, exp, i;

    m := Length( CPCS.gens );
    elms := StructuralCopy( CPCS.gens );
    Add( elms, elm );
    rels:= RelationLatticeTF( F, elms );
    v := rels[1];
    exp:=[];
    for i in [1..m] do
        exp[i]:=-v[i]/v[m+1];
    od;
    Assert( 2, MappedVector( exp, CPCS.gens ) = elm );
    return exp;
end;

#############################################################################
##
#F Exp2genList(exp);
##
Exp2GenList:= function(exp)
    local n, genList,i;
    n:=Length(exp);
    genList:=[];
    for i in [1..n] do
        if exp[i] <> 0 then
            Append(genList,[i,exp[i]]);
        fi;
    od;
    return genList; 
end;

#############################################################################
##
#F PCPOfTFGroupByFieldElementsByCPCS( F, CPCS )
##
PCPOfTFGroupByFieldElementsByCPCS := function( F, CPCS ) 
    local ro, n;
    # Setup
    ro := CPCS.relord;
    n := Length( CPCS.gens );
    return AbelianPcpGroup( n, ro );
end;

#############################################################################
##
#F PcpPresentationOfTFGroupByFieldElements( F, elms )
##
## given a field F and elms in F.
## this function computes a polycyclic presentation for the group
## generated by elms
##
PcpPresentationOfTFGroupByFieldElements := function( F, elms )
    local CPCS, pcp;
    CPCS :=  CPCSOfTFGroupByFieldElements( F, elms ); 
    pcp := PCPOfTFGroupByFieldElementsByCPCS( F, CPCS );

    return pcp;
end;

#############################################################################
# generalization to groups with torsion

#############################################################################
##
#F GeneratorLattice( rels )
##
## rels is a sublattice of Z^n.
## this function compute a minimal generatorset of Z^n/rels
## and the orders of the generators.
##
GeneratorLattice := function( rels )
    local n, normal,i,gens, torsion, relord, j;

    torsion := false;
    n := Length( rels[1] );
    normal:=NormalFormIntMat(rels,13);
    for i in [1..Length( normal.normal )] do
        if normal.normal[i][i] <> 1 then
            torsion := true;
            break;
        fi;
    od;
    if not torsion then
        i := i+1;
    fi;
    #gens := IdentityMat( n );
    #gens := gens{[i..n]};
    #gens := gens * normal.coltrans^-1;    

    gens := (normal.coltrans^-1);
    gens := gens{[i..n]};

    # set relative orders of gens
    relord := [];
    for j in [i..n] do
        if IsBound(normal.normal[j]) then 
            Add( relord, normal.normal[j][j] );
        else 
            Add( relord, 0 );
        fi;
    od;
    return rec(exps := gens, relord:=relord );
end;

#############################################################################
##
#F CPCSOfGroupByFieldElements( F, gens )
##
## computes a constructive polycyclic sequence for gens
##
CPCSOfGroupByFieldElements := function( F, gens )
    local rels, exps, newGens, e, newRels;

    rels := RelationLattice( F, gens );
    if rels = [] then
        return  rec( gens:=gens,  
                     relord:=List([1..Length(gens)], x -> 0));
    fi;
    exps := GeneratorLattice(rels); 
    newGens := [];
    for e in exps.exps do
        Add( newGens, MappedVector( e, gens ));
    od;
    return rec( gens:=newGens,  relord:=exps.relord);
end;

#############################################################################
##
#F ExpVectorOfGroupByFieldElements( F, CPCS, elm )
##
ExpVectorOfGroupByFieldElements := function( F, CPCS, elm )
    local elms, rels, l, m, exp, i;

    if IsList(CPCS.gens[1]) then
        if Length(elm) <> Length(CPCS.gens[1]) then
            return fail;
        fi;
    fi;
    m := Length( CPCS.gens ); 
    if elm=elm^0 then
        return List([1..m], x-> 0);
    fi;
    elms := StructuralCopy( CPCS.gens );
    l :=Concatenation([elm],elms);
    rels := RelationLattice( F, l );
    if rels=[] then
        return fail;
    fi;
    rels := NormalFormIntMat(rels,0).normal;
    if not rels[1][1]=1 then return fail; fi;
    exp := -rels[1]{[2..(m+1)]};
    Assert( 2, MappedVector( exp, CPCS.gens ) = elm, 
            "failure in ExpVectorOfGroupByFieldElements" );
    return exp;
end;

#############################################################################
##
#F PCPOfGroupByFieldElementsByCPCS( F, CPCS )
##
PCPOfGroupByFieldElementsByCPCS := function( F, CPCS ) 
    local ro, n;
    # Setup
    ro := CPCS.relord;
    n := Length( CPCS.gens );
    return AbelianPcpGroup( n, ro );
end;

#############################################################################
##
#F PcpPresentationOfGroupByFieldElements( F, elms )
##
## given a field F and elms in F.
## this function computes a polycyclic presentation for the group
## generated by elms
##
PcpPresentationOfGroupByFieldElements := function( F, elms )
    local CPCS, pcp;
    CPCS :=  CPCSOfGroupByFieldElements( F, elms ); 
    pcp := PCPOfGroupByFieldElementsByCPCS( F, CPCS );

    return pcp;
end;
 
InstallGlobalFunction( PcpPresentationMultGroupByFieldEl, function( F, elms )
    local CPCS, pcp;
    CPCS :=  CPCSOfGroupByFieldElements( F, elms ); 
    pcp := PCPOfGroupByFieldElementsByCPCS( F, CPCS );

    return pcp; 
end);

InstallGlobalFunction( PcpPresentationOfMultiplicativeSubgroup, function( F, elms )
    local CPCS, pcp;
    CPCS :=  CPCSOfGroupByFieldElements( F, elms ); 
    pcp := PCPOfGroupByFieldElementsByCPCS( F, CPCS );

    return pcp; 
end);


#############################################################################
# test functions

RandomGroupElement := function(gens)
    local d,k,g,i,length,x,n;
    k:=Length(gens);
    g:=gens[1]^0;
    length:=Random(5,30);
    for i in [1..length] do
        x:=Random(1,k);
        n:=Random(Integers);
        g:=g*(gens[x]^n);
    od;
    return g;
end;

TestExpVectorOfGroupByFieldElements :=function( F, CPCS, gens,numberOfTests)
    local i,g,exp;
    SetAssertionLevel(2);
    for i in [1..numberOfTests] do
        Print(i);
        g:=RandomGroupElement(gens);
        #Print("g ist gleich ",g,"\n");
        exp:=ExpVectorOfGroupByFieldElements( F, CPCS, g );
        #Print("exp ist gleich ",exp,"\n");
    od;
    SetAssertionLevel(0);
end;


TestCPCSOfGroupByFieldElements := function( mats )
    local F,j, CPCS;
    F := FieldByMatricesNC( mats );
    #j := Random([1..Length(mats)]);
    j := Length(mats); 
    CPCS:=CPCSOfGroupByFieldElements( F, mats{[1..j]} );
    TestExpVectorOfGroupByFieldElements( F, CPCS, mats{[1..j]},10);
end;

# faster
TestCPCSOfGroupByFieldElements2 := function( mats )
    local F,j, CPCS,b;
    F := FieldByMatricesNC( mats );
    b := Basis( F );
    F := FieldByMatrixBasisNC( b );
    #j := Random([1..Length(mats)]); 
    j := Length(mats);
    CPCS:=CPCSOfGroupByFieldElements( F, mats{[1..j]} );
    TestExpVectorOfGroupByFieldElements( F, CPCS, mats{[1..j]},10);
end;

TestCPCSOfGroupByFieldElementsPol := function( pol )
    local elms,F,j, CPCS;
    F := FieldByPolynomialNC( pol );
    elms := List( [1..10], x-> Random(F) );
    CPCS:=CPCSOfGroupByFieldElements( F, elms );
    TestExpVectorOfGroupByFieldElements( F, CPCS, elms,10);
end;