Index: Singular/LIB/fpaprops.lib
===================================================================
--- Singular/LIB/fpaprops.lib	(revision 1708fac9cfbd392cceea00167eaa2746d291cd98)
+++ Singular/LIB/fpaprops.lib	(revision d906dc5d406b00b056fb825f5c5c8988ebcaceb3)
@@ -877,5 +877,5 @@
 }
 
-proc lpGkDim(ideal G)
+proc lpGkDim_lib(ideal G)
 "USAGE: lpGkDim(G); G an ideal in a letterplace ring
 RETURN: int
Index: Singular/dyn_modules/freealgebra/freealgebra.cc
===================================================================
--- Singular/dyn_modules/freealgebra/freealgebra.cc	(revision 1708fac9cfbd392cceea00167eaa2746d291cd98)
+++ Singular/dyn_modules/freealgebra/freealgebra.cc	(revision d906dc5d406b00b056fb825f5c5c8988ebcaceb3)
@@ -1,3 +1,4 @@
 #include "Singular/libsingular.h"
+#include <vector>
 
 #ifdef HAVE_SHIFTBBA
@@ -80,4 +81,16 @@
 }
 
+static BOOLEAN p_LPDivisibleBy(ideal I, poly p, ring r)
+{
+  for(int i = 0; i < IDELEMS(I); i++)
+  {
+    if (p_LPDivisibleBy(I->m[i], p, r))
+    {
+      return TRUE;
+    }
+  }
+  return FALSE;
+}
+
 static BOOLEAN lpLmDivides(leftv res, leftv h)
 {
@@ -97,13 +110,5 @@
     poly q=(poly)h->next->Data();
     res->rtyp = INT_CMD;
-    for(int i=0;i<IDELEMS(I);i++)
-    {
-      if (p_LPDivisibleBy(I->m[i],q, currRing))
-      {
-        res->data=(void*)(long)1;
-        return FALSE;
-      }
-    }
-    res->data=(void*)(long)0;
+    res->data=(void*)(long) p_LPDivisibleBy(I, q, currRing);
     return FALSE;
   }
@@ -124,4 +129,276 @@
   else return TRUE;
 }
+
+static void _computeStandardWords(ideal words, int n, ideal M, int& last)
+{
+  if (n <= 0){
+    words->m[0] = pOne();
+    last = 0;
+    return;
+  }
+
+  _computeStandardWords(words, n - 1, M, last);
+
+  int nVars = currRing->isLPring;
+
+  for (int j = nVars - 1; j >= 0; j--)
+  {
+    for (int i = last; i >= 0; i--)
+    {
+      int index = (j * (last + 1)) + i;
+
+      if (words->m[i] != NULL)
+      {
+        if (j > 0) {
+          words->m[index] = pCopy(words->m[i]);
+        }
+
+        int varOffset = ((n - 1) * nVars) + 1;
+        pSetExp(words->m[index], varOffset + j, 1);
+        pSetm(words->m[index]);
+        pTest(words->m[index]);
+
+        if (p_LPDivisibleBy(M, words->m[index], currRing))
+        {
+          pDelete(&words->m[index]);
+          words->m[index] = NULL;
+        }
+      }
+    }
+  }
+
+  last = nVars * last + nVars - 1;
+}
+
+static ideal computeStandardWords(int n, ideal M)
+{
+  int nVars = currRing->isLPring;
+
+  int maxElems = 1;
+  for (int i = 0; i < n; i++) // maxElems = nVars^n
+    maxElems *= nVars;
+  ideal words = idInit(maxElems);
+  int last;
+  _computeStandardWords(words, n, M, last);
+  idSkipZeroes(words);
+  return words;
+}
+
+// NULL if graph is undefined
+static intvec* ufnarovskiGraph(ideal G)
+{
+  long l = 0;
+  for (int i = 0; i < IDELEMS(G); i++)
+    l = si_max(pTotaldegree(G->m[i]), l);
+  l--;
+  if (l <= 0)
+  {
+    WerrorS("Ufnarovski graph not implemented for l <= 0");
+    return NULL;
+  }
+  int lV = currRing->isLPring;
+
+  ideal standardWords = computeStandardWords(l, G);
+
+  int n = IDELEMS(standardWords);
+  intvec* UG = new intvec(n, n, 0);
+  for (int i = 0; i < n; i++)
+  {
+    for (int j = 0; j < n; j++)
+    {
+      poly v = standardWords->m[i];
+      poly w = standardWords->m[j];
+
+      // check whether v*x1 = x2*w (overlap)
+      bool overlap = true;
+      for (int k = 1; k <= (l - 1) * lV; k++)
+      {
+        if (pGetExp(v, k + lV) != pGetExp(w, k)) {
+          overlap = false;
+          break;
+        }
+      }
+
+      if (overlap)
+      {
+        // create the overlap
+        poly p = pMult(pCopy(v), p_LPVarAt(w, l, currRing));
+
+        // check whether the overlap is normal
+        bool normal = true;
+        for (int k = 0; k < IDELEMS(G); k++)
+        {
+          if (p_LPDivisibleBy(G->m[k], p, currRing))
+          {
+            normal = false;
+            break;
+          }
+        }
+
+        if (normal)
+        {
+          IMATELEM(*UG, i + 1, j + 1) = 1;
+        }
+      }
+    }
+  }
+  return UG;
+}
+
+static std::vector<int> countCycles(const intvec* _G, int v, std::vector<int> path, std::vector<BOOLEAN> visited, std::vector<BOOLEAN> cyclic, std::vector<int> cache)
+{
+  intvec* G = ivCopy(_G); // modifications must be local
+
+  if (cache[v] != -2) return cache; // value is already cached
+
+  visited[v] = TRUE;
+  path.push_back(v);
+
+  int cycles = 0;
+  for (int w = 0; w < G->cols(); w++)
+  {
+    if (IMATELEM(*G, v + 1, w + 1)) // edge v -> w exists in G
+    {
+      if (!visited[w])
+      { // continue with w
+        cache = countCycles(G, w, path, visited, cyclic, cache);
+        if (cache[w] == -1)
+        {
+          cache[v] = -1;
+          return cache;
+        }
+        cycles = si_max(cycles, cache[w]);
+      }
+      else
+      { // found new cycle
+        int pathIndexOfW = -1;
+        for (int i = path.size() - 1; i >= 0; i--) {
+          if (cyclic[path[i]] == 1) { // found an already cyclic vertex
+            cache[v] = -1;
+            return cache;
+          }
+          cyclic[path[i]] = TRUE;
+
+          if (path[i] == w) { // end of the cycle
+            assume(IMATELEM(*G, v + 1, w + 1) != 0);
+            IMATELEM(*G, v + 1, w + 1) = 0; // remove edge v -> w
+            pathIndexOfW = i;
+            break;
+          } else {
+            assume(IMATELEM(*G, path[i - 1] + 1, path[i] + 1) != 0);
+            IMATELEM(*G, path[i - 1] + 1, path[i] + 1) = 0; // remove edge vi-1 -> vi
+          }
+        }
+        assume(pathIndexOfW != -1); // should never happen
+        for (int i = path.size() - 1; i >= pathIndexOfW; i--) {
+          cache = countCycles(G, path[i], path, visited, cyclic, cache);
+          if (cache[path[i]] == -1)
+          {
+            cache[v] = -1;
+            return cache;
+          }
+          cycles = si_max(cycles, cache[path[i]] + 1);
+        }
+      }
+    }
+  }
+  cache[v] = cycles;
+
+  delete G;
+  return cache;
+}
+
+// -1 is infinity
+static int graphGrowth(const intvec* G)
+{
+  // init
+  int n = G->cols();
+  std::vector<int> path;
+  std::vector<BOOLEAN> visited;
+  std::vector<BOOLEAN> cyclic;
+  std::vector<int> cache;
+  visited.resize(n, FALSE);
+  cyclic.resize(n, FALSE);
+  cache.resize(n, -2);
+
+  // get max number of cycles
+  int cycles = 0;
+  for (int v = 0; v < n; v++)
+  {
+    cache = countCycles(G, v, path, visited, cyclic, cache);
+    if (cache[v] == -1)
+      return -1;
+    cycles = si_max(cycles, cache[v]);
+  }
+  return cycles;
+}
+
+// -1 is infinity, -2 is error
+static int gkDim(const ideal _G)
+{
+  if (rField_is_Ring(currRing)) {
+      WerrorS("GK-Dim not implemented for rings");
+      return -2;
+  }
+
+  for (int i=IDELEMS(_G)-1;i>=0; i--)
+  {
+    if (pGetComp(_G->m[i]) != 0)
+    {
+      WerrorS("GK-Dim not implemented for modules");
+      return -2;
+    }
+  }
+
+  ideal G = id_Head(_G, currRing); // G = LM(G) (and copy)
+  idSkipZeroes(G); // remove zeros
+  id_DelLmEquals(G, currRing); // remove duplicates
+
+  // get the max deg
+  long maxDeg = 0;
+  for (int i = 0; i < IDELEMS(G); i++)
+  {
+    maxDeg = si_max(maxDeg, pTotaldegree(G->m[i]));
+
+    // also check whether G = <1>
+    if (pIsConstantComp(G->m[i]))
+    {
+      WerrorS("GK-Dim not defined for 0-ring");
+      return -2;
+    }
+  }
+
+  // early termination if G \subset X
+  if (maxDeg <= 1)
+  {
+    int lV = currRing->isLPring;
+    if (IDELEMS(G) == lV) // V = {1} no edges
+      return 0;
+    if (IDELEMS(G) == lV - 1) // V = {1} with loop
+      return 1;
+    if (IDELEMS(G) <= lV - 2) // V = {1} with more than one loop
+      return -1;
+  }
+
+  intvec* UG = ufnarovskiGraph(G);
+  if (errorreported || UG == NULL) return -2;
+  return graphGrowth(UG);
+}
+
+
+static BOOLEAN lpGkDim(leftv res, leftv h)
+{
+  const short t[]={1,IDEAL_CMD};
+  if (iiCheckTypes(h,t,1))
+  {
+    assumeStdFlag(h);
+    ideal G = (ideal) h->Data();
+    res->rtyp = INT_CMD;
+    res->data = (void*)(long) gkDim(G);
+    if (errorreported) return TRUE;
+    return FALSE;
+  }
+  else return TRUE;
+}
 #endif
 
@@ -134,4 +411,6 @@
   p->iiAddCproc("freealgebra.so","lpLmDivides",FALSE,lpLmDivides);
   p->iiAddCproc("freealgebra.so","lpVarAt",FALSE,lpVarAt);
+  p->iiAddCproc("freealgebra.so","lpGkDim",FALSE,lpGkDim);
+
   p->iiAddCproc("freealgebra.so","stest",TRUE,stest);
   p->iiAddCproc("freealgebra.so","btest",TRUE,btest);
Index: Tst/Letterplace.lst
===================================================================
--- Tst/Letterplace.lst	(revision 1708fac9cfbd392cceea00167eaa2746d291cd98)
+++ Tst/Letterplace.lst	(revision d906dc5d406b00b056fb825f5c5c8988ebcaceb3)
@@ -9,4 +9,5 @@
 Manual/makeLetterplaceRing.tst
 Manual/serreRelations.tst
+Manual/lpGkDim.tst
 Manual/lpKDim.tst
 Manual/lpMonomialPrinting.tst
@@ -18,2 +19,3 @@
 Manual/lpSickleDim.tst
 Manual/lpHilbert.tst
+Manual/lpLmDivisible.tst
Index: Tst/Manual/letterplace_std.res.gz.uu
===================================================================
--- Tst/Manual/letterplace_std.res.gz.uu	(revision 1708fac9cfbd392cceea00167eaa2746d291cd98)
+++ Tst/Manual/letterplace_std.res.gz.uu	(revision d906dc5d406b00b056fb825f5c5c8988ebcaceb3)
@@ -1,11 +1,130 @@
-begin 640 letterplace_std.res.gz
-M'XL(",KG3EP"`VQE='1E<G!L86-E7W-T9"YR97,`39%=:X,P%(;O_16'L@N-
-M6HS6?B`&-GIC&;MH=S>DZ$Q%$%<T97&_?B?1-KT0S7N>]SD$3Y_[[`,`*(/W
-M[`T68A#+MBD7">#7N>D:83N)I=[`&+1<"-Y?V^*;GP=1+3O^NQQ$(:S3K`EG
-MS:7GO"XGTV,8,>B;KH8>4@@\6WJC]^=X^ZLA5@R:3D#%:^R?RY];5R$;&R!F
-M.+S`$5.UXK6M>=D7=N_%CH'6#`8N]*JC23?HKGC10H9E7Y+1WY"1C&Y$))$>
-M8$"DCP\936=[[QRP@Q>VLZ<U.P:'Q#I\T3S5#N/$,,S3,%0RS"*BM7Y(U9%(
-M5T,:BZ:N6GW'W3OF&VRE;-L@F@(TT%T4S&,-Q'F*T327RK&)J8'7]`E=Y^GX
-:.,YWH0'3_UO]R]M@4R=YL?X!*I4F?1H"````
+begin 644 letterplace_std.res.gz
+M'XL("(6:P5P"`VQE='1E<G!L86-E7W-T9"YR97,`?9M)CQQ7=H7W^A6)AA=4
+M)9/]Y@$""=CHC0##"[4!+PR"D%IL@3`A-ZAJN.A?[^][.41&RG:SR:J,C'C#
+M'<XY][[0G__U3]__R^%PB.\.__S]/QW^\/S;\YO/GW[ZPW<'?OOPZ==/SZ^^
+M_>X;?Q[>O3M\_OC\_/'+WS[_^)>/'WY[_OG-KQ__Z\UOSS\^?_/GRS#I,LQ?
+MOWS\^,M/YY%N7^9WA]OOY<WACW\\Q-OG^N;PY=.OOQR^'-X>PNM7+Z^_OO[O
+M;U__Z6_;T^W=X=.OSX>?/_["V!]^^L^___HS]];MAOZ.+_]Z^(&K3O^/GW_Y
+M^-.7'U]]>5V_W6X:[PZ_?7Q>4_VP79V,_?/''S\?ON?AT\O3UU-_^OKT]9B?
+M7IY>7A^X\/1RXN_3U]LS,3#2\\^OOF?P#_\>W[]=]V[/<C&]?YN2#W$M/ZW'
+M3RGZ\>GEN&Y:M^7SLTYQO?UXO>VTW58<;81\OL`(<>9P^7K=4-^_Y=+Y^Q?'
+MZ#5N-[=X=VM[__;K[>-U0W%S3TQO#O_QZ?/GPY=MOWAO7=K,%LO=$W4Y-!U>
+M_>5#^1`_]`__]NWMN_;@W/+Z);]^2:]?XL[%\?_TX*%O+HR;"U_]<'=YY\.7
+M\O123JD^^4LZO40_MB=_YM-</]/1?^/KZP`IO%F/Y6/,Y\>.,:U?HD]X[5C6
+MSW0L<?T2<<]YZ#7@-E1DJ'R9:CV0SO<]3HF98[^LD;4F?SJV]VYW949;7[DP
+M1SJ5\TXNPY[W=S=L.3\0C^7R?5X_X\U8J3X$[_]Z^SF$+ZNZS%BO]Y1PNXD`
+M_G]V>P[=VS:OVSNE<-U$#Y<Q4]@&K;=GN".4BR-BS1=7M'&9K,U^=@9>*9>)
+M4[L,?LHU]8N[N;@-WV[#EU,,Y;+B4POILJI69[]N=8[-(OW]VXLM7$\[_[Z>
+M8)C;IW3JN5X_^-@@>Z^/I>,XW^0":VG;$#WTN`U1T\5&ES$F0!':>8BUQ+,)
+MUL)C#+%=/[*6,OKV.:VOT^US/(YXGG49M<7;TC3&V%9WS#&GZQ(*^1#JO"TI
+MGV*/:6SK-V'R''&W\1@PV"PUS5+JN"[>!3/43".%=K>+%FLI+2^C7/>29BJY
+MQQI&O]L1M@FAII%3'MN^8LRM])##V+:71J^ISG&YMJ*'SS-D]Q.NFR4B9RZU
+MS%KNKA)!O0V6V6>K=Y9H?;("K%QJV&(`>*^ML8;&WMKF/2Q39PTAY=IRBR7O
+M+$3^I8EY&/*\E?.R0XJ)*(KE9C2V5]H8/5RNK:440IRU5+DC7Q&NQL"(;=GA
+M8C&"*T2R(:;M3I!DY-GQQ643:^8Z6IACYK;9*^:<:HYSC+39"V\';FR]I;2%
+M3,R#_Y41YYV]VFRY,U>;H]P%T)AQAC"P52WWUB+YR+DY8\._<6<L$(D8"?F<
+MO&L/!&&]>F=M@$?CN/,VL[04Q[;R08"5?-GS\G+K>*;,;<6X%K*=,6_I>6I`
+MR`C8<4L*N``KP\1Q/G@55#1!KWA9XVW!QRL&^GM.=_8`P>ZL0++O4TD)D*^D
+MM,)MS&U4MASG-G#JZ3Z*<]L2^93;V&8]$I5AF]:L?IA7+(ZCW.82?6>,F]-/
+M/?;1YMT$^+GWDK9)B$ARIN>[B7+'Q"6T'<A%D/EE[W(@EU`C&\CK-$:.;<9:
+M6Z@DPIP]D"*D[(B%9,Q`36XY\Q5I"T;DVMEZ!YQS:9&'"K?WF+N.G#,!?J&G
+M`D3-.@K)`*!Q>V2241%8D5L8O>78Y^9@EP_Q1+)_Q#1[6T;C]R98Y9);SZ.)
+M9&#9#(/L9)S0B/Y!6(]&?O)P9@*P35T7@9G.K;!A"8XVB4A`@[LZN2@DECJE
+MJE!J9<*"OF.8IP=C#8W501/7`W;-+-*QTQGB2(5,`.58@_B5&""Q3]AAEIXG
+MN.=T3,@"@"H`(X*R';0DU3/VJ0#Q&(VX8W23E^6'EA/_!Y=PP[Q;#P1!G`'P
+MV"E6`!1W]3'88\/>G9]I1%"X59W+2C)3L^8$6'`#:^BES0*MUL9204?2D;\%
+MS,^%=8VN=1TKUH&I6FM:-F'D#.#?>VM1$RA4E_')C5HR[I9$V";C8%C,R@\P
+M5EH`P0AAAAQR2A\U@.O\PW:ADXRQ(+H\(K[!:Z7@8)<6ZL)WJ`ZD;C@]CHX[
+M'KT$E1.-F+LG8P,[81<,/J8AD(UQ.$1S`XS$WB1(6V%K$UMW8")%PWU@UTF:
+MM0XY5L)5VFFAL[`4!3@@`<O"Z2'=+0&=HYWG\@CXB^NF&8(WV>FH8",6Q_O,
+MBI_X-;$9K`W]L"-0O/!L-1%U!+\V/)M8C\MJ5;$!-Z?6.DO#V&7320L,)K@^
+M_5+@GZ0!ZU4*P"9E5)['_CD!*?H:N!\XC]C(F1!FSY.O8&"BA"S6WVR0_&Q5
+M_612:\FA9]BW:19B?TC=R0I-102$8W0-#&T3F4F?+&P@R4A`HQ<;X!?N`E.R
+MWC'N!EDHSQ("U03E<7U*Z!)_"(DDV^,V2"3D\1`!"5DTPA()'1R46!DQ,0FI
+M9!2!4PF^QL*U,P:K&$4'D7GZ&C1)4Y0B>DD%MDD*8XD63.1$FL*_P,#<@'ZQ
+M,Z,:[`1$(+0#""6DX",`E#P#N=AMJ@0^:&-DLV?"04$@@I*5$'X3,[0\L:[8
+M@=>)=9`<__`K2[P/MJ-I6;KN-FF;F8_Q"!C2!(@FW)L0`L6,N0PPD!N4LI,0
+M;2*ANBSP''#)\DFS5*,X&8TPC(>7^'(78<U<CGU],;4AT$\D:$CF"\0O.U#5
+M%%P'@$<A.)%C9#>X1'*;'F"*#(&A15RB3$!FV7UYCLAM;1=7)$,?XAAX0)BP
+M6>*)U;-R2&C9:.`<S15<#R.X(3"B+G@-?!X(59`_*6V5S6"`/H>(,!(H60G0
+M1SQ)43P!`,'.:.P4,8`T9$`21H'"MX._6%#EHSYCL5"`6%Z!#O:#";#41*CB
+M=@`N+\1LFP*Z:%"(Q`2%T/$`[F%F8D/,DD.'XV,9890L5<G581)/0TNC,!$A
+M0(@"=9`XM<K00R-L$F7%*C?#F=*G4@SH(=:7*@8S`3R(12)GFR#Q9)!!OFM$
+MK,YFY)(B72:V$PB3X'T!;#B71G=H2,DA36$$H%4&Z`(FR!.0&18OH.B:*:KM
+M)6T`D5QIV(TM:?61F#EI0LR][*(I"-^Q"\O5LY'*HP*W5A=G:B!/9>FBFP@J
+MJ6GEA'PH$V(:HH(1V340RPB$%?LWA%451755PBX8EX29ZE)2J6DEXM[L@6Z)
+M<ZXT,1A=SV"=:RB7Q?.$J%A#L0`^=F-:<,-NKI[AB-9X5^1=0G`)<T8%++$T
+M*V07C$9.F;":7;*"V]FGJ*&"P+RZ-G>1&D2>IB!&A%"[J-W&S7SGXK2[?5P)
+M`I,_I#ZDO7@WFG,@(-L$*8%R-#J!719[2JOJ4Q:FR[+B40D!WHZXBVYJ_6J8
+M9=2`'*-\3*"JA@`-V`H,I;)JJYX3^P!*XHD_X$%<0"5U)05=5=[TL(_JZ<#D
+M#,8DMC*A,M43A!N7*=I0%UB7[['A5'Z1/<:,FY$QUK:C;%BL3Z#].'9PR_=#
+MDJ+<<H6)VX/@Q542!D0J:J71634$!2@AUJO[!=]A60:>HI[215%2DSO<$_B)
+MU;)FY3<Y9LFO"I0XAGEMH%"5`M8D(J;+`!HN9R.&5-3VXCE[[^JC0A@NG173
+M7K)!YZ23#,ENDH\"D^#,7(^:'/(*!L1:Q<B49YS"!4P9.!!P,+P)*V`@[$?X
+M'7A2J<FZ-PM:/>&37>21JCLF+93ZQ,#>M]1C(%W8>0,!1:"4O?E,/7-XAT-4
+MZ*0SYJGY<87EVG2Z5.Y'TFDW,9FR(UV*.B[U/3L1SB7]+F_KM3.5K@VUL),,
+MIYWK*>WJR&$W%?`)(>R)D!3(Z7$J2CO<0L"1@.U^0UB3E"%]VV:1<Q,D+[8U
+MQK<R\=S!@6@(55@1Y']@J(!T4RFKRLO>02@'Z'ZIY#9W^Q*NSYH.L5/B;H?P
+M-Y[M%!GZ+.W"U`X>J3:L8@I_XN.N*5\)2`M452<%ZC+`Q!6DG::@T!">JGAC
+MX0;[5B43Z$-Z6OU1Z5B2P3)AZV*L/AYU#)@'0`U[5UUZ+-(!P('X@7:[VF/`
+M*@H<N%T%"7\.R9OTQTO@L6*P[)$V.**CH;#6H^I^S$/&HMRFM)Y,:TJ-*3P.
+M>-$R/%N:!.OHN9)615UVB6-O`#XN2TC8HF*9"R)@EFH:(TG(<Z#0\CJ[(7-?
+M!0Q9<'M73"W*(.4W\#OW.9@2MK0;H![%S(IKUJBEE`=P3+;,0.=9NJ('B`5K
+M3<S!DK*J&G6H`,ICKV.M8?F#D[(=2="9C014ET6ZX`*1*_PLNN4NV$$>LT@M
+MX!"4D(T[0!#^PO-C[#$5C2<ARCOL&&X05_DX5//$,W^3YL;=[#XJS6$/=DJ=
+M3*A,:^!0UK0I+PVSAU/L/&U,8#0L;$_4VHNB@=#&/%6%!6:`KG9;F:$9<NS)
+M-:L4+#&E-,.8*=OOD-3F`R2/69@"QR%^W;Z*4,ECX3T7!C,-,I4$M=XR@PF3
+MJ3C0N)`WL]UZE.<^.RED`2'C*`497GD(`K/`G@4.C6Z?UT*""\D,(G/D/$J!
+M060B/^ZSYZ3JGM3G2E>7C:.P*CIH29YH!XNOIZUCPE5/(*I!,)-J=:XQ49;I
+M=BKEN`K_9J\\:R\$,J)O552&"RJ(@"$(<>O4Q,/^$W)`_"`(L2XXT"Q)RXYQ
+MCGQM/5<M0]0'D-LB'"MO##[TZKI0;"(4R\-ASXC?[%OR$.,C[IN1N],D3&I)
+M$VV.V8<8]JG($(3):I4`\(5457@!%DMGD?#3F@63&^!(2RQDVN]`=2`SFMZU
+MH]/-OZY$D[J#+5_W7RQPK95'7(+6=+1,*VJN;&;*^4BX/>O$U4QB3>1L,1-9
+M)EQAL4IY;$.(/+=D!SN()]/.LH`%HP6ROPT['$/9!6*4':8/ZY]IK82P#+8<
+MA)!L/X3`L@"F9,R6L/C2>@;!OJI8U,>P[]A+,IR&9QR_Y]Q)GJ@LF_V49M$"
+M('@Z`/:8R>A_0955)&LFH@PG0DTM61!X[%+LU)2['$DGE)#-$C*[NEI[&>AY
+M_)Y5KU9X^B"N8JO9=XJB6%!!>7F6M)T6K(8R<TNOEBK]7'_WU2JP4*"2M@T"
+MN!JZ:LJN23PU(*V3[#9'V66;!SX=]&``#6^P%GLL"+.V0H.PP&CV.P1P:DA,
+MD>6)8FM^/E8#1PJS8D=`65C2@G%K&78)>]J$`A%;//<);4TFZ<CZ&;EIJ470
+MC+WXMY-"=@X?E"BC(I],CK9+U1I6RM4U,M$P0;D-@;=*:3M/81UGW646Q*L4
+MM1PN%D3^0]2**-PN/(##:?41VUD*H#^:#:YY[BR9+3L64CQ;6;95./*\>HRL
+MA#'4$X`)&=.:-9O\:)K!;-VZ`>"DH*;LLJ&UYQY+)@*DK>82HEQXI<PS/(07
+MA!%Q9)-V!35,!+DB!5;Y296-.A-;'@2\ZD$*MB'7XU(9=OQM/Q0S5?FF7X/I
+MVUBY=9\B0^LF0ZK9H\W](7]R0$BNWANJ`9=*]+)KM0\*S`Y(RC86O]O]P]'6
+M,LF:<+:[$/?`!5JV4B)S$>6V(FQJF2[=0Z4RUZ$!WY?UM1TATK#V^V&2ASCV
+MC(!BS6B!BPA)(CO`G^6GU4C5`,Y#<25/*ZQV+&>_)Q(+V`O):T:N)"OV$.<Z
+M5$1\>E06Z[GC1P3./:<=53?$;;1)G"WF;`1FR1HW$M/=DPCD!`A"/LJ,P5)]
+M7^W@Y>$)!F%FL`7//Z.%%[N$(:.)K@9824S!F^P-CC!VZ815A'1@4>YP%7V=
+M2`ZC:X%T#PLVH&RN-`NB9NH_%,S8TA!6`MB#MS`%.>QS1J-&38L:I`2)-A'#
+MRDD(K>ZJE'+JUF%RL(<7LK?M9'&,8AS&M518.E&("^N\>G4^[-L]\,ZJH2TI
+M04)E.:1),G@VQ?KF.CM)'L?7:4_8O)+^U['HGF3(QVZ%HTH%$J+-3//$+N-<
+MR[,Q2;9:*`\)@F3!ACD^5HAY-0"MZ:T@SPT5NWVV04$F]!S;UCC5>C\JU>\B
+MKQR'66^OT1,#6*\D-:1GH"TLQ>LF]'5,\DXKNRP2:E7^"#P"=O35(E7HV21C
+M+=D/4_6^FD^YQ7WZV+!H]M64'JS6(R(!TJ[I-#FG:AZ,QV!$8M]E7SS9L4EJ
+M@&J,*Z`!GF0G14PEXFQAJV;K.HYX**"4SW-U1DP9/![M$())=L3SVC"?F@HF
+MIO!0)/5U@"'"P5R>`F'V2*+*@MU.$(R.S\[UR%U/8>6'HJ18M\65`U-.)S7!
+M=)Z-UD8L;`JUR2.$NV;S6;0M5K3!UST'P?C8S?K:E5"KJK7Q0]=V5GEU7\='
+MJPQ<7-8)F!W5J`?-C&K&>MCFN=HZ?JMN-;:'7J8G)AY46#^LW@II*K$&+6`A
+ME06]8JWKBCR.W#<DLHT?,M>QLZAG7QZ@-G"QNXW"8E_2YC?!%ZS<'R/?ON.0
+M6O4<&(+-TC)CL7_JV52XO0.QNA7$6;:YM1I"VA6`)[B0':7>!]9Z30"+-OO&
+MJPG!DC"(Y,W6QI(C^?[]'VR%I"!NL`Q.46MT6\68T$.H%'9ZC80G2CWHZ[8T
+M@5,%E<?"\/:2^3LU!OYU3[]E%O+`3BY%`F+0MO4>OX^^*^-K"D5)7%=7&4'?
+M[=81"WE7CQ^[M=.TUP=T*M@]EF$J]FHEW/=A=TJV(8I:E7$]&$I*Y2DNXT"D
+MSKZMXIF@*;].[:VK;0_F:M_?&CF8S[NPP@]](0%TX'FF;F?E'M58M]K>;?L&
+MC"?[1$J,ZY"^VAHD*0PJ#<93+<7R&#;Y_=MDZ6@_&HI.ZYV.?-?>0TUE6_2K
+MB-U>M5HV(!IL+TA[1-C802D)'X0`0-]@F#N.!RM-`_4E1(-8&_M*ERJ=`GJ]
+MI:"<\HR^A'T8-"6^0$CP]O;0'[?[RG:M>E=K?=^R!%ILI)`2+L%CMOWA()K#
+M5R;.YZQJWX?^A_6D?9YI+G3Q]J&%`8(4@<1""'JW/9_;PSD\P(H_@F=3MH`,
+MI_Y8(&7?&/2]C(`-2EGD9^MJLU6^+&AFNS*6@G;@+=,7RN9[^>#!B3TZSQ*#
+M?09[AKM$]]!%\*VK11I\=6.%9]@E>%N]KFH_76S'2YX!SM5GN<OKXALDI:PF
+M%^'AV6%:DGG'6D<T</)PRY<P1"R+R+EO<I[6D9HZT$;\ZH#AG=+W[<X,UGM0
+MC?.(>JM\*'L=D.Y;Q$L\V;2P%S4\(O>4I(Z]3$)R$AH`RRCKZ-?"CRR=H<;]
+M&7[R#).5@8V>QK3S09Q=\=SW^;GTFKTEK>$A>5WHC._K^)V0\5TC]8:"M?K6
+M&+!5[G7[N98<RKF\R@3/VV"6<BXX\SU2K;,<9X8]H(5U4K;/5IPH>J));3MV
+M:\75JMDGK?U(6[(.(JEY,&^IM]-!Z6B1%ZR75EFL\BG3PY2=V(I'SSN'[1.%
+M.`+)/*^E['M(>-,W7SP78\;I>S1S[@^KCE!=]_P(`0*5K^X^(I'@VY]*+#%?
+M/9+R;1!%DIH_UOTK(=E>D3RU#NK7^Y&RU_"ECWV[?V3?5%CUJ:]LV,FK=E9'
+M?1"X^-M^H\=;S5/7ZBM0OGB!-?>.O[Z7W+8WRE-_L_X;!/_[@K__]BI^^]T_
++?/,_T)H[0:XP````
 `
 end
Index: Tst/Manual/letterplace_std.stat
===================================================================
--- Tst/Manual/letterplace_std.stat	(revision 1708fac9cfbd392cceea00167eaa2746d291cd98)
+++ Tst/Manual/letterplace_std.stat	(revision d906dc5d406b00b056fb825f5c5c8988ebcaceb3)
@@ -1,4 +1,4 @@
-1 >> tst_memory_0 :: 1548675018:4114, 64 bit:4.1.1:x86_64-Linux:nepomuck:331856
-1 >> tst_memory_1 :: 1548675018:4114, 64 bit:4.1.1:x86_64-Linux:nepomuck:2150160
-1 >> tst_memory_2 :: 1548675018:4114, 64 bit:4.1.1:x86_64-Linux:nepomuck:2191264
-1 >> tst_timer_1 :: 1548675018:4114, 64 bit:4.1.1:x86_64-Linux:nepomuck:6
+1 >> tst_memory_0 :: 1556191877:4120, 64 bit:4.1.2:x86_64-Darwin:Karims-MBP.localdomain:20013576
+1 >> tst_memory_1 :: 1556191877:4120, 64 bit:4.1.2:x86_64-Darwin:Karims-MBP.localdomain:21011760
+1 >> tst_memory_2 :: 1556191877:4120, 64 bit:4.1.2:x86_64-Darwin:Karims-MBP.localdomain:21068800
+1 >> tst_timer_1 :: 1556191877:4120, 64 bit:4.1.2:x86_64-Darwin:Karims-MBP.localdomain:22
Index: Tst/Manual/letterplace_std.tst
===================================================================
--- Tst/Manual/letterplace_std.tst	(revision 1708fac9cfbd392cceea00167eaa2746d291cd98)
+++ Tst/Manual/letterplace_std.tst	(revision d906dc5d406b00b056fb825f5c5c8988ebcaceb3)
@@ -1,4 +1,6 @@
 LIB "tst.lib"; tst_init();
 LIB "freegb.lib";
+
+// 1
 ring r = 0,(x,y,z),Dp;
 int degree_bound = 5;
@@ -6,5 +8,20 @@
 setring R;
 ideal I = -x*y-7*y*y+3*x*x, x*y*x-y*x*y;
-ideal J = std(I);
-J;
+std(I);
+
+kill r;
+kill R;
+
+// 2 (c_4_1_7_W)
+ring r = 0,(x4,x3,x2,x1),Dp;
+def R = freeAlgebra(r, 7);
+setring(R);
+ideal I = x4*x4-25*x4*x2-x1*x4-6*x1*x3-9*x1*x2+x1*x1,
+x4*x3+13*x4*x2+12*x4*x1-9*x3*x4+4*x3*x2+41*x3*x1-7*x1*x4-x1*x2,
+x3*x3-9*x3*x2+2*x1*x4+x1*x1,
+17*x4*x2-5*x2*x2-41*x1*x4,
+x2*x2-13*x2*x1-4*x1*x3+2*x1*x2-x1*x1,
+x2*x1+4*x1*x2-3*x1*x1;
+std(I);
+
 tst_status(1);$
Index: Tst/Manual/lpGkDim.res.gz.uu
===================================================================
--- Tst/Manual/lpGkDim.res.gz.uu	(revision d906dc5d406b00b056fb825f5c5c8988ebcaceb3)
+++ Tst/Manual/lpGkDim.res.gz.uu	(revision d906dc5d406b00b056fb825f5c5c8988ebcaceb3)
@@ -0,0 +1,16 @@
+begin 644 lpGkDim.res.gz
+M'XL("-:7P5P"`VQP1VM$:6TN<F5S`'U438^;0`R]YU=8JQX(7QM[!D@4%:FK
+M5%&D555E>Z_89K)"(5D$5"7_OC,#FH&PFPLV8_N-W\/FY==F]P,`,(7GW1,\
+M-'43%OGKPQJD]SN_Y(TS7\^4A32%HMR>-ODYO(A_8=UDS>RE+Z>^_%AF9?5>
+MUAV&";,4C,]#>'P$-.]1"%5^>8,*OL+"=UK_.O<WI:V-4SB((^QE^%@)\:UX
+M$Z]5YE0^1'.;E:10BT8#[>WI,H7\(+("MK*Z=:_N=:TNSXI*9(<K9+!],KDK
+M0\_92N#`=(@+VSUB"*>\**`REZ#DKH_LO3C@BQU?,N^W?+G?,K\EO\41;Y2\
+M.SI3XHDECI:XLQ\<&^8[Q9R[+0\H<I5#08OJ-7:59<%*6_+4$WT#L`IU&?.0
+M=64>DG905:@SCVM+'D?M8)"X';0&-%"TD%"LOTH74)=W<R5);3'I>Y2]DK(*
+M6^7:+))H.J0:4T@![YCTL!V_`2SK"M#C?9QIBT8LXL,QJ9N#L[-*4C2>BX4)
+MQ/8C4S(9"UI.QH)6MH(M]%@P<,[O%YR;8[R_#8P^W09N>V;LPZ%@?#04<AU:
+M'^1#;H5)B>Y(P>+/5H0E`V;+B19L-=&"#Y:*H]:"@U/D/S&F[U8/3C=ZH%R5
+MD2*<647.V4D\BZ8155ED?\1>\1_(POF'LO!H)$LW<.1K3PV:38SOB,.3L3C,
+<!)8#IG*KU']5_3O_U@[.UU]F_P%U#<IJ@@4`````
+`
+end
Index: Tst/Manual/lpGkDim.stat
===================================================================
--- Tst/Manual/lpGkDim.stat	(revision d906dc5d406b00b056fb825f5c5c8988ebcaceb3)
+++ Tst/Manual/lpGkDim.stat	(revision d906dc5d406b00b056fb825f5c5c8988ebcaceb3)
@@ -0,0 +1,4 @@
+1 >> tst_memory_0 :: 1556191190:4120, 64 bit:4.1.2:x86_64-Darwin:Karims-MBP.localdomain:20026328
+1 >> tst_memory_1 :: 1556191190:4120, 64 bit:4.1.2:x86_64-Darwin:Karims-MBP.localdomain:21016080
+1 >> tst_memory_2 :: 1556191190:4120, 64 bit:4.1.2:x86_64-Darwin:Karims-MBP.localdomain:21140112
+1 >> tst_timer_1 :: 1556191190:4120, 64 bit:4.1.2:x86_64-Darwin:Karims-MBP.localdomain:24
Index: Tst/Manual/lpGkDim.tst
===================================================================
--- Tst/Manual/lpGkDim.tst	(revision d906dc5d406b00b056fb825f5c5c8988ebcaceb3)
+++ Tst/Manual/lpGkDim.tst	(revision d906dc5d406b00b056fb825f5c5c8988ebcaceb3)
@@ -0,0 +1,49 @@
+LIB "tst.lib"; tst_init();
+LIB "fpaprops.lib";
+
+// 1
+ring r = 0,(x,y),Dp;
+def R = freeAlgebra(r, 5);
+setring R;
+ideal G = x*y*y; // already a GB
+lpGkDim(G);
+
+kill r;
+kill R;
+
+// 2
+ring r = 0,(x4,x3,x2,x1),Dp;
+ring R = freeAlgebra(r, 7);
+setring(R);
+ideal I = x4*x4-25*x4*x2-x1*x4-6*x1*x3-9*x1*x2+x1*x1,
+x4*x3+13*x4*x2+12*x4*x1-9*x3*x4+4*x3*x2+41*x3*x1-7*x1*x4-x1*x2,
+x3*x3-9*x3*x2+2*x1*x4+x1*x1,
+17*x4*x2-5*x2*x2-41*x1*x4,
+x2*x2-13*x2*x1-4*x1*x3+2*x1*x2-x1*x1,
+x2*x1+4*x1*x2-3*x1*x1;
+ideal G = std(I);
+lpGkDim(G);
+
+kill r;
+kill R;
+
+// 3 (mon1)
+ring r = 0,(x,y),Dp;
+def R = freeAlgebra(r, 4);
+setring(R);
+ideal I = x*y*x, y*x*y;
+ideal G = std(I);
+lpGkDim(G);
+
+kill r;
+kill R;
+
+// 4 (liP162E1)
+ring r = 0,(x1,x2),Dp;
+def R = makeLetterplaceRing(4);
+setring(R);
+ideal I = x1*x1*x2, x1*x2*x2;
+ideal G = std(I);
+lpGkDim(G);
+
+tst_status(1);$
Index: Tst/Manual/lpLmDivisible.res.gz.uu
===================================================================
--- Tst/Manual/lpLmDivisible.res.gz.uu	(revision d906dc5d406b00b056fb825f5c5c8988ebcaceb3)
+++ Tst/Manual/lpLmDivisible.res.gz.uu	(revision d906dc5d406b00b056fb825f5c5c8988ebcaceb3)
@@ -0,0 +1,11 @@
+begin 644 lpLmDivisible.res.gz
+M'XL("`>AP5P"`VQP3&U$:79I<VEB;&4N<F5S`'V406N#,!B&[_Z*#]G!B(B)
+M6BUB8,-+H>RP]CXJRR3@G*C;S+^?VJ)M_=*3@3QY\KY1<SAFNU<`H!SVNQ<P
+MN[9S2YF;"0RC=UG)SB*),3Z!<RCK_5<F?V4K\U*XE?ASV^[4&8>+A$T2\[,1
+MHLC/FGG.YS"/`Q<:61700`J>8_6.(DY6+VS(S_-OP_PH>RX+D3<GJW$@)`NV
+M60)]B-:JOTME><2!RX!`F@)-##HOB#0+^@GUKM'X%NT?6+>(E<[6:Y1ZN)62
+M50!*[U!;83DI0S"UQGS,9B.^`/-A8(@:U;KS!M_:1K>/\.UQ.,8CS/!-C*TF
+MAD)@YFDSKPLRJB^(I&9,7Q'#?7U)+'F@KXGAH;XHAC]XE]C)1,L_SV)WNE'&
+2^^*G';[XY,GX!ST%+L-\!```
+`
+end
Index: Tst/Manual/lpLmDivisible.stat
===================================================================
--- Tst/Manual/lpLmDivisible.stat	(revision d906dc5d406b00b056fb825f5c5c8988ebcaceb3)
+++ Tst/Manual/lpLmDivisible.stat	(revision d906dc5d406b00b056fb825f5c5c8988ebcaceb3)
@@ -0,0 +1,4 @@
+1 >> tst_memory_0 :: 1556193543:4120, 64 bit:4.1.2:x86_64-Darwin:Karims-MBP.localdomain:227632
+1 >> tst_memory_1 :: 1556193543:4120, 64 bit:4.1.2:x86_64-Darwin:Karims-MBP.localdomain:2151440
+1 >> tst_memory_2 :: 1556193543:4120, 64 bit:4.1.2:x86_64-Darwin:Karims-MBP.localdomain:2265744
+1 >> tst_timer_1 :: 1556193543:4120, 64 bit:4.1.2:x86_64-Darwin:Karims-MBP.localdomain:8
Index: Tst/Manual/lpLmDivisible.tst
===================================================================
--- Tst/Manual/lpLmDivisible.tst	(revision d906dc5d406b00b056fb825f5c5c8988ebcaceb3)
+++ Tst/Manual/lpLmDivisible.tst	(revision d906dc5d406b00b056fb825f5c5c8988ebcaceb3)
@@ -0,0 +1,28 @@
+LIB "tst.lib"; tst_init();
+LIB"freegb.lib";
+
+ring r = 0,(x,y),Dp;
+ring R = freeAlgebra(r, 5);
+lpLmDivides(poly(0), poly(0)) == 1;
+lpLmDivides(poly(0), x) == 0;
+lpLmDivides(x, poly(0)) == 1;
+lpLmDivides(poly(1), x) == 1;
+lpLmDivides(x, poly(1)) == 0;
+lpLmDivides(x*y, x) == 0;
+lpLmDivides(x*y, y) == 0;
+lpLmDivides(x*y, x*x) == 0;
+lpLmDivides(x*y, y*x) == 0;
+lpLmDivides(x*y, x*y) == 1;
+lpLmDivides(x*y, x*x*x*x) == 0;
+lpLmDivides(x*y, y*x*x*x) == 0;
+lpLmDivides(x*y, x*y*x*x) == 1;
+lpLmDivides(x*y, x*x*y*x) == 1;
+lpLmDivides(x*y, x*x*x*y) == 1;
+lpLmDivides(x*y, x*x*x*x*x) == 0;
+lpLmDivides(x*y, y*x*x*x*x) == 0;
+lpLmDivides(x*y, x*y*x*x*x) == 1;
+lpLmDivides(x*y, x*x*y*x*x) == 1;
+lpLmDivides(x*y, x*x*x*y*x) == 1;
+lpLmDivides(x*y, x*x*x*x*y) == 1;
+
+tst_status(1);$
Index: libpolys/polys/shiftop.cc
===================================================================
--- libpolys/polys/shiftop.cc	(revision 1708fac9cfbd392cceea00167eaa2746d291cd98)
+++ libpolys/polys/shiftop.cc	(revision d906dc5d406b00b056fb825f5c5c8988ebcaceb3)
@@ -13,5 +13,5 @@
  * -> wait until the new interface is released
 */
-#define SHIFT_MULT_COMPAT_MODE
+/* #define SHIFT_MULT_COMPAT_MODE */
 
 #ifdef SHIFT_MULT_DEBUG
@@ -718,6 +718,4 @@
 BOOLEAN _p_LPLmDivisibleByNoComp(poly a, poly b, const ring r)
 {
-  if(p_LmIsConstantComp(a, r))
-    return TRUE;
 #ifdef SHIFT_MULT_COMPAT_MODE
   a = p_Head(a, r);
@@ -726,9 +724,8 @@
   p_mLPunshift(b, r);
 #endif
-  int i = (r->N / r->isLPring) - p_LastVblock(a, r);
-  do {
-    int j = r->N - (i * r->isLPring);
+  for (int i = (r->N / r->isLPring) - p_LastVblock(a, r); i >= 0; i--)
+  {
     bool divisible = true;
-    do
+    for (int j = r->N - (i * r->isLPring); j >= 0; j--)
     {
       if (p_GetExp(a, j, r) > p_GetExp(b, j + (i * r->isLPring), r))
@@ -737,11 +734,7 @@
         break;
       }
-      j--;
-    }
-    while (j);
+    }
     if (divisible) return TRUE;
-    i--;
-  }
-  while (i > -1);
+  }
 #ifdef SHIFT_MULT_COMPAT_MODE
   p_Delete(&a, r);
