1#############################################################################
2##
3#W  frobenius-extra-4ti2gap.gi        Ignacio Ojeda <mdelgado@fc.up.pt>
4#W                                    Carlos Jesús Moreno Ávila <camorenoa@alumnos.unex.es>
5#W                                    Manuel Delgado <mdelgado@fc.up.pt>
6#W                                    Pedro Garcia-Sanchez <pedro@ugr.es>
7##
8#Y  Copyright 2015-- Universidad de Extremadura and Universidad de Granada, Spain
9#############################################################################
10
11#############################################################################
12##
13#F  FrobeniusNumber(s)
14##
15##  Computes the Frobenius Number of the numerical semigroup <s>.
16##
17##  The definition of Frobenius Number can be found in
18##  the book
19##   - Rosales, J. C.; García-Sánchez, P. A. Numerical semigroups.
20##     Developments in Mathematics, 20. Springer, New York, 2009.
21##  The main algorithm used appears in
22##   - Roune, B.H. The slice algorithm for irreducible decomposition of
23##     monomial ideals.J. Symbolic Comput. 44 (2009), no. 4, 358–381.
24##
25##   REQUERIMENTS: 4ti2Interface
26#############################################################################
27InstallMethod(FrobeniusNumber,
28    "method using 4ti2 for the calculaction of the Frobenius number",
29    [IsNumericalSemigroup],60,
30    function( S )
31    local v, n, M, msm, MonomialIdeal, MaximalStandardMonomials,  BelongsToMonomialIdeal, MinimalGeneratingSystemOfMonomialIdeal, QuotientOfMonomialIdealByMonomial;
32
33    Info(InfoNumSgps,2,"Using 4ti2gap for the calculation of the Frobenius number");
34    MonomialIdeal := function(v)
35        local n, I, M, E, upperbound, C, m, L, ap, i;
36        n := Length(v);
37        I := GroebnerBasis4ti2( [v], [v] );
38        I := I{[1 .. Length(I)]}{[2 .. n]};
39        M := [];
40        for i in I do
41    	     Add(M,List(i,x->Maximum(x,0)));
42        od;
43        return M;
44    end;
45
46    MinimalGeneratingSystemOfMonomialIdeal := function(M)
47        return Filtered(M, m->not(BelongsToMonomialIdeal(Difference(M,[m]),m)));
48    end;
49
50    BelongsToMonomialIdeal := function(M,m)
51        return ForAny(M, x->ForAll(m-x, y -> y>=0));
52    end;
53
54    QuotientOfMonomialIdealByMonomial := function(M,m)
55        local n,quotient,f,g;
56        n := Length(m);
57        quotient := [];
58        for f in M do
59            g := List(f-m, x->Maximum(x,0));
60            if IsZero(g) then
61                return [g];
62            fi;
63            Add(quotient,g);
64        od;
65        return quotient;
66    end;
67
68    MaximalStandardMonomials := function(M,S,p,i,msm)
69        local n, C, q, M1, S1,tr;
70
71        tr:=function(v)
72          return List(v-1, x->Maximum(x,0));
73        end;
74        n := Length(M[1]);
75        M := MinimalGeneratingSystemOfMonomialIdeal(M);
76        if ForAll(Sum(M), x->x=1) then
77            Add(msm,p);
78            return msm;
79        fi;
80        q:=First(M{[i..Length(M)]}, qq->not(IsZero(tr(qq)) or BelongsToMonomialIdeal(S,tr(qq))));
81        if q<>fail then
82          q:=tr(q);
83          M1 := QuotientOfMonomialIdealByMonomial(M,q);
84          S1 := QuotientOfMonomialIdealByMonomial(S,q);
85          msm := MaximalStandardMonomials(M1,MinimalGeneratingSystemOfMonomialIdeal(S1),p+q,1,msm);
86          Add(S,q);
87          i:=i+1;
88          msm := MaximalStandardMonomials(M,MinimalGeneratingSystemOfMonomialIdeal(S),p,i,msm);
89          return msm;
90        fi;
91        return msm;
92    end;
93
94    v := MinimalGeneratingSystemOfNumericalSemigroup(S);
95    n := Length(v);
96    M := MonomialIdeal(v);
97    msm := MaximalStandardMonomials(M,[],Zero([1 .. n-1]),1,[]);
98    return Maximum(msm*v{[2 .. Length(v)]})-v[1]; #return maximum S-degree - v_1
99end);
100
101#############################################################################
102##
103#F  AperyList(s)
104##
105##  Computes the Apery set of the numerical semigroup <s> with respect to
106##  the multiplicit of <s>
107##
108##  The definition of Apery set can be found in
109##  the book
110##   - Rosales, J. C.; García-Sánchez, P. A. Numerical semigroups.
111##     Developments in Mathematics, 20. Springer, New York, 2009.
112##  The main algorithm used appears in
113##   - Roune, B.H. The slice algorithm for irreducible decomposition of
114##     monomial ideals.J. Symbolic Comput. 44 (2009), no. 4, 358–381.
115##
116##   REQUERIMENTS: 4ti2Interface
117#############################################################################
118
119InstallMethod(AperyList,
120    "method using 4ti2 for the calculaction of the Apery set",
121    [IsNumericalSemigroup],60,
122    function( S )
123    local v, n, M, msm, c, L, MonomialIdeal, MaximalStandardMonomials, BelongsToMonomialIdeal, MinimalGeneratingSystemOfMonomialIdeal, QuotientOfMonomialIdealByMonomial, LatticePointsInBoxGivenByDiagonal;
124
125    Info(InfoNumSgps,2,"Using 4ti2gap for the calculation of the Apery set");
126
127    MonomialIdeal := function(v)
128        local n, I, M, E, upperbound, C, m, L, ap, i;
129        n := Length(v);
130        I := GroebnerBasis4ti2([v], [v] );
131        I := I{[1 .. Length(I)]}{[2 .. n]};
132        M := [];
133        for i in I do
134    	     Add(M,List(i,x->Maximum(x,0)));
135        od;
136        return M;
137    end;
138
139    MinimalGeneratingSystemOfMonomialIdeal := function(M)
140        return Filtered(M, m->not(BelongsToMonomialIdeal(Difference(M,[m]),m)));
141    end;
142
143    BelongsToMonomialIdeal := function(M,m)
144        return ForAny(M, x->ForAll(m-x, y -> y>=0));
145    end;
146
147    QuotientOfMonomialIdealByMonomial := function(M,m)
148        local n,quotient,f,g;
149        n := Length(m);
150        quotient := [];
151        for f in M do
152            g := List(f-m, x->Maximum(x,0));
153            if IsZero(g) then
154                return [g];
155            fi;
156            Add(quotient,g);
157        od;
158        return quotient;
159    end;
160
161    MaximalStandardMonomials := function(M,S,p,i,msm)
162        local n, C, q, M1, S1,tr;
163
164        tr:=function(v)
165          return List(v-1, x->Maximum(x,0));
166        end;
167        n := Length(M[1]);
168        M := MinimalGeneratingSystemOfMonomialIdeal(M);
169        if ForAll(Sum(M), x->x=1) then
170            Add(msm,p);
171            return msm;
172        fi;
173        q:=First(M{[i..Length(M)]}, qq->not(IsZero(tr(qq)) or BelongsToMonomialIdeal(S,tr(qq))));
174        if q<>fail then
175          q:=tr(q);
176          M1 := QuotientOfMonomialIdealByMonomial(M,q);
177          S1 := QuotientOfMonomialIdealByMonomial(S,q);
178          msm := MaximalStandardMonomials(M1,MinimalGeneratingSystemOfMonomialIdeal(S1),p+q,1,msm);
179          Add(S,q);
180          i:=i+1;
181          msm := MaximalStandardMonomials(M,MinimalGeneratingSystemOfMonomialIdeal(S),p,i,msm);
182          return msm;
183        fi;
184        return msm;
185    end;
186
187    LatticePointsInBoxGivenByDiagonal := function( lowerconer, uppercorner )
188        local V,i;
189        V := [];
190        for i in [1 .. Length(lowerconer)] do
191            Add(V,[lowerconer[i] .. uppercorner[i]]);
192        od;
193        return Cartesian(V);
194    end;
195
196    v := MinimalGeneratingSystemOfNumericalSemigroup(S);
197    n := Length(v);
198    M := MonomialIdeal(v);
199    msm := MaximalStandardMonomials(M,[],Zero([1 .. n-1]),1,[]);
200    L := [];
201    for c in msm do
202        L := Union(L,LatticePointsInBoxGivenByDiagonal(Zero([1 .. n-1]),c));
203    od;
204    L:= L*v{[2 .. Length(v)]};
205    return List([0..v[1]-1], i->First(L, y->(y-i) mod v[1]=0));
206end);
207