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