spielwiese
Last change on this file since a56ed4 was a56ed4, checked in by Hans Schoenemann <hannes@…>, 13 years ago
• Property mode set to `100755`
File size: 70.9 KB
Line
1///////////////////////////////////////////////////////
2version="\$Id: fpadim.lib,v beta 2010/09/27 13:14:51 studzins Exp \$";
3category="Noncommutative";
4info="
5LIBRARY: fpadim.lib     Algorithms for quotient algebras
6AUTHORS: Grischa Studzinski,       grischa.studzinski@rwth-aachen.de
7
8SUPPORT: Projects LE 2697/2-1; KR 1907/3-1 of the Priority Programme SPP 1489:
9@* 'Algorithmische und Experimentelle Methoden in Algebra, Geometrie und Zahlentheorie'
10@* of the German DFG
11
12OVERVIEW: Given the free algebra A = K<x_1,...,x_n> and a (finite) Groebner basis
13@*      GB = {g_1,..,g_w}, one is interested in the K-dimension and in the
14@*      explicit K-basis of A/<GB>.
15@*      Therefore one is interested in the following data:
16@*      - the Ufnarovskij graph induced by GB
17@*      - the mistletoes of A/<GB>
18@*      - the K-dimension of A/<GB>
19@*      - the Hilbert series of A/<GB>
20@*
21@*      The Ufnarovskij graph is used to determine whether A/<GB> has finite
22@*      K-dimension. One has to check if the graph contains cycles.
23@*      For the whole theory we refer to [ufna]. Given a
24@*      reduced set of monomials GB one can define the basis tree, which vertex
25@*      set V consists of all normal monomials w.r.t. GB. For every two
26@*      monomials m_1, m_2 in V there is a direct edge from m_1 to m_2, if and
27@*      only if there exists x_k in {x_1,..,x_n}, such that m_1*x_k = m_2. The
28@*      set M = {m in V | there is no edge from m to another monomial in V} is
29@*      called the set of mistletoes. As one can easily see it consists of
30@*      the endpoints of the graph. Since there is a unique path to every
31@*      monomial in V the whole graph can be described only from the knowledge
32@*      of the mistletoes. Note that V corresponds to a basis of A/<GB>, so
33@*      knowing the mistletoes we know a K-basis. For more details see
34@*      [studzins]. This package uses the Letterplace format introduced by
35@*      [lls]. The algebra can either be represented as a Letterplace ring or
36@*      via integer vectors: Every variable will only be represented by its
37@*      number, so variable one is represented as 1, variable two as 2 and so
38@*      on. The monomial x_1*x_3*x_2 for example will be stored as (1,3,2).
39@*      Multiplication is concatenation. Note that there is no algorithm for
40@*      computing the normalform yet, but for our case it is not needed.
41@*
42
43REFERENCES:
44
45@*   [ufna] Ufnarovskij: Combinatorical and asymptotic methods in algebra, 1990
46@*   [lls] Levandovskyy, La Scala: Letterplace ideals and non-commutative
47           Groebner bases, 2009
48@*   [studzins] Studzinski: Dimension computations in non-commutative,
49                      associative algebras, Diploma thesis, RWTH Aachen, 2010
50
51ASSUMPTIONS:
52@* - basering is always a Letterplace ring
53@* - all intvecs correspond to Letterplace monomials
54@* - if you specify a different degree bound d,
55      d <= attrib(basering,uptodeg) holds
56@* In the procedures below, 'iv' stands for intvec representation
57   and 'lp' for the letterplace representation of monomials
58
59PROCEDURES:
60
61ivDHilbert(L,n[,d]);       computes the K-dimension and the Hilbert series
62ivDHilbertSickle(L,n[,d]); computes mistletoes, K-dimension and Hilbert series
63ivDimCheck(L,n);           checks if the K-dimension of A/<L> is infinite
64ivHilbert(L,n[,d]);        computes the Hilbert series of A/<L> in intvec format
65ivKDim(L,n[,d]);           computes the K-dimension of A/<L> in intvec format
66ivMis2Dim(M);              computes the K-dimension of the factor algebra
67ivOrdMisLex(M);            orders a list of intvecs lexicographically
68ivSickle(L,n[,d]);         computes the mistletoes of A/<L> in intvec format
69ivSickleHil(L,n[,d]);      computes the mistletoes and Hilbert series of A/<L>
70ivSickleDim(L,n[,d]);      computes the mistletoes and the K-dimension of A/<L>
71lpDHilbert(G[,d,n]);       computes the K-dimension and Hilbert series of A/<G>
72lpDHilbertSickle(G[,d,n]); computes mistletoes, K-dimension and Hilbert series
73lpHilbert(G[,d,n]);        computes the Hilbert series of A/<G> in lp format
74lpDimCheck(G);             checks if the K-dimension of A/<G> is infinite
75lpKDim(G[,d,n]);           computes the K-dimension of A/<G> in lp format
76lpMis2Dim(M);              computes the K-dimension of the factor algebra
77lpOrdMisLex(M);            orders an ideal of lp-monomials lexicographically
78lpSickle(G[,d,n]);         computes the mistletoes of A/<G> in lp format
79lpSickleHil(G[,d,n]);      computes the mistletoes and Hilbert series of A/<G>
80lpSickleDim(G[,d,n]);      computes the mistletoes and the K-dimension of A/<G>
81sickle(G[,m,d,h]);         can be used to access all lp main procedures
82
83
84ivL2lpI(L);           transforms a list of intvecs into an ideal of lp monomials
85iv2lp(I);             transforms an intvec into the corresponding monomial
86iv2lpList(L);         transforms a list of intmats into an ideal of lp monomials
87iv2lpMat(M);          transforms an intmat into an ideal of lp monomials
88lp2iv(p);             transforms a polynomial into the corresponding intvec
89lp2ivId(G);           transforms an ideal into the corresponding list of intmats
90lpId2ivLi(G);         transforms a lp-ideal into the corresponding list of intvecs
91
93";
94
95LIB "freegb.lib"; //for letterplace rings
96LIB "general.lib";//for sorting mistletoes
97
98/////////////////////////////////////////////////////////
99
100
101//--------------- auxiliary procedures ------------------
102
103static proc allVars(list L, intvec P, int n)
104"USAGE: allVars(L,P,n); L a list of intmats, P an intvec, n an integer
105RETURN: 0, if all variables are contained in the quotient algebra, 1 otherwise
106"
107{int i,j,r;
108 intvec V;
109 for (i = 1; i <= size(P); i++) {if (P[i] == 1){ j = i; break;}}
110 V = L[j][1..nrows(L[j]),1];
111 for (i = 1; i <= n; i++) {if (isInVec(i,V) == 0) {r = 1; break;}}
112 if (r == 0) {return(1);}
113 else {return(0);}
114}
115
116static proc checkAssumptions(int d, list L)
117"PURPOSE: Checks, if all the Assumptions are holding
118"
119{if (typeof(attrib(basering,"isLetterplaceRing"))=="string") {ERROR("Basering is not a Letterplace ring!");}
120 if (d > attrib(basering,"uptodeg")) {ERROR("Specified degree bound exceeds ring parameter!");}
121 int i;
122 for (i = 1; i <= size(L); i++)
123 {if (entryViolation(L[i], attrib(basering,"lV")))
124  {ERROR("Not allowed monomial/intvec found!");}
125 }
126 return();
127}
128
129static proc createStartMat(int d, int n)
130"USAGE: createStartMat(d,n); d, n integers
131RETURN: An intmat
132PURPOSE:Creating the intmat with all normal monomials in n variables and of degree d to start with
133NOTE:   d has to be > 0
134"
135{intmat M[(n^d)][d];
136 int i1,i2,i3,i4;
137 for (i1 = 1; i1 <= d; i1++)  //Spalten
138 {i2 = 1; //durchlaeuft Zeilen
139  while (i2 <= (n^d))
140  {for (i3 = 1; i3 <= n; i3++)
141   {for (i4 = 1; i4 <= (n^(i1-1)); i4++)
142    {M[i2,i1] = i3;
143     i2 = i2 + 1;
144    }
145   }
146  }
147 }
148 return(M);
149}
150
151static proc createStartMat1(int n, intmat M)
152"USAGE: createStartMat1(n,M); n an integer, M an intmat
153RETURN: An intmat with all variables except those in M
154"
155{int i;
156 intvec V,Vt;
157 V = M[(1..nrows(M)),1];
158 for (i = 1; i <= size(V); i++) {if (isInVec(i,V) == 0) {Vt = Vt,i;}}
159 if (Vt == 0) {intmat S; return(S);}
160 else {Vt = Vt[2..size(Vt)]; intmat S [size(Vt)][1]; S[1..size(Vt),1] = Vt; return(S);}
161}
162
163static proc entryViolation(intmat M, int n)
164"PURPOSE:checks, if all entries in M are variable-related
165"
166{int i,j;
167 for (i = 1; i <= nrows(M); i++)
168 {for (j = 1; j <= ncols(M); j++)
169  {if(!((1<=M[i,j])&&(M[i,j]<=n))) {return(1);}}
170 }
171 return(0);
172}
173
174static proc findDimen(intvec V, int n, list L, intvec P, list #)
175"USAGE: findDimen(V,n,L,P,degbound); V,P intvecs, n, an integer, L a list,
176@*      degbound an optional integer
177RETURN: An integer
178PURPOSE:Computing the K-dimension of the quotient algebra
179"
180{int degbound = 0;
181 if (size(#) > 0) {if (#[1] > 0) {degbound = #[1];}}
182 int dimen,i,j,w,it;
183 intvec Vt,Vt2;
184 module M;
185 if (degbound == 0)
186 {for (i = 1; i <= n; i++)
187  {Vt = V, i; w = 0;
188   for (j = 1; j<= size(P); j++)
189   {if (P[j] <= size(Vt))
190    {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
191     if (isInMat(Vt2,L[j]) > 0) {w = 1; break;}
192    }
193   }
194    if (w == 0)
195    {vector Vtt;
196     for (it = 1; it <= size(Vt); it++){Vtt = Vtt + Vt[it]*gen(it);}
197     M = M,Vtt;
198     kill Vtt;
199    }
200  }
201  if (size(M) == 0) {return(0);}
202  else
203  {M = simplify(M,2);
204   for (i = 1; i <= size(M); i++)
205   {kill Vt; intvec Vt;
206    for (j =1; j <= size(M[i]); j++){Vt[j] =  int(leadcoef(M[i][j]));}
207    dimen = dimen + 1 + findDimen(Vt,n,L,P);
208   }
209   return(dimen);
210  }
211 }
212 else
213 {if (size(V) > degbound) {ERROR("monomial exceeds degreebound");}
214  if (size(V) == degbound) {return(0);}
215  for (i = 1; i <= n; i++)
216  {Vt = V, i; w = 0;
217   for (j = 1; j<= size(P); j++)
218   {if (P[j] <= size(Vt))
219    {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
220     if (isInMat(Vt2,L[j]) > 0) {w = 1; break;}
221    }
222   }
223    if (w == 0) {vector Vtt;
224     for (it = 1; it <= size(Vt); it++){Vtt = Vtt + Vt[it]*gen(it);}
225     M = M,Vtt;
226     kill Vtt;
227    }
228  }
229  if (size(M) == 0) {return(0);}
230  else
231  {M = simplify(M,2);
232   for (i = 1; i <= size(M); i++)
233   {kill Vt; intvec Vt;
234    for (j =1; j <= size(M[i]); j++){Vt[j] =  int(leadcoef(M[i][j]));}
235    dimen = dimen + 1 + findDimen(Vt,n,L,P,degbound);
236   }
237   return(dimen);
238  }
239 }
240}
241
242static proc findCycle(intvec V, list L, intvec P, int n, int ld, module M)
243"USAGE:
244RETURN: 1, if Ufn-graph contains a cycle, or 0 otherwise
245PURPOSE:Searching the Ufnarovskij graph for cycles
246"
247{int i,j,w,r;intvec Vt,Vt2;
248 int it, it2;
249 if (size(V) < ld)
250 {for (i = 1; i <= n; i++)
251  {Vt = V,i; w = 0;
252   for (j = 1; j <= size(P); j++)
253   {if (P[j] <= size(Vt))
254    {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
255     if (isInMat(Vt2,L[j]) > 0)
256     {w = 1; break;}
257    }
258   }
259   if (w == 0) {r = findCycle(Vt,L,P,n,ld,M);}
260   if (r == 1) {break;}
261  }
262  return(r);
263 }
264 else
265 {j = size(M);
266  if (j > 0)
267  {
268   intmat Mt[j][nrows(M)];
269   for (it = 1; it <= j; it++)
270   { for(it2 = 1; it2 <= nrows(M);it2++)
272   }
273   Vt = V[(size(V)-ld+1)..size(V)];
274   //Mt; type(Mt);Vt;type(Vt);
275   if (isInMat(Vt,Mt) > 0) {return(1);}
276   else
277   {vector Vtt;
278    for (it =1; it <= size(Vt); it++)
279     {Vtt = Vtt + Vt[it]*gen(it);}
280    M = M,Vtt;
281    kill Vtt;
282    for (i = 1; i <= n; i++)
283    {Vt = V,i; w = 0;
284     for (j = 1; j <= size(P); j++)
285     {if (P[j] <= size(Vt))
286      {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
287      //L[j]; type(L[j]);Vt2;type(Vt2);
288       if (isInMat(Vt2,L[j]) > 0)
289       {w = 1; break;}
290      }
291     }
292     if (w == 0) {r = findCycle(Vt,L,P,n,ld,M);}
293     if (r == 1) {break;}
294    }
295    return(r);
296   }
297  }
298  else
299  { Vt = V[(size(V)-ld+1)..size(V)];
300    vector Vtt;
301    for (it = 1; it <= size(Vt); it++)
302     {Vtt = Vtt + Vt[it]*gen(it);}
303    M = Vtt;
304    kill Vtt;
305    for (i = 1; i <= n; i++)
306    {Vt = V,i; w = 0;
307     for (j = 1; j <= size(P); j++)
308     {if (P[j] <= size(Vt))
309      {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
310      //L[j]; type(L[j]);Vt2;type(Vt2);
311       if (isInMat(Vt2,L[j]) > 0)
312       {w = 1; break;}
313      }
314     }
315     if (w == 0) {r = findCycle(Vt,L,P,n,ld,M);}
316     if (r == 1) {break;}
317    }
318    return(r);
319  }
320 }
321}
322
323static proc findHCoeff(intvec V,int n,list L,intvec P,intvec H,list #)
324"USAGE: findHCoeff(V,n,L,P,H,degbound); L a list of intmats, degbound an integer
325RETURN: An intvec
326PURPOSE:Computing the coefficient of the Hilbert series (upto degree degbound)
327NOTE:   Starting with a part of the Hilbert series we change the coefficient
328@*      depending on how many baseelements we found on the actual branch
329"
330{int degbound = 0;
331 if (size(#) > 0){if (#[1] > 0){degbound = #[1];}}
332 int i,w,j,it;
333 int h1 = 0;
334 intvec Vt,Vt2,H1;
335 module M;
336 if (degbound == 0)
337 {for (i = 1; i <= n; i++)
338  {Vt = V, i; w = 0;
339   for (j = 1; j<= size(P); j++)
340   {if (P[j] <= size(Vt))
341    {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
342     if (isInMat(Vt2,L[j]) > 0) {w = 1; break;}
343    }
344   }
345    if (w == 0)
346    {vector Vtt;
347     for (it = 1; it <= size(Vt); it++){Vtt = Vtt + Vt[it]*gen(it);}
348     M = M,Vtt;
349     kill Vtt;
350    }
351  }
352  if (size(M) == 0) {return(H);}
353  else
354  {M = simplify(M,2);
355   for (i = 1; i <= size(M); i++)
356   {kill Vt; intvec Vt;
357    for (j =1; j <= size(M[i]); j++) {Vt[j] =  int(leadcoef(M[i][j]));}
358    h1 = h1 + 1; H1 = findHCoeff(Vt,n,L,P,H1);
359   }
360   if (size(H1) < (size(V)+2)) {H1[(size(V)+2)] = h1;}
361   else {H1[(size(V)+2)] = H1[(size(V)+2)] + h1;}
362   H1 = H1 + H;
363   return(H1);
364  }
365 }
366 else
367 {if (size(V) > degbound) {ERROR("monomial exceeds degreebound");}
368  if (size(V) == degbound) {return(H);}
369  for (i = 1; i <= n; i++)
370  {Vt = V, i; w = 0;
371   for (j = 1; j<= size(P); j++)
372   {if (P[j] <= size(Vt))
373    {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
374     if (isInMat(Vt2,L[j]) > 0) {w = 1; break;}
375    }
376   }
377    if (w == 0)
378    {vector Vtt;
379     for (it = 1; it <= size(Vt); it++){Vtt = Vtt + Vt[it]*gen(it);}
380     M = M,Vtt;
381     kill Vtt;
382    }
383  }
384  if (size(M) == 0) {return(H);}
385  else
386  {M = simplify(M,2);
387   for (i = 1; i <= size(M); i++)
388   {kill Vt; intvec Vt;
389    for (j =1; j <= size(M[i]); j++)
391    h1 = h1 + 1; H1 = findHCoeff(Vt,n,L,P,H1,degbound);
392   }
393   if (size(H1) < (size(V)+2)) { H1[(size(V)+2)] = h1;}
394   else {H1[(size(V)+2)] = H1[(size(V)+2)] + h1;}
395   H1 = H1 + H;
396   return(H1);
397  }
398 }
399}
400
401static proc findHCoeffMis(intvec V, int n, list L, intvec P, list R,list #)
402"USAGE: findHCoeffMis(V,n,L,P,R,degbound); degbound an optional integer, L a
403@*      list of Intmats, R
404RETURN: A list
405PURPOSE:Computing the coefficients of the Hilbert series and the Mistletoes all
406@*      at once
407"
408{int degbound = 0;
409 if (size(#) > 0) {if (#[1] > 0) {degbound = #[1];}}
410 int i,w,j,h1;
411 intvec Vt,Vt2,H1; int it;
412 module M;
413 if (degbound == 0)
414 {for (i = 1; i <= n; i++)
415  {Vt = V, i; w = 0;
416   for (j = 1; j<= size(P); j++)
417   {if (P[j] <= size(Vt))
418    {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
419     if (isInMat(Vt2,L[j]) > 0) {w = 1; break;}
420    }
421   }
422    if (w == 0)
423    {vector Vtt;
424    for (it = 1; it <= size(Vt); it++){Vtt = Vtt + Vt[it]*gen(it);}
425    M = M,Vtt;
426    kill Vtt;
427    }
428  }
429  if (size(M) == 0) {if (size(R) < 2){R[2] = list(V);} else {R[2] = R[2] + list(V);} return(R);}
430  else
431  {M = simplify(M,2);
432   for (i = 1; i <= size(M); i++)
433   {kill Vt; intvec Vt;
434    for (j =1; j <= size(M[i]); j++)
436    if (size(R[1]) < (size(V)+2)) { R[1][(size(V)+2)] = 1;}
437    else
438    {R[1][(size(V)+2)] = R[1][(size(V)+2)] + 1;}
439    R = findHCoeffMis(Vt,n,L,P,R);
440   }
441   return(R);
442  }
443 }
444 else
445 {if (size(V) > degbound) {ERROR("monomial exceeds degreebound");}
446  if (size(V) == degbound)
447  {if (size(R) < 2){R[2] = list (V);}
448   else{R[2] = R[2] + list (V);}
449   return(R);
450  }
451  for (i = 1; i <= n; i++)
452  {Vt = V, i; w = 0;
453   for (j = 1; j<= size(P); j++)
454   {if (P[j] <= size(Vt))
455    {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
456     if (isInMat(Vt2,L[j]) > 0) {w = 1; break;}
457    }
458   }
459    if (w == 0)
460    {vector Vtt;
461    for (it = 1; it <= size(Vt); it++){Vtt = Vtt + Vt[it]*gen(it);}
462    M = M,Vtt;
463    kill Vtt;
464    }
465  }
466  if (size(M) == 0) {if (size(R) < 2){R[2] = list(V);} else {R[2] = R[2] + list(V);} return(R);}
467  else
468  {M = simplify(M,2);
469    for (i = 1; i <= ncols(M); i++)
470    {kill Vt; intvec Vt;
471     for (j =1; j <= size(M[i]); j++)
473     if (size(R[1]) < (size(V)+2)) { R[1][(size(V)+2)] = 1;}
474     else
475     {R[1][(size(V)+2)] = R[1][(size(V)+2)] + 1;}
476     R = findHCoeffMis(Vt,n,L,P,R,degbound);
477    }
478   return(R);
479  }
480 }
481}
482
483
484static proc findMisDim(intvec V,int n,list L,intvec P,list R,list #)
485"USAGE:
486RETURN: A list
487PURPOSE:Computing the K-dimension and the Mistletoes all at once
488"
489{int degbound = 0;
490 if (size(#) > 0) {if (#[1] > 0) {degbound = #[1];}}
491 int dimen,i,j,w;
492 intvec Vt,Vt2; int it;
493 module M;
494 if (degbound == 0)
495 {for (i = 1; i <= n; i++)
496  {Vt = V, i; w = 0;
497   for (j = 1; j<= size(P); j++)
498   {if (P[j] <= size(Vt))
499    {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
500     if (isInMat(Vt2,L[j]) > 0) {w = 1; break;}
501    }
502   }
503    if (w == 0)
504    {vector Vtt;
505     for (it = 1; it <= size(Vt); it++){Vtt = Vtt + Vt[it]*gen(it);}
506     M = M,Vtt;
507     kill Vtt;
508    }
509  }
510  if (size(M) == 0)
511  {if (size(R) < 2){R[2] = list (V);}
512   else{R[2] = R[2] + list(V);}
513   return(R);
514  }
515  else
516  {M = simplify(M,2);
517   for (i = 1; i <= size(M); i++)
518   {kill Vt; intvec Vt;
519    for (j =1; j <= size(M[i]); j++){Vt[j] =  int(leadcoef(M[i][j]));}
520     R[1] = R[1] + 1; R = findMisDim(Vt,n,L,P,R);
521   }
522   return(R);
523  }
524 }
525 else
526 {if (size(V) > degbound) {ERROR("monomial exceeds degreebound");}
527  if (size(V) == degbound)
528  {if (size(R) < 2){R[2] = list (V);}
529   else{R[2] = R[2] + list (V);}
530   return(R);
531  }
532  for (i = 1; i <= n; i++)
533  {Vt = V, i; w = 0;
534   for (j = 1; j<= size(P); j++)
535   {if (P[j] <= size(Vt))
536    {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
537     if (isInMat(Vt2,L[j]) > 0) {w = 1; break;}
538    }
539   }
540    if (w == 0)
541    {vector Vtt;
542     for (it = 1; it <= size(Vt); it++){Vtt = Vtt + Vt[it]*gen(it);}
543     M = M,Vtt;
544     kill Vtt;
545    }
546  }
547  if (size(M) == 0)
548  {if (size(R) < 2){R[2] = list (V);}
549   else{R[2] = R[2] + list(V);}
550   return(R);
551  }
552  else
553  {M = simplify(M,2);
554   for (i = 1; i <= size(M); i++)
555   {kill Vt; intvec Vt;
556    for (j =1; j <= size(M[i]); j++){Vt[j] =  int(leadcoef(M[i][j]));}
557     R[1] = R[1] + 1; R = findMisDim(Vt,n,L,P,R,degbound);
558   }
559   return(R);
560
561  }
562 }
563}
564
565
566static proc findmistletoes(intvec V, int n, list L, intvec P, list #)
567"USAGE: findmistletoes(V,n,L,P,degbound); V a normal word, n the number of
568@*      variables, L the GB, P the occuring degrees,
569@*      and degbound the (optional) degreebound
570RETURN: A list
571PURPOSE:Computing mistletoes starting in V
572NOTE:   V has to be normal w.r.t. L, it will not be checked for being so
573"
574{int degbound = 0;
575 if (size(#) > 0) {if (#[1] > 0) {degbound = #[1];}}
576 list R; intvec Vt,Vt2; int it;
577 int i,j;
578 module M;
579 if (degbound == 0)
580 {int w;
581  for (i = 1; i <= n; i++)
582  {Vt = V,i; w = 0;
583   for (j = 1; j <= size(P); j++)
584   {if (P[j] <= size(Vt))
585    {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
586     if (isInMat(Vt2,L[j]) > 0)
587     {w = 1; break;}
588    }
589   }
590   if (w == 0)
591   {vector Vtt;
592    for (it = 1; it <= size(Vt); it++){Vtt = Vtt + Vt[it]*gen(it);}
593    M = M,Vtt;
594    kill Vtt;
595   }
596  }
597  if (size(M)==0) {R = V; return(R);}
598  else
599  {M = simplify(M,2);
600   for (i = 1; i <= size(M); i++)
601   {kill Vt; intvec Vt;
602    for (j =1; j <= size(M[i]); j++){Vt[j] =  int(leadcoef(M[i][j]));}
603    R = R + findmistletoes(Vt,n,L,P);
604   }
605   return(R);
606  }
607 }
608 else
609 {if (size(V) > degbound) {ERROR("monomial exceeds degreebound");}
610  if (size(V) == degbound) {R = V; return(R);}
611  int w;
612  for (i = 1; i <= n; i++)
613  {Vt = V,i; w = 0;
614   for (j = 1; j <= size(P); j++)
615   {if (P[j] <= size(Vt))
616    {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
617     if (isInMat(Vt2,L[j]) > 0){w = 1; break;}
618    }
619   }
620   if (w == 0)
621   {vector Vtt;
622    for (it = 1; it <= size(Vt); it++){Vtt = Vtt + Vt[it]*gen(it);}
623    M = M,Vtt;
624    kill Vtt;
625   }
626  }
627  if (size(M) == 0) {R = V; return(R);}
628  else
629  {M = simplify(M,2);
630   for (i = 1; i <= ncols(M); i++)
631   {kill Vt; intvec Vt;
632    for (j =1; j <= size(M[i]); j++)
634      //Vt; typeof(Vt); size(Vt);
635      R = R + findmistletoes(Vt,n,L,P,degbound);
636   }
637   return(R);
638  }
639 }
640}
641
642static proc isInList(intvec V, list L)
643"USAGE: isInList(V,L); V an intvec, L a list of intvecs
644RETURN: An integer
645PURPOSE:Finding the position of V in L, returns 0, if V is not in M
646"
647{int i,n;
648 n = 0;
649 for (i = 1; i <= size(L); i++) {if (L[i] == V) {n = i; break;}}
650 return(n);
651}
652
653static proc isInMat(intvec V, intmat M)
654"USAGE: isInMat(V,M);V an intvec, M an intmat
655RETURN: An integer
656PURPOSE:Finding the position of V in M, returns 0, if V is not in M
657"
658{if (size(V) <> ncols(M)) {return(0);}
659 int i;
660 intvec Vt;
661 for (i = 1; i <= nrows(M); i++)
662 {Vt = M[i,1..ncols(M)];
663  if ((V-Vt) == 0){return(i);}
664 }
665 return(0);
666}
667
668static proc isInVec(int v,intvec V)
669"USAGE: isInVec(v,V); v an integer,V an intvec
670RETURN: An integer
671PURPOSE:Finding the position of v in V, returns 0, if v is not in V
672"
673{int i,n;
674 n = 0;
675 for (i = 1; i <= size(V); i++) {if (V[i] == v) {n = i; break;}}
676 return(n);
677}
678
679proc ivL2lpI(list L)
680"USAGE: ivL2lpI(L); L a list of intvecs
681RETURN: ideal
682PURPOSE:Transforming a list of intvecs into an ideal of Letterplace monomials
683ASSUME: - Intvec corresponds to a Letterplace monomial
684@*      - basering has to be a Letterplace ring
685EXAMPLE: example ivL2lpI; shows examples
686"
687{checkAssumptions(0,L);
688 int i; ideal G;
689 poly p;
690 for (i = 1; i <= size(L); i++)
691 {p = iv2lp(L[i]);
692  G[(size(G) + 1)] = p;
693 }
694 return(G);
695}
696example
697{
698  "EXAMPLE:"; echo = 2;
699  ring r = 0,(x,y,z),dp;
700  def R = makeLetterplaceRing(5);// constructs a Letterplace ring
701  setring R; //sets basering to Letterplace ring
702  intvec u = 1,1,2; intvec v = 2,1,3; intvec w = 3,1,1;
703  // u = x^2y, v = yxz, w = zx^2 in intvec representation
704  list L = u,v,w;
705  ivL2lpI(L);// invokes the procedure, returns the ideal containing u,v,w
706}
707
708proc iv2lp(intvec I)
709"USAGE: iv2lp(I); I an intvec
710RETURN: poly
711PURPOSE:Transforming an intvec into the corresponding Letterplace polynomial
712ASSUME: - Intvec corresponds to a Letterplace monomial
713@*      - basering has to be a Letterplace ring
714NOTE:   - Assumptions will not be checked!
715EXAMPLE: example iv2lp; shows examples
716"
717{if (I[1] == 0) {return(1);}
718 int i = size(I);
719 if (i > attrib(basering,"uptodeg")) {ERROR("polynomial exceeds degreebound");}
720 int j; poly p = 1;
721 for (j = 1; j <= i; j++) {if (I[j] > 0) { p = lpMult(p,var(I[j]));}} //ignore zeroes, because they correspond to 1
722 return(p);
723}
724example
725{
726  "EXAMPLE:"; echo = 2;
727  ring r = 0,(x,y,z),dp;
728  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
729  setring R; //sets basering to Letterplace ring
730  intvec u = 1,1,2; intvec v = 2,1,3; intvec w = 3,1,1;
731  // u = x^2y, v = yxz, w = zx^2 in intvec representation
732  iv2lp(u); // invokes the procedure and returns the corresponding poly
733  iv2lp(v);
734  iv2lp(w);
735}
736
737proc iv2lpList(list L)
738"USAGE: iv2lpList(L); L a list of intmats
739RETURN: ideal
740PURPOSE:Converting a list of intmats into an ideal of corresponding monomials
741ASSUME: - The rows of each intmat in L must correspond to a Letterplace monomial
742@*      - basering has to be a Letterplace ring
743EXAMPLE: example iv2lpList; shows examples
744"
745{checkAssumptions(0,L);
746 ideal G;
747 int i;
748 for (i = 1; i <= size(L); i++){G = G + iv2lpMat(L[i]);}
749 return(G);
750}
751example
752{
753  "EXAMPLE:"; echo = 2;
754  ring r = 0,(x,y,z),dp;
755  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
756  setring R; // sets basering to Letterplace ring
757  intmat u[3][1] = 1,1,2; intmat v[1][3] = 2,1,3; intmat w[2][3] = 3,1,1,2,3,1;
758  // defines intmats of different size containing intvec representations of
759  // monomials as rows
760  list L = u,v,w;
761  print(u); print(v); print(w); // shows the intmats contained in L
762  iv2lpList(L); // returns the corresponding monomials as an ideal
763}
764
765
766proc iv2lpMat(intmat M)
767"USAGE: iv2lpMat(M); M an intmat
768RETURN: ideal
769PURPOSE:Converting an intmat into an ideal of the corresponding monomials
770ASSUME: - The rows of M must correspond to Letterplace monomials
771@*      - basering has to be a Letterplace ring
772EXAMPLE: example iv2lpMat; shows examples
773"
774{list L = M;
775 checkAssumptions(0,L);
776 kill L;
777 ideal G; poly p;
778 int i; intvec I;
779 for (i = 1; i <= nrows(M); i++)
780  { I = M[i,1..ncols(M)];
781    p = iv2lp(I);
782    G[size(G)+1] = p;
783  }
784 return(G);
785}
786example
787{
788  "EXAMPLE:"; echo = 2;
789  ring r = 0,(x,y,z),dp;
790  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
791  setring R; // sets basering to Letterplace ring
792  intmat u[3][1] = 1,1,2; intmat v[1][3] = 2,1,3; intmat w[2][3] = 3,1,1,2,3,1;
793  // defines intmats of different size containing intvec representations of
794  // monomials as rows
795  iv2lpMat(u); // returns the monomials contained in u
796  iv2lpMat(v); // returns the monomials contained in v
797  iv2lpMat(w); // returns the monomials contained in w
798}
799
800proc lpId2ivLi(ideal G)
801"USAGE: lpId2ivLi(G); G an ideal
802RETURN: list
803PURPOSE:Transforming an ideal into the corresponding list of intvecs
804ASSUME: - basering has to be a Letterplace ring
805EXAMPLE: example lpId2ivLi; shows examples
806"
807{int i,j,k;
808 list M;
809 checkAssumptions(0,M);
810 for (i = 1; i <= size(G); i++) {M[i] = lp2iv(G[i]);}
811 return(M);
812}
813example
814{
815  "EXAMPLE:"; echo = 2;
816   ring r = 0,(x,y),dp;
817   def R = makeLetterplaceRing(5); // constructs a Letterplace ring
818   setring R; // sets basering to Letterplace ring
819   ideal L = x(1)*x(2),y(1)*y(2),x(1)*y(2)*x(3);
820   lpId2ivLi(L); // returns the corresponding intvecs as a list
821}
822
823proc lp2iv(poly p)
824"USAGE: lp2iv(p); p a poly
825RETURN: intvec
826PURPOSE:Transforming a monomial into the corresponding intvec
827ASSUME: - basering has to be a Letterplace ring
828NOTE:   - Assumptions will not be checked!
829EXAMPLE: example lp2iv; shows examples
830"
832 intvec I;
833 int i,j;
834 if (deg(p) > attrib(basering,"uptodeg")) {ERROR("Monomial exceeds degreebound");}
835 if (p == 1) {return(I);}
836 if (p == 0) {ERROR("Monomial is not allowed to equal zero");}
838 for ( i = 1; i <= attrib(basering,"lV"); i++) {if (lep[i] == 1) {I = i; break;}}
839 for (i = (attrib(basering,"lV")+1); i <= size(lep); i++)
840   {if (lep[i] == 1)
841    { j = (i mod attrib(basering,"lV"));
842      if (j == 0) {I = I,attrib(basering,"lV");}
843      else {I = I,j;}
844    }
845    else { if (lep[i] > 1) {ERROR("monomial has a not allowed multidegree");}}
846   }
847 if (I[1] == 0) {ERROR("monomial has a not allowed multidegree");}
848
849 return(I);
850}
851example
852{
853  "EXAMPLE:"; echo = 2;
854  ring r = 0,(x,y,z),dp;
855  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
856  setring R; // sets basering to Letterplace ring
857  poly p = x(1)*x(2)*z(3); poly q = y(1)*y(2)*x(3)*x(4);
858  poly w= z(1)*y(2)*x(3)*z(4)*z(5);
859  // p,q,w are some polynomials we want to transform into their
860  // intvec representation
861  lp2iv(p); lp2iv(q); lp2iv(w);
862}
863
864proc lp2ivId(ideal G)
865"USAGE: lp2ivId(G); G an ideal
866RETURN: list
867PURPOSE:Converting an ideal into an list of intmats,
868@*      the corresponding intvecs forming the rows
869ASSUME: - basering has to be a Letterplace ring
870EXAMPLE: example lp2ivId; shows examples
871"
873 intvec I; list L;
874 checkAssumptions(0,L);
875 int i,md;
876 for (i = 1; i <= size(G); i++) { if (md <= deg(G[i])) {md = deg(G[i]);}}
877 while (size(G) > 0)
878 {ideal Gt;
879  for (i = 1; i <= ncols(G); i++) {if (md == deg(G[i])) {Gt = Gt + G[i]; G[i] = 0;}}
880  if (size(Gt) > 0)
881  {G = simplify(G,2);
882   intmat M [size(Gt)][md];
883   for (i = 1; i <= size(Gt); i++) {M[i,1..md] = lp2iv(Gt[i]);}
884   L = insert(L,M);
885   kill M; kill Gt;
886   md = md - 1;
887  }
888  else {kill Gt; md = md - 1;}
889 }
890 return(L);
891}
892example
893{
894  "EXAMPLE:"; echo = 2;
895  ring r = 0,(x,y,z),dp;
896  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
897  setring R; // sets basering to Letterplace ring
898  poly p = x(1)*x(2)*z(3); poly q = y(1)*y(2)*x(3)*x(4);
899  poly w = z(1)*y(2)*x(3)*z(4);
900  // p,q,w are some polynomials we want to transform into their
901  // intvec representation
902  ideal G = p,q,w;
903  // define the ideal containing p,q and w
904  lp2ivId(G); // and return the list of intmats for this ideal
905}
906
907// -----------------main procedures----------------------
908
909proc ivDHilbert(list L, int n, list #)
910"USAGE: ivDHilbert(L,n[,degbound]); L a list of intmats, n an integer,
911@*      degbound an optional integer
912RETURN: list
913PURPOSE:Computing the K-dimension and the Hilbert series
914ASSUME: - basering is a Letterplace ring
915@*      - all rows of each intmat correspond to a Letterplace monomial
916@*      - if you specify a different degree bound degbound,
917@*        degbound <= attrib(basering,uptodeg) holds
918NOTE: - If L is the list returned, then L[1] is an integer corresponding to the
919@*      dimension, L[2] is an intvec which contains the coefficients of the
920@*      Hilbert series
921@*    - If degbound is set, there will be a degree bound added. By default there
922@*      is no degree bound
923@*    - n is the number of variables
924@*    - If I = L[2] is the intvec returned, then I[k] is the (k-1)-th coefficient of
925@*      the Hilbert series.
926@*    - If the K-dimension is known to be infinite, a degree bound is needed
927EXAMPLE: example ivDHilbert; shows examples
928"
929{int degbound = 0;
930 if (size(#) > 0){if (typeof(#[1])=="int"){if (#[1] > 0){degbound = #[1];}}}
931 checkAssumptions(degbound,L);
932 intvec H; int i,dimen;
933 H = ivHilbert(L,n,degbound);
934 for (i = 1; i <= size(H); i++){dimen = dimen + H[i];}
935 L = dimen,H;
936 return(L);
937}
938example
939{
940  "EXAMPLE:"; echo = 2;
941  ring r = 0,(x,y),dp;
942  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
943    R;
944  setring R; // sets basering to Letterplace ring
945  //some intmats, which contain monomials in intvec representation as rows
946  intmat I1 [2][2] = 1,1,2,2; intmat I2 [1][3]  = 1,2,1;
947  intmat J1 [1][2] =  1,1; intmat J2 [2][3] = 2,1,2,1,2,1;
948  print(I1);
949  print(I2);
950  print(J1);
951  print(J2);
952  list G = I1,I2; // ideal, which is already a Groebner basis
953  list I = J1,J2; // ideal, which is already a Groebner basis
954  //the procedure without a degree bound
955  ivDHilbert(G,2);
956  // the procedure with degree bound 5
957  ivDHilbert(I,2,5);
958}
959
960proc ivDHilbertSickle(list L, int n, list #)
961"USAGE: ivDHilbertSickle(L,n[,degbound]); L a list of intmats, n an integer,
962@*      degbound an optional integer
963RETURN: list
964PURPOSE:Computing K-dimension, Hilbert series and mistletoes
965ASSUME: - basering is a Letterplace ring.
966@*      - All rows of each intmat correspond to a Letterplace monomial.
967@*      - If you specify a different degree bound degbound,
968@*        degbound <= attrib(basering,uptodeg) holds.
969NOTE: - If L is the list returned, then L[1] is an intvec which contains the
970@*      coefficients of the Hilbert series, L[2] is an integer and L[3]
971@*      is a list, containing the mistletoes as intvecs.
972@*    - If degbound is set, a degree bound will be added. By default there
973@*      is no degree bound.
974@*    - n is the number of variables.
975@*    - If I = L[1] is the intvec returned, then I[k] is the (k-1)-th
976@*      coefficient of the Hilbert series.
977@*    - If the K-dimension is known to be infinite, a degree bound is needed
978EXAMPLE: example ivDHilbertSickle; shows examples
979"
980{int degbound = 0;
981 if (size(#) > 0){if (typeof(#[1])=="int"){if (#[1] > 0){degbound = #[1];}}}
982 checkAssumptions(degbound,L);
983 int i,dimen; list R;
984 R = ivSickleHil(L,n,degbound);
985 for (i = 1; i <= size(R[1]); i++){dimen = dimen + R[1][i];}
986 R[3] = R[2]; R[2] = dimen;
987 return(R);
988}
989example
990{
991  "EXAMPLE:"; echo = 2;
992  ring r = 0,(x,y),dp;
993  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
994  R;
995  setring R; // sets basering to Letterplace ring
996  //some intmats, which contain monomials in intvec representation as rows
997  intmat I1 [2][2] = 1,1,2,2; intmat I2 [1][3]  = 1,2,1;
998  intmat J1 [1][2] =  1,1; intmat J2 [2][3] = 2,1,2,1,2,1;
999  print(I1);
1000  print(I2);
1001  print(J1);
1002  print(J2);
1003  list G = I1,I2;// ideal, which is already a Groebner basis
1004  list I = J1,J2; // ideal, which is already a Groebner basis
1005  ivDHilbertSickle(G,2); // invokes the procedure without a degree bound
1006  ivDHilbertSickle(I,2,3); // invokes the procedure with degree bound 3
1007}
1008
1009proc ivDimCheck(list L, int n)
1010"USAGE: ivDimCheck(L,n); L a list of intmats, n an integer
1011RETURN: int, 0 if the dimension is finite, or 1 otherwise
1012PURPOSE:Decides, whether the K-dimension is finite or not
1013ASSUME: - basering is a Letterplace ring.
1014@*      - All rows of each intmat correspond to a Letterplace monomial.
1015NOTE:   - n is the number of variables.
1016EXAMPLE: example ivDimCheck; shows examples
1017"
1018{checkAssumptions(0,L);
1019 int i,r;
1020 intvec P,H;
1021 for (i = 1; i <= size(L); i++)
1022 {P[i] = ncols(L[i]);
1023  if (P[i] == 1) {if (isInMat(H,L[i]) > 0) {ERROR("Quotient algebra is trivial");}}
1024 }
1025 if (size(L) == 0) {ERROR("GB is empty, quotient algebra corresponds to free algebra");}
1026 kill H;
1027 intmat S; int sd,ld; intvec V;
1028 sd = P[1]; ld = P[1];
1029 for (i = 2; i <= size(P); i++)
1030 {if (P[i] < sd) {sd = P[i];}
1031  if (P[i] > ld) {ld = P[i];}
1032 }
1033 sd = (sd - 1); ld = ld - 1;
1034 if (ld == 0) { return(allVars(L,P,n));}
1035 if (sd == 0) { for (i = 1; i <= size(L); i++){if (ncols(L[i]) == 1){S = createStartMat1(n,L[i]); break;}}}
1036 else {S = createStartMat(sd,n);}
1037 module M;
1038 for (i = 1; i <= nrows(S); i++)
1039 {V = S[i,1..ncols(S)];
1040  if (findCycle(V,L,P,n,ld,M)) {r = 1; break;}
1041 }
1042 return(r);
1043}
1044example
1045{
1046  "EXAMPLE:"; echo = 2;
1047  ring r = 0,(x,y),dp;
1048  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
1049  R;
1050  setring R; // sets basering to Letterplace ring
1051  //some intmats, which contain monomials in intvec representation as rows
1052  intmat I1 [2][2] = 1,1,2,2; intmat I2 [1][3]  = 1,2,1;
1053  intmat J1 [1][2] =  1,1; intmat J2 [2][3] = 2,1,2,1,2,1;
1054  print(I1);
1055  print(I2);
1056  print(J1);
1057  print(J2);
1058  list G = I1,I2;// ideal, which is already a Groebner basis
1059  list I = J1,J2; // ideal, which is already a Groebner basis and which
1060  ivDimCheck(G,2); // invokes the procedure, factor is of finite K-dimension
1061  ivDimCheck(I,2); // invokes the procedure, factor is not of finite K-dimension
1062}
1063
1064proc ivHilbert(list L, int n, list #)
1065"USAGE: ivHilbert(L,n[,degbound]); L a list of intmats, n an integer,
1066@*      degbound an optional integer
1067RETURN: An intvec, containing the coefficients of the Hilbert series
1068PURPOSE:Computing the Hilbert series
1069ASSUME: - basering is a Letterplace ring.
1070@*      - all rows of each intmat correspond to a Letterplace monomial
1071@*      - if you specify a different degree bound degbound,
1072@*       degbound <= attrib(basering,uptodeg) holds.
1073NOTE: - If degbound is set, a degree bound  will be added. By default there
1074@*      is no degree bound.
1075@*    - n is the number of variables.
1076@*    - If I is returned, then I[k] is the (k-1)-th coefficient of the Hilbert
1077@*      series.
1078@*    - If the K-dimension is known to be infinite, a degree bound is needed
1079EXAMPLE: example ivHilbert; shows examples
1080"
1081{int degbound = 0;
1082 if (size(#) > 0) {if (typeof(#[1])=="int"){if (#[1] > 0) {degbound = #[1];}}}
1083 intvec P,H; int i;
1084 for (i = 1; i <= size(L); i++)
1085 {P[i] = ncols(L[i]);
1086  if (P[i] == 1) {if ( isInMat(H,L[i]) > 0) {ERROR("Quotient algebra is trivial");}}
1087 }
1088 if (size(L) == 0) {ERROR("GB is empty, quotient algebra corresponds to free algebra");}
1089 H[1] = 1;
1090 checkAssumptions(degbound,L);
1091 if (degbound == 0)
1092 {int sd;
1093  intmat S;
1094  sd = P[1];
1095  for (i = 2; i <= size(P); i++) {if (P[i] < sd) {sd = P[i];}}
1096  sd = (sd - 1);
1097  if (sd == 0) { for (i = 1; i <= size(L); i++){if (ncols(L[i]) == 1){S = createStartMat1(n,L[i]); break;}}}
1098  else {S = createStartMat(sd,n);}
1099  if (intvec(S) == 0) {return(H);}
1100  for (i = 1; i <= sd; i++) {H = H,(n^i);}
1101  for (i = 1; i <= nrows(S); i++)
1102  {intvec St = S[i,1..ncols(S)];
1103   H = findHCoeff(St,n,L,P,H);
1104   kill St;
1105  }
1106  return(H);
1107 }
1108 else
1109 {for (i = 1; i <= size(P); i++)
1110  {if (P[i] > degbound) {ERROR("degreebound is too small, GB contains elements of higher degree");}}
1111  int sd;
1112  intmat S;
1113  sd = P[1];
1114  for (i = 2; i <= size(P); i++) {if (P[i] < sd) {sd = P[i];}}
1115  sd = (sd - 1);
1116  if (sd == 0) { for (i = 1; i <= size(L); i++){if (ncols(L[i]) == 1){S = createStartMat1(n,L[i]); break;}}}
1117  else {S = createStartMat(sd,n);}
1118  if (intvec(S) == 0) {return(H);}
1119  for (i = 1; i <= sd; i++) {H = H,(n^i);}
1120  for (i = 1; i <= nrows(S); i++)
1121  {intvec St = S[i,1..ncols(S)];
1122   H = findHCoeff(St,n,L,P,H,degbound);
1123   kill St;
1124  }
1125  return(H);
1126 }
1127}
1128example
1129{
1130  "EXAMPLE:"; echo = 2;
1131  ring r = 0,(x,y),dp;
1132  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
1133  R;
1134  setring R; // sets basering to Letterplace ring
1135  //some intmats, which contain monomials in intvec representation as rows
1136  intmat I1 [2][2] = 1,1,2,2; intmat I2 [1][3]  = 1,2,1;
1137  intmat J1 [1][2] =  1,1; intmat J2 [2][3] = 2,1,2,1,2,1;
1138  print(I1);
1139  print(I2);
1140  print(J1);
1141  print(J2);
1142  list G = I1,I2; // ideal, which is already a Groebner basis
1143  list I = J1,J2; // ideal, which is already a Groebner basis
1144  ivHilbert(G,2); // invokes the procedure without any degree bound
1145  ivHilbert(I,2,5); // invokes the procedure with degree bound 5
1146}
1147
1148
1149proc ivKDim(list L, int n, list #)
1150"USAGE: ivKDim(L,n[,degbound]); L a list of intmats,
1151@*      n an integer, degbound an optional integer
1152RETURN: An integer, the K-dimension of A/<L>
1153PURPOSE:Computing the K-dimension of A/<L>
1154ASSUME: - basering is a Letterplace ring.
1155@*      - all rows of each intmat correspond to a Letterplace monomial
1156@*      - if you specify a different degree bound degbound,
1157@*        degbound <= attrib(basering,uptodeg) holds.
1158NOTE: - If degbound is set, a degree bound will be added. By default there
1159@*      is no degree bound.
1160@*    - n is the number of variables.
1161@*    - If the K-dimension is known to be infinite, a degree bound is needed
1162EXAMPLE: example ivKDim; shows examples
1163"
1164{int degbound = 0;
1165 if (size(#) > 0) {if (typeof(#[1])=="int"){if (#[1] > 0) {degbound = #[1];}}}
1166 intvec P,H; int i;
1167 for (i = 1; i <= size(L); i++)
1168 {P[i] = ncols(L[i]);
1169  if (P[i] == 1) {if ( isInMat(H,L[i]) > 0) {ERROR("Quotient algebra is trivial");}}
1170 }
1171 if (size(L) == 0) {ERROR("GB is empty, quotient algebra corresponds to free algebra");}
1172 kill H;
1173 checkAssumptions(degbound,L);
1174 if (degbound == 0)
1175 {int sd; int dimen = 1;
1176  intmat S;
1177  sd = P[1];
1178  for (i = 2; i <= size(P); i++) {if (P[i] < sd) {sd = P[i];}}
1179  sd = (sd - 1);
1180  if (sd == 0) { for (i = 1; i <= size(L); i++){if (ncols(L[i]) == 1){S = createStartMat1(n,L[i]); break;}}}
1181  else {S = createStartMat(sd,n);}
1182  if (intvec(S) == 0) {return(dimen);}
1183  for (i = 1; i <= sd; i++) {dimen = dimen +(n^i);}
1184  for (i = 1; i <= nrows(S); i++)
1185  {intvec St = S[i,1..ncols(S)];
1186   dimen = dimen + findDimen(St,n,L,P);
1187   kill St;
1188  }
1189  return(dimen);
1190 }
1191 else
1192 {for (i = 1; i <= size(P); i++)
1193  {if (P[i] > degbound) {ERROR("degreebound is too small, GB contains elements of higher degree");}}
1194  int sd; int dimen = 1;
1195  intmat S;
1196  sd = P[1];
1197  for (i = 2; i <= size(P); i++) {if (P[i] < sd) {sd = P[i];}}
1198  sd = (sd - 1);
1199  if (sd == 0) { for (i = 1; i <= size(L); i++){if (ncols(L[i]) == 1){S = createStartMat1(n,L[i]); break;}}}
1200  else {S = createStartMat(sd,n);}
1201  if (intvec(S) == 0) {return(dimen);}
1202  for (i = 1; i <= sd; i++) {dimen = dimen +(n^i);}
1203  for (i = 1; i <= nrows(S); i++)
1204  {intvec St = S[i,1..ncols(S)];
1205   dimen = dimen + findDimen(St,n,L,P, degbound);
1206   kill St;
1207  }
1208  return(dimen);
1209 }
1210}
1211example
1212{
1213  "EXAMPLE:"; echo = 2;
1214  ring r = 0,(x,y),dp;
1215  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
1216  R;
1217  setring R; // sets basering to Letterplace ring
1218  //some intmats, which contain monomials in intvec representation as rows
1219  intmat I1 [2][2] = 1,1,2,2; intmat I2 [1][3]  = 1,2,1;
1220  intmat J1 [1][2] =  1,1; intmat J2 [2][3] = 2,1,2,1,2,1;
1221  print(I1);
1222  print(I2);
1223  print(J1);
1224  print(J2);
1225  list G = I1,I2; // ideal, which is already a Groebner basis
1226  list I = J1,J2; // ideal, which is already a Groebner basis
1227  ivKDim(G,2); // invokes the procedure without any degree bound
1228  ivKDim(I,2,5); // invokes the procedure with degree bound 5
1229}
1230
1231proc ivMis2Dim(list M)
1232"USAGE: ivMis2Dim(M); M a list of intvecs
1233RETURN: An integer, the K-dimension of the given algebra
1234PURPOSE:Computing the K-dimension out of given mistletoes
1235ASSUME: - The mistletoes have to be ordered lexicographically -> OrdMisLex.
1236@*        Otherwise the returned value may differ from the K-dimension.
1237@*      - basering is a Letterplace ring.
1238EXAMPLE: example ivMis2Dim; shows examples
1239"
1240{checkAssumptions(0,M);
1241 intvec L;
1242 if (size(M) == 0){ERROR("There are no mistletoes, so it appears your dimension is infinite!");}
1243 if (isInList(L,M) > 0) {print("1 is a mistletoe, therefore dim = 1"); return(1);}
1244 int i,j,d,s;
1245 j = 1;
1246 d = 1 + size(M[1]);
1247 for (i = 1; i < size(M); i++)
1248  {s = size(M[i]); if (s > size(M[i+1])){s = size(M[i+1]);}
1249   while ((M[i][j] == M[i+1][j]) && (j <= s)){j = j + 1;}
1250   d = d + size(M[i+1])- j + 1;
1251  }
1252 return(d);
1253}
1254example
1255{
1256  "EXAMPLE:"; echo = 2;
1257   ring r = 0,(x,y),dp;
1258   def R = makeLetterplaceRing(5); // constructs a Letterplace ring
1259   R;
1260   setring R; // sets basering to Letterplace ring
1261   intvec i1 = 1,2; intvec i2 = 2,1,2;
1262   // the mistletoes are xy and yxy, which are already ordered lexicographically
1263   list L = i1,i2;
1264   ivMis2Dim(L); // returns the dimension of the factor algebra
1265}
1266
1267proc ivOrdMisLex(list M)
1268"USAGE: ivOrdMisLex(M); M a list of intvecs
1269RETURN: A list, containing the ordered intvecs of M
1270PURPOSE:Orders a given set of mistletoes lexicographically
1271ASSUME: - basering is a Letterplace ring.
1272        - intvecs correspond to monomials
1273NOTE:   - This is preprocessing, it's not needed if the mistletoes are returned
1274@*        from the sickle algorithm.
1275@*      - Each entry of the list returned is an intvec.
1276EXAMPLE: example ivOrdMisLex; shows examples
1277"
1278{checkAssumptions(0,M);
1279 return(sort(M)[1]);
1280}
1281example
1282{
1283  "EXAMPLE:"; echo = 2;
1284   ring r = 0,(x,y),dp;
1285   def R = makeLetterplaceRing(5); // constructs a Letterplace ring
1286   setring R; // sets basering to Letterplace ring
1287   intvec i1 = 1,2,1; intvec i2 = 2,2,1; intvec i3 = 1,1; intvec i4 = 2,1,1,1;
1288   // the corresponding monomials are xyx,y^2x,x^2,yx^3
1289   list M = i1,i2,i3,i4;
1290   M;
1291   ivOrdMisLex(M);// orders the list of monomials
1292}
1293
1294proc ivSickle(list L, int n, list #)
1295"USAGE: ivSickle(L,n,[degbound]); L a list of intmats, n an int, degbound an
1296@*      optional integer
1297RETURN: A list, containing intvecs, the mistletoes of A/<L>
1298PURPOSE:Computing the mistletoes for a given Groebner basis L
1299ASSUME: - basering is a Letterplace ring.
1300@*      - all rows of each intmat correspond to a Letterplace monomial
1301@*      - if you specify a different degree bound degbound,
1302@*        degbound <= attrib(basering,uptodeg) holds.
1303NOTE: - If degbound is set, a degree bound will be added. By default there
1304@*      is no degree bound.
1305@*    - n is the number of variables.
1306@*    - If the K-dimension is known to be infinite, a degree bound is needed
1307EXAMPLE: example ivSickle; shows examples
1308"
1309{list M;
1310 int degbound = 0;
1311 if (size(#) > 0){if (typeof(#[1])=="int"){if (#[1] > 0){degbound = #[1];}}}
1312 int i;
1313 intvec P,H;
1314 for (i = 1; i <= size(L); i++)
1315 {P[i] = ncols(L[i]);
1316  if (P[i] == 1) {if (isInMat(H,L[i]) > 0) {ERROR("Quotient algebra is trivial");}}
1317 }
1318 if (size(L) == 0) {ERROR("GB is empty, quotient algebra corresponds to free algebra");}
1319 kill H;
1320 checkAssumptions(degbound,L);
1321 if (degbound == 0)
1322 {intmat S; int sd;
1323  sd = P[1];
1324  for (i = 2; i <= size(P); i++) {if (P[i] < sd) {sd = P[i];}}
1325  sd = (sd - 1);
1326  if (sd == 0) { for (i = 1; i <= size(L); i++){if (ncols(L[i]) == 1){S = createStartMat1(n,L[i]); break;}}}
1327  else {S = createStartMat(sd,n);}
1328  if (intvec(S) == 0) {return(list (intvec(0)));}
1329  for (i = 1; i <= nrows(S); i++)
1330  {intvec St = S[i,1..ncols(S)];
1331   M = M + findmistletoes(St,n,L,P);
1332   kill St;
1333  }
1334  return(M);
1335 }
1336 else
1337 {for (i = 1; i <= size(P); i++)
1338  {if (P[i] > degbound) {ERROR("degreebound is too small, GB contains elements of higher degree");}}
1339  intmat S; int sd;
1340  sd = P[1];
1341  for (i = 2; i <= size(P); i++) {if (P[i] < sd) {sd = P[i];}}
1342  sd = (sd - 1);
1343  if (sd == 0) { for (i = 1; i <= size(L); i++){if (ncols(L[i]) == 1){S = createStartMat1(n,L[i]); break;}}}
1344  else {S = createStartMat(sd,n);}
1345  if (intvec(S) == 0) {return(list (intvec(0)));}
1346  for (i = 1; i <= nrows(S); i++)
1347  {intvec St = S[i,1..ncols(S)];
1348   M = M + findmistletoes(St,n,L,P,degbound);
1349   kill St;
1350  }
1351  return(M);
1352 }
1353}
1354example
1355{
1356  "EXAMPLE:"; echo = 2;
1357  ring r = 0,(x,y),dp;
1358  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
1359  setring R; // sets basering to Letterplace ring
1360  //some intmats, which contain monomials in intvec representation as rows
1361  intmat I1 [2][2] = 1,1,2,2; intmat I2 [1][3]  = 1,2,1;
1362  intmat J1 [1][2] =  1,1; intmat J2 [2][3] = 2,1,2,1,2,1;
1363  print(I1);
1364  print(I2);
1365  print(J1);
1366  print(J2);
1367  list G = I1,I2; // ideal, which is already a Groebner basis
1368  list I =  J1,J2; // ideal, which is already a Groebner basis
1369  ivSickle(G,2); // invokes the procedure without any degree bound
1370  ivSickle(I,2,5); // invokes the procedure with degree bound 5
1371}
1372
1373proc ivSickleDim(list L, int n, list #)
1374"USAGE: ivSickleDim(L,n[,degbound]); L a list of intmats, n an integer, degbound
1375@*      an optional integer
1376RETURN: A list
1377PURPOSE:Computing mistletoes and the K-dimension
1378ASSUME: - basering is a Letterplace ring.
1379@*      - all rows of each intmat correspond to a Letterplace monomial
1380@*      - if you specify a different degree bound degbound,
1381@*        degbound <= attrib(basering,uptodeg) holds.
1382NOTE: - If L is the list returned, then L[1] is an integer, L[2] is a list,
1383@*      containing the mistletoes as intvecs.
1384@*    - If degbound is set, a degree bound will be added. By default there
1385@*      is no degree bound.
1386@*    - n is the number of variables.
1387@*    - If the K-dimension is known to be infinite, a degree bound is needed
1388EXAMPLE: example ivSickleDim; shows examples
1389"
1390{list M;
1391 int degbound = 0;
1392 if (size(#) > 0){if (typeof(#[1])=="int"){if (#[1] > 0){degbound = #[1];}}}
1393 int i,dimen; list R;
1394 intvec P,H;
1395 for (i = 1; i <= size(L); i++)
1396 {P[i] = ncols(L[i]);
1397  if (P[i] == 1) {if (isInMat(H,L[i]) > 0) {ERROR("Quotient algebra is trivial, dimension equals zero");}}
1398 }
1399 if (size(L) == 0) {ERROR("GB is empty, quotient algebra corresponds to free algebra");}
1400 kill H;
1401 checkAssumptions(degbound,L);
1402 if (degbound == 0)
1403 {int sd; dimen = 1;
1404  intmat S;
1405  sd = P[1];
1406  for (i = 2; i <= size(P); i++) {if (P[i] < sd) {sd = P[i];}}
1407  sd = (sd - 1);
1408  if (sd == 0) { for (i = 1; i <= size(L); i++){if (ncols(L[i]) == 1){S = createStartMat1(n,L[i]); break;}}}
1409  else {S = createStartMat(sd,n);}
1410  if (intvec(S) == 0) {return(list(dimen,list(intvec(0))));}
1411  for (i = 1; i <= sd; i++) {dimen = dimen +(n^i);}
1412  R[1] = dimen;
1413  for (i = 1; i <= nrows(S); i++)
1414  {intvec St = S[i,1..ncols(S)];
1415   R = findMisDim(St,n,L,P,R);
1416   kill St;
1417  }
1418  return(R);
1419 }
1420 else
1421 {for (i = 1; i <= size(P); i++)
1422  {if (P[i] > degbound) {ERROR("degreebound is too small, GB contains elements of higher degree");}}
1423  int sd; dimen = 1;
1424  intmat S;
1425  sd = P[1];
1426  for (i = 2; i <= size(P); i++) {if (P[i] < sd) {sd = P[i];}}
1427  sd = (sd - 1);
1428  if (sd == 0) { for (i = 1; i <= size(L); i++){if (ncols(L[i]) == 1){S = createStartMat1(n,L[i]); break;}}}
1429  else {S = createStartMat(sd,n);}
1430  if (intvec(S) == 0) {return(list(dimen,list(intvec(0))));}
1431  for (i = 1; i <= sd; i++) {dimen = dimen +(n^i);}
1432  R[1] = dimen;
1433  for (i = 1; i <= nrows(S); i++)
1434  {intvec St = S[i,1..ncols(S)];
1435   R = findMisDim(St,n,L,P,R,degbound);
1436   kill St;
1437  }
1438  return(R);
1439 }
1440}
1441example
1442{
1443  "EXAMPLE:"; echo = 2;
1444  ring r = 0,(x,y),dp;
1445  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
1446  setring R; // sets basering to Letterplace ring
1447  //some intmats, which contain monomials in intvec representation as rows
1448  intmat I1 [2][2] = 1,1,2,2; intmat I2 [1][3]  = 1,2,1;
1449  intmat J1 [1][2] =  1,1; intmat J2 [2][3] = 2,1,2,1,2,1;
1450  print(I1);
1451  print(I2);
1452  print(J1);
1453  print(J2);
1454  list G = I1,I2;// ideal, which is already a Groebner basis
1455  list I =  J1,J2; // ideal, which is already a Groebner basis
1456  ivSickleDim(G,2); // invokes the procedure without any degree bound
1457  ivSickleDim(I,2,5); // invokes the procedure with degree bound 5
1458}
1459
1460proc ivSickleHil(list L, int n, list #)
1461"USAGE:ivSickleHil(L,n[,degbound]); L a list of intmats, n an integer,
1462@*     degbound an optional integer
1463RETURN: A list
1464PURPOSE:Computing the mistletoes and the Hilbert series
1465ASSUME: - basering is a Letterplace ring.
1466@*      - all rows of each intmat correspond to a Letterplace monomial
1467@*      - if you specify a different degree bound degbound,
1468@*        degbound <= attrib(basering,uptodeg) holds.
1469NOTE: - If L is the list returned, then L[1] is an intvec, L[2] is a list,
1470@*      containing the mistletoes as intvecs.
1471@*    - If degbound is set, a degree bound will be added. By default there
1472@*      is no degree bound.
1473@*    - n is the number of variables.
1474@*    - If I = L[1] is the intvec returned, then I[k] is the (k-1)-th
1475@*      coefficient of the Hilbert series.
1476@*    - If the K-dimension is known to be infinite, a degree bound is needed
1477EXAMPLE: example ivSickleHil; shows examples
1478"
1479{int degbound = 0;
1480 if (size(#) > 0) {if (typeof(#[1])=="int"){if (#[1] > 0) {degbound = #[1];}}}
1481 intvec P,H; int i; list R;
1482 for (i = 1; i <= size(L); i++)
1483 {P[i] = ncols(L[i]);
1484  if (P[i] == 1) {if ( isInMat(H,L[i]) > 0) {ERROR("Quotient algebra is trivial");}}
1485 }
1486 if (size(L) == 0) {ERROR("GB is empty, quotient algebra corresponds to free algebra");}
1487 H[1] = 1;
1488 checkAssumptions(degbound,L);
1489 if (degbound == 0)
1490 {int sd;
1491  intmat S;
1492  sd = P[1];
1493  for (i = 2; i <= size(P); i++) {if (P[i] < sd) {sd = P[i];}}
1494  sd = (sd - 1);
1495  if (sd == 0) { for (i = 1; i <= size(L); i++){if (ncols(L[i]) == 1){S = createStartMat1(n,L[i]); break;}}}
1496  else {S = createStartMat(sd,n);}
1497  if (intvec(S) == 0) {return(list(H,list(intvec (0))));}
1498  for (i = 1; i <= sd; i++) {H = H,(n^i);}
1499  R[1] = H; kill H;
1500  for (i = 1; i <= nrows(S); i++)
1501  {intvec St = S[i,1..ncols(S)];
1502   R = findHCoeffMis(St,n,L,P,R);
1503   kill St;
1504  }
1505  return(R);
1506 }
1507 else
1508 {for (i = 1; i <= size(P); i++)
1509  {if (P[i] > degbound) {ERROR("degreebound is too small, GB contains elements of higher degree");}}
1510  int sd;
1511  intmat S;
1512  sd = P[1];
1513  for (i = 2; i <= size(P); i++) {if (P[i] < sd) {sd = P[i];}}
1514  sd = (sd - 1);
1515  if (sd == 0) { for (i = 1; i <= size(L); i++){if (ncols(L[i]) == 1){S = createStartMat1(n,L[i]); break;}}}
1516  else {S = createStartMat(sd,n);}
1517  if (intvec(S) == 0) {return(list(H,list(intvec(0))));}
1518  for (i = 1; i <= sd; i++) {H = H,(n^i);}
1519  R[1] = H; kill H;
1520  for (i = 1; i <= nrows(S); i++)
1521  {intvec St = S[i,1..ncols(S)];
1522   R = findHCoeffMis(St,n,L,P,R,degbound);
1523   kill St;
1524  }
1525  return(R);
1526 }
1527}
1528example
1529{
1530  "EXAMPLE:"; echo = 2;
1531  ring r = 0,(x,y),dp;
1532  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
1533  setring R; // sets basering to Letterplace ring
1534  //some intmats, which contain monomials in intvec representation as rows
1535  intmat I1[2][2] = 1,1,2,2; intmat I2[1][3]  = 1,2,1;
1536  intmat J1[1][2] =  1,1; intmat J2[2][3] = 2,1,2,1,2,1;
1537  print(I1);
1538  print(I2);
1539  print(J1);
1540  print(J2);
1541  list G = I1,I2;// ideal, which is already a Groebner basis
1542  list I =  J1,J2; // ideal, which is already a Groebner basis
1543  ivSickleHil(G,2); // invokes the procedure without any degree bound
1544  ivSickleHil(I,2,5); // invokes the procedure with degree bound 5
1545}
1546
1547proc lpDHilbert(ideal G, list #)
1548"USAGE: lpDHilbert(G[,degbound,n]); G an ideal, degbound, n optional integers
1549RETURN: A list
1550PURPOSE:Computing K-dimension and Hilbert series, starting with a lp-ideal
1551ASSUME: - basering is a Letterplace ring.
1552@*      - if you specify a different degree bound degbound,
1553@*        degbound <= attrib(basering,uptodeg) holds.
1554NOTE: - If L is the list returned, then L[1] is an integer, L[2] is an intvec.
1555@*    - If degbound is set, there will be a degree bound added. 0 means no
1556@*      degree bound. Default: attrib(basering,uptodeg).
1557@*    - n can be set to a different number of variables.
1558@*      Default: n = attrib(basering, lV).
1559@*    - If I = L[2] is the intvec returned, then I[k] is the (k-1)-th
1560@*      coefficient of the Hilbert series.
1561@*    - If the K-dimension is known to be infinite, a degree bound is needed
1562EXAMPLE: example lpDHilbert; shows examples
1563"
1564{int degbound = attrib(basering,"uptodeg");int n = attrib(basering, "lV");
1565 if (size(#) > 0){if (typeof(#[1])=="int"){if (#[1] >= 0){degbound = #[1];}}}
1566 if (size(#) > 1){if (typeof(#[1])=="int"){if (#[2] > 0){n = #[2];}}}
1567 list L;
1569 return(ivDHilbert(L,n,degbound));
1570}
1571example
1572{
1573  "EXAMPLE:"; echo = 2;
1574  ring r = 0,(x,y),dp;
1575  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
1576  setring R; // sets basering to Letterplace ring
1577  ideal G = x(1)*x(2), y(1)*y(2),x(1)*y(2)*x(3); // ideal G contains a
1578  //Groebner basis
1579  lpDHilbert(G,5,2); // invokes procedure with degree bound 5 and 2 variables
1580  // note that the optional parameters are not necessary, due to the finiteness
1581  // of the K-dimension of the factor algebra
1582  lpDHilbert(G); // procedure with ring parameters
1583  lpDHilbert(G,0); // procedure without degreebound
1584}
1585
1586proc lpDHilbertSickle(ideal G, list #)
1587"USAGE: lpDHilbertSickle(G[,degbound,n]); G an ideal, degbound, n optional
1588@*      integers
1589RETURN: A list
1590PURPOSE:Computing K-dimension, Hilbert series and mistletoes at once
1591ASSUME: - basering is a Letterplace ring.
1592@*      - if you specify a different degree bound degbound,
1593@*        degbound <= attrib(basering,uptodeg) holds.
1594NOTE: - If L is the list returned, then L[1] is an intvec, the Hilbert series,
1595@*      L[2] is an integer, the K-dimension and L[3] is an ideal, the mistletoes
1596@*    - If degbound is set, there will be a degree bound added. 0 means no
1597@*      degree bound. Default: attrib(basering,uptodeg).
1598@*    - n can be set to a different number of variables.
1599@*      Default: n = attrib(basering, lV).
1600@*    - If I = L[1] is the intvec returned, then I[k] is the (k-1)-th
1601@*      coefficient of the Hilbert series.
1602@*    - If the K-dimension is known to be infinite, a degree bound is needed
1603EXAMPLE: example lpDHilbertSickle; shows examples
1604"
1605{int degbound = attrib(basering,"uptodeg");int n = attrib(basering, "lV");
1606 if (size(#) > 0){if (typeof(#[1])=="int"){if (#[1] >= 0){degbound = #[1];}}}
1607 if (size(#) > 1){if (typeof(#[1])=="int"){if (#[2] > 0){n = #[2];}}}
1608 list L;
1610 L = ivDHilbertSickle(L,n,degbound);
1611 L[3] =  ivL2lpI(L[3]);
1612 return(L);
1613}
1614example
1615{
1616  "EXAMPLE:"; echo = 2;
1617  ring r = 0,(x,y),dp;
1618  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
1619  setring R; // sets basering to Letterplace ring
1620  ideal G = x(1)*x(2), y(1)*y(2),x(1)*y(2)*x(3); // ideal G contains a
1621  //Groebner basis
1622  lpDHilbertSickle(G,5,2); //invokes procedure with degree bound 5 and 2 variables
1623  // note that the optional parameters are not necessary, due to the finiteness
1624  // of the K-dimension of the factor algebra
1625  lpDHilbert(G); // procedure with ring parameters
1626  lpDHilbert(G,0); // procedure without degreebound
1627}
1628
1629proc lpHilbert(ideal G, list #)
1630"USAGE: lpHilbert(G[,degbound,n]); G an ideal, degbound, n optional integers
1631RETURN: An intvec, containing the coefficients of the Hilbert series
1632PURPOSE:Computing the Hilbert series
1633ASSUME: - basering is a Letterplace ring.
1634@*      - if you specify a different degree bound degbound,
1635@*        degbound <= attrib(basering,uptodeg) holds.
1636NOTE: - If degbound is set, there will be a degree bound added. 0 means no
1637@*      degree bound. Default: attrib(basering,uptodeg).
1638@*    - n is the number of variables, which can be set to a different number.
1639@*      Default: attrib(basering, lV).
1640@*    - If I is returned, then I[k] is the (k-1)-th coefficient of the Hilbert
1641@*      series.
1642@*    - If the K-dimension is known to be infinite, a degree bound is needed
1643EXAMPLE: example lpHilbert; shows examples
1644"
1645{int degbound = attrib(basering,"uptodeg");int n = attrib(basering, "lV");
1646 if (size(#) > 0){if (typeof(#[1])=="int"){if (#[1] >= 0){degbound = #[1];}}}
1647 if (size(#) > 1){if (typeof(#[1])=="int"){if (#[2] > 0){n = #[2];}}}
1648 list L;
1650 return(ivHilbert(L,n,degbound));
1651}
1652example
1653{
1654  "EXAMPLE:"; echo = 2;
1655  ring r = 0,(x,y),dp;
1656  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
1657  setring R; // sets basering to Letterplace ring
1658  ideal G = x(1)*x(2), y(1)*y(2),x(1)*y(2)*x(3); // ideal G contains a
1659  //Groebner basis
1660  lpHilbert(G,5,2); // invokes procedure with degree bound 5 and 2 variables
1661  // note that the optional parameters are not necessary, due to the finiteness
1662  // of the K-dimension of the factor algebra
1663  lpDHilbert(G); // procedure with ring parameters
1664  lpDHilbert(G,0); // procedure without degreebound
1665}
1666
1667proc lpDimCheck(ideal G)
1668"USAGE: lpDimCheck(G);
1669RETURN: 1, if K-dimension of the factor algebra is infinite, 0 otherwise
1670PURPOSE:Checking a factor algebra for finiteness of the K-dimension
1671ASSUME: - basering is a Letterplace ring.
1672EXAMPLE: example lpDimCheck; shows examples
1673"
1674{int n = attrib(basering,"lV");
1675 list L;
1676 ideal R;
1678 L = lp2ivId(R);
1679 return(ivDimCheck(L,n));
1680}
1681example
1682{
1683  "EXAMPLE:"; echo = 2;
1684  ring r = 0,(x,y),dp;
1685  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
1686  setring R; // sets basering to Letterplace ring
1687  ideal G = x(1)*x(2), y(1)*y(2),x(1)*y(2)*x(3);
1688  // Groebner basis
1689  ideal I = x(1)*x(2), y(1)*x(2)*y(3), x(1)*y(2)*x(3);
1690  // Groebner basis
1691  lpDimCheck(G); // invokes procedure, factor algebra is of finite K-dimension
1692  lpDimCheck(I); // invokes procedure, factor algebra is of infinite Kdimension
1693}
1694
1695proc lpKDim(ideal G, list #)
1696"USAGE: lpKDim(G[,degbound, n]); G an ideal, degbound, n optional integers
1697RETURN: An integer, the K-dimension of the factor algebra
1698PURPOSE:Computing the K-dimension of a factor algebra, given via an ideal
1699ASSUME: - basering is a Letterplace ring
1700@*      - if you specify a different degree bound degbound,
1701@*        degbound <= attrib(basering,uptodeg) holds.
1702NOTE: - If degbound is set, there will be a degree bound added. 0 means no
1703@*      degree bound. Default: attrib(basering, uptodeg).
1704@*    - n is the number of variables, which can be set to a different number.
1705@*      Default: attrib(basering, lV).
1706@*    - If the K-dimension is known to be infinite, a degree bound is needed
1707EXAMPLE: example lpKDim; shows examples
1708"
1709{int degbound = attrib(basering, "uptodeg");int n = attrib(basering, "lV");
1710 if (size(#) > 0){if (typeof(#[1])=="int"){if (#[1] >= 0){degbound = #[1];}}}
1711 if (size(#) > 1){if (typeof(#[1])=="int"){if (#[2] > 0){n = #[2];}}}
1712 list L;
1714 return(ivKDim(L,n,degbound));
1715}
1716example
1717{
1718  "EXAMPLE:"; echo = 2;
1719  ring r = 0,(x,y),dp;
1720  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
1721  setring R; // sets basering to Letterplace ring
1722  ideal G = x(1)*x(2), y(1)*y(2),x(1)*y(2)*x(3);
1723  // ideal G contains a Groebner basis
1724  lpKDim(G); //procedure invoked with ring parameters
1725  // the factor algebra is finite, so the degree bound given by the Letterplace
1726  // ring is not necessary
1727  lpKDim(G,0); // procedure without any degree bound
1728}
1729
1730proc lpMis2Dim(ideal M)
1731"USAGE: lpMis2Dim(M); M an ideal
1732RETURN: An integer, the K-dimension of the factor algebra
1733PURPOSE:Computing the K-dimension out of given mistletoes
1734ASSUME: - basering is a Letterplace ring.
1735@*      - M contains only monomials
1736NOTE:   - The mistletoes have to be ordered lexicographically -> OrdMisLex.
1737EXAMPLE: example lpMis2Dim; shows examples
1738"
1739{list L;
1740 L = lpId2ivLi(M);
1741 return(ivMis2Dim(L));
1742}
1743example
1744{
1745  "EXAMPLE:"; echo = 2;
1746   ring r = 0,(x,y),dp;
1747   def R = makeLetterplaceRing(5); // constructs a Letterplace ring
1748  setring R; // sets basering to Letterplace ring
1749   ideal L = x(1)*y(2),y(1)*x(2)*y(3);
1750   // ideal containing the mistletoes
1751   lpMis2Dim(L); // returns the K-dimension of the factor algebra
1752}
1753
1754proc lpOrdMisLex(ideal M)
1755"USAGE: lpOrdMisLex(M); M an ideal of mistletoes
1756RETURN: An ideal, containing the mistletoes, ordered lexicographically
1757PURPOSE:A given set of mistletoes is ordered lexicographically
1758ASSUME: - basering is a Letterplace ring.
1759NOTE:   This is preprocessing, it is not needed if the mistletoes are returned
1760@*      from the sickle algorithm.
1761EXAMPLE: example lpOrdMisLex; shows examples
1762"
1763{return(ivL2lpI(sort(lpId2ivLi(M))[1]));}
1764example
1765{
1766  "EXAMPLE:"; echo = 2;
1767   ring r = 0,(x,y),dp;
1768   def R = makeLetterplaceRing(5); // constructs a Letterplace ring
1769   setring R; // sets basering to Letterplace ring
1770   ideal M = x(1)*y(2)*x(3), y(1)*y(2)*x(3), x(1)*x(2), y(1)*x(2)*x(3)*x(4);
1771   // some monomials
1772   lpOrdMisLex(M); // orders the monomials lexicographically
1773}
1774
1775proc lpSickle(ideal G,  list #)
1776"USAGE: lpSickle(G[,degbound,n]); G an ideal, degbound, n optional integers
1777RETURN: An ideal
1778PURPOSE:Computing the mistletoes of K[X]/<G>
1779ASSUME: - basering is a Letterplace ring.
1780@*      - if you specify a different degree bound degbound,
1781@*        degbound <= attrib(basering,uptodeg) holds.
1782NOTE: - If degbound is set, there will be a degree bound added. 0 means no
1783@*      degree bound. Default: attrib(basering,uptodeg).
1784@*    - n is the number of variables, which can be set to a different number.
1785@*      Default: attrib(basering, lV).
1786@*    - If the K-dimension is known to be infinite, a degree bound is needed
1787EXAMPLE: example lpSickle; shows examples
1788"
1789{int degbound = attrib(basering,"uptodeg"); int n = attrib(basering, "lV");
1790 if (size(#) > 0){if (typeof(#[1])=="int"){if (#[1] >= 0){degbound = #[1];}}}
1791 if (size(#) > 1){if (typeof(#[1])=="int"){if (#[2] > 0){n = #[2];}}}
1792 list L; ideal R;
1794 L = lp2ivId(R);
1795 L = ivSickle(L,n,degbound);
1796 R = ivL2lpI(L);
1797 return(R);
1798}
1799example
1800{
1801  "EXAMPLE:"; echo = 2;
1802  ring r = 0,(x,y),dp;
1803  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
1804  setring R; // sets basering to Letterplace ring
1805  ideal G = x(1)*x(2), y(1)*y(2),x(1)*y(2)*x(3); // ideal G contains a
1806  //Groebner basis
1807  lpSickle(G); //invokes the procedure with ring parameters
1808  // the factor algebra is finite, so the degree bound given by the Letterplace
1809  // ring is not necessary
1810  lpSickle(G,0); // procedure without any degree bound
1811}
1812
1813proc lpSickleDim(ideal G, list #)
1814"USAGE: lpSickleDim(G[,degbound,n]); G an ideal, degbound, n optional integers
1815RETURN: A list
1816PURPOSE:Computing the K-dimension and the mistletoes
1817ASSUME: - basering is a Letterplace ring.
1818@*      - if you specify a different degree bound degbound,
1819@*        degbound <= attrib(basering,uptodeg) holds.
1820NOTE: - If L is the list returned, then L[1] is an integer, the K-dimension,
1821@*      L[2] is an ideal, the mistletoes.
1822@*    - If degbound is set, there will be a degree bound added. 0 means no
1823@*      degree bound. Default: attrib(basering,uptodeg).
1824@*    - n is the number of variables, which can be set to a different number.
1825@*      Default: attrib(basering, lV).
1826@*    - If the K-dimension is known to be infinite, a degree bound is needed
1827EXAMPLE: example lpSickleDim; shows examples
1828"
1829{int degbound = attrib(basering,"uptodeg");int n = attrib(basering, "lV");
1830 if (size(#) > 0){if (typeof(#[1])=="int"){if (#[1] >= 0){degbound = #[1];}}}
1831 if (size(#) > 1){if (typeof(#[1])=="int"){if (#[2] > 0){n = #[2];}}}
1832 list L;
1834 L = ivSickleDim(L,n,degbound);
1835 L[2] = ivL2lpI(L[2]);
1836 return(L);
1837}
1838example
1839{
1840  "EXAMPLE:"; echo = 2;
1841  ring r = 0,(x,y),dp;
1842  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
1843  setring R; // sets basering to Letterplace ring
1844  ideal G = x(1)*x(2), y(1)*y(2),x(1)*y(2)*x(3); // ideal G contains a
1845  //Groebner basis
1846  lpSickleDim(G); // invokes the procedure with ring parameters
1847  // the factor algebra is finite, so the degree bound given by the Letterplace
1848  // ring is not necessary
1849  lpSickleDim(G,0); // procedure without any degree bound
1850}
1851
1852proc lpSickleHil(ideal G, list #)
1853"USAGE: lpSickleHil(G);
1854RETURN: A list
1855PURPOSE:Computing the Hilbert series and the mistletoes
1856ASSUME: - basering is a Letterplace ring.
1857@*      - if you specify a different degree bound degbound,
1858@*        degbound <= attrib(basering,uptodeg) holds.
1859NOTE: - If L is the list returned, then L[1] is an intvec, corresponding to the
1860@*      Hilbert series, L[2] is an ideal, the mistletoes.
1861@*    - If degbound is set, there will be a degree bound added. 0 means no
1862@*      degree bound. Default: attrib(basering,uptodeg).
1863@*    - n is the number of variables, which can be set to a different number.
1864@*      Default: attrib(basering, lV).
1865@*    - If I = L[1] is the intvec returned, then I[k] is the (k-1)-th
1866@*      coefficient of the Hilbert series.
1867@*    - If the K-dimension is known to be infinite, a degree bound is needed
1868EXAMPLE: example lpSickleHil; shows examples
1869"
1870{int degbound = attrib(basering,"uptodeg");int n = attrib(basering, "lV");
1871 if (size(#) > 0){if (typeof(#[1])=="int"){if (#[1] >= 0){degbound = #[1];}}}
1872 if (size(#) > 1){if (typeof(#[1])=="int"){if (#[2] > 0){n = #[2];}}}
1873 list L;
1875 L = ivSickleHil(L,n,degbound);
1876 L[2] =  ivL2lpI(L[2]);
1877 return(L);
1878}
1879example
1880{
1881  "EXAMPLE:"; echo = 2;
1882  ring r = 0,(x,y),dp;
1883  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
1884  setring R; // sets basering to Letterplace ring
1885  ideal G = x(1)*x(2), y(1)*y(2),x(1)*y(2)*x(3); // ideal G contains a
1886  //Groebner basis
1887  lpSickleHil(G); // invokes the procedure with ring parameters
1888  // the factor algebra is finite, so the degree bound given by the Letterplace
1889  // ring is not necessary
1890  lpSickleHil(G,0); // procedure without any degree bound
1891}
1892
1893proc sickle(ideal G, list #)
1894"USAGE: sickle(G[,m, d, h, degbound]); G an ideal; m,d,h,degbound optional
1895@*      integers
1896RETURN: A list
1897PURPOSE:Allowing the user to access all procs with one command
1898ASSUME: - basering is a Letterplace ring.
1899@*      - if you specify a different degree bound degbound,
1900@*        degbound <= attrib(basering,uptodeg) holds.
1901NOTE:   The returned object will always be a list, but the entries of the
1902@*      returned list may be very different
1903@* case m=1,d=1,h=1: see lpDHilbertSickle
1904@* case m=1,d=1,h=0: see lpSickleDim
1905@* case m=1,d=0,h=1: see lpSickleHil
1906@* case m=1,d=0,h=0: see lpSickle (this is the default case)
1907@* case m=0,d=1,h=1: see lpDHilbert
1908@* case m=0,d=1,h=0: see lpKDim
1909@* case m=0,d=0,h=1: see lpHilbert
1910@* case m=0,d=0,h=0: returns an error
1911@*    - If degbound is set, there will be a degree bound added. 0 means no
1912@*      degree bound. Default: attrib(basering,uptodeg).
1913@*    - If the K-dimension is known to be infinite, a degree bound is needed
1914EXAMPLE: example sickle; shows examples
1915"
1916{int m,d,h,degbound;
1917 m = 1; d = 0; h = 0; degbound = attrib(basering,"uptodeg");
1918 if (size(#) > 0) {if (typeof(#[1])=="int"){if (#[1] < 1) {m = 0;}}}
1919 if (size(#) > 1) {if (typeof(#[1])=="int"){if (#[2] > 0) {d = 1;}}}
1920 if (size(#) > 2) {if (typeof(#[1])=="int"){if (#[3] > 0) {h = 1;}}}
1921 if (size(#) > 3) {if (typeof(#[1])=="int"){if (#[4] >= 0) {degbound = #[4];}}}
1922 if (m == 1)
1923 {if (d == 0)
1924  {if (h == 0) {return(lpSickle(G,degbound,attrib(basering,"lV")));}
1925   else        {return(lpSickleHil(G,degbound,attrib(basering,"lV")));}
1926  }
1927  else
1928  {if (h == 0) {return(lpSickleDim(G,degbound,attrib(basering,"lV")));}
1929   else {return(lpDHilbertSickle(G,degbound,attrib(basering,"lV")));}
1930  }
1931 }
1932 else
1933 {if (d == 0)
1934  {if (h == 0) {ERROR("You request to do nothing, so relax and do so");}
1935   else        {return(lpHilbert(G,degbound,attrib(basering,"lV")));}
1936  }
1937  else
1938  {if (h == 0) {return(lpKDim(G,degbound,attrib(basering,"lV")));}
1939   else {return(lpDHilbert(G,degbound,attrib(basering,"lV")));}
1940  }
1941 }
1942}
1943example
1944{
1945  "EXAMPLE:"; echo = 2;
1946  ring r = 0,(x,y),dp;
1947  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
1948  setring R; // sets basering to Letterplace ring
1949  ideal G = x(1)*x(2), y(1)*y(2),x(1)*y(2)*x(3);
1950  // G contains a Groebner basis
1951  sickle(G,1,1,1); // computes mistletoes, K-dimension and the Hilbert series
1952  sickle(G,1,0,0); // computes mistletoes only
1953  sickle(G,0,1,0); // computes K-dimension only
1954  sickle(G,0,0,1); // computes Hilbert series only
1955}
1956
1957///////////////////////////////////////////////////////////////////////////////
1958
1959
1961{
1962 example ivDHilbert;
1963 example ivDHilbertSickle;
1964 example ivDimCheck;
1965 example ivHilbert;
1966 example ivKDim;
1967 example ivMis2Dim;
1968 example ivOrdMisLex;
1969 example ivSickle;
1970 example ivSickleHil;
1971 example ivSickleDim;
1972 example lpDHilbert;
1973 example lpDHilbertSickle;
1974 example lpHilbert;
1975 example lpDimCheck;
1976 example lpKDim;
1977 example lpMis2Dim;
1978 example lpOrdMisLex;
1979 example lpSickle;
1980 example lpSickleHil;
1981 example lpSickleDim;
1982 example sickle;
1983 example ivL2lpI;
1984 example iv2lp;
1985 example iv2lpList;
1986 example iv2lpMat;
1987 example lp2iv;
1988 example lp2ivId;
1989 example lpId2ivLi;
1990}
1991
1992
1993
1994
1995
1996/*
1997Here are some examples one may try. Just copy them into your console.
1998These are relations for braid groups, up to degree d:
1999
2000
2002ring r = 0,(x,y,z),dp;
2003int d =10; // degree
2004def R = makeLetterplaceRing(d);
2005setring R;
2006ideal I = y(1)*x(2)*y(3) - z(1)*y(2)*z(3), x(1)*y(2)*x(3) - z(1)*x(2)*y(3),
2007z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) + y(1)*y(2)*y(3) +
2008z(1)*z(2)*z(3) + x(1)*y(2)*z(3);
2009option(prot);
2010option(redSB);option(redTail);option(mem);
2011ideal J = system("freegb",I,d,3);
2012lpDimCheck(J);
2013sickle(J,1,1,1,d);//Computes mistletoes, K-dimension and the Hilbert series
2014
2015
2016
2018ring r = 0,(x,y,z),dp;
2019int d =11; // degree
2020def R = makeLetterplaceRing(d);
2021setring R;
2022ideal I = y(1)*x(2)*y(3) - z(1)*y(2)*z(3), x(1)*y(2)*z(3) - z(1)*x(2)*y(3),
2023z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) + y(1)*y(2)*y(3) +
2024z(1)*z(2)*z(3) + x(1)*y(2)*z(3);
2025option(prot);
2026option(redSB);option(redTail);option(mem);
2027ideal J = system("freegb",I,d,3);
2028lpDimCheck(J);
2029sickle(J,1,1,1,d);
2030
2031
2032
2034ring r = 0,(x,y,z),dp;
2035int d  = 6; // degree
2036def R  = makeLetterplaceRing(d);
2037setring R;
2038ideal I = y(1)*x(2)*y(3) - z(1)*y(2)*z(3), x(1)*y(2)*x(3) - z(1)*x(2)*y(3),
2039z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) -2*y(1)*y(2)*y(3) + 3*z(1)*z(2)*z(3) -4*x(1)*y(2)*z(3) + 5*x(1)*z(2)*z(3)- 6*x(1)*y(2)*y(3) +7*x(1)*x(2)*z(3) - 8*x(1)*x(2)*y(3);
2040option(prot);
2041option(redSB);option(redTail);option(mem);
2042ideal J = system("freegb",I,d,3);
2043lpDimCheck(J);
2044sickle(J,1,1,1,d);
2045*/
2046
2047/*
2048Here are some examples, which can also be found in [studzins]:
2049
2050// takes up to 880Mb of memory
2052ring r = 0,(x,y,z),dp;
2053int d =10; // degree
2054def R = makeLetterplaceRing(d);
2055setring R;
2056ideal I =
2057z(1)*z(2)*z(3)*z(4) + y(1)*x(2)*y(3)*x(4) - x(1)*y(2)*y(3)*x(4) - 3*z(1)*y(2)*x(3)*z(4), x(1)*x(2)*x(3) + y(1)*x(2)*y(3) - x(1)*y(2)*x(3), z(1)*y(2)*x(3)-x(1)*y(2)*z(3) + z(1)*x(2)*z(3);
2058option(prot);
2059option(redSB);option(redTail);option(mem);
2060ideal J = system("freegb",I,d,nvars(r));
2061lpDimCheck(J);
2062sickle(J,1,1,1,d); // dimension is 24872
2063
2064