GAP 4.8.9 installation with standard packages -- copy to your CoCalc project to get it

1
  
2
  2 Numerical Semigroups
3
  
4
  This chapter describes how to create numerical semigroups in GAP and perform
5
  some basic tests.
6
  
7
  
8
  2.1 Generating Numerical Semigroups
9
  
10
  We recall some definitions from Chapter 1.
11
  
12
  A  numerical semigroup is a subset of the set N of nonnegative integers that
13
  is closed under addition, contains 0 and whose complement in N is finite.
14
  
15
  We  refer  to  the  elements  in a numerical semigroup that are less than or
16
  equal to the conductor as small elements of the semigroup.
17
  
18
  A  gap  of a numerical semigroup S is a nonnegative integer not belonging to
19
  S. The fundamental gaps of S are those gaps that are maximal with respect to
20
  the partial order induced by division in N.
21
  
22
  Given  a  numerical  semigroup  S  and  a  nonzero  element s in it, one can
23
  consider  for every integer i ranging from 0 to s-1, the smallest element in
24
  S  congruent  with  i  modulo  s,  say  w(i)  (this element exists since the
25
  complement  of  S  in  N  is  finite).  Clearly  w(0)=0.  The  set Ap(S,s)={
26
  w(0),w(1),..., w(s-1)} is called the Apéry set of S with respect to s.
27
  
28
  Let  a,b,c,d  be positive integers such that a/b < c/d, and let I=[a/b,c/d].
29
  Then  the  set  S(I)=  N∩ ⋃_n≥ 0 n I is a numerical semigroup. This class of
30
  numerical  semigroups  coincides with that of sets of solutions to equations
31
  of  the  form  A  x  mod  B  ≤ C x with A,B,C positive integers. A numerical
32
  semigroup in this class is said to be proportionally modular. If C = 1, then
33
  it is said to be modular.
34
  
35
  There  are different ways to specify a numerical semigroup S, namely, by its
36
  generators;  by  its gaps, its fundamental or special gaps by its Apéry set,
37
  just to name some. In this section we describe functions that may be used to
38
  specify, in one of these ways, a numerical semigroup in GAP.
39
  
40
  2.1-1 NumericalSemigroupByGenerators
41
  
42
  NumericalSemigroupByGenerators( List )  function
43
  NumericalSemigroup( String, List )  function
44
  
45
  List is a list of nonnegative integers with greatest common divisor equal to
46
  one.  These  integers  may be given as a list or by a sequence of individual
47
  elements. The output is the numerical semigroup spanned by List.
48
  
49
  String  does  not  need  to  be  present.  When  it  is  present, it must be
50
  "generators".
51
  
52
    Example  
53
    gap> s1 := NumericalSemigroupByGenerators(3,5,7);             
54
    <Numerical semigroup with 3 generators>
55
    gap> s2 := NumericalSemigroupByGenerators([3,5,7]);
56
    <Numerical semigroup with 3 generators>
57
    gap> s3 := NumericalSemigroup("generators",3,5,7); 
58
    <Numerical semigroup with 3 generators>
59
    gap> s4 := NumericalSemigroup("generators",[3,5,7]);
60
    <Numerical semigroup with 3 generators>
61
    gap> s5 := NumericalSemigroup(3,5,7);               
62
    <Numerical semigroup with 3 generators>
63
    gap> s6 := NumericalSemigroup([3,5,7]);
64
    <Numerical semigroup with 3 generators>
65
    gap> s1=s2;s2=s3;s3=s4;s4=s5;s5=s6;
66
    true
67
    true
68
    true
69
    true
70
    true
71
  
72
  
73
  2.1-2 NumericalSemigroupBySubAdditiveFunction
74
  
75
  NumericalSemigroupBySubAdditiveFunction( List )  function
76
  NumericalSemigroup( String, List )  function
77
  
78
  A  periodic  subadditive function with period m is given through the list of
79
  images  of  the integers from 1 to m. The image of m has to be 0. The output
80
  is the numerical semigroup determined by this subadditive function.
81
  
82
  In the second form, String must be "subadditive".
83
  
84
    Example  
85
    gap> s := NumericalSemigroupBySubAdditiveFunction([5,4,2,0]);
86
    <Numerical semigroup>
87
    gap> t := NumericalSemigroup("subadditive",[5,4,2,0]);;     
88
    gap> s=t;
89
    true
90
  
91
  
92
  2.1-3 NumericalSemigroupByAperyList
93
  
94
  NumericalSemigroupByAperyList( List )  function
95
  NumericalSemigroup( String, List )  function
96
  
97
  List is an Apéry list. The output is the numerical semigroup whose Apéry set
98
  with respect to the length of given list is List.
99
  
100
  In the second form, String must be "apery".
101
  
102
    Example  
103
    gap> s:=NumericalSemigroup(3,11);;
104
    gap> ap := AperyListOfNumericalSemigroupWRTElement(s,20);
105
    [ 0, 21, 22, 3, 24, 25, 6, 27, 28, 9, 30, 11, 12, 33, 14, 15, 36, 17, 18, 39 ]
106
    gap> t:=NumericalSemigroupByAperyList(ap);;
107
    gap> r := NumericalSemigroup("apery",ap);;
108
    gap> s=t;t=r;
109
    true
110
    true
111
  
112
  
113
  2.1-4 NumericalSemigroupBySmallElements
114
  
115
  NumericalSemigroupBySmallElements( List )  function
116
  NumericalSemigroup( String, List )  function
117
  
118
  List is the set of small elements of a numerical semigroup, that is, the set
119
  of  all elements not greater than the conductor. The output is the numerical
120
  semigroup with this set of small elements. When no such semigroup exists, an
121
  error is returned.
122
  
123
  In the second form, String must be "elements".
124
  
125
    Example  
126
    gap> s:=NumericalSemigroup(3,11);;
127
    gap> se := SmallElements(s);
128
    [ 0, 3, 6, 9, 11, 12, 14, 15, 17, 18, 20 ]
129
    gap> t := NumericalSemigroupBySmallElements(se);;
130
    gap> r := NumericalSemigroup("elements",se);;
131
    gap> s=t;t=r;                                            
132
    true
133
    true
134
    gap> e := [ 0, 3, 6, 9, 11, 14, 15, 17, 18, 20 ];    
135
    [ 0, 3, 6, 9, 11, 14, 15, 17, 18, 20 ]
136
    gap> NumericalSemigroupBySmallElements(e);
137
    Error, The argument does not represent a numerical semigroup called from
138
    <function "NumericalSemigroupBySmallElements">( <arguments> )
139
     called from read-eval loop at line 35 of *stdin*
140
    you can 'quit;' to quit to outer loop, or
141
    you can 'return;' to continue
142
    brk> 
143
  
144
  
145
  2.1-5 NumericalSemigroupByGaps
146
  
147
  NumericalSemigroupByGaps( List )  function
148
  NumericalSemigroup( String, List )  function
149
  
150
  List  is  the  set  of  gaps  of  a  numerical  semigroup. The output is the
151
  numerical semigroup with this set of gaps. When no semigroup exists with the
152
  given set as set of gaps, an error is returned.
153
  
154
  In the second form, String must be "gaps".
155
  
156
    Example  
157
    gap> g := [ 1, 2, 4, 5, 7, 8, 10, 13, 16 ];;
158
    gap> s := NumericalSemigroupByGaps(g);;
159
    gap> t := NumericalSemigroup("gaps",g);;
160
    gap> s=t;
161
    true
162
    gap> h := [ 1, 2, 5, 7, 8, 10, 13, 16 ];;   
163
    gap> NumericalSemigroupByGaps(h);
164
    Error, The argument does not represent the gaps of a numerical semigroup called
165
     from
166
    <function "NumericalSemigroupByGaps">( <arguments> )
167
     called from read-eval loop at line 34 of *stdin*
168
    you can 'quit;' to quit to outer loop, or
169
    you can 'return;' to continue
170
    brk> 
171
  
172
  
173
  2.1-6 NumericalSemigroupByFundamentalGaps
174
  
175
  NumericalSemigroupByFundamentalGaps( List )  function
176
  NumericalSemigroup( String, List )  function
177
  
178
  List  is the set of fundamental gaps of a numerical semigroup. The output is
179
  the  numerical  semigroup  determined  by  these  gaps.  When  the given set
180
  contains  elements  (which will be gaps) that are not fundamental gaps, they
181
  are silently removed.
182
  
183
  In the second form, String must be "fundamentalgaps".
184
  
185
    Example  
186
    gap> fg := [ 11, 14, 17, 20, 23, 26, 29, 32, 35 ];;
187
    gap> NumericalSemigroupByFundamentalGaps(fg);
188
    <Numerical semigroup>
189
    gap> NumericalSemigroup("fundamentalgaps",fg);     
190
    <Numerical semigroup>
191
    gap> last=last2;
192
    true
193
    gap> gg := [ 11, 17, 20, 22, 23, 26, 29, 32, 35 ];; #22 is not fundamental
194
    gap> NumericalSemigroup("fundamentalgaps",fg);     
195
    <Numerical semigroup>
196
  
197
  
198
  2.1-7 NumericalSemigroupByAffineMap
199
  
200
  NumericalSemigroupByAffineMap( a, b, c )  function
201
  NumericalSemigroup( String, a, b )  function
202
  
203
  Given three nonnegative integers a, b and c, with a,c>0 and gcd(b,c)=1, this
204
  function  returns the least (with restpect to set order inclusion) numerical
205
  semigroup  containing  c  and closed under the map x↦ ax+b. The procedure is
206
  explained in [Ugo16].
207
  
208
  In the second form, String must be "affinemap".
209
  
210
    Example  
211
    gap> s:=NumericalSemigroupByAffineMap(3,1,3);
212
    <Numerical semigroup with 3 generators>
213
    gap> SmallElements(s);
214
    [ 0, 3, 6, 9, 10, 12, 13, 15, 16, 18 ]
215
    gap> t:=NumericalSemigroup("affinemap",3,1,3);;
216
    gap> s=t;
217
    true
218
  
219
  
220
  2.1-8 ModularNumericalSemigroup
221
  
222
  ModularNumericalSemigroup( a, b )  function
223
  NumericalSemigroup( String, a, b )  function
224
  
225
  Given  two  positive  integers  a  and  b,  this  function returns a modular
226
  numerical semigroup satisfying ax mod b le x.
227
  
228
  In the second form, String must be "modular".
229
  
230
    Example  
231
    gap> ModularNumericalSemigroup(3,7);
232
    <Modular numerical semigroup satisfying 3x mod 7 <= x >
233
    gap> NumericalSemigroup("modular",3,7);  
234
    <Modular numerical semigroup satisfying 3x mod 7 <= x >
235
  
236
  
237
  2.1-9 ProportionallyModularNumericalSemigroup
238
  
239
  ProportionallyModularNumericalSemigroup( a, b, c )  function
240
  NumericalSemigroup( String, a, b )  function
241
  
242
  Given  three  positive  integers  a,  b  and  c,  this  function  returns  a
243
  proportionally modular numerical semigroup satisfying axmod b le cx.
244
  
245
  In the second form, String must be "propmodular".
246
  
247
    Example  
248
    gap> ProportionallyModularNumericalSemigroup(3,7,12);
249
    <Proportionally modular numerical semigroup satisfying 3x mod 7 <= 12x >
250
    gap> NumericalSemigroup("propmodular",3,7,12);
251
    <Proportionally modular numerical semigroup satisfying 3x mod 7 <= 12x >
252
  
253
  
254
  When c=1, the semigroup is seen as a modular numerical semigroup.
255
  
256
    Example  
257
    gap> NumericalSemigroup("propmodular",67,98,1);
258
    <Modular numerical semigroup satisfying 67x mod 98 <= x >
259
  
260
  
261
  Numerical semigroups generated by an interval of positive integers are known
262
  to  be  proportionally  modular,  and  thus  they are treated as such, since
263
  membership   and   other  problems  can  be  solved  efficiently  for  these
264
  semigroups.
265
  
266
  2.1-10 NumericalSemigroupByInterval
267
  
268
  NumericalSemigroupByInterval( List )  function
269
  NumericalSemigroup( String, List )  function
270
  
271
  The  input  is  a  list  of rational numbers defining a closed interval. The
272
  output  is  the  semigroup  of  numerators  of  all rational numbers in this
273
  interval.
274
  
275
  String  does  not  need  to  be  present.  When  it  is  present, it must be
276
  "interval".
277
  
278
    Example  
279
    gap> NumericalSemigroupByInterval(7/5,5/3);
280
    <Proportionally modular numerical semigroup satisfying 25x mod 35 <= 4x >
281
    gap> NumericalSemigroup("interval",[7/5,5/3]);
282
    <Proportionally modular numerical semigroup satisfying 25x mod 35 <= 4x >
283
    gap> SmallElements(last);
284
    [ 0, 3, 5 ]
285
  
286
  
287
  2.1-11 NumericalSemigroupByOpenInterval
288
  
289
  NumericalSemigroupByOpenInterval( List )  function
290
  NumericalSemigroup( String, List )  function
291
  
292
  The input is a list of rational numbers defining a open interval. The output
293
  is the semigroup of numerators of all rational numbers in this interval.
294
  
295
  String  does  not  need  to  be  present.  When  it  is  present, it must be
296
  "openinterval".
297
  
298
    Example  
299
    gap> NumericalSemigroupByOpenInterval(7/5,5/3);
300
    <Numerical semigroup>
301
    gap> NumericalSemigroup("openinterval",[7/5,5/3]);
302
    <Numerical semigroup>
303
    gap> SmallElements(last);                         
304
    [ 0, 3, 6, 8 ] 
305
  
306
  
307
  
308
  2.2 Some basic tests
309
  
310
  This  section  describes some basic tests on numerical semigroups. The first
311
  described  tests  refer  to what the semigroup is currently known to be (not
312
  necessarily the way it was created). Then are presented functions to test if
313
  a  given  list represents the small elements, gaps or the Apéry set (see 1.)
314
  of  a  numerical  semigroup;  to  test  if an integer belongs to a numerical
315
  semigroup and if a numerical semigroup is a subsemigroup of another one.
316
  
317
  2.2-1 IsNumericalSemigroup
318
  
319
  IsNumericalSemigroup( NS )  attribute
320
  IsNumericalSemigroupByGenerators( NS )  attribute
321
  IsNumericalSemigroupByMinimalGenerators( NS )  attribute
322
  IsNumericalSemigroupByInterval( NS )  attribute
323
  IsNumericalSemigroupByOpenInterval( NS )  attribute
324
  IsNumericalSemigroupBySubAdditiveFunction( NS )  attribute
325
  IsNumericalSemigroupByAperyList( NS )  attribute
326
  IsNumericalSemigroupBySmallElements( NS )  attribute
327
  IsNumericalSemigroupByGaps( NS )  attribute
328
  IsNumericalSemigroupByFundamentalGaps( NS )  attribute
329
  IsProportionallyModularNumericalSemigroup( NS )  attribute
330
  IsModularNumericalSemigroup( NS )  attribute
331
  
332
  NS  is a numerical semigroup and these attributes are available (their names
333
  should be self explanatory).
334
  
335
    Example  
336
    gap> s:=NumericalSemigroup(3,7);
337
    <Numerical semigroup with 2 generators>
338
    gap> AperyListOfNumericalSemigroupWRTElement(s,30);;
339
    gap> t:=NumericalSemigroupByAperyList(last);
340
    <Numerical semigroup>
341
    gap> IsNumericalSemigroupByGenerators(s);
342
    true
343
    gap> IsNumericalSemigroupByGenerators(t);
344
    false
345
    gap> IsNumericalSemigroupByAperyList(s);
346
    false
347
    gap> IsNumericalSemigroupByAperyList(t);
348
    true
349
  
350
  
351
  2.2-2 RepresentsSmallElementsOfNumericalSemigroup
352
  
353
  RepresentsSmallElementsOfNumericalSemigroup( L )  attribute
354
  
355
  Tests  if  the  list  L  (which  has to be a set) may represent the ``small"
356
  elements of a numerical semigroup.
357
  
358
    Example  
359
    gap> L:=[ 0, 3, 6, 9, 11, 12, 14, 15, 17, 18, 20 ];
360
    [ 0, 3, 6, 9, 11, 12, 14, 15, 17, 18, 20 ]
361
    gap> RepresentsSmallElementsOfNumericalSemigroup(L);
362
    true
363
    gap> L:=[ 6, 9, 11, 12, 14, 15, 17, 18, 20 ];
364
    [ 6, 9, 11, 12, 14, 15, 17, 18, 20 ]
365
    gap> RepresentsSmallElementsOfNumericalSemigroup(L);
366
    false
367
  
368
  
369
  2.2-3 RepresentsGapsOfNumericalSemigroup
370
  
371
  RepresentsGapsOfNumericalSemigroup( L )  attribute
372
  
373
  Tests  if  the  list  L  may  represent  the  gaps  (see  1.) of a numerical
374
  semigroup.
375
  
376
    Example  
377
    gap> s:=NumericalSemigroup(3,7);
378
    <Numerical semigroup with 2 generators>
379
    gap> L:=GapsOfNumericalSemigroup(s);
380
    [ 1, 2, 4, 5, 8, 11 ]
381
    gap> RepresentsGapsOfNumericalSemigroup(L);
382
    true
383
    gap> L:=Set(List([1..21],i->RandomList([1..50])));
384
    [ 2, 6, 7, 8, 10, 12, 14, 19, 24, 28, 31, 35, 42, 50 ]
385
    gap> RepresentsGapsOfNumericalSemigroup(L);
386
    false
387
  
388
  
389
  2.2-4 IsAperyListOfNumericalSemigroup
390
  
391
  IsAperyListOfNumericalSemigroup( L )  function
392
  
393
  Tests  whether  a  list  L  of  integers  may  represent the Apéry list of a
394
  numerical  semigroup. It returns true when the periodic function represented
395
  by  L is subadditive (see RepresentsPeriodicSubAdditiveFunction (A.2-1)) and
396
  the  remainder  of  the division of L[i] by the length of L is i and returns
397
  false otherwise (the criterium used is the one explained in [Ros96b]).
398
  
399
    Example  
400
    gap> IsAperyListOfNumericalSemigroup([0,21,7,28,14]);
401
    true
402
  
403
  
404
  2.2-5 IsSubsemigroupOfNumericalSemigroup
405
  
406
  IsSubsemigroupOfNumericalSemigroup( S, T )  function
407
  
408
  S and T are numerical semigroups. Tests whether T is contained in S.
409
  
410
    Example  
411
    gap> S := NumericalSemigroup("modular", 5,53);
412
    <Modular numerical semigroup satisfying 5x mod 53 <= x >
413
    gap> T:=NumericalSemigroup(2,3);
414
    <Numerical semigroup with 2 generators>
415
    gap> IsSubsemigroupOfNumericalSemigroup(T,S);
416
    true
417
    gap> IsSubsemigroupOfNumericalSemigroup(S,T);
418
    false
419
  
420
  
421
  2.2-6 IsSubset
422
  
423
  IsSubset( S, T )  attribute
424
  
425
  S  is  a  numerical semigroup. T can be a numerical semigroup, in which case
426
  the   function  is  just  a  synonym  of  IsSubsemigroupOfNumericalSemigroup
427
  (2.2-5),  or a list of integers, in which case tests whether all elements of
428
  the list belong to S.
429
  
430
    Example  
431
    gap> ns1 := NumericalSemigroup(5,7);;
432
    gap> ns2 := NumericalSemigroup(5,7,11);;
433
    gap> IsSubset(ns1,ns2);
434
    false
435
    gap> IsSubset(ns2,[5,15]);
436
    true
437
    gap> IsSubset(ns1,[5,11]);
438
    false
439
    gap> IsSubset(ns2,ns1);   
440
    true
441
  
442
  
443
  2.2-7 BelongsToNumericalSemigroup
444
  
445
  BelongsToNumericalSemigroup( n, S )  operation
446
  \in( n, S )  operation
447
  
448
  n  is  an integer and S is a numerical semigroup. Tests whether n belongs to
449
  S.  \in(n,S) calls the infix variant n in S, and both can be seen as a short
450
  for BelongsToNumericalSemigroup(n,S).
451
  
452
    Example  
453
    gap> S := NumericalSemigroup("modular", 5,53);
454
    <Modular numerical semigroup satisfying 5x mod 53 <= x >
455
    gap> BelongsToNumericalSemigroup(15,S);
456
    false
457
    gap> 15 in S;
458
    false
459
    gap> SmallElementsOfNumericalSemigroup(S);
460
    [ 0, 11, 12, 13, 22, 23, 24, 25, 26, 32, 33, 34, 35, 36, 37, 38, 39, 43 ]
461
    gap> BelongsToNumericalSemigroup(13,S);
462
    true
463
    gap> 13 in S;
464
    true
465
  
466
  
467

468