1#############################################################################
2##
3#W  ideals-def.gi           Manuel Delgado <mdelgado@fc.up.pt>
4#W                          Pedro Garcia-Sanchez <pedro@ugr.es>
5#W                          Jose Morais <josejoao@fc.up.pt>
6##
7##
8#Y  Copyright 2005 by Manuel Delgado,
9#Y  Pedro Garcia-Sanchez and Jose Joao Morais
10#Y  We adopt the copyright regulations of GAP as detailed in the
11#Y  copyright notice in the GAP manual.
12##
13#############################################################################
14
15
16#############################################################################
17#####################        Defining Ideals           ######################
18#############################################################################
19##
20#F IdealOfNumericalSemigroup(l,S)
21##
22## l is a list of integers and S a numerical semigroup
23##
24## returns the ideal of S generated by l.
25##
26#############################################################################
27InstallGlobalFunction(IdealOfNumericalSemigroup, function(l,S)
28  local  I;
29      if not (IsNumericalSemigroup(S) and IsListOfIntegersNS(l)) then
30        Error("The arguments of IdealOfNumericalSemigroup must be a numerical semigroup and a nonempty list of integers.");
31    fi;
32    I := rec();
33    ObjectifyWithAttributes(I, IdealsOfNumericalSemigroupsType,
34        UnderlyingNSIdeal, S,
35        Generators, Set(l)
36        );
37    return I;
38end );
39
40
41##############################################################################
42## L is a list of integers and S a numerical semigroup
43## L + S is an abbreviation for IdealOfNumericalSemigroup(L, S)
44##
45InstallOtherMethod( \+, "for a list and a numerical semigroup", true,
46        [IsList and IsAdditiveElement,
47         IsNumericalSemigroup], 0,
48        function( L,S )
49    return(IdealOfNumericalSemigroup(L, S));
50end);
51
52##############################################################################
53## n is an integer and S a numerical semigroup
54## n + S is an abbreviation for IdealOfNumericalSemigroup([n], S)
55##
56InstallOtherMethod( \+, "for an integer and a numerical semigroup", true,
57        [IsInt and IsAdditiveElement,
58         IsNumericalSemigroup], 0,
59        function( n,S )
60    return(IdealOfNumericalSemigroup([n], S));
61end);
62
63#############################################################################
64##
65#M  PrintObj(S)
66##
67##  This method for ideals of numerical semigroups.
68##
69#############################################################################
70
71InstallMethod( PrintObj,
72        "prints an Ideal of a Numerical Semigroup",
73        [ IsIdealOfNumericalSemigroup],
74        function( I )
75    Print(Generators(I)," + NumericalSemigroup( ", GeneratorsOfNumericalSemigroup(UnderlyingNSIdeal(I)), " )\n");
76end);
77
78#############################################################################
79##
80#M  ViewString(S)
81##
82##  This method for ideals of numerical semigroups.
83##
84#############################################################################
85
86InstallMethod( ViewString,
87        "prints an Ideal of a Numerical Semigroup",
88        [ IsIdealOfNumericalSemigroup],
89        function( I )
90    return ("Ideal of numerical semigroup");
91end);
92
93#############################################################################
94##
95#M  ViewObj(S)
96##
97##  This method for ideals of numerical semigroups.
98##
99#############################################################################
100
101InstallMethod( ViewObj,
102        "prints an Ideal of a Numerical Semigroup",
103        [ IsIdealOfNumericalSemigroup],
104        function( I )
105    Print("<Ideal of numerical semigroup>");
106end);
107
108#############################################################################
109##
110#M  DisplayObj(S)
111##
112##  This method for ideals of numerical semigroups.
113##
114#############################################################################
115InstallMethod( Display,
116        "displays an ideal of a numerical semigroup",
117    [IsIdealOfNumericalSemigroup],
118        function( I )
119    local   condensed,  L,  M,  u;
120
121    condensed := function(L)
122        local   C,  bool,  j,  c,  search;
123
124        C := [];
125        bool := true;
126        j := 0;
127        c := L[1];
128        search := function(n) # searches the greatest subinterval starting in n
129            local i, k;
130            k := 0;
131            for i in [Position(L,n).. Length(L)-1] do
132                if not (L[i]+1 = L[i+1]) then
133                    c := L[i+1];
134                    return [n..n+k];
135                fi;
136                k := k+1;
137            od;
138            bool := false;
139            return [n..L[Length(L)]];
140        end;
141        while bool do
142            Add(C,search(c));
143        od;
144        return C;
145    end;
146    ##  End of condensed()  --
147
148    L := SmallElementsOfIdealOfNumericalSemigroup(I);
149    M := condensed(L);
150    u := [M[Length(M)][1],"->"];
151    M[Length(M)] := u;
152    return M;
153end);
154
155
156############################################################################
157##
158#M Methods for the comparison of ideals of a numerical semigroup.
159##
160InstallMethod( \=,
161        "for two ideals of numerical semigroups",
162        [IsIdealOfNumericalSemigroup,
163         IsIdealOfNumericalSemigroup],
164        function(I, J )
165
166    if not AmbientNumericalSemigroupOfIdeal(I)
167       = AmbientNumericalSemigroupOfIdeal(J) then
168        #Error("The ambient numerical semigroup must be the same for both ideals.");
169        return false;
170    fi;
171    if HasMinimalGeneratingSystemOfIdealOfNumericalSemigroup(I) and HasMinimalGeneratingSystemOfIdealOfNumericalSemigroup(J) then
172        return MinimalGeneratingSystemOfIdealOfNumericalSemigroup(I)
173               = MinimalGeneratingSystemOfIdealOfNumericalSemigroup(J);
174    fi;
175    return SmallElementsOfIdealOfNumericalSemigroup(I)
176           = SmallElementsOfIdealOfNumericalSemigroup(J);
177end);
178
179InstallMethod( \<,
180        "for two ideals of a numerical semigroups",
181        [IsIdealOfNumericalSemigroup,IsIdealOfNumericalSemigroup],
182        function(I, J )
183    if not AmbientNumericalSemigroupOfIdeal(I)
184       = AmbientNumericalSemigroupOfIdeal(J) then
185        Error("The ambient numerical semigroup must be the same for both ideals.");
186    fi;
187    return(SmallElementsOfIdealOfNumericalSemigroup(I) < SmallElementsOfIdealOfNumericalSemigroup(J));
188end );
189
190
191#############################################################################
192##
193#A  Generators(I)
194#A  GeneratorsOfIdealOfNumericalSemigroup(I)
195##
196##  Returns a set of generators of the ideal I.
197##  If a minimal generating system has already been computed, this
198##  is the set returned.
199############################################################################
200InstallMethod(GeneratorsOfIdealOfNumericalSemigroup,
201        "Returns the minimal generating system of an ideal",
202        [IsIdealOfNumericalSemigroup],
203        function(I)
204    if HasMinimalGenerators(I) then
205       return (MinimalGenerators(I));
206    fi;
207    return(Generators(I));
208end);
209
210
211#############################################################################
212##
213#F  GeneratorsOfIdealOfNumericalSemigroupNC(I)
214##
215##  Returns a set of generators of the ideal I.
216############################################################################
217# InstallGlobalFunction(GeneratorsOfIdealOfNumericalSemigroupNC, function(I)
218#     if not IsIdealOfNumericalSemigroup(I) then
219#         Error("The argument must be an ideal of a numerical semigroup.");
220#     fi;
221#     return(GeneratorsIdealNS(I));
222# end);
223
224#############################################################################
225##
226#F AmbientNumericalSemigroupOfIdeal(I)
227##
228##  Returns the ambient semigroup of the ideal I.
229############################################################################
230InstallGlobalFunction(AmbientNumericalSemigroupOfIdeal, function(I)
231    if not IsIdealOfNumericalSemigroup(I) then
232        Error("The argument must be an ideal of a numerical semigroup.");
233    fi;
234    return(UnderlyingNSIdeal(I));
235end);
236
237#############################################################################
238##
239#P  IsIntegralIdealOfNumericalSemigroup(i)
240##
241##  Detects if the ideal i is contained in its ambient semigroup
242##
243#############################################################################
244InstallMethod(IsIntegralIdealOfNumericalSemigroup,
245  "Test it the ideal is integral", [IsIdealOfNumericalSemigroup],
246  function(I)
247     local s;
248
249     s:=AmbientNumericalSemigroupOfIdeal(I);
250
251     return IsSubset(s,MinimalGeneratingSystemOfIdealOfNumericalSemigroup(I));
252end);
253
254
255#############################################################################
256##
257#A SmallElementsOfIdealOfNumericalSemigroup
258##
259##  Returns the list of elements in the ideal I up to the last gap + 1.
260##
261#############################################################################
262InstallMethod(SmallElementsOfIdealOfNumericalSemigroup,
263        "Returns the list of elements in the ideal not greater that the last gap",
264        [IsIdealOfNumericalSemigroup ],
265        function(I)
266    local   smallS,  g,  gI,  l,  min,  l2,  maxgap;
267
268    # if not (IsIdealOfNumericalSemigroup(I)) then
269    #     Error("The argument must be an ideal of a numerical semigroup");
270    # fi;
271
272    smallS := SmallElementsOfNumericalSemigroup(AmbientNumericalSemigroupOfIdeal(I));
273    g := smallS[Length(smallS)]; #Frobenius number + 1
274    gI := GeneratorsOfIdealOfNumericalSemigroup(I);
275
276    l := Union(List(gI, i -> i+ smallS));
277
278    min := Minimum(gI);
279
280    l := Intersection(l,[min .. min+g]);
281
282    l2 := Difference([min..min+g],l);
283    if l2 = [] then
284        return([min]);
285    else
286        maxgap := Maximum(Difference(l2,l));
287        return(Intersection(l,[min..maxgap+1]));
288    fi;
289end);
290
291#############################################################################
292##
293#F  ConductorOfIdealOfNumericalSemigroup(I)
294##
295##  Returns the conductor of I, the largest element in SmallElements(I)
296##
297#############################################################################
298InstallMethod(Conductor,
299        "Returns the conductor of I, the largest element in SmallElements(I)",
300        [IsIdealOfNumericalSemigroup ],
301        function(I)
302     local seI;
303
304     # if not IsIdealOfNumericalSemigroup(I) then
305     #     Error("The argument must be an ideal of a numerical semigroup");
306     # fi;
307     seI:=SmallElementsOfIdealOfNumericalSemigroup(I);
308
309     return seI[Length(seI)];
310end);
311
312#############################################################################
313##
314#F  BelongsToIdealOfNumericalSemigroup(n,I)
315##
316##  Tests if the integer n belongs to the ideal I.
317##
318#############################################################################
319InstallGlobalFunction(BelongsToIdealOfNumericalSemigroup, function(x, I)
320    local gI, S, small;
321
322    if not (IsIdealOfNumericalSemigroup(I) and IsInt(x)) then
323        Error("The arguments must be an integer and an ideal of a numerical semigroup");
324    fi;
325    if HasSmallElementsOfIdealOfNumericalSemigroup(I) then
326        small := SmallElementsOfIdealOfNumericalSemigroup(I);
327        return( (x in small) or (x > Maximum(small)));
328    fi;
329
330    S := AmbientNumericalSemigroupOfIdeal(I);
331    gI := GeneratorsOfIdealOfNumericalSemigroup(I);
332
333    return(First(gI, n -> (BelongsToNumericalSemigroup(x-n,S))) <> fail);
334end);
335###########################################################
336## n in I means BelongsToIdealOfNumericalSemigroup(n,I)
337##########
338InstallMethod( \in,
339        "for ideals of numerical semigroups",
340        [ IsInt, IsIdealOfNumericalSemigroup ],
341        function( x, I )
342    return BelongsToIdealOfNumericalSemigroup(x,I);
343end);
344
345#############################################################################
346##
347#A MinimalGenerators(I)
348#A MinimalGeneratingSystem(I)
349#A MinimalGeneratingSystemOfIdealOfNumericalSemigroup(I)
350##
351## The argument I is an ideal of a numerical semigroup
352## returns the minimal generating system of I.
353##
354#############################################################################
355InstallMethod(MinimalGeneratingSystemOfIdealOfNumericalSemigroup,
356        "Returns the minimal generating system of an ideal",
357        [IsIdealOfNumericalSemigroup],
358        function(I)
359  local  S, m, mingens;
360
361    S := AmbientNumericalSemigroupOfIdeal(I);
362    m := MaximalIdealOfNumericalSemigroup(S);
363    mingens := DifferenceOfIdealsOfNumericalSemigroup(I,m+I);
364#    Setter(Generators)(I,mingens); #does not work
365    return mingens;
366  end);
367
368#############################################################################
369##
370#F SumIdealsOfNumericalSemigroup(I,J)
371##
372## returns the sum of the ideals I and J (in the same ambient semigroup)
373#############################################################################
374InstallGlobalFunction(SumIdealsOfNumericalSemigroup, function(I, J)
375    local   l1,  l2,  l;
376
377    if not (IsIdealOfNumericalSemigroup(I) and IsIdealOfNumericalSemigroup(J))
378       or not AmbientNumericalSemigroupOfIdeal(I)
379       = AmbientNumericalSemigroupOfIdeal(J) then
380        Error("The arguments must be ideals of the same numerical semigroup.");
381    fi;
382
383    l1:=GeneratorsOfIdealOfNumericalSemigroup(I);
384    l2:=GeneratorsOfIdealOfNumericalSemigroup(J);
385    l := Set(Cartesian(l1,l2),n -> Sum(n));
386    return(IdealOfNumericalSemigroup(l,AmbientNumericalSemigroupOfIdeal(I)));
387end);
388
389###########################################################
390## I + J means SumIdealsOfNumericalSemigroup(I,J)
391##########
392
393InstallOtherMethod( \+, "for ideals of the same numerical semigroup", true,
394        [IsIdealOfNumericalSemigroup,
395         IsIdealOfNumericalSemigroup], 0,
396        function( I, J )
397    return(SumIdealsOfNumericalSemigroup( I, J ));
398end);
399
400#############################################################################
401##
402#F SubtractIdealsOfNumericalSemigroup(I,J)
403##
404## returns the ideal I - J
405#############################################################################
406InstallGlobalFunction(SubtractIdealsOfNumericalSemigroup, function(I, J)
407    local   s,  g,  mult,  gI,  gJ,  i,  j,  l,  l2,  maxgap,  maxl,  mingen,
408            ideal;
409
410    if not (IsIdealOfNumericalSemigroup(I) and IsIdealOfNumericalSemigroup(J))
411       or not AmbientNumericalSemigroupOfIdeal(I)
412       = AmbientNumericalSemigroupOfIdeal(J) then
413        Error("The arguments must be ideals of the same numerical semigroup.");
414    fi;
415    s := AmbientNumericalSemigroupOfIdeal(I);
416    g := FrobeniusNumberOfNumericalSemigroup(s);
417    mult:= MultiplicityOfNumericalSemigroup(s);
418
419    gI := GeneratorsOfIdealOfNumericalSemigroup(I);
420    gJ := GeneratorsOfIdealOfNumericalSemigroup(J);
421
422    i := Minimum(gI);
423    j := Minimum(gJ);
424
425    l := Filtered([i-j..i-j+g+1], n -> ForAll(gJ, z-> BelongsToIdealOfNumericalSemigroup(z+n,I)));
426
427
428
429    l2 := Difference([i-j..i-j+g+1],l);
430    if l2 = [] then
431        maxgap := i-j-1;
432    else
433        maxgap := Maximum(Difference(l2,l));
434    fi;
435
436    l := Intersection(l,[i-j..maxgap+1]);
437    maxl:= Maximum(l);
438
439    mingen := MinimalGeneratingSystemOfIdealOfNumericalSemigroup(
440        Concatenation(l,[maxl+1..maxl+mult+1])+s);
441
442    ideal := mingen + s;
443
444    Setter(SmallElementsOfIdealOfNumericalSemigroup)(ideal,l);
445
446    Setter(MinimalGeneratingSystemOfIdealOfNumericalSemigroup)(ideal,mingen);
447
448    return ideal;
449end);
450
451###########################################################
452## I - J means SubtractIdealsOfNumericalSemigroup(I,J)
453## I can be the ambient numerical semigroup of J
454##########
455
456InstallOtherMethod( \-, "for ideals of the same numerical semigroup", true,
457        [IsIdealOfNumericalSemigroup,
458         IsIdealOfNumericalSemigroup], 0,
459        function( I, J )
460    return(SubtractIdealsOfNumericalSemigroup( I, J ));
461end);
462
463InstallOtherMethod( \-, "for a numerical semigroup and one of its ideals", true,
464        [IsNumericalSemigroup,
465         IsIdealOfNumericalSemigroup], 0,
466        function( S, J )
467    return(SubtractIdealsOfNumericalSemigroup( 0+S, J ));
468end);
469
470
471#############################################################################
472##
473#F DifferenceOfdealsOfNumericalSemigroup(I,J)
474##
475## returns the set difference I\J #(J must be contained in I)-no more required, from version 1.1 on
476#############################################################################
477InstallOtherMethod(Difference, [IsIdealOfNumericalSemigroup, IsIdealOfNumericalSemigroup], function(I, J)
478  return DifferenceOfIdealsOfNumericalSemigroup(I,J);
479end);
480
481InstallGlobalFunction(DifferenceOfIdealsOfNumericalSemigroup, function(I, J)
482    local   sI,  sJ,  MI,  MJ,  M,  SI,  SJ;
483
484    if not (IsIdealOfNumericalSemigroup(I) and IsIdealOfNumericalSemigroup(J))
485#       or not AmbientNumericalSemigroupOfIdeal(I) = AmbientNumericalSemigroupOfIdeal(J)
486       then
487#        Error("The arguments must be ideals of the same numerical semigroup.");
488        Error("The arguments must be ideals of some numerical semigroup.");
489    fi;
490    sI := SmallElementsOfIdealOfNumericalSemigroup(I);
491    sJ := SmallElementsOfIdealOfNumericalSemigroup(J);
492    MI := Maximum(sI);
493    MJ := Maximum(sJ);
494    M := Maximum(MI,MJ);
495    SI := Union(sI,[MI..M]);
496    SJ := Union(sJ,[MJ..M]);
497    # if not IsSubset(SI,SJ) then
498    #     Error("The second ideal must be contained in the first");
499    # fi;
500    return Difference(SI,SJ);
501end);
502
503#############################################################################
504##
505#F MultipleOfIdealOfNumericalSemigroup(n,I)
506##
507## n is a non negative integer and I is an ideal
508## returns the multiple nI (I+...+I n times) of I
509#############################################################################
510InstallGlobalFunction(MultipleOfIdealOfNumericalSemigroup, function(n,I)
511    local i, II;
512     if not (IsInt(n) and n >=0 and IsIdealOfNumericalSemigroup(I)) then
513         Error("The arguments must be a non negative integer and an ideal.");
514     fi;
515     if n=0 then
516         return [0]+AmbientNumericalSemigroupOfIdeal(I);
517     elif n=1 then
518         return I;
519     fi;
520     II:=I;
521     for i in [1..n-1] do
522         II := II+I;
523     od;
524     return II;
525end);
526###########################################################
527## n is an integer and S a numerical semigroup
528## n * I is an abbreviation for MultipleOfIdealOfNumericalSemigroup(n,I)
529##########
530InstallOtherMethod( \*, "for a non negative integer and an ideal of a numerical semigroup", true,
531        [IsInt and IsMultiplicativeElement,
532         IsIdealOfNumericalSemigroup], 999999990,
533        function( n,I )
534    return(MultipleOfIdealOfNumericalSemigroup(n, I));
535end);
536
537
538#############################################################################
539##
540#F HilbertFunctionOfIdealOfNumericalSemigroup(n,I)
541##
542## returns the value of the Hilbert function associated to I in n,
543## that is, nI\(n+1)I. I must be an ideal included in its ambient semigroup.
544#############################################################################
545InstallGlobalFunction(HilbertFunctionOfIdealOfNumericalSemigroup, function(n,I)
546    if not (IsInt(n) and n >=0 and IsIdealOfNumericalSemigroup(I)) then
547        Error("The arguments must be a non negative integer and an ideal.");
548    fi;
549    return Length(DifferenceOfIdealsOfNumericalSemigroup(n*I,(n+1)*I));
550end);
551
552InstallMethod(HilbertFunction,
553    "gives the Hilbert function of the ideal",
554    [IsIdealOfNumericalSemigroup],
555    function(I)
556        return n->HilbertFunctionOfIdealOfNumericalSemigroup(n,I);
557    end);
558
559#############################################################################
560##
561#P IsMonomialNumericalSemigroup
562## Tests if a numerical semigroup is a monomial semigroup ring
563##
564#############################################################################
565InstallMethod(IsMonomialNumericalSemigroup,
566  "Detects if the semigroup ring of the semigroup is monomial",[IsNumericalSemigroup],
567  function(s)
568    local l,c,gen,gaps;
569
570    gen:=MinimalGeneratingSystemOfNumericalSemigroup(s);
571    gaps:=GapsOfNumericalSemigroup(s);
572    l:=List(gen,g->Filtered(gaps-g,x->x>0));
573    c:=Filtered(Cartesian([1..Length(l)],[1..Length(l)]),x->x[1]<x[2]);
574    return First(c,x->Intersection(l[x[1]],l[x[2]])<>[])=fail;
575end);
576
577
578#############################################################################
579##
580#F BlowUpIdealOfNumericalSemigroup(I)
581##
582##
583#############################################################################
584InstallGlobalFunction(BlowUpIdealOfNumericalSemigroup, function(I)
585    local r;
586    if not IsIdealOfNumericalSemigroup(I) then
587        Error("The argument must be an ideal.");
588    fi;
589
590    r:=ReductionNumberIdealNumericalSemigroup(I);
591
592    return r*I-r*I;
593end);
594
595InstallMethod(BlowUp,
596    "blow up of a numerical semigroup",
597    [IsIdealOfNumericalSemigroup],
598    BlowUpIdealOfNumericalSemigroup);
599
600#############################################################################
601##
602#F  MaximalIdealOfNumericalSemigroup(S)
603##
604##  Returns the maximal ideal of S.
605##
606#############################################################################
607InstallGlobalFunction(MaximalIdealOfNumericalSemigroup, function(S)
608    if not IsNumericalSemigroup(S) then
609        Error("The argument must be a numerical semigroup.");
610    fi;
611    return MinimalGeneratingSystemOfNumericalSemigroup(S)+S;
612end);
613
614InstallMethod(MaximalIdeal,
615    "of a numerical semigroup",
616    [IsNumericalSemigroup],
617    MaximalIdealOfNumericalSemigroup);
618
619
620#############################################################################
621##
622#F  BlowUpOfNumericalSemigroup(s)
623##
624##  Computes the Blow Up (of the maximal ideal) of
625##  the numerical semigroup <s>.
626##
627#############################################################################
628InstallGlobalFunction(BlowUpOfNumericalSemigroup, function(s)
629    local gen, genbu, m;
630
631    if not IsNumericalSemigroup(s) then
632        Error("The argument must be a numerical semigroup.");
633    fi;
634
635
636    gen:=MinimalGeneratingSystemOfNumericalSemigroup(s);
637    m:=MultiplicityOfNumericalSemigroup(s);
638    genbu:=gen-m;
639    genbu:=genbu+[m];
640
641    return NumericalSemigroup(genbu);
642end);
643
644InstallMethod(BlowUp,
645    "Blow up of the numerical semigroup",
646    [IsNumericalSemigroup],
647    BlowUpOfNumericalSemigroup);
648
649#############################################################################
650##
651#F MultiplicitySequenceOfNumericalSemigroup(s)
652##
653##  Computes the multiplicity sequence of the numerical semigroup <s>.
654##
655#############################################################################
656InstallGlobalFunction(MultiplicitySequenceOfNumericalSemigroup, function(s)
657      local msg, m;
658
659    if not(IsNumericalSemigroup(s)) then
660      Error("The argument must be a numerical semigroup");
661    fi;
662
663    if (1 in s) then
664      return [1];
665    fi;
666
667    msg:=MinimalGenerators(s);
668    m:=MultiplicityOfNumericalSemigroup(s);
669    msg:=Union(Difference(msg-m,[0]),[m]);
670    return Concatenation([m],MultiplicitySequenceOfNumericalSemigroup(NumericalSemigroup(msg)));
671end);
672
673InstallMethod(MultiplicitySequence,
674    "of a numerical semigroup",
675    [IsNumericalSemigroup],
676    MultiplicitySequenceOfNumericalSemigroup);
677
678#############################################################################
679##
680#F  MicroInvariantsOfNumericalSemigroup(s)
681##
682##  Computes the microinvariants of the numerical semigroup <s>
683##  using the formula given by Valentina and Ralf [BF06]. The
684##  microinvariants of a numerial semigroup where introduced
685##  by J. Elias in [E01].
686##
687#############################################################################
688InstallGlobalFunction(MicroInvariantsOfNumericalSemigroup, function(s)
689    local e,m;
690
691    if not IsNumericalSemigroup(s) then
692        Error("The argument must be a numerical semigroup.");
693    fi;
694
695    m:=MaximalIdealOfNumericalSemigroup(s);
696    e:=MultiplicityOfNumericalSemigroup(s);
697    return (-AperyListOfNumericalSemigroupWRTElement(BlowUpOfNumericalSemigroup(s),e)
698            +AperyListOfNumericalSemigroupWRTElement(s,e))/e;
699
700end);
701InstallMethod(MicroInvariants,
702    "of a numerical semigroup",
703    [IsNumericalSemigroup],
704    MicroInvariantsOfNumericalSemigroup);
705
706#############################################################################
707##
708#P  IsGradedAssociatedRingNumericalSemigroupCM(s)
709##
710##  Returns true if the associated graded ring of
711##  the semigroup ring algebra k[[s]] is Cohen-Macaulay.
712##  This function implements the algorithm given in [BF06].
713##
714#############################################################################
715InstallMethod(IsGradedAssociatedRingNumericalSemigroupCM,
716  "Tests for Cohen-Macaulayness of graded ring associated to the numerical semigroup",
717  [IsNumericalSemigroup],
718  function(s)
719    local ai,bi,e,m;
720
721    if not IsNumericalSemigroup(s) then
722        Error("The argument must be a numerical semigroup.");
723    fi;
724
725
726    m:=MaximalIdealOfNumericalSemigroup(s);
727    e:=MultiplicityOfNumericalSemigroup(s);
728    ai:=MicroInvariantsOfNumericalSemigroup(s);
729    bi:=List(AperyListOfNumericalSemigroupWRTElement(s,e),
730        w->MaximumDegreeOfElementWRTNumericalSemigroup(w,s));
731    return ai=bi;
732end);
733
734
735#############################################################################
736##
737#F  CanonicalIdealOfNumericalSemigroup(s)
738##
739##  Computes a canonical ideal of <s> ([B06]):
740##      { x in Z | g-x not in S}
741##
742#############################################################################
743InstallGlobalFunction(CanonicalIdealOfNumericalSemigroup, function(s)
744
745    if not IsNumericalSemigroup(s) then
746        Error("The argument must be a numerical semigroup.");
747    fi;
748
749    return IdealOfNumericalSemigroup(FrobeniusNumberOfNumericalSemigroup(s)-
750            PseudoFrobeniusOfNumericalSemigroup(s),s);
751end);
752
753InstallMethod(CanonicalIdeal,
754    "of a numerical semigroup",
755    [IsNumericalSemigroup],
756    CanonicalIdealOfNumericalSemigroup);
757
758#############################################################################
759##
760#P  IsCanonicalIdealOfNumericalSemigroup(e)
761##
762##  Detects if the ideal e is a translation of the canonical ideal of its
763##  ambient semigroup
764##
765#############################################################################
766InstallMethod(IsCanonicalIdealOfNumericalSemigroup,
767  "Detects if the ideal is canonical", [IsIdealOfNumericalSemigroup],
768  function(i)
769
770  local c, mc, me;
771
772  if not(IsIdealOfNumericalSemigroup(i)) then
773    Error("The argument must be an ideal of a numerical semigroup");
774  fi;
775
776  c:=CanonicalIdealOfNumericalSemigroup(AmbientNumericalSemigroupOfIdeal(i));
777  if c=i then
778    return true;
779  fi;
780
781  mc:=Minimum(Generators(c));
782  me:=Minimum(Generators(i));
783
784  return i=(me-mc)+c;
785end);
786
787
788#############################################################################
789##
790#F  ReductionNumberIdealNumericalSemigroup(I)
791##
792##  Returns the least nonnegative integer such that
793##  nI-nI=(n+1)I-(n+1)I, see [B06].
794##
795#############################################################################
796InstallMethod(ReductionNumber,
797"Computes the reduction number of the ideal",
798[IsIdealOfNumericalSemigroup],
799function(I)
800
801    local n, S, i;
802
803    i:=Minimum(SmallElementsOfIdealOfNumericalSemigroup(I));
804    n := 1;
805    S:=AmbientNumericalSemigroupOfIdeal(I);
806    while (n+1)*I <> (i+MinimalGeneratingSystemOfIdealOfNumericalSemigroup(n*I))+S do
807        n := n+1;
808    od;
809    return n;
810
811end);
812
813
814#############################################################################
815##
816#F  RatliffRushClosureOfIdealOfNumericalSemigroup(I)
817##
818##  Returns the the union of all (n+1)I-nI with n nonnegative integers
819##
820#############################################################################
821InstallGlobalFunction(RatliffRushClosureOfIdealOfNumericalSemigroup,
822function(I)
823
824  local r,S;
825
826  if not IsIdealOfNumericalSemigroup(I) then
827      Error("The argument must be an ideal.");
828  fi;
829
830  r:=ReductionNumberIdealNumericalSemigroup(I);
831  return (r+1)*I-r*I;
832end);
833
834InstallMethod(RatliffRushClosure,
835    "Ratliff-Rush closure of an ideal of a numerical semigroup",
836    [IsIdealOfNumericalSemigroup],
837    RatliffRushClosureOfIdealOfNumericalSemigroup);
838
839
840#############################################################################
841##
842#F  RatliffRushNumberOfIdealOfNumericalSemigroup(I)
843##
844##  Returns the least nonnegative integer such that
845##  (n+1)I-nI is the Ratliff-Rush closure of I, see [DA-G-H].
846##
847#############################################################################
848InstallGlobalFunction(RatliffRushNumberOfIdealOfNumericalSemigroup,
849function(I)
850
851  local n, J, Jn, rrc;
852
853  if not IsIdealOfNumericalSemigroup(I) then
854      Error("The argument must be an ideal.");
855  fi;
856
857  rrc:=RatliffRushClosureOfIdealOfNumericalSemigroup(I);
858  J:=I-0*I;
859  n:=0;
860  while rrc<>(n+1)*I-n*I do
861    n:=n+1;
862  od;
863
864  return n;
865end);
866
867InstallMethod(RatliffRushNumber,
868    "Ratliff-Rush number of ideal of a numerical semigroup",
869    [IsIdealOfNumericalSemigroup],
870    RatliffRushNumberOfIdealOfNumericalSemigroup);
871
872#############################################################################
873##
874#F  AsymptoticRatliffRushNumberOfIdealOfNumericalSemigroup(I)
875##
876##  Returns the least nonnegative integer n such that
877##  mI equals the Ratliff-Rush closure of mI for all m>=n,  see [DA-G-H].
878##
879#############################################################################
880InstallGlobalFunction(AsymptoticRatliffRushNumberOfIdealOfNumericalSemigroup,
881function(I)
882
883  local r, nI, n;
884
885  if not IsIdealOfNumericalSemigroup(I) then
886      Error("The argument must be an ideal.");
887  fi;
888
889  r:=ReductionNumberIdealNumericalSemigroup(I);
890  n:=r;
891  while n>0 do
892    nI:=n*I;
893    if nI<>RatliffRushClosureOfIdealOfNumericalSemigroup(nI) then
894      return n+1;
895    fi;
896    n:=n-1;
897  od;
898end);
899
900InstallMethod(AsymptoticRatliffRushNumber,
901    "Asymptotic Ratliff-Rush number of ideal of a numerical semigroup",
902    [IsIdealOfNumericalSemigroup],
903    AsymptoticRatliffRushNumberOfIdealOfNumericalSemigroup);
904
905#############################################################################
906##
907#F  TranslationOfIdealOfNumericalSemigroup(k,I)
908##
909##  Given an ideal <I> of a numerical semigroup S and an integer <k>
910##  returns an ideal of the numerical semigroup S generated by
911##  {i1+k,...,in+k} where {i1,...,in} is the system of generators of <I>.
912##
913#############################################################################
914InstallGlobalFunction(TranslationOfIdealOfNumericalSemigroup, function(k,I)
915    local l;
916    if not IsInt(k) then
917        Error("<k> must be an integer");
918    fi;
919    if not IsIdealOfNumericalSemigroup(I) then
920        Error("<I> must be an ideal of a numerical semigroup");
921    fi;
922    l := List(GeneratorsOfIdealOfNumericalSemigroup(I), g -> g+k);
923    return IdealOfNumericalSemigroup(l, AmbientNumericalSemigroupOfIdeal(I));
924end);
925
926
927
928##############################################################################
929##
930##  <k> is an integer and <I> an ideal of a numerical semigroup.
931##  k + I is an abbreviation for TranslationOfIdealOfNumericalSemigroup(k, I)
932##
933InstallOtherMethod( \+, "for an integer and an ideal of a numerical semigroup", true,
934        [IsInt and IsAdditiveElement,
935         IsIdealOfNumericalSemigroup], 0,
936        function(k,I)
937    return(TranslationOfIdealOfNumericalSemigroup(k, I));
938end);
939
940
941
942#############################################################################
943##
944#F  IntersectionIdealsOfNumericalSemigroup(I,J)
945##
946##  Given two ideals <I> and <J> of a numerical semigroup S
947##  returns the ideal of the numerical semigroup S which is the
948##  intersection of the ideals <I> and <J>.
949##
950#############################################################################
951InstallOtherMethod(Intersection2, [IsIdealOfNumericalSemigroup, IsIdealOfNumericalSemigroup], function(I,J)
952  return IntersectionIdealsOfNumericalSemigroup(I,J);
953end);
954
955InstallGlobalFunction(IntersectionIdealsOfNumericalSemigroup, function(I, J)
956    local l,i,j,max,mult,l1,l2;
957
958    if not (IsIdealOfNumericalSemigroup(I) and IsIdealOfNumericalSemigroup(J))
959       or not AmbientNumericalSemigroupOfIdeal(I)
960       = AmbientNumericalSemigroupOfIdeal(J) then
961        Error("The arguments must be ideals of the same numerical semigroup.");
962    fi;
963
964    mult:=MultiplicityOfNumericalSemigroup(AmbientNumericalSemigroupOfIdeal(I));
965
966    l1:=SmallElementsOfIdealOfNumericalSemigroup(I);
967    l2:=SmallElementsOfIdealOfNumericalSemigroup(J);
968    i:=Maximum(l1);
969    j:=Maximum(l2);
970    max:=Maximum(i,j);
971    l1:=Concatenation(l1,[(i+1)..max]);
972    l2:=Concatenation(l2,[(j+1)..max]);
973    l := Concatenation(Intersection(l1,l2),[(max+1)..(max+mult)]);
974
975    return(IdealOfNumericalSemigroup(l,AmbientNumericalSemigroupOfIdeal(I)));
976
977end);
978
979#############################################################################
980##
981#O  Union(I,J)
982##
983##  Given two ideals <I> and <J> of a numerical semigroup S
984##  returns their union
985##
986#############################################################################
987InstallOtherMethod(Union2, [IsIdealOfNumericalSemigroup, IsIdealOfNumericalSemigroup],
988function(I,J)
989  if not(AmbientNumericalSemigroupOfIdeal(I)=AmbientNumericalSemigroupOfIdeal(J)) then
990    Error("Both ideals must be ideals of the same semigroup");
991  fi;
992  return Union(MinimalGenerators(I),MinimalGenerators(J))+AmbientNumericalSemigroupOfIdeal(I);
993end);
994
995
996########################################################################
997##
998#F AperyListOfIdealOfNumericalSemigroupWRTElement(I,n)
999##
1000##  Computes the sets of elements x of I such that x-n not in I,
1001##  where n is supposed to be in the ambient semigroup of I.
1002##  The element in the i-th position of the output list (starting in 0)
1003##  is congruent with i modulo n
1004########################################################################
1005InstallGlobalFunction(AperyListOfIdealOfNumericalSemigroupWRTElement,function(ideal,n)
1006	local msg, apambient, s, ap, cand, i;
1007
1008	s:=AmbientNumericalSemigroupOfIdeal(ideal);
1009	apambient:=AperyListOfNumericalSemigroupWRTElement(s,n);
1010	msg:=MinimalGeneratingSystemOfIdealOfNumericalSemigroup(ideal);
1011	ap:=ShallowCopy(apambient);
1012
1013	cand:=Set(Cartesian(msg,apambient), p->p[1]+p[2]);
1014
1015	for i in [0..n-1] do
1016		ap[i+1]:=Minimum(Filtered(cand, w-> w mod n=i));
1017	od;
1018	return ap;
1019end);
1020
1021InstallOtherMethod(AperyList,
1022    "for ideals and an element in the ambient semigroup",
1023    [IsIdealOfNumericalSemigroup,IsInt],
1024    AperyListOfIdealOfNumericalSemigroupWRTElement);
1025
1026########################################################################
1027##
1028#F AperyTableOfNumericalSemigroup(S)
1029##
1030##  Computes the Apéry table associated to S as
1031## explained in [CJZ],
1032##  that is, a list containing the Apéry list of S with respect to
1033## its multiplicity and the Apéry lists of kM (with M the maximal
1034##  ideal of S) with respect to the multiplicity of S, for k=1..r,
1035##  where r is the reduction number of M
1036##  (see ReductionNumberIdealNumericalSemigroup).
1037########################################################################
1038InstallGlobalFunction(AperyTableOfNumericalSemigroup,function(S)
1039	local M,m, table, k, r;
1040
1041	M:=MaximalIdealOfNumericalSemigroup(S);
1042	m:=MultiplicityOfNumericalSemigroup(S);
1043	table:=[AperyListOfNumericalSemigroupWRTElement(S,m)];
1044	r:=ReductionNumberIdealNumericalSemigroup(M);
1045	for k in [1..r] do
1046		Append(table,[AperyListOfIdealOfNumericalSemigroupWRTElement(k*M,m)]);
1047	od;
1048	return table;
1049end);
1050
1051InstallMethod(AperyTable,
1052    "for numerical semigroups",
1053    [IsNumericalSemigroup],
1054    AperyTableOfNumericalSemigroup);
1055
1056########################################################################
1057##
1058#F StarClosureOfIdealOfNumericalSemigroup(i,is)
1059##  i is an ideal and is is a set of ideals (all from the same
1060##	numerical semigroup). The output is i^{*_is}, where
1061## *_is is the star operation generated by is
1062## The implementation uses Section 3 of
1063##  -D. Spirito, Star Operations on Numerical Semigroups
1064########################################################################
1065
1066InstallGlobalFunction(StarClosureOfIdealOfNumericalSemigroup, function(i,is)
1067	local j, s, k;
1068
1069	s:=AmbientNumericalSemigroupOfIdeal(i);
1070	j:=s-(s-i); # i^v
1071
1072	for k in is do
1073		j:=IntersectionIdealsOfNumericalSemigroup(j,k-(k-i));
1074	od;
1075
1076	return j;
1077
1078end);
1079
1080########################################################################
1081## The minimum of an ideal
1082##
1083
1084InstallOtherMethod( MinimumList,
1085"minimum of an ideal",
1086[IsIdealOfNumericalSemigroup],
1087function( I )
1088  if HasSmallElements(I) then
1089    return Minimum(SmallElements(I));
1090  fi;
1091  return Minimum(Generators(I));
1092end);
1093
1094
1095##################################################################################
1096##
1097#O Iterator(I)
1098## Iterator for ideals of numerical semigroups
1099##################################################################################
1100InstallMethod(Iterator,
1101    "Iterator for numerical semigroups",
1102    [IsIdealOfNumericalSemigroup],
1103    function(ideal)
1104    local iter;
1105
1106    iter:=IteratorByFunctions(rec(
1107        pos := -1,
1108        i := ideal,
1109        IsDoneIterator := ReturnFalse,
1110        NextIterator := function(iter)
1111                            local n, m;
1112                            m:=Multiplicity(AmbientNumericalSemigroupOfIdeal(iter!.i));
1113                            n:=First([iter!.pos+1..iter!.pos+m+1],
1114                            x->x in iter!.i);
1115                            iter!.pos:=n;
1116                            return n;
1117                        end,
1118        ShallowCopy := iter -> rec( i := iter!.i,  pos := iter!.pos )
1119        ));
1120    return iter;
1121    end
1122);
1123
1124
1125#############################################################################
1126##
1127#F ElementNumber_IdealOfNumericalSemigroup(I,n)
1128# Given an ideal I of a numerical semigroup and an integer n, returns
1129# the nth element of I
1130#############################################################################
1131InstallGlobalFunction(ElementNumber_IdealOfNumericalSemigroup,
1132        function(I,r)
1133    local   selts,  n;
1134    if r<=0 then
1135        Error("The index must be a positive integer");
1136    fi;
1137    if not(IsIdealOfNumericalSemigroup(I)) then
1138        Error("The first argument must be an ideal of a numerical semigroup");
1139    fi;
1140    selts := SmallElementsOfIdealOfNumericalSemigroup( I );
1141    n := Length(selts);
1142    if r <= Length(selts) then
1143        return selts[r];
1144    else
1145        return selts[n] + r - n;
1146    fi;
1147end);
1148
1149
1150#############################################################################
1151##
1152#F NumberElement_IdealOfNumericalSemigroup(S,n)
1153# Given an ideal of a numerical semigroup I and an integer n, returns the
1154# position of n in I
1155#############################################################################
1156InstallGlobalFunction(NumberElement_IdealOfNumericalSemigroup,
1157    function(i,n)
1158        local c, nse;
1159        if not(n in i) then
1160            return(fail);
1161        fi;
1162        c:=Conductor(i);
1163        if n<=c then
1164            return Position(SmallElements(i),n);
1165        fi;
1166        nse:=Length(SmallElements(i));
1167        return nse+n-c;
1168    end
1169);
1170
1171##################################################################################
1172##
1173#O I[n]
1174## The nth element of I
1175##################################################################################
1176
1177InstallOtherMethod(\[\], [IsIdealOfNumericalSemigroup,IsInt],
1178    function(i,n)
1179        return ElementNumber_IdealOfNumericalSemigroup(i,n);
1180    end
1181);
1182
1183##################################################################################
1184##
1185#O I{ls}
1186## [I[n] :  n in ls]
1187##################################################################################
1188
1189
1190InstallOtherMethod(\{\}, [IsIdealOfNumericalSemigroup,IsList],
1191    function(i,l)
1192        return List(l,n->i[n]);
1193    end
1194);
1195