Changeset 578051 in git for Singular/LIB/fpadim.lib
- Timestamp:
- Dec 18, 2017, 4:15:00 PM (6 years ago)
- Branches:
- (u'spielwiese', '5b153614cbc72bfa198d75b1e9e33dab2645d9fe')
- Children:
- 909b29541ce0c334010bba6696154e22461eb5ce
- Parents:
- 9b58b3fcc6a12daf4ea426458fac85c628277f67179aaba41255e379952db14e553b6a3df355202c
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
Singular/LIB/fpadim.lib
r179aaba r578051 4 4 info=" 5 5 LIBRARY: fpadim.lib Algorithms for quotient algebras in the letterplace case 6 AUTHORS: Grischa Studzinski, grischa.studzinski@rwth-aachen.de 6 AUTHORS: 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 7 9 8 10 Support: 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' 12 of the German DFG 13 and Project II.6 of the transregional collaborative research centre 14 SFB-TRR 195 'Symbolic Tools in Mathematics and their Application' of the German DFG 15 16 OVERVIEW: Given the free associative algebra A = K<x_1,...,x_n> and a (finite) Groebner basis 13 17 GB = {g_1,..,g_w}, one is interested in the K-dimension and in the 14 18 explicit K-basis of A/<GB>. 15 19 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 @* 45 50 46 51 REFERENCES: … … 48 53 @* [ufna] Ufnarovskij: Combinatorical and asymptotic methods in algebra, 1990 49 54 @* [lls] Levandovskyy, La Scala: Letterplace ideals and non-commutative 50 55 Groebner bases, 2009 51 56 @* [studzins] Studzinski: Dimension computations in non-commutative, 52 53 54 Assumptions:55 @*- basering is always a Letterplace ring56 @*- all intvecs correspond to Letterplace monomials57 @* - if you specify a different degree bound d, 58 d <= attrib(basering,uptodeg) should hold. 59 @*In the procedures below, 'iv' stands for intvec representation60 57 associative algebras, Diploma thesis, RWTH Aachen, 2010 58 59 NOTE: 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 64 In the procedures below, 'iv' stands for intvec representation 65 and 'lp' for the letterplace representation of monomials 61 66 62 67 PROCEDURES: … … 86 91 sickle(G[,m,d,h]); can be used to access all lp main procedures 87 92 88 89 93 ivL2lpI(L); transforms a list of intvecs into an ideal of lp monomials 90 94 iv2lp(I); transforms an intvec into the corresponding monomial … … 145 149 {for (i3 = 1; i3 <= n; i3++) 146 150 {for (i4 = 1; i4 <= (n^(i1-1)); i4++) 147 { 148 M[i2,i1] = i3; 151 {M[i2,i1] = i3; 149 152 i2 = i2 + 1; 150 }153 } 151 154 } 152 155 } … … 170 173 "PURPOSE:checks, if all entries in M are variable-related 171 174 " 172 {if ((nrows(M) == 1) && (ncols(M) == 1)) {if (M[1,1] == 0){return(0);}} 173 int i,j; 175 {int i,j; 174 176 for (i = 1; i <= nrows(M); i++) 175 177 {for (j = 1; j <= ncols(M); j++) … … 328 330 } 329 331 332 333 static proc findCycleDFS(int i, intmat T, intvec V) 334 " 335 PURPOSE: 336 this 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 330 366 static proc findHCoeff(intvec V,int n,list L,intvec P,intvec H,list #) 331 367 "USAGE: findHCoeff(V,n,L,P,H,degbound); L a list of intmats, degbound an integer … … 565 601 } 566 602 return(R); 567 568 603 } 569 604 } … … 647 682 } 648 683 684 static proc growthAlg(intmat T, list #) 685 " 686 real 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 779 static 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 813 static 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 830 static 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 649 838 static proc isInList(intvec V, list L) 650 839 "USAGE: isInList(V,L); V an intvec, L a list of intvecs … … 684 873 } 685 874 875 876 static proc isPF(intvec P, intvec I) 877 " 878 PURPOSE: 879 checks, 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 686 890 proc ivL2lpI(list L) 687 891 "USAGE: ivL2lpI(L); L a list of intvecs 688 892 RETURN: ideal 689 PURPOSE:Transforming a list of intvecs into an ideal of Letterplace monomials. 690 @* For the encoding of the variables see the overview. 893 PURPOSE:Transforming a list of intvecs into an ideal of Letterplace monomials 691 894 ASSUME: - Intvec corresponds to a Letterplace monomial 692 895 @* - basering has to be a Letterplace ring 896 NOTE: - Assumptions will not be checked! 693 897 EXAMPLE: example ivL2lpI; shows examples 694 898 " 695 { checkAssumptions(0,L);899 { 696 900 int i; ideal G; 697 901 poly p; … … 718 922 RETURN: poly 719 923 PURPOSE:Transforming an intvec into the corresponding Letterplace polynomial 720 @* For the encoding of the variables see the overview.721 924 ASSUME: - Intvec corresponds to a Letterplace monomial 722 925 @* - basering has to be a Letterplace ring … … 748 951 RETURN: ideal 749 952 PURPOSE:Converting a list of intmats into an ideal of corresponding monomials 750 @* The rows of the intmat corresponds to an intvec, which stores the751 @* monomial.752 @* For the encoding of the variables see the overview.753 953 ASSUME: - The rows of each intmat in L must correspond to a Letterplace monomial 754 954 @* - basering has to be a Letterplace ring … … 779 979 "USAGE: iv2lpMat(M); M an intmat 780 980 RETURN: 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. 981 PURPOSE:Converting an intmat into an ideal of the corresponding monomials 785 982 ASSUME: - The rows of M must correspond to Letterplace monomials 786 983 @* - basering has to be a Letterplace ring … … 816 1013 "USAGE: lpId2ivLi(G); G an ideal 817 1014 RETURN: list 818 PURPOSE:Transforming an ideal into the corresponding list of intvecs. 819 @* For the encoding of the variables see the overview. 1015 PURPOSE:Transforming an ideal into the corresponding list of intvecs 820 1016 ASSUME: - basering has to be a Letterplace ring 821 1017 EXAMPLE: example lpId2ivLi; shows examples 822 1018 " 823 {int i,j,k; 1019 { 1020 int i,j,k; 824 1021 list M; 825 1022 checkAssumptions(0,M); … … 840 1037 "USAGE: lp2iv(p); p a poly 841 1038 RETURN: intvec 842 PURPOSE:Transforming a monomial into the corresponding intvec. 843 @* For the encoding of the variables see the overview. 1039 PURPOSE:Transforming a monomial into the corresponding intvec 844 1040 ASSUME: - basering has to be a Letterplace ring 845 1041 NOTE: - Assumptions will not be checked! … … 883 1079 RETURN: list 884 1080 PURPOSE: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 887 1082 ASSUME: - basering has to be a Letterplace ring 888 1083 EXAMPLE: example lp2ivId; shows examples … … 925 1120 // -----------------main procedures---------------------- 926 1121 1122 static proc lpGraphOfNormalWords(ideal G) 1123 "USAGE: lpGraphOfNormalWords(G); G a set of monomials in a letterplace ring 1124 RETURN: intmat 1125 PURPOSE: Constructs the graph of normal words induced by G 1126 @*: the adjacency matrix of the graph of normal words induced by G 1127 ASSUME: - 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 927 1206 proc ivDHilbert(list L, int n, list #) 928 1207 "USAGE: ivDHilbert(L,n[,degbound]); L a list of intmats, n an integer, … … 932 1211 ASSUME: - basering is a Letterplace ring 933 1212 @* - all rows of each intmat correspond to a Letterplace monomial 934 @* for the encoding of the variables see the overview935 1213 @* - if you specify a different degree bound degbound, 936 @* degbound <= attrib(basering,uptodeg) should hold.1214 @* degbound <= attrib(basering,uptodeg) holds 937 1215 NOTE: - If L is the list returned, then L[1] is an integer corresponding to the 938 1216 @* dimension, L[2] is an intvec which contains the coefficients of the … … 984 1262 ASSUME: - basering is a Letterplace ring. 985 1263 @* - All rows of each intmat correspond to a Letterplace monomial. 986 @* for the encoding of the variables see the overview987 1264 @* - If you specify a different degree bound degbound, 988 @* degbound <= attrib(basering,uptodeg) should hold.1265 @* degbound <= attrib(basering,uptodeg) holds. 989 1266 NOTE: - If L is the list returned, then L[1] is an integer, L[2] is an intvec 990 1267 @* which contains the coefficients of the Hilbert series and L[3] … … 1031 1308 RETURN: int, 0 if the dimension is finite, or 1 otherwise 1032 1309 PURPOSE: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 1310 ASSUME: - basering is a Letterplace ring. 1311 @* - All rows of each intmat correspond to a Letterplace monomial. 1312 NOTE: - n is the number of variables. 1037 1313 EXAMPLE: example ivDimCheck; shows examples 1038 1314 " … … 1090 1366 ASSUME: - basering is a Letterplace ring. 1091 1367 @* - all rows of each intmat correspond to a Letterplace monomial 1092 @* for the encoding of the variables see the overview1093 1368 @* - if you specify a different degree bound degbound, 1094 @* degbound <= attrib(basering,uptodeg) should hold.1369 @* degbound <= attrib(basering,uptodeg) holds. 1095 1370 NOTE: - If degbound is set, a degree bound will be added. By default there 1096 1371 @* is no degree bound. … … 1176 1451 ASSUME: - basering is a Letterplace ring. 1177 1452 @* - all rows of each intmat correspond to a Letterplace monomial 1178 @* for the encoding of the variables see the overview1179 1453 @* - if you specify a different degree bound degbound, 1180 @* degbound <= attrib(basering,uptodeg) should hold.1454 @* degbound <= attrib(basering,uptodeg) holds. 1181 1455 NOTE: - If degbound is set, a degree bound will be added. By default there 1182 1456 @* is no degree bound. … … 1263 1537 " 1264 1538 { 1265 //checkAssumptions(0,M);1539 //checkAssumptions(0,M); 1266 1540 intvec L,A; 1267 1541 if (size(M) == 0){ERROR("There are no mistletoes, so it appears your dimension is infinite!");} … … 1274 1548 for (i = 2; i <= size(M); i++) 1275 1549 {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 } 1291 1565 } 1292 1566 return(Rt); … … 1313 1587 @* Otherwise the returned value may differ from the K-dimension. 1314 1588 @* - basering is a Letterplace ring. 1315 @* - mistletoes are stored as intvecs, as described in the overview1316 1589 EXAMPLE: example ivMis2Dim; shows examples 1317 1590 " … … 1321 1594 if (isInList(L,M) > 0) {print("1 is a mistletoe, therefore dim = 1"); return(1);} 1322 1595 int i,j,d,s; 1596 j = 1; 1323 1597 d = 1 + size(M[1]); 1324 1598 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; 1329 1602 } 1330 1603 return(d); … … 1348 1621 PURPOSE:Orders a given set of mistletoes lexicographically 1349 1622 ASSUME: - basering is a Letterplace ring. 1350 @* - intvecs correspond to monomials, as explained in the overview 1623 - intvecs correspond to monomials 1351 1624 NOTE: - This is preprocessing, it's not needed if the mistletoes are returned 1352 1625 @* from the sickle algorithm. … … 1374 1647 @* optional integer 1375 1648 RETURN: list, containing intvecs, the mistletoes of A/<L> 1376 PURPOSE:Computing the mistletoes for a given Groebner basis L , given by intmats1649 PURPOSE:Computing the mistletoes for a given Groebner basis L 1377 1650 ASSUME: - basering is a Letterplace ring. 1378 1651 @* - all rows of each intmat correspond to a Letterplace monomial 1379 @* as explained in the overview1380 1652 @* - if you specify a different degree bound degbound, 1381 @* degbound <= attrib(basering,uptodeg) should hold.1653 @* degbound <= attrib(basering,uptodeg) holds. 1382 1654 NOTE: - If degbound is set, a degree bound will be added. By default there 1383 1655 @* is no degree bound. … … 1457 1729 ASSUME: - basering is a Letterplace ring. 1458 1730 @* - all rows of each intmat correspond to a Letterplace monomial 1459 @* as explained in the overview1460 1731 @* - if you specify a different degree bound degbound, 1461 @* degbound <= attrib(basering,uptodeg) should hold.1732 @* degbound <= attrib(basering,uptodeg) holds. 1462 1733 NOTE: - If L is the list returned, then L[1] is an integer, L[2] is a list, 1463 1734 @* containing the mistletoes as intvecs. … … 1545 1816 ASSUME: - basering is a Letterplace ring. 1546 1817 @* - all rows of each intmat correspond to a Letterplace monomial 1547 @* as explained in the overview1548 1818 @* - if you specify a different degree bound degbound, 1549 @* degbound <= attrib(basering,uptodeg) should hold.1819 @* degbound <= attrib(basering,uptodeg) holds. 1550 1820 NOTE: - If L is the list returned, then L[1] is an intvec, L[2] is a list, 1551 1821 @* containing the mistletoes as intvecs. … … 1630 1900 RETURN: list 1631 1901 PURPOSE:Computing K-dimension and Hilbert series, starting with a lp-ideal 1632 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.1902 ASSUME: - basering is a Letterplace ring. 1633 1903 @* - if you specify a different degree bound degbound, 1634 @* degbound <= attrib(basering,uptodeg) should hold.1904 @* degbound <= attrib(basering,uptodeg) holds. 1635 1905 NOTE: - If L is the list returned, then L[1] is an integer corresponding to the 1636 1906 @* dimension, L[2] is an intvec which contains the coefficients of the … … 1672 1942 RETURN: list 1673 1943 PURPOSE:Computing K-dimension, Hilbert series and mistletoes at once 1674 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.1944 ASSUME: - basering is a Letterplace ring. 1675 1945 @* - if you specify a different degree bound degbound, 1676 @* degbound <= attrib(basering,uptodeg) should hold.1946 @* degbound <= attrib(basering,uptodeg) holds. 1677 1947 NOTE: - If L is the list returned, then L[1] is an integer, the K-dimension, 1678 1948 @* L[2] is an intvec, the Hilbert series and L[3] is an ideal, … … 1715 1985 RETURN: intvec, containing the coefficients of the Hilbert series 1716 1986 PURPOSE:Computing the Hilbert series 1717 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.1987 ASSUME: - basering is a Letterplace ring. 1718 1988 @* - if you specify a different degree bound degbound, 1719 @* degbound <= attrib(basering,uptodeg) should hold.1989 @* degbound <= attrib(basering,uptodeg) holds. 1720 1990 NOTE: - If degbound is set, there will be a degree bound added. 0 means no 1721 1991 @* degree bound. Default: attrib(basering,uptodeg). … … 1753 2023 RETURN: int, 1 if K-dimension of the factor algebra is infinite, 0 otherwise 1754 2024 PURPOSE:Checking a factor algebra for finiteness of the K-dimension 1755 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.2025 ASSUME: - basering is a Letterplace ring. 1756 2026 EXAMPLE: example lpDimCheck; shows examples 1757 2027 " … … 1781 2051 RETURN: int, the K-dimension of the factor algebra 1782 2052 PURPOSE:Computing the K-dimension of a factor algebra, given via an ideal 1783 ASSUME: - basering is a Letterplace ring . G is a Letterplace ideal.2053 ASSUME: - basering is a Letterplace ring 1784 2054 @* - if you specify a different degree bound degbound, 1785 @* degbound <= attrib(basering,uptodeg) should hold.2055 @* degbound <= attrib(basering,uptodeg) holds. 1786 2056 NOTE: - If degbound is set, there will be a degree bound added. 0 means no 1787 2057 @* degree bound. Default: attrib(basering, uptodeg). … … 1840 2110 RETURN: int, the K-dimension of the factor algebra 1841 2111 PURPOSE:Computing the K-dimension out of given mistletoes 1842 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.2112 ASSUME: - basering is a Letterplace ring. 1843 2113 @* - M contains only monomials 1844 2114 NOTE: - The mistletoes have to be ordered lexicographically -> OrdMisLex. … … 1864 2134 RETURN: ideal, containing the mistletoes, ordered lexicographically 1865 2135 PURPOSE:A given set of mistletoes is ordered lexicographically 1866 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.2136 ASSUME: - basering is a Letterplace ring. 1867 2137 NOTE: This is preprocessing, it is not needed if the mistletoes are returned 1868 2138 @* from the sickle algorithm. … … 1885 2155 RETURN: ideal 1886 2156 PURPOSE:Computing the mistletoes of K[X]/<G> 1887 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.2157 ASSUME: - basering is a Letterplace ring. 1888 2158 @* - if you specify a different degree bound degbound, 1889 @* degbound <= attrib(basering,uptodeg) should hold.2159 @* degbound <= attrib(basering,uptodeg) holds. 1890 2160 NOTE: - If degbound is set, there will be a degree bound added. 0 means no 1891 2161 @* degree bound. Default: attrib(basering,uptodeg). … … 1923 2193 RETURN: list 1924 2194 PURPOSE:Computing the K-dimension and the mistletoes 1925 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.2195 ASSUME: - basering is a Letterplace ring. 1926 2196 @* - if you specify a different degree bound degbound, 1927 @* degbound <= attrib(basering,uptodeg) should hold.2197 @* degbound <= attrib(basering,uptodeg) holds. 1928 2198 NOTE: - If L is the list returned, then L[1] is an integer, the K-dimension, 1929 2199 @* L[2] is an ideal, the mistletoes. … … 1962 2232 RETURN: list 1963 2233 PURPOSE:Computing the Hilbert series and the mistletoes 1964 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.2234 ASSUME: - basering is a Letterplace ring. 1965 2235 @* - if you specify a different degree bound degbound, 1966 @* degbound <= attrib(basering,uptodeg) should hold.2236 @* degbound <= attrib(basering,uptodeg) holds. 1967 2237 NOTE: - If L is the list returned, then L[1] is an intvec, corresponding to the 1968 2238 @* Hilbert series, L[2] is an ideal, the mistletoes. … … 2004 2274 RETURN: list 2005 2275 PURPOSE:Allowing the user to access all procs with one command 2006 ASSUME: - basering is a Letterplace ring. G is a Letterplace ideal.2276 ASSUME: - basering is a Letterplace ring. 2007 2277 @* - if you specify a different degree bound degbound, 2008 @* degbound <= attrib(basering,uptodeg) should hold.2278 @* degbound <= attrib(basering,uptodeg) holds. 2009 2279 NOTE: The returned object will always be a list, but the entries of the 2010 2280 @* returned list may be very different … … 2062 2332 sickle(G,0,0,1); // computes Hilbert series only 2063 2333 } 2334 2335 proc 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 } 2375 example { 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 2386 proc 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 } 2398 example { 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 2409 proc 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 } 2490 example { 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 2507 todo: doc, example 2508 */ 2509 static 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 2526 static 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 2549 static 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 2064 2568 2065 2569 /////////////////////////////////////////////////////////////////////////////// … … 2098 2602 example lp2ivId; 2099 2603 example lpId2ivLi; 2100 } 2101 2102 2103 2104 2604 example lpSubstitute; 2605 } 2105 2606 2106 2607 /* 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 2662 LIB "fpadim.lib"; 2663 ring r = 0,(x,y,z),dp; 2664 int d =10; // degree 2665 def R = makeLetterplaceRing(d); 2666 setring R; 2667 ideal I = 2668 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); 2669 option(prot); 2670 option(redSB);option(redTail);option(mem); 2671 ideal J = system("freegb",I,d,nvars(r)); 2672 lpDimCheck(J); 2673 sickle(J,1,1,1,d); // dimension is 24872 2674 2675 2676 LIB "fpadim.lib"; 2677 ring r = 0,(x,y,z),dp; 2678 int d =10; // degree 2679 def R = makeLetterplaceRing(d); 2680 setring R; 2681 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); 2682 option(prot); 2683 option(redSB);option(redTail);option(mem); 2684 ideal J = system("freegb",I,d,3); 2685 lpDimCheck(J); 2686 sickle(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 2761 proc 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 2155 2824 */ 2156 2825 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 2829 LIB "fpadim.lib"; 2830 ring r = (0,a,b,g),(x,y),Dp; 2831 def R = makeLetterplaceRing(6); // constructs a Letterplace ring 2832 setring R; 2833 poly F1 = g*x(1); 2834 poly F2 = g*y(1); 2835 ideal J = x(1)*x(2)*y(3)-a*x(1)*y(2)*x(3) - b*y(1)*x(2)*x(3) - F1, 2836 x(1)*y(2)*y(3)-a*y(1)*x(2)*y(3) - b*y(1)*y(2)*x(3) - F2; 2837 J = letplaceGBasis(J); 2838 lpGkDim(J); // 3 == correct 2839 2840 // downup algebra B 2841 LIB "fpadim.lib"; 2842 ring r = (0,a,b,g, p(1..7),q(1..7)),(x,y),Dp; 2843 def R = makeLetterplaceRing(6); // constructs a Letterplace ring 2844 setring R; 2845 ideal imn = 1, y(1)*y(2)*y(3), x(1)*y(2), y(1)*x(2), x(1)*x(2), y(1)*y(2), x(1), y(1); 2846 int i; 2847 poly F1, F2; 2848 for(i=1;i<=7;i++) 2849 { 2850 F1 = F1 + p(i)*imn[i]; 2851 F2 = F2 + q(i)*imn[i]; 2852 } 2853 ideal J = x(1)*x(2)*y(3)-a*x(1)*y(2)*x(3) - b*y(1)*x(2)*x(3) - F1, 2854 x(1)*y(2)*y(3)-a*y(1)*x(2)*y(3) - b*y(1)*y(2)*x(3) - F2; 2855 J = letplaceGBasis(J); 2856 lpGkDim(J); // 3 == correct 2857 2858 */
Note: See TracChangeset
for help on using the changeset viewer.