1 | /////////////////////////////////////////////////////////////////////////////// |
---|
2 | version="version algebra.lib 4.2.0.1 Mar_2021 "; // $Id$ |
---|
3 | category="Commutative Algebra"; |
---|
4 | info=" |
---|
5 | LIBRARY: algebra.lib Compute with Algbras and Algebra Maps |
---|
6 | AUTHORS: Gert-Martin Greuel, greuel@mathematik.uni-kl.de, |
---|
7 | @* Agnes Eileen Heydtmann, agnes@math.uni-sb.de, |
---|
8 | @* Gerhard Pfister, pfister@mathematik.uni-kl.de |
---|
9 | |
---|
10 | PROCEDURES: |
---|
11 | algebra_containment(); query of algebra containment |
---|
12 | module_containment(); query of module containment over a subalgebra |
---|
13 | inSubring(p,I); test whether polynomial p is in subring generated by I |
---|
14 | algDependent(I); computes algebraic relations between generators of I |
---|
15 | alg_kernel(phi); computes the kernel of the ringmap phi |
---|
16 | is_injective(phi); test for injectivity of ringmap phi |
---|
17 | is_surjective(phi); test for surjectivity of ringmap phi |
---|
18 | is_bijective(phi); test for bijectivity of ring map phi |
---|
19 | noetherNormal(id); noether normalization of ideal id |
---|
20 | mapIsFinite(R,phi,I); query for finiteness of map phi:R --> basering/I |
---|
21 | |
---|
22 | finitenessTest(i,z); find variables which occur as pure power in lead(i) |
---|
23 | nonZeroEntry(id); list describing non-zero entries of an identifier |
---|
24 | "; |
---|
25 | |
---|
26 | LIB "inout.lib"; |
---|
27 | LIB "elim.lib"; |
---|
28 | LIB "ring.lib"; |
---|
29 | LIB "matrix.lib"; |
---|
30 | |
---|
31 | /////////////////////////////////////////////////////////////////////////////// |
---|
32 | |
---|
33 | proc algebra_containment (poly p, ideal A, list #) |
---|
34 | "USAGE: algebra_containment(p,A[,k]); p poly, A ideal, k integer. |
---|
35 | @* A = A[1],...,A[m] generators of subalgebra of the basering |
---|
36 | RETURN: |
---|
37 | @format |
---|
38 | - k=0 (or if k is not given) an integer: |
---|
39 | 1 : if p is contained in the subalgebra K[A[1],...,A[m]] |
---|
40 | 0 : if p is not contained in K[A[1],...,A[m]] |
---|
41 | - k=1 : a list, say l, of size 2, l[1] integer, l[2] ring, satisfying |
---|
42 | l[1]=1 if p is in the subalgebra K[A[1],...,A[m]] and then the ring |
---|
43 | l[2]: ring, contains poly check = h(y(1),...,y(m)) if p=h(A[1],...,A[m]) |
---|
44 | l[1]=0 if p is not in the subalgebra K[A[1],...,A[m]] and then |
---|
45 | l[2] contains the poly check = h(x,y(1),...,y(m)) if p satisfies |
---|
46 | the nonlinear relation p = h(x,A[1],...,A[m]) where |
---|
47 | x = x(1),...,x(n) denote the variables of the basering |
---|
48 | @end format |
---|
49 | DISPLAY: if k=0 and printlevel >= voice+1 (default) display the polynomial check |
---|
50 | NOTE: The proc inSubring uses a different algorithm which is sometimes |
---|
51 | faster. |
---|
52 | THEORY: The ideal of algebraic relations of the algebra generators A[1],..., |
---|
53 | A[m] is computed introducing new variables y(i) and the product |
---|
54 | order with x(i) >> y(i). |
---|
55 | p reduces to a polynomial only in the y(i) <=> p is contained in the |
---|
56 | subring generated by the polynomials A[1],...,A[m]. |
---|
57 | EXAMPLE: example algebra_containment; shows an example |
---|
58 | " |
---|
59 | { int DEGB = degBound; |
---|
60 | degBound = 0; |
---|
61 | if (size(#)==0) |
---|
62 | { #[1] = 0; |
---|
63 | } |
---|
64 | def br=basering; |
---|
65 | int n = nvars(br); |
---|
66 | int m = ncols(A); |
---|
67 | int i; |
---|
68 | //----------------- |
---|
69 | // neu CL 10/05: |
---|
70 | int is_qring; |
---|
71 | if (size(ideal(br))>0) |
---|
72 | { |
---|
73 | is_qring=1; |
---|
74 | ideal IdQ = ideal(br); |
---|
75 | } |
---|
76 | //----------------- |
---|
77 | // ---------- create new ring with extra variables -------------------- |
---|
78 | list l3; |
---|
79 | for (int zz = 1; zz <= n; zz++) |
---|
80 | { |
---|
81 | l3[size(l3)+1] = "x("+string(zz)+")"; |
---|
82 | } |
---|
83 | for (int yy = 1; yy <= m; yy++) |
---|
84 | { |
---|
85 | l3[size(l3)+1] = "y("+string(yy)+")"; |
---|
86 | } |
---|
87 | list RL=ringlist(br); |
---|
88 | RL[2]=l3; //vars |
---|
89 | RL[3]=list(list("dp",1:n),list("dp",1:m)); //ord |
---|
90 | RL[4]=ideal(0); // reset qring |
---|
91 | ring R=ring(RL); |
---|
92 | ideal A=fetch(br,A); |
---|
93 | poly check=fetch(br,p); |
---|
94 | for (i=1;i<=m;i=i+1) |
---|
95 | { |
---|
96 | A[i]=A[i]-y(i); |
---|
97 | } |
---|
98 | //----------------- |
---|
99 | // neu CL 10/05: |
---|
100 | if (is_qring) { A = A,fetch(br,IdQ); } |
---|
101 | //----------------- |
---|
102 | A=std(A); |
---|
103 | check=reduce(check,A); |
---|
104 | /*alternatively we could use reduce(check,A,1) which is a little faster |
---|
105 | but result is bigger since it is not tail-reduced |
---|
106 | */ |
---|
107 | //--- checking whether all variables from old ring have disappeared ------ |
---|
108 | // if so, then the sum of the first n leading exponents is 0, hence i=1 |
---|
109 | // use i also to control the display |
---|
110 | i = (sum(leadexp(check),1..n)==0); |
---|
111 | degBound = DEGB; |
---|
112 | if( #[1] == 0 ) |
---|
113 | { dbprint(printlevel-voice+3,"// "+string(check)); |
---|
114 | return(i); |
---|
115 | } |
---|
116 | else |
---|
117 | { list l = i,R; |
---|
118 | kill A; |
---|
119 | export check; |
---|
120 | dbprint(printlevel-voice+3," |
---|
121 | // 'algebra_containment' created a ring as 2nd element of the list. |
---|
122 | // The ring contains the polynomial check which defines the algebraic relation. |
---|
123 | // To access to the ring and see check you must give the ring a name, |
---|
124 | // e.g.: |
---|
125 | def S = l[2]; setring S; check; |
---|
126 | "); |
---|
127 | setring br; |
---|
128 | return(l); |
---|
129 | } |
---|
130 | } |
---|
131 | example |
---|
132 | { "EXAMPLE: Sturmfels: Algorithms in Invariant Theory 2.3.7:"; echo=2; |
---|
133 | int p = printlevel; printlevel = 1; |
---|
134 | ring R = 0,(x,y,z),dp; |
---|
135 | ideal A=x2+y2,z2,x4+y4,1,x2z-1y2z,xyz,x3y-1xy3; |
---|
136 | poly p1=z; |
---|
137 | poly p2= |
---|
138 | x10z3-x8y2z3+2x6y4z3-2x4y6z3+x2y8z3-y10z3+x6z4+3x4y2z4+3x2y4z4+y6z4; |
---|
139 | algebra_containment(p1,A); |
---|
140 | algebra_containment(p2,A); |
---|
141 | list L = algebra_containment(p2,A,1); |
---|
142 | L[1]; |
---|
143 | def S = L[2]; setring S; |
---|
144 | check; |
---|
145 | printlevel = p; |
---|
146 | } |
---|
147 | /////////////////////////////////////////////////////////////////////////////// |
---|
148 | |
---|
149 | proc module_containment(poly p, ideal P, ideal S, list #) |
---|
150 | "USAGE: module_containment(p,P,M[,k]); p poly, P ideal, M ideal, k int |
---|
151 | @* P = P[1],...,P[n] generators of a subalgebra of the basering, |
---|
152 | @* M = M[1],...,M[m] generators of a module over the subalgebra K[P] |
---|
153 | ASSUME: ncols(P) = nvars(basering), the P[i] are algebraically independent |
---|
154 | RETURN: |
---|
155 | @format |
---|
156 | - k=0 (or if k is not given), an integer: |
---|
157 | 1 : if p is contained in the module <M[1],...,M[m]> over K[P] |
---|
158 | 0 : if p is not contained in <M[1],...,M[m]> |
---|
159 | - k=1, a list, say l, of size 2, l[1] integer, l[2] ring: |
---|
160 | l[1]=1 : if p is in <M[1],...,M[m]> and then the ring l[2] contains |
---|
161 | the polynomial check = h(y(1),...,y(m),z(1),...,z(n)) if |
---|
162 | p = h(M[1],...,M[m],P[1],...,P[n]) |
---|
163 | l[1]=0 : if p is in not in <M[1],...,M[m]>, then l[2] contains the |
---|
164 | poly check = h(x,y(1),...,y(m),z(1),...,z(n)) if p satisfies |
---|
165 | the nonlinear relation p = h(x,M[1],...,M[m],P[1],...,P[n]) where |
---|
166 | x = x(1),...,x(n) denote the variables of the basering |
---|
167 | @end format |
---|
168 | DISPLAY: the polynomial h(y(1),...,y(m),z(1),...,z(n)) if k=0, resp. |
---|
169 | a comment how to access the relation check if k=1, provided |
---|
170 | printlevel >= voice+1 (default). |
---|
171 | THEORY: The ideal of algebraic relations of all the generators p1,...,pn, |
---|
172 | s1,...,st given by P and S is computed introducing new variables y(j), |
---|
173 | z(i) and the product order: x^a*y^b*z^c > x^d*y^e*z^f if x^a > x^d |
---|
174 | with respect to the lp ordering or else if z^c > z^f with respect to |
---|
175 | the dp ordering or else if y^b > y^e with respect to the lp ordering |
---|
176 | again. p reduces to a polynomial only in the y(j) and z(i), linear in |
---|
177 | the z(i) <=> p is contained in the module. |
---|
178 | EXAMPLE: example module_containment; shows an example |
---|
179 | " |
---|
180 | { def br=basering; |
---|
181 | int DEGB = degBound; |
---|
182 | degBound=0; |
---|
183 | if (size(#)==0) |
---|
184 | { #[1] = 0; |
---|
185 | } |
---|
186 | int n=nvars(br); |
---|
187 | if ( ncols(P)==n ) |
---|
188 | { int m=ncols(S); |
---|
189 | string mp=string(minpoly); |
---|
190 | // ---------- create new ring with extra variables -------------------- |
---|
191 | list l4; |
---|
192 | for (int xx = 1; xx <= n; xx++) |
---|
193 | { |
---|
194 | l4[size(l4)+1] = "x("+string(xx)+")"; |
---|
195 | } |
---|
196 | for (int yy = 1; yy <= m; yy++) |
---|
197 | { |
---|
198 | l4[size(l4)+1] = "y("+string(yy)+")"; |
---|
199 | } |
---|
200 | for (int zz = 1; zz <= n; zz++) |
---|
201 | { |
---|
202 | l4[size(l4)+1] = "z("+string(zz)+")"; |
---|
203 | } |
---|
204 | ring R = create_ring(ring_list(br)[1], l4, "(lp("+string(n)+"),dp("+string(m)+"),lp("+string(n)+"))", "no_minpoly"); |
---|
205 | if (mp!="0") |
---|
206 | { execute ("minpoly=number("+mp+");"); } |
---|
207 | ideal vars = x(1..n); |
---|
208 | map emb = br,vars; |
---|
209 | ideal P = emb(P); |
---|
210 | ideal S = emb(S); |
---|
211 | poly check = emb(p); |
---|
212 | ideal I; |
---|
213 | for (int i=1;i<=m;i=i+1) |
---|
214 | { I[i]=S[i]-y(i); |
---|
215 | } |
---|
216 | for (i=1;i<=n;i=i+1) |
---|
217 | { I[m+i]=P[i]-z(i); |
---|
218 | } |
---|
219 | I=std(I); |
---|
220 | check = reduce(check,I); |
---|
221 | //--- checking whether all variables from old ring have disappeared ------ |
---|
222 | // if so, then the sum of the first n leading exponents is 0 |
---|
223 | i = (sum(leadexp(check),1..n)==0); |
---|
224 | if( #[1] == 0 ) |
---|
225 | { dbprint(i*(printlevel-voice+3),"// "+string(check)); |
---|
226 | setring br; |
---|
227 | return(i); |
---|
228 | } |
---|
229 | else |
---|
230 | { list l = i,R; |
---|
231 | kill I,vars,emb,P,S; |
---|
232 | export check; |
---|
233 | dbprint(printlevel-voice+3," |
---|
234 | // 'module_containment' created a ring as 2nd element of the list. The |
---|
235 | // ring contains the polynomial check which defines the algebraic relation |
---|
236 | // for p. To access to the ring and see check you must give the ring |
---|
237 | // a name, e.g.: |
---|
238 | def S = l[2]; setring S; check; |
---|
239 | "); |
---|
240 | setring br; |
---|
241 | return(l); |
---|
242 | } |
---|
243 | } |
---|
244 | else |
---|
245 | { |
---|
246 | setring br; |
---|
247 | "ERROR: the first ideal must have nvars(basering) entries"; |
---|
248 | return(); |
---|
249 | } |
---|
250 | } |
---|
251 | example |
---|
252 | { "EXAMPLE: Sturmfels: Algorithms in Invariant Theory 2.3.7:"; echo=2; |
---|
253 | int p = printlevel; printlevel = 1; |
---|
254 | ring R=0,(x,y,z),dp; |
---|
255 | ideal P = x2+y2,z2,x4+y4; //algebra generators |
---|
256 | ideal M = 1,x2z-1y2z,xyz,x3y-1xy3; //module generators |
---|
257 | poly p1= |
---|
258 | x10z3-x8y2z3+2x6y4z3-2x4y6z3+x2y8z3-y10z3+x6z4+3x4y2z4+3x2y4z4+y6z4; |
---|
259 | module_containment(p1,P,M); |
---|
260 | poly p2=z; |
---|
261 | list l = module_containment(p2,P,M,1); |
---|
262 | l[1]; |
---|
263 | def S = l[2]; setring S; check; |
---|
264 | printlevel=p; |
---|
265 | } |
---|
266 | /////////////////////////////////////////////////////////////////////////////// |
---|
267 | |
---|
268 | proc inSubring(poly p, ideal I) |
---|
269 | "USAGE: inSubring(p,i); p poly, i ideal |
---|
270 | RETURN: |
---|
271 | @format |
---|
272 | a list l of size 2, l[1] integer, l[2] string |
---|
273 | l[1]=1 if and only if p is in the subring generated by i=i[1],...,i[k], |
---|
274 | and then l[2] = y(0)-h(y(1),...,y(k)) if p = h(i[1],...,i[k]) |
---|
275 | l[1]=0 if and only if p is in not the subring generated by i, |
---|
276 | and then l[2] = h(y(0),y(1),...,y(k)) where p satisfies the |
---|
277 | nonlinear relation h(p,i[1],...,i[k])=0. |
---|
278 | @end format |
---|
279 | NOTE: the proc algebra_containment tests the same using a different |
---|
280 | algorithm, which is often faster |
---|
281 | if l[1] == 0 then l[2] may contain more than one relation h(y(0),y(1),...,y(k)), |
---|
282 | separated by comma |
---|
283 | EXAMPLE: example inSubring; shows an example |
---|
284 | " |
---|
285 | {int z=ncols(I); |
---|
286 | int i; |
---|
287 | def gnir=basering; |
---|
288 | int n = nvars(gnir); |
---|
289 | string mp=string(minpoly); |
---|
290 | list l; |
---|
291 | // neu CL 10/05: |
---|
292 | int is_qring; |
---|
293 | if (size(ideal(gnir))>0) |
---|
294 | { |
---|
295 | is_qring=1; |
---|
296 | ideal IdQ = ideal(gnir); |
---|
297 | } |
---|
298 | // ---------- create new ring with extra variables -------------------- |
---|
299 | //the intersection of ideal nett=(p-y(0),I[1]-y(1),...) |
---|
300 | //with the ring k[y(0),...,y(n)] is computed, the result is ker |
---|
301 | list l5; |
---|
302 | for (int xx = 1; xx <= n; xx++) |
---|
303 | { |
---|
304 | l5[size(l5)+1] = "x("+string(xx)+")"; |
---|
305 | } |
---|
306 | for (int yy = 0; yy <= z; yy++) |
---|
307 | { |
---|
308 | l5[size(l5)+1] = "y("+string(yy)+")"; |
---|
309 | } |
---|
310 | ring r1 = create_ring(ring_list(basering)[1], l5, "lp", "no_minpoly"); |
---|
311 | if (mp!="0") |
---|
312 | { execute ("minpoly=number("+mp+");"); } |
---|
313 | ideal va = x(1..n); |
---|
314 | map emb = gnir,va; |
---|
315 | ideal nett = emb(I); |
---|
316 | for (i=1;i<=z;i++) |
---|
317 | { nett[i]=nett[i]-y(i); |
---|
318 | } |
---|
319 | nett=emb(p)-y(0),nett; |
---|
320 | // neu CL 10/05: |
---|
321 | if (is_qring) { nett = nett,emb(IdQ); } |
---|
322 | //----------------- |
---|
323 | ideal ker=eliminate(nett,product(va)); |
---|
324 | ker=std(ker); |
---|
325 | //---------- test whether y(0)-h(y(1),...,y(z)) is in ker -------------- |
---|
326 | l[1]=0; |
---|
327 | l[2]=""; |
---|
328 | for (i=1;i<=size(ker);i++) |
---|
329 | { if (deg(ker[i]/y(0))==0) |
---|
330 | { string str=string(ker[i]); |
---|
331 | setring gnir; |
---|
332 | l[1]=1; |
---|
333 | l[2]=str; |
---|
334 | return(l); |
---|
335 | } |
---|
336 | if (deg(ker[i]/y(0))>0) |
---|
337 | { if( l[2] != "" ){ l[2] = l[2] + ","; } |
---|
338 | l[2] = l[2] + string(ker[i]); |
---|
339 | } |
---|
340 | } |
---|
341 | setring gnir; |
---|
342 | return(l); |
---|
343 | } |
---|
344 | example |
---|
345 | { "EXAMPLE:"; echo = 2; |
---|
346 | ring q=0,(x,y,z,u,v,w),dp; |
---|
347 | poly p=xyzu2w-1yzu2w2+u4w2-1xu2vw+u2vw2+xyz-1yzw+2u2w-1xv+vw+2; |
---|
348 | ideal I =x-w,u2w+1,yz-v; |
---|
349 | inSubring(p,I); |
---|
350 | } |
---|
351 | ////////////////////////////////////////////////////////////////////////////// |
---|
352 | |
---|
353 | proc algDependent( ideal A, list # ) |
---|
354 | "USAGE: algDependent(f[,c]); f ideal (say, f = f1,...,fm), c integer |
---|
355 | RETURN: |
---|
356 | @format |
---|
357 | a list l of size 2, l[1] integer, l[2] ring: |
---|
358 | - l[1] = 1 if f1,...,fm are algebraic dependent, 0 if not |
---|
359 | - l[2] is a ring with variables x(1),...,x(n),y(1),...,y(m) if the |
---|
360 | basering has n variables. It contains the ideal 'ker', depending |
---|
361 | only on the y(i) and generating the algebraic relations between the |
---|
362 | f[i], i.e. substituting y(i) by fi yields 0. Of course, ker is |
---|
363 | nothing but the kernel of the ring map |
---|
364 | K[y(1),...,y(m)] ---> basering, y(i) --> fi. |
---|
365 | @end format |
---|
366 | NOTE: Three different algorithms are used depending on c = 1,2,3. |
---|
367 | If c is not given or c=0, a heuristically best method is chosen. |
---|
368 | The basering may be a quotient ring. |
---|
369 | To access to the ring l[2] and see ker you must give the ring a name, |
---|
370 | e.g. def S=l[2]; setring S; ker; |
---|
371 | DISPLAY: The above comment is displayed if printlevel >= 0 (default). |
---|
372 | EXAMPLE: example algDependent; shows an example |
---|
373 | " |
---|
374 | { |
---|
375 | int bestoption = 3; |
---|
376 | // bestoption is the default algorithm, it may be set to 1,2 or 3; |
---|
377 | // it should be changed, if another algorithm turns out to be faster |
---|
378 | // in general. Is perhaps dependent on the input (# vars, size ...) |
---|
379 | int tt; |
---|
380 | if( size(#) > 0 ) |
---|
381 | { if( typeof(#[1]) == "int" ) |
---|
382 | { tt = #[1]; |
---|
383 | } |
---|
384 | } |
---|
385 | if( size(#) == 0 or tt == 0 ) |
---|
386 | { tt = bestoption; |
---|
387 | } |
---|
388 | def br=basering; |
---|
389 | int n = nvars(br); |
---|
390 | ideal B = ideal(br); |
---|
391 | int m = ncols(A); |
---|
392 | int s = size(B); |
---|
393 | int i,@xx,@yy; |
---|
394 | string mp = string(minpoly); |
---|
395 | // --------------------- 1st variant of algorithm ---------------------- |
---|
396 | // use internal preimage command (should be equivalent to 2nd variant) |
---|
397 | if ( tt == 1 ) |
---|
398 | { |
---|
399 | list l6; |
---|
400 | for (@xx = 1; @xx <= m; @xx++) |
---|
401 | { |
---|
402 | l6[size(l6)+1] = "y("+string(@xx)+")"; |
---|
403 | } |
---|
404 | ring R1 = create_ring(ring_list(br)[1], l6, "dp", "no_minpoly"); |
---|
405 | if (mp!="0") |
---|
406 | { execute ("minpoly=number("+mp+");"); } |
---|
407 | setring br; |
---|
408 | map phi = R1,A; |
---|
409 | setring R1; |
---|
410 | ideal ker = preimage(br,phi,B); |
---|
411 | } |
---|
412 | // ---------- create new ring with extra variables -------------------- |
---|
413 | list l7; |
---|
414 | for (@xx = n; @xx >= 1; @xx--) |
---|
415 | { |
---|
416 | l7[@xx] = "x("+string(@xx)+")"; |
---|
417 | } |
---|
418 | for (@yy = m; @yy >= 1; @yy--) |
---|
419 | { |
---|
420 | l7[n+@yy] = "y("+string(@yy)+")"; |
---|
421 | } |
---|
422 | ring R2 = create_ring(ring_list(br)[1], l7, "dp", "no_minpoly"); |
---|
423 | if (mp!="0") |
---|
424 | { execute ("minpoly=number("+mp+");"); } |
---|
425 | if( tt == 1 ) |
---|
426 | { |
---|
427 | ideal ker = imap(R1,ker); |
---|
428 | } |
---|
429 | else |
---|
430 | { |
---|
431 | ideal vars = x(1..n); |
---|
432 | map emb = br,vars; |
---|
433 | ideal A = emb(A); |
---|
434 | for (i=1; i<=m; i=i+1) |
---|
435 | { A[i] = A[i]-y(i); |
---|
436 | } |
---|
437 | // --------------------- 2nd variant of algorithm ---------------------- |
---|
438 | // use internal eliminate for eliminating m variables x(i) from |
---|
439 | // ideal A[i] - y(i) (uses extra eliminating 'first row', a-order) |
---|
440 | if ( s == 0 and tt == 2 ) |
---|
441 | { ideal ker = eliminate(A,product(vars)); |
---|
442 | } |
---|
443 | else |
---|
444 | // eliminate does not work in qrings |
---|
445 | // --------------------- 3rd variant of algorithm ---------------------- |
---|
446 | // eliminate m variables x(i) from ideal A[i] - y(i) by choosing product |
---|
447 | // order |
---|
448 | { |
---|
449 | list l8; |
---|
450 | for (@xx = n; @xx >=1; @xx--) |
---|
451 | { |
---|
452 | l8[@xx] = "x("+string(@xx)+")"; |
---|
453 | } |
---|
454 | for (@yy = m; @yy >= 1; @yy--) |
---|
455 | { |
---|
456 | l8[n+@yy] = "y("+string(@yy)+")"; |
---|
457 | } |
---|
458 | setring(br); |
---|
459 | ring R3 = create_ring(ring_list(br)[1], l8, "(dp("+string(n)+"),dp("+string(m)+"))", "no_minpoly"); |
---|
460 | if (mp!="0") |
---|
461 | { execute ("minpoly=number("+mp+");"); } |
---|
462 | if ( s != 0 ) |
---|
463 | { ideal vars = x(1..n); |
---|
464 | map emb = br,vars; |
---|
465 | ideal B = emb(B); |
---|
466 | attrib(B,"isSB",1); |
---|
467 | qring Q = B; |
---|
468 | } |
---|
469 | ideal A = imap(R2,A); |
---|
470 | A = std(A); |
---|
471 | ideal ker = nselect(A,1..n); |
---|
472 | setring R2; |
---|
473 | if ( defined(Q)==voice ) |
---|
474 | { ideal ker = imap(Q,ker); |
---|
475 | } |
---|
476 | else |
---|
477 | { ideal ker = imap(R3,ker); |
---|
478 | } |
---|
479 | kill A,emb,vars; |
---|
480 | } |
---|
481 | } |
---|
482 | // --------------------------- return ---------------------------------- |
---|
483 | s = size(ker); |
---|
484 | list L = (s!=0), R2; |
---|
485 | export(ker); |
---|
486 | dbprint(printlevel-voice+3," |
---|
487 | // The 2nd element of the list l is a ring with variables x(1),...,x(n), |
---|
488 | // and y(1),...,y(m) if the basering has n variables and if the ideal |
---|
489 | // is f[1],...,f[m]. The ring contains the ideal ker which depends only |
---|
490 | // on the y(i) and generates the relations between the f[i]. |
---|
491 | // I.e. substituting y(i) by f[i] yields 0. |
---|
492 | // To access to the ring and see ker you must give the ring a name, |
---|
493 | // e.g.: |
---|
494 | def S = l[2]; setring S; ker; |
---|
495 | "); |
---|
496 | setring br; |
---|
497 | return (L); |
---|
498 | } |
---|
499 | example |
---|
500 | { "EXAMPLE:"; echo = 2; |
---|
501 | int p = printlevel; printlevel = 1; |
---|
502 | ring R = 0,(x,y,z,u,v,w),dp; |
---|
503 | ideal I = xyzu2w-1yzu2w2+u4w2-1xu2vw+u2vw2+xyz-1yzw+2u2w-1xv+vw+2, |
---|
504 | x-w, u2w+1, yz-v; |
---|
505 | list l = algDependent(I); |
---|
506 | l[1]; |
---|
507 | def S = l[2]; setring S; |
---|
508 | ker; |
---|
509 | printlevel = p; |
---|
510 | } |
---|
511 | ////////////////////////////////////////////////////////////////////////////// |
---|
512 | proc alg_kernel( map phi, def pr, list #) |
---|
513 | "USAGE: alg_kernel(phi,pr[,s,c]); phi map to basering, pr preimage ring, |
---|
514 | s string (name of kernel in pr), c integer. |
---|
515 | RETURN: a string, the kernel of phi as string. |
---|
516 | If, moreover, a string s is given, the algorithm creates, in the |
---|
517 | preimage ring pr the kernel of phi with name s. |
---|
518 | Three different algorithms are used depending on c = 1,2,3. |
---|
519 | If c is not given or c=0, a heuristically best method is chosen. |
---|
520 | (algorithm 1 uses the preimage command) |
---|
521 | NOTE: Since the kernel of phi lives in pr, it cannot be returned to the |
---|
522 | basering. If s is given, the user has access to it in pr via s. |
---|
523 | The basering may be a quotient ring. |
---|
524 | EXAMPLE: example alg_kernel; shows an example |
---|
525 | " |
---|
526 | { int tt; |
---|
527 | def BAS = basering; |
---|
528 | if( size(#) >0 ) |
---|
529 | { if( typeof(#[1]) == "int") |
---|
530 | { tt = #[1]; |
---|
531 | } |
---|
532 | if( typeof(#[1]) == "string") |
---|
533 | { string nker=#[1]; |
---|
534 | } |
---|
535 | if( size(#)>1 ) |
---|
536 | { if( typeof(#[2]) == "string") |
---|
537 | { string nker=#[2]; |
---|
538 | } |
---|
539 | if( typeof(#[2]) == "int") |
---|
540 | { tt = #[2]; |
---|
541 | } |
---|
542 | } |
---|
543 | } |
---|
544 | int n = nvars(basering); |
---|
545 | string mp = string(minpoly); |
---|
546 | ideal A = ideal(phi); |
---|
547 | //def pr = preimage(phi); |
---|
548 | //folgendes Auffuellen oder Stutzen ist ev nicht mehr noetig |
---|
549 | //falls map das richtig macht |
---|
550 | int m = nvars(pr); |
---|
551 | ideal j; |
---|
552 | j[m]=0; |
---|
553 | A=A,j; |
---|
554 | A=A[1..m]; |
---|
555 | list L = algDependent(A,tt); |
---|
556 | // algDependent is called with "bestoption" if tt = 0 |
---|
557 | def S = L[2]; |
---|
558 | list l9; |
---|
559 | for (int xx = 1; xx <= n; xx++) |
---|
560 | { |
---|
561 | l9[size(l9)+1] = "@("+string(xx)+")"; |
---|
562 | } |
---|
563 | ring R = create_ring(ring_list(basering)[1], "("+string(l9)+","+varstr(pr)+")", "dp", "no_minpoly"); |
---|
564 | if (mp!="0") |
---|
565 | { execute ("minpoly=number("+mp+");"); } |
---|
566 | ideal ker = fetch(S,ker); //in order to have variable names correct |
---|
567 | string sker = string(ker); |
---|
568 | if (defined(nker) == voice) |
---|
569 | { setring pr; |
---|
570 | execute("ideal "+nker+"="+sker+";"); |
---|
571 | execute("export("+nker+");"); |
---|
572 | } |
---|
573 | setring BAS; |
---|
574 | return(sker); |
---|
575 | } |
---|
576 | example |
---|
577 | { "EXAMPLE:"; echo = 2; |
---|
578 | ring r = 0,(a,b,c),ds; |
---|
579 | ring s = 0,(x,y,z,u,v,w),dp; |
---|
580 | ideal I = x-w,u2w+1,yz-v; |
---|
581 | map phi = r,I; // a map from r to s: |
---|
582 | alg_kernel(phi,r); // a,b,c ---> x-w,u2w+1,yz-v |
---|
583 | |
---|
584 | ring S = 0,(a,b,c),ds; |
---|
585 | ring R = 0,(x,y,z),dp; |
---|
586 | qring Q = std(x-y); |
---|
587 | ideal i = x, y, x2-y3; |
---|
588 | map phi = S,i; // a map to a quotient ring |
---|
589 | alg_kernel(phi,S,"ker",3); // uses algorithm 3 |
---|
590 | setring S; // you have access to kernel in preimage |
---|
591 | ker; |
---|
592 | } |
---|
593 | ////////////////////////////////////////////////////////////////////////////// |
---|
594 | |
---|
595 | proc is_injective( map phi,def pr,list #) |
---|
596 | "USAGE: is_injective(phi,pr[,c,s]); phi map, pr preimage ring, c int, s string |
---|
597 | RETURN: |
---|
598 | @format |
---|
599 | - 1 (type int) if phi is injective, 0 if not (if s is not given). |
---|
600 | - If s is given, return a list l of size 2, l[1] int, l[2] ring: |
---|
601 | l[1] is 1 if phi is injective, 0 if not |
---|
602 | l[2] is a ring with variables x(1),...,x(n),y(1),...,y(m) if the |
---|
603 | basering has n variables and the map m components, it contains the |
---|
604 | ideal 'ker', depending only on the y(i), the kernel of the given map |
---|
605 | @end format |
---|
606 | NOTE: Three different algorithms are used depending on c = 1,2,3. |
---|
607 | If c is not given or c=0, a heuristically best method is chosen. |
---|
608 | The basering may be a quotient ring. However, if the preimage ring is |
---|
609 | a quotient ring, say pr = P/I, consider phi as a map from P and then |
---|
610 | the algorithm returns 1 if the kernel of phi is 0 mod I. |
---|
611 | To access to the ring l[2] and see ker you must give the ring a name, |
---|
612 | e.g. def S=l[2]; setring S; ker; |
---|
613 | DISPLAY: The above comment is displayed if printlevel >= 0 (default). |
---|
614 | EXAMPLE: example is_injective; shows an example |
---|
615 | " |
---|
616 | { def bsr = basering; |
---|
617 | int tt; |
---|
618 | if( size(#) >0 ) |
---|
619 | { if( typeof(#[1]) == "int") |
---|
620 | { tt = #[1]; |
---|
621 | } |
---|
622 | if( typeof(#[1]) == "string") |
---|
623 | { string pau=#[1]; |
---|
624 | } |
---|
625 | if( size(#)>1 ) |
---|
626 | { if( typeof(#[2]) == "string") |
---|
627 | { string pau=#[2]; |
---|
628 | } |
---|
629 | if( typeof(#[2]) == "int") |
---|
630 | { tt = #[2]; |
---|
631 | } |
---|
632 | } |
---|
633 | } |
---|
634 | int n = nvars(basering); |
---|
635 | string mp = string(minpoly); |
---|
636 | ideal A = ideal(phi); |
---|
637 | //def pr = preimage(phi); |
---|
638 | //folgendes Auffuellen oder Stutzen ist ev nicht mehr noetig |
---|
639 | //falls map das richtig macht |
---|
640 | int m = nvars(pr); |
---|
641 | ideal j; |
---|
642 | j[m]=0; |
---|
643 | A=A,j; |
---|
644 | A=A[1..m]; |
---|
645 | list L = algDependent(A,tt); |
---|
646 | L[1] = L[1]==0; |
---|
647 | // the preimage ring may be a quotient ring, we still have to check whether |
---|
648 | // the kernel is 0 mod ideal of the quotient ring |
---|
649 | setring pr; |
---|
650 | if ( size(ideal(pr)) != 0 ) |
---|
651 | { def S = L[2]; |
---|
652 | ideal proj; |
---|
653 | proj [n+1..n+m] = maxideal(1); |
---|
654 | map psi = S,proj; |
---|
655 | L[1] = size(NF(psi(ker),std(0))) == 0; |
---|
656 | } |
---|
657 | setring bsr; |
---|
658 | if ( defined(pau) != voice ) |
---|
659 | { return (L[1]); |
---|
660 | } |
---|
661 | else |
---|
662 | { |
---|
663 | dbprint(printlevel-voice+3," |
---|
664 | // The 2nd element of the list is a ring with variables x(1),...,x(n), |
---|
665 | // y(1),...,y(m) if the basering has n variables and the map is |
---|
666 | // F[1],...,F[m]. |
---|
667 | // It contains the ideal ker, the kernel of the given map y(i) --> F[i]. |
---|
668 | // To access to the ring and see ker you must give the ring a name, |
---|
669 | // e.g.: |
---|
670 | def S = l[2]; setring S; ker; |
---|
671 | "); |
---|
672 | return(L); |
---|
673 | } |
---|
674 | } |
---|
675 | example |
---|
676 | { "EXAMPLE:"; echo = 2; |
---|
677 | int p = printlevel; |
---|
678 | ring r = 0,(a,b,c),ds; |
---|
679 | ring s = 0,(x,y,z,u,v,w),dp; |
---|
680 | ideal I = x-w,u2w+1,yz-v; |
---|
681 | map phi = r,I; // a map from r to s: |
---|
682 | is_injective(phi,r); // a,b,c ---> x-w,u2w+1,yz-v |
---|
683 | ring R = 0,(x,y,z),dp; |
---|
684 | ideal i = x, y, x2-y3; |
---|
685 | map phi = R,i; // a map from R to itself, z --> x2-y3 |
---|
686 | list l = is_injective(phi,R,""); |
---|
687 | l[1]; |
---|
688 | def S = l[2]; setring S; |
---|
689 | ker; |
---|
690 | } |
---|
691 | /////////////////////////////////////////////////////////////////////////////// |
---|
692 | |
---|
693 | proc is_surjective( map phi ) |
---|
694 | "USAGE: is_surjective(phi); phi map to basering, or ideal defining it |
---|
695 | RETURN: an integer, 1 if phi is surjective, 0 if not |
---|
696 | NOTE: The algorithm returns 1 if and only if all the variables of the basering are |
---|
697 | contained in the polynomial subalgebra generated by the polynomials |
---|
698 | defining phi. Hence, it tests surjectivity in the case of a global odering. |
---|
699 | If the basering has local or mixed ordering or if the preimage ring is a |
---|
700 | quotient ring (in which case the map may not be well defined) then the return |
---|
701 | value 1 needs to be interpreted with care. |
---|
702 | EXAMPLE: example is_surjective; shows an example |
---|
703 | " |
---|
704 | { |
---|
705 | def br=basering; |
---|
706 | ideal B = ideal(br); |
---|
707 | int s = size(B); |
---|
708 | int n = nvars(br); |
---|
709 | ideal A = ideal(phi); |
---|
710 | int m = ncols(A); |
---|
711 | int ii,t=1,1; |
---|
712 | string mp=string(minpoly); |
---|
713 | // ------------ create new ring with extra variables --------------------- |
---|
714 | list l10; |
---|
715 | for (int yy = 1; yy <= n; yy++) |
---|
716 | { |
---|
717 | l10[size(l10)+1] = "x("+string(yy)+")"; |
---|
718 | } |
---|
719 | for (int zz = 1; zz <= m; zz++) |
---|
720 | { |
---|
721 | l10[size(l10)+1] = "y("+string(zz)+")"; |
---|
722 | } |
---|
723 | ring R = create_ring(ring_list(br)[1], l10, "(dp("+string(n)+"),dp("+string(m)+"))", "no_minpoly"); |
---|
724 | |
---|
725 | if (mp!="0") |
---|
726 | { execute ("minpoly=number("+mp+");"); } |
---|
727 | ideal vars = x(1..n); |
---|
728 | map emb = br,vars; |
---|
729 | if ( s != 0 ) |
---|
730 | { ideal B = emb(B); |
---|
731 | attrib(B,"isSB",1); |
---|
732 | qring Q = B; |
---|
733 | ideal vars = x(1..n); |
---|
734 | map emb = br,vars; |
---|
735 | } |
---|
736 | ideal A = emb(A); |
---|
737 | for ( ii=1; ii<=m; ii++ ) |
---|
738 | { A[ii] = A [ii]-y(ii); |
---|
739 | } |
---|
740 | A=std(A); |
---|
741 | // ------------- check whether the x(i) are in the image ----------------- |
---|
742 | poly check; |
---|
743 | for (ii=1; ii<=n; ii++ ) |
---|
744 | { check=reduce(x(ii),A,1); |
---|
745 | // --- checking whether all variables from old ring have disappeared ----- |
---|
746 | // if so, then the sum of the first n leading exponents is 0 |
---|
747 | if( sum(leadexp(check),1..n)!=0 ) |
---|
748 | { t=0; |
---|
749 | break; |
---|
750 | } |
---|
751 | } |
---|
752 | setring br; |
---|
753 | return(t); |
---|
754 | } |
---|
755 | example |
---|
756 | { "EXAMPLE:"; echo = 2; |
---|
757 | ring R = 0,(x,y,z),dp; |
---|
758 | ideal i = x, y, x2-y3; |
---|
759 | map phi = R,i; // a map from R to itself, z->x2-y3 |
---|
760 | is_surjective(phi); |
---|
761 | qring Q = std(ideal(z-x37)); |
---|
762 | map psi = R, x,y,x2-y3; // the same map to the quotient ring |
---|
763 | is_surjective(psi); |
---|
764 | |
---|
765 | ring S = 0,(a,b,c),dp; |
---|
766 | map psi = R,ideal(a,a+b,c-a2+b3); // a map from R to S, |
---|
767 | is_surjective(psi); // x->a, y->a+b, z->c-a2+b3 |
---|
768 | } |
---|
769 | |
---|
770 | /////////////////////////////////////////////////////////////////////////////// |
---|
771 | |
---|
772 | proc is_bijective ( map phi,def pr ) |
---|
773 | "USAGE: is_bijective(phi,pr); phi map to basering, pr preimage ring |
---|
774 | RETURN: an integer, 1 if phi is bijective, 0 if not |
---|
775 | NOTE: The algorithm checks first injectivity and then surjectivity. |
---|
776 | To interpret this for local/mixed orderings, or for quotient rings |
---|
777 | type help is_surjective; and help is_injective; |
---|
778 | DISPLAY: A comment if printlevel >= voice-1 (default) |
---|
779 | EXAMPLE: example is_bijective; shows an example |
---|
780 | " |
---|
781 | { |
---|
782 | def br = basering; |
---|
783 | int n = nvars(br); |
---|
784 | ideal B = ideal(br); |
---|
785 | int s = size(B); |
---|
786 | ideal A = ideal(phi); |
---|
787 | //folgendes Auffuellen oder Stutzen ist ev nicht mehr noetig |
---|
788 | //falls map das richtig macht |
---|
789 | int m = nvars(pr); |
---|
790 | ideal j; |
---|
791 | j[m]=0; |
---|
792 | A=A,j; |
---|
793 | A=A[1..m]; |
---|
794 | int ii,t = 1,1; |
---|
795 | string mp=string(minpoly); |
---|
796 | // ------------ create new ring with extra variables --------------------- |
---|
797 | list l11; |
---|
798 | for (int yy = 1; yy <= n; yy++) |
---|
799 | { |
---|
800 | l11[size(l11)+1] = "x("+string(yy)+")"; |
---|
801 | } |
---|
802 | for (int zz = 1; zz <= m; zz++) |
---|
803 | { |
---|
804 | l11[size(l11)+1] = "y("+string(zz)+")"; |
---|
805 | } |
---|
806 | ring R = create_ring(ring_list(br)[1], l11, "(dp("+string(n)+"),dp("+string(m)+"))", "no_minpoly"); |
---|
807 | if (mp!="0") |
---|
808 | { execute ("minpoly=number("+mp+");"); } |
---|
809 | ideal vars = x(1..n); |
---|
810 | map emb = br,vars; |
---|
811 | if ( s != 0 ) |
---|
812 | { ideal B = emb(B); |
---|
813 | attrib(B,"isSB",1); |
---|
814 | qring Q = B; |
---|
815 | ideal vars = x(1..n); |
---|
816 | map emb = br,vars; |
---|
817 | } |
---|
818 | ideal A = emb(A); |
---|
819 | for ( ii=1; ii<=m; ii++ ) |
---|
820 | { A[ii] = A[ii]-y(ii); |
---|
821 | } |
---|
822 | A=std(A); |
---|
823 | def bsr = basering; |
---|
824 | // ------- checking whether phi is injective by computing the kernel ------- |
---|
825 | ideal ker = nselect(A,1..n); |
---|
826 | t = size(ker); |
---|
827 | setring pr; |
---|
828 | if ( size(ideal(pr)) != 0 ) |
---|
829 | { |
---|
830 | ideal proj; |
---|
831 | proj[n+1..n+m] = maxideal(1); |
---|
832 | map psi = bsr,proj; |
---|
833 | t = size(NF(psi(ker),std(0))); |
---|
834 | } |
---|
835 | if ( t != 0 ) |
---|
836 | { dbprint(printlevel-voice+3,"// map not injective" ); |
---|
837 | setring br; |
---|
838 | return(0); |
---|
839 | } |
---|
840 | else |
---|
841 | // -------------- checking whether phi is surjective ---------------------- |
---|
842 | { t = 1; |
---|
843 | setring bsr; |
---|
844 | poly check; |
---|
845 | for (ii=1; ii<=n; ii++ ) |
---|
846 | { check=reduce(x(ii),A,1); |
---|
847 | // --- checking whether all variables from old ring have disappeared ----- |
---|
848 | // if so, then the sum of the first n leading exponents is 0 |
---|
849 | if( sum(leadexp(check),1..n)!=0 ) |
---|
850 | { t=0; |
---|
851 | break; |
---|
852 | } |
---|
853 | } |
---|
854 | if ( t == 0 ) |
---|
855 | { dbprint(printlevel-voice+3,"// map injective, but not surjective" ); |
---|
856 | } |
---|
857 | setring br; |
---|
858 | return(t); |
---|
859 | } |
---|
860 | } |
---|
861 | example |
---|
862 | { "EXAMPLE:"; echo = 2; |
---|
863 | int p = printlevel; printlevel = 1; |
---|
864 | ring R = 0,(x,y,z),dp; |
---|
865 | ideal i = x, y, x2-y3; |
---|
866 | map phi = R,i; // a map from R to itself, z->x2-y3 |
---|
867 | is_bijective(phi,R); |
---|
868 | qring Q = std(z-x2+y3); |
---|
869 | is_bijective(ideal(x,y,x2-y3),Q); |
---|
870 | |
---|
871 | ring S = 0,(a,b,c,d),dp; |
---|
872 | map psi = R,ideal(a,a+b,c-a2+b3,0); // a map from R to S, |
---|
873 | is_bijective(psi,R); // x->a, y->a+b, z->c-a2+b3 |
---|
874 | qring T = std(d,c-a2+b3); |
---|
875 | map chi = Q,a,b,a2-b3; // amap between two quotient rings |
---|
876 | is_bijective(chi,Q); |
---|
877 | |
---|
878 | printlevel = p; |
---|
879 | } |
---|
880 | /////////////////////////////////////////////////////////////////////////////// |
---|
881 | |
---|
882 | proc noetherNormal(ideal i, list #) |
---|
883 | "USAGE: noetherNormal(id[,p]); id ideal, p integer |
---|
884 | RETURN: |
---|
885 | @format |
---|
886 | a list l of two ideals, say I,J: |
---|
887 | - I defines a map (coordinate change in the basering), such that: |
---|
888 | - J is generated by a subset of the variables with size(J) = dim(id) |
---|
889 | if we define map phi=basering,I; |
---|
890 | then k[var(1),...,var(n)]/phi(id) is finite over k[J]. |
---|
891 | If p is given, 0<=p<=100, a sparse coordinate change with p percent |
---|
892 | of the matrix entries being 0 (default: p=0 i.e. dense) |
---|
893 | @end format |
---|
894 | NOTE: Designed for characteristic 0.It works also in char k > 0 if it |
---|
895 | terminates,but may result in an infinite loop in small characteristic. |
---|
896 | EXAMPLE: example noetherNormal; shows an example |
---|
897 | " |
---|
898 | { |
---|
899 | i=simplify(i,2); |
---|
900 | if (size(i)== 0) |
---|
901 | { |
---|
902 | list l = maxideal(1),maxideal(1); |
---|
903 | return( l ); |
---|
904 | } |
---|
905 | int p; |
---|
906 | if( size(#) != 0 ) |
---|
907 | { |
---|
908 | p = #[1]; |
---|
909 | } |
---|
910 | def r = basering; |
---|
911 | int n = nvars(r); |
---|
912 | list good; |
---|
913 | // ------------------------ change of ordering --------------------------- |
---|
914 | //a procedure from ring.lib changing the order to dp creating a new |
---|
915 | //basering @R in order to compute the dimension d of i |
---|
916 | def @R=changeord(list(list("dp",1:nvars(basering)))); |
---|
917 | setring @R; |
---|
918 | ideal i = imap(r,i); |
---|
919 | list j = mstd(i); |
---|
920 | i = j[2]; |
---|
921 | int d = dim(j[1]); |
---|
922 | if ( d <= 0) |
---|
923 | { |
---|
924 | setring r; |
---|
925 | list l = maxideal(1),ideal(0); |
---|
926 | return( l ); |
---|
927 | } |
---|
928 | // ------------------------ change of ordering --------------------------- |
---|
929 | //Now change the order to (dp(n-d),lp) creating a new basering @S |
---|
930 | def @S=changeord(list(list("dp",1:(n-d)),list("lp",1:d))); |
---|
931 | setring @S; |
---|
932 | ideal m; |
---|
933 | |
---|
934 | // ----------------- sparse-random coordinate change -------------------- |
---|
935 | //creating lower triangular random generators for the maximal ideal |
---|
936 | //a procedure from random.lib, as sparse as possible |
---|
937 | if( char(@S) > 0 ) |
---|
938 | { |
---|
939 | m=ideal(sparsetriag(n,n,p,char(@S)+1)*transpose(maxideal(1))); |
---|
940 | } |
---|
941 | if( char(@S) == 0 ) |
---|
942 | { |
---|
943 | if ( voice <= 6 ) |
---|
944 | { |
---|
945 | m=ideal(sparsetriag(n,n,p,10)*transpose(maxideal(1))); |
---|
946 | } |
---|
947 | if( voice > 6 and voice <= 11) |
---|
948 | { |
---|
949 | m=ideal(sparsetriag(n,n,p,100)*transpose(maxideal(1))); |
---|
950 | } |
---|
951 | if ( voice > 11 ) |
---|
952 | { |
---|
953 | m=ideal(sparsetriag(n,n,p,30000)*transpose(maxideal(1))); |
---|
954 | } |
---|
955 | } |
---|
956 | |
---|
957 | map phi=r,m; |
---|
958 | //map phi=@R,m; |
---|
959 | ideal i=std(phi(i)); |
---|
960 | |
---|
961 | // ----------------------- test for finiteness --------------------------- |
---|
962 | //We need a test whether the coordinate change was random enough, if yes |
---|
963 | //we are ready, else call noetherNormal again |
---|
964 | list l=finitenessTest(i); |
---|
965 | |
---|
966 | setring r; |
---|
967 | list l=imap(@S,l); |
---|
968 | |
---|
969 | if(size(l[3]) == d) //the generic case |
---|
970 | { |
---|
971 | good = fetch(@S,m),l[3]; |
---|
972 | kill @S,@R; |
---|
973 | return(good); |
---|
974 | } |
---|
975 | else //the bad case |
---|
976 | { kill @S,@R; |
---|
977 | if ( voice >= 21 ) |
---|
978 | { |
---|
979 | "// WARNING: In case of a finite ground field"; |
---|
980 | "// the characteristic may be too small."; |
---|
981 | "// This could result in an infinite loop."; |
---|
982 | "// Loop in noetherNormal, voice:";, voice;""; |
---|
983 | } |
---|
984 | if ( voice >= 16 ) |
---|
985 | { |
---|
986 | "// Switch to dense coordinate change";""; |
---|
987 | return(noetherNormal(i)); |
---|
988 | } |
---|
989 | return(noetherNormal(i,p)); |
---|
990 | } |
---|
991 | } |
---|
992 | example |
---|
993 | { "EXAMPLE:"; echo = 2; |
---|
994 | ring r=0,(x,y,z),dp; |
---|
995 | ideal i= xy,xz; |
---|
996 | noetherNormal(i); |
---|
997 | } |
---|
998 | /////////////////////////////////////////////////////////////////////////////// |
---|
999 | |
---|
1000 | proc finitenessTest(ideal i, list #) |
---|
1001 | "USAGE: finitenessTest(J[,v]); J ideal, v intvec (say v1,...,vr with vi>0) |
---|
1002 | RETURN: |
---|
1003 | @format |
---|
1004 | a list l with l[1] integer, l[2], l[3], l[4] ideals |
---|
1005 | - l[1] = 1 if var(v1),...,var(vr) are in l[2] and 0 else |
---|
1006 | - l[2] (resp. l[3]) contains those variables which occur, |
---|
1007 | (resp. do not occur) as pure power in the leading term of one of the |
---|
1008 | generators of J, |
---|
1009 | - l[4] contains those J[i] for which the leading term is a pure power |
---|
1010 | of a variable (which is then in l[2]) |
---|
1011 | (default: v = [1,2,..,nvars(basering)]) |
---|
1012 | @end format |
---|
1013 | THEORY: If J is a standard basis of an ideal generated by x_1 - f_1(y),..., |
---|
1014 | x_n - f_n with y_j ordered lexicographically and y_j >> x_i, then, |
---|
1015 | if y_i appears as pure power in the leading term of J[k], J[k] defines |
---|
1016 | an integral relation for y_i over the y_(i+1),... and the f's. |
---|
1017 | Moreover, in this situation, if l[2] = y_1,...,y_r, then K[y_1,...y_r] |
---|
1018 | is finite over K[f_1..f_n]. If J contains furthermore polynomials |
---|
1019 | h_j(y), then K[y_1,...y_z]/<h_j> is finite over K[f_1..f_n]. |
---|
1020 | For a proof cf. Prop. 3.1.5, p. 214. in [G.-M. Greuel, G. Pfister: |
---|
1021 | A SINGULAR Introduction to Commutative Algebra, 2nd Edition, |
---|
1022 | Springer Verlag (2007)] |
---|
1023 | EXAMPLE: example finitenessTest; shows an example |
---|
1024 | " |
---|
1025 | { int n = nvars(basering); |
---|
1026 | intvec v,w; |
---|
1027 | int j,z,ii; |
---|
1028 | v[n]=0; //v should have size n |
---|
1029 | intvec V = 1..n; |
---|
1030 | list nze; //the non-zero entries of a leadexp |
---|
1031 | if (size(#) != 0 ) |
---|
1032 | { |
---|
1033 | V = #[1]; |
---|
1034 | } |
---|
1035 | intmat W[1][n]; //create intmat with 1 row, having 1 at |
---|
1036 | //position V[j], i = 1..size(V), 0 else |
---|
1037 | for( j=1; j<=size(V); j++ ) |
---|
1038 | { |
---|
1039 | W[1,V[j]] = 1; |
---|
1040 | } |
---|
1041 | ideal relation,zero,nonzero; |
---|
1042 | // ---------------------- check leading exponents ------------------------- |
---|
1043 | |
---|
1044 | for(j=1;j<=ncols(i);j++) |
---|
1045 | { |
---|
1046 | w = leadexp(i[j]); |
---|
1047 | nze = nonZeroEntry(w); |
---|
1048 | if( nze[1] == 1 ) //the leading term of i[j] is a |
---|
1049 | { //pure power of some variable |
---|
1050 | if( W*w != 0 ) //case: variable has index appearing in V |
---|
1051 | { |
---|
1052 | relation[size(relation)+1] = i[j]; |
---|
1053 | v=v+w; |
---|
1054 | } |
---|
1055 | } |
---|
1056 | } |
---|
1057 | // ----------------- pick the corresponding variables --------------------- |
---|
1058 | //the nonzero entries of v correspond to variables which occur as |
---|
1059 | //pure power in the leading term of some polynomial in i |
---|
1060 | |
---|
1061 | for(j=1; j<=size(v); j++) |
---|
1062 | { |
---|
1063 | if(v[j]==0) |
---|
1064 | { |
---|
1065 | zero[size(zero)+1]=var(j); |
---|
1066 | } |
---|
1067 | else |
---|
1068 | { |
---|
1069 | nonzero[size(nonzero)+1]=var(j); |
---|
1070 | } |
---|
1071 | } |
---|
1072 | // ---------------- do we have all pure powers we want? ------------------- |
---|
1073 | // test this by dividing the product of corresponding variables |
---|
1074 | ideal max = maxideal(1); |
---|
1075 | max = max[V]; |
---|
1076 | z = (product(nonzero)/product(max) != 0); |
---|
1077 | return(list(z,nonzero,zero,relation)); |
---|
1078 | } |
---|
1079 | example |
---|
1080 | { "EXAMPLE:"; echo = 2; |
---|
1081 | ring s = 0,(x,y,z,a,b,c),(lp(3),dp); |
---|
1082 | ideal i= a -(xy)^3+x2-z, b -y2-1, c -z3; |
---|
1083 | ideal j = a -(xy)^3+x2-z, b -y2-1, c -z3, xy; |
---|
1084 | finitenessTest(std(i),1..3); |
---|
1085 | finitenessTest(std(j),1..3); |
---|
1086 | } |
---|
1087 | /////////////////////////////////////////////////////////////////////////////// |
---|
1088 | |
---|
1089 | proc mapIsFinite(map phi,def R, list #) |
---|
1090 | "USAGE: mapIsFinite(phi,R[,J]); R the preimage ring of the map |
---|
1091 | phi: R ---> basering |
---|
1092 | J an ideal in the basering, J = 0 if not given |
---|
1093 | RETURN: 1 if R ---> basering/J is finite and 0 else |
---|
1094 | NOTE: R may be a quotient ring (this will be ignored since a map R/I-->S/J |
---|
1095 | is finite if and only if the induced map R-->S/J is finite). |
---|
1096 | SEE ALSO: finitenessTest |
---|
1097 | EXAMPLE: example mapIsFinite; shows an example |
---|
1098 | " |
---|
1099 | { |
---|
1100 | def bsr = basering; |
---|
1101 | ideal J; |
---|
1102 | if( size(#) != 0 ) |
---|
1103 | { |
---|
1104 | J = #[1]; |
---|
1105 | } |
---|
1106 | string os = ordstr(bsr); |
---|
1107 | int m = nvars(bsr); |
---|
1108 | int n = nvars(R); |
---|
1109 | ideal PHI = ideal(phi); |
---|
1110 | if ( ncols(PHI) < n ) |
---|
1111 | { PHI[n]=0; |
---|
1112 | } |
---|
1113 | // --------------------- change of variable names ------------------------- |
---|
1114 | list l2; |
---|
1115 | for (int ii = 1; ii <= m; ii++) |
---|
1116 | { |
---|
1117 | l2[ii] = "y("+string(ii)+")"; |
---|
1118 | } |
---|
1119 | ring @bsr = create_ring(ring_list(bsr)[1], l2, "("+os+")", "no_minpoly"); |
---|
1120 | ideal J = fetch(bsr,J); |
---|
1121 | ideal PHI = fetch(bsr,PHI); |
---|
1122 | |
---|
1123 | // --------------------------- enlarging ring ----------------------------- |
---|
1124 | list l12; |
---|
1125 | for (int yy = 1; yy <= m; yy++) |
---|
1126 | { |
---|
1127 | l12[size(l12)+1] = "y("+string(yy)+")"; |
---|
1128 | } |
---|
1129 | for (int zz = 1; zz <= n; zz++) |
---|
1130 | { |
---|
1131 | l12[size(l12)+1] = "x("+string(zz)+")"; |
---|
1132 | } |
---|
1133 | ring @rr = create_ring(ring_list(bsr)[1], l12, "(lp("+string(m)+"),dp)", "no_minpoly"); |
---|
1134 | ideal J = imap(@bsr,J); |
---|
1135 | ideal PHI = imap(@bsr,PHI); |
---|
1136 | ideal M; |
---|
1137 | int i; |
---|
1138 | |
---|
1139 | for(i=1;i<=n;i++) |
---|
1140 | { |
---|
1141 | M[i]=x(i)-PHI[i]; |
---|
1142 | } |
---|
1143 | M = std(M+J); |
---|
1144 | // ----------------------- test for finiteness --------------------------- |
---|
1145 | list l = finitenessTest(M,1..m); |
---|
1146 | int result = l[1]; |
---|
1147 | setring bsr; |
---|
1148 | return( result ); |
---|
1149 | } |
---|
1150 | example |
---|
1151 | { "EXAMPLE:"; echo = 2; |
---|
1152 | ring r = 0,(a,b,c),dp; |
---|
1153 | ring s = 0,(x,y,z),dp; |
---|
1154 | ideal i= xy; |
---|
1155 | map phi= r,(xy)^3+x2+z,y2-1,z3; |
---|
1156 | mapIsFinite(phi,r,i); |
---|
1157 | } |
---|
1158 | ////////////////////////////////////////////////////////////////////////////// |
---|
1159 | |
---|
1160 | proc nonZeroEntry(def id) |
---|
1161 | "USAGE: nonZeroEntry(id); id=object for which the test 'id[i]!=0', i=1,..,N, |
---|
1162 | N=size(id) (resp. ncols(id) for id of type ideal or module) |
---|
1163 | is defined (e.g. ideal, vector, list of polynomials, intvec,...) |
---|
1164 | RETURN: @format |
---|
1165 | a list, say l, with l[1] an integer, l[2], l[3] integer vectors: |
---|
1166 | - l[1] number of non-zero entries of id |
---|
1167 | - l[2] intvec of size l[1] with l[2][i]=i if id[i] != 0 |
---|
1168 | in case l[1]!=0 (and l[2]=0 if l[1]=0) |
---|
1169 | - l[3] intvec with l[3][i]=1 if id[i]!=0 and l[3][i]=0 else |
---|
1170 | @end format |
---|
1171 | NOTE: |
---|
1172 | EXAMPLE: example nonZeroEntry; shows an example |
---|
1173 | " |
---|
1174 | { |
---|
1175 | int ii,jj,N,n; |
---|
1176 | intvec v,V; |
---|
1177 | |
---|
1178 | if ( typeof(id) == "ideal" || typeof(id) == "module" ) |
---|
1179 | { |
---|
1180 | N = ncols(id); |
---|
1181 | } |
---|
1182 | else |
---|
1183 | { |
---|
1184 | N = size(id); |
---|
1185 | } |
---|
1186 | for ( ii=1; ii<=N; ii++ ) |
---|
1187 | { |
---|
1188 | V[ii] = 0; |
---|
1189 | if ( id[ii] != 0 ) |
---|
1190 | { |
---|
1191 | n++; |
---|
1192 | v=v,ii; //the first entry of v is always 0 |
---|
1193 | V[ii] = 1; |
---|
1194 | } |
---|
1195 | } |
---|
1196 | if ( size(v) > 1 ) //if id[ii] != 0 for at least one ii delete the first 0 |
---|
1197 | { |
---|
1198 | v = v[2..size(v)]; |
---|
1199 | } |
---|
1200 | |
---|
1201 | list l = n,v,V; |
---|
1202 | return(l); |
---|
1203 | } |
---|
1204 | example |
---|
1205 | { "EXAMPLE:"; echo = 2; |
---|
1206 | ring r = 0,(a,b,c),dp; |
---|
1207 | poly f = a3c+b3+c2+a; |
---|
1208 | intvec v = leadexp(f); |
---|
1209 | nonZeroEntry(v); |
---|
1210 | |
---|
1211 | intvec w; |
---|
1212 | list L = 37,0,f,v,w; |
---|
1213 | nonZeroEntry(L); |
---|
1214 | } |
---|
1215 | ////////////////////////////////////////////////////////////////////////////// |
---|
1216 | |
---|