source: git/Singular/LIB/fpadim.lib @ cb8103a

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