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

///////////////////////////////////////////////////////
version="$Id: fpadim.lib,v beta 2010/09/27 13:14:51 studzins Exp $";
category="Noncommutative";
info="
LIBRARY: fpadim.lib     Algorithms for quotient algebras
AUTHORS: Grischa Studzinski,       grischa.studzinski@rwth-aachen.de

SUPPORT: Projects LE 2697/2-1; KR 1907/3-1 of the Priority Programme SPP 1489:
@* 'Algorithmische und Experimentelle Methoden in Algebra, Geometrie und Zahlentheorie'
@* of the German DFG

THEORY: Given the free 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, which 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. 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 normalform yet, but for our case it is not needed.
@*

REFERENCES:

@*   [ufna]     Ufnarovskij: Combinatorical and asymptotic methods in algebra,
@*                           1990
@*   [lls]      Levandovskyy, La Scala: Letterplace ideals and non-commutative
@*                                      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) holds
@*
@* In the procedures below, 'iv' stands for intvec representation
@* and 'lp' for the letterplace representation of monomials

MAIN PROCEDURES:

ivDHilbert(L,n[,d]);       computes the K-dimension and the Hilbert series
ivDHilbertSickle(L,n[,d]); computes mistletoes, K-dimension and Hilbert series
ivDimCheck(L,n);           checks if the K-dimension of A/<L> is infinite
ivHilbert(L,n[,d]);        computes the Hilbert series of A/<L> in intvec format
ivKDim(L,n[,d]);           computes the K-dimension of A/<L> in intvec format
ivMis2Dim(M);              computes the K-dimension of the factor algebra
ivOrdMisLex(M);            orders a list of intvecs lexicographically
ivSickle(L,n[,d]);         computes the mistletoes of A/<L> in intvec format
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
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
lpSickleHil(G[,d,n]);      computes the mistletoes and Hilbert series of A/<G>
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


AUXILIARY PROCEDURES:

ivL2lpI(L);           transforms a list of intvecs into an ideal of lp monomials
iv2lp(I);             transforms an intvec into the corresponding monomial 
iv2lpList(L);         transforms a list of intmats into an ideal of lp monomials
iv2lpMat(M);          transforms an intmat into an ideal of lp monomials
lp2iv(p);             transforms a polynomial into the corresponding intvec
lp2ivId(G);           transforms an ideal into the corresponding list of intmats
lpId2ivLi(G);         transforms a lp-ideal into the corresponding list of intvecs

SEE ALSO: freegb_lib
";

LIB "freegb.lib"; //for letterplace rings
LIB "general.lib";//for sorting mistletoes

/////////////////////////////////////////////////////////


//--------------- auxiliary procedures ------------------

static proc allVars(list L, intvec P, int n)
"USAGE: allVars(L,P,n); L a list of intmats, P an intvec, n an integer
RETURN: 0, if all variables are contained in the quotient algebra, 1 otherwise
"
{int i,j,r;
 intvec V;
 for (i = 1; i <= size(P); i++) {if (P[i] == 1){ j = i; break;}}
 V = L[j][1..nrows(L[j]),1];
 for (i = 1; i <= n; i++) {if (isInVec(i,V) == 0) {r = 1; break;}}
 if (r == 0) {return(1);}
 else {return(0);}
}

static proc checkAssumptions(int d, list L)
"PURPOSE: Checks, if all the Assumptions are holding
"
{if (typeof(attrib(basering,"isLetterplaceRing"))=="string") {ERROR("Basering is not a Letterplace ring!");}
 if (d > attrib(basering,"uptodeg")) {ERROR("Specified degree bound exceeds ring parameter!");}
 int i;
 for (i = 1; i <= size(L); i++)
 {if (entryViolation(L[i], attrib(basering,"lV")))
  {ERROR("Not allowed monomial/intvec found!");}
 }
 return();
}

static proc createStartMat(int d, int n)
"USAGE: createStartMat(d,n); d, n integers
RETURN: An intmat
PURPOSE:Creating the intmat with all normal monomials in n variables and of degree d to start with
NOTE:   d has to be > 0
"
{intmat M[(n^d)][d];
 int i1,i2,i3,i4;
 for (i1 = 1; i1 <= d; i1++)  //Spalten
 {i2 = 1; //durchlaeuft Zeilen
  while (i2 <= (n^d))
  {for (i3 = 1; i3 <= n; i3++)
   {for (i4 = 1; i4 <= (n^(i1-1)); i4++)
    {M[i2,i1] = i3;
     i2 = i2 + 1;
    }
   }
  }
 }
 return(M);
}

static proc createStartMat1(int n, intmat M)
"USAGE: createStartMat1(n,M); n an integer, M an intmat
RETURN: An intmat with all variables except those in M
"
{int i;
 intvec V,Vt;
 V = M[(1..nrows(M)),1];
 for (i = 1; i <= size(V); i++) {if (isInVec(i,V) == 0) {Vt = Vt,i;}}
 if (Vt == 0) {intmat S; return(S);}
 else {Vt = Vt[2..size(Vt)]; intmat S [size(Vt)][1]; S[1..size(Vt),1] = Vt; return(S);}
}

static proc entryViolation(intmat M, int n)
"PURPOSE:checks, if all entries in M are variable-related
"
{int i,j;
 for (i = 1; i <= nrows(M); i++)
 {for (j = 1; j <= ncols(M); j++)
  {if(!((1<=M[i,j])&&(M[i,j]<=n))) {return(1);}}
 }
 return(0);
}

static proc findDimen(intvec V, int n, list L, intvec P, list #)
"USAGE: findDimen(V,n,L,P,degbound); V,P intvecs, n, an integer, L a list,
@*      degbound an optional integer
RETURN: An integer
PURPOSE:Computing the K-dimension of the quotient algebra
"
{int degbound = 0;
 if (size(#) > 0) {if (#[1] > 0) {degbound = #[1];}}
 int dimen,i,j,w,it;
 intvec Vt,Vt2; 
 module M;
 if (degbound == 0)
 {for (i = 1; i <= n; i++)
  {Vt = V, i; w = 0;
   for (j = 1; j<= size(P); j++)
   {if (P[j] <= size(Vt))
    {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
     if (isInMat(Vt2,L[j]) > 0) {w = 1; break;}
    }
   }
    if (w == 0) 
    {vector Vtt;
     for (it = 1; it <= size(Vt); it++){Vtt = Vtt + Vt[it]*gen(it);}
     M = M,Vtt;
     kill Vtt;
    }
  }
  if (size(M) == 0) {return(0);}
  else
  {M = simplify(M,2); 
   for (i = 1; i <= size(M); i++)
   {kill Vt; intvec Vt;
    for (j =1; j <= size(M[i]); j++){Vt[j] =  int(leadcoef(M[i][j]));}
    dimen = dimen + 1 + findDimen(Vt,n,L,P);
   }
   return(dimen);
  }
 }
 else
 {if (size(V) > degbound) {ERROR("monomial exceeds degreebound");}
  if (size(V) == degbound) {return(0);}
  for (i = 1; i <= n; i++)
  {Vt = V, i; w = 0;
   for (j = 1; j<= size(P); j++)
   {if (P[j] <= size(Vt))
    {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
     if (isInMat(Vt2,L[j]) > 0) {w = 1; break;}
    }
   }
    if (w == 0) {vector Vtt;
     for (it = 1; it <= size(Vt); it++){Vtt = Vtt + Vt[it]*gen(it);}
     M = M,Vtt;
     kill Vtt;
    }
  }
  if (size(M) == 0) {return(0);}
  else
  {M = simplify(M,2); 
   for (i = 1; i <= size(M); i++)
   {kill Vt; intvec Vt;
    for (j =1; j <= size(M[i]); j++){Vt[j] =  int(leadcoef(M[i][j]));}
    dimen = dimen + 1 + findDimen(Vt,n,L,P,degbound);
   }
   return(dimen);
  }
 }
}

static proc findCycle(intvec V, list L, intvec P, int n, int ld, module M)
"USAGE:
RETURN: 1, if Ufn-graph contains a cycle, or 0 otherwise
PURPOSE:Searching the Ufnarovskij graph for cycles
"
{int i,j,w,r;intvec Vt,Vt2;
 int it, it2;
 if (size(V) < ld)
 {for (i = 1; i <= n; i++)
  {Vt = V,i; w = 0;
   for (j = 1; j <= size(P); j++)
   {if (P[j] <= size(Vt))
    {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
     if (isInMat(Vt2,L[j]) > 0)
     {w = 1; break;}
    }
   }
   if (w == 0) {r = findCycle(Vt,L,P,n,ld,M);}
   if (r == 1) {break;}
  }
  return(r);
 }
 else
 {j = size(M);
  if (j > 0)
  {
   intmat Mt[j][nrows(M)];
   for (it = 1; it <= j; it++)
   { for(it2 = 1; it2 <= nrows(M);it2++)
     {Mt[it,it2] = int(leadcoef(M[it2,it]));}
   }
   Vt = V[(size(V)-ld+1)..size(V)];
   //Mt; type(Mt);Vt;type(Vt);
   if (isInMat(Vt,Mt) > 0) {return(1);}
   else
   {vector Vtt;
    for (it =1; it <= size(Vt); it++)
     {Vtt = Vtt + Vt[it]*gen(it);}
    M = M,Vtt;
    kill Vtt;
    for (i = 1; i <= n; i++)
    {Vt = V,i; w = 0;
     for (j = 1; j <= size(P); j++)
     {if (P[j] <= size(Vt))
      {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
      //L[j]; type(L[j]);Vt2;type(Vt2);
       if (isInMat(Vt2,L[j]) > 0)
       {w = 1; break;}
      }
     }
     if (w == 0) {r = findCycle(Vt,L,P,n,ld,M);}
     if (r == 1) {break;}
    }
    return(r);
   }
  }
  else
  { Vt = V[(size(V)-ld+1)..size(V)];
    vector Vtt; 
    for (it = 1; it <= size(Vt); it++)
     {Vtt = Vtt + Vt[it]*gen(it);}
    M = Vtt;
    kill Vtt;
    for (i = 1; i <= n; i++)
    {Vt = V,i; w = 0;
     for (j = 1; j <= size(P); j++)
     {if (P[j] <= size(Vt))
      {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
      //L[j]; type(L[j]);Vt2;type(Vt2);
       if (isInMat(Vt2,L[j]) > 0)
       {w = 1; break;}
      }
     }
     if (w == 0) {r = findCycle(Vt,L,P,n,ld,M);} 
     if (r == 1) {break;}
    }
    return(r);
  }
 }
}

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
RETURN: An intvec
PURPOSE:Computing the coefficient of the Hilbert series (upto degree degbound)
NOTE:   Starting with a part of the Hilbert series we change the coefficient
@*      depending on how many baseelements we found on the actual branch 
"       
{int degbound = 0;
 if (size(#) > 0){if (#[1] > 0){degbound = #[1];}}
 int i,w,j,it;
 int h1 = 0;
 intvec Vt,Vt2,H1;
 module M; 
 if (degbound == 0)
 {for (i = 1; i <= n; i++)
  {Vt = V, i; w = 0;
   for (j = 1; j<= size(P); j++)
   {if (P[j] <= size(Vt))
    {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
     if (isInMat(Vt2,L[j]) > 0) {w = 1; break;}
    }
   }
    if (w == 0) 
    {vector Vtt;
     for (it = 1; it <= size(Vt); it++){Vtt = Vtt + Vt[it]*gen(it);}
     M = M,Vtt;
     kill Vtt;
    }
  }
  if (size(M) == 0) {return(H);}
  else
  {M = simplify(M,2);
   for (i = 1; i <= size(M); i++)
   {kill Vt; intvec Vt;
    for (j =1; j <= size(M[i]); j++) {Vt[j] =  int(leadcoef(M[i][j]));}
    h1 = h1 + 1; H1 = findHCoeff(Vt,n,L,P,H1);
   }
   if (size(H1) < (size(V)+2)) {H1[(size(V)+2)] = h1;}
   else {H1[(size(V)+2)] = H1[(size(V)+2)] + h1;}
   H1 = H1 + H;
   return(H1);
  }
 }
 else
 {if (size(V) > degbound) {ERROR("monomial exceeds degreebound");}
  if (size(V) == degbound) {return(H);}
  for (i = 1; i <= n; i++)
  {Vt = V, i; w = 0;
   for (j = 1; j<= size(P); j++)
   {if (P[j] <= size(Vt))
    {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
     if (isInMat(Vt2,L[j]) > 0) {w = 1; break;}
    }
   }
    if (w == 0)
    {vector Vtt;
     for (it = 1; it <= size(Vt); it++){Vtt = Vtt + Vt[it]*gen(it);}
     M = M,Vtt;
     kill Vtt;
    }
  }
  if (size(M) == 0) {return(H);}
  else
  {M = simplify(M,2);
   for (i = 1; i <= size(M); i++)
   {kill Vt; intvec Vt;
    for (j =1; j <= size(M[i]); j++)
     {Vt[j] =  int(leadcoef(M[i][j]));}
    h1 = h1 + 1; H1 = findHCoeff(Vt,n,L,P,H1,degbound);
   }
   if (size(H1) < (size(V)+2)) { H1[(size(V)+2)] = h1;}
   else {H1[(size(V)+2)] = H1[(size(V)+2)] + h1;}
   H1 = H1 + H;
   return(H1);
  }
 }
}

static proc findHCoeffMis(intvec V, int n, list L, intvec P, list R,list #)
"USAGE: findHCoeffMis(V,n,L,P,R,degbound); degbound an optional integer, L a
@*      list of Intmats, R
RETURN: A list
PURPOSE:Computing the coefficients of the Hilbert series and the Mistletoes all
@*      at once
"
{int degbound = 0;
 if (size(#) > 0) {if (#[1] > 0) {degbound = #[1];}}
 int i,w,j,h1;
 intvec Vt,Vt2,H1; int it;
 module M;
 if (degbound == 0)
 {for (i = 1; i <= n; i++)
  {Vt = V, i; w = 0;
   for (j = 1; j<= size(P); j++)
   {if (P[j] <= size(Vt))
    {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
     if (isInMat(Vt2,L[j]) > 0) {w = 1; break;}
    }
   }
    if (w == 0)
    {vector Vtt;
    for (it = 1; it <= size(Vt); it++){Vtt = Vtt + Vt[it]*gen(it);}
    M = M,Vtt;
    kill Vtt;
    }
  }
  if (size(M) == 0) {if (size(R) < 2){R[2] = list(V);} else {R[2] = R[2] + list(V);} return(R);}
  else
  {M = simplify(M,2);
   for (i = 1; i <= size(M); i++)
   {kill Vt; intvec Vt;
    for (j =1; j <= size(M[i]); j++)
     {Vt[j] =  int(leadcoef(M[i][j]));}
    if (size(R[1]) < (size(V)+2)) { R[1][(size(V)+2)] = 1;}
    else 
    {R[1][(size(V)+2)] = R[1][(size(V)+2)] + 1;}
    R = findHCoeffMis(Vt,n,L,P,R);
   }
   return(R);
  }
 }
 else
 {if (size(V) > degbound) {ERROR("monomial exceeds degreebound");}
  if (size(V) == degbound)
  {if (size(R) < 2){R[2] = list (V);}
   else{R[2] = R[2] + list (V);} 
   return(R);
  }
  for (i = 1; i <= n; i++)
  {Vt = V, i; w = 0;
   for (j = 1; j<= size(P); j++)
   {if (P[j] <= size(Vt))
    {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
     if (isInMat(Vt2,L[j]) > 0) {w = 1; break;}
    }
   }
    if (w == 0)
    {vector Vtt;
    for (it = 1; it <= size(Vt); it++){Vtt = Vtt + Vt[it]*gen(it);}
    M = M,Vtt;
    kill Vtt;
    }
  }
  if (size(M) == 0) {if (size(R) < 2){R[2] = list(V);} else {R[2] = R[2] + list(V);} return(R);}
  else
  {M = simplify(M,2);
    for (i = 1; i <= ncols(M); i++)
    {kill Vt; intvec Vt;
     for (j =1; j <= size(M[i]); j++)
     {Vt[j] =  int(leadcoef(M[i][j]));}
     if (size(R[1]) < (size(V)+2)) { R[1][(size(V)+2)] = 1;}
     else 
     {R[1][(size(V)+2)] = R[1][(size(V)+2)] + 1;}
     R = findHCoeffMis(Vt,n,L,P,R,degbound);
    }
   return(R);
  }
 }
}


static proc findMisDim(intvec V,int n,list L,intvec P,list R,list #)
"USAGE:
RETURN: A list
PURPOSE:Computing the K-dimension and the Mistletoes all at once
"
{int degbound = 0;
 if (size(#) > 0) {if (#[1] > 0) {degbound = #[1];}}
 int dimen,i,j,w;
 intvec Vt,Vt2; int it;
 module M;
 if (degbound == 0)
 {for (i = 1; i <= n; i++)
  {Vt = V, i; w = 0;
   for (j = 1; j<= size(P); j++)
   {if (P[j] <= size(Vt))
    {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
     if (isInMat(Vt2,L[j]) > 0) {w = 1; break;}
    }
   }
    if (w == 0) 
    {vector Vtt;
     for (it = 1; it <= size(Vt); it++){Vtt = Vtt + Vt[it]*gen(it);}
     M = M,Vtt;
     kill Vtt;
    }
  }
  if (size(M) == 0) 
  {if (size(R) < 2){R[2] = list (V);}
   else{R[2] = R[2] + list(V);} 
   return(R);
  }
  else
  {M = simplify(M,2);
   for (i = 1; i <= size(M); i++)
   {kill Vt; intvec Vt;
    for (j =1; j <= size(M[i]); j++){Vt[j] =  int(leadcoef(M[i][j]));}
     R[1] = R[1] + 1; R = findMisDim(Vt,n,L,P,R);
   }
   return(R);
  }
 }
 else
 {if (size(V) > degbound) {ERROR("monomial exceeds degreebound");}
  if (size(V) == degbound)
  {if (size(R) < 2){R[2] = list (V);}
   else{R[2] = R[2] + list (V);} 
   return(R);
  }
  for (i = 1; i <= n; i++)
  {Vt = V, i; w = 0;
   for (j = 1; j<= size(P); j++)
   {if (P[j] <= size(Vt))
    {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
     if (isInMat(Vt2,L[j]) > 0) {w = 1; break;}
    }
   }
    if (w == 0) 
    {vector Vtt;
     for (it = 1; it <= size(Vt); it++){Vtt = Vtt + Vt[it]*gen(it);}
     M = M,Vtt;
     kill Vtt;
    }
  }
  if (size(M) == 0) 
  {if (size(R) < 2){R[2] = list (V);}
   else{R[2] = R[2] + list(V);} 
   return(R);
  }
  else
  {M = simplify(M,2);
   for (i = 1; i <= size(M); i++)
   {kill Vt; intvec Vt;
    for (j =1; j <= size(M[i]); j++){Vt[j] =  int(leadcoef(M[i][j]));}
     R[1] = R[1] + 1; R = findMisDim(Vt,n,L,P,R,degbound);
   }
   return(R);

  }
 }
}


static proc findmistletoes(intvec V, int n, list L, intvec P, list #)
"USAGE: findmistletoes(V,n,L,P,degbound); V a normal word, n the number of
@*      variables, L the GB, P the occuring degrees,
@*      and degbound the (optional) degreebound
RETURN: A list
PURPOSE:Computing mistletoes starting in V
NOTE:   V has to be normal w.r.t. L, it will not be checked for being so
"
{int degbound = 0;
 if (size(#) > 0) {if (#[1] > 0) {degbound = #[1];}}
 list R; intvec Vt,Vt2; int it;
 int i,j;
 module M;
 if (degbound == 0)
 {int w;
  for (i = 1; i <= n; i++)
  {Vt = V,i; w = 0;
   for (j = 1; j <= size(P); j++)
   {if (P[j] <= size(Vt))
    {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
     if (isInMat(Vt2,L[j]) > 0)
     {w = 1; break;}
    }
   }
   if (w == 0)
   {vector Vtt;
    for (it = 1; it <= size(Vt); it++){Vtt = Vtt + Vt[it]*gen(it);}
    M = M,Vtt;
    kill Vtt;
   }
  }
  if (size(M)==0) {R = V; return(R);}
  else
  {M = simplify(M,2); 
   for (i = 1; i <= size(M); i++)
   {kill Vt; intvec Vt;
    for (j =1; j <= size(M[i]); j++){Vt[j] =  int(leadcoef(M[i][j]));}
    R = R + findmistletoes(Vt,n,L,P);
   }
   return(R);
  }
 }
 else
 {if (size(V) > degbound) {ERROR("monomial exceeds degreebound");}
  if (size(V) == degbound) {R = V; return(R);}
  int w;
  for (i = 1; i <= n; i++)
  {Vt = V,i; w = 0;
   for (j = 1; j <= size(P); j++)
   {if (P[j] <= size(Vt))
    {Vt2 = Vt[(size(Vt)-P[j]+1)..size(Vt)];
     if (isInMat(Vt2,L[j]) > 0){w = 1; break;}
    }
   }
   if (w == 0) 
   {vector Vtt;
    for (it = 1; it <= size(Vt); it++){Vtt = Vtt + Vt[it]*gen(it);}
    M = M,Vtt;
    kill Vtt;
   }
  } 
  if (size(M) == 0) {R = V; return(R);}
  else
  {M = simplify(M,2);
   for (i = 1; i <= ncols(M); i++)
   {kill Vt; intvec Vt;
    for (j =1; j <= size(M[i]); j++)
     {Vt[j] =  int(leadcoef(M[i][j]));}
      //Vt; typeof(Vt); size(Vt);
      R = R + findmistletoes(Vt,n,L,P,degbound);
   }
   return(R);
  }
 }
}

static proc isInList(intvec V, list L)
"USAGE: isInList(V,L); V an intvec, L a list of intvecs
RETURN: An integer
PURPOSE:Finding the position of V in L, returns 0, if V is not in M
"
{int i,n;
 n = 0;
 for (i = 1; i <= size(L); i++) {if (L[i] == V) {n = i; break;}}
 return(n);
}

static proc isInMat(intvec V, intmat M)
"USAGE: isInMat(V,M);V an intvec, M an intmat
RETURN: An integer
PURPOSE:Finding the position of V in M, returns 0, if V is not in M
"
{if (size(V) <> ncols(M)) {return(0);}
 int i;
 intvec Vt;
 for (i = 1; i <= nrows(M); i++)
 {Vt = M[i,1..ncols(M)];
  if ((V-Vt) == 0){return(i);}
 }
 return(0);
}

static proc isInVec(int v,intvec V)
"USAGE: isInVec(v,V); v an integer,V an intvec
RETURN: An integer
PURPOSE:Finding the position of v in V, returns 0, if v is not in V
"
{int i,n;
 n = 0;
 for (i = 1; i <= size(V); i++) {if (V[i] == v) {n = i; break;}}
 return(n);
}

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
ASSUME: - Intvec corresponds to a Letterplace monomial
@*      - basering has to be a Letterplace ring
EXAMPLE: example ivL2lpI; shows examples
"
{checkAssumptions(0,L);
 int i; ideal G;
 poly p;
 for (i = 1; i <= size(L); i++)
 {p = iv2lp(L[i]);
  G[(size(G) + 1)] = p;
 }
 return(G);
}
example
{
  "EXAMPLE:"; echo = 2;
  ring r = 0,(x,y,z),dp;
  def R = makeLetterplaceRing(5);// constructs a Letterplace ring
  setring R; //sets basering to Letterplace ring
  intvec u = 1,1,2; intvec v = 2,1,3; intvec w = 3,1,1; 
  // u = x^2y, v = yxz, w = zx^2 in intvec representation
  list L = u,v,w;
  ivL2lpI(L);// invokes the procedure, returns the ideal containing u,v,w
}

proc iv2lp(intvec I)
"USAGE: iv2lp(I); I an intvec
RETURN: poly
PURPOSE:Transforming an intvec into the corresponding Letterplace polynomial
ASSUME: - Intvec corresponds to a Letterplace monomial
@*      - basering has to be a Letterplace ring
NOTE:   - Assumptions will not be checked!
EXAMPLE: example iv2lp; shows examples
"
{if (I[1] == 0) {return(1);}
 int i = size(I);
 if (i > attrib(basering,"uptodeg")) {ERROR("polynomial exceeds degreebound");} 
 int j; poly p = 1;
 for (j = 1; j <= i; j++) {if (I[j] > 0) { p = lpMult(p,var(I[j]));}} //ignore zeroes, because they correspond to 1
 return(p);
}
example
{
  "EXAMPLE:"; echo = 2;
  ring r = 0,(x,y,z),dp;
  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
  setring R; //sets basering to Letterplace ring
  intvec u = 1,1,2; intvec v = 2,1,3; intvec w = 3,1,1; 
  // u = x^2y, v = yxz, w = zx^2 in intvec representation
  iv2lp(u); // invokes the procedure and returns the corresponding poly
  iv2lp(v);
  iv2lp(w);
}

proc iv2lpList(list L)
"USAGE: iv2lpList(L); L a list of intmats
RETURN: ideal
PURPOSE:Converting a list of intmats into an ideal of corresponding monomials
ASSUME: - The rows of each intmat in L must correspond to a Letterplace monomial
@*      - basering has to be a Letterplace ring
EXAMPLE: example iv2lpList; shows examples
"
{checkAssumptions(0,L);
 ideal G;
 int i;
 for (i = 1; i <= size(L); i++){G = G + iv2lpMat(L[i]);}
 return(G);
}
example
{
  "EXAMPLE:"; echo = 2;
  ring r = 0,(x,y,z),dp;
  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
  setring R; // sets basering to Letterplace ring
  intmat u[3][1] = 1,1,2; intmat v[1][3] = 2,1,3; intmat w[2][3] = 3,1,1,2,3,1;
  // defines intmats of different size containing intvec representations of
  // monomials as rows
  list L = u,v,w; 
  print(u); print(v); print(w); // shows the intmats contained in L
  iv2lpList(L); // returns the corresponding monomials as an ideal
}


proc iv2lpMat(intmat M)
"USAGE: iv2lpMat(M); M an intmat
RETURN: ideal
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
EXAMPLE: example iv2lpMat; shows examples
"
{list L = M;
 checkAssumptions(0,L);
 kill L;
 ideal G; poly p;
 int i; intvec I;
 for (i = 1; i <= nrows(M); i++)
  { I = M[i,1..ncols(M)];
    p = iv2lp(I);
    G[size(G)+1] = p;
  }
 return(G);
} 
example
{
  "EXAMPLE:"; echo = 2;
  ring r = 0,(x,y,z),dp;
  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
  setring R; // sets basering to Letterplace ring
  intmat u[3][1] = 1,1,2; intmat v[1][3] = 2,1,3; intmat w[2][3] = 3,1,1,2,3,1;
  // defines intmats of different size containing intvec representations of
  // monomials as rows
  iv2lpMat(u); // returns the monomials contained in u
  iv2lpMat(v); // returns the monomials contained in v
  iv2lpMat(w); // returns the monomials contained in w
}

proc lpId2ivLi(ideal G)
"USAGE: lpId2ivLi(G); G an ideal
RETURN: list
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;
 list M;
 checkAssumptions(0,M);
 for (i = 1; i <= size(G); i++) {M[i] = lp2iv(G[i]);}
 return(M);
}
example
{
  "EXAMPLE:"; echo = 2;
   ring r = 0,(x,y),dp;
   def R = makeLetterplaceRing(5); // constructs a Letterplace ring
   setring R; // sets basering to Letterplace ring
   ideal L = x(1)*x(2),y(1)*y(2),x(1)*y(2)*x(3);
   lpId2ivLi(L); // returns the corresponding intvecs as a list
}  

proc lp2iv(poly p)
"USAGE: lp2iv(p); p a poly
RETURN: intvec
PURPOSE:Transforming a monomial into the corresponding intvec
ASSUME: - basering has to be a Letterplace ring
NOTE:   - Assumptions will not be checked!
EXAMPLE: example lp2iv; shows examples
"
{p = normalize(lead(p));
 intvec I;
 int i,j;
 if (deg(p) > attrib(basering,"uptodeg")) {ERROR("Monomial exceeds degreebound");}
 if (p == 1) {return(I);}
 if (p == 0) {ERROR("Monomial is not allowed to equal zero");}
 intvec lep = leadexp(p);
 for ( i = 1; i <= attrib(basering,"lV"); i++) {if (lep[i] == 1) {I = i; break;}}
 for (i = (attrib(basering,"lV")+1); i <= size(lep); i++)
   {if (lep[i] == 1) 
    { j = (i mod attrib(basering,"lV")); 
      if (j == 0) {I = I,attrib(basering,"lV");}
      else {I = I,j;}
    }
    else { if (lep[i] > 1) {ERROR("monomial has a not allowed multidegree");}}
   }
 if (I[1] == 0) {ERROR("monomial has a not allowed multidegree");}

 return(I);
}
example
{
  "EXAMPLE:"; echo = 2;
  ring r = 0,(x,y,z),dp;
  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
  setring R; // sets basering to Letterplace ring
  poly p = x(1)*x(2)*z(3); poly q = y(1)*y(2)*x(3)*x(4);
  poly w= z(1)*y(2)*x(3)*z(4)*z(5);
  // p,q,w are some polynomials we want to transform into their 
  // intvec representation
  lp2iv(p); lp2iv(q); lp2iv(w);
}

proc lp2ivId(ideal G)
"USAGE: lp2ivId(G); G an ideal
RETURN: list
PURPOSE:Converting an ideal into an list of intmats,
@*      the corresponding intvecs forming the rows
ASSUME: - basering has to be a Letterplace ring
EXAMPLE: example lp2ivId; shows examples
"
{G = normalize(lead(G));
 intvec I; list L;
 checkAssumptions(0,L);
 int i,md;
 for (i = 1; i <= size(G); i++) { if (md <= deg(G[i])) {md = deg(G[i]);}} 
 while (size(G) > 0)
 {ideal Gt;
  for (i = 1; i <= ncols(G); i++) {if (md == deg(G[i])) {Gt = Gt + G[i]; G[i] = 0;}}
  if (size(Gt) > 0)
  {G = simplify(G,2);  
   intmat M [size(Gt)][md];
   for (i = 1; i <= size(Gt); i++) {M[i,1..md] = lp2iv(Gt[i]);}
   L = insert(L,M);
   kill M; kill Gt;
   md = md - 1;  
  }
  else {kill Gt; md = md - 1;} 
 }
 return(L);
}
example
{
  "EXAMPLE:"; echo = 2;
  ring r = 0,(x,y,z),dp;
  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
  setring R; // sets basering to Letterplace ring
  poly p = x(1)*x(2)*z(3); poly q = y(1)*y(2)*x(3)*x(4);
  poly w = z(1)*y(2)*x(3)*z(4);
  // p,q,w are some polynomials we want to transform into their 
  // intvec representation
  ideal G = p,q,w;
  // define the ideal containing p,q and w
  lp2ivId(G); // and return the list of intmats for this ideal
}

// -----------------main procedures----------------------

proc ivDHilbert(list L, int n, list #)
"USAGE: ivDHilbert(L,n[,degbound]); L a list of intmats, n an integer,
@*      degbound an optional integer
RETURN: list
PURPOSE:Computing the K-dimension and the Hilbert series
ASSUME: - basering is a Letterplace ring
@*      - all rows of each intmat correspond to a Letterplace monomial
@*      - if you specify a different degree bound degbound, 
@*        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
@*      Hilbert series
@*    - If degbound is set, there will be a degree bound added. By default there
@*      is no degree bound
@*    - n is the number of variables
@*    - If I = L[2] is the intvec returned, then I[k] is the (k-1)-th coefficient of
@*      the Hilbert series.
@*    - If the K-dimension is known to be infinite, a degree bound is needed
EXAMPLE: example ivDHilbert; shows examples
"
{int degbound = 0;
 if (size(#) > 0){if (typeof(#[1])=="int"){if (#[1] > 0){degbound = #[1];}}}
 checkAssumptions(degbound,L);
 intvec H; int i,dimen;
 H = ivHilbert(L,n,degbound);
 for (i = 1; i <= size(H); i++){dimen = dimen + H[i];}
 L = dimen,H;
 return(L);
}
example
{
  "EXAMPLE:"; echo = 2;
  ring r = 0,(x,y),dp;
  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
    R;
  setring R; // sets basering to Letterplace ring
  //some intmats, which contain monomials in intvec representation as rows
  intmat I1 [2][2] = 1,1,2,2; intmat I2 [1][3]  = 1,2,1;
  intmat J1 [1][2] =  1,1; intmat J2 [2][3] = 2,1,2,1,2,1;
  print(I1);
  print(I2);
  print(J1);
  print(J2);
  list G = I1,I2; // ideal, which is already a Groebner basis
  list I = J1,J2; // ideal, which is already a Groebner basis
  //the procedure without a degree bound
  ivDHilbert(G,2);
  // the procedure with degree bound 5
  ivDHilbert(I,2,5);
}

proc ivDHilbertSickle(list L, int n, list #)
"USAGE: ivDHilbertSickle(L,n[,degbound]); L a list of intmats, n an integer,
@*      degbound an optional integer
RETURN: list
PURPOSE:Computing K-dimension, Hilbert series and mistletoes
ASSUME: - basering is a Letterplace ring.
@*      - All rows of each intmat correspond to a Letterplace monomial.
@*      - If you specify a different degree bound degbound,
@*        degbound <= attrib(basering,uptodeg) holds.
NOTE: - If L is the list returned, then L[1] is an intvec which contains the
@*      coefficients of the Hilbert series, L[2] is an integer and L[3]
@*      is a list, containing the mistletoes as intvecs.
@*    - If degbound is set, a degree bound will be added. By default there
@*      is no degree bound.
@*    - n is the number of variables.
@*    - If I = L[1] is the intvec returned, then I[k] is the (k-1)-th
@*      coefficient of the Hilbert series.
@*    - If the K-dimension is known to be infinite, a degree bound is needed
EXAMPLE: example ivDHilbertSickle; shows examples
"
{int degbound = 0;
 if (size(#) > 0){if (typeof(#[1])=="int"){if (#[1] > 0){degbound = #[1];}}}
 checkAssumptions(degbound,L);
 int i,dimen; list R;
 R = ivSickleHil(L,n,degbound);
 for (i = 1; i <= size(R[1]); i++){dimen = dimen + R[1][i];}
 R[3] = R[2]; R[2] = dimen;
 return(R);
}
example
{
  "EXAMPLE:"; echo = 2;
  ring r = 0,(x,y),dp;
  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
  R;
  setring R; // sets basering to Letterplace ring
  //some intmats, which contain monomials in intvec representation as rows
  intmat I1 [2][2] = 1,1,2,2; intmat I2 [1][3]  = 1,2,1;
  intmat J1 [1][2] =  1,1; intmat J2 [2][3] = 2,1,2,1,2,1;
  print(I1);
  print(I2);
  print(J1);
  print(J2);
  list G = I1,I2;// ideal, which is already a Groebner basis
  list I = J1,J2; // ideal, which is already a Groebner basis
  ivDHilbertSickle(G,2); // invokes the procedure without a degree bound
  ivDHilbertSickle(I,2,3); // invokes the procedure with degree bound 3
}

proc ivDimCheck(list L, int n)
"USAGE: ivDimCheck(L,n); L a list of intmats, n an integer
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.
NOTE:   - n is the number of variables.
EXAMPLE: example ivDimCheck; shows examples
"
{checkAssumptions(0,L);
 int i,r;
 intvec P,H;
 for (i = 1; i <= size(L); i++) 
 {P[i] = ncols(L[i]);
  if (P[i] == 1) {if (isInMat(H,L[i]) > 0) {ERROR("Quotient algebra is trivial");}}
 }
 if (size(L) == 0) {ERROR("GB is empty, quotient algebra corresponds to free algebra");}
 kill H;
 intmat S; int sd,ld; intvec V;
 sd = P[1]; ld = P[1];
 for (i = 2; i <= size(P); i++) 
 {if (P[i] < sd) {sd = P[i];}
  if (P[i] > ld) {ld = P[i];}
 }
 sd = (sd - 1); ld = ld - 1;
 if (ld == 0) { return(allVars(L,P,n));}
 if (sd == 0) { for (i = 1; i <= size(L); i++){if (ncols(L[i]) == 1){S = createStartMat1(n,L[i]); break;}}}
 else {S = createStartMat(sd,n);}
 module M;
 for (i = 1; i <= nrows(S); i++)
 {V = S[i,1..ncols(S)];
  if (findCycle(V,L,P,n,ld,M)) {r = 1; break;}
 }
 return(r);
}
example
{
  "EXAMPLE:"; echo = 2;
  ring r = 0,(x,y),dp;
  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
  R;
  setring R; // sets basering to Letterplace ring
  //some intmats, which contain monomials in intvec representation as rows
  intmat I1 [2][2] = 1,1,2,2; intmat I2 [1][3]  = 1,2,1;
  intmat J1 [1][2] =  1,1; intmat J2 [2][3] = 2,1,2,1,2,1;
  print(I1);
  print(I2);
  print(J1);
  print(J2);
  list G = I1,I2;// ideal, which is already a Groebner basis
  list I = J1,J2; // ideal, which is already a Groebner basis and which
  ivDimCheck(G,2); // invokes the procedure, factor is of finite K-dimension
  ivDimCheck(I,2); // invokes the procedure, factor is not of finite K-dimension
}

proc ivHilbert(list L, int n, list #)
"USAGE: ivHilbert(L,n[,degbound]); L a list of intmats, n an integer,
@*      degbound an optional integer
RETURN: An intvec, containing the coefficients of the Hilbert series
PURPOSE:Computing the Hilbert series
ASSUME: - basering is a Letterplace ring.
@*      - all rows of each intmat correspond to a Letterplace monomial
@*      - if you specify a different degree bound degbound,
@*       degbound <= attrib(basering,uptodeg) holds.
NOTE: - If degbound is set, a degree bound  will be added. By default there
@*      is no degree bound.
@*    - n is the number of variables.
@*    - If I is returned, then I[k] is the (k-1)-th coefficient of the Hilbert
@*      series.
@*    - If the K-dimension is known to be infinite, a degree bound is needed
EXAMPLE: example ivHilbert; shows examples
"
{int degbound = 0;
 if (size(#) > 0) {if (typeof(#[1])=="int"){if (#[1] > 0) {degbound = #[1];}}}
 intvec P,H; int i;
 for (i = 1; i <= size(L); i++) 
 {P[i] = ncols(L[i]);
  if (P[i] == 1) {if ( isInMat(H,L[i]) > 0) {ERROR("Quotient algebra is trivial");}}
 }
 if (size(L) == 0) {ERROR("GB is empty, quotient algebra corresponds to free algebra");}
 H[1] = 1;
 checkAssumptions(degbound,L);
 if (degbound == 0)
 {int sd;  
  intmat S;
  sd = P[1];
  for (i = 2; i <= size(P); i++) {if (P[i] < sd) {sd = P[i];}}
  sd = (sd - 1); 
  if (sd == 0) { for (i = 1; i <= size(L); i++){if (ncols(L[i]) == 1){S = createStartMat1(n,L[i]); break;}}}
  else {S = createStartMat(sd,n);}
  if (intvec(S) == 0) {return(H);}
  for (i = 1; i <= sd; i++) {H = H,(n^i);}
  for (i = 1; i <= nrows(S); i++)
  {intvec St = S[i,1..ncols(S)]; 
   H = findHCoeff(St,n,L,P,H);
   kill St;
  }
  return(H); 
 }
 else
 {for (i = 1; i <= size(P); i++) 
  {if (P[i] > degbound) {ERROR("degreebound is too small, GB contains elements of higher degree");}}
  int sd;  
  intmat S;
  sd = P[1];
  for (i = 2; i <= size(P); i++) {if (P[i] < sd) {sd = P[i];}}
  sd = (sd - 1); 
  if (sd == 0) { for (i = 1; i <= size(L); i++){if (ncols(L[i]) == 1){S = createStartMat1(n,L[i]); break;}}}
  else {S = createStartMat(sd,n);}
  if (intvec(S) == 0) {return(H);}
  for (i = 1; i <= sd; i++) {H = H,(n^i);}
  for (i = 1; i <= nrows(S); i++)
  {intvec St = S[i,1..ncols(S)]; 
   H = findHCoeff(St,n,L,P,H,degbound);
   kill St;
  }
  return(H);   
 }
}
example
{
  "EXAMPLE:"; echo = 2;
  ring r = 0,(x,y),dp;
  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
  R;
  setring R; // sets basering to Letterplace ring
  //some intmats, which contain monomials in intvec representation as rows
  intmat I1 [2][2] = 1,1,2,2; intmat I2 [1][3]  = 1,2,1;
  intmat J1 [1][2] =  1,1; intmat J2 [2][3] = 2,1,2,1,2,1;
  print(I1);
  print(I2);
  print(J1);
  print(J2);
  list G = I1,I2; // ideal, which is already a Groebner basis
  list I = J1,J2; // ideal, which is already a Groebner basis
  ivHilbert(G,2); // invokes the procedure without any degree bound
  ivHilbert(I,2,5); // invokes the procedure with degree bound 5
}


proc ivKDim(list L, int n, list #)
"USAGE: ivKDim(L,n[,degbound]); L a list of intmats,
@*      n an integer, degbound an optional integer
RETURN: An integer, the K-dimension of A/<L>
PURPOSE:Computing the K-dimension of A/<L>
ASSUME: - basering is a Letterplace ring.
@*      - all rows of each intmat correspond to a Letterplace monomial
@*      - if you specify a different degree bound degbound,
@*        degbound <= attrib(basering,uptodeg) holds.
NOTE: - If degbound is set, a degree bound will be added. By default there
@*      is no degree bound.
@*    - n is the number of variables.
@*    - If the K-dimension is known to be infinite, a degree bound is needed
EXAMPLE: example ivKDim; shows examples
"
{int degbound = 0;
 if (size(#) > 0) {if (typeof(#[1])=="int"){if (#[1] > 0) {degbound = #[1];}}}
 intvec P,H; int i;
 for (i = 1; i <= size(L); i++) 
 {P[i] = ncols(L[i]);
  if (P[i] == 1) {if ( isInMat(H,L[i]) > 0) {ERROR("Quotient algebra is trivial");}}
 }
 if (size(L) == 0) {ERROR("GB is empty, quotient algebra corresponds to free algebra");}
 kill H;
 checkAssumptions(degbound,L);
 if (degbound == 0)
 {int sd; int dimen = 1; 
  intmat S;
  sd = P[1];
  for (i = 2; i <= size(P); i++) {if (P[i] < sd) {sd = P[i];}}
  sd = (sd - 1); 
  if (sd == 0) { for (i = 1; i <= size(L); i++){if (ncols(L[i]) == 1){S = createStartMat1(n,L[i]); break;}}}
  else {S = createStartMat(sd,n);}
  if (intvec(S) == 0) {return(dimen);}
  for (i = 1; i <= sd; i++) {dimen = dimen +(n^i);}
  for (i = 1; i <= nrows(S); i++)
  {intvec St = S[i,1..ncols(S)]; 
   dimen = dimen + findDimen(St,n,L,P);
   kill St;
  }
  return(dimen); 
 }
 else
 {for (i = 1; i <= size(P); i++) 
  {if (P[i] > degbound) {ERROR("degreebound is too small, GB contains elements of higher degree");}}
  int sd; int dimen = 1; 
  intmat S;
  sd = P[1];
  for (i = 2; i <= size(P); i++) {if (P[i] < sd) {sd = P[i];}}
  sd = (sd - 1); 
  if (sd == 0) { for (i = 1; i <= size(L); i++){if (ncols(L[i]) == 1){S = createStartMat1(n,L[i]); break;}}}
  else {S = createStartMat(sd,n);}
  if (intvec(S) == 0) {return(dimen);}
  for (i = 1; i <= sd; i++) {dimen = dimen +(n^i);}
  for (i = 1; i <= nrows(S); i++)
  {intvec St = S[i,1..ncols(S)]; 
   dimen = dimen + findDimen(St,n,L,P, degbound);
   kill St;
  }
  return(dimen);
 }
}
example
{
  "EXAMPLE:"; echo = 2;
  ring r = 0,(x,y),dp;
  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
  R;
  setring R; // sets basering to Letterplace ring
  //some intmats, which contain monomials in intvec representation as rows
  intmat I1 [2][2] = 1,1,2,2; intmat I2 [1][3]  = 1,2,1;
  intmat J1 [1][2] =  1,1; intmat J2 [2][3] = 2,1,2,1,2,1;
  print(I1);
  print(I2);
  print(J1);
  print(J2);
  list G = I1,I2; // ideal, which is already a Groebner basis
  list I = J1,J2; // ideal, which is already a Groebner basis
  ivKDim(G,2); // invokes the procedure without any degree bound
  ivKDim(I,2,5); // invokes the procedure with degree bound 5
}

proc ivMis2Dim(list M)
"USAGE: ivMis2Dim(M); M a list of intvecs
RETURN: An integer, the K-dimension of the given algebra
PURPOSE:Computing the K-dimension out of given mistletoes
ASSUME: - The mistletoes have to be ordered lexicographically -> OrdMisLex.
@*        Otherwise the returned value may differ from the K-dimension.
@*      - basering is a Letterplace ring.
EXAMPLE: example ivMis2Dim; shows examples
"
{checkAssumptions(0,M);
 intvec L;
 if (size(M) == 0){ERROR("There are no mistletoes, so it appears your dimension is infinite!");}
 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++)
  {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);
}
example
{
  "EXAMPLE:"; echo = 2;
   ring r = 0,(x,y),dp;
   def R = makeLetterplaceRing(5); // constructs a Letterplace ring
   R;
   setring R; // sets basering to Letterplace ring
   intvec i1 = 1,2; intvec i2 = 2,1,2;
   // the mistletoes are xy and yxy, which are already ordered lexicographically
   list L = i1,i2;
   ivMis2Dim(L); // returns the dimension of the factor algebra
}

proc ivOrdMisLex(list M)
"USAGE: ivOrdMisLex(M); M a list of intvecs
RETURN: A list, containing the ordered intvecs of M
PURPOSE:Orders a given set of mistletoes lexicographically
ASSUME: - basering is a Letterplace ring.
        - intvecs correspond to monomials
NOTE:   - This is preprocessing, it's not needed if the mistletoes are returned
@*        from the sickle algorithm.
@*      - Each entry of the list returned is an intvec.
EXAMPLE: example ivOrdMisLex; shows examples
"
{checkAssumptions(0,M);
 return(sort(M)[1]);
}
example
{
  "EXAMPLE:"; echo = 2;
   ring r = 0,(x,y),dp;
   def R = makeLetterplaceRing(5); // constructs a Letterplace ring
   setring R; // sets basering to Letterplace ring
   intvec i1 = 1,2,1; intvec i2 = 2,2,1; intvec i3 = 1,1; intvec i4 = 2,1,1,1;
   // the corresponding monomials are xyx,y^2x,x^2,yx^3
   list M = i1,i2,i3,i4;
   M;
   ivOrdMisLex(M);// orders the list of monomials
}

proc ivSickle(list L, int n, list #)
"USAGE: ivSickle(L,n,[degbound]); L a list of intmats, n an int, degbound an
@*      optional integer
RETURN: A list, containing intvecs, the mistletoes of A/<L>
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
@*      - if you specify a different degree bound degbound,
@*        degbound <= attrib(basering,uptodeg) holds.
NOTE: - If degbound is set, a degree bound will be added. By default there
@*      is no degree bound.
@*    - n is the number of variables.
@*    - If the K-dimension is known to be infinite, a degree bound is needed
EXAMPLE: example ivSickle; shows examples
"
{list M;
 int degbound = 0;
 if (size(#) > 0){if (typeof(#[1])=="int"){if (#[1] > 0){degbound = #[1];}}}
 int i;
 intvec P,H;
 for (i = 1; i <= size(L); i++) 
 {P[i] = ncols(L[i]);
  if (P[i] == 1) {if (isInMat(H,L[i]) > 0) {ERROR("Quotient algebra is trivial");}}
 }
 if (size(L) == 0) {ERROR("GB is empty, quotient algebra corresponds to free algebra");}
 kill H;
 checkAssumptions(degbound,L);
 if (degbound == 0)
 {intmat S; int sd;
  sd = P[1];
  for (i = 2; i <= size(P); i++) {if (P[i] < sd) {sd = P[i];}}
  sd = (sd - 1);
  if (sd == 0) { for (i = 1; i <= size(L); i++){if (ncols(L[i]) == 1){S = createStartMat1(n,L[i]); break;}}}
  else {S = createStartMat(sd,n);}
  if (intvec(S) == 0) {return(list (intvec(0)));}
  for (i = 1; i <= nrows(S); i++)
  {intvec St = S[i,1..ncols(S)]; 
   M = M + findmistletoes(St,n,L,P);
   kill St;
  }
  return(M);
 }
 else
 {for (i = 1; i <= size(P); i++) 
  {if (P[i] > degbound) {ERROR("degreebound is too small, GB contains elements of higher degree");}}
  intmat S; int sd;
  sd = P[1];
  for (i = 2; i <= size(P); i++) {if (P[i] < sd) {sd = P[i];}}
  sd = (sd - 1);
  if (sd == 0) { for (i = 1; i <= size(L); i++){if (ncols(L[i]) == 1){S = createStartMat1(n,L[i]); break;}}}
  else {S = createStartMat(sd,n);}
  if (intvec(S) == 0) {return(list (intvec(0)));}
  for (i = 1; i <= nrows(S); i++)
  {intvec St = S[i,1..ncols(S)]; 
   M = M + findmistletoes(St,n,L,P,degbound);
   kill St;
  }
  return(M);
 }
}
example
{
  "EXAMPLE:"; echo = 2;
  ring r = 0,(x,y),dp;
  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
  setring R; // sets basering to Letterplace ring
  //some intmats, which contain monomials in intvec representation as rows
  intmat I1 [2][2] = 1,1,2,2; intmat I2 [1][3]  = 1,2,1;
  intmat J1 [1][2] =  1,1; intmat J2 [2][3] = 2,1,2,1,2,1;
  print(I1);
  print(I2);
  print(J1);
  print(J2);
  list G = I1,I2; // ideal, which is already a Groebner basis
  list I =  J1,J2; // ideal, which is already a Groebner basis
  ivSickle(G,2); // invokes the procedure without any degree bound
  ivSickle(I,2,5); // invokes the procedure with degree bound 5
}

proc ivSickleDim(list L, int n, list #)
"USAGE: ivSickleDim(L,n[,degbound]); L a list of intmats, n an integer, degbound
@*      an optional integer
RETURN: A list
PURPOSE:Computing mistletoes and the K-dimension
ASSUME: - basering is a Letterplace ring.
@*      - all rows of each intmat correspond to a Letterplace monomial
@*      - if you specify a different degree bound degbound,
@*        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.
@*    - If degbound is set, a degree bound will be added. By default there
@*      is no degree bound.
@*    - n is the number of variables.
@*    - If the K-dimension is known to be infinite, a degree bound is needed
EXAMPLE: example ivSickleDim; shows examples
"
{list M;
 int degbound = 0;
 if (size(#) > 0){if (typeof(#[1])=="int"){if (#[1] > 0){degbound = #[1];}}}
 int i,dimen; list R;
 intvec P,H;
 for (i = 1; i <= size(L); i++) 
 {P[i] = ncols(L[i]);
  if (P[i] == 1) {if (isInMat(H,L[i]) > 0) {ERROR("Quotient algebra is trivial, dimension equals zero");}}
 }
 if (size(L) == 0) {ERROR("GB is empty, quotient algebra corresponds to free algebra");}
 kill H;
 checkAssumptions(degbound,L);
 if (degbound == 0)
 {int sd; dimen = 1; 
  intmat S;
  sd = P[1];
  for (i = 2; i <= size(P); i++) {if (P[i] < sd) {sd = P[i];}}
  sd = (sd - 1); 
  if (sd == 0) { for (i = 1; i <= size(L); i++){if (ncols(L[i]) == 1){S = createStartMat1(n,L[i]); break;}}}
  else {S = createStartMat(sd,n);}
  if (intvec(S) == 0) {return(list(dimen,list(intvec(0))));}
  for (i = 1; i <= sd; i++) {dimen = dimen +(n^i);}
  R[1] = dimen;
  for (i = 1; i <= nrows(S); i++)
  {intvec St = S[i,1..ncols(S)]; 
   R = findMisDim(St,n,L,P,R);
   kill St;
  }
  return(R); 
 }
 else
 {for (i = 1; i <= size(P); i++) 
  {if (P[i] > degbound) {ERROR("degreebound is too small, GB contains elements of higher degree");}}
  int sd; dimen = 1; 
  intmat S;
  sd = P[1];
  for (i = 2; i <= size(P); i++) {if (P[i] < sd) {sd = P[i];}}
  sd = (sd - 1); 
  if (sd == 0) { for (i = 1; i <= size(L); i++){if (ncols(L[i]) == 1){S = createStartMat1(n,L[i]); break;}}}
  else {S = createStartMat(sd,n);}
  if (intvec(S) == 0) {return(list(dimen,list(intvec(0))));}
  for (i = 1; i <= sd; i++) {dimen = dimen +(n^i);}
  R[1] = dimen;
  for (i = 1; i <= nrows(S); i++)
  {intvec St = S[i,1..ncols(S)]; 
   R = findMisDim(St,n,L,P,R,degbound);
   kill St;
  }
  return(R); 
 }
}
example
{
  "EXAMPLE:"; echo = 2;
  ring r = 0,(x,y),dp;
  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
  setring R; // sets basering to Letterplace ring
  //some intmats, which contain monomials in intvec representation as rows
  intmat I1 [2][2] = 1,1,2,2; intmat I2 [1][3]  = 1,2,1;
  intmat J1 [1][2] =  1,1; intmat J2 [2][3] = 2,1,2,1,2,1;
  print(I1);
  print(I2);
  print(J1);
  print(J2);
  list G = I1,I2;// ideal, which is already a Groebner basis
  list I =  J1,J2; // ideal, which is already a Groebner basis
  ivSickleDim(G,2); // invokes the procedure without any degree bound
  ivSickleDim(I,2,5); // invokes the procedure with degree bound 5
}

proc ivSickleHil(list L, int n, list #)
"USAGE:ivSickleHil(L,n[,degbound]); L a list of intmats, n an integer,
@*     degbound an optional integer
RETURN: A list
PURPOSE:Computing the mistletoes and the Hilbert series
ASSUME: - basering is a Letterplace ring.
@*      - all rows of each intmat correspond to a Letterplace monomial
@*      - if you specify a different degree bound degbound,
@*        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.
@*    - If degbound is set, a degree bound will be added. By default there
@*      is no degree bound.
@*    - n is the number of variables.
@*    - If I = L[1] is the intvec returned, then I[k] is the (k-1)-th
@*      coefficient of the Hilbert series.
@*    - If the K-dimension is known to be infinite, a degree bound is needed
EXAMPLE: example ivSickleHil; shows examples
"
{int degbound = 0;
 if (size(#) > 0) {if (typeof(#[1])=="int"){if (#[1] > 0) {degbound = #[1];}}}
 intvec P,H; int i; list R;
 for (i = 1; i <= size(L); i++) 
 {P[i] = ncols(L[i]);
  if (P[i] == 1) {if ( isInMat(H,L[i]) > 0) {ERROR("Quotient algebra is trivial");}}
 }
 if (size(L) == 0) {ERROR("GB is empty, quotient algebra corresponds to free algebra");}
 H[1] = 1;
 checkAssumptions(degbound,L);
 if (degbound == 0)
 {int sd;  
  intmat S;
  sd = P[1];
  for (i = 2; i <= size(P); i++) {if (P[i] < sd) {sd = P[i];}}
  sd = (sd - 1); 
  if (sd == 0) { for (i = 1; i <= size(L); i++){if (ncols(L[i]) == 1){S = createStartMat1(n,L[i]); break;}}}
  else {S = createStartMat(sd,n);}
  if (intvec(S) == 0) {return(list(H,list(intvec (0))));}
  for (i = 1; i <= sd; i++) {H = H,(n^i);}
  R[1] = H; kill H;
  for (i = 1; i <= nrows(S); i++)
  {intvec St = S[i,1..ncols(S)]; 
   R = findHCoeffMis(St,n,L,P,R);
   kill St;
  }
  return(R); 
 }
 else
 {for (i = 1; i <= size(P); i++) 
  {if (P[i] > degbound) {ERROR("degreebound is too small, GB contains elements of higher degree");}}
  int sd;  
  intmat S;
  sd = P[1];
  for (i = 2; i <= size(P); i++) {if (P[i] < sd) {sd = P[i];}}
  sd = (sd - 1); 
  if (sd == 0) { for (i = 1; i <= size(L); i++){if (ncols(L[i]) == 1){S = createStartMat1(n,L[i]); break;}}}
  else {S = createStartMat(sd,n);}
  if (intvec(S) == 0) {return(list(H,list(intvec(0))));}
  for (i = 1; i <= sd; i++) {H = H,(n^i);}
  R[1] = H; kill H;
  for (i = 1; i <= nrows(S); i++)
  {intvec St = S[i,1..ncols(S)]; 
   R = findHCoeffMis(St,n,L,P,R,degbound);
   kill St;
  }
  return(R); 
 }
}
example
{
  "EXAMPLE:"; echo = 2;
  ring r = 0,(x,y),dp;
  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
  setring R; // sets basering to Letterplace ring
  //some intmats, which contain monomials in intvec representation as rows
  intmat I1[2][2] = 1,1,2,2; intmat I2[1][3]  = 1,2,1;
  intmat J1[1][2] =  1,1; intmat J2[2][3] = 2,1,2,1,2,1;
  print(I1);
  print(I2);
  print(J1);
  print(J2);
  list G = I1,I2;// ideal, which is already a Groebner basis
  list I =  J1,J2; // ideal, which is already a Groebner basis
  ivSickleHil(G,2); // invokes the procedure without any degree bound
  ivSickleHil(I,2,5); // invokes the procedure with degree bound 5
}

proc lpDHilbert(ideal G, list #)
"USAGE: lpDHilbert(G[,degbound,n]); G an ideal, degbound, n optional integers
RETURN: A list
PURPOSE:Computing K-dimension and Hilbert series, starting with a lp-ideal
ASSUME: - basering is a Letterplace ring.
@*      - if you specify a different degree bound degbound,
@*        degbound <= attrib(basering,uptodeg) holds.
NOTE: - If L is the list returned, then L[1] is an integer, L[2] is an intvec.
@*    - If degbound is set, there will be a degree bound added. 0 means no
@*      degree bound. Default: attrib(basering,uptodeg).
@*    - n can be set to a different number of variables.
@*      Default: n = attrib(basering, lV).
@*    - If I = L[2] is the intvec returned, then I[k] is the (k-1)-th
@*      coefficient of the Hilbert series.
@*    - If the K-dimension is known to be infinite, a degree bound is needed
EXAMPLE: example lpDHilbert; shows examples
"
{int degbound = attrib(basering,"uptodeg");int n = attrib(basering, "lV");
 if (size(#) > 0){if (typeof(#[1])=="int"){if (#[1] >= 0){degbound = #[1];}}}
 if (size(#) > 1){if (typeof(#[1])=="int"){if (#[2] > 0){n = #[2];}}}
 list L;
 L = lp2ivId(normalize(lead(G)));
 return(ivDHilbert(L,n,degbound));
}
example
{
  "EXAMPLE:"; echo = 2;
  ring r = 0,(x,y),dp;
  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
  setring R; // sets basering to Letterplace ring
  ideal G = x(1)*x(2), y(1)*y(2),x(1)*y(2)*x(3); // ideal G contains a 
  //Groebner basis
  lpDHilbert(G,5,2); // invokes procedure with degree bound 5 and 2 variables
  // note that the optional parameters are not necessary, due to the finiteness
  // of the K-dimension of the factor algebra
  lpDHilbert(G); // procedure with ring parameters
  lpDHilbert(G,0); // procedure without degreebound
}

proc lpDHilbertSickle(ideal G, list #)
"USAGE: lpDHilbertSickle(G[,degbound,n]); G an ideal, degbound, n optional
@*      integers
RETURN: A list
PURPOSE:Computing K-dimension, Hilbert series and mistletoes at once
ASSUME: - basering is a Letterplace ring.
@*      - if you specify a different degree bound degbound,
@*        degbound <= attrib(basering,uptodeg) holds.
NOTE: - If L is the list returned, then L[1] is an intvec, the Hilbert series,
@*      L[2] is an integer, the K-dimension and L[3] is an ideal, the mistletoes
@*    - If degbound is set, there will be a degree bound added. 0 means no
@*      degree bound. Default: attrib(basering,uptodeg).
@*    - n can be set to a different number of variables.
@*      Default: n = attrib(basering, lV).
@*    - If I = L[1] is the intvec returned, then I[k] is the (k-1)-th
@*      coefficient of the Hilbert series.
@*    - If the K-dimension is known to be infinite, a degree bound is needed
EXAMPLE: example lpDHilbertSickle; shows examples
"
{int degbound = attrib(basering,"uptodeg");int n = attrib(basering, "lV");
 if (size(#) > 0){if (typeof(#[1])=="int"){if (#[1] >= 0){degbound = #[1];}}}
 if (size(#) > 1){if (typeof(#[1])=="int"){if (#[2] > 0){n = #[2];}}}
 list L;
 L = lp2ivId(normalize(lead(G)));
 L = ivDHilbertSickle(L,n,degbound);
 L[3] =  ivL2lpI(L[3]);
 return(L);
}
example
{
  "EXAMPLE:"; echo = 2;
  ring r = 0,(x,y),dp;
  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
  setring R; // sets basering to Letterplace ring
  ideal G = x(1)*x(2), y(1)*y(2),x(1)*y(2)*x(3); // ideal G contains a 
  //Groebner basis
  lpDHilbertSickle(G,5,2); //invokes procedure with degree bound 5 and 2 variables
  // note that the optional parameters are not necessary, due to the finiteness
  // of the K-dimension of the factor algebra
  lpDHilbert(G); // procedure with ring parameters
  lpDHilbert(G,0); // procedure without degreebound
}

proc lpHilbert(ideal G, list #)
"USAGE: lpHilbert(G[,degbound,n]); G an ideal, degbound, n optional integers
RETURN: An intvec, containing the coefficients of the Hilbert series
PURPOSE:Computing the Hilbert series
ASSUME: - basering is a Letterplace ring.
@*      - if you specify a different degree bound degbound,
@*        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).
@*    - n is the number of variables, which can be set to a different number.
@*      Default: attrib(basering, lV).
@*    - If I is returned, then I[k] is the (k-1)-th coefficient of the Hilbert
@*      series.
@*    - If the K-dimension is known to be infinite, a degree bound is needed
EXAMPLE: example lpHilbert; shows examples
"
{int degbound = attrib(basering,"uptodeg");int n = attrib(basering, "lV");
 if (size(#) > 0){if (typeof(#[1])=="int"){if (#[1] >= 0){degbound = #[1];}}}
 if (size(#) > 1){if (typeof(#[1])=="int"){if (#[2] > 0){n = #[2];}}}
 list L;
 L = lp2ivId(normalize(lead(G)));
 return(ivHilbert(L,n,degbound));
}
example
{
  "EXAMPLE:"; echo = 2;
  ring r = 0,(x,y),dp;
  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
  setring R; // sets basering to Letterplace ring
  ideal G = x(1)*x(2), y(1)*y(2),x(1)*y(2)*x(3); // ideal G contains a
  //Groebner basis
  lpHilbert(G,5,2); // invokes procedure with degree bound 5 and 2 variables
  // note that the optional parameters are not necessary, due to the finiteness
  // of the K-dimension of the factor algebra
  lpDHilbert(G); // procedure with ring parameters
  lpDHilbert(G,0); // procedure without degreebound
}

proc lpDimCheck(ideal G)
"USAGE: lpDimCheck(G);
RETURN: 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.
EXAMPLE: example lpDimCheck; shows examples
"
{int n = attrib(basering,"lV");
 list L;
 ideal R;
 R = normalize(lead(G));
 L = lp2ivId(R);
 return(ivDimCheck(L,n));
}
example
{
  "EXAMPLE:"; echo = 2;
  ring r = 0,(x,y),dp;
  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
  setring R; // sets basering to Letterplace ring
  ideal G = x(1)*x(2), y(1)*y(2),x(1)*y(2)*x(3);
  // Groebner basis
  ideal I = x(1)*x(2), y(1)*x(2)*y(3), x(1)*y(2)*x(3);
  // Groebner basis
  lpDimCheck(G); // invokes procedure, factor algebra is of finite K-dimension
  lpDimCheck(I); // invokes procedure, factor algebra is of infinite Kdimension
}

proc lpKDim(ideal G, list #)
"USAGE: lpKDim(G[,degbound, n]); G an ideal, degbound, n optional integers
RETURN: An integer, 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
@*      - if you specify a different degree bound degbound, 
@*        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).
@*    - n is the number of variables, which can be set to a different number.
@*      Default: attrib(basering, lV).
@*    - If the K-dimension is known to be infinite, a degree bound is needed
EXAMPLE: example lpKDim; shows examples
"
{int degbound = attrib(basering, "uptodeg");int n = attrib(basering, "lV");
 if (size(#) > 0){if (typeof(#[1])=="int"){if (#[1] >= 0){degbound = #[1];}}}
 if (size(#) > 1){if (typeof(#[1])=="int"){if (#[2] > 0){n = #[2];}}}
 list L;
 L = lp2ivId(normalize(lead(G)));
 return(ivKDim(L,n,degbound));
}
example
{
  "EXAMPLE:"; echo = 2;
  ring r = 0,(x,y),dp;
  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
  setring R; // sets basering to Letterplace ring
  ideal G = x(1)*x(2), y(1)*y(2),x(1)*y(2)*x(3);
  // ideal G contains a Groebner basis
  lpKDim(G); //procedure invoked with ring parameters
  // the factor algebra is finite, so the degree bound given by the Letterplace
  // ring is not necessary
  lpKDim(G,0); // procedure without any degree bound
}

proc lpMis2Dim(ideal M)
"USAGE: lpMis2Dim(M); M an ideal
RETURN: An integer, the K-dimension of the factor algebra
PURPOSE:Computing the K-dimension out of given mistletoes
ASSUME: - basering is a Letterplace ring.
@*      - M contains only monomials
NOTE:   - The mistletoes have to be ordered lexicographically -> OrdMisLex.
EXAMPLE: example lpMis2Dim; shows examples
"
{list L;
 L = lpId2ivLi(M);
 return(ivMis2Dim(L));
}
example
{
  "EXAMPLE:"; echo = 2;
   ring r = 0,(x,y),dp;
   def R = makeLetterplaceRing(5); // constructs a Letterplace ring
  setring R; // sets basering to Letterplace ring
   ideal L = x(1)*y(2),y(1)*x(2)*y(3);
   // ideal containing the mistletoes
   lpMis2Dim(L); // returns the K-dimension of the factor algebra
}

proc lpOrdMisLex(ideal M)
"USAGE: lpOrdMisLex(M); M an ideal of mistletoes
RETURN: An ideal, containing the mistletoes, ordered lexicographically
PURPOSE:A given set of mistletoes is ordered lexicographically
ASSUME: - basering is a Letterplace ring.
NOTE:   This is preprocessing, it is not needed if the mistletoes are returned
@*      from the sickle algorithm.
EXAMPLE: example lpOrdMisLex; shows examples
"
{return(ivL2lpI(sort(lpId2ivLi(M))[1]));}
example
{
  "EXAMPLE:"; echo = 2;
   ring r = 0,(x,y),dp;
   def R = makeLetterplaceRing(5); // constructs a Letterplace ring
   setring R; // sets basering to Letterplace ring
   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);
   // some monomials
   lpOrdMisLex(M); // orders the monomials lexicographically
}

proc lpSickle(ideal G,  list #)
"USAGE: lpSickle(G[,degbound,n]); G an ideal, degbound, n optional integers
RETURN: An ideal
PURPOSE:Computing the mistletoes of K[X]/<G>
ASSUME: - basering is a Letterplace ring.
@*      - if you specify a different degree bound degbound, 
@*        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).
@*    - n is the number of variables, which can be set to a different number.
@*      Default: attrib(basering, lV).
@*    - If the K-dimension is known to be infinite, a degree bound is needed
EXAMPLE: example lpSickle; shows examples
"
{int degbound = attrib(basering,"uptodeg"); int n = attrib(basering, "lV");
 if (size(#) > 0){if (typeof(#[1])=="int"){if (#[1] >= 0){degbound = #[1];}}}
 if (size(#) > 1){if (typeof(#[1])=="int"){if (#[2] > 0){n = #[2];}}}
 list L; ideal R;
 R = normalize(lead(G));
 L = lp2ivId(R);
 L = ivSickle(L,n,degbound);
 R = ivL2lpI(L);
 return(R);
}
example
{
  "EXAMPLE:"; echo = 2;
  ring r = 0,(x,y),dp;
  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
  setring R; // sets basering to Letterplace ring
  ideal G = x(1)*x(2), y(1)*y(2),x(1)*y(2)*x(3); // ideal G contains a
  //Groebner basis
  lpSickle(G); //invokes the procedure with ring parameters
  // the factor algebra is finite, so the degree bound given by the Letterplace
  // ring is not necessary
  lpSickle(G,0); // procedure without any degree bound
}

proc lpSickleDim(ideal G, list #)
"USAGE: lpSickleDim(G[,degbound,n]); G an ideal, degbound, n optional integers
RETURN: A list
PURPOSE:Computing the K-dimension and the mistletoes
ASSUME: - basering is a Letterplace ring.
@*      - if you specify a different degree bound degbound, 
@*        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.
@*    - If degbound is set, there will be a degree bound added. 0 means no
@*      degree bound. Default: attrib(basering,uptodeg).
@*    - n is the number of variables, which can be set to a different number.
@*      Default: attrib(basering, lV).
@*    - If the K-dimension is known to be infinite, a degree bound is needed
EXAMPLE: example lpSickleDim; shows examples
"
{int degbound = attrib(basering,"uptodeg");int n = attrib(basering, "lV");
 if (size(#) > 0){if (typeof(#[1])=="int"){if (#[1] >= 0){degbound = #[1];}}}
 if (size(#) > 1){if (typeof(#[1])=="int"){if (#[2] > 0){n = #[2];}}}
 list L;
 L = lp2ivId(normalize(lead(G)));
 L = ivSickleDim(L,n,degbound);
 L[2] = ivL2lpI(L[2]);
 return(L);
}
example
{
  "EXAMPLE:"; echo = 2;
  ring r = 0,(x,y),dp;
  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
  setring R; // sets basering to Letterplace ring
  ideal G = x(1)*x(2), y(1)*y(2),x(1)*y(2)*x(3); // ideal G contains a
  //Groebner basis
  lpSickleDim(G); // invokes the procedure with ring parameters
  // the factor algebra is finite, so the degree bound given by the Letterplace
  // ring is not necessary
  lpSickleDim(G,0); // procedure without any degree bound
}

proc lpSickleHil(ideal G, list #)
"USAGE: lpSickleHil(G);
RETURN: A list
PURPOSE:Computing the Hilbert series and the mistletoes
ASSUME: - basering is a Letterplace ring.
@*      - if you specify a different degree bound degbound, 
@*        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.
@*    - If degbound is set, there will be a degree bound added. 0 means no
@*      degree bound. Default: attrib(basering,uptodeg).
@*    - n is the number of variables, which can be set to a different number.
@*      Default: attrib(basering, lV).
@*    - If I = L[1] is the intvec returned, then I[k] is the (k-1)-th
@*      coefficient of the Hilbert series.
@*    - If the K-dimension is known to be infinite, a degree bound is needed
EXAMPLE: example lpSickleHil; shows examples
"
{int degbound = attrib(basering,"uptodeg");int n = attrib(basering, "lV");
 if (size(#) > 0){if (typeof(#[1])=="int"){if (#[1] >= 0){degbound = #[1];}}}
 if (size(#) > 1){if (typeof(#[1])=="int"){if (#[2] > 0){n = #[2];}}}
 list L;
 L = lp2ivId(normalize(lead(G)));
 L = ivSickleHil(L,n,degbound);
 L[2] =  ivL2lpI(L[2]);
 return(L);
}
example
{
  "EXAMPLE:"; echo = 2;
  ring r = 0,(x,y),dp;
  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
  setring R; // sets basering to Letterplace ring
  ideal G = x(1)*x(2), y(1)*y(2),x(1)*y(2)*x(3); // ideal G contains a
  //Groebner basis
  lpSickleHil(G); // invokes the procedure with ring parameters
  // the factor algebra is finite, so the degree bound given by the Letterplace
  // ring is not necessary
  lpSickleHil(G,0); // procedure without any degree bound
}

proc sickle(ideal G, list #)
"USAGE: sickle(G[,m, d, h, degbound]); G an ideal; m,d,h,degbound optional
@*      integers
RETURN: A list 
PURPOSE:Allowing the user to access all procs with one command
ASSUME: - basering is a Letterplace ring.
@*      - if you specify a different degree bound degbound, 
@*        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
@* case m=1,d=1,h=1: see lpDHilbertSickle
@* case m=1,d=1,h=0: see lpSickleDim
@* case m=1,d=0,h=1: see lpSickleHil
@* case m=1,d=0,h=0: see lpSickle (this is the default case)
@* case m=0,d=1,h=1: see lpDHilbert
@* case m=0,d=1,h=0: see lpKDim
@* case m=0,d=0,h=1: see lpHilbert
@* case m=0,d=0,h=0: returns an error
@*    - If degbound is set, there will be a degree bound added. 0 means no
@*      degree bound. Default: attrib(basering,uptodeg).
@*    - If the K-dimension is known to be infinite, a degree bound is needed
EXAMPLE: example sickle; shows examples
"
{int m,d,h,degbound;
 m = 1; d = 0; h = 0; degbound = attrib(basering,"uptodeg");
 if (size(#) > 0) {if (typeof(#[1])=="int"){if (#[1] < 1) {m = 0;}}}
 if (size(#) > 1) {if (typeof(#[1])=="int"){if (#[2] > 0) {d = 1;}}}
 if (size(#) > 2) {if (typeof(#[1])=="int"){if (#[3] > 0) {h = 1;}}}
 if (size(#) > 3) {if (typeof(#[1])=="int"){if (#[4] >= 0) {degbound = #[4];}}}
 if (m == 1)
 {if (d == 0)
  {if (h == 0) {return(lpSickle(G,degbound,attrib(basering,"lV")));}
   else        {return(lpSickleHil(G,degbound,attrib(basering,"lV")));}
  }
  else
  {if (h == 0) {return(lpSickleDim(G,degbound,attrib(basering,"lV")));}
   else {return(lpDHilbertSickle(G,degbound,attrib(basering,"lV")));}
  }
 }
 else
 {if (d == 0)
  {if (h == 0) {ERROR("You request to do nothing, so relax and do so");}
   else        {return(lpHilbert(G,degbound,attrib(basering,"lV")));}
  }
  else
  {if (h == 0) {return(lpKDim(G,degbound,attrib(basering,"lV")));}
   else {return(lpDHilbert(G,degbound,attrib(basering,"lV")));}
  }
 }
}
example
{
  "EXAMPLE:"; echo = 2;
  ring r = 0,(x,y),dp;
  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
  setring R; // sets basering to Letterplace ring
  ideal G = x(1)*x(2), y(1)*y(2),x(1)*y(2)*x(3);
  // G contains a Groebner basis
  sickle(G,1,1,1); // computes mistletoes, K-dimension and the Hilbert series
  sickle(G,1,0,0); // computes mistletoes only
  sickle(G,0,1,0); // computes K-dimension only
  sickle(G,0,0,1); // computes Hilbert series only
}

///////////////////////////////////////////////////////////////////////////////


proc tst_fpadim()
{
 example ivDHilbert;
 example ivDHilbertSickle;
 example ivDimCheck;
 example ivHilbert;
 example ivKDim;
 example ivMis2Dim;
 example ivOrdMisLex;
 example ivSickle;
 example ivSickleHil;
 example ivSickleDim;
 example lpDHilbert;
 example lpDHilbertSickle;
 example lpHilbert;
 example lpDimCheck;
 example lpKDim;
 example lpMis2Dim;
 example lpOrdMisLex;
 example lpSickle;
 example lpSickleHil;
 example lpSickleDim;
 example sickle;
 example ivL2lpI;
 example iv2lp;
 example iv2lpList;
 example iv2lpMat;
 example lp2iv;
 example lp2ivId;
 example lpId2ivLi;
}





/*
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);
*/