1 | //////////////////////////////////////////////////////////////// |
---|
2 | version="version fpaprops.lib 4.1.2.0 Feb_2019 "; // $Id$ |
---|
3 | category="Noncommutative"; |
---|
4 | info=" |
---|
5 | LIBRARY: fpaprops.lib Algorithmic ring-theoretic properties of finitely presented algebras (Letterplace) |
---|
6 | AUTHORS: Karim Abou Zeid, karim.abou.zeid at rwth-aachen.de |
---|
7 | |
---|
8 | Support: Project II.6 in the transregional collaborative research centre |
---|
9 | SFB-TRR 195 'Symbolic Tools in Mathematics and their Application' of the German DFG |
---|
10 | |
---|
11 | OVERVIEW: |
---|
12 | In this library, algorithms for computing various ring-theoretic properties of |
---|
13 | finitely presented algebras are implemented. |
---|
14 | Applicability: Letterplace rings. |
---|
15 | |
---|
16 | REFERENCES: |
---|
17 | Huishi Li: Groebner bases in ring theory. World Scientific, 2010. |
---|
18 | |
---|
19 | KEYWORDS: finitely presented algebra; ring theory; Letterplace Groebner basis; |
---|
20 | growth of algebra; Gelfand-Kirillov dimension; global homological dimension; semi-prime ideal; Ufnarovski graph |
---|
21 | |
---|
22 | SEE ALSO: fpadim_lib, freegb_lib |
---|
23 | |
---|
24 | PROCEDURES: |
---|
25 | lpNoetherian(<GB>); check whether A/<LM(GB)> is (left/right) Noetherian |
---|
26 | lpIsSemiPrime(<GB>); check whether A/<LM(GB)> is semi-prime |
---|
27 | lpIsPrime(<GB>); check whether A/<LM(GB)> is prime |
---|
28 | lpGkDim(<GB>); compute the Gelfand Kirillov dimension of A/<GB> |
---|
29 | lpGlDimBound(<GB>); compute an upper bound for the global dimension of A/<GB> |
---|
30 | lpSubstitute(); substitute a variable with polynomials (ring homomorphism) |
---|
31 | lpUfGraph(<GB>); constructs the Ufnarovskij graph for <LM(GB)> |
---|
32 | lpCalcSubstDegBound(); utility for lpSubstitute |
---|
33 | "; |
---|
34 | |
---|
35 | LIB "fpadim.lib"; |
---|
36 | |
---|
37 | /* very fast and cheap test of consistency and functionality |
---|
38 | DO NOT make it static ! |
---|
39 | after adding the new proc, add it here */ |
---|
40 | proc tstfpaprops() |
---|
41 | { |
---|
42 | example lpNoetherian; |
---|
43 | example lpIsSemiPrime; |
---|
44 | example lpIsPrime; |
---|
45 | example lpGkDim; |
---|
46 | example lpGlDimBound; |
---|
47 | example lpSubstitute; |
---|
48 | example lpUfGraph; |
---|
49 | example lpCalcSubstDegBound; |
---|
50 | }; |
---|
51 | |
---|
52 | |
---|
53 | //////////////////////////////////////////////////////////////////// |
---|
54 | proc lpNoetherian(ideal G) |
---|
55 | "USAGE: lpNoetherian(G); G an ideal in a Letterplace ring |
---|
56 | RETURN: int |
---|
57 | 0 not Noetherian |
---|
58 | 1 left Noetherian |
---|
59 | 2 right Noetherian |
---|
60 | 3 Noetherian |
---|
61 | 4 weak Noetherian |
---|
62 | PURPOSE: Check whether the monomial algebra A/<LM(G)> is (left/right) noetherian |
---|
63 | ASSUME: - basering is a Letterplace ring |
---|
64 | - G is a Groebner basis |
---|
65 | THEORY: lpNoetherian works with the monomial algebra A/<LM(G)>. |
---|
66 | If it gives an affirmative answer for one of the properties, then it |
---|
67 | holds for both A/<LM(G)> and A/<G>. However, a negative answer applies |
---|
68 | only to A/<LM(G)> and not necessarily to A/<G>. |
---|
69 | NOTE: Weak Noetherian means that two-sided ideals in A/<LM(G)> satisfy |
---|
70 | the acc (ascending chain condition). |
---|
71 | " |
---|
72 | { |
---|
73 | G = lead(G); |
---|
74 | G = simplify(G, 2+4+8); |
---|
75 | |
---|
76 | // check special case 1 |
---|
77 | int l = 0; |
---|
78 | for (int i = 1; i <= size(G); i++) { |
---|
79 | // find the max degree in G |
---|
80 | int d = deg(G[i]); |
---|
81 | if (d > l) { |
---|
82 | l = d; |
---|
83 | } |
---|
84 | |
---|
85 | // also if G is the whole ring |
---|
86 | if (leadmonom(G[i]) == 1) { |
---|
87 | ERROR("noetherianity not defined for 0-ring") |
---|
88 | } |
---|
89 | kill d; |
---|
90 | } kill i; |
---|
91 | // if longest word has length 1 we handle it as a special case |
---|
92 | if (l == 1) { |
---|
93 | int n = lpVarBlockSize(basering); // variable count |
---|
94 | int k = size(G); |
---|
95 | if (k == n) { // only the field left |
---|
96 | return(3); // every field is noetherian |
---|
97 | } |
---|
98 | if (k == n-1) { // V = {1} with loop |
---|
99 | return(3); |
---|
100 | } |
---|
101 | if (k <= n-2) { // V = {1} with more than one loop |
---|
102 | return(0); |
---|
103 | } |
---|
104 | } |
---|
105 | |
---|
106 | intmat UG = lpUfGraph(G); |
---|
107 | |
---|
108 | // check special case 2 |
---|
109 | intmat zero[nrows(UG)][ncols(UG)]; |
---|
110 | if (UG == zero) { |
---|
111 | return (3); |
---|
112 | } |
---|
113 | |
---|
114 | if (!imHasLoops(UG) && imIsUpRightTriangle(topologicalSort(UG))) { |
---|
115 | // UG is a DAG |
---|
116 | return (3); |
---|
117 | } |
---|
118 | |
---|
119 | // DFS from every vertex, if cycle is found, check every vertex for incomming/outcom |
---|
120 | intvec visited; |
---|
121 | visited[ncols(UG)] = 0; |
---|
122 | int inFlag, outFlag, inOutFlag; |
---|
123 | for (int v = 1; v <= ncols(UG) && (inFlag + outFlag) != 3; v++) { |
---|
124 | int inOutFlags = inOutCommingEdgesInCycles(UG, v, visited, 0); |
---|
125 | if (inOutFlags == 1) { |
---|
126 | inFlag = 1; |
---|
127 | } |
---|
128 | if (inOutFlags == 2) { |
---|
129 | outFlag = 1; |
---|
130 | } |
---|
131 | if (inOutFlags == 3) { |
---|
132 | inFlag = 1; |
---|
133 | outFlag = 1; |
---|
134 | } |
---|
135 | if (inOutFlags == 4) { |
---|
136 | inOutFlag = 1; |
---|
137 | } |
---|
138 | if (inOutFlags == 5) { |
---|
139 | inFlag = 1; |
---|
140 | inOutFlag = 1; |
---|
141 | } |
---|
142 | if (inOutFlags == 6) { |
---|
143 | outFlag = 1; |
---|
144 | inOutFlag = 1; |
---|
145 | } |
---|
146 | if (inOutFlags == 7) { |
---|
147 | inFlag = 1; |
---|
148 | outFlag = 1; |
---|
149 | inOutFlag = 1; |
---|
150 | } |
---|
151 | kill inOutFlags; |
---|
152 | } kill v; |
---|
153 | int noetherian = 3 - 1*inFlag - 2*outFlag; |
---|
154 | if (noetherian == 0) { |
---|
155 | return (4 - 4*inOutFlag); // weak noetherian |
---|
156 | } |
---|
157 | return (noetherian); |
---|
158 | } |
---|
159 | example |
---|
160 | { |
---|
161 | "EXAMPLE:"; echo = 2; |
---|
162 | ring r = 0,(x,y),dp; |
---|
163 | def R = freeAlgebra(r, 5); |
---|
164 | setring R; |
---|
165 | ideal G = x*x, y*x; // K<x,y>/<xx,yx> is right noetherian |
---|
166 | lpNoetherian(G); |
---|
167 | } |
---|
168 | |
---|
169 | static proc inOutCommingEdgesInCycles(intmat G, int v, intvec visited, intvec path) { |
---|
170 | // Mark the current vertex as visited |
---|
171 | visited[v] = 1; |
---|
172 | |
---|
173 | // Store the current vertex in path |
---|
174 | if (path[1] == 0) { |
---|
175 | path[1] = v; |
---|
176 | } else { |
---|
177 | path[size(path) + 1] = v; |
---|
178 | } |
---|
179 | |
---|
180 | int inFlag, outFlag, inOutFlag; |
---|
181 | |
---|
182 | for (int w = 1; w <= ncols(G) && (inFlag + outFlag) != 3; w++) { |
---|
183 | if (G[v,w] == 1) { |
---|
184 | if (visited[w] == 1) { // new cycle |
---|
185 | int tmpInFlag; |
---|
186 | int tmpOutFlag; |
---|
187 | if (v == w) { // cycle is a loop |
---|
188 | for (int u = 1; u <= ncols(G); u++) { |
---|
189 | if (G[v,u] && u != v) { |
---|
190 | outFlag = 1; |
---|
191 | tmpOutFlag = 1; |
---|
192 | } |
---|
193 | if (G[u,v] && u != v) { |
---|
194 | inFlag = 1; |
---|
195 | tmpInFlag = 1; |
---|
196 | } |
---|
197 | } kill u; |
---|
198 | } else { |
---|
199 | for (int i = size(path); i >= 1; i--) { // for each vertex in the path |
---|
200 | // check for neighbors not directly next or prev in cycle |
---|
201 | for (int u = 1; u <= ncols(G); u++) { |
---|
202 | if (G[path[i],u] == 1) { // there is an edge to u |
---|
203 | if (path[i] != v) { |
---|
204 | if (u != path[i+1]) { // and u is not the next element in the cycle |
---|
205 | outFlag = 1; |
---|
206 | tmpOutFlag = 1; |
---|
207 | } |
---|
208 | } else { |
---|
209 | if (u != w) { |
---|
210 | outFlag = 1; |
---|
211 | tmpOutFlag = 1; |
---|
212 | } |
---|
213 | } |
---|
214 | } |
---|
215 | if (G[u,path[i]] == 1) { // there is an edge from u |
---|
216 | if (path[i] != w) { |
---|
217 | if (u != path[i-1]) { // and u is not the previous element in the cylce |
---|
218 | inFlag = 1; |
---|
219 | tmpInFlag = 1; |
---|
220 | } |
---|
221 | } else { |
---|
222 | if (u != v) { |
---|
223 | inFlag = 1; |
---|
224 | tmpInFlag = 1; |
---|
225 | } |
---|
226 | } |
---|
227 | } |
---|
228 | } kill u; |
---|
229 | if (path[i] == w) { |
---|
230 | break; |
---|
231 | } |
---|
232 | } kill i; |
---|
233 | } |
---|
234 | if (tmpInFlag > 0 && tmpOutFlag > 0) { |
---|
235 | // there are both in and outcomming edges in this cycle |
---|
236 | inOutFlag = 1; |
---|
237 | } |
---|
238 | kill tmpInFlag; |
---|
239 | kill tmpOutFlag; |
---|
240 | } else { |
---|
241 | int inOutFlags = inOutCommingEdgesInCycles(G, w, visited, path); |
---|
242 | if (inOutFlags == 1) { |
---|
243 | inFlag = 1; |
---|
244 | } |
---|
245 | if (inOutFlags == 2) { |
---|
246 | outFlag = 1; |
---|
247 | } |
---|
248 | if (inOutFlags == 3) { |
---|
249 | inFlag = 1; |
---|
250 | outFlag = 1; |
---|
251 | } |
---|
252 | if (inOutFlags == 4) { |
---|
253 | inOutFlag = 1; |
---|
254 | } |
---|
255 | if (inOutFlags == 5) { |
---|
256 | inFlag = 1; |
---|
257 | inOutFlag = 1; |
---|
258 | } |
---|
259 | if (inOutFlags == 6) { |
---|
260 | outFlag = 1; |
---|
261 | inOutFlag = 1; |
---|
262 | } |
---|
263 | if (inOutFlags == 7) { |
---|
264 | inFlag = 1; |
---|
265 | outFlag = 1; |
---|
266 | inOutFlag = 1; |
---|
267 | } |
---|
268 | kill inOutFlags; |
---|
269 | } |
---|
270 | } |
---|
271 | } kill w; |
---|
272 | |
---|
273 | return (1*inFlag + 2*outFlag + 4*inOutFlag); |
---|
274 | } |
---|
275 | |
---|
276 | proc lpIsSemiPrime(ideal G) |
---|
277 | "USAGE: lpIsSemiPrime(G); G an ideal in a Letterplace ring |
---|
278 | RETURN: boolean |
---|
279 | PURPOSE: Check whether A/<LM(G)> is semi-prime ring, |
---|
280 | alternatively whether <LM(G)> is a semi-prime ideal in A. |
---|
281 | ASSUME: - basering is a Letterplace ring |
---|
282 | - G is a Groebner basis |
---|
283 | THEORY: A (two-sided) ideal I in the ring A is semi-prime, if for any a in A one has |
---|
284 | aAa subseteq I implies a in I. |
---|
285 | NOTE: lpIsSemiPrime works with the monomial algebra A/<LM(G)>. |
---|
286 | A positive answer holds for both A/<LM(G)> and A/<G>, while |
---|
287 | a negative answer applies only to A/<LM(G)> and not necessarily to |
---|
288 | A/<G>. |
---|
289 | " |
---|
290 | { |
---|
291 | // old theory part: that is when p * (A/<LM(G)>) * p != 0 for all p in (A/<LM(G)> - {0}). |
---|
292 | G = lead(G); |
---|
293 | G = simplify(G, 2+4+8); |
---|
294 | |
---|
295 | // check special case 1 |
---|
296 | int l = 0; |
---|
297 | for (int i = 1; i <= size(G); i++) { |
---|
298 | // find the max degree in G |
---|
299 | int d = deg(G[i]); |
---|
300 | if (d > l) { |
---|
301 | l = d; |
---|
302 | } |
---|
303 | |
---|
304 | // also if G is the whole ring |
---|
305 | if (leadmonom(G[i]) == 1) { |
---|
306 | ERROR("primeness not defined for 0-ring") |
---|
307 | } |
---|
308 | kill d; |
---|
309 | } kill i; |
---|
310 | // if longest word has length 1 we handle it as a special case |
---|
311 | if (l == 1) { |
---|
312 | return(1); |
---|
313 | } |
---|
314 | |
---|
315 | list VUG = lpUfGraph(G, 1); |
---|
316 | intmat UG = VUG[1]; // the Ufnarovskij graph |
---|
317 | ideal V = VUG[2]; // the vertices of UG (standard words with length = l-1) |
---|
318 | |
---|
319 | list LG = lpId2ivLi(G); |
---|
320 | list SW = ivStandardWordsUpToLength(LG, maxDeg(G)); |
---|
321 | list LV = lpId2ivLi(V); |
---|
322 | |
---|
323 | // delete the 0 in SW |
---|
324 | int indexofzero = ivIndexOf(SW, 0); |
---|
325 | if (indexofzero > 0) { // should be always true when |SW| > 0 |
---|
326 | SW = delete(SW, indexofzero); |
---|
327 | } |
---|
328 | |
---|
329 | // check if each monomial in SW is cyclic |
---|
330 | for (int i = 1; i <= size(SW); i++) { |
---|
331 | if (!isCyclicInUfGraph(UG, LV, SW[i])) { |
---|
332 | return (0); |
---|
333 | } |
---|
334 | } kill i; |
---|
335 | |
---|
336 | return (1); |
---|
337 | } |
---|
338 | example |
---|
339 | { |
---|
340 | "EXAMPLE:"; echo = 2; |
---|
341 | ring r = 0,(x1,x2),dp; |
---|
342 | def R = freeAlgebra(r, 5); |
---|
343 | setring R; |
---|
344 | ideal G = x1*x2, x2*x1; // K<x1,x2>/<x1*x2,x2*x1> is semi prime |
---|
345 | lpIsSemiPrime(G); |
---|
346 | } |
---|
347 | |
---|
348 | // checks whether a monomial is a cyclic monomial |
---|
349 | static proc isCyclicInUfGraph(intmat UG, list LV, intvec u) |
---|
350 | { |
---|
351 | if (ncols(UG) == 0) {return (0);} // UG is empty |
---|
352 | if (u == 0) {return (0);} // 0 is never cyclic |
---|
353 | |
---|
354 | int l = size(LV[1]) + 1; |
---|
355 | |
---|
356 | int s = size(u); |
---|
357 | if (s <= l - 1) { |
---|
358 | for (int i = 1; i <= size(LV); i++) { |
---|
359 | // for all vertices where u is a suffix |
---|
360 | if(isSF(u, LV[i])) { |
---|
361 | if (existsRoute(UG, i, i)) { |
---|
362 | return (1); |
---|
363 | } |
---|
364 | } |
---|
365 | } kill i; |
---|
366 | } else { // size(u) > l - 1 |
---|
367 | int m = s - l + 1; |
---|
368 | |
---|
369 | // there must be a route from v0 to vm |
---|
370 | intvec v0 = u[1..(l-1)]; // first in route of u |
---|
371 | intvec vm = u[m+1..m+(l-1)]; // last in route of u |
---|
372 | |
---|
373 | int iv0 = ivIndexOf(LV, v0); |
---|
374 | int ivm = ivIndexOf(LV, vm); |
---|
375 | if (iv0 <= 0 || ivm <= 0) { |
---|
376 | ERROR("u is not a standard word"); |
---|
377 | } |
---|
378 | |
---|
379 | return (existsRoute(UG, ivm, iv0)); |
---|
380 | } |
---|
381 | |
---|
382 | return (0); |
---|
383 | } |
---|
384 | |
---|
385 | proc lpIsPrime(ideal G) |
---|
386 | "USAGE: lpIsPrime(G); G an ideal in a Letterplace ring |
---|
387 | RETURN: boolean |
---|
388 | PURPOSE: Check whether A/<LM(G)> is prime ring, |
---|
389 | alternatively whether <LM(G)> is a prime ideal in A. |
---|
390 | ASSUME: - basering is a Letterplace ring |
---|
391 | - G is a Groebner basis |
---|
392 | THEORY: A (two-sided) ideal I in the ring A is prime, if for any a,b in A one has |
---|
393 | aAb subseteq I implies a in I or b in I. |
---|
394 | NOTE: lpIsPrime works with the monomial algebra A/<LM(G)>. |
---|
395 | A positive answer holds for both A/<LM(G)> and A/<G>, while |
---|
396 | a negative answer applies only to A/<LM(G)> and not necessarily to A/<G>. |
---|
397 | " |
---|
398 | { |
---|
399 | // old theory part: that is when p1 * (A/<LM(G)>) * p2 != 0 for all p1, p2 in (A/<LM(G)> - {0}). |
---|
400 | G = lead(G); |
---|
401 | G = simplify(G, 2+4+8); |
---|
402 | |
---|
403 | // check special case 1 |
---|
404 | int l = 0; |
---|
405 | for (int i = 1; i <= size(G); i++) { |
---|
406 | // find the max degree in G |
---|
407 | int d = deg(G[i]); |
---|
408 | if (d > l) { |
---|
409 | l = d; |
---|
410 | } |
---|
411 | |
---|
412 | // also if G is the whole ring |
---|
413 | if (leadmonom(G[i]) == 1) { |
---|
414 | ERROR("primeness not defined for 0-ring") |
---|
415 | } |
---|
416 | kill d; |
---|
417 | } kill i; |
---|
418 | // if longest word has length 1 we handle it as a special case |
---|
419 | if (l == 1) { |
---|
420 | return(1); |
---|
421 | } |
---|
422 | |
---|
423 | list VUG = lpUfGraph(G, 1); |
---|
424 | intmat UG = VUG[1]; // the Ufnarovskij graph |
---|
425 | ideal V = VUG[2]; // the vertices of UG (standard words with length = l-1) |
---|
426 | |
---|
427 | list LG = lpId2ivLi(G); |
---|
428 | list LV = lpId2ivLi(V); |
---|
429 | |
---|
430 | int n = ncols(UG); |
---|
431 | |
---|
432 | // 1) for each vi vj there exists a route from vi to vj (means UG is connected) |
---|
433 | for (int i = 1; i <= n; i++) { |
---|
434 | for (int j = 1; j <= n; j++) { |
---|
435 | if (!existsRoute(UG, i, j)) { |
---|
436 | return (0); |
---|
437 | } |
---|
438 | } kill j; |
---|
439 | } kill i; |
---|
440 | |
---|
441 | // 2) any standard word with length < l-1 is a suffix of a vertex |
---|
442 | list SW = ivStandardWordsUpToLength(LG, maxDeg(G) - 2); // < maxDeg - 1 |
---|
443 | if (size(SW) > 0 && size(LV) == 0) {return (0);} |
---|
444 | for (int i = 1; i <= size(SW); i++) { |
---|
445 | // check if SW[i] is a suffix of some LV |
---|
446 | for (int j = 1; j <= size(LV); j++) { |
---|
447 | if (!isSF(SW[i], LV[j])) { |
---|
448 | if (j == size(LV)) { |
---|
449 | return (0); |
---|
450 | } |
---|
451 | } else { |
---|
452 | break; |
---|
453 | } |
---|
454 | } |
---|
455 | } kill i; |
---|
456 | |
---|
457 | return (1); |
---|
458 | } |
---|
459 | example |
---|
460 | { |
---|
461 | "EXAMPLE:"; echo = 2; |
---|
462 | ring r = 0,(x,y),dp; |
---|
463 | def R = freeAlgebra(r, 5); |
---|
464 | setring R; |
---|
465 | ideal G = x*x, y*y; // K<x,y>/<xx,yy> is prime |
---|
466 | lpIsPrime(G); |
---|
467 | } |
---|
468 | |
---|
469 | static proc existsRoute(intmat G, int v, int u, list #) |
---|
470 | "USAGE: existsRoute(G,v,u); G a graph, v and u vertices |
---|
471 | NOTE: don't pass anything to # (internal use for recursion) |
---|
472 | routes always have at least one edge |
---|
473 | " |
---|
474 | { |
---|
475 | int n = ncols(G); |
---|
476 | |
---|
477 | // init visited |
---|
478 | intvec visited; |
---|
479 | if (size(#) > 0) { |
---|
480 | if (v == u) {return (1);} // don't check on first call so |route| >= 1 holds |
---|
481 | visited = #[1]; |
---|
482 | } else { // first call |
---|
483 | visited[n] = 0; |
---|
484 | } |
---|
485 | |
---|
486 | // mark current vertex as visited |
---|
487 | visited[v] = 1; |
---|
488 | |
---|
489 | // recursive DFS |
---|
490 | for (int i = 1; i <= n; i++) { |
---|
491 | if (G[v,i] && (!visited[i] || i == u)) { // i == u to allow routes from u to u |
---|
492 | if (existsRoute(G, i, u, visited)) { |
---|
493 | return (1); |
---|
494 | } |
---|
495 | } |
---|
496 | } kill i; |
---|
497 | |
---|
498 | return (0); |
---|
499 | } |
---|
500 | |
---|
501 | static proc UfGraphURTNZDGrowth(intmat UG) { |
---|
502 | // URTNZD = upper right triangle non zero diagonal |
---|
503 | for (int i = 1; i <= ncols(UG); i++) { |
---|
504 | UG[i,i] = 0; // remove all loops |
---|
505 | } kill i; |
---|
506 | intmat UGk = UG; |
---|
507 | intmat zero[nrows(UGk)][ncols(UGk)]; |
---|
508 | int k = 1; |
---|
509 | while (UGk != zero) { |
---|
510 | UGk = UGk * UG; |
---|
511 | k++; |
---|
512 | } |
---|
513 | return (k); |
---|
514 | } |
---|
515 | |
---|
516 | static proc imIsUpRightTriangle(intmat M) { |
---|
517 | for (int i = 1; i <= nrows(M); i++) { |
---|
518 | for (int j = 1; j < i; j++) { |
---|
519 | if(M[i,j] != 0) { return (0); } |
---|
520 | } kill j; |
---|
521 | } kill i; |
---|
522 | return (1); |
---|
523 | } |
---|
524 | |
---|
525 | static proc eliminateZerosUpTriangle(intmat G) { |
---|
526 | // G is expected to be an upper triangle matrix |
---|
527 | for (int i = ncols(G); i >= 1; i--) { // loop order is important because we delete entries |
---|
528 | if (G[i,i] == 0) { // i doesn't have a cycle |
---|
529 | for (int j = 1; j < i; j++) { |
---|
530 | if (G[j,i] == 1) { // j has an edge to i |
---|
531 | for (int k = i + 1; k <= nrows(G); k++) { |
---|
532 | if (G[i,k] == 1) { |
---|
533 | G[j,k] = G[i,k]; // give j all edges from i |
---|
534 | } |
---|
535 | } kill k; |
---|
536 | } |
---|
537 | } kill j; |
---|
538 | G = imDelRowCol(G,i,i); // remove vertex i |
---|
539 | } |
---|
540 | } kill i; |
---|
541 | return (G); |
---|
542 | } |
---|
543 | |
---|
544 | static proc imDelRowCol(intmat M, int row, int col) { |
---|
545 | // row and col are expected to be > 0 |
---|
546 | int nr = nrows(M); |
---|
547 | int nc = ncols(M); |
---|
548 | intmat Mdel[nr - 1][nc - 1]; |
---|
549 | for (int i = 1; i <= nr; i++) { |
---|
550 | for (int j = 1; j <= nc; j++) { |
---|
551 | if(i != row && j != col) { |
---|
552 | int newi = i; |
---|
553 | int newj = j; |
---|
554 | if (i > row) { newi = i - 1; } |
---|
555 | if (j > col) { newj = j - 1; } |
---|
556 | Mdel[newi,newj] = M[i,j]; |
---|
557 | kill newi; kill newj; |
---|
558 | } |
---|
559 | } kill j; |
---|
560 | } kill i; |
---|
561 | return (Mdel); |
---|
562 | } |
---|
563 | |
---|
564 | static proc topologicalSort(intmat G) { |
---|
565 | // NOTE: ignores loops |
---|
566 | // NOTE: this takes O(|V^3|), can be optimized |
---|
567 | int n = ncols(G); |
---|
568 | for (int i = 1; i <= n; i++) { // only use the submat at i |
---|
569 | // find a vertex v in the submat at i with no incoming edges |
---|
570 | int v; |
---|
571 | for (int j = i; j <= n; j++) { |
---|
572 | int incoming = 0; |
---|
573 | for (int k = i; k <= n; k++) { |
---|
574 | if (k != j && G[k,j] == 1) { |
---|
575 | incoming = 1; |
---|
576 | } |
---|
577 | } kill k; |
---|
578 | if (incoming == 0) { |
---|
579 | v = j; |
---|
580 | kill incoming; |
---|
581 | break; |
---|
582 | } else { |
---|
583 | if (j == n) { |
---|
584 | // G contains at least one cycle, abort |
---|
585 | return (G); |
---|
586 | } |
---|
587 | } |
---|
588 | kill incoming; |
---|
589 | } kill j; |
---|
590 | |
---|
591 | // swap v and i |
---|
592 | if (v != i) { |
---|
593 | G = imPermcol(G, v, i); |
---|
594 | G = imPermrow(G, v, i); |
---|
595 | } |
---|
596 | kill v; |
---|
597 | } kill i; |
---|
598 | return (G); |
---|
599 | } |
---|
600 | |
---|
601 | static proc imPermcol (intmat A, int c1, int c2) |
---|
602 | { |
---|
603 | intmat B = A; |
---|
604 | int k = nrows(B); |
---|
605 | B[1..k,c1] = A[1..k,c2]; |
---|
606 | B[1..k,c2] = A[1..k,c1]; |
---|
607 | return (B); |
---|
608 | } |
---|
609 | |
---|
610 | static proc imPermrow (intmat A, int r1, int r2) |
---|
611 | { |
---|
612 | intmat B = A; |
---|
613 | int k = ncols(B); |
---|
614 | B[r1,1..k] = A[r2,1..k]; |
---|
615 | B[r2,1..k] = A[r1,1..k]; |
---|
616 | return (B); |
---|
617 | } |
---|
618 | |
---|
619 | static proc UfGraphGrowth(intmat UG) |
---|
620 | { |
---|
621 | int n = ncols(UG); // number of vertices |
---|
622 | // iterate through all vertices |
---|
623 | |
---|
624 | intvec visited = 0:n; |
---|
625 | intvec cyclic = 0:n; |
---|
626 | intvec countedCycles = -2:n; |
---|
627 | |
---|
628 | int maxCycleCount = 0; |
---|
629 | for (int v = 1; v <= n; v++) { |
---|
630 | countedCycles = countCycles(UG, v, visited, cyclic, 0, countedCycles); |
---|
631 | dbprint("counted " + string(countedCycles[v]) + " cycles from vertex " + string(v) + "/" + string(n) + " (cache: " + string(countedCycles) + ")"); |
---|
632 | if (countedCycles[v] == -1) { |
---|
633 | return(-1); |
---|
634 | } |
---|
635 | if (countedCycles[v] > maxCycleCount) { |
---|
636 | maxCycleCount = countedCycles[v]; |
---|
637 | } |
---|
638 | } kill v; |
---|
639 | return (maxCycleCount); |
---|
640 | } |
---|
641 | |
---|
642 | static proc countCycles(intmat G, int v, intvec visited, intvec cyclic, intvec path, intvec countedCycles) |
---|
643 | "USAGE: countCycles(G, v, visited, cyclic, path); G a Graph, v the vertex to |
---|
644 | start. The parameter visited, cyclic and path should be 0. |
---|
645 | RETURN: int |
---|
646 | Maximal number of distinct cycles |
---|
647 | PURPOSE: Calculate the maximal number of distinct cycles in a single path starting at v |
---|
648 | ASSUME: Basering is a Letterplace ring |
---|
649 | " |
---|
650 | { |
---|
651 | if (countedCycles[v] > -2) { |
---|
652 | return (countedCycles); |
---|
653 | } |
---|
654 | // Mark the current vertex as visited |
---|
655 | visited[v] = 1; |
---|
656 | |
---|
657 | // Store the current vertex in path |
---|
658 | if (path[1] == 0) { |
---|
659 | path[1] = v; |
---|
660 | } else { |
---|
661 | path[size(path) + 1] = v; |
---|
662 | } |
---|
663 | |
---|
664 | int cycles = 0; |
---|
665 | for (int w = 1; w <= ncols(G); w++) { |
---|
666 | if (G[v,w] == 1) { |
---|
667 | if (visited[w] == 1) { // found new cycle |
---|
668 | // 1. for all vertices in path until w, check if they are cyclic |
---|
669 | for (int j = size(path); j >= 1; j--) { |
---|
670 | if(cyclic[path[j]] == 1) { |
---|
671 | // 1.1 if yes, return -1 |
---|
672 | countedCycles[v] = -1; |
---|
673 | return (countedCycles); |
---|
674 | } |
---|
675 | if (path[j] == w) { |
---|
676 | break; |
---|
677 | } |
---|
678 | } kill j; |
---|
679 | |
---|
680 | // 2. otherwise cycles++ |
---|
681 | for (int j = size(path); j >= 1; j--) { |
---|
682 | // 2.2 remove the edges from that cycle and mark the vertices as cyclic |
---|
683 | if (j == size(path)) { // special case in the first iteration |
---|
684 | cyclic[v] = 1; |
---|
685 | G[v, w] = 0; |
---|
686 | } else { |
---|
687 | cyclic[path[j]] = 1; |
---|
688 | G[path[j], path[j+1]] = 0; |
---|
689 | } |
---|
690 | if (path[j] == w) { |
---|
691 | break; |
---|
692 | } |
---|
693 | } kill j; |
---|
694 | |
---|
695 | // 3. countCycles() on all these vertices |
---|
696 | int maxCycleCount = 0; |
---|
697 | for (int j = size(path); j >= 1; j--) { |
---|
698 | countedCycles = countCycles(G, path[j], visited, cyclic, path, countedCycles); |
---|
699 | if(countedCycles[path[j]] == -1) { |
---|
700 | countedCycles[v] = -1; |
---|
701 | return (countedCycles); |
---|
702 | } |
---|
703 | if (countedCycles[path[j]] > maxCycleCount) { |
---|
704 | maxCycleCount = countedCycles[path[j]]; |
---|
705 | } |
---|
706 | if (path[j] == w) { |
---|
707 | break; |
---|
708 | } |
---|
709 | } kill j; |
---|
710 | if (maxCycleCount >= cycles) { |
---|
711 | cycles = maxCycleCount + 1; |
---|
712 | } |
---|
713 | kill maxCycleCount; |
---|
714 | } else { |
---|
715 | countedCycles = countCycles(G, w, visited, cyclic, path, countedCycles); |
---|
716 | if (countedCycles[w] == -1) { |
---|
717 | countedCycles[v] = -1; |
---|
718 | return (countedCycles); |
---|
719 | } |
---|
720 | if (countedCycles[w] > cycles) { |
---|
721 | cycles = countedCycles[w]; |
---|
722 | } |
---|
723 | } |
---|
724 | } |
---|
725 | } kill w; |
---|
726 | countedCycles[v] = cycles; |
---|
727 | return (countedCycles); |
---|
728 | } |
---|
729 | |
---|
730 | proc lpUfGraph(ideal G, list #) |
---|
731 | "USAGE: lpUfGraph(G); G a set of monomials in a letterplace ring. |
---|
732 | RETURN: intmat or list |
---|
733 | NOTE: lpUfGraph(G); returns intmat. lpUfGraph(G,1); returns list L with L[1] an intmat and L[2] an ideal. |
---|
734 | The intmat is the Ufnarovskij Graph and the ideal contains the vertices. |
---|
735 | PURPOSE: Constructs the Ufnarovskij graph induced by G |
---|
736 | the adjacency matrix of the Ufnarovskij graph induced by G |
---|
737 | ASSUME: - basering is a Letterplace ring |
---|
738 | - G are the leading monomials of a Groebner basis |
---|
739 | " |
---|
740 | { |
---|
741 | dbprint("computing maxDeg"); |
---|
742 | int l = maxDeg(G); |
---|
743 | if (l - 1 == 0) { |
---|
744 | // TODO: how should the graph look like when l - 1 = 0 ? |
---|
745 | ERROR("Ufnarovskij graph not implemented for l = 1"); |
---|
746 | } |
---|
747 | int lV = lpVarBlockSize(basering); |
---|
748 | // TODO: what if l <= 0? |
---|
749 | dbprint("computing standard words"); |
---|
750 | ideal SW = lpStandardWords(G, l - 1); // vertices |
---|
751 | int n = ncols(SW); |
---|
752 | dbprint("n = " + string(n)); |
---|
753 | intmat UG[n][n]; // Ufnarovskij graph |
---|
754 | for (int i = 1; i <= n; i++) { |
---|
755 | for (int j = 1; j <= n; j++) { |
---|
756 | dbprint("Ufnarovskii graph: " + string((i-1)*n + j) + "/" + string(n*n) + " entries"); |
---|
757 | // [Studzinski page 76] |
---|
758 | poly v = SW[i]; |
---|
759 | poly w = SW[j]; |
---|
760 | intvec v_overlap; |
---|
761 | intvec w_overlap; |
---|
762 | if (l - 1 > 1) { |
---|
763 | v_overlap = leadexp(v); |
---|
764 | w_overlap = leadexp(w); |
---|
765 | v_overlap = v_overlap[(lV+1) .. (l-1)*lV]; |
---|
766 | w_overlap = w_overlap[1 .. (l-2)*lV]; |
---|
767 | } |
---|
768 | if (v_overlap == w_overlap && !lpLmDivides(G, v * lpVarAt(w, l - 1))) { |
---|
769 | UG[i,j] = 1; |
---|
770 | } |
---|
771 | kill v; kill w; kill v_overlap; kill w_overlap; |
---|
772 | } kill j; |
---|
773 | } kill i; |
---|
774 | if (size(#) > 0) { |
---|
775 | if (typeof(#[1]) == "int") { |
---|
776 | if (#[1] != 0) { |
---|
777 | list ret = UG; |
---|
778 | ret[2] = SW; // the vertices |
---|
779 | return (ret); |
---|
780 | } |
---|
781 | } |
---|
782 | } |
---|
783 | return (UG); |
---|
784 | } |
---|
785 | example |
---|
786 | { |
---|
787 | "EXAMPLE:"; echo = 2; |
---|
788 | ring r = 0,(x,y,z),dp; |
---|
789 | def R = freeAlgebra(r, 5); // constructs a Letterplace ring |
---|
790 | setring R; // sets basering to Letterplace ring |
---|
791 | ideal I = x*y, x*z, z*y, z*z; |
---|
792 | lpUfGraph(I); |
---|
793 | lpUfGraph(I,1); |
---|
794 | } |
---|
795 | |
---|
796 | static proc maxDeg(ideal G) |
---|
797 | { |
---|
798 | int l = 0; |
---|
799 | for (int i = 1; i <= size(G); i++) { // find the max degree in G |
---|
800 | int d = deg(G[i]); |
---|
801 | if (d > l) { |
---|
802 | l = d; |
---|
803 | } |
---|
804 | kill d; |
---|
805 | } kill i; |
---|
806 | return (l); |
---|
807 | } |
---|
808 | |
---|
809 | static proc lpStandardWords(ideal G, int length) |
---|
810 | "ASSUME: G is simplified |
---|
811 | " |
---|
812 | { |
---|
813 | if (length < 0) { |
---|
814 | return (delete(ideal(0), 1)); // no standard words |
---|
815 | } |
---|
816 | |
---|
817 | ideal words = maxideal(length); |
---|
818 | for (int i = ncols(words); i >= 1; i--) { |
---|
819 | if (lpLmDivides(G, words[i])) { |
---|
820 | words = delete(words, i); |
---|
821 | } |
---|
822 | } kill i; |
---|
823 | return (words); |
---|
824 | } |
---|
825 | |
---|
826 | static proc ivStandardWords(list G, int length) |
---|
827 | "ASSUME: G is simplified |
---|
828 | " |
---|
829 | { |
---|
830 | if (length <= 0) { |
---|
831 | list words; |
---|
832 | if (length == 0 && !ivdivides(G,0)) { |
---|
833 | words[1] = 0; // iv = 0 means monom = 1 |
---|
834 | } |
---|
835 | return (words); // no standard words |
---|
836 | } |
---|
837 | int lV = lpVarBlockSize(basering); // variable count |
---|
838 | list prevWords = ivStandardWords(G, length - 1); |
---|
839 | list words; |
---|
840 | for (int i = 1; i <= lV; i++) { |
---|
841 | for (int j = 1; j <= size(prevWords); j++) { |
---|
842 | intvec word = prevWords[j]; |
---|
843 | word[length] = i; |
---|
844 | // assumes that G is simplified! |
---|
845 | if (!ivdivides(G, word)) { |
---|
846 | words = insert(words, word); |
---|
847 | } |
---|
848 | kill word; |
---|
849 | } kill j; |
---|
850 | } kill i; |
---|
851 | return (words); |
---|
852 | } |
---|
853 | |
---|
854 | static proc ivStandardWordsUpToLength(list G, int length) |
---|
855 | "ASSUME: G is simplified |
---|
856 | " |
---|
857 | { |
---|
858 | list words = ivStandardWords(G,0); |
---|
859 | if (size(words) == 0) {return (words)} |
---|
860 | for (int i = 1; i <= length; i++) { |
---|
861 | words = words + ivStandardWords(G, i); |
---|
862 | } kill i; |
---|
863 | return (words); |
---|
864 | } |
---|
865 | |
---|
866 | static proc ivdivides(list G, intvec iv) { |
---|
867 | for (int k = 1; k <= size(G); k++) { |
---|
868 | if (isIF(G[k], iv)) { |
---|
869 | return (1); |
---|
870 | } else { |
---|
871 | if (k == size(G)) { |
---|
872 | return (0); |
---|
873 | } |
---|
874 | } |
---|
875 | } kill k; |
---|
876 | return (0); |
---|
877 | } |
---|
878 | |
---|
879 | proc lpGkDim(ideal G) |
---|
880 | "USAGE: lpGkDim(G); G an ideal in a letterplace ring |
---|
881 | RETURN: int |
---|
882 | PURPOSE: Determines the Gelfand Kirillov dimension of A/<G> |
---|
883 | -1 means positive infinite |
---|
884 | ASSUME: - basering is a Letterplace ring |
---|
885 | - G is a Groebner basis |
---|
886 | " |
---|
887 | { |
---|
888 | G = lead(G); |
---|
889 | G = simplify(G, 2+4+8); |
---|
890 | |
---|
891 | // check special case 1 |
---|
892 | int l = 0; |
---|
893 | for (int i = 1; i <= size(G); i++) { |
---|
894 | // find the max degree in G |
---|
895 | int d = deg(G[i]); |
---|
896 | if (d > l) { |
---|
897 | l = d; |
---|
898 | } |
---|
899 | |
---|
900 | // also if G is the whole ring return minus infinity |
---|
901 | if (leadmonom(G[i]) == 1) { |
---|
902 | ERROR("GK-Dim not defined for 0-ring") |
---|
903 | } |
---|
904 | kill d; |
---|
905 | } kill i; |
---|
906 | // if longest word has length 1, or G is the zero ideal, we handle it as a special case |
---|
907 | if (l == 1 || size(G) == 0) { |
---|
908 | int n = lpVarBlockSize(basering); // variable count |
---|
909 | int k = size(G); |
---|
910 | if (k == n) { // V = {1} no edges |
---|
911 | return(0); |
---|
912 | } |
---|
913 | if (k == n-1) { // V = {1} with loop |
---|
914 | return(1); |
---|
915 | } |
---|
916 | if (k <= n-2) { // V = {1} with more than one loop |
---|
917 | return(-1); |
---|
918 | } |
---|
919 | } |
---|
920 | |
---|
921 | dbprint("computing Ufnarovskii graph"); |
---|
922 | intmat UG = lpUfGraph(G); |
---|
923 | if (printlevel >= voice + 1) { |
---|
924 | UG; |
---|
925 | } |
---|
926 | |
---|
927 | // check special case 2 |
---|
928 | intmat zero[nrows(UG)][ncols(UG)]; |
---|
929 | if (UG == zero) { |
---|
930 | return (0); |
---|
931 | } |
---|
932 | |
---|
933 | // check special case 3 |
---|
934 | dbprint("topological sorting of Ufnarovskii graph"); |
---|
935 | UG = topologicalSort(UG); |
---|
936 | if (printlevel >= voice + 1) { |
---|
937 | UG; |
---|
938 | } |
---|
939 | |
---|
940 | dbprint("check if Ufnarovskii graph is DAG"); |
---|
941 | if (imIsUpRightTriangle(UG)) { |
---|
942 | UG = eliminateZerosUpTriangle(UG); |
---|
943 | if (ncols(UG) == 0 || nrows(UG) == 0) { // when the diagonal was zero |
---|
944 | return (0) |
---|
945 | } |
---|
946 | dbprint("DAG detected, using URTNZD growth alg"); |
---|
947 | return(UfGraphURTNZDGrowth(UG)); |
---|
948 | } |
---|
949 | |
---|
950 | // otherwise count cycles in the Ufnarovskij Graph |
---|
951 | dbprint("not a DAG, using regular growth alg"); |
---|
952 | return(UfGraphGrowth(UG)); |
---|
953 | } |
---|
954 | example |
---|
955 | { |
---|
956 | "EXAMPLE:"; echo = 2; |
---|
957 | ring r = 0,(x,y,z),dp; |
---|
958 | def R = freeAlgebra(r, 5); // constructs a Letterplace ring |
---|
959 | R; |
---|
960 | setring R; // sets basering to Letterplace ring |
---|
961 | ideal I = z;//an example of infinite GK dimension |
---|
962 | lpGkDim(I); |
---|
963 | I = x,y,z; // gkDim = 0 |
---|
964 | lpGkDim(I); |
---|
965 | I = x*y, x*z, z*y, z*z;//gkDim = 2 |
---|
966 | lpGkDim(I); |
---|
967 | ideal G = y*x - x*y, z*x - x*z, z*y - y*z; G = std(G); |
---|
968 | G; |
---|
969 | lpGkDim(G); // 3, as expected for K[x,y,z] |
---|
970 | } |
---|
971 | |
---|
972 | proc lpGlDimBound(ideal G) |
---|
973 | "USAGE: lpGlDimBound(I); I an ideal |
---|
974 | RETURN: int, an upper bound for the global dimension, -1 means infinity |
---|
975 | PURPOSE: computing an upper bound for the global dimension |
---|
976 | ASSUME: - basering is a Letterplace ring, G is a reduced Groebner Basis |
---|
977 | EXAMPLE: example lpGlDimBound; shows example |
---|
978 | NOTE: if I = LM(I), then the global dimension is equal the Gelfand |
---|
979 | Kirillov dimension if it is finite |
---|
980 | Global dimension should be 0 for A/G = K and 1 for A/G = K<x1...xn> |
---|
981 | " |
---|
982 | { |
---|
983 | G = simplify(G,2); // remove zero generators |
---|
984 | // NOTE: Gl should be 0 for A/G = K and 1 for A/G = K<x1...xn> |
---|
985 | // G1 contains generators with single variable in LM |
---|
986 | ideal G1; |
---|
987 | for (int i = 1; i <= size(G); i++) { |
---|
988 | if (ord(G[i]) < 2) { // single variable in LM |
---|
989 | G1 = insertGenerator(G1,G[i]); |
---|
990 | } |
---|
991 | } kill i; |
---|
992 | G1 = simplify(G1,2); // remove zero generators |
---|
993 | |
---|
994 | // G = NF(G,G1) |
---|
995 | for (int i = 1; i <= ncols(G); i++) { // do not use size() here |
---|
996 | G[i] = lpNF(G[i],G1); |
---|
997 | } kill i; |
---|
998 | G = simplify(G,2); // remove zero generators |
---|
999 | |
---|
1000 | // delete variables in LM(G1) from the ring |
---|
1001 | def save = basering; |
---|
1002 | def R = basering; |
---|
1003 | if (size(G1) > 0) { |
---|
1004 | while (size(G1) > 0) { |
---|
1005 | if (lpVarBlockSize(R) > 1) { |
---|
1006 | def @R = R - string(G1[1]); |
---|
1007 | R = @R; |
---|
1008 | kill @R; |
---|
1009 | setring R; |
---|
1010 | /* ring R = lpDelVar(lp2iv(G1[1])[1]); // TODO replace with proper method */ |
---|
1011 | ideal G1 = imap(save,G1); |
---|
1012 | G1 = simplify(G1, 2); // remove zero generators |
---|
1013 | } else { |
---|
1014 | // only the field is left (no variables) |
---|
1015 | return(0); |
---|
1016 | } |
---|
1017 | } |
---|
1018 | ideal G = imap(save, G); // put this here, because when save == R this call would make G = 0 |
---|
1019 | } |
---|
1020 | |
---|
1021 | // Li p. 184 if G = LM(G), then I = LM(I) and thus glDim = gkDim if it's finite |
---|
1022 | for (int i = 1; i <= size(G); i++) { |
---|
1023 | if (G[i] != lead(G[i])) { |
---|
1024 | break; |
---|
1025 | } else { |
---|
1026 | if (i == size(G)) { // if last iteration |
---|
1027 | int gkDim = lpGkDim(G); |
---|
1028 | if (gkDim >= 0) { |
---|
1029 | return (gkDim); |
---|
1030 | } |
---|
1031 | kill gkDim; |
---|
1032 | } |
---|
1033 | } |
---|
1034 | } kill i; |
---|
1035 | |
---|
1036 | intmat GNC = lpGraphOfNChains(G); |
---|
1037 | |
---|
1038 | // assuming GNC is connected |
---|
1039 | |
---|
1040 | // TODO: maybe loop+cycle checking could be done more efficiently? |
---|
1041 | if (!imHasLoops(GNC) && imIsUpRightTriangle(topologicalSort(GNC))) { |
---|
1042 | // GNC is a DAG |
---|
1043 | intmat GNCk = GNC; |
---|
1044 | intmat zero[1][ncols(GNCk)]; |
---|
1045 | int k = 1; |
---|
1046 | // while first row isn't empty |
---|
1047 | while (GNCk[1,1..(ncols(GNCk))] != zero[1,1..(ncols(zero))]) { |
---|
1048 | GNCk = GNCk * GNC; |
---|
1049 | k++; |
---|
1050 | } |
---|
1051 | // k-1 = number of edges in longest path starting from 1 |
---|
1052 | return (k-1); |
---|
1053 | } else { |
---|
1054 | // GNC contains loops/cycles => there is always an n-chain |
---|
1055 | return (-1); // infinity |
---|
1056 | } |
---|
1057 | } |
---|
1058 | example |
---|
1059 | { |
---|
1060 | "EXAMPLE:"; echo = 2; |
---|
1061 | ring r = 0,(x,y),dp; |
---|
1062 | def R = freeAlgebra(r, 5); // constructs a Letterplace ring |
---|
1063 | setring R; // sets basering to Letterplace ring |
---|
1064 | ideal G = x*x, y*y,x*y*x; // it is a monomial Groebner basis |
---|
1065 | lpGlDimBound(G); |
---|
1066 | ideal H = y*x - x*y; H = std(H); // H is a Groebner basis |
---|
1067 | lpGlDimBound(H); // gl dim of K[x,y] is 2, as expected |
---|
1068 | } |
---|
1069 | |
---|
1070 | static proc imHasLoops(intmat A) { |
---|
1071 | int n = ncols(A); |
---|
1072 | for (int i = 1; i <= n; i++) { |
---|
1073 | if (A[i,i] == 1) { |
---|
1074 | return (1); |
---|
1075 | } |
---|
1076 | } kill i; |
---|
1077 | return (0); |
---|
1078 | } |
---|
1079 | |
---|
1080 | static proc lpGraphOfNChains(ideal G) // G must be reduced |
---|
1081 | { |
---|
1082 | list LG = lpId2ivLi(lead(G)); |
---|
1083 | int n = lpVarBlockSize(basering); |
---|
1084 | int degbound = lpDegBound(basering); |
---|
1085 | |
---|
1086 | list V; |
---|
1087 | for (int i = 0; i <= n; i++) { |
---|
1088 | V[i+1] = i; // add 1 and all variables |
---|
1089 | } kill i; |
---|
1090 | for (int i = 1; i <= size(LG); i++) { |
---|
1091 | intvec u = LG[i]; |
---|
1092 | for (int j = 2; j <= size(u); j++) { |
---|
1093 | intvec v = u[j..size(u)]; |
---|
1094 | if (!contains(V, v)) { |
---|
1095 | V = insert(V, v, size(V)); // add subword j..size |
---|
1096 | } |
---|
1097 | kill v; |
---|
1098 | } kill j; |
---|
1099 | kill u; |
---|
1100 | } kill i; |
---|
1101 | int nV = size(V); |
---|
1102 | intmat GNC[nV][nV]; // graph of n-chains |
---|
1103 | |
---|
1104 | // for vertex 1 |
---|
1105 | for (int i = 2; i <= n + 1; i++) { |
---|
1106 | GNC[1,i] = 1; // 1 has an edge to all variables |
---|
1107 | } kill i; |
---|
1108 | |
---|
1109 | // for the other vertices |
---|
1110 | for (int i = 2; i <= nV; i++) { |
---|
1111 | for (int j = 2; j <= nV; j++) { |
---|
1112 | intvec uv = V[i],V[j]; |
---|
1113 | |
---|
1114 | if (contains(LG, uv)) { |
---|
1115 | GNC[i,j] = 1; |
---|
1116 | } else { |
---|
1117 | // Li p. 177 |
---|
1118 | // search for a right divisor 'w' of uv in G |
---|
1119 | // then check if G doesn't divide the subword uv-1 |
---|
1120 | |
---|
1121 | // look for a right divisor in LG |
---|
1122 | for (int k = 1; k <= size(LG); k++) { |
---|
1123 | if (isSF(LG[k], uv)) { |
---|
1124 | // w = LG[k] |
---|
1125 | if(!ivdivides(LG, uv[1..(size(uv)-1)])) { |
---|
1126 | // G doesn't divide uv-1 |
---|
1127 | GNC[i,j] = 1; |
---|
1128 | break; |
---|
1129 | } |
---|
1130 | } |
---|
1131 | } kill k; |
---|
1132 | } |
---|
1133 | kill uv; |
---|
1134 | } kill j; |
---|
1135 | } kill i; |
---|
1136 | |
---|
1137 | return(GNC); |
---|
1138 | } |
---|
1139 | |
---|
1140 | static proc contains(list L, def item) |
---|
1141 | { |
---|
1142 | for (int i = 1; i <= size(L); i++) { |
---|
1143 | if (L[i] == item) { |
---|
1144 | return (1); |
---|
1145 | } |
---|
1146 | } kill i; |
---|
1147 | return (0); |
---|
1148 | } |
---|
1149 | |
---|
1150 | proc lpSubstitute(poly f, ideal s1, ideal s2, list #) |
---|
1151 | "USAGE: lpSubstitute(f,s1,s2[,G]); f poly, s1 list (ideal) of variables |
---|
1152 | to replace, s2 list (ideal) of polynomials to replace with, G optional ideal to |
---|
1153 | reduce with. |
---|
1154 | RETURN: poly, the substituted polynomial |
---|
1155 | ASSUME: - basering is a Letterplace ring |
---|
1156 | - s1 contains a subset of the set of variables |
---|
1157 | - s2 and s1 are of the same size |
---|
1158 | - G is a Groebner basis, |
---|
1159 | - the current ring has a sufficient degbound (which also can be calculated with lpCalcSubstDegBound()) |
---|
1160 | NOTE: the procedure implements the image of a polynomial f |
---|
1161 | under an endomorphism of a free algebra, defined by s1 and s2: |
---|
1162 | variables, not present in s1, are left unchanged; |
---|
1163 | variable s1[k] is mapped to a polynomial s2[k]. |
---|
1164 | - An optional ideal G extends the endomorphism as above to the morphism into the factor algebra K<X>/G. |
---|
1165 | EXAMPLE: example lpSubstitute; shows examples |
---|
1166 | " |
---|
1167 | { |
---|
1168 | ideal G; |
---|
1169 | if (size(#) > 0) { |
---|
1170 | if (typeof(#[1])=="ideal") { |
---|
1171 | G = #[1]; |
---|
1172 | } |
---|
1173 | } |
---|
1174 | |
---|
1175 | poly fs; |
---|
1176 | for (int i = 1; i <= size(f); i++) { |
---|
1177 | poly fis = leadcoef(f[i]); |
---|
1178 | intvec ivfi = lp2iv(f[i]); |
---|
1179 | for (int j = 1; j <= size(ivfi); j++) { |
---|
1180 | int varindex = ivfi[j]; |
---|
1181 | if (varindex > 0) { |
---|
1182 | int subindex = lpIndexOf(s1, var(varindex)); |
---|
1183 | if (subindex > 0) { |
---|
1184 | s2[subindex] = lpNF(s2[subindex],G); |
---|
1185 | fis = fis * s2[subindex]; |
---|
1186 | } else { |
---|
1187 | fis = fis * lpNF(iv2lp(varindex),G); |
---|
1188 | } |
---|
1189 | /*fis = lpNF(fis,G);*/ |
---|
1190 | kill subindex; |
---|
1191 | } |
---|
1192 | kill varindex; |
---|
1193 | } kill j; |
---|
1194 | kill ivfi; |
---|
1195 | fs = fs + fis; |
---|
1196 | kill fis; |
---|
1197 | } |
---|
1198 | kill i; |
---|
1199 | fs = lpNF(fs, G); |
---|
1200 | return (fs); |
---|
1201 | } |
---|
1202 | example |
---|
1203 | { |
---|
1204 | "EXAMPLE:"; echo = 2; |
---|
1205 | ring r = 0,(x,y,z),dp; |
---|
1206 | def R = freeAlgebra(r, 4); |
---|
1207 | setring R; |
---|
1208 | ideal G = x*y; // optional |
---|
1209 | poly f = 3*x*x+y*x; |
---|
1210 | ideal s1 = x, y; |
---|
1211 | ideal s2 = y*z*z, x; // i.e. x --> yzz and y --> x |
---|
1212 | // the substitution probably needs a higher degbound |
---|
1213 | int minDegBound = lpCalcSubstDegBound(f,s1,s2); |
---|
1214 | minDegBound; // thus the bound needs to be increased |
---|
1215 | setring r; // back to original r |
---|
1216 | def R1 = freeAlgebra(r, minDegBound); |
---|
1217 | setring R1; |
---|
1218 | lpSubstitute(imap(R,f), imap(R,s1), imap(R,s2)); |
---|
1219 | // the last parameter is optional; above it was G=<xy> |
---|
1220 | // the output will be reduced with respect to G |
---|
1221 | lpSubstitute(imap(R,f), imap(R,s1), imap(R,s2), imap(R,G)); |
---|
1222 | } |
---|
1223 | |
---|
1224 | // another example: |
---|
1225 | /* |
---|
1226 | //////// EXAMPLE B //////// |
---|
1227 | ring r = 0,(x,y,z),dp; |
---|
1228 | def R = freeAlgebra(r, 4); |
---|
1229 | setring R; |
---|
1230 | |
---|
1231 | poly f = 3*x*x+y*x; |
---|
1232 | poly g = z*x+y; |
---|
1233 | poly h = 7*x*z+x; |
---|
1234 | ideal I = f,g,h; |
---|
1235 | ideal s1 = x, y; |
---|
1236 | ideal s2 = y*z*z, x; |
---|
1237 | |
---|
1238 | int minDegBound = lpCalcSubstDegBound(I,s1,s2); |
---|
1239 | setring r; |
---|
1240 | def R1 = freeAlgebra(r, minDegBound); |
---|
1241 | setring R1; |
---|
1242 | |
---|
1243 | ideal I = imap(R,I); |
---|
1244 | ideal s1 = imap(R,s1); |
---|
1245 | ideal s2 = imap(R,s2); |
---|
1246 | for (int i = 1; i <= size(I); i++) { |
---|
1247 | lpSubstitute(I[i], s1, s2); |
---|
1248 | } |
---|
1249 | */ |
---|
1250 | |
---|
1251 | static proc lpIndexOf(ideal I, poly p) { |
---|
1252 | for (int i = 1; i <= size(I); i++) { |
---|
1253 | if (I[i] == p) { |
---|
1254 | return (i); |
---|
1255 | } |
---|
1256 | } kill i; |
---|
1257 | return (-1); |
---|
1258 | } |
---|
1259 | |
---|
1260 | static proc ivIndexOf(list L, intvec iv) { |
---|
1261 | for (int i = 1; i <= size(L); i++) { |
---|
1262 | if (L[i] == iv) { |
---|
1263 | return (i); |
---|
1264 | } |
---|
1265 | } kill i; |
---|
1266 | return (-1); |
---|
1267 | } |
---|
1268 | |
---|
1269 | |
---|
1270 | static proc lpCalcSubstDegBoundSingle(poly f, ideal s1, ideal s2) |
---|
1271 | "USAGE: lpCalcSubstDegBoundSingle(f,s1,s2); f letterplace polynomial, s1 list (ideal) of variables |
---|
1272 | to replace, s2 list (ideal) of polynomials to replace with |
---|
1273 | RETURN: int, the min degbound required to perform the substitution |
---|
1274 | ASSUME: - basering is a Letterplace ring |
---|
1275 | EXAMPLE: example lpCalcSubstDegBoundSingle; shows examples |
---|
1276 | " |
---|
1277 | { |
---|
1278 | int maxDegBound = 0; |
---|
1279 | for (int i = 1; i <= size(f); i++) { |
---|
1280 | intvec ivfi = lp2iv(f[i]); |
---|
1281 | int tmpDegBound; |
---|
1282 | for (int j = 1; j <= size(ivfi); j++) { |
---|
1283 | int varindex = ivfi[j]; |
---|
1284 | if (varindex > 0) { |
---|
1285 | int subindex = lpIndexOf(s1, var(varindex)); |
---|
1286 | if (subindex > 0) { |
---|
1287 | tmpDegBound = tmpDegBound + deg(s2[subindex]); |
---|
1288 | } else { |
---|
1289 | tmpDegBound = tmpDegBound + 1; |
---|
1290 | } |
---|
1291 | kill subindex; |
---|
1292 | } |
---|
1293 | kill varindex; |
---|
1294 | } kill j; |
---|
1295 | if (tmpDegBound > maxDegBound) { |
---|
1296 | maxDegBound = tmpDegBound; |
---|
1297 | } |
---|
1298 | kill ivfi; kill tmpDegBound; |
---|
1299 | } kill i; |
---|
1300 | |
---|
1301 | // increase degbound by 50% when ideal is provided |
---|
1302 | // needed for lpNF |
---|
1303 | maxDegBound = maxDegBound + (maxDegBound div 2); |
---|
1304 | |
---|
1305 | return (maxDegBound); |
---|
1306 | } |
---|
1307 | example |
---|
1308 | { |
---|
1309 | // see lpCalcSubstDegBound() |
---|
1310 | } |
---|
1311 | |
---|
1312 | proc lpCalcSubstDegBound(ideal I, ideal s1, ideal s2) |
---|
1313 | "USAGE: lpCalcSubstDegBound(I,s1,s2); I ideal of polynomials, s1 ideal of variables to replace, s2 ideal of polynomials to replace with |
---|
1314 | RETURN: int, the min degbound required to perform all of the substitutions |
---|
1315 | ASSUME: - basering is a Letterplace ring |
---|
1316 | EXAMPLE: example lpCalcSubstDegBound; shows examples |
---|
1317 | NOTE: convenience method |
---|
1318 | " |
---|
1319 | { |
---|
1320 | int maxDegBound = 0; |
---|
1321 | for (int i = 1; i <= size(I); i++) { |
---|
1322 | int tmpDegBound = lpCalcSubstDegBoundSingle(I[i], s1, s2, #); |
---|
1323 | if (tmpDegBound > maxDegBound) { |
---|
1324 | maxDegBound = tmpDegBound; |
---|
1325 | } |
---|
1326 | kill tmpDegBound; |
---|
1327 | } kill i; |
---|
1328 | return (maxDegBound); |
---|
1329 | } |
---|
1330 | example |
---|
1331 | { |
---|
1332 | "EXAMPLE:"; echo = 2; |
---|
1333 | ring r = 0,(x,y,z),dp; |
---|
1334 | def R = freeAlgebra(r, 4); |
---|
1335 | setring R; |
---|
1336 | ideal I = 3*x*x+y*x, x*y*x - z; |
---|
1337 | ideal s1 = x, y; // z --> z |
---|
1338 | ideal s2 = y*z*z, x; // i.e. x --> yzz and y --> x |
---|
1339 | // the substitution probably needs a higher degbound |
---|
1340 | lpCalcSubstDegBound(I,s1,s2); |
---|
1341 | lpCalcSubstDegBound(I[1],s1,s2); |
---|
1342 | } |
---|
1343 | |
---|
1344 | static proc isSF(intvec S, intvec I) |
---|
1345 | " |
---|
1346 | PURPOSE: |
---|
1347 | checks, if a word S is a suffix of another word I |
---|
1348 | " |
---|
1349 | { |
---|
1350 | int n = size(S); |
---|
1351 | if (n <= 0 || S == 0) {return(1);} |
---|
1352 | int m = size(I); |
---|
1353 | if (m < n) {return(0);} |
---|
1354 | intvec IS = I[(m-n+1)..m]; |
---|
1355 | if (IS == S) {return(1);} |
---|
1356 | else {return(0);} |
---|
1357 | } |
---|
1358 | |
---|
1359 | static proc isIF(intvec IF, intvec I) |
---|
1360 | " |
---|
1361 | PURPOSE: |
---|
1362 | checks, if a word IF is an infix of another word I |
---|
1363 | " |
---|
1364 | { |
---|
1365 | int n = size(IF); |
---|
1366 | int m = size(I); |
---|
1367 | |
---|
1368 | if (n <= 0 || IF == 0) {return(1);} |
---|
1369 | if (m < n) {return(0);} |
---|
1370 | |
---|
1371 | for (int i = 0; (n + i) <= m; i++){ |
---|
1372 | intvec IIF = I[(1 + i)..(n + i)]; |
---|
1373 | if (IIF == IF) { |
---|
1374 | return(1); |
---|
1375 | } |
---|
1376 | kill IIF; |
---|
1377 | } kill i; |
---|
1378 | return(0); |
---|
1379 | } |
---|
1380 | |
---|
1381 | // no longer working with new interface and new orderings |
---|
1382 | /* // TODO: use original ring attrib to create a new letterplace ring */ |
---|
1383 | /* // removes a variable from a letterplace ring (a bit of a hack) */ |
---|
1384 | /* static proc lpDelVar(int index) { */ |
---|
1385 | /* int lV = lpVarBlockSize(basering); // number of variables in the main block */ |
---|
1386 | /* int d = lpDegBound(basering); // degree bround */ |
---|
1387 | /* list LR = ringlist(basering); */ |
---|
1388 | |
---|
1389 | /* if (!(index >= 1 && index <= lV)) { return (basering); } // invalid index */ |
---|
1390 | |
---|
1391 | /* // remove frome the variable list */ |
---|
1392 | /* for (int i = (d-1)*lV + index; i >= 1; i = i - lV) { */ |
---|
1393 | /* LR[2] = delete(LR[2], i); */ |
---|
1394 | /* } kill i; */ |
---|
1395 | |
---|
1396 | /* // remove from a ordering */ |
---|
1397 | /* intvec aiv = LR[3][1][2]; */ |
---|
1398 | /* aiv = aiv[1..(d*lV-d)]; */ |
---|
1399 | /* LR[3][1][2] = aiv; */ |
---|
1400 | |
---|
1401 | /* // remove block orderings */ |
---|
1402 | /* int del = (lV - index); */ |
---|
1403 | /* int cnt = -1; */ |
---|
1404 | /* for (int i = size(LR[3]); i >= 2; i--) { */ |
---|
1405 | /* if (LR[3][i][2] != 0) { */ |
---|
1406 | /* for (int j = size(LR[3][i][2]); j >= 1; j--) { */ |
---|
1407 | /* cnt++; // next 1 */ |
---|
1408 | /* if (cnt%lV == del) { */ |
---|
1409 | /* // delete */ |
---|
1410 | /* if (size(LR[3][i][2]) > 1) { // if we have more than one element left, delete one */ |
---|
1411 | /* LR[3][i][2] = delete(LR[3][i][2],j); */ |
---|
1412 | /* } else { // otherwise delete the whole block */ |
---|
1413 | /* LR[3] = delete(LR[3], i); */ |
---|
1414 | /* break; */ |
---|
1415 | /* } */ |
---|
1416 | /* } */ |
---|
1417 | /* } kill j; */ |
---|
1418 | /* } */ |
---|
1419 | /* } kill i; */ |
---|
1420 | |
---|
1421 | /* def R = setLetterplaceAttributes(ring(LR),d,lV-1); */ |
---|
1422 | /* return (R); */ |
---|
1423 | /* } */ |
---|
1424 | /* example */ |
---|
1425 | /* { */ |
---|
1426 | /* "EXAMPLE:"; echo = 2; */ |
---|
1427 | /* ring r = 0,(x,y,z),dp; */ |
---|
1428 | /* def A = freeAlgebra(r, 3); */ |
---|
1429 | /* setring A; A; */ |
---|
1430 | /* def R = lpDelVar(2); setring R; R; */ |
---|
1431 | /* } */ |
---|