good-ideals.gi

#############################################################################
##
#W  good-ideals.gi          Manuel Delgado <[email protected]>
#W                          Pedro A. Garcia-Sanchez <[email protected]>
##
#Y  Copyright 2016-- Centro de Matemática da Universidade do Porto, Portugal and IEMath-GR, Universidad de Granada, Spain
#############################################################################

#############################################################################
#####################        Defining Good Ideals           ######################
#############################################################################
##
#F GoodIdealOfGoodSemigroup(l,S)
##
## l is a list of pairs of integers and S a good semigroup
##
## returns the ideal of S generated by l.
##
#############################################################################
InstallGlobalFunction(GoodIdeal, function(l,S)
  local  I, sm, sms, c, cs, min, le, inf, x, conG2, cn;
      if not (IsGoodSemigroup(S) and IsHomogeneousList(l)) then
        Error("The arguments of GoodIdeal must be a good semigroup and a nonempty list of vectors.");
    fi;
    if not(ForAll(l, x->IsList(x) and ForAll(x,IsInt))) then
      Error("The first argument must be a list of pairs of integers");
    fi;

    le:=function(a,b)
      return (a[1]<=b[1]) and (a[2]<=b[2]);
    end;

    inf:=function(a,b)
      return [Minimum(a[1],b[1]),Minimum(a[2],b[2])];
    end;

    cs:=Conductor(S);
    sms:=SmallElementsOfGoodSemigroup(S);
    min := [Minimum(Set(l,x->x[1])),Minimum(Set(l,x->x[2]))];
    c:= cs+min;

    sm:=[];
    for x in l do
      sm:=Union(sm, Filtered(x+sms, y->le(min,y) and le(y,c)));
    od;

    sm:=Set(Cartesian(sm,sm), x->inf(x[1],x[2]));

    # now c might be sharpened and the sm redefined
    cn:=c;
    while ((c-[0,1]) in sm) or ((c-[1,0]) in sm) do
      if ((c-[0,1]) in sm) and ((c-[1,0]) in sm) then #c-[1,1] also in sm
        c:=c-[1,1];
      elif c-[0,1] in sm then
        c:=c-[0,1];
      else
        c:=c-[1,0];
      fi;
    od;
    if cn<>c then #sm must be redefined
      sm:=Filtered(sm, x->le(x,c));
    fi;
    conG2:=First(sm, x->x[1]<c[1] and ForAny(sm,y-> x[1]=y[1] and x[2]<y[2] and not(ForAny(sm, z->x[2]=z[2] and z[1]>x[1]))));
    if conG2<>fail then
        Error("The set given set does not generate a good ideal.");
    fi;
    conG2:=First(sm, x->x[2]<c[2] and ForAny(sm,y-> x[2]=y[2] and x[1]<y[1] and not(ForAny(sm, z->x[1]=z[1] and z[2]>x[2]))));
    if conG2<>fail then
      Error("The set given set does not generate a good ideal.");
    fi;

    sm:=Union(sm,[c]);
    I := rec();
    ObjectifyWithAttributes(I, GoodIdealType,
        AmbientGS, S,
        GoodGeneratorsIdealGS, Set(l),
        Conductor, c,
        SmallElementsOfGoodIdeal, sm,
        MinIGS, min
        );
    return I;
end );


#############################################################################
##
#M  ViewString(S)
##
##  This method for good ideals of good semigroups
##
#############################################################################

InstallMethod( ViewString,
        "prints a Good Ideal of a Good Semigroup",
        [ IsGoodIdeal],
        function( I )
    return ("Good ideal of good semigroup");
end);

#############################################################################
##
#M  ViewObj(S)
##
##  This method for good ideals of numerical semigroups.
##
#############################################################################

InstallMethod( ViewObj,
        "prints an Ideal of a Good Semigroup",
        [ IsGoodIdeal],
        function( I )
    Print("<Good ideal of good semigroup>");
end);

#############################################################################
##
#M  PrintObj(S)
##
##  This method for ideals of good semigroups.
##
#############################################################################
InstallMethod( PrintObj,
        "prints an Ideal of a Good Semigroup",
        [ IsGoodIdeal],
        function( I )
    # Improve this in the future
    Print("Ideal generated by ",GoodGeneratorsIdealGS(I),"\n"); #" + NumericalSemigroup( ", GeneratorsOfNumericalSemigroup(UnderlyingNSIdeal(I)), " )\n");
end);



#############################################################################
##
#F  GoodGeneratingSystemOfGoodIdeal(I)
##
##  Returns a set of generators of the ideal I.
##  If a minimal generating system has already been computed, this
##  is the set returned.
############################################################################
InstallGlobalFunction(GoodGeneratingSystemOfGoodIdeal,
  function(I)
    if not IsGoodIdeal(I) then
        Error("The argument must be an ideal of a good semigroup.");
    fi;
    if HasMinimalGoodGeneratorsIdealGS(I) then
       return (MinimalGoodGeneratorsIdealGS(I));
    fi;
    return(GoodGeneratorsIdealGS(I));
end);

#############################################################################
##
#F AmbientGoodSemigroupOfIdeal(I)
##
##  Returns the ambient semigroup of the ideal I.
############################################################################
InstallGlobalFunction(AmbientGoodSemigroupOfGoodIdeal, function(I)
    if not IsGoodIdeal(I) then
        Error("The argument must be a good ideal of a good semigroup.");
    fi;
    return(AmbientGS(I));
end);

#############################################################################
##
#A MinimalGoodGeneratingSystemOfGoodIdeal(I)
##
## The argument I is an ideal of a numerical semigroup
## returns the minimal generating system of I.
##
#############################################################################
InstallGlobalFunction(MinimalGoodGeneratingSystemOfGoodIdeal,
  function(I)
    local gens, S, sm, C; #member, member1, member2, inf, C, sm;

    if not IsGoodIdeal(I) then
        Error("The argument must be an ideal of a good semigroup.");
    fi;
    if HasMinimalGoodGeneratorsIdealGS(I) then
       return (MinimalGoodGeneratorsIdealGS(I));
    fi;
    gens:=ShallowCopy(GoodGeneratorsIdealGS(I));
    S:=AmbientGoodSemigroupOfGoodIdeal(I);
    # filtering gens by sums
    gens:=Filtered(gens, y->not(ForAny(gens, x-> x<> y and y-x in S)));
    C:=Conductor(I);
    # filtering gens by inf
    gens:=Filtered(gens, x->not(ForAny(gens,y ->y[1]=x[1] and y[2]>x[2]) and
      ForAny(gens, y->y[1]>x[1] and y[2]=x[2])));

    if IsGoodSemigroupByCartesianProduct(S) then
      SetMinimalGoodGeneratorsIdealGS(I,gens);
      return gens;
    fi;

    #experimental, we need to prove this
    sm:=SmallElementsOfGoodIdeal(I);
    gens:=Filtered(gens, x->not(ForAny(sm, y ->y[1]=x[1] and y[2]>x[2]) and
      ForAny(sm, y->y[1]>x[1] and y[2]=x[2])));
    SetMinimalGoodGeneratorsIdealGS(I,gens);
    return gens;
end);

###################################################
##
#M BelongsToGoodIdeal
## decides if a vector is in the ideal
##################################################
InstallMethod(BelongsToGoodIdeal,
  "for good ideals",
  [ IsHomogeneousList, IsGoodIdeal],
  function(v, i)
    local m, c, sm, le;

    le:=function(a,b)
      return (a[1]<=b[1]) and (a[2]<=b[2]);
    end;

    if not(IsHomogeneousList(v)) or Length(v)<>2 then
      Error("The first argument must be a list with two integers (a pair)");
    fi;
    if not(ForAll(v, IsInt)) then
      Error("The first argument must be a list with two integers (a pair)");
    fi;
    sm := SmallElementsOfGoodIdeal(i);
    m := MinIGS(i);
    c := Conductor(i);
    # see if we are in the box [0,c]
    if (le(m,v) and le(v,c)) then
      return v in sm;
    fi;
    # see if we are below right or left the minimum
    if (v[1]<m[1]) or (v[2]<m[2]) then
      return false;
    fi;
    # see if we are above the conductor
    if (le(c,v)) then
      return true;
    fi;
    # see if we are above the small elements
    # at this point v>= m, and not greater than c and not in the box [0,c]
    # see if we are at the left of the conductor
    if v[1]<c[1] then
      return [v[1],c[2]] in sm;
    fi;
  return [c[1],v[2]] in sm;
end);

###################################################
##
#M BelongsToGoodIdeal
## decides if a vector is in the semigroup
##################################################
InstallMethod( \in,
        "for good ideals",
        [ IsHomogeneousList, IsGoodIdeal], 100,
        function( v, i )
    return BelongsToGoodIdeal(v,i);
end);

#############################################################################
##
#A  ConductorOfIdeal(I)
##
##  Returns the conductor of I, the largest element in SmallElements(I)
##
#############################################################################
InstallMethod(Conductor,
  "Returns the conductor of an ideal",
  [IsGoodIdeal],
  function(I)
  local G,C,m;

  return Conductor(I);

end);

#############################################################################
##
#F  CanonicalIdealOfGoodSemigroup(s)
##
##  Computes a canonical ideal of <s>
##
#############################################################################

InstallGlobalFunction(CanonicalIdealOfGoodSemigroup,
  function(G)
  local s1,s2,sm, c, gamma, gen,x;

  if not(IsGoodSemigroup(G)) then
    Error("The argument must be a good semigroup");
  fi;

  c := Conductor(G);
  gamma:= c-[1,1];
  sm := SmallElementsOfGoodSemigroup(G);

  s1:=Set(sm, x->x[1]);
  s2:=Set(sm, x->x[2]);
  gen:=[];
  gen:=Concatenation(List(Difference([0..c[1]],s1), x1 -> [gamma[1]-x1,c[2]]),
  List(Difference([0..c[2]],s2), x2 -> [c[1],gamma[2]-x2]));

  for x in sm do
    if (x[1]<c[1]) and (x[2]<c[2])
      and not(ForAny(sm, y->(y[1]>x[1] and y[2]=x[2]) or (y[2]>x[2] and y[1]=x[1]))) then
      Add(gen,gamma-x);
    fi;
  od;

  return GoodIdeal(Set(gen),G);
end);