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