[GAP Forum] methods for Igs and PreImagesRepresentative

[Yoongbok Lee]

I’m doing a research project that uses two different methods for solving the membership search problem in polycyclic groups. The first one is Igs, and the second one is using homomorphism. As I need to understand what each of the methods are doing beneath the surface, general explanation of the two methods (for each while loops and for loops) and what specific methods they are using would be really appreciated.

I found the source codes for both of them:

Igs
InstallGlobalFunction( AddToIgs, function( igs, gens )
    local coll, rels, todo, n, ind, g, d, h, k, eg, eh, e, f, c, i, l;

    if Length( gens ) = 0 then return igs; fi;

    # get information
    coll := Collector( gens[1] );
    rels := RelativeOrders( coll );
    n    := NumberOfGenerators( coll );

    # create new list from igs
    ind  := ListWithIdenticalEntries(n, false );
    for g in igs do ind[Depth(g)] := g; od;

    # set counter and add tail as far as possible
    c := UpdateCounter( ind, gens, n+1 );

    # create a to-do list and a pointer
    todo := Set( Filtered( gens, x -> Depth( x ) < c ) );

    # loop over to-do list until it is empty
    while Length( todo ) > 0 and c > 1 do

        g := Remove( todo );
        d := Depth( g );
        f := [];

        # shift g into ind
        while d < c do
            h := ind[d];
            if not IsBool( h ) then

                # reduce g with h
                eg := LeadingExponent( g );
                eh := LeadingExponent( h );
                e  := Gcdex( eg, eh );

                # adjust ind[d] by gcd
                ind[d] := (g^e.coeff1) * (h^e.coeff2);
                if e.coeff1 <> 0 then Add( f, d ); fi;

                # adjust g
                g := (g^e.coeff3) * (h^e.coeff4);
            else

                # just add g into ind
                ind[d] := g;
                g := g^0;
                Add( f, d );
            fi;
           d := Depth( g );
            c := UpdateCounter( ind, todo, c );
        od;

        # now add powers and commutators
        for d in f do
            g := ind[d];
            if d <= Length( rels ) and rels[d] > 0 and d < c then
                k := g ^ RelativeOrderPcp( g );
                if Depth(k) < c then  Add( todo, k ); fi;
            fi;
            for l in [1..n] do
                if not IsBool( ind[l] ) and ( d < c  or l < c ) then
                    k := Comm( g, ind[l] );
                    if Depth(k) < c then  Add( todo, k ); fi;
                fi;
            od;
        od;

        # try sorting
        Sort( todo );

    od;

    # return resulting list
    return Filtered( ind, x -> not IsBool( x ) );
end );


PreImagesRepresentative:

InstallMethod( PreImagesRepresentative,
    "for Fp to SCA mapping, and element",
    FamRangeEqFamElm,
    [ IsFptoSCAMorphism, IsSCAlgebraObj ], 0, 
        
    function( f, x )        
        
    local   IsLyndonT,  dim,  e,  gens,  imgs,  b1,  b2,  levs,  
            brackets,  sp,  deg,  newlev,  newbracks,  d,  br1,  br2,  
            i,  j,  a,  b,  c,  z,  imz,  cf;
    
    IsLyndonT:= function( t )

        # This function tests whether the bracketed expression `t' is
        # a Lyndon tree.
        
        local w,w1,w2,b,y;

        if not IsList( t ) then return true; fi;
        
        w:= Flat( t );
        if IsList( t[1] ) then
            w1:= Flat( t[1] );
            b:= false;
        else
            w1:= [ t[1] ];
            b:=true;
        fi;
        if IsList( t[2] ) then
            w2:= Flat( t[2] );
        else
            w2:= [ t[2] ];
        fi;
        
        if w<w2 and w1<w2 then
            if not b then
                y:= Flat( [ t[1][2] ] );
                if y  < w2 then return false; fi;
            fi;
        else
            return false;
        fi;
        
        if not IsLyndonT( t[1] ) then return false; fi;
        if not IsLyndonT( t[2] ) then return false; fi;
        return true;
        
    end;
       
    if not IsBound( f!.bases ) then
        
        # We find bases of the source and the range that are mapped to 
        # each other.

        dim:= Dimension( Range(f) );
        e:=MappingGeneratorsImages(f);
        gens:= e[1];
       imgs:= e[2];
        b1:= ShallowCopy( gens ); 
        b2:= ShallowCopy( imgs );
        levs:= [ gens ];
        brackets:= [ [1..Length(gens)] ];
        sp:= MutableBasis( LeftActingDomain(Range(f)), b2 );
        deg:= 1;
        while Length( b1 ) <> dim do
            deg:= deg+1;
            newlev:= [ ];
            newbracks:= [ ];
            # get all Lyndon elements of degree deg:
            for d in [1..Length(brackets)] do
                if Length( b1 ) = dim then break; fi;
                br1:= brackets[d];
                br2:= brackets[deg-d];
                for i in [1..Length(br1)] do
                    if Length( b1 ) = dim then break; fi;
                    for j in [1..Length(br2)] do
                        if Length( b1 ) = dim then break; fi;
                        a:= br1[i]; b:= br2[j];
                        if IsLyndonT( [a,b] ) then
                            c:= [a,b];
                            z:= levs[d][i]*levs[deg-d][j];
                        elif IsLyndonT( [b,a] ) then
                            c:= [b,a];
                            z:= levs[deg-d][j]*levs[d][i];
                        else
                            c:= [ ];
                        fi;
                        
                        if c <> [] then

                            imz:= Image( f, z );
                            if not IsContainedInSpan( sp, imz ) then
                                CloseMutableBasis( sp, imz );
                                Add( b1, z );
                                Add( newlev, z );
                                Add( newbracks, c );
                                Add( b2, imz );
                            fi;
                        fi;
                        
                    od;
                od;
            od;
            Add( levs, newlev );
            Add( brackets, newbracks );
        od;

        f!.bases:= [ b1, Basis( Range(f), b2 ) ];
    fi;
    
    cf:= Coefficients( f!.bases[2], x );
    return cf*f!.bases[1];
        
end);

Windows 10용 메일에서 보냄