1#############################################################################
2##
3#W  good-ideals.gi          Manuel Delgado <mdelgado@fc.up.pt>
4#W                          Pedro A. Garcia-Sanchez <pedro@ugr.es>
5##
6#Y  Copyright 2016-- Centro de Matemática da Universidade do Porto, Portugal and IEMath-GR, Universidad de Granada, Spain
7#############################################################################
8
9#############################################################################
10#####################        Defining Good Ideals           ######################
11#############################################################################
12##
13#F GoodIdealOfGoodSemigroup(l,S)
14##
15## l is a list of pairs of integers and S a good semigroup
16##
17## returns the ideal of S generated by l.
18##
19#############################################################################
20InstallGlobalFunction(GoodIdeal, function(l,S)
21  local  I, sm, sms, c, cs, min, le, inf, x, conG2, cn;
22      if not (IsGoodSemigroup(S) and IsHomogeneousList(l)) then
23        Error("The arguments of GoodIdeal must be a good semigroup and a nonempty list of vectors.");
24    fi;
25    if not(ForAll(l, x->IsList(x) and ForAll(x,IsInt))) then
26      Error("The first argument must be a list of pairs of integers");
27    fi;
28
29    le:=function(a,b)
30      return (a[1]<=b[1]) and (a[2]<=b[2]);
31    end;
32
33    inf:=function(a,b)
34      return [Minimum(a[1],b[1]),Minimum(a[2],b[2])];
35    end;
36
37    cs:=Conductor(S);
38    sms:=SmallElementsOfGoodSemigroup(S);
39    min := [Minimum(Set(l,x->x[1])),Minimum(Set(l,x->x[2]))];
40    c:= cs+min;
41
42    sm:=[];
43    for x in l do
44      sm:=Union(sm, Filtered(x+sms, y->le(min,y) and le(y,c)));
45    od;
46
47    sm:=Set(Cartesian(sm,sm), x->inf(x[1],x[2]));
48
49    # now c might be sharpened and the sm redefined
50    cn:=c;
51    while ((c-[0,1]) in sm) or ((c-[1,0]) in sm) do
52      if ((c-[0,1]) in sm) and ((c-[1,0]) in sm) then #c-[1,1] also in sm
53        c:=c-[1,1];
54      elif c-[0,1] in sm then
55        c:=c-[0,1];
56      else
57        c:=c-[1,0];
58      fi;
59    od;
60    if cn<>c then #sm must be redefined
61      sm:=Filtered(sm, x->le(x,c));
62    fi;
63    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]))));
64    if conG2<>fail then
65        Error("The set given set does not generate a good ideal.");
66    fi;
67    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]))));
68    if conG2<>fail then
69      Error("The set given set does not generate a good ideal.");
70    fi;
71
72    sm:=Union(sm,[c]);
73    I := rec();
74    ObjectifyWithAttributes(I, GoodIdealType,
75        AmbientGS, S,
76        GoodGeneratorsIdealGS, Set(l),
77        Conductor, c,
78        SmallElementsOfGoodIdeal, sm,
79        MinIGS, min
80        );
81    return I;
82end );
83
84
85#############################################################################
86##
87#M  ViewString(S)
88##
89##  This method for good ideals of good semigroups
90##
91#############################################################################
92
93InstallMethod( ViewString,
94        "prints a Good Ideal of a Good Semigroup",
95        [ IsGoodIdeal],
96        function( I )
97    return ("Good ideal of good semigroup");
98end);
99
100#############################################################################
101##
102#M  ViewObj(S)
103##
104##  This method for good ideals of numerical semigroups.
105##
106#############################################################################
107
108InstallMethod( ViewObj,
109        "prints an Ideal of a Good Semigroup",
110        [ IsGoodIdeal],
111        function( I )
112    Print("<Good ideal of good semigroup>");
113end);
114
115#############################################################################
116##
117#M  PrintObj(S)
118##
119##  This method for ideals of good semigroups.
120##
121#############################################################################
122InstallMethod( PrintObj,
123        "prints an Ideal of a Good Semigroup",
124        [ IsGoodIdeal],
125        function( I )
126    # Improve this in the future
127    Print("Ideal generated by ",GoodGeneratorsIdealGS(I),"\n"); #" + NumericalSemigroup( ", GeneratorsOfNumericalSemigroup(UnderlyingNSIdeal(I)), " )\n");
128end);
129
130
131
132#############################################################################
133##
134#F  GoodGeneratingSystemOfGoodIdeal(I)
135##
136##  Returns a set of generators of the ideal I.
137##  If a minimal generating system has already been computed, this
138##  is the set returned.
139############################################################################
140InstallGlobalFunction(GoodGeneratingSystemOfGoodIdeal,
141  function(I)
142    if not IsGoodIdeal(I) then
143        Error("The argument must be an ideal of a good semigroup.");
144    fi;
145    if HasMinimalGoodGeneratorsIdealGS(I) then
146       return (MinimalGoodGeneratorsIdealGS(I));
147    fi;
148    return(GoodGeneratorsIdealGS(I));
149end);
150
151#############################################################################
152##
153#F AmbientGoodSemigroupOfIdeal(I)
154##
155##  Returns the ambient semigroup of the ideal I.
156############################################################################
157InstallGlobalFunction(AmbientGoodSemigroupOfGoodIdeal, function(I)
158    if not IsGoodIdeal(I) then
159        Error("The argument must be a good ideal of a good semigroup.");
160    fi;
161    return(AmbientGS(I));
162end);
163
164#############################################################################
165##
166#A MinimalGoodGeneratingSystemOfGoodIdeal(I)
167##
168## The argument I is an ideal of a numerical semigroup
169## returns the minimal generating system of I.
170##
171#############################################################################
172InstallGlobalFunction(MinimalGoodGeneratingSystemOfGoodIdeal,
173  function(I)
174    local gens, S, sm, C; #member, member1, member2, inf, C, sm;
175
176    if not IsGoodIdeal(I) then
177        Error("The argument must be an ideal of a good semigroup.");
178    fi;
179    if HasMinimalGoodGeneratorsIdealGS(I) then
180       return (MinimalGoodGeneratorsIdealGS(I));
181    fi;
182    gens:=ShallowCopy(GoodGeneratorsIdealGS(I));
183    S:=AmbientGoodSemigroupOfGoodIdeal(I);
184    # filtering gens by sums
185    gens:=Filtered(gens, y->not(ForAny(gens, x-> x<> y and y-x in S)));
186    C:=Conductor(I);
187    # filtering gens by inf
188    gens:=Filtered(gens, x->not(ForAny(gens,y ->y[1]=x[1] and y[2]>x[2]) and
189      ForAny(gens, y->y[1]>x[1] and y[2]=x[2])));
190
191    if IsGoodSemigroupByCartesianProduct(S) then
192      SetMinimalGoodGeneratorsIdealGS(I,gens);
193      return gens;
194    fi;
195
196    #experimental, we need to prove this
197    sm:=SmallElementsOfGoodIdeal(I);
198    gens:=Filtered(gens, x->not(ForAny(sm, y ->y[1]=x[1] and y[2]>x[2]) and
199      ForAny(sm, y->y[1]>x[1] and y[2]=x[2])));
200    SetMinimalGoodGeneratorsIdealGS(I,gens);
201    return gens;
202end);
203
204###################################################
205##
206#M BelongsToGoodIdeal
207## decides if a vector is in the ideal
208##################################################
209InstallMethod(BelongsToGoodIdeal,
210  "for good ideals",
211  [ IsHomogeneousList, IsGoodIdeal],
212  function(v, i)
213    local m, c, sm, le;
214
215    le:=function(a,b)
216      return (a[1]<=b[1]) and (a[2]<=b[2]);
217    end;
218
219    if not(IsHomogeneousList(v)) or Length(v)<>2 then
220      Error("The first argument must be a list with two integers (a pair)");
221    fi;
222    if not(ForAll(v, IsInt)) then
223      Error("The first argument must be a list with two integers (a pair)");
224    fi;
225    sm := SmallElementsOfGoodIdeal(i);
226    m := MinIGS(i);
227    c := Conductor(i);
228    # see if we are in the box [0,c]
229    if (le(m,v) and le(v,c)) then
230      return v in sm;
231    fi;
232    # see if we are below right or left the minimum
233    if (v[1]<m[1]) or (v[2]<m[2]) then
234      return false;
235    fi;
236    # see if we are above the conductor
237    if (le(c,v)) then
238      return true;
239    fi;
240    # see if we are above the small elements
241    # at this point v>= m, and not greater than c and not in the box [0,c]
242    # see if we are at the left of the conductor
243    if v[1]<c[1] then
244      return [v[1],c[2]] in sm;
245    fi;
246  return [c[1],v[2]] in sm;
247end);
248
249###################################################
250##
251#M BelongsToGoodIdeal
252## decides if a vector is in the semigroup
253##################################################
254InstallMethod( \in,
255        "for good ideals",
256        [ IsHomogeneousList, IsGoodIdeal], 100,
257        function( v, i )
258    return BelongsToGoodIdeal(v,i);
259end);
260
261#############################################################################
262##
263#A  ConductorOfIdeal(I)
264##
265##  Returns the conductor of I, the largest element in SmallElements(I)
266##
267#############################################################################
268InstallMethod(Conductor,
269  "Returns the conductor of an ideal",
270  [IsGoodIdeal],
271  function(I)
272  local G,C,m;
273
274  return Conductor(I);
275
276end);
277
278#############################################################################
279##
280#F  CanonicalIdealOfGoodSemigroup(s)
281##
282##  Computes a canonical ideal of <s>
283##
284#############################################################################
285
286InstallGlobalFunction(CanonicalIdealOfGoodSemigroup,
287  function(G)
288  local s1,s2,sm, c, gamma, gen,x;
289
290  if not(IsGoodSemigroup(G)) then
291    Error("The argument must be a good semigroup");
292  fi;
293
294  c := Conductor(G);
295  gamma:= c-[1,1];
296  sm := SmallElementsOfGoodSemigroup(G);
297
298  s1:=Set(sm, x->x[1]);
299  s2:=Set(sm, x->x[2]);
300  gen:=[];
301  gen:=Concatenation(List(Difference([0..c[1]],s1), x1 -> [gamma[1]-x1,c[2]]),
302  List(Difference([0..c[2]],s2), x2 -> [c[1],gamma[2]-x2]));
303
304  for x in sm do
305    if (x[1]<c[1]) and (x[2]<c[2])
306      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
307      Add(gen,gamma-x);
308    fi;
309  od;
310
311  return GoodIdeal(Set(gen),G);
312end);
313