Changeset 578051 in git for Singular/LIB/fpadim.lib


Ignore:
Timestamp:
Dec 18, 2017, 4:15:00 PM (6 years ago)
Author:
Karim Abou Zeid <karim23697@…>
Branches:
(u'spielwiese', '5b153614cbc72bfa198d75b1e9e33dab2645d9fe')
Children:
909b29541ce0c334010bba6696154e22461eb5ce
Parents:
9b58b3fcc6a12daf4ea426458fac85c628277f67179aaba41255e379952db14e553b6a3df355202c
Message:
Merge branch 'spielwiese' into develop
File:
1 edited

Legend:

Unmodified
Added
Removed
  • Singular/LIB/fpadim.lib

    r179aaba r578051  
    44info="
    55LIBRARY: fpadim.lib     Algorithms for quotient algebras in the letterplace case
    6 AUTHORS: Grischa Studzinski,       grischa.studzinski@rwth-aachen.de
     6AUTHORS: Grischa Studzinski,       grischa.studzinski at rwth-aachen.de
     7@*       Viktor Levandovskyy,      viktor.levandovskyy at math.rwth-aachen.de
     8@*       Karim Abou Zeid,          karim.abou.zeid at rwth-aachen.de
    79
    810Support: Joint projects LE 2697/2-1 and KR 1907/3-1 of the Priority Programme SPP 1489:
    9 @* 'Algorithmische und Experimentelle Methoden in Algebra, Geometrie und Zahlentheorie'
    10 @* of the German DFG
    11 
    12 OVERVIEW: Given the free algebra A = K<x_1,...,x_n> and a (finite) Groebner basis
     11'Algorithmische und Experimentelle Methoden in Algebra, Geometrie und Zahlentheorie'
     12of the German DFG
     13and Project II.6 of the transregional collaborative research centre
     14SFB-TRR 195 'Symbolic Tools in Mathematics and their Application' of the German DFG
     15
     16OVERVIEW: Given the free associative algebra A = K<x_1,...,x_n> and a (finite) Groebner basis
    1317      GB = {g_1,..,g_w}, one is interested in the K-dimension and in the
    1418      explicit K-basis of A/<GB>.
    1519      Therefore one is interested in the following data:
    16 @*      - the Ufnarovskij graph induced by GB
    17 @*      - the mistletoes of A/<GB>
    18 @*      - the K-dimension of A/<GB>
    19 @*      - the Hilbert series of A/<GB>
    20 
    21       The Ufnarovskij graph is used to determine whether A/<GB> has finite
    22       K-dimension. One has to check if the graph contains cycles.
    23       For the whole theory we refer to [ufna]. Given a
    24       reduced set of monomials GB one can define the basis tree, whose vertex
    25       set V consists of all normal monomials w.r.t. GB. For every two
    26       monomials m_1, m_2 in V there is a direct edge from m_1 to m_2, if and
    27       only if there exists x_k in {x_1,..,x_n}, such that m_1*x_k = m_2. The
    28       set M = {m in V | there is no edge from m to another monomial in V} is
    29       called the set of mistletoes. As one can easily see it consists of
    30       the endpoints of the graph. Since there is a unique path to every
    31       monomial in V the whole graph can be described only from the knowledge
    32       of the mistletoes. Note that V corresponds to a basis of A/<GB>, so
    33       knowing the mistletoes we know a K-basis. The name mistletoes was given
    34       to those points because of these miraculous value and the algorithm is
    35       named sickle, because a sickle is the tool to harvest mistletoes.
    36       For more details see [studzins]. This package uses the Letterplace
    37       format introduced by [lls]. The algebra can either be represented as a
    38       Letterplace ring or via integer vectors: Every variable will only be
    39       represented by its number, so variable one is represented as 1,
    40       variable two as 2 and so on. The monomial x_1*x_3*x_2 for example will
    41       be stored as (1,3,2). Multiplication is concatenation. Note that there
    42       is no algorithm for computing the normal form needed for our case.
    43       Note that the name fpadim.lib is short for dimensions of finite
    44       presented algebras.
     20      - the Ufnarovskij graph induced by GB
     21      - the mistletoes of A/<GB> (special monomials in a basis)
     22      - the K-dimension of A/<GB>
     23      - the Hilbert series of A/<GB>
     24
     25@*      The Ufnarovskij graph is used to determine whether A/<GB> has finite
     26@*      K-dimension. One has to check if the graph contains cycles.
     27@*      For the whole theory we refer to [ufna]. Given a
     28@*      reduced set of monomials GB one can define the basis tree, whose vertex
     29@*      set V consists of all normal monomials w.r.t. GB. For every two
     30@*      monomials m_1, m_2 in V there is a direct edge from m_1 to m_2, if and
     31@*      only if there exists x_k in {x_1,..,x_n}, such that m_1*x_k = m_2. The
     32@*      set M = {m in V | there is no edge from m to another monomial in V} is
     33@*      called the set of mistletoes. As one can easily see it consists of
     34@*      the endpoints of the graph. Since there is a unique path to every
     35@*      monomial in V the whole graph can be described only from the knowledge
     36@*      of the mistletoes. Note that V corresponds to a basis of A/<GB>, so
     37@*      knowing the mistletoes we know a K-basis. The name mistletoes was given
     38@*      to those points because of these miraculous value and the algorithm is
     39@*      named sickle, because a sickle is the tool to harvest mistletoes.
     40@*      For more details see [studzins]. This package uses the Letterplace
     41@*      format introduced by [lls]. The algebra can either be represented as a
     42@*      Letterplace ring or via integer vectors: Every variable will only be
     43@*      represented by its number, so variable one is represented as 1,
     44@*      variable two as 2 and so on. The monomial x_1*x_3*x_2 for example will
     45@*      be stored as (1,3,2). Multiplication is concatenation. Note that the
     46@*      approach in this library does not need an algorithm for computing the normal
     47@*      form yet. Note that the name fpadim.lib is short for dimensions of
     48@*      finite presented algebras.
     49@*
    4550
    4651REFERENCES:
     
    4853@*   [ufna] Ufnarovskij: Combinatorical and asymptotic methods in algebra, 1990
    4954@*   [lls] Levandovskyy, La Scala: Letterplace ideals and non-commutative
    50           Groebner bases, 2009
     55Groebner bases, 2009
    5156@*   [studzins] Studzinski: Dimension computations in non-commutative,
    52                      associative algebras, Diploma thesis, RWTH Aachen, 2010
    53 
    54 Assumptions:
    55 @* - basering is always a Letterplace ring
    56 @* - all intvecs correspond to Letterplace monomials
    57 @* - if you specify a different degree bound d,
    58      d <= attrib(basering,uptodeg) should hold.
    59 @* In the procedures below, 'iv' stands for intvec representation
    60   and 'lp' for the letterplace representation of monomials
     57associative algebras, Diploma thesis, RWTH Aachen, 2010
     58
     59NOTE:
     60- basering is always a Letterplace ring
     61- all intvecs correspond to Letterplace monomials
     62- if you specify a different degree bound d, d <= attrib(basering,uptodeg) holds
     63
     64In the procedures below, 'iv' stands for intvec representation
     65and 'lp' for the letterplace representation of monomials
    6166
    6267PROCEDURES:
     
    8691sickle(G[,m,d,h]);         can be used to access all lp main procedures
    8792
    88 
    8993ivL2lpI(L);           transforms a list of intvecs into an ideal of lp monomials
    9094iv2lp(I);             transforms an intvec into the corresponding monomial
     
    145149    {for (i3 = 1; i3 <= n; i3++)
    146150      {for (i4 = 1; i4 <= (n^(i1-1)); i4++)
    147       {
    148         M[i2,i1] = i3;
     151        {M[i2,i1] = i3;
    149152          i2 = i2 + 1;
    150        }
     153        }
    151154      }
    152155    }
     
    170173"PURPOSE:checks, if all entries in M are variable-related
    171174"
    172 {if ((nrows(M) == 1) && (ncols(M) == 1)) {if (M[1,1] == 0){return(0);}}
    173  int i,j;
     175{int i,j;
    174176  for (i = 1; i <= nrows(M); i++)
    175177  {for (j = 1; j <= ncols(M); j++)
     
    328330}
    329331
     332
     333static proc findCycleDFS(int i, intmat T, intvec V)
     334"
     335PURPOSE:
     336this is a classical deep-first search for cycles contained in a graph given by an intmat
     337"
     338{
     339  intvec rV;
     340  int k,k1,t;
     341  int j = V[size(V)];
     342  if (T[j,i] > 0) {return(V);}
     343  else
     344  {
     345    for (k = 1; k <= ncols(T); k++)
     346    {
     347      t = 0;
     348      if (T[j,k] > 0)
     349      {
     350        for (k1 = 1; k1 <= size(V); k1++) {if (V[k1] == k) {t = 1; break;}}
     351        if (t == 0)
     352        {
     353          rV = V;
     354          rV[size(rV)+1] = k;
     355          rV = findCycleDFS(i,T,rV);
     356          if (rV[1] > -1) {return(rV);}
     357        }
     358      }
     359    }
     360  }
     361  return(intvec(-1));
     362}
     363
     364
     365
    330366static proc findHCoeff(intvec V,int n,list L,intvec P,intvec H,list #)
    331367"USAGE: findHCoeff(V,n,L,P,H,degbound); L a list of intmats, degbound an integer
     
    565601      }
    566602      return(R);
    567 
    568603    }
    569604  }
     
    647682}
    648683
     684static proc growthAlg(intmat T, list #)
     685"
     686real algorithm for checking the growth of an algebra
     687"
     688{
     689  int s = 1;
     690  if (size(#) > 0) { s = #[1];}
     691  int j;
     692  int n = ncols(T);
     693  intvec NV,C; NV[n] = 0; int m,i;
     694  intmat T2[n][n] = T[1..n,1..n]; intmat N[n][n];
     695  if (T2 == N)
     696  {
     697    for (i = 1; i <= n; i++)
     698    {
     699      if (m <  T[n+1,i]) { m = T[n+1,i];}
     700    }
     701    return(m);
     702  }
     703
     704  //first part: the diagonals
     705  for (i = s; i <= n; i++)
     706  {
     707    if (T[i,i] > 0)
     708    {
     709      if ((T[i,i] >= 1) && (T[n+1,i] > 0)) {return(-1);}
     710      if ((T[i,i] == 1) && (T[n+1,i] == 0))
     711      {
     712        T[i,i] = 0;
     713        T[n+1,i] = 1;
     714        return(growthAlg(T));
     715      }
     716    }
     717  }
     718
     719  //second part: searching for the last but one vertices
     720  T2 = T2*T2;
     721  for (i = s; i <= n; i++)
     722  {
     723    if ((intvec(T[i,1..n]) <> intvec(0)) && (intvec(T2[i,1..n]) == intvec(0)))
     724    {
     725      for (j = 1; j <= n; j++)
     726      {
     727        if ((T[i,j] > 0) && (m < T[n+1,j])) {m = T[n+1,j];}
     728      }
     729      T[n+1,i] = T[n+1,i] + m;
     730      T[i,1..n] = NV;
     731      return(growthAlg(T));
     732    }
     733  }
     734  m = 0;
     735
     736  //third part: searching for circles
     737  for (i = s; i <= n; i++)
     738  {
     739    T2 = T[1..n,1..n];
     740    C = findCycleDFS(i,T2, intvec(i));
     741    if (C[1] > 0)
     742    {
     743      for (j = 2; j <= size(C); j++)
     744      {
     745        T[i,1..n] = T[i,1..n] + T[C[j],1..n];
     746        T[C[j],1..n] = NV;
     747      }
     748      for (j = 2; j <= size(C); j++)
     749      {
     750        T[1..n,i] = T[1..n,i] + T[1..n,C[j]];
     751        T[1..n,C[j]] = NV;
     752      }
     753      T[i,i] = T[i,i] - size(C) + 1;
     754      m = 0;
     755      for (j = 1; j <= size(C); j++)
     756      {
     757        m = m + T[n+1,C[j]];
     758      }
     759      for (j = 1; j <= size(C); j++)
     760      {
     761        T[n+1,C[j]] = m;
     762      }
     763      return(growthAlg(T,i));
     764    }
     765    else {ERROR("No Cycle found, something seems wrong! Please contact the authors.");}
     766  }
     767
     768  m = 0;
     769  for (i = 1; i <= n; i++)
     770  {
     771    if (m < T[n+1,i])
     772    {
     773      m = T[n+1,i];
     774    }
     775  }
     776  return(m);
     777}
     778
     779static proc GlDimSuffix(intvec v, intvec g)
     780{
     781  //Computes the shortest r such that g is a suffix for vr
     782  //only valid for lex orderings?
     783  intvec r,gt,vt,lt,g2;
     784  int lg,lv,l,i,c,f;
     785  lg = size(g); lv = size(v);
     786  if (lg <= lv)
     787  {
     788    l = lv-lg;
     789  }
     790  else
     791  {
     792    l = 0; g2 = g[(lv+1)..lg];
     793    g = g[1..lv]; lg = size(g);
     794    c = 1;
     795  }
     796  while (l < lv)
     797  {
     798    vt = v[(l+1)..lv];
     799    gt = g[1..(lv-l)];
     800    lt = size(gt);
     801    for (i = 1; i <= lt; i++)
     802    {
     803      if (vt[i]<>gt[i]) {l++; break;}
     804    }
     805    if (lt <=i ) { f = 1; break;}
     806  }
     807  if (f == 0) {return(g);}
     808  r = g[(lv-l+1)..lg];
     809  if (c == 1) {r = r,g2;}
     810  return(r);
     811}
     812
     813static proc isNormal(intvec V, list G)
     814{
     815  int i,j,k,l;
     816  k = 0;
     817  for (i = 1; i <= size(G); i++)
     818  {
     819    if ( size(G[i]) <= size(V) )
     820    {
     821      while ( size(G[i])+k <= size(V) )
     822      {
     823        if ( G[i] == V[(1+k)..size(V)] ) {return(1);}
     824      }
     825    }
     826  }
     827  return(0);
     828}
     829
     830static proc findDChain(list L)
     831{
     832  list Li; int i,j;
     833  for (i = 1; i <= size(L); i++) {Li[i] = size(L[i]);}
     834  Li = sort(Li); Li = Li[1];
     835  return(Li[size(Li)]);
     836}
     837
    649838static proc isInList(intvec V, list L)
    650839"USAGE: isInList(V,L); V an intvec, L a list of intvecs
     
    684873}
    685874
     875
     876static proc isPF(intvec P, intvec I)
     877"
     878PURPOSE:
     879checks, if a word P is a praefix of another word I
     880"
     881{
     882  int n = size(P);
     883  if (n <= 0 || P == 0) {return(1);}
     884  if (size(I) < n) {return(0);}
     885  intvec IP = I[1..n];
     886  if (IP == P) {return(1);}
     887  else {return(0);}
     888}
     889
    686890proc ivL2lpI(list L)
    687891"USAGE: ivL2lpI(L); L a list of intvecs
    688892RETURN: ideal
    689 PURPOSE:Transforming a list of intvecs into an ideal of Letterplace monomials.
    690 @*      For the encoding of the variables see the overview.
     893PURPOSE:Transforming a list of intvecs into an ideal of Letterplace monomials
    691894ASSUME: - Intvec corresponds to a Letterplace monomial
    692895@*      - basering has to be a Letterplace ring
     896NOTE:   - Assumptions will not be checked!
    693897EXAMPLE: example ivL2lpI; shows examples
    694898"
    695 {checkAssumptions(0,L);
     899{
    696900  int i; ideal G;
    697901  poly p;
     
    718922RETURN: poly
    719923PURPOSE:Transforming an intvec into the corresponding Letterplace polynomial
    720 @*      For the encoding of the variables see the overview.
    721924ASSUME: - Intvec corresponds to a Letterplace monomial
    722925@*      - basering has to be a Letterplace ring
     
    748951RETURN: ideal
    749952PURPOSE:Converting a list of intmats into an ideal of corresponding monomials
    750 @*      The rows of the intmat corresponds to an intvec, which stores the
    751 @*      monomial.
    752 @*      For the encoding of the variables see the overview.
    753953ASSUME: - The rows of each intmat in L must correspond to a Letterplace monomial
    754954@*      - basering has to be a Letterplace ring
     
    779979"USAGE: iv2lpMat(M); M an intmat
    780980RETURN: ideal
    781 PURPOSE:Converting an intmat into an ideal of the corresponding monomials.
    782 @*      The rows of the intmat corresponds to an intvec, which stores the
    783 @*      monomial.
    784 @*      For the encoding of the variables see the overview.
     981PURPOSE:Converting an intmat into an ideal of the corresponding monomials
    785982ASSUME: - The rows of M must correspond to Letterplace monomials
    786983@*      - basering has to be a Letterplace ring
     
    8161013"USAGE: lpId2ivLi(G); G an ideal
    8171014RETURN: list
    818 PURPOSE:Transforming an ideal into the corresponding list of intvecs.
    819 @*      For the encoding of the variables see the overview.
     1015PURPOSE:Transforming an ideal into the corresponding list of intvecs
    8201016ASSUME: - basering has to be a Letterplace ring
    8211017EXAMPLE: example lpId2ivLi; shows examples
    8221018"
    823 {int i,j,k;
     1019{
     1020  int i,j,k;
    8241021  list M;
    8251022  checkAssumptions(0,M);
     
    8401037"USAGE: lp2iv(p); p a poly
    8411038RETURN: intvec
    842 PURPOSE:Transforming a monomial into the corresponding intvec.
    843 @*      For the encoding of the variables see the overview.
     1039PURPOSE:Transforming a monomial into the corresponding intvec
    8441040ASSUME: - basering has to be a Letterplace ring
    8451041NOTE:   - Assumptions will not be checked!
     
    8831079RETURN: list
    8841080PURPOSE:Converting an ideal into an list of intmats,
    885 @*      the corresponding intvecs forming the rows.
    886 @*      For the encoding of the variables see the overview.
     1081@*      the corresponding intvecs forming the rows
    8871082ASSUME: - basering has to be a Letterplace ring
    8881083EXAMPLE: example lp2ivId; shows examples
     
    9251120// -----------------main procedures----------------------
    9261121
     1122static proc lpGraphOfNormalWords(ideal G)
     1123"USAGE: lpGraphOfNormalWords(G); G a set of monomials in a letterplace ring
     1124RETURN: intmat
     1125PURPOSE: Constructs the graph of normal words induced by G
     1126@*:      the adjacency matrix of the graph of normal words induced by G
     1127ASSUME: - basering is a Letterplace ring
     1128- G are the leading monomials of a Groebner basis
     1129"
     1130{
     1131  // construct the Graph of normal words [Studzinski page 78]
     1132  // construct set of vertices
     1133  int v = attrib(basering,"lV"); int d = attrib(basering,"uptodeg");
     1134  ideal V; poly p,q,w;
     1135  ideal LG = lead(G);
     1136  int i,j,k,b; intvec E,Et;
     1137  for (i = 1; i <= v; i++){V = V, var(i);}
     1138  for (i = 1; i <= size(LG); i++)
     1139  {
     1140    E = leadexp(LG[i]);
     1141    if (E == intvec(0)) {V = V,monomial(intvec(0));}
     1142    else
     1143    {
     1144      for (j = 1; j < d; j++)
     1145      {
     1146        Et = E[(j*v+1)..(d*v)];
     1147        if (Et == intvec(0)) {break;}
     1148        else {V = V, monomial(Et);}
     1149      }
     1150    }
     1151  }
     1152  V = simplify(V,2+4);
     1153  printf("V = %p", V);
     1154
     1155
     1156  // construct incidence matrix
     1157
     1158  list LV = lpId2ivLi(V);
     1159  intvec Ip,Iw;
     1160  int n = size(V);
     1161  intmat T[n+1][n];
     1162  for (i = 1; i <= n; i++)
     1163  {
     1164    // printf("for1 (i=%p, n=%p)", i, n);
     1165    p = V[i]; Ip = lp2iv(p);
     1166    for (j = 1; j <= n; j++)
     1167    {
     1168      // printf("for2 (j=%p, n=%p)", j, n);
     1169      k = 1; b = 1;
     1170      q = V[j];
     1171      w = lpNF(lpMult(p,q),LG);
     1172      if (w <> 0)
     1173      {
     1174        Iw = lp2iv(w);
     1175        while (k <= n)
     1176        {
     1177          // printf("while (k=%p, n=%p)", k, n);
     1178          if (isPF(LV[k],Iw) > 0)
     1179          {if (isPF(LV[k],Ip) == 0) {b = 0; k = n+1;} else {k++;}
     1180          }
     1181          else {k++;}
     1182        }
     1183        T[i,j] = b;
     1184        //  print("Incidence Matrix:");
     1185        // print(T);
     1186      }
     1187    }
     1188  }
     1189  return(T);
     1190}
     1191
     1192// This proc is deprecated, see lpGkDim() in fpaprops.lib
     1193/* proc lpGkDim(ideal G) */
     1194/* "USAGE: lpGkDim(G); G an ideal in a letterplace ring */
     1195/* RETURN: int */
     1196/* PURPOSE: Determines the Gelfand Kirillov dimension of A/<G> */
     1197/* @*:     -1 means it is infinite */
     1198/* ASSUME: - basering is a Letterplace ring */
     1199/* - G is a Groebner basis */
     1200/* NOTE: see fpaprops.lib for a faster and more up to date version of this method */
     1201/* " */
     1202/* { */
     1203/*   return(growthAlg(lpGraphOfNormalWords(G))); */
     1204/* } */
     1205
    9271206proc ivDHilbert(list L, int n, list #)
    9281207"USAGE: ivDHilbert(L,n[,degbound]); L a list of intmats, n an integer,
     
    9321211ASSUME: - basering is a Letterplace ring
    9331212@*      - all rows of each intmat correspond to a Letterplace monomial
    934 @*        for the encoding of the variables see the overview
    9351213@*      - if you specify a different degree bound degbound,
    936 @*        degbound <= attrib(basering,uptodeg) should hold.
     1214@*        degbound <= attrib(basering,uptodeg) holds
    9371215NOTE: - If L is the list returned, then L[1] is an integer corresponding to the
    9381216@*      dimension, L[2] is an intvec which contains the coefficients of the
     
    9841262ASSUME: - basering is a Letterplace ring.
    9851263@*      - All rows of each intmat correspond to a Letterplace monomial.
    986 @*        for the encoding of the variables see the overview
    9871264@*      - If you specify a different degree bound degbound,
    988 @*        degbound <= attrib(basering,uptodeg) should hold.
     1265@*        degbound <= attrib(basering,uptodeg) holds.
    9891266NOTE: - If L is the list returned, then L[1] is an integer, L[2] is an intvec
    9901267@*      which contains the coefficients of the Hilbert series and L[3]
     
    10311308RETURN: int, 0 if the dimension is finite, or 1 otherwise
    10321309PURPOSE:Decides, whether the K-dimension is finite or not
    1033 ASSUME: - basering is a Letterplace ring
    1034 @*      - All rows of each intmat correspond to a Letterplace monomial
    1035 @*        For the encoding of the variables see the overview.
    1036 NOTE:   - n is the number of variables
     1310ASSUME: - basering is a Letterplace ring.
     1311@*      - All rows of each intmat correspond to a Letterplace monomial.
     1312NOTE:   - n is the number of variables.
    10371313EXAMPLE: example ivDimCheck; shows examples
    10381314"
     
    10901366ASSUME: - basering is a Letterplace ring.
    10911367@*      - all rows of each intmat correspond to a Letterplace monomial
    1092 @*        for the encoding of the variables see the overview
    10931368@*      - if you specify a different degree bound degbound,
    1094 @*       degbound <= attrib(basering,uptodeg) should hold.
     1369@*       degbound <= attrib(basering,uptodeg) holds.
    10951370NOTE: - If degbound is set, a degree bound  will be added. By default there
    10961371@*      is no degree bound.
     
    11761451ASSUME: - basering is a Letterplace ring.
    11771452@*      - all rows of each intmat correspond to a Letterplace monomial
    1178 @*        for the encoding of the variables see the overview
    11791453@*      - if you specify a different degree bound degbound,
    1180 @*        degbound <= attrib(basering,uptodeg) should hold.
     1454@*        degbound <= attrib(basering,uptodeg) holds.
    11811455NOTE: - If degbound is set, a degree bound will be added. By default there
    11821456@*      is no degree bound.
     
    12631537"
    12641538{
    1265 //checkAssumptions(0,M);
     1539  //checkAssumptions(0,M);
    12661540  intvec L,A;
    12671541  if (size(M) == 0){ERROR("There are no mistletoes, so it appears your dimension is infinite!");}
     
    12741548  for (i = 2; i <= size(M); i++)
    12751549  {A = M[i]; L = M[i-1];
    1276    s = size(A);
    1277    if (s > size(L))
    1278    {d = size(L);
    1279     for (j = s; j > d; j--) {Rt = insert(Rt,intvec(A[1..j]));}
    1280     A = A[1..d];
    1281    }
    1282    if (size(L) > s){L = L[1..s];}
    1283    while (A <> L)
    1284    {Rt = insert(Rt, intvec(A));
    1285     if (size(A) > 1)
    1286     {A = A[1..(size(A)-1)];
    1287      L = L[1..(size(L)-1)];
    1288     }
    1289     else {break;}
    1290    }
     1550    s = size(A);
     1551    if (s > size(L))
     1552    {d = size(L);
     1553      for (j = s; j > d; j--) {Rt = insert(Rt,intvec(A[1..j]));}
     1554      A = A[1..d];
     1555    }
     1556    if (size(L) > s){L = L[1..s];}
     1557    while (A <> L)
     1558    {Rt = insert(Rt, intvec(A));
     1559      if (size(A) > 1)
     1560      {A = A[1..(size(A)-1)];
     1561        L = L[1..(size(L)-1)];
     1562      }
     1563      else {break;}
     1564    }
    12911565  }
    12921566  return(Rt);
     
    13131587@*        Otherwise the returned value may differ from the K-dimension.
    13141588@*      - basering is a Letterplace ring.
    1315 @*      - mistletoes are stored as intvecs, as described in the overview
    13161589EXAMPLE: example ivMis2Dim; shows examples
    13171590"
     
    13211594  if (isInList(L,M) > 0) {print("1 is a mistletoe, therefore dim = 1"); return(1);}
    13221595  int i,j,d,s;
     1596  j = 1;
    13231597  d = 1 + size(M[1]);
    13241598  for (i = 1; i < size(M); i++)
    1325   {j = 1;
    1326    s = size(M[i]); if (s > size(M[i+1])){s = size(M[i+1]);}
    1327    while ((M[i][j] == M[i+1][j]) && (j <= s)){j = j + 1;}
    1328    d = d + size(M[i+1])- j + 1;
     1599  {s = size(M[i]); if (s > size(M[i+1])){s = size(M[i+1]);}
     1600    while ((M[i][j] == M[i+1][j]) && (j <= s)){j = j + 1;}
     1601    d = d + size(M[i+1])- j + 1;
    13291602  }
    13301603  return(d);
     
    13481621PURPOSE:Orders a given set of mistletoes lexicographically
    13491622ASSUME: - basering is a Letterplace ring.
    1350 @*      - intvecs correspond to monomials, as explained in the overview
     1623- intvecs correspond to monomials
    13511624NOTE:   - This is preprocessing, it's not needed if the mistletoes are returned
    13521625@*        from the sickle algorithm.
     
    13741647@*      optional integer
    13751648RETURN: list, containing intvecs, the mistletoes of A/<L>
    1376 PURPOSE:Computing the mistletoes for a given Groebner basis L, given by intmats
     1649PURPOSE:Computing the mistletoes for a given Groebner basis L
    13771650ASSUME: - basering is a Letterplace ring.
    13781651@*      - all rows of each intmat correspond to a Letterplace monomial
    1379 @*        as explained in the overview
    13801652@*      - if you specify a different degree bound degbound,
    1381 @*        degbound <= attrib(basering,uptodeg) should hold.
     1653@*        degbound <= attrib(basering,uptodeg) holds.
    13821654NOTE: - If degbound is set, a degree bound will be added. By default there
    13831655@*      is no degree bound.
     
    14571729ASSUME: - basering is a Letterplace ring.
    14581730@*      - all rows of each intmat correspond to a Letterplace monomial
    1459 @*        as explained in the overview
    14601731@*      - if you specify a different degree bound degbound,
    1461 @*        degbound <= attrib(basering,uptodeg) should hold.
     1732@*        degbound <= attrib(basering,uptodeg) holds.
    14621733NOTE: - If L is the list returned, then L[1] is an integer, L[2] is a list,
    14631734@*      containing the mistletoes as intvecs.
     
    15451816ASSUME: - basering is a Letterplace ring.
    15461817@*      - all rows of each intmat correspond to a Letterplace monomial
    1547 @*        as explained in the overview
    15481818@*      - if you specify a different degree bound degbound,
    1549 @*        degbound <= attrib(basering,uptodeg) should hold.
     1819@*        degbound <= attrib(basering,uptodeg) holds.
    15501820NOTE: - If L is the list returned, then L[1] is an intvec, L[2] is a list,
    15511821@*      containing the mistletoes as intvecs.
     
    16301900RETURN: list
    16311901PURPOSE:Computing K-dimension and Hilbert series, starting with a lp-ideal
    1632 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
     1902ASSUME: - basering is a Letterplace ring.
    16331903@*      - if you specify a different degree bound degbound,
    1634 @*        degbound <= attrib(basering,uptodeg) should hold.
     1904@*        degbound <= attrib(basering,uptodeg) holds.
    16351905NOTE: - If L is the list returned, then L[1] is an integer corresponding to the
    16361906@*      dimension, L[2] is an intvec which contains the coefficients of the
     
    16721942RETURN: list
    16731943PURPOSE:Computing K-dimension, Hilbert series and mistletoes at once
    1674 ASSUME: - basering is a Letterplace ring.  G is a Letterplace ideal.
     1944ASSUME: - basering is a Letterplace ring.
    16751945@*      - if you specify a different degree bound degbound,
    1676 @*        degbound <= attrib(basering,uptodeg) should hold.
     1946@*        degbound <= attrib(basering,uptodeg) holds.
    16771947NOTE: - If L is the list returned, then L[1] is an integer, the K-dimension,
    16781948@*      L[2] is an intvec, the Hilbert series and L[3] is an ideal,
     
    17151985RETURN: intvec, containing the coefficients of the Hilbert series
    17161986PURPOSE:Computing the Hilbert series
    1717 ASSUME: - basering is a Letterplace ring.  G is a Letterplace ideal.
     1987ASSUME: - basering is a Letterplace ring.
    17181988@*      - if you specify a different degree bound degbound,
    1719 @*        degbound <= attrib(basering,uptodeg) should hold.
     1989@*        degbound <= attrib(basering,uptodeg) holds.
    17201990NOTE: - If degbound is set, there will be a degree bound added. 0 means no
    17211991@*      degree bound. Default: attrib(basering,uptodeg).
     
    17532023RETURN: int, 1 if K-dimension of the factor algebra is infinite, 0 otherwise
    17542024PURPOSE:Checking a factor algebra for finiteness of the K-dimension
    1755 ASSUME: - basering is a Letterplace ring.  G is a Letterplace ideal.
     2025ASSUME: - basering is a Letterplace ring.
    17562026EXAMPLE: example lpDimCheck; shows examples
    17572027"
     
    17812051RETURN: int, the K-dimension of the factor algebra
    17822052PURPOSE:Computing the K-dimension of a factor algebra, given via an ideal
    1783 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
     2053ASSUME: - basering is a Letterplace ring
    17842054@*      - if you specify a different degree bound degbound,
    1785 @*        degbound <= attrib(basering,uptodeg) should hold.
     2055@*        degbound <= attrib(basering,uptodeg) holds.
    17862056NOTE: - If degbound is set, there will be a degree bound added. 0 means no
    17872057@*      degree bound. Default: attrib(basering, uptodeg).
     
    18402110RETURN: int, the K-dimension of the factor algebra
    18412111PURPOSE:Computing the K-dimension out of given mistletoes
    1842 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
     2112ASSUME: - basering is a Letterplace ring.
    18432113@*      - M contains only monomials
    18442114NOTE:   - The mistletoes have to be ordered lexicographically -> OrdMisLex.
     
    18642134RETURN: ideal, containing the mistletoes, ordered lexicographically
    18652135PURPOSE:A given set of mistletoes is ordered lexicographically
    1866 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
     2136ASSUME: - basering is a Letterplace ring.
    18672137NOTE:   This is preprocessing, it is not needed if the mistletoes are returned
    18682138@*      from the sickle algorithm.
     
    18852155RETURN: ideal
    18862156PURPOSE:Computing the mistletoes of K[X]/<G>
    1887 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
     2157ASSUME: - basering is a Letterplace ring.
    18882158@*      - if you specify a different degree bound degbound,
    1889 @*        degbound <= attrib(basering,uptodeg) should hold.
     2159@*        degbound <= attrib(basering,uptodeg) holds.
    18902160NOTE: - If degbound is set, there will be a degree bound added. 0 means no
    18912161@*      degree bound. Default: attrib(basering,uptodeg).
     
    19232193RETURN: list
    19242194PURPOSE:Computing the K-dimension and the mistletoes
    1925 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
     2195ASSUME: - basering is a Letterplace ring.
    19262196@*      - if you specify a different degree bound degbound,
    1927 @*        degbound <= attrib(basering,uptodeg) should hold.
     2197@*        degbound <= attrib(basering,uptodeg) holds.
    19282198NOTE: - If L is the list returned, then L[1] is an integer, the K-dimension,
    19292199@*      L[2] is an ideal, the mistletoes.
     
    19622232RETURN: list
    19632233PURPOSE:Computing the Hilbert series and the mistletoes
    1964 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
     2234ASSUME: - basering is a Letterplace ring.
    19652235@*      - if you specify a different degree bound degbound,
    1966 @*        degbound <= attrib(basering,uptodeg) should hold.
     2236@*        degbound <= attrib(basering,uptodeg) holds.
    19672237NOTE: - If L is the list returned, then L[1] is an intvec, corresponding to the
    19682238@*      Hilbert series, L[2] is an ideal, the mistletoes.
     
    20042274RETURN: list
    20052275PURPOSE:Allowing the user to access all procs with one command
    2006 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.
     2276ASSUME: - basering is a Letterplace ring.
    20072277@*      - if you specify a different degree bound degbound,
    2008 @*        degbound <= attrib(basering,uptodeg) should hold.
     2278@*        degbound <= attrib(basering,uptodeg) holds.
    20092279NOTE:   The returned object will always be a list, but the entries of the
    20102280@*      returned list may be very different
     
    20622332  sickle(G,0,0,1); // computes Hilbert series only
    20632333}
     2334
     2335proc ivMaxIdeal(int l, int lonly)
     2336  "USAGE: lpMaxIdeal(l, lonly); l an integer, lonly an integer
     2337  RETURN: list
     2338  PURPOSE: computes a list of free monomials in intvec presentation
     2339  @*       with length <= l
     2340  @*       if donly <> 0, only monomials of degree d are returned
     2341  ASSUME: - basering is a Letterplace ring.
     2342  NOTE: see also lpMaxIdeal()
     2343  "
     2344{
     2345  if (l < 0) {
     2346    ERROR("l must not be negative")
     2347  }
     2348  list words;
     2349  if (l == 0) {
     2350     words = 0;
     2351     return (words);
     2352  }
     2353  int lV = attrib(basering, "lV"); // variable count
     2354  list prevWords;
     2355  if (l > 1) {
     2356    prevWords = ivMaxIdeal(l - 1, lonly);
     2357  } else {
     2358    prevWords = 0;
     2359  }
     2360  for (int i = 1; i <= size(prevWords); i++) {
     2361    if (size(prevWords[i]) >= l - 1) {
     2362      for (int j = 1; j <= lV; j++) {
     2363        intvec word = prevWords[i];
     2364        word[l] = j;
     2365        words = insert(words, word);
     2366        kill word;
     2367      } kill j;
     2368    }
     2369  } kill i;
     2370  if (!lonly && l > 1) {
     2371    words = prevWords + words;
     2372  }
     2373  return (words);
     2374}
     2375example {
     2376  "EXAMPLE:"; echo = 2;
     2377  ring r = 0,(a,b,c),dp;
     2378  def R = makeLetterplaceRing(7); setring R;
     2379  ivMaxIdeal(1,0);
     2380  ivMaxIdeal(2,0);
     2381  ivMaxIdeal(2,1);
     2382  ivMaxIdeal(4,0);
     2383  ivMaxIdeal(4,1);
     2384}
     2385
     2386proc lpMaxIdeal(int d, int donly)
     2387  "USAGE: lpMaxIdeal(d, donly); d an integer, donly an integer
     2388  RETURN: ideal
     2389  PURPOSE: computes a list of free monomials of degree at most d
     2390  @*       if donly <> 0, only monomials of degree d are returned
     2391  ASSUME: - basering is a Letterplace ring.
     2392  @*      - d <= attrib(basering,uptodeg) holds.
     2393  NOTE: analogous to maxideal(d) in the commutative case
     2394  "
     2395{
     2396  ivL2lpI(ivMaxIdeal(d, donly));
     2397}
     2398example {
     2399  "EXAMPLE:"; echo = 2;
     2400  ring r = 0,(a,b,c),dp;
     2401  def R = makeLetterplaceRing(7); setring R;
     2402  lpMaxIdeal(1,0);
     2403  lpMaxIdeal(2,0);
     2404  lpMaxIdeal(2,1);
     2405  lpMaxIdeal(4,0);
     2406  lpMaxIdeal(4,1);
     2407}
     2408
     2409proc monomialBasis(int d, int donly, ideal J)
     2410  "USAGE: monomialBasis(d, donly, J); d, donly integers, J an ideal
     2411  RETURN: ideal
     2412  PURPOSE: computes a list of free monomials in a Letterplace
     2413  @*       basering R of degree at most d and not contained in <LM(J)>
     2414  @*       if donly <> 0, only monomials of degree d are returned
     2415  ASSUME: - basering is a Letterplace ring.
     2416  @*      - d <= attrib(basering,uptodeg) holds.
     2417  @*      - J is a Groebner basis
     2418  "
     2419{
     2420  int nv = attrib(basering,"uptodeg");
     2421  if ((d>nv) || (d<0) )
     2422  {
     2423    ERROR("incorrect degree");
     2424  }
     2425  nv = attrib(basering,"lV"); // nvars
     2426  if (d==0)
     2427  {
     2428    return(ideal(1));
     2429  }
     2430  /* from now on d>=1 */
     2431  ideal I;
     2432  if (size(J)==0)
     2433  {
     2434    I = lpMaxIdeal(d,donly);
     2435    if (!donly)
     2436    {
     2437      // append 1 as the first element; d>=1
     2438      I = 1, I;
     2439    }
     2440    return( I );
     2441  }
     2442  // ok, Sickle misbehaves: have to remove all
     2443  // elts from J of degree >d
     2444  ideal JJ;
     2445  int j; int sj = ncols(J);
     2446  int cnt=0;
     2447  for(j=1;j<=sj;j++)
     2448  {
     2449    if (deg(J[j]) <= d)
     2450    {
     2451      cnt++;
     2452      JJ[cnt]=lead(J[j]); // only LMs are needed
     2453    }
     2454  }
     2455  if (cnt==0)
     2456  {
     2457    // there are no elements in J of degree <= d
     2458    // return free stuff and the 1
     2459    I = monomialBasis(d, donly, std(0));
     2460    if (!donly)
     2461    {
     2462      I = 1, I;
     2463    }
     2464    return(I);
     2465  }
     2466  // from here on, Ibase is not zero
     2467  ideal Ibase = lpMis2Base(lpSickle(JJ,d)); // the complete K-basis modulo J up to d
     2468  if (!donly)
     2469  {
     2470    // for not donly, give everything back
     2471    // sort by DP starting with smaller terms
     2472    Ibase = sort(Ibase,"Dp")[1];
     2473    return(Ibase);
     2474  }
     2475  /* !donly: pick out only monomials of degree d */
     2476  int i; int si = ncols(Ibase);
     2477  cnt=0;
     2478  I=0;
     2479  for(i=1;i<=si;i++)
     2480  {
     2481    if (deg(Ibase[i]) == d)
     2482    {
     2483      cnt++;
     2484      I[cnt]=Ibase[i];
     2485    }
     2486  }
     2487  kill Ibase;
     2488  return(I);
     2489}
     2490example {
     2491  "EXAMPLE:"; echo = 2;
     2492  ring r = 0,(x,y),dp;
     2493  def R = makeLetterplaceRing(7); setring R;
     2494  ideal J = x(1)*y(2)*x(3) - y(1)*x(2)*y(3);
     2495  option(redSB); option(redTail);
     2496  J = letplaceGBasis(J);
     2497  J;
     2498  monomialBasis(2,1,std(0));
     2499  monomialBasis(2,0,std(0));
     2500  monomialBasis(3,1,J);
     2501  monomialBasis(3,0,J);
     2502}
     2503
     2504
     2505///////////////////////////////////////////////////////////////////////////////
     2506/* vl: stuff for conversion to Magma and to SD
     2507todo: doc, example
     2508 */
     2509static proc extractVars(r)
     2510{
     2511  int i = 1;
     2512  int j = 1;
     2513  string candidate;
     2514  list result = list();
     2515  for (i = 1; i<=nvars(r);i++)
     2516  {
     2517    candidate = string(var(i))[1,find(string(var(i)),"(")-1];
     2518    if (!inList(result, candidate))
     2519    {
     2520      result = insert(result,candidate,size(result));
     2521    }
     2522  }
     2523  return(result);
     2524}
     2525
     2526static proc letterPlacePoly2MagmaString(poly h)
     2527{
     2528  int pos;
     2529  string s = string(h);
     2530  while(find(s,"("))
     2531  {
     2532    pos = find(s,"(");
     2533    while(s[pos]!=")")
     2534    {
     2535      s = s[1,pos-1]+s[pos+1,size(s)-pos];
     2536    }
     2537    if (size(s)!=pos)
     2538    {
     2539      s = s[1,pos-1]+s[pos+1,size(s)-pos]; // The last (")")
     2540    }
     2541    else
     2542    {
     2543      s = s[1,pos-1];
     2544    }
     2545  }
     2546  return(s);
     2547}
     2548
     2549static proc letterPlaceIdeal2SD(ideal I, int upToDeg)
     2550{
     2551  int i;
     2552  print("Don't forget to fill in the formal Data in the file");
     2553  string result = "<?xml version=\"1.0\"?>"+newline+"<FREEALGEBRA createdAt=\"\" createdBy=\"Singular\" id=\"FREEALGEBRA/\">"+newline;
     2554  result = result + "<vars>"+string(extractVars(basering))+"</vars>"+newline;
     2555  result = result + "<basis>"+newline;
     2556  for (i = 1;i<=size(I);i++)
     2557  {
     2558    result = result + "<poly>"+letterPlacePoly2MagmaString(I[i])+"</poly>"+newline;
     2559  }
     2560  result = result + "</basis>"+newline;
     2561  result = result + "<uptoDeg>"+ string(upToDeg)+"</uptoDeg>"+newline;
     2562  result = result + "<Comment></Comment>"+newline;
     2563  result = result + "<Version></Version>"+newline;
     2564  result = result + "</FREEALGEBRA>";
     2565  return(result);
     2566}
     2567
    20642568
    20652569///////////////////////////////////////////////////////////////////////////////
     
    20982602  example lp2ivId;
    20992603  example lpId2ivLi;
    2100 }
    2101 
    2102 
    2103 
    2104 
     2604  example lpSubstitute;
     2605}
    21052606
    21062607/*
    2107   Here are some examples one may try. Just copy them into your console.
    2108   These are relations for braid groups, up to degree d:
    2109 
    2110 
    2111   LIB "fpadim.lib";
    2112   ring r = 0,(x,y,z),dp;
    2113   int d =10; // degree
    2114   def R = makeLetterplaceRing(d);
    2115   setring R;
    2116   ideal I = y(1)*x(2)*y(3) - z(1)*y(2)*z(3), x(1)*y(2)*x(3) - z(1)*x(2)*y(3),
    2117   z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) + y(1)*y(2)*y(3) +
    2118   z(1)*z(2)*z(3) + x(1)*y(2)*z(3);
    2119   option(prot);
    2120   option(redSB);option(redTail);option(mem);
    2121   ideal J = system("freegb",I,d,3);
    2122   lpDimCheck(J);
    2123   sickle(J,1,1,1,d);//Computes mistletoes, K-dimension and the Hilbert series
    2124 
    2125 
    2126 
    2127   LIB "fpadim.lib";
    2128   ring r = 0,(x,y,z),dp;
    2129   int d =11; // degree
    2130   def R = makeLetterplaceRing(d);
    2131   setring R;
    2132   ideal I = y(1)*x(2)*y(3) - z(1)*y(2)*z(3), x(1)*y(2)*z(3) - z(1)*x(2)*y(3),
    2133   z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) + y(1)*y(2)*y(3) +
    2134   z(1)*z(2)*z(3) + x(1)*y(2)*z(3);
    2135   option(prot);
    2136   option(redSB);option(redTail);option(mem);
    2137   ideal J = system("freegb",I,d,3);
    2138   lpDimCheck(J);
    2139   sickle(J,1,1,1,d);
    2140 
    2141 
    2142 
    2143   LIB "fpadim.lib";
    2144   ring r = 0,(x,y,z),dp;
    2145   int d  = 6; // degree
    2146   def R  = makeLetterplaceRing(d);
    2147   setring R;
    2148   ideal I = y(1)*x(2)*y(3) - z(1)*y(2)*z(3), x(1)*y(2)*x(3) - z(1)*x(2)*y(3),
    2149   z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) -2*y(1)*y(2)*y(3) + 3*z(1)*z(2)*z(3) -4*x(1)*y(2)*z(3) + 5*x(1)*z(2)*z(3)- 6*x(1)*y(2)*y(3) +7*x(1)*x(2)*z(3) - 8*x(1)*x(2)*y(3);
    2150   option(prot);
    2151   option(redSB);option(redTail);option(mem);
    2152   ideal J = system("freegb",I,d,3);
    2153   lpDimCheck(J);
    2154   sickle(J,1,1,1,d);
     2608   Here are some examples one may try. Just copy them into your console.
     2609   These are relations for braid groups, up to degree d:
     2610
     2611
     2612   LIB "fpadim.lib";
     2613   ring r = 0,(x,y,z),dp;
     2614   int d =10; // degree
     2615   def R = makeLetterplaceRing(d);
     2616   setring R;
     2617   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),
     2618   z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) + y(1)*y(2)*y(3) +
     2619   z(1)*z(2)*z(3) + x(1)*y(2)*z(3);
     2620   option(prot);
     2621   option(redSB);option(redTail);option(mem);
     2622   ideal J = system("freegb",I,d,3);
     2623   lpDimCheck(J);
     2624   sickle(J,1,1,1,d);//Computes mistletoes, K-dimension and the Hilbert series
     2625
     2626
     2627
     2628   LIB "fpadim.lib";
     2629   ring r = 0,(x,y,z),dp;
     2630   int d =11; // degree
     2631   def R = makeLetterplaceRing(d);
     2632   setring R;
     2633   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),
     2634   z(1)*x(2)*z(3) - y(1)*z(2)*x(3), x(1)*x(2)*x(3) + y(1)*y(2)*y(3) +
     2635   z(1)*z(2)*z(3) + x(1)*y(2)*z(3);
     2636   option(prot);
     2637   option(redSB);option(redTail);option(mem);
     2638   ideal J = system("freegb",I,d,3);
     2639   lpDimCheck(J);
     2640   sickle(J,1,1,1,d);
     2641
     2642
     2643
     2644   LIB "fpadim.lib";
     2645   ring r = 0,(x,y,z),dp;
     2646   int d  = 6; // degree
     2647   def R  = makeLetterplaceRing(d);
     2648   setring R;
     2649   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),
     2650   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);
     2651   option(prot);
     2652   option(redSB);option(redTail);option(mem);
     2653   ideal J = system("freegb",I,d,3);
     2654   lpDimCheck(J);
     2655   sickle(J,1,1,1,d);
     2656 */
     2657
     2658/*
     2659   Here are some examples, which can also be found in [studzins]:
     2660
     2661// takes up to 880Mb of memory
     2662LIB "fpadim.lib";
     2663ring r = 0,(x,y,z),dp;
     2664int d =10; // degree
     2665def R = makeLetterplaceRing(d);
     2666setring R;
     2667ideal I =
     2668z(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);
     2669option(prot);
     2670option(redSB);option(redTail);option(mem);
     2671ideal J = system("freegb",I,d,nvars(r));
     2672lpDimCheck(J);
     2673sickle(J,1,1,1,d); // dimension is 24872
     2674
     2675
     2676LIB "fpadim.lib";
     2677ring r = 0,(x,y,z),dp;
     2678int d =10; // degree
     2679def R = makeLetterplaceRing(d);
     2680setring R;
     2681ideal 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);
     2682option(prot);
     2683option(redSB);option(redTail);option(mem);
     2684ideal J = system("freegb",I,d,3);
     2685lpDimCheck(J);
     2686sickle(J,1,1,1,d);
     2687 */
     2688
     2689
     2690/*
     2691   Example for computing GK dimension:
     2692   returns a ring which contains an ideal I
     2693   run gkDim(I) inside this ring and it should return 2n (the GK dimension
     2694   of n-th Weyl algebra including evaluation operators).
     2695
     2696   static proc createWeylEx(int n, int d)
     2697   "
     2698   "
     2699   {
     2700   int baseringdef;
     2701   if (defined(basering)) // if a basering is defined, it should be saved for later use
     2702   {
     2703   def save = basering;
     2704   baseringdef = 1;
     2705   }
     2706   ring r = 0,(d(1..n),x(1..n),e(1..n)),dp;
     2707   def R = makeLetterplaceRing(d);
     2708   setring R;
     2709   ideal I; int i,j;
     2710
     2711   for (i = 1; i <= n; i++)
     2712   {
     2713   for (j = i+1; j<= n; j++)
     2714   {
     2715   I[size(I)+1] = lpMult(var(i),var(j));
     2716   }
     2717   }
     2718
     2719   for (i = 1; i <= n; i++)
     2720   {
     2721   for (j = i+1; j<= n; j++)
     2722   {
     2723   I[size(I)+1] = lpMult(var(n+i),var(n+j));
     2724   }
     2725   }
     2726   for (i = 1; i <= n; i++)
     2727   {
     2728   for (j = 1; j<= n; j++)
     2729   {
     2730   I[size(I)+1] = lpMult(var(i),var(n+j));
     2731   }
     2732   }
     2733   for (i = 1; i <= n; i++)
     2734   {
     2735   for (j = 1; j<= n; j++)
     2736   {
     2737   I[size(I)+1] = lpMult(var(i),var(2*n+j));
     2738   }
     2739   }
     2740   for (i = 1; i <= n; i++)
     2741   {
     2742   for (j = 1; j<= n; j++)
     2743   {
     2744   I[size(I)+1] = lpMult(var(2*n+i),var(n+j));
     2745   }
     2746   }
     2747   for (i = 1; i <= n; i++)
     2748   {
     2749   for (j = 1; j<= n; j++)
     2750   {
     2751   I[size(I)+1] = lpMult(var(2*n+i),var(2*n+j));
     2752   }
     2753   }
     2754   I = simplify(I,2+4);
     2755   I = letplaceGBasis(I);
     2756   export(I);
     2757   if (baseringdef == 1) {setring save;}
     2758   return(R);
     2759   }
     2760
     2761proc TestGKAuslander3()
     2762{
     2763  ring r = (0,q),(z,x,y),(dp(1),dp(2));
     2764  def R = makeLetterplaceRing(5); // constructs a Letterplace ring
     2765  R; setring R; // sets basering to Letterplace ring
     2766  ideal I;
     2767  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);
     2768  I = letplaceGBasis(I);
     2769  lpGkDim(I); // must be 3
     2770  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
     2771  I = letplaceGBasis(I); // not finite BUT contains a poly in x,y only
     2772  lpGkDim(I); // must be 4
     2773
     2774  ring r = 0,(y,x,z),dp;
     2775  def R = makeLetterplaceRing(10); // constructs a Letterplace ring
     2776  R; setring R; // sets basering to Letterplace ring
     2777  ideal I;
     2778  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
     2779  I = letplaceGBasis(I); // computed as it would be homogenized; infinite
     2780  poly p = x(1)*y(2)*y(3)*x(4)-y(1)*x(2)*x(3)*y(4);
     2781  lpNF(p, I); // 0 as expected
     2782
     2783  // with inverse of z
     2784  ring r = 0,(iz,z,x,y),dp;
     2785  def R = makeLetterplaceRing(11); // constructs a Letterplace ring
     2786  R; setring R; // sets basering to Letterplace ring
     2787  ideal I;
     2788  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),
     2789    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;
     2790  I = letplaceGBasis(I); //
     2791  setring r;
     2792  def R2 = makeLetterplaceRing(23); // constructs a Letterplace ring
     2793  setring R2; // sets basering to Letterplace ring
     2794  ideal I = imap(R,I);
     2795  lpGkDim(I);
     2796
     2797
     2798  ring r = 0,(t,z,x,y),(dp(2),dp(2));
     2799  def R = makeLetterplaceRing(20); // constructs a Letterplace ring
     2800  R; setring R; // sets basering to Letterplace ring
     2801  ideal I;
     2802  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),
     2803    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
     2804  I = letplaceGBasis(I); // computed as it would be homogenized; infinite
     2805  LIB "elim.lib";
     2806  ideal Inoz = nselect(I,intvec(2,6,10,14,18,22,26,30));
     2807  for(int i=1; i<=20; i++)
     2808  {
     2809    Inoz=subst(Inoz,t(i),1);
     2810  }
     2811  ideal J = x(1)*y(2)*y(3)*x(4)-y(1)*x(2)*x(3)*y(4);
     2812  J = letplaceGBasis(J);
     2813
     2814  poly p = x(1)*y(2)*y(3)*x(4)-y(1)*x(2)*x(3)*y(4);
     2815  lpNF(p, I); // 0 as expected
     2816
     2817  ring r2 = 0,(x,y),dp;
     2818  def R2 = makeLetterplaceRing(50); // constructs a Letterplace ring
     2819  setring R2;
     2820  ideal J = x(1)*y(2)*y(3)*x(4)-y(1)*x(2)*x(3)*y(4);
     2821  J = letplaceGBasis(J);
     2822}
     2823
    21552824*/
    21562825
    2157 /*
    2158   Here are some examples, which can also be found in [studzins]:
    2159 
    2160   // takes up to 880Mb of memory
    2161   LIB "fpadim.lib";
    2162   ring r = 0,(x,y,z),dp;
    2163   int d =10; // degree
    2164   def R = makeLetterplaceRing(d);
    2165   setring R;
    2166   ideal I =
    2167   z(1)*z(2)*z(3)*z(4) + y(1)*x(2)*y(3)*x(4) - x(1)*y(2)*y(3)*x(4) - 3*z(1)*y(2)*x(3)*z(4), x(1)*x(2)*x(3) + y(1)*x(2)*y(3) - x(1)*y(2)*x(3), z(1)*y(2)*x(3)-x(1)*y(2)*z(3) + z(1)*x(2)*z(3);
    2168   option(prot);
    2169   option(redSB);option(redTail);option(mem);
    2170   ideal J = system("freegb",I,d,nvars(r));
    2171   lpDimCheck(J);
    2172   sickle(J,1,1,1,d); // dimension is 24872
    2173 
    2174 
    2175   LIB "fpadim.lib";
    2176   ring r = 0,(x,y,z),dp;
    2177   int d =10; // degree
    2178   def R = makeLetterplaceRing(d);
    2179   setring R;
    2180   ideal I = x(1)*y(2) + y(1)*z(2), x(1)*x(2) + x(1)*y(2) - y(1)*x(2) - y(1)*y(2);
    2181   option(prot);
    2182   option(redSB);option(redTail);option(mem);
    2183   ideal J = system("freegb",I,d,3);
    2184   lpDimCheck(J);
    2185   sickle(J,1,1,1,d);
    2186 */
     2826
     2827/*   actual work:
     2828// downup algebra A
     2829LIB "fpadim.lib";
     2830ring r = (0,a,b,g),(x,y),Dp;
     2831def R = makeLetterplaceRing(6); // constructs a Letterplace ring
     2832setring R;
     2833poly F1 = g*x(1);
     2834poly F2 = g*y(1);
     2835ideal J = x(1)*x(2)*y(3)-a*x(1)*y(2)*x(3) - b*y(1)*x(2)*x(3) - F1,
     2836x(1)*y(2)*y(3)-a*y(1)*x(2)*y(3) - b*y(1)*y(2)*x(3) - F2;
     2837J = letplaceGBasis(J);
     2838lpGkDim(J); // 3 == correct
     2839
     2840// downup algebra B
     2841LIB "fpadim.lib";
     2842ring r = (0,a,b,g, p(1..7),q(1..7)),(x,y),Dp;
     2843def R = makeLetterplaceRing(6); // constructs a Letterplace ring
     2844setring R;
     2845ideal 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);
     2846int i;
     2847poly F1, F2;
     2848for(i=1;i<=7;i++)
     2849{
     2850F1 = F1 + p(i)*imn[i];
     2851F2 = F2 + q(i)*imn[i];
     2852}
     2853ideal J = x(1)*x(2)*y(3)-a*x(1)*y(2)*x(3) - b*y(1)*x(2)*x(3) - F1,
     2854x(1)*y(2)*y(3)-a*y(1)*x(2)*y(3) - b*y(1)*y(2)*x(3) - F2;
     2855J = letplaceGBasis(J);
     2856lpGkDim(J); // 3 == correct
     2857
     2858 */
Note: See TracChangeset for help on using the changeset viewer.