Changeset 601afa in git for Singular/LIB/fpadim.lib

Timestamp:

Jan 8, 2018, 3:36:18 PM (6 years ago)

Author:

Hans Schoenemann <hannes@…>

Branches:

(u'spielwiese', '17f1d200f27c5bd38f5dfc6e8a0879242279d1d8')

Children:

42d919575c3833261bf0756fdfd90f0f27dac0e6

Parents:

6b02216593677b82e2b32595292b3622d7c6816e88dc1d4c1c83ba8ca3e1cbb7e574d2427539b133

Message:

Merge branch 'test' into spielwiese

File:

• Singular/LIB/fpadim.lib (modified) (43 diffs)

Singular/LIB/fpadim.lib

@@ -4 +4 @@
 info="
 LIBRARY: fpadim.lib     Algorithms for quotient algebras in the letterplace case
-AUTHORS: Grischa Studzinski,       grischa.studzinski@rwth-aachen.de
+AUTHORS: Grischa Studzinski,       grischa.studzinski at rwth-aachen.de
+@*       Viktor Levandovskyy,      viktor.levandovskyy at math.rwth-aachen.de
+@*       Karim Abou Zeid,          karim.abou.zeid at rwth-aachen.de
 
 Support: Joint projects LE 2697/2-1 and KR 1907/3-1 of the Priority Programme SPP 1489:
-@* 'Algorithmische und Experimentelle Methoden in Algebra, Geometrie und Zahlentheorie'
-@* of the German DFG
-
-OVERVIEW: Given the free algebra A = K<x_1,...,x_n> and a (finite) Groebner basis
+'Algorithmische und Experimentelle Methoden in Algebra, Geometrie und Zahlentheorie'
+of the German DFG
+and Project II.6 of the transregional collaborative research centre
+SFB-TRR 195 'Symbolic Tools in Mathematics and their Application' of the German DFG
+
+OVERVIEW: Given the free associative algebra A = K<x_1,...,x_n> and a (finite) Groebner basis
       GB = {g_1,..,g_w}, one is interested in the K-dimension and in the
       explicit K-basis of A/<GB>.
       Therefore one is interested in the following data:
-@*      - the Ufnarovskij graph induced by GB
-@*      - the mistletoes of A/<GB>
-@*      - the K-dimension of A/<GB>
-@*      - the Hilbert series of A/<GB>
-
-      The Ufnarovskij graph is used to determine whether A/<GB> has finite
-      K-dimension. One has to check if the graph contains cycles.
-      For the whole theory we refer to [ufna]. Given a
-      reduced set of monomials GB one can define the basis tree, whose vertex
-      set V consists of all normal monomials w.r.t. GB. For every two
-      monomials m_1, m_2 in V there is a direct edge from m_1 to m_2, if and
-      only if there exists x_k in {x_1,..,x_n}, such that m_1*x_k = m_2. The
-      set M = {m in V | there is no edge from m to another monomial in V} is
-      called the set of mistletoes. As one can easily see it consists of
-      the endpoints of the graph. Since there is a unique path to every
-      monomial in V the whole graph can be described only from the knowledge
-      of the mistletoes. Note that V corresponds to a basis of A/<GB>, so
-      knowing the mistletoes we know a K-basis. The name mistletoes was given
-      to those points because of these miraculous value and the algorithm is
-      named sickle, because a sickle is the tool to harvest mistletoes.
-      For more details see [studzins]. This package uses the Letterplace
-      format introduced by [lls]. The algebra can either be represented as a
-      Letterplace ring or via integer vectors: Every variable will only be
-      represented by its number, so variable one is represented as 1,
-      variable two as 2 and so on. The monomial x_1*x_3*x_2 for example will
-      be stored as (1,3,2). Multiplication is concatenation. Note that there
-      is no algorithm for computing the normal form needed for our case.
-      Note that the name fpadim.lib is short for dimensions of finite
-      presented algebras.
+      - the Ufnarovskij graph induced by GB
+      - the mistletoes of A/<GB> (special monomials in a basis)
+      - the K-dimension of A/<GB>
+      - the Hilbert series of A/<GB>
+
+@*      The Ufnarovskij graph is used to determine whether A/<GB> has finite
+@*      K-dimension. One has to check if the graph contains cycles.
+@*      For the whole theory we refer to [ufna]. Given a
+@*      reduced set of monomials GB one can define the basis tree, whose vertex
+@*      set V consists of all normal monomials w.r.t. GB. For every two
+@*      monomials m_1, m_2 in V there is a direct edge from m_1 to m_2, if and
+@*      only if there exists x_k in {x_1,..,x_n}, such that m_1*x_k = m_2. The
+@*      set M = {m in V | there is no edge from m to another monomial in V} is
+@*      called the set of mistletoes. As one can easily see it consists of
+@*      the endpoints of the graph. Since there is a unique path to every
+@*      monomial in V the whole graph can be described only from the knowledge
+@*      of the mistletoes. Note that V corresponds to a basis of A/<GB>, so
+@*      knowing the mistletoes we know a K-basis. The name mistletoes was given
+@*      to those points because of these miraculous value and the algorithm is
+@*      named sickle, because a sickle is the tool to harvest mistletoes.
+@*      For more details see [studzins]. This package uses the Letterplace
+@*      format introduced by [lls]. The algebra can either be represented as a
+@*      Letterplace ring or via integer vectors: Every variable will only be
+@*      represented by its number, so variable one is represented as 1,
+@*      variable two as 2 and so on. The monomial x_1*x_3*x_2 for example will
+@*      be stored as (1,3,2). Multiplication is concatenation. Note that the
+@*      approach in this library does not need an algorithm for computing the normal
+@*      form yet. Note that the name fpadim.lib is short for dimensions of
+@*      finite presented algebras.
+@*
 
 REFERENCES:
@@ -48 +53 @@
 @*   [ufna] Ufnarovskij: Combinatorical and asymptotic methods in algebra, 1990
 @*   [lls] Levandovskyy, La Scala: Letterplace ideals and non-commutative
-          Groebner bases, 2009
+Groebner bases, 2009
 @*   [studzins] Studzinski: Dimension computations in non-commutative,
-                     associative algebras, Diploma thesis, RWTH Aachen, 2010
-
-Assumptions:
-@* - basering is always a Letterplace ring
-@* - all intvecs correspond to Letterplace monomials
-@* - if you specify a different degree bound d,
-     d <= attrib(basering,uptodeg) should hold.
-@* In the procedures below, 'iv' stands for intvec representation
-  and 'lp' for the letterplace representation of monomials
+associative algebras, Diploma thesis, RWTH Aachen, 2010
+
+NOTE:
+- basering is always a Letterplace ring
+- all intvecs correspond to Letterplace monomials
+- if you specify a different degree bound d, d <= attrib(basering,uptodeg) holds
+
+In the procedures below, 'iv' stands for intvec representation
+and 'lp' for the letterplace representation of monomials
 
 PROCEDURES:
+
+lpMis2Dim(M);              computes the K-dimension of the monomial factor algebra
+lpKDim(G[,d,n]);           computes the K-dimension of A/<G>
+lpDimCheck(G);             checks if the K-dimension of A/<G> is infinite
+lpMis2Base(M);             computes a K-basis of the factor algebra
+lpHilbert(G[,d,n]);        computes the Hilbert series of A/<G> in lp format
+lpDHilbert(G[,d,n]);       computes the K-dimension and Hilbert series of A/<G>
+lpDHilbertSickle(G[,d,n]); computes mistletoes, K-dimension and Hilbert series
 
 ivDHilbert(L,n[,d]);       computes the K-dimension and the Hilbert series
@@ -73 +86 @@
 ivSickleHil(L,n[,d]);      computes the mistletoes and Hilbert series of A/<L>
 ivSickleDim(L,n[,d]);      computes the mistletoes and the K-dimension of A/<L>
-lpDHilbert(G[,d,n]);       computes the K-dimension and Hilbert series of A/<G>
-lpDHilbertSickle(G[,d,n]); computes mistletoes, K-dimension and Hilbert series
-lpHilbert(G[,d,n]);        computes the Hilbert series of A/<G> in lp format
-lpDimCheck(G);             checks if the K-dimension of A/<G> is infinite
-lpKDim(G[,d,n]);           computes the K-dimension of A/<G> in lp format
-lpMis2Base(M);             computes a K-basis of the factor algebra
-lpMis2Dim(M);              computes the K-dimension of the factor algebra
 lpOrdMisLex(M);            orders an ideal of lp-monomials lexicographically
 lpSickle(G[,d,n]);         computes the mistletoes of A/<G> in lp format
@@ -85 +91 @@
 lpSickleDim(G[,d,n]);      computes the mistletoes and the K-dimension of A/<G>
 sickle(G[,m,d,h]);         can be used to access all lp main procedures
-
 
 ivL2lpI(L);           transforms a list of intvecs into an ideal of lp monomials
@@ -145 +150 @@
     {for (i3 = 1; i3 <= n; i3++)
       {for (i4 = 1; i4 <= (n^(i1-1)); i4++)
-      {
-        M[i2,i1] = i3;
+        {M[i2,i1] = i3;
           i2 = i2 + 1;
-       }
+        }
       }
     }
@@ -170 +174 @@
 "PURPOSE:checks, if all entries in M are variable-related
 "
-{if ((nrows(M) == 1) && (ncols(M) == 1)) {if (M[1,1] == 0){return(0);}}
- int i,j;
+{int i,j;
   for (i = 1; i <= nrows(M); i++)
   {for (j = 1; j <= ncols(M); j++)
@@ -328 +331 @@
 }
 
+
+static proc findCycleDFS(int i, intmat T, intvec V)
+"
+PURPOSE:
+this is a classical deep-first search for cycles contained in a graph given by an intmat
+"
+{
+  intvec rV;
+  int k,k1,t;
+  int j = V[size(V)];
+  if (T[j,i] > 0) {return(V);}
+  else
+  {
+    for (k = 1; k <= ncols(T); k++)
+    {
+      t = 0;
+      if (T[j,k] > 0)
+      {
+        for (k1 = 1; k1 <= size(V); k1++) {if (V[k1] == k) {t = 1; break;}}
+        if (t == 0)
+        {
+          rV = V;
+          rV[size(rV)+1] = k;
+          rV = findCycleDFS(i,T,rV);
+          if (rV[1] > -1) {return(rV);}
+        }
+      }
+    }
+  }
+  return(intvec(-1));
+}
+
+
+
 static proc findHCoeff(intvec V,int n,list L,intvec P,intvec H,list #)
 "USAGE: findHCoeff(V,n,L,P,H,degbound); L a list of intmats, degbound an integer
@@ -565 +602 @@
       }
       return(R);
-
     }
   }
@@ -647 +683 @@
 }
 
+static proc growthAlg(intmat T, list #)
+"
+real algorithm for checking the growth of an algebra
+"
+{
+  int s = 1;
+  if (size(#) > 0) { s = #[1];}
+  int j;
+  int n = ncols(T);
+  intvec NV,C; NV[n] = 0; int m,i;
+  intmat T2[n][n] = T[1..n,1..n]; intmat N[n][n];
+  if (T2 == N)
+  {
+    for (i = 1; i <= n; i++)
+    {
+      if (m <  T[n+1,i]) { m = T[n+1,i];}
+    }
+    return(m);
+  }
+
+  //first part: the diagonals
+  for (i = s; i <= n; i++)
+  {
+    if (T[i,i] > 0)
+    {
+      if ((T[i,i] >= 1) && (T[n+1,i] > 0)) {return(-1);}
+      if ((T[i,i] == 1) && (T[n+1,i] == 0))
+      {
+        T[i,i] = 0;
+        T[n+1,i] = 1;
+        return(growthAlg(T));
+      }
+    }
+  }
+
+  //second part: searching for the last but one vertices
+  T2 = T2*T2;
+  for (i = s; i <= n; i++)
+  {
+    if ((intvec(T[i,1..n]) <> intvec(0)) && (intvec(T2[i,1..n]) == intvec(0)))
+    {
+      for (j = 1; j <= n; j++)
+      {
+        if ((T[i,j] > 0) && (m < T[n+1,j])) {m = T[n+1,j];}
+      }
+      T[n+1,i] = T[n+1,i] + m;
+      T[i,1..n] = NV;
+      return(growthAlg(T));
+    }
+  }
+  m = 0;
+
+  //third part: searching for circles
+  for (i = s; i <= n; i++)
+  {
+    T2 = T[1..n,1..n];
+    C = findCycleDFS(i,T2, intvec(i));
+    if (C[1] > 0)
+    {
+      for (j = 2; j <= size(C); j++)
+      {
+        T[i,1..n] = T[i,1..n] + T[C[j],1..n];
+        T[C[j],1..n] = NV;
+      }
+      for (j = 2; j <= size(C); j++)
+      {
+        T[1..n,i] = T[1..n,i] + T[1..n,C[j]];
+        T[1..n,C[j]] = NV;
+      }
+      T[i,i] = T[i,i] - size(C) + 1;
+      m = 0;
+      for (j = 1; j <= size(C); j++)
+      {
+        m = m + T[n+1,C[j]];
+      }
+      for (j = 1; j <= size(C); j++)
+      {
+        T[n+1,C[j]] = m;
+      }
+      return(growthAlg(T,i));
+    }
+    else {ERROR("No Cycle found, something seems wrong! Please contact the authors.");}
+  }
+
+  m = 0;
+  for (i = 1; i <= n; i++)
+  {
+    if (m < T[n+1,i])
+    {
+      m = T[n+1,i];
+    }
+  }
+  return(m);
+}
+
+static proc GlDimSuffix(intvec v, intvec g)
+{
+  //Computes the shortest r such that g is a suffix for vr
+  //only valid for lex orderings?
+  intvec r,gt,vt,lt,g2;
+  int lg,lv,l,i,c,f;
+  lg = size(g); lv = size(v);
+  if (lg <= lv)
+  {
+    l = lv-lg;
+  }
+  else
+  {
+    l = 0; g2 = g[(lv+1)..lg];
+    g = g[1..lv]; lg = size(g);
+    c = 1;
+  }
+  while (l < lv)
+  {
+    vt = v[(l+1)..lv];
+    gt = g[1..(lv-l)];
+    lt = size(gt);
+    for (i = 1; i <= lt; i++)
+    {
+      if (vt[i]<>gt[i]) {l++; break;}
+    }
+    if (lt <=i ) { f = 1; break;}
+  }
+  if (f == 0) {return(g);}
+  r = g[(lv-l+1)..lg];
+  if (c == 1) {r = r,g2;}
+  return(r);
+}
+
+static proc isNormal(intvec V, list G)
+{
+  int i,j,k,l;
+  k = 0;
+  for (i = 1; i <= size(G); i++)
+  {
+    if ( size(G[i]) <= size(V) )
+    {
+      while ( size(G[i])+k <= size(V) )
+      {
+        if ( G[i] == V[(1+k)..size(V)] ) {return(1);}
+      }
+    }
+  }
+  return(0);
+}
+
+static proc findDChain(list L)
+{
+  list Li; int i,j;
+  for (i = 1; i <= size(L); i++) {Li[i] = size(L[i]);}
+  Li = sort(Li); Li = Li[1];
+  return(Li[size(Li)]);
+}
+
 static proc isInList(intvec V, list L)
 "USAGE: isInList(V,L); V an intvec, L a list of intvecs
@@ -684 +874 @@
 }
 
+
+static proc isPF(intvec P, intvec I)
+"
+PURPOSE:
+checks, if a word P is a praefix of another word I
+"
+{
+  int n = size(P);
+  if (n <= 0 || P == 0) {return(1);}
+  if (size(I) < n) {return(0);}
+  intvec IP = I[1..n];
+  if (IP == P) {return(1);}
+  else {return(0);}
+}
+
 proc ivL2lpI(list L)
 "USAGE: ivL2lpI(L); L a list of intvecs
 RETURN: ideal
-PURPOSE:Transforming a list of intvecs into an ideal of Letterplace monomials.
-@*      For the encoding of the variables see the overview.
+PURPOSE:Transforming a list of intvecs into an ideal of Letterplace monomials
 ASSUME: - Intvec corresponds to a Letterplace monomial
 @*      - basering has to be a Letterplace ring
+NOTE:   - Assumptions will not be checked!
 EXAMPLE: example ivL2lpI; shows examples
 "
-{checkAssumptions(0,L);
+{
   int i; ideal G;
   poly p;
@@ -718 +923 @@
 RETURN: poly
 PURPOSE:Transforming an intvec into the corresponding Letterplace polynomial
-@*      For the encoding of the variables see the overview.
 ASSUME: - Intvec corresponds to a Letterplace monomial
 @*      - basering has to be a Letterplace ring
@@ -748 +952 @@
 RETURN: ideal
 PURPOSE:Converting a list of intmats into an ideal of corresponding monomials
-@*      The rows of the intmat corresponds to an intvec, which stores the
-@*      monomial.
-@*      For the encoding of the variables see the overview.
 ASSUME: - The rows of each intmat in L must correspond to a Letterplace monomial
 @*      - basering has to be a Letterplace ring
@@ -779 +980 @@
 "USAGE: iv2lpMat(M); M an intmat
 RETURN: ideal
-PURPOSE:Converting an intmat into an ideal of the corresponding monomials.
-@*      The rows of the intmat corresponds to an intvec, which stores the
-@*      monomial.
-@*      For the encoding of the variables see the overview.
+PURPOSE:Converting an intmat into an ideal of the corresponding monomials
 ASSUME: - The rows of M must correspond to Letterplace monomials
 @*      - basering has to be a Letterplace ring
@@ -816 +1014 @@
 "USAGE: lpId2ivLi(G); G an ideal
 RETURN: list
-PURPOSE:Transforming an ideal into the corresponding list of intvecs.
-@*      For the encoding of the variables see the overview.
+PURPOSE:Transforming an ideal into the corresponding list of intvecs
 ASSUME: - basering has to be a Letterplace ring
 EXAMPLE: example lpId2ivLi; shows examples
 "
-{int i,j,k;
+{
+  int i,j,k;
   list M;
   checkAssumptions(0,M);
@@ -840 +1038 @@
 "USAGE: lp2iv(p); p a poly
 RETURN: intvec
-PURPOSE:Transforming a monomial into the corresponding intvec.
-@*      For the encoding of the variables see the overview.
+PURPOSE:Transforming a monomial into the corresponding intvec
 ASSUME: - basering has to be a Letterplace ring
 NOTE:   - Assumptions will not be checked!
@@ -883 +1080 @@
 RETURN: list
 PURPOSE:Converting an ideal into an list of intmats,
-@*      the corresponding intvecs forming the rows.
-@*      For the encoding of the variables see the overview.
+@*      the corresponding intvecs forming the rows
 ASSUME: - basering has to be a Letterplace ring
 EXAMPLE: example lp2ivId; shows examples
@@ -925 +1121 @@
 // -----------------main procedures----------------------
 
+static proc lpGraphOfNormalWords(ideal G)
+"USAGE: lpGraphOfNormalWords(G); G a set of monomials in a letterplace ring
+RETURN: intmat
+PURPOSE: Constructs the graph of normal words induced by G
+@*:      the adjacency matrix of the graph of normal words induced by G
+ASSUME: - basering is a Letterplace ring
+- G are the leading monomials of a Groebner basis
+"
+{
+  // construct the Graph of normal words [Studzinski page 78]
+  // construct set of vertices
+  int v = attrib(basering,"lV"); int d = attrib(basering,"uptodeg");
+  ideal V; poly p,q,w;
+  ideal LG = lead(G);
+  int i,j,k,b; intvec E,Et;
+  for (i = 1; i <= v; i++){V = V, var(i);}
+  for (i = 1; i <= size(LG); i++)
+  {
+    E = leadexp(LG[i]);
+    if (E == intvec(0)) {V = V,monomial(intvec(0));}
+    else
+    {
+      for (j = 1; j < d; j++)
+      {
+        Et = E[(j*v+1)..(d*v)];
+        if (Et == intvec(0)) {break;}
+        else {V = V, monomial(Et);}
+      }
+    }
+  }
+  V = simplify(V,2+4);
+  printf("V = %p", V);
+
+
+  // construct incidence matrix
+
+  list LV = lpId2ivLi(V);
+  intvec Ip,Iw;
+  int n = size(V);
+  intmat T[n+1][n];
+  for (i = 1; i <= n; i++)
+  {
+    // printf("for1 (i=%p, n=%p)", i, n);
+    p = V[i]; Ip = lp2iv(p);
+    for (j = 1; j <= n; j++)
+    {
+      // printf("for2 (j=%p, n=%p)", j, n);
+      k = 1; b = 1;
+      q = V[j];
+      w = lpNF(lpMult(p,q),LG);
+      if (w <> 0)
+      {
+        Iw = lp2iv(w);
+        while (k <= n)
+        {
+          // printf("while (k=%p, n=%p)", k, n);
+          if (isPF(LV[k],Iw) > 0)
+          {if (isPF(LV[k],Ip) == 0) {b = 0; k = n+1;} else {k++;}
+          }
+          else {k++;}
+        }
+        T[i,j] = b;
+        //  print("Incidence Matrix:");
+        // print(T);
+      }
+    }
+  }
+  return(T);
+}
+
+// This proc is deprecated, see lpGkDim() in fpaprops.lib
+/* proc lpGkDim(ideal G) */
+/* "USAGE: lpGkDim(G); G an ideal in a letterplace ring */
+/* RETURN: int */
+/* PURPOSE: Determines the Gelfand Kirillov dimension of A/<G> */
+/* @*:     -1 means it is infinite */
+/* ASSUME: - basering is a Letterplace ring */
+/* - G is a Groebner basis */
+/* NOTE: see fpaprops.lib for a faster and more up to date version of this method */
+/* " */
+/* { */
+/*   return(growthAlg(lpGraphOfNormalWords(G))); */
+/* } */
+
 proc ivDHilbert(list L, int n, list #)
 "USAGE: ivDHilbert(L,n[,degbound]); L a list of intmats, n an integer,
@@ -932 +1212 @@
 ASSUME: - basering is a Letterplace ring
 @*      - all rows of each intmat correspond to a Letterplace monomial
-@*        for the encoding of the variables see the overview
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds
 NOTE: - If L is the list returned, then L[1] is an integer corresponding to the
 @*      dimension, L[2] is an intvec which contains the coefficients of the
@@ -984 +1263 @@
 ASSUME: - basering is a Letterplace ring.
 @*      - All rows of each intmat correspond to a Letterplace monomial.
-@*        for the encoding of the variables see the overview
 @*      - If you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If L is the list returned, then L[1] is an integer, L[2] is an intvec
 @*      which contains the coefficients of the Hilbert series and L[3]
@@ -1031 +1309 @@
 RETURN: int, 0 if the dimension is finite, or 1 otherwise
 PURPOSE:Decides, whether the K-dimension is finite or not
-ASSUME: - basering is a Letterplace ring
-@*      - All rows of each intmat correspond to a Letterplace monomial
-@*        For the encoding of the variables see the overview.
-NOTE:   - n is the number of variables
+ASSUME: - basering is a Letterplace ring.
+@*      - All rows of each intmat correspond to a Letterplace monomial.
+NOTE:   - n is the number of variables.
 EXAMPLE: example ivDimCheck; shows examples
 "
@@ -1090 +1367 @@
 ASSUME: - basering is a Letterplace ring.
 @*      - all rows of each intmat correspond to a Letterplace monomial
-@*        for the encoding of the variables see the overview
 @*      - if you specify a different degree bound degbound,
-@*       degbound <= attrib(basering,uptodeg) should hold.
+@*       degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If degbound is set, a degree bound  will be added. By default there
 @*      is no degree bound.
@@ -1176 +1452 @@
 ASSUME: - basering is a Letterplace ring.
 @*      - all rows of each intmat correspond to a Letterplace monomial
-@*        for the encoding of the variables see the overview
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If degbound is set, a degree bound will be added. By default there
 @*      is no degree bound.
@@ -1263 +1538 @@
 "
 {
-//checkAssumptions(0,M);
+  //checkAssumptions(0,M);
   intvec L,A;
   if (size(M) == 0){ERROR("There are no mistletoes, so it appears your dimension is infinite!");}
@@ -1274 +1549 @@
   for (i = 2; i <= size(M); i++)
   {A = M[i]; L = M[i-1];
-   s = size(A);
-   if (s > size(L))
-   {d = size(L);
-    for (j = s; j > d; j--) {Rt = insert(Rt,intvec(A[1..j]));}
-    A = A[1..d];
-   }
-   if (size(L) > s){L = L[1..s];}
-   while (A <> L)
-   {Rt = insert(Rt, intvec(A));
-    if (size(A) > 1)
-    {A = A[1..(size(A)-1)];
-     L = L[1..(size(L)-1)];
-    }
-    else {break;}
-   }
+    s = size(A);
+    if (s > size(L))
+    {d = size(L);
+      for (j = s; j > d; j--) {Rt = insert(Rt,intvec(A[1..j]));}
+      A = A[1..d];
+    }
+    if (size(L) > s){L = L[1..s];}
+    while (A <> L)
+    {Rt = insert(Rt, intvec(A));
+      if (size(A) > 1)
+      {A = A[1..(size(A)-1)];
+        L = L[1..(size(L)-1)];
+      }
+      else {break;}
+    }
   }
   return(Rt);
@@ -1313 +1588 @@
 @*        Otherwise the returned value may differ from the K-dimension.
 @*      - basering is a Letterplace ring.
-@*      - mistletoes are stored as intvecs, as described in the overview
 EXAMPLE: example ivMis2Dim; shows examples
 "
@@ -1321 +1595 @@
   if (isInList(L,M) > 0) {print("1 is a mistletoe, therefore dim = 1"); return(1);}
   int i,j,d,s;
+  j = 1;
   d = 1 + size(M[1]);
   for (i = 1; i < size(M); i++)
-  {j = 1;
-   s = size(M[i]); if (s > size(M[i+1])){s = size(M[i+1]);}
-   while ((M[i][j] == M[i+1][j]) && (j <= s)){j = j + 1;}
-   d = d + size(M[i+1])- j + 1;
+  {s = size(M[i]); if (s > size(M[i+1])){s = size(M[i+1]);}
+    while ((M[i][j] == M[i+1][j]) && (j <= s)){j = j + 1;}
+    d = d + size(M[i+1])- j + 1;
   }
   return(d);
@@ -1348 +1622 @@
 PURPOSE:Orders a given set of mistletoes lexicographically
 ASSUME: - basering is a Letterplace ring.
-@*      - intvecs correspond to monomials, as explained in the overview
+- intvecs correspond to monomials
 NOTE:   - This is preprocessing, it's not needed if the mistletoes are returned
 @*        from the sickle algorithm.
@@ -1374 +1648 @@
 @*      optional integer
 RETURN: list, containing intvecs, the mistletoes of A/<L>
-PURPOSE:Computing the mistletoes for a given Groebner basis L, given by intmats
+PURPOSE:Computing the mistletoes for a given Groebner basis L
 ASSUME: - basering is a Letterplace ring.
 @*      - all rows of each intmat correspond to a Letterplace monomial
-@*        as explained in the overview
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If degbound is set, a degree bound will be added. By default there
 @*      is no degree bound.
@@ -1457 +1730 @@
 ASSUME: - basering is a Letterplace ring.
 @*      - all rows of each intmat correspond to a Letterplace monomial
-@*        as explained in the overview
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If L is the list returned, then L[1] is an integer, L[2] is a list,
 @*      containing the mistletoes as intvecs.
@@ -1545 +1817 @@
 ASSUME: - basering is a Letterplace ring.
 @*      - all rows of each intmat correspond to a Letterplace monomial
-@*        as explained in the overview
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If L is the list returned, then L[1] is an intvec, L[2] is a list,
 @*      containing the mistletoes as intvecs.
@@ -1630 +1901 @@
 RETURN: list
 PURPOSE:Computing K-dimension and Hilbert series, starting with a lp-ideal
-ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If L is the list returned, then L[1] is an integer corresponding to the
 @*      dimension, L[2] is an intvec which contains the coefficients of the
@@ -1672 +1943 @@
 RETURN: list
 PURPOSE:Computing K-dimension, Hilbert series and mistletoes at once
-ASSUME: - basering is a Letterplace ring.  G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If L is the list returned, then L[1] is an integer, the K-dimension,
 @*      L[2] is an intvec, the Hilbert series and L[3] is an ideal,
@@ -1715 +1986 @@
 RETURN: intvec, containing the coefficients of the Hilbert series
 PURPOSE:Computing the Hilbert series
-ASSUME: - basering is a Letterplace ring.  G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If degbound is set, there will be a degree bound added. 0 means no
 @*      degree bound. Default: attrib(basering,uptodeg).
@@ -1753 +2024 @@
 RETURN: int, 1 if K-dimension of the factor algebra is infinite, 0 otherwise
 PURPOSE:Checking a factor algebra for finiteness of the K-dimension
-ASSUME: - basering is a Letterplace ring.  G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 EXAMPLE: example lpDimCheck; shows examples
 "
@@ -1781 +2052 @@
 RETURN: int, the K-dimension of the factor algebra
 PURPOSE:Computing the K-dimension of a factor algebra, given via an ideal
-ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If degbound is set, there will be a degree bound added. 0 means no
 @*      degree bound. Default: attrib(basering, uptodeg).
@@ -1840 +2111 @@
 RETURN: int, the K-dimension of the factor algebra
 PURPOSE:Computing the K-dimension out of given mistletoes
-ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - M contains only monomials
 NOTE:   - The mistletoes have to be ordered lexicographically -> OrdMisLex.
@@ -1864 +2135 @@
 RETURN: ideal, containing the mistletoes, ordered lexicographically
 PURPOSE:A given set of mistletoes is ordered lexicographically
-ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 NOTE:   This is preprocessing, it is not needed if the mistletoes are returned
 @*      from the sickle algorithm.
@@ -1885 +2156 @@
 RETURN: ideal
 PURPOSE:Computing the mistletoes of K[X]/<G>
-ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If degbound is set, there will be a degree bound added. 0 means no
 @*      degree bound. Default: attrib(basering,uptodeg).
@@ -1923 +2194 @@
 RETURN: list
 PURPOSE:Computing the K-dimension and the mistletoes
-ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If L is the list returned, then L[1] is an integer, the K-dimension,
 @*      L[2] is an ideal, the mistletoes.
@@ -1962 +2233 @@
 RETURN: list
 PURPOSE:Computing the Hilbert series and the mistletoes
-ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE: - If L is the list returned, then L[1] is an intvec, corresponding to the
 @*      Hilbert series, L[2] is an ideal, the mistletoes.
@@ -2004 +2275 @@
 RETURN: list
 PURPOSE:Allowing the user to access all procs with one command
-ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
+ASSUME: - basering is a Letterplace ring.
 @*      - if you specify a different degree bound degbound,
-@*        degbound <= attrib(basering,uptodeg) should hold.
+@*        degbound <= attrib(basering,uptodeg) holds.
 NOTE:   The returned object will always be a list, but the entries of the
 @*      returned list may be very different
@@ -2062 +2333 @@
   sickle(G,0,0,1); // computes Hilbert series only
 }
+
+proc ivMaxIdeal(int l, int lonly)
+  "USAGE: lpMaxIdeal(l, lonly); l an integer, lonly an integer
+  RETURN: list
+  PURPOSE: computes a list of free monomials in intvec presentation
+  @*       with length <= l
+  @*       if donly <> 0, only monomials of degree d are returned
+  ASSUME: - basering is a Letterplace ring.
+  NOTE: see also lpMaxIdeal()
+  "
+{
+  if (l < 0) {
+    ERROR("l must not be negative")
+  }
+  list words;
+  if (l == 0) {
+     words = 0;
+     return (words);
+  }
+  int lV = attrib(basering, "lV"); // variable count
+  list prevWords;
+  if (l > 1) {
+    prevWords = ivMaxIdeal(l - 1, lonly);
+  } else {
+    prevWords = 0;
+  }
+  for (int i = 1; i <= size(prevWords); i++) {
+    if (size(prevWords[i]) >= l - 1) {
+      for (int j = 1; j <= lV; j++) {
+        intvec word = prevWords[i];
+        word[l] = j;
+        words = insert(words, word);
+        kill word;
+      } kill j;
+    }
+  } kill i;
+  if (!lonly && l > 1) {
+    words = prevWords + words;
+  }
+  return (words);
+}
+example {
+  "EXAMPLE:"; echo = 2;
+  ring r = 0,(a,b,c),dp;
+  def R = makeLetterplaceRing(7); setring R;
+  ivMaxIdeal(1,0);
+  ivMaxIdeal(2,0);
+  ivMaxIdeal(2,1);
+  ivMaxIdeal(4,0);
+  ivMaxIdeal(4,1);
+}
+
+proc lpMaxIdeal(int d, int donly)
+  "USAGE: lpMaxIdeal(d, donly); d an integer, donly an integer
+  RETURN: ideal
+  PURPOSE: computes a list of free monomials of degree at most d
+  @*       if donly <> 0, only monomials of degree d are returned
+  ASSUME: - basering is a Letterplace ring.
+  @*      - d <= attrib(basering,uptodeg) holds.
+  NOTE: analogous to maxideal(d) in the commutative case
+  "
+{
+  ivL2lpI(ivMaxIdeal(d, donly));
+}
+example {
+  "EXAMPLE:"; echo = 2;
+  ring r = 0,(a,b,c),dp;
+  def R = makeLetterplaceRing(7); setring R;
+  lpMaxIdeal(1,0);
+  lpMaxIdeal(2,0);
+  lpMaxIdeal(2,1);
+  lpMaxIdeal(4,0);
+  lpMaxIdeal(4,1);
+}
+
+proc monomialBasis(int d, int donly, ideal J)
+  "USAGE: monomialBasis(d, donly, J); d, donly integers, J an ideal
+  RETURN: ideal
+  PURPOSE: computes a list of free monomials in a Letterplace
+  @*       basering R of degree at most d and not contained in <LM(J)>
+  @*       if donly <> 0, only monomials of degree d are returned
+  ASSUME: - basering is a Letterplace ring.
+  @*      - d <= attrib(basering,uptodeg) holds.
+  @*      - J is a Groebner basis
+  "
+{
+  int nv = attrib(basering,"uptodeg");
+  if ((d>nv) || (d<0) )
+  {
+    ERROR("incorrect degree");
+  }
+  nv = attrib(basering,"lV"); // nvars
+  if (d==0)
+  {
+    return(ideal(1));
+  }
+  /* from now on d>=1 */
+  ideal I;
+  if (size(J)==0)
+  {
+    I = lpMaxIdeal(d,donly);
+    if (!donly)
+    {
+      // append 1 as the first element; d>=1
+      I = 1, I;
+    }
+    return( I );
+  }
+  // ok, Sickle misbehaves: have to remove all
+  // elts from J of degree >d
+  ideal JJ;
+  int j; int sj = ncols(J);
+  int cnt=0;
+  for(j=1;j<=sj;j++)
+  {
+    if (deg(J[j]) <= d)
+    {
+      cnt++;
+      JJ[cnt]=lead(J[j]); // only LMs are needed
+    }
+  }
+  if (cnt==0)
+  {
+    // there are no elements in J of degree <= d
+    // return free stuff and the 1
+    I = monomialBasis(d, donly, std(0));
+    if (!donly)
+    {
+      I = 1, I;
+    }
+    return(I);
+  }
+  // from here on, Ibase is not zero
+  ideal Ibase = lpMis2Base(lpSickle(JJ,d)); // the complete K-basis modulo J up to d
+  if (!donly)
+  {
+    // for not donly, give everything back
+    // sort by DP starting with smaller terms
+    Ibase = sort(Ibase,"Dp")[1];
+    return(Ibase);
+  }
+  /* !donly: pick out only monomials of degree d */
+  int i; int si = ncols(Ibase);
+  cnt=0;
+  I=0;
+  for(i=1;i<=si;i++)
+  {
+    if (deg(Ibase[i]) == d)
+    {
+      cnt++;
+      I[cnt]=Ibase[i];
+    }
+  }
+  kill Ibase;
+  return(I);
+}
+example {
+  "EXAMPLE:"; echo = 2;
+  ring r = 0,(x,y),dp;
+  def R = makeLetterplaceRing(7); setring R;
+  ideal J = x(1)*y(2)*x(3) - y(1)*x(2)*y(3);
+  option(redSB); option(redTail);
+  J = letplaceGBasis(J);
+  J;
+  monomialBasis(2,1,std(0));
+  monomialBasis(2,0,std(0));
+  monomialBasis(3,1,J);
+  monomialBasis(3,0,J);
+}
+
+
+///////////////////////////////////////////////////////////////////////////////
+/* vl: stuff for conversion to Magma and to SD
+todo: doc, example
+ */
+static proc extractVars(r)
+{
+  int i = 1;
+  int j = 1;
+  string candidate;
+  list result = list();
+  for (i = 1; i<=nvars(r);i++)
+  {
+    candidate = string(var(i))[1,find(string(var(i)),"(")-1];
+    if (!inList(result, candidate))
+    {
+      result = insert(result,candidate,size(result));
+    }
+  }
+  return(result);
+}
+
+static proc letterPlacePoly2MagmaString(poly h)
+{
+  int pos;
+  string s = string(h);
+  while(find(s,"("))
+  {
+    pos = find(s,"(");
+    while(s[pos]!=")")
+    {
+      s = s[1,pos-1]+s[pos+1,size(s)-pos];
+    }
+    if (size(s)!=pos)
+    {
+      s = s[1,pos-1]+s[pos+1,size(s)-pos]; // The last (")")
+    }
+    else
+    {
+      s = s[1,pos-1];
+    }
+  }
+  return(s);
+}
+
+static proc letterPlaceIdeal2SD(ideal I, int upToDeg)
+{
+  int i;
+  print("Don't forget to fill in the formal Data in the file");
+  string result = "<?xml version=\"1.0\"?>"+newline+"<FREEALGEBRA createdAt=\"\" createdBy=\"Singular\" id=\"FREEALGEBRA/\">"+newline;
+  result = result + "<vars>"+string(extractVars(basering))+"</vars>"+newline;
+  result = result + "<basis>"+newline;
+  for (i = 1;i<=size(I);i++)
+  {
+    result = result + "<poly>"+letterPlacePoly2MagmaString(I[i])+"</poly>"+newline;
+  }
+  result = result + "</basis>"+newline;
+  result = result + "<uptoDeg>"+ string(upToDeg)+"</uptoDeg>"+newline;
+  result = result + "<Comment></Comment>"+newline;
+  result = result + "<Version></Version>"+newline;
+  result = result + "</FREEALGEBRA>";
+  return(result);
+}
+
 
 ///////////////////////////////////////////////////////////////////////////////
@@ -2098 +2603 @@
   example lp2ivId;
   example lpId2ivLi;
-}
-
-
-
-
+  example lpSubstitute;
+}
 
 /*
-  Here are some examples one may try. Just copy them into your console.
-  These are relations for braid groups, up to degree d:
-
-
-  LIB "fpadim.lib";
-  ring r = 0,(x,y,z),dp;
-  int d =10; // degree
-  def R = makeLetterplaceRing(d);
-  setring R;
-  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),
-  z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) + y(1)*y(2)*y(3) +
-  z(1)*z(2)*z(3) + x(1)*y(2)*z(3);
-  option(prot);
-  option(redSB);option(redTail);option(mem);
-  ideal J = system("freegb",I,d,3);
-  lpDimCheck(J);
-  sickle(J,1,1,1,d);//Computes mistletoes, K-dimension and the Hilbert series
-
-
-
-  LIB "fpadim.lib";
-  ring r = 0,(x,y,z),dp;
-  int d =11; // degree
-  def R = makeLetterplaceRing(d);
-  setring R;
-  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),
-  z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) + y(1)*y(2)*y(3) +
-  z(1)*z(2)*z(3) + x(1)*y(2)*z(3);
-  option(prot);
-  option(redSB);option(redTail);option(mem);
-  ideal J = system("freegb",I,d,3);
-  lpDimCheck(J);
-  sickle(J,1,1,1,d);
-
-
-
-  LIB "fpadim.lib";
-  ring r = 0,(x,y,z),dp;
-  int d  = 6; // degree
-  def R  = makeLetterplaceRing(d);
-  setring R;
-  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),
-  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);
-  option(prot);
-  option(redSB);option(redTail);option(mem);
-  ideal J = system("freegb",I,d,3);
-  lpDimCheck(J);
-  sickle(J,1,1,1,d);
+   Here are some examples one may try. Just copy them into your console.
+   These are relations for braid groups, up to degree d:
+
+   LIB "fpadim.lib";
+   ring r = 0,(x,y,z),dp;
+   int d =10; // degree
+   def R = makeLetterplaceRing(d);
+   setring R;
+   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),
+   z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) + y(1)*y(2)*y(3) +
+   z(1)*z(2)*z(3) + x(1)*y(2)*z(3);
+   option(prot);
+   option(redSB);option(redTail);option(mem);
+   ideal J = system("freegb",I,d,3);
+   lpDimCheck(J);
+   sickle(J,1,1,1,d);//Computes mistletoes, K-dimension and the Hilbert series
+
+
+
+   LIB "fpadim.lib";
+   ring r = 0,(x,y,z),dp;
+   int d =11; // degree
+   def R = makeLetterplaceRing(d);
+   setring R;
+   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),
+   z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) + y(1)*y(2)*y(3) +
+   z(1)*z(2)*z(3) + x(1)*y(2)*z(3);
+   option(prot);
+   option(redSB);option(redTail);option(mem);
+   ideal J = system("freegb",I,d,3);
+   lpDimCheck(J);
+   sickle(J,1,1,1,d);
+
+
+
+   LIB "fpadim.lib";
+   ring r = 0,(x,y,z),dp;
+   int d  = 6; // degree
+   def R  = makeLetterplaceRing(d);
+   setring R;
+   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),
+   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);
+   option(prot);
+   option(redSB);option(redTail);option(mem);
+   ideal J = system("freegb",I,d,3);
+   lpDimCheck(J);
+   sickle(J,1,1,1,d);
+ */
+
+/*
+   Here are some examples, which can also be found in [studzins]:
+
+// takes up to 880Mb of memory
+LIB "fpadim.lib";
+ring r = 0,(x,y,z),dp;
+int d =10; // degree
+def R = makeLetterplaceRing(d);
+setring R;
+ideal I =
+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);
+option(prot);
+option(redSB);option(redTail);option(mem);
+ideal J = system("freegb",I,d,nvars(r));
+lpDimCheck(J);
+sickle(J,1,1,1,d); // dimension is 24872
+
+
+LIB "fpadim.lib";
+ring r = 0,(x,y,z),dp;
+int d =10; // degree
+def R = makeLetterplaceRing(d);
+setring R;
+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);
+option(prot);
+option(redSB);option(redTail);option(mem);
+ideal J = system("freegb",I,d,3);
+lpDimCheck(J);
+sickle(J,1,1,1,d);
+ */
+
+
+/*
+   Example for computing GK dimension:
+   returns a ring which contains an ideal I
+   run gkDim(I) inside this ring and it should return 2n (the GK dimension
+   of n-th Weyl algebra including evaluation operators).
+
+   static proc createWeylEx(int n, int d)
+   "
+   "
+   {
+   int baseringdef;
+   if (defined(basering)) // if a basering is defined, it should be saved for later use
+   {
+   def save = basering;
+   baseringdef = 1;
+   }
+   ring r = 0,(d(1..n),x(1..n),e(1..n)),dp;
+   def R = makeLetterplaceRing(d);
+   setring R;
+   ideal I; int i,j;
+
+   for (i = 1; i <= n; i++)
+   {
+   for (j = i+1; j<= n; j++)
+   {
+   I[size(I)+1] = lpMult(var(i),var(j));
+   }
+   }
+
+   for (i = 1; i <= n; i++)
+   {
+   for (j = i+1; j<= n; j++)
+   {
+   I[size(I)+1] = lpMult(var(n+i),var(n+j));
+   }
+   }
+   for (i = 1; i <= n; i++)
+   {
+   for (j = 1; j<= n; j++)
+   {
+   I[size(I)+1] = lpMult(var(i),var(n+j));
+   }
+   }
+   for (i = 1; i <= n; i++)
+   {
+   for (j = 1; j<= n; j++)
+   {
+   I[size(I)+1] = lpMult(var(i),var(2*n+j));
+   }
+   }
+   for (i = 1; i <= n; i++)
+   {
+   for (j = 1; j<= n; j++)
+   {
+   I[size(I)+1] = lpMult(var(2*n+i),var(n+j));
+   }
+   }
+   for (i = 1; i <= n; i++)
+   {
+   for (j = 1; j<= n; j++)
+   {
+   I[size(I)+1] = lpMult(var(2*n+i),var(2*n+j));
+   }
+   }
+   I = simplify(I,2+4);
+   I = letplaceGBasis(I);
+   export(I);
+   if (baseringdef == 1) {setring save;}
+   return(R);
+   }
+
+proc TestGKAuslander3()
+{
+  ring r = (0,q),(z,x,y),(dp(1),dp(2));
+  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
+  R; setring R; // sets basering to Letterplace ring
+  ideal I;
+  I = q*x(1)*y(2) - y(1)*x(2), z(1)*y(2) - y(1)*z(2), z(1)*x(2) - x(1)*z(2);
+  I = letplaceGBasis(I);
+  lpGkDim(I); // must be 3
+  I = x(1)*y(2)*z(3) - y(1)*x(2), z(1)*y(2) - y(1)*z(2), z(1)*x(2) - x(1)*z(2);//gkDim = 2
+  I = letplaceGBasis(I); // not finite BUT contains a poly in x,y only
+  lpGkDim(I); // must be 4
+
+  ring r = 0,(y,x,z),dp;
+  def R = makeLetterplaceRing(10); // constructs a Letterplace ring
+  R; setring R; // sets basering to Letterplace ring
+  ideal I;
+  I = x(1)*y(2)*z(3) - y(1)*x(2), z(1)*y(2) - y(1)*z(2), z(1)*x(2) - x(1)*z(2);//gkDim = 2
+  I = letplaceGBasis(I); // computed as it would be homogenized; infinite
+  poly p = x(1)*y(2)*y(3)*x(4)-y(1)*x(2)*x(3)*y(4);
+  lpNF(p, I); // 0 as expected
+
+  // with inverse of z
+  ring r = 0,(iz,z,x,y),dp;
+  def R = makeLetterplaceRing(11); // constructs a Letterplace ring
+  R; setring R; // sets basering to Letterplace ring
+  ideal I;
+  I = x(1)*y(2)*z(3) - y(1)*x(2), z(1)*y(2) - y(1)*z(2), z(1)*x(2) - x(1)*z(2),
+    iz(1)*y(2) - y(1)*iz(2), iz(1)*x(2) - x(1)*iz(2), iz(1)*z(2)-1, z(1)*iz(2) -1;
+  I = letplaceGBasis(I); //
+  setring r;
+  def R2 = makeLetterplaceRing(23); // constructs a Letterplace ring
+  setring R2; // sets basering to Letterplace ring
+  ideal I = imap(R,I);
+  lpGkDim(I);
+
+
+  ring r = 0,(t,z,x,y),(dp(2),dp(2));
+  def R = makeLetterplaceRing(20); // constructs a Letterplace ring
+  R; setring R; // sets basering to Letterplace ring
+  ideal I;
+  I = x(1)*y(2)*z(3) - y(1)*x(2)*t(3), z(1)*y(2) - y(1)*z(2), z(1)*x(2) - x(1)*z(2),
+    t(1)*y(2) - y(1)*t(2), t(1)*x(2) - x(1)*t(2), t(1)*z(2) - z(1)*t(2);//gkDim = 2
+  I = letplaceGBasis(I); // computed as it would be homogenized; infinite
+  LIB "elim.lib";
+  ideal Inoz = nselect(I,intvec(2,6,10,14,18,22,26,30));
+  for(int i=1; i<=20; i++)
+  {
+    Inoz=subst(Inoz,t(i),1);
+  }
+  ideal J = x(1)*y(2)*y(3)*x(4)-y(1)*x(2)*x(3)*y(4);
+  J = letplaceGBasis(J);
+
+  poly p = x(1)*y(2)*y(3)*x(4)-y(1)*x(2)*x(3)*y(4);
+  lpNF(p, I); // 0 as expected
+
+  ring r2 = 0,(x,y),dp;
+  def R2 = makeLetterplaceRing(50); // constructs a Letterplace ring
+  setring R2;
+  ideal J = x(1)*y(2)*y(3)*x(4)-y(1)*x(2)*x(3)*y(4);
+  J = letplaceGBasis(J);
+}
+
 */
 
-/*
-  Here are some examples, which can also be found in [studzins]:
-
-  // takes up to 880Mb of memory
-  LIB "fpadim.lib";
-  ring r = 0,(x,y,z),dp;
-  int d =10; // degree
-  def R = makeLetterplaceRing(d);
-  setring R;
-  ideal I =
-  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);
-  option(prot);
-  option(redSB);option(redTail);option(mem);
-  ideal J = system("freegb",I,d,nvars(r));
-  lpDimCheck(J);
-  sickle(J,1,1,1,d); // dimension is 24872
-
-
-  LIB "fpadim.lib";
-  ring r = 0,(x,y,z),dp;
-  int d =10; // degree
-  def R = makeLetterplaceRing(d);
-  setring R;
-  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);
-  option(prot);
-  option(redSB);option(redTail);option(mem);
-  ideal J = system("freegb",I,d,3);
-  lpDimCheck(J);
-  sickle(J,1,1,1,d);
-*/
+
+/*   more tests : downup algebra A
+LIB "fpadim.lib";
+ring r = (0,a,b,g),(x,y),Dp;
+def R = makeLetterplaceRing(6); // constructs a Letterplace ring
+setring R;
+poly F1 = g*x(1);
+poly F2 = g*y(1);
+ideal J = x(1)*x(2)*y(3)-a*x(1)*y(2)*x(3) - b*y(1)*x(2)*x(3) - F1,
+x(1)*y(2)*y(3)-a*y(1)*x(2)*y(3) - b*y(1)*y(2)*x(3) - F2;
+J = letplaceGBasis(J);
+lpGkDim(J); // 3 == correct
+
+// downup algebra B
+LIB "fpadim.lib";
+ring r = (0,a,b,g, p(1..7),q(1..7)),(x,y),Dp;
+def R = makeLetterplaceRing(6); // constructs a Letterplace ring
+setring R;
+ideal imn = 1, y(1)*y(2)*y(3), x(1)*y(2), y(1)*x(2), x(1)*x(2), y(1)*y(2), x(1), y(1);
+int i;
+poly F1, F2;
+for(i=1;i<=7;i++)
+{
+F1 = F1 + p(i)*imn[i];
+F2 = F2 + q(i)*imn[i];
+}
+ideal J = x(1)*x(2)*y(3)-a*x(1)*y(2)*x(3) - b*y(1)*x(2)*x(3) - F1,
+x(1)*y(2)*y(3)-a*y(1)*x(2)*y(3) - b*y(1)*y(2)*x(3) - F2;
+J = letplaceGBasis(J);
+lpGkDim(J); // 3 == correct
+
+ */