source: git/Singular/LIB/fpadim.lib @ 5ec7e3

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