affine-def.gi

#############################################################################
##
#W  affine-def.gi           Manuel Delgado <[email protected]>
#W                          Pedro Garcia-Sanchez <[email protected]>
##
#Y  Copyright 2015-- Centro de Matemática da Universidade do Porto, Portugal and Universidad de Granada, Spain
#############################################################################
#################        Defining Affine Semigroups           ###############
###############################################################################
##
#F AffineSemigroupByGenerators(arg)
##
## Returns the affine semigroup generated by arg.
##
## The argument arg is either a list of lists of positive integers of equal length (a matrix) or consists of lists of integers with equal length
#############################################################################
InstallGlobalFunction(AffineSemigroupByGenerators, function(arg)
  local  gens, M;


  if Length(arg) = 1 then
    gens := Set(arg[1]);
  else
    gens := Set(arg);
  fi;

  if not IsMatrix(gens) then
    Error("The arguments must be lists of non negative integers with the same length, or a list of such lists");
  elif not ForAll(gens, l -> ForAll(l,x -> (IsPosInt(x) or x = 0))) then
    Error("The arguments must be lists of non negative integers with the same length, or a list of such lists");
  fi;
  M:= Objectify( AffineSemigroupsType, rec());

  SetGenerators(M,gens);
  SetDimension(M,Length(gens[1]));

#  Setter(IsAffineSemigroupByGenerators)(M,true);
  return M;
end);
#############################################################################
##
#O  Generators(S)
##
##  Computes a set of generators of the affine semigroup S.
##  If a set of generators has already been computed, this
##  is the set returned.
############################################################################
InstallMethod(Generators,
         "Computes a set of generators of the affine semigroup",
         [IsAffineSemigroup],1,
        function(S)
  local  basis, eq;

  if HasGenerators(S) then
      return Generators(S);
  fi;
  if HasMinimalGenerators(S) then
      return MinimalGenerators(S);
  fi;

  if HasEquations(S) then
      eq:=Equations(S);
      basis := HilbertBasisOfSystemOfHomogeneousEquations(eq[1],eq[2]);
      SetMinimalGenerators(S,basis);
      return MinimalGenerators(S);
  elif HasInequalities(S) then
      basis := HilbertBasisOfSystemOfHomogeneousInequalities(AffineSemigroupInequalities(S));
      SetMinimalGenerators(S,basis);
      return MinimalGenerators(S);
  fi;
end);

#############################################################################
##
#O  MinimalGenerators(S)
##
##  Computes the set of minimal  generators of the affine semigroup S.
##  If a set of generators has already been computed, this
##  is the set returned.
############################################################################
InstallMethod(MinimalGenerators,
         "Computes the set of minimal generators of the affine semigroup",
         [IsAffineSemigroup],1,
        function(S)
  local  basis, eq, gen;

  if HasMinimalGenerators(S) then
      return MinimalGenerators(S);
  fi;

  if HasEquations(S) then
      eq:=Equations(S);
      basis := HilbertBasisOfSystemOfHomogeneousEquations(eq[1],eq[2]);
      SetMinimalGenerators(S,basis);
      return MinimalGenerators(S);
  elif HasInequalities(S) then
      basis := HilbertBasisOfSystemOfHomogeneousInequalities(AffineSemigroupInequalities(S));
      SetMinimalGenerators(S,basis);
      return MinimalGenerators(S);
  fi;
  gen:=Generators(S);
  basis:=Filtered(gen, y->ForAll(Difference(gen,[y]),x->not((y-x) in S)));
  SetMinimalGenerators(S,basis);
  return MinimalGenerators(S);

end);

#############################################################################
##
#O  Inequalities(S)
##
##  If S is defined by inequalities, it returns them.
############################################################################
InstallMethod(Inequalities,
         "Computes the set of equations of S, if S is a affine semigroup",
         [IsAffineSemigroup and HasInequalities],1,
        function(S)
          return AffineSemigroupInequalities(S);
end);
#############################################################################
## Full ffine semigroups
#############################################################################
##
#F  AffineSemigroupByEquations(ls,md)
##
##  Returns the (full) affine semigroup defined by the system A X=0 mod md, where the rows
## of A are the elements of ls.
##
#############################################################################
InstallGlobalFunction(AffineSemigroupByEquations, function(arg)
  local  ls, md, M;

  if Length(arg) = 1 then
    ls := arg[1][1];
    md := arg[1][2];
  else
    ls := arg[1];
    md := arg[2];
  fi;

  if not(IsHomogeneousList(ls)) or not(IsHomogeneousList(md)) then
    Error("The arguments must be homogeneous lists.");
  fi;

  if not(ForAll(ls,IsListOfIntegersNS)) then
    Error("The first argument must be a list of lists of integers.");
  fi;

  if not(md = [] or IsListOfIntegersNS(md)) then
    Error("The second argument must be a lists of integers.");
  fi;

  if not(ForAll(md,x->x>0)) then
    Error("The second argument must be a list of positive integers");
  fi;

  if not(Length(Set(ls, Length))=1) then
    Error("The first argument must be a list of lists all with the same length.");
  fi;

  M:= Objectify( AffineSemigroupsType, rec());
  SetEquations(M,[ls,md]);
  SetDimension(M,Length(ls[1]));

#  Setter(IsAffineSemigroupByEquations)(M,true);
#  Setter(IsFullAffineSemigroup)(M,true);
  return M;
end);

#############################################################################
##
#F  AffineSemigroupByInequalities(ls)
##
##  Returns the (full) affine semigroup defined by the system  ls*X>=0 over
##  the nonnegative integers
##
#############################################################################
InstallGlobalFunction(AffineSemigroupByInequalities, function(arg)
  local  ls, M;

  if Length(arg) = 1 then
    ls := Set(arg[1]);
  else
    ls := Set(arg);
  fi;

  if not IsMatrix(ls) then
    Error("The arguments must be lists of integers with the same length, or a list of such lists");
  fi;

  M:= Objectify( AffineSemigroupsType, rec());

  SetAffineSemigroupInequalities(M,ls);
  SetDimension(M,Length(ls[1]));
 # Setter(IsAffineSemigroupByEquations)(M,true);
 # Setter(IsFullAffineSemigroup)(M,true);
  return M;
end);


#############################################################################

#############################################################################
##
#F  AffineSemigroup(arg)
##
##  This function's first argument may be one of:
##  "generators", "equations", "inequalities"...
##
##  The following arguments must conform to the arguments of
##  the corresponding function defined above.
##  By default, the option "generators" is used, so,
##  gap> AffineSemigroup([1,3],[7,2],[1,5]);
##  <Affine semigroup in 3-dimensional space, with 3 generators>
##
##
#############################################################################
InstallGlobalFunction(AffineSemigroup, function(arg)

  if IsString(arg[1]) then
    if arg[1] = "generators" then
      return AffineSemigroupByGenerators(Filtered(arg, x -> not IsString(x))[1]);
    elif arg[1] = "equations" then
      return AffineSemigroupByEquations(Filtered(arg, x -> not IsString(x))[1]);
    elif arg[1] = "inequalities" then
      return AffineSemigroupByInequalities(Filtered(arg, x -> not IsString(x))[1]);
    else
      Error("Invalid first argument, it should be one of: \"generators\", \"minimalgenerators\" ");
    fi;
  elif Length(arg) = 1 and IsList(arg[1]) then
    return AffineSemigroupByGenerators(arg[1]);
  else
    return AffineSemigroupByGenerators(arg);
  fi;
end);

#############################################################################
##
#P  IsAffineSemigroupByGenerators(S)
##
##  Tests if the affine semigroup S was given by generators.
##
#############################################################################
 # InstallMethod(IsAffineSemigroupByGenerators,
 #         "Tests if the affine semigroup S was given by generators",
 #         [IsAffineSemigroup],
 #         function( S )
 #   return(HasGeneratorsAS( S ));
 # end);
#############################################################################
##
#P  IsAffineSemigroupByMinimalGenerators(S)
##
##  Tests if the affine semigroup S was given by its minimal generators.
##
#############################################################################
 # InstallMethod(IsAffineSemigroupByMinimalGenerators,
 #         "Tests if the affine semigroup S was given by its minimal generators",
 #         [IsAffineSemigroup],
 #         function( S )
 #   return(HasIsAffineSemigroupByMinimalGenerators( S ));
 # end);
#############################################################################
##
#P  IsAffineSemigroupByEquations(S)
##
##  Tests if the affine semigroup S was given by equations or equations have already been computed.
##
 #############################################################################
 # InstallMethod(IsAffineSemigroupByEquations,
 #         "Tests if the affine semigroup S was given by equations",
 #         [IsAffineSemigroup],
 #         function( S )
 #   return(HasEquationsAS( S ));
 # end);

#############################################################################
##
#P  IsAffineSemigroupByInequalities(S)
##
##  Tests if the affine semigroup S was given by inequalities or inequalities have already been computed.
##
# #############################################################################
 # InstallMethod(IsAffineSemigroupByInequalities,
 #         "Tests if the affine semigroup S was given by inequalities",
 #         [IsAffineSemigroup],
 #         function( S )
 #   return(HasInequalitiesAS( S ));
 # end);

#############################################################################
##
#P  IsFullAffineSemigroup(S)
##
##  Tests if the affine semigroup S has the property of being full.
##
# Detects if the affine semigroup is full: the nonnegative
# of the the group spanned by it coincides with the semigroup
# itself; or in other words, if a,b\in S and a-b\in \mathbb N^n,
# then a-b\in S
#############################################################################
 InstallMethod(IsFullAffineSemigroup,
         "Tests if the affine semigroup S has the property of being full",
         [IsAffineSemigroup],1,
         function( S )
   local  gens, eq, h, dim;

   if HasEquations(S) then
     return true;
   fi;


   gens := GeneratorsOfAffineSemigroup(S);
   if gens=[] then
       return true;
   fi;
   dim:=Length(gens[1]);
   eq:=EquationsOfGroupGeneratedBy(gens);
   if eq[1]=[] then
       h:=IdentityMat(dim);
   else
       h:=HilbertBasisOfSystemOfHomogeneousEquations(eq[1],eq[2]);
   fi;
  if ForAll(h, x->BelongsToAffineSemigroup(x,S)) then
    SetEquations(S,eq);
    #Setter(IsAffineSemigroupByEquations)(S,true);
    #Setter(IsFullAffineSemigroup)(S,true);
    return true;
  fi;
  return false;

end);


#############################################################################
 ##
 #M  PrintObj(S)
 ##
 ##  This method for affine semigroups.
 ##
 #############################################################################
InstallMethod( PrintObj,
        "Prints an Affine Semigroup",
        [ IsAffineSemigroup],
        function( S )
  if HasGenerators(S) then
    Print("AffineSemigroup( ", Generators(S), " )\n");
  elif HasEquations(S) then
    Print("AffineSemigroupByEquations( ", Equations(S), " )\n");
  elif HasInequalities(S) then
    Print("AffineSemigroupByInequalities( ", Inequalities(S), " )\n");
  else
    Print("AffineSemigroup( ", GeneratorsOfAffineSemigroup(S), " )\n");
  fi;
end);



 #############################################################################
 ##
 #M  ViewString(S)
 ##
 ##  This method for affine semigroups.
 ##
 #############################################################################
 InstallMethod( ViewString,
         "Displays an Affine Semigroup",
         [IsAffineSemigroup],
         function( S )
   if HasMinimalGenerators(S) then
         return Concatenation("Affine semigroup in ", String(Length(MinimalGenerators(S)[1]))," dimensional space, with ", String(Length(MinimalGenerators(S))), " generators");
     elif HasGenerators(S) then
         return Concatenation("Affine semigroup in ", String(Length(Generators(S)[1]))," dimensional space, with ", String(Length(Generators(S))), " generators");
     else
         return ("<Affine semigroup>");
     fi;
 end);


 #############################################################################
 ##
 #M  ViewObj(S)
 ##
 ##  This method for affine semigroups.
 ##
 #############################################################################
 InstallMethod( ViewObj,
         "Displays an Affine Semigroup",
         [IsAffineSemigroup],
         function( S )
   if HasMinimalGenerators(S) then
         Print("<Affine semigroup in ", Length(MinimalGenerators(S)[1])," dimensional space, with ", Length(MinimalGenerators(S)), " generators>");
     elif HasGenerators(S) then
         Print("<Affine semigroup in ", Length(Generators(S)[1])," dimensional space, with ", Length(Generators(S)), " generators>");
     else
         Print("<Affine semigroup>");
     fi;
 end);



 #############################################################################
 ##
 #M  Display(S)
 ##
 ##  This method for affine semigroups. ## under construction... (= View)
 ##
 #############################################################################
InstallMethod( Display,
         "Displays an Affine Semigroup",
         [IsAffineSemigroup],
         function( S )
     if HasMinimalGenerators(S) then
         Print("<Affine semigroup in ", Length(MinimalGenerators(S)[1]),"-dimensional space, with ", Length(MinimalGenerators(S)), " generators>");
     elif HasGenerators(S) then
         Print("<Affine semigroup in ", Length(Generators(S)[1]),"-dimensional space, with ", Length(Generators(S)), " generators>");
     else
         Print("<Affine semigroup>");
     fi;
 end);



 ####################################################
 ####################################################


 ############################################################################
 ##
 #M Methods for the comparison of affine semigroups.
 ##
 InstallMethod( \=,
         "for two numerical semigroups",
         [IsAffineSemigroup and IsAffineSemigroupRep,
          IsAffineSemigroup and IsAffineSemigroupRep],
         function(x, y )
   local  genx, geny;

   if Dimension(x) <> Dimension(y) then
     return false;
   fi;

   if  HasEquations(x) and HasEquations(y) and
       Equations(x) = Equations(y) then
     return true;

   elif HasInequalities(x) and HasInequalities(y) and
     AffineSemigroupInequalities(x) = AffineSemigroupInequalities(y) then
     return true;

   elif HasGenerators(x) and HasGenerators(y) and
     Generators(x) = Generators(y) then
     return  true;

   elif HasGenerators(x) and HasGenerators(y) and not(EquationsOfGroupGeneratedBy(Generators(x))=EquationsOfGroupGeneratedBy(Generators(y))) then
     return false;
   fi;
   genx:=GeneratorsOfAffineSemigroup(x);
   geny:=GeneratorsOfAffineSemigroup(y);
   return ForAll(genx, g-> g in y) and
          ForAll(geny, g-> g in x);
 end);

 ## x < y returns true if:  (dimension(x)<dimension(y)) or (x is (strictly) contained in y) or (genx < geny), where genS is the *current* set of generators of S...
 InstallMethod( \<,
         "for two affine semigroups",
         [IsAffineSemigroup,IsAffineSemigroup],
         function(x, y )
   local  genx, geny;

   if Dimension(x) < Dimension(y) then
     return true;
   fi;

   genx:=GeneratorsOfAffineSemigroup(x);
   geny:=GeneratorsOfAffineSemigroup(y);
   if ForAll(genx, g-> g in y) and not ForAll(geny, g-> g in x) then
     return true;
   fi;

   return genx < geny;
end );


#############################################################################
##
#F AsAffineSemigroup(S)
##
## Takes a numerical semigroup as argument and returns it as affine semigroup
##
#############################################################################
InstallGlobalFunction(AsAffineSemigroup, function(s)
    local msg;

    if not(IsNumericalSemigroup(s)) then
        Error("The argument must be a numerical semigroup");
    fi;

    msg:=MinimalGeneratingSystem(s);
    return AffineSemigroup(List(msg, x->[x]));

end);