gap-libs 4r7p5-2 / usr / share / gap / lib / smgideal.gi

#############################################################################
##
#W  smgideal.gi              GAP library                     Robert Arthur
##
##
#Y  Copyright (C)  1996,  Lehrstuhl D für Mathematik,  RWTH Aachen,  Germany
#Y  (C) 1998 School Math and Comp. Sci., University of St Andrews, Scotland
#Y  Copyright (C) 2002 The GAP Group
##
##  This file contains generic methods for semigroup ideals.
##


#############################################################################
##
##  Immediate methods for
##
##  IsLeftSemigroupIdeal
##  IsRightSemigroupIdeal
##  IsSemigroupIdeal
##
#############################################################################
InstallImmediateMethod( IsLeftSemigroupIdeal,
    IsLeftMagmaIdeal and HasLeftActingDomain and IsAttributeStoringRep, 0,
    I -> HasIsSemigroup(LeftActingDomain(I)) and
         IsSemigroup(LeftActingDomain(I)) );

InstallImmediateMethod( IsRightSemigroupIdeal,
    IsRightMagmaIdeal and HasRightActingDomain and IsAttributeStoringRep, 0,
    I -> HasIsSemigroup(RightActingDomain(I)) and
         IsSemigroup(RightActingDomain(I)) );

InstallImmediateMethod(IsSemigroupIdeal,
    IsMagmaIdeal and HasActingDomain and IsAttributeStoringRep, 0,
    I -> HasIsSemigroup(ActingDomain(I)) and IsSemigroup(ActingDomain(I)) );


#############################################################################
#############################################################################
##                                                                         ##
##                   ENUMERATORS                                           ##
##                                                                         ##
#############################################################################
#############################################################################

#############################################################################
##
#F  RightSemigroupIdealEnumeratorDataGetElement( <enum>, <n> )
##
##  Returns a pair [T/F, elm], such that if <n> is less than or equal to
##  the size of the right ideal the first of the pair will be
##  true, and elm will be the element at the <n>th place.   Otherwise, the
##  first of the pair will be false.
##
BindGlobal( "RightSemigroupIdealEnumeratorDataGetElement",
    function( enum, n )
    local i, ideal, new;

    ideal:= UnderlyingCollection(enum);

    if n <= Length(enum!.currentlist) then
      return [true, enum!.currentlist[n]];
    fi;

    # Starting at the first non-expanded element of the list, multiply
    # every element of the list by generators, until it is large enough
    # to give the nth element.
    while IsBound(enum!.currentlist[enum!.nextelm]) do
      for i in enum!.gens do
        new:= enum!.currentlist[enum!.nextelm] * i;
        if not new in enum!.orderedlist then
          Add(enum!.currentlist, new);
          AddSet(enum!.orderedlist, new);
        fi;
      od;
      enum!.nextelm:= enum!.nextelm+1;

      # If we have now evaluated the element in the nth place
      if n <= Length(enum!.currentlist) then
        return [true, enum!.currentlist[n]];
      fi;
    od;

    # By now we have closed the list, and found it not to contain n
    # elements.
    if not HasAsSSortedList(ideal) then
      SetAsSSortedList(ideal, enum!.orderedlist);
    fi;
    return [false, 0];
    end );


#############################################################################
##
#F  LeftSemigroupIdealEnumeratorDataGetElement( <Enum>, <n> )
##
##  Returns a pair [T/F, elm], such that if <n> is less than or equal to
##  the size of the underlying left ideal the first of the pair will be
##  true, and elm will be the element at the <n>th place.   Otherwise, the
##  first of the pair will be false.
##
BindGlobal("LeftSemigroupIdealEnumeratorDataGetElement",
function (enum, n)

local i, ideal, new;

ideal:= UnderlyingCollection(enum);

if n <= Length(enum!.currentlist) then
return [true, enum!.currentlist[n]];
fi;

# Starting at the first non-expanded element of the list, multiply
# every element of the list by generators, until it is large enough
# to give the nth element.
while IsBound(enum!.currentlist[enum!.nextelm]) do
for i in enum!.gens do
new:= i * enum!.currentlist[enum!.nextelm];
if not new in enum!.orderedlist then
Add(enum!.currentlist, new);
AddSet(enum!.orderedlist, new);
fi;
od;
enum!.nextelm:= enum!.nextelm+1;

# If we have now evaluated the element in the nth place
if n <= Length(enum!.currentlist) then
return [true, enum!.currentlist[n]];
fi;
od;

# By now we have closed the list, and found it not to contain n
# elements.
if not HasAsSSortedList(ideal) then
SetAsSSortedList(ideal, enum!.orderedlist);
fi;
return [false, 0];
end);

#############################################################################
##
#F  SemigroupIdealEnumeratorDataGetElement( <Enum>, <n> )
##
##  Returns a pair [T/F, elm], such that if <n> is less than or equal to
##  the size of the underlying  ideal the first of the pair will be
##  true, and elm will be the element at the <n>th place.   Otherwise, the
##  first of the pair will be false.
##
BindGlobal("SemigroupIdealEnumeratorDataGetElement",
function (enum, n)

local i, j, new, onleft, ideal;

ideal:= UnderlyingCollection(enum);

if n <= Length(enum!.currentlist) then
return [true, enum!.currentlist[n]];
fi;

# Starting at the first non-expanded element of the list, multiply
# every element of the list by generators, until it is large enough
# to give the nth element.
onleft:= false;
while IsBound(enum!.currentlist[enum!.nextelm]) do
for i in enum!.gens do
for j in [1,2] do
if onleft then
new:= i * enum!.currentlist[enum!.nextelm];
else
new:= enum!.currentlist[enum!.nextelm] * i;
fi;
if not new in enum!.orderedlist then
Add(enum!.currentlist, new);
AddSet(enum!.orderedlist, new);
fi;
onleft:= not onleft;
od;
od;
enum!.nextelm:= enum!.nextelm+1;

# If we have now evaluated the element in the nth place
if n <= Length(enum!.currentlist) then
return [true, enum!.currentlist[n]];
fi;
od;

# By now we have closed the list, and found it not to contain n
# elements.
if not HasAsSSortedList(ideal) then
SetAsSSortedList(ideal, enum!.orderedlist);
fi;
return [false, 0];
end);


#############################################################################
##
#M  \[\]( <E>, <n> )
##
##  Returns the <n>th element of a right semigroup ideal enumerator.   Sets
##  AsSSorted list for the underlying ideal when all elements have been
##  found.
##
BindGlobal( "ElementNumber_SemigroupIdealEnumerator", function( enum, n )
    if IsBound( enum[n] ) then
      return( enum!.currentlist[n] );  # we know it to be bound, so
                                       # must have computed it!
    else
      Error("Position out of range");
    fi;
    end );


#############################################################################
##
#M  Position( <E>, <elm>, 0 )
##
##  There was no special `Position' method for these enumerators,
##  so we install a simpleminded approach.
##
BindGlobal( "NumberElement_SemigroupIdealEnumerator", function( enum, elm )
    local pos;

    if not IsCollsElms( FamilyObj( enum ), FamilyObj( elm ) ) then
      return fail;
    fi;

    pos:= 1;
    while IsBound( enum[ pos ] ) do
      if enum[ pos ] = elm then
        return pos;
      fi;
      pos:= pos + 1;
    od;
    return fail;
    end );


#############################################################################
##
#M  IsBound\[\]( <E>, <n> )
##
##  Returns true if the enumerator has size at least <n>.   This is the meat
##  of the enumerators calculation, with \[\] relying on it to set the
##  required data.
##
InstallGlobalFunction( IsBound_RightSemigroupIdealEnumerator,
    function( enum, n )
    return RightSemigroupIdealEnumeratorDataGetElement( enum, n )[1];
    end );

InstallGlobalFunction( IsBound_LeftSemigroupIdealEnumerator,
    function( enum, n )
    return LeftSemigroupIdealEnumeratorDataGetElement( enum, n )[1];
    end );

BindGlobal( "IsBound_SemigroupIdealEnumerator", function( enum, n )
    return SemigroupIdealEnumeratorDataGetElement( enum, n )[1];
    end );


#############################################################################
##
##  The following Length and \in methods are needed because of an
##  infinite recursion which is caused by the method
##  Size  "for a collection" calling
##  Length "for domain enumerator with underlying collection"
##  which in turn calls Size "for a collection" for the underlying collection.
##  This sets up the recursion.
##
##  The methods below insure we never get into this infinite recursion
##  with Semigroup enumerators.
##
##  Example:
##
##  f:=FreeSemigroup("a","b","c");
##  x:=GeneratorsOfSemigroup(f);
##  a:=x[1];;b:=x[2];;c:=x[3];;
##  r:= [ [a*b,b*a],[a*c,c*a],[b*c,c*b],[a*a,a],[b*b,b],[c*c,c] ];
##  s := f/r;
##  Size(s);
##
##  recursion depth trap (5000)
##  at
##  return Size( UnderlyingCollection( enum ) );
##  Length( Enumerator( C ) ) called from
##  Size( UnderlyingCollection( enum ) ) called from
##  Length( Enumerator( C ) ) called from
##  Size( UnderlyingCollection( enum ) ) called from
##  Length( Enumerator( C ) ) called from
##

#############################################################################
##
#M  Length(<semigroupenum>)
##
##  Find the length of the enumerator of a semigroup ideal enumerator.
##
BindGlobal( "Length_SemigroupIdealEnumerator", function( e )
    local n;

    n:=1;
    while IsBound(e[n]) do
      n := n+1;
    od;
    return n-1;
    end );


#############################################################################
##
#M  \in (obj, semigroupenum)
##
##  Needed only for infinite semigroups which do not have their own \in
##  method e.g. finitely presented semigroups.
##  For example a semigroup of matrices over a infinite domain.
##
##  m := [[2,3],[4,5]];
##  s := Semigroup(m);
##  [[2,3],[4,5]] in s;
##
##  Without the \in method below we would use the default case which
##  implicitly requires the Length of the semigroup to be computed never
##  terminating.
##
BindGlobal( "Membership_SemigroupIdealEnumerator", function( obj, enum )
    local i;

    i := 1;
    while IsBound( enum[i] ) do
      if obj = enum[i] then
        return true;
      fi;
      i := i +1;
    od;
    return false;
    end );


#############################################################################
##
#M  Enumerator( <I> ) . . . . . . . . . . . . . . for a right semigroup ideal
#M  Enumerator( <I> ) . . . . . . . . . . . . . .  for a left semigroup ideal
#M  Enumerator( <I> ) . . . . . . . . . . . for a (two sided) semigroup ideal
##
InstallGlobalFunction( EnumeratorOfSemigroupIdeal,
    function( I, actdom, isbound, gens )

    if not HasGeneratorsOfSemigroup( actdom ) then
      TryNextMethod();
    fi;

    return EnumeratorByFunctions( I, rec(
        ElementNumber := ElementNumber_SemigroupIdealEnumerator,
        NumberElement := NumberElement_SemigroupIdealEnumerator,
        IsBound\[\]   := isbound,
        Length        := Length_SemigroupIdealEnumerator,
        Membership    := Membership_SemigroupIdealEnumerator,

        currentlist   := ShallowCopy( AsSet( gens ) ),
        gens          := AsSet( GeneratorsOfSemigroup( actdom ) ),
        nextelm       := 1,
        orderedlist   := ShallowCopy( AsSet( gens ) ) ) );
    end );

InstallMethod( Enumerator,
    "for a right semigroup ideal",
    [ IsRightSemigroupIdeal and HasGeneratorsOfRightMagmaIdeal ],
    I -> EnumeratorOfSemigroupIdeal( I, RightActingDomain( I ),
             IsBound_RightSemigroupIdealEnumerator,
             GeneratorsOfRightMagmaIdeal( I ) ) );

InstallMethod( Enumerator,
    "for a left semigroup ideal",
    [ IsLeftSemigroupIdeal and HasGeneratorsOfLeftMagmaIdeal ],
    I -> EnumeratorOfSemigroupIdeal( I, LeftActingDomain( I ),
             IsBound_LeftSemigroupIdealEnumerator,
             GeneratorsOfLeftMagmaIdeal( I ) ) );

InstallMethod( Enumerator,
    "for a semigroup ideal",
    [ IsSemigroupIdeal and HasGeneratorsOfMagmaIdeal ],
    I -> EnumeratorOfSemigroupIdeal( I, ActingDomain( I ),
             IsBound_SemigroupIdealEnumerator,
             GeneratorsOfMagmaIdeal( I ) ) );


#############################################################################
##
#M  ReesCongruenceOfSemigroupIdeal( <I> )
##
##  A two sided ideal <I> of a semigroup <S>  defines a congruence on
##  <S> given by $\Delta \cup I \times I$.
##
InstallMethod(ReesCongruenceOfSemigroupIdeal,
    "for a two sided semigroup congruence",
    [ IsMagmaIdeal and IsSemigroupIdeal ],
    function(i)
    local mc;

    mc := LR2MagmaCongruenceByPartitionNCCAT(Parent(i),
              [Enumerator(i)], IsMagmaCongruence);
    SetIsSemigroupCongruence(mc, true);

    return mc;
    end );


#############################################################################
##
#M  PrintObj( <S> ) . . . . . . . . . . . . . . . . . .  for a SemigroupIdeal
##
InstallMethod( PrintObj,
    "for a semigroup ideal",
    [ IsMagmaIdeal and IsSemigroupIdeal ],
    function( S )
    Print( "SemigroupIdeal( ... )" );
    end );

InstallMethod( PrintObj,
    "for a semigroup ideal with known generators",
    [ IsMagmaIdeal and IsSemigroupIdeal and HasGeneratorsOfMagmaIdeal ],
    function( S )
    Print( "SemigroupIdeal( ", GeneratorsOfMagmaIdeal( S ), " )" );
    end );


#############################################################################
##
#M  ViewObj( <S> )  . . . . . . . . . . . . . . . . . .  for a SemigroupIdeal
##
InstallMethod( ViewObj,
    "for a semigroup ideal",
    [ IsMagmaIdeal and IsSemigroupIdeal ],
    function( S )
    Print( "<SemigroupIdeal>" );
    end );

InstallMethod( ViewObj,
    "for a semigroup ideal with known generators",
    [ IsMagmaIdeal and IsSemigroupIdeal and HasGeneratorsOfMagmaIdeal ],
    function( S )
    Print( "<semigroup ideal with ", Length(GeneratorsOfMagmaIdeal( S )),
           " generators>" );
    end );


#############################################################################
##
#E