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