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