[2e7410] | 1 | //////////////////////////////////////////////////////////////////////////////// |
---|
[b5f8c2] | 2 | version="$Id$"; |
---|
[7ef5b6] | 3 | category = "Commutative Algebra"; |
---|
| 4 | info=" |
---|
[602b552] | 5 | LIBRARY: primdecint.lib primary decomposition of an ideal in the polynomial |
---|
| 6 | ring over the integers |
---|
[7ef5b6] | 7 | |
---|
[d69ff5] | 8 | AUTHORS: G. Pfister pfister@mathematik.uni-kl.de |
---|
| 9 | @* A. Sadiq afshanatiq@gmail.com |
---|
| 10 | @* S. Steidel steidel@mathematik.uni-kl.de |
---|
[7ef5b6] | 11 | |
---|
[f9ca02] | 12 | OVERVIEW: |
---|
[7ef5b6] | 13 | |
---|
[ea87a9] | 14 | A library for computing the primary decomposition of an ideal in the |
---|
[d69ff5] | 15 | polynomial ring over the integers, Z[x_1,...,x_n]. |
---|
[602b552] | 16 | The first procedure 'primdecZ' can be used in parallel. |
---|
[7ef5b6] | 17 | |
---|
| 18 | PROCEDURES: |
---|
| 19 | primdecZ(I); compute the primary decomposition of I |
---|
| 20 | minAssZ(I); compute the minimal associated primes of I |
---|
| 21 | radicalZ(I); compute the radical of I |
---|
| 22 | heightZ(I); compute the height of I |
---|
| 23 | equidimZ(I); compute the equidimensional part of I |
---|
[049b78] | 24 | intersectZ(I,J) compute the intersection of I and J |
---|
[7ef5b6] | 25 | "; |
---|
| 26 | |
---|
[2ae57f] | 27 | LIB "primdec.lib"; |
---|
[7ef5b6] | 28 | |
---|
| 29 | //////////////////////////////////////////////////////////////////////////////// |
---|
| 30 | |
---|
| 31 | proc primdecZ(ideal I, list #) |
---|
[602b552] | 32 | "USAGE: primdecZ(I[, n]); I ideal, n integer (number of processors) |
---|
[7ef5b6] | 33 | NOTE: If size(#) > 0, then #[1] is the number of available processors for |
---|
[602b552] | 34 | the computation. |
---|
[7ef5b6] | 35 | RETURN: a list pr of primary ideals and their associated primes: |
---|
| 36 | @format |
---|
| 37 | pr[i][1] the i-th primary component, |
---|
| 38 | pr[i][2] the i-th prime component. |
---|
| 39 | @end format |
---|
| 40 | EXAMPLE: example primdecZ; shows an example |
---|
| 41 | " |
---|
| 42 | { |
---|
[2e7410] | 43 | if(size(I)==0){return(list(ideal(0),ideal(0)));} |
---|
[7ef5b6] | 44 | |
---|
[d69ff5] | 45 | //-------------------- Initialize optional parameters ------------------------ |
---|
[7ef5b6] | 46 | if(size(#) > 0) |
---|
| 47 | { |
---|
| 48 | if(size(#) == 1) |
---|
| 49 | { |
---|
| 50 | int n = #[1]; |
---|
| 51 | ideal TES = 1; |
---|
| 52 | } |
---|
| 53 | if(size(#) == 2) |
---|
| 54 | { |
---|
| 55 | int n = #[1]; |
---|
| 56 | ideal TES = #[2]; |
---|
| 57 | } |
---|
[2e7410] | 58 | } |
---|
[7ef5b6] | 59 | else |
---|
| 60 | { |
---|
| 61 | int n = 1; |
---|
| 62 | ideal TES = 1; |
---|
| 63 | } |
---|
| 64 | |
---|
| 65 | |
---|
[602b552] | 66 | if(deg(I[1]) == 0) |
---|
[7ef5b6] | 67 | { |
---|
[602b552] | 68 | ideal J = I; |
---|
[7ef5b6] | 69 | } |
---|
| 70 | else |
---|
| 71 | { |
---|
[602b552] | 72 | ideal J = stdZ(I); |
---|
[7ef5b6] | 73 | } |
---|
| 74 | |
---|
| 75 | ideal K,N; |
---|
| 76 | def R=basering; |
---|
| 77 | number s; |
---|
| 78 | list rl=ringlist(R); |
---|
| 79 | int i,j,p,m,ex,nu,k_link; |
---|
| 80 | list P,B,IS; |
---|
| 81 | ideal Q,JJ; |
---|
| 82 | ideal TQ=1; |
---|
| 83 | if(deg(J[1])==0) |
---|
| 84 | { |
---|
| 85 | //=== I intersected with Z is not zero |
---|
| 86 | list rp=rl; |
---|
| 87 | rp[1]=0; |
---|
| 88 | //=== q is generator of I intersect Z |
---|
| 89 | number q=leadcoef(J[1]); |
---|
| 90 | def Rhelp=ring(rp); |
---|
| 91 | setring Rhelp; |
---|
| 92 | number q=imap(R,q); |
---|
[2e7410] | 93 | //=== computes the primes occuring in a generator of I intersect Z |
---|
[7ef5b6] | 94 | |
---|
[2e7410] | 95 | list L = primefactors(q); |
---|
| 96 | |
---|
| 97 | list A; |
---|
| 98 | ideal J = imap(R,J); |
---|
| 99 | |
---|
[8acd267] | 100 | for(j=1;j<=size(L[2]);j++) |
---|
[7ef5b6] | 101 | { |
---|
[8acd267] | 102 | if(L[2][j] > 1){ ex = 1; break; } |
---|
[7ef5b6] | 103 | } |
---|
| 104 | |
---|
| 105 | if(printlevel >= 10) |
---|
| 106 | { |
---|
| 107 | "n = "+string(n); |
---|
[8acd267] | 108 | "size(L[2]) = "+string(size(L[2])); |
---|
[7ef5b6] | 109 | } |
---|
| 110 | |
---|
| 111 | int RT = rtimer; |
---|
[8acd267] | 112 | if((n > 1) && (n < size(L[2]))) |
---|
[7ef5b6] | 113 | { |
---|
| 114 | |
---|
| 115 | //----- Create n1 links l(1),...,l(n1), open all of them and compute --------- |
---|
[d69ff5] | 116 | //----- standard basis for the primes L[1][2],...,L[1][n + 1]. --------- |
---|
[7ef5b6] | 117 | |
---|
| 118 | for(i = 1; i <= n; i++) |
---|
| 119 | { |
---|
[8acd267] | 120 | p=int(L[1][i + 1]); |
---|
| 121 | nu=int(L[2][i + 1]); |
---|
[602b552] | 122 | //link l(i) = "MPtcp:fork"; |
---|
| 123 | link l(i) = "ssi:fork"; |
---|
[7ef5b6] | 124 | open(l(i)); |
---|
| 125 | write(l(i), quote(modp(eval(J), eval(p), eval(nu)))); |
---|
| 126 | } |
---|
| 127 | |
---|
[8acd267] | 128 | p = int(L[1][1]); |
---|
| 129 | nu = int(L[2][1]); |
---|
[7ef5b6] | 130 | int t = timer; |
---|
| 131 | A[size(A)+1] = modp(J, p, nu); |
---|
| 132 | t = timer - t; |
---|
| 133 | if(t > 60) { t = 60; } |
---|
| 134 | int i_sleep = system("sh", "sleep "+string(t)); |
---|
| 135 | |
---|
| 136 | j = n + 2; |
---|
| 137 | |
---|
[8acd267] | 138 | while(j <= size(L[2]) + 1) |
---|
[7ef5b6] | 139 | { |
---|
| 140 | for(i = 1; i <= n; i++) |
---|
| 141 | { |
---|
[ea87a9] | 142 | //=== ask if link l(i) is ready otherwise sleep for t seconds |
---|
| 143 | if(status(l(i), "read", "ready")) |
---|
[7ef5b6] | 144 | { |
---|
[ea87a9] | 145 | //=== read the result from l(i) |
---|
| 146 | A[size(A)+1] = read(l(i)); |
---|
[7ef5b6] | 147 | |
---|
[8acd267] | 148 | if(j <= size(L[2])) |
---|
[7ef5b6] | 149 | { |
---|
[8acd267] | 150 | p=int(L[1][j]); |
---|
| 151 | nu=int(L[2][j]); |
---|
[7ef5b6] | 152 | write(l(i), quote(modp(eval(J), eval(p), eval(nu)))); |
---|
| 153 | j++; |
---|
| 154 | } |
---|
| 155 | else |
---|
| 156 | { |
---|
| 157 | k_link++; |
---|
| 158 | close(l(i)); |
---|
| 159 | } |
---|
| 160 | } |
---|
| 161 | } |
---|
[f9ca02] | 162 | //=== k_link describes the number of closed links |
---|
[ea87a9] | 163 | if(k_link == n) |
---|
[7ef5b6] | 164 | { |
---|
| 165 | j++; |
---|
| 166 | } |
---|
| 167 | i_sleep = system("sh", "sleep "+string(t)); |
---|
| 168 | } |
---|
| 169 | |
---|
| 170 | } |
---|
| 171 | else |
---|
| 172 | { |
---|
[8acd267] | 173 | for(j=1;j<=size(L[2]);j++) |
---|
[7ef5b6] | 174 | { |
---|
[8acd267] | 175 | A[size(A)+1] = modp(J, L[1][j], L[2][j]); |
---|
[7ef5b6] | 176 | } |
---|
| 177 | } |
---|
| 178 | |
---|
| 179 | setring R; |
---|
| 180 | list A = imap(Rhelp,A); |
---|
| 181 | if(printlevel >= 10) |
---|
| 182 | { |
---|
| 183 | "A is computed in "+string(rtimer - RT)+" seconds."; |
---|
| 184 | } |
---|
| 185 | for(i=1;i<=size(A);i++) |
---|
| 186 | { |
---|
[ea87a9] | 187 | //=== computes for all p in L the minimal associated primes of |
---|
[d69ff5] | 188 | //=== IZ/p[variables] |
---|
[7ef5b6] | 189 | p = int(A[i][2]); |
---|
| 190 | if(printlevel >= 10) |
---|
| 191 | { |
---|
| 192 | "p = "+string(p); |
---|
| 193 | RT = rtimer; |
---|
| 194 | } |
---|
| 195 | nu = int(A[i][3]); |
---|
| 196 | //=== maximal power of p dividing q, generator of I intersect Z |
---|
| 197 | s = p^nu; |
---|
| 198 | |
---|
| 199 | rp[1] = p; |
---|
| 200 | def S = ring(rp); |
---|
| 201 | setring S; |
---|
| 202 | ideal J = imap(R,J); |
---|
| 203 | setring R; |
---|
| 204 | |
---|
| 205 | if(nu>1) |
---|
| 206 | { |
---|
| 207 | //=== p is of multiplicity > 1 in q |
---|
| 208 | |
---|
| 209 | B = A[i][1]; |
---|
| 210 | for(j=1;j<=size(B);j++) |
---|
| 211 | { |
---|
| 212 | //=== the minimal associated primes of I |
---|
| 213 | K=B[j],p; |
---|
| 214 | K=stdZ(K); |
---|
| 215 | B[j]=K; |
---|
| 216 | } |
---|
| 217 | for(j=1;j<=size(B);j++) |
---|
| 218 | { |
---|
| 219 | K=B[j]; |
---|
| 220 | //=== compute maximal independent set for KZ/p[variables] |
---|
| 221 | |
---|
| 222 | setring S; |
---|
| 223 | J=imap(R,K); |
---|
| 224 | J=simplify(J,2); |
---|
| 225 | attrib(J,"isSB",1); |
---|
| 226 | IS=maxIndependSet(J); |
---|
| 227 | setring R; |
---|
| 228 | //=== computing the pseudo primary and extract it |
---|
| 229 | N=J,s; |
---|
| 230 | N=stdZ(N); |
---|
| 231 | Q=extractZ(N,j,IS,B); |
---|
| 232 | //=== test for useless primaries |
---|
| 233 | if(size(reduce(TES,Q))>0) |
---|
| 234 | { |
---|
[049b78] | 235 | TQ=intersectZ(TQ,Q); |
---|
| 236 | //TQ=intersect(TQ,Q); |
---|
[7ef5b6] | 237 | P[size(P)+1]=list(Q,K); |
---|
| 238 | } |
---|
| 239 | } |
---|
| 240 | } |
---|
| 241 | else |
---|
| 242 | { |
---|
| 243 | //=== p is of multiplicity 1 in q we can compute the |
---|
| 244 | //=== primary decomposition directly |
---|
| 245 | |
---|
| 246 | B = A[i][1]; |
---|
| 247 | for(j=1;j<=size(B);j++) |
---|
| 248 | { |
---|
| 249 | K=B[j][2],p; |
---|
| 250 | K=stdZ(K); |
---|
| 251 | Q=B[j][1],p; |
---|
| 252 | Q=stdZ(Q); |
---|
| 253 | if(size(reduce(TES,Q))>0) |
---|
| 254 | { |
---|
[049b78] | 255 | //TQ=intersectZ(TQ,Q); |
---|
[7ef5b6] | 256 | P[size(P)+1]=list(Q,K); |
---|
| 257 | } |
---|
| 258 | } |
---|
| 259 | if(ex) |
---|
| 260 | { |
---|
| 261 | JJ=imap(S,J); |
---|
| 262 | JJ=JJ,p; |
---|
| 263 | JJ=stdZ(JJ); |
---|
[049b78] | 264 | TQ=intersectZ(TQ,JJ); |
---|
| 265 | //TQ=intersect(TQ,JJ); |
---|
[7ef5b6] | 266 | } |
---|
| 267 | } |
---|
| 268 | kill S; |
---|
| 269 | if(printlevel >= 10) |
---|
| 270 | { |
---|
| 271 | string(p)+" done in "+string(rtimer - RT)+" seconds."; |
---|
| 272 | } |
---|
| 273 | } |
---|
| 274 | |
---|
| 275 | setring R; |
---|
| 276 | if(!ex){return(P);} |
---|
| 277 | J=stdZ(J); |
---|
[049b78] | 278 | TQ=intersectZ(TQ,TES); |
---|
| 279 | //TQ=intersect(TQ,TES); |
---|
[7ef5b6] | 280 | if(size(reduce(TQ,J))!=0) |
---|
| 281 | { |
---|
| 282 | //=== taking care about embedded components |
---|
| 283 | K=stdZ(quotientZ(J,TQ)); |
---|
| 284 | ideal W=K; |
---|
| 285 | m++; |
---|
[049b78] | 286 | while(size(reduce(intersectZ(W,TQ),J))!=0) |
---|
| 287 | //while(size(reduce(intersect(W,TQ),J))!=0) |
---|
[7ef5b6] | 288 | { |
---|
| 289 | //W=stdZ(addIdealZ(I,K^m)); |
---|
| 290 | W=stdZ(addIdealZ(I,specialPowerZ(K,m))); |
---|
| 291 | m++; |
---|
| 292 | } |
---|
| 293 | list E=primdecZ(W,n,TQ); |
---|
| 294 | for(i=1;i<=size(E);i++) |
---|
| 295 | { |
---|
| 296 | P[size(P)+1]=E[i]; |
---|
| 297 | } |
---|
| 298 | } |
---|
| 299 | return(P); |
---|
| 300 | } |
---|
| 301 | |
---|
| 302 | //==== the ideal intersected with Z is zero |
---|
| 303 | rl[1]=0; |
---|
| 304 | def Rhelp=ring(rl); |
---|
| 305 | setring Rhelp; |
---|
| 306 | ideal J=imap(R,J); |
---|
| 307 | J=std(J); |
---|
[ea87a9] | 308 | //=== the primary decomposition over Q which gives the primary |
---|
[d69ff5] | 309 | //=== decomposition of I:h for a suitable integer h |
---|
[7ef5b6] | 310 | list pr=primdecGTZ(J); |
---|
| 311 | for(i=1;i<=size(pr);i++) |
---|
| 312 | { |
---|
| 313 | pr[i]=list(std(pr[i][1]),std(pr[i][2])); |
---|
| 314 | } |
---|
| 315 | setring R; |
---|
| 316 | list pr=imap(Rhelp,pr); |
---|
| 317 | //=== intersection with Z[variables] |
---|
| 318 | for(i=1;i<=size(pr);i++) |
---|
| 319 | { |
---|
| 320 | pr[i]=list(coefZ(pr[i][1])[1],coefZ(pr[i][2])[1]); |
---|
| 321 | } |
---|
| 322 | //=== find h in Z such that I is the intersection of I:h and <I,h> |
---|
| 323 | //=== and I:h = IQ[variables] intersected with Z[varables] |
---|
| 324 | list H =coefZ(J); |
---|
| 325 | ideal Y=H[1]; |
---|
| 326 | int h=H[2]; |
---|
| 327 | J=J,h; |
---|
| 328 | //=== call primary decomposition over Z for <I,h> |
---|
| 329 | list M; |
---|
| 330 | if(h!=1) |
---|
| 331 | { |
---|
| 332 | M=primdecZ(J,n,Y); |
---|
| 333 | j=0; |
---|
| 334 | //=== remove useless primary ideals |
---|
| 335 | while(j<size(M)) |
---|
| 336 | { |
---|
| 337 | j++; |
---|
| 338 | M[j][1]=stdZ(M[j][1]); |
---|
| 339 | for(i=1;i<=size(pr);i++) |
---|
| 340 | { |
---|
| 341 | if(size(reduce(pr[i][1],M[j][1]))==0) |
---|
| 342 | { |
---|
| 343 | M=delete(M,j); |
---|
| 344 | j--; |
---|
| 345 | break; |
---|
| 346 | } |
---|
| 347 | } |
---|
| 348 | } |
---|
| 349 | for(i=1;i<=size(M);i++) |
---|
| 350 | { |
---|
| 351 | pr[size(pr)+1]=M[i]; |
---|
| 352 | } |
---|
| 353 | } |
---|
| 354 | return(pr); |
---|
| 355 | } |
---|
| 356 | example |
---|
| 357 | { "EXAMPLE:"; echo = 2; |
---|
| 358 | ring R=integer,(a,b,c,d),dp; |
---|
| 359 | ideal I1=9,a,b; |
---|
| 360 | ideal I2=3,c; |
---|
| 361 | ideal I3=11,2a,7b; |
---|
| 362 | ideal I4=13a2,17b4; |
---|
| 363 | ideal I5=9c5,6d5; |
---|
| 364 | ideal I6=17,a15,b15,c15,d15; |
---|
[049b78] | 365 | ideal I=intersectZ(I1,I2); |
---|
| 366 | I=intersectZ(I,I3); |
---|
| 367 | I=intersectZ(I,I4); |
---|
| 368 | I=intersectZ(I,I5); |
---|
| 369 | I=intersectZ(I,I6); |
---|
[7ef5b6] | 370 | primdecZ(I); |
---|
[049b78] | 371 | ideal J=intersectZ(ideal(17,a),ideal(17,a2,b)); |
---|
[7ef5b6] | 372 | primdecZ(J); |
---|
[049b78] | 373 | ideal K=intersectZ(ideal(9,a+3),ideal(9,b+3)); |
---|
[7ef5b6] | 374 | primdecZ(K); |
---|
| 375 | } |
---|
| 376 | |
---|
[d69ff5] | 377 | //////////////////////////////////////////////////////////////////////////////// |
---|
[7ef5b6] | 378 | |
---|
| 379 | proc minAssZ(ideal I) |
---|
| 380 | "USAGE: minAssZ(I); I ideal |
---|
| 381 | RETURN: a list pr of associated primes: |
---|
| 382 | EXAMPLE: example minAssZ; shows an example |
---|
| 383 | " |
---|
| 384 | { |
---|
| 385 | if(size(I)==0){return(list(ideal(0)));} |
---|
| 386 | if(deg(I[1])==0) |
---|
| 387 | { |
---|
| 388 | ideal J=I; |
---|
| 389 | } |
---|
| 390 | else |
---|
| 391 | { |
---|
| 392 | ideal J=stdZ(I); |
---|
| 393 | } |
---|
| 394 | ideal K; |
---|
| 395 | def R=basering; |
---|
| 396 | list rl=ringlist(R); |
---|
| 397 | int i,j,p,m; |
---|
| 398 | list P,B; |
---|
| 399 | if(deg(J[1])==0) |
---|
| 400 | { |
---|
| 401 | //=== I intersected with Z is not zero |
---|
| 402 | list rp=rl; |
---|
| 403 | rp[1]=0; |
---|
| 404 | number q=leadcoef(J[1]); |
---|
| 405 | def Rhelp=ring(rp); |
---|
| 406 | setring Rhelp; |
---|
| 407 | number q=imap(R,q); |
---|
| 408 | //=== computes the primes occuring in a generator of I intersect Z |
---|
[2ae57f] | 409 | //list L=PollardRho(q,5000,1); |
---|
| 410 | list L=primefactors(q)[1]; |
---|
[7ef5b6] | 411 | for(i=1;i<=size(L);i++) |
---|
| 412 | { |
---|
[ea87a9] | 413 | //=== computes for all p in L the minimal associated primes of |
---|
[d69ff5] | 414 | //=== IZ/p[variables] |
---|
[7ef5b6] | 415 | p=int(L[i]); |
---|
| 416 | setring R; |
---|
| 417 | rp[1]=p; |
---|
| 418 | def S=ring(rp); |
---|
| 419 | setring S; |
---|
| 420 | ideal J=imap(R,J); |
---|
| 421 | list A=minAssGTZ(J); |
---|
| 422 | setring R; |
---|
| 423 | B=imap(S,A); |
---|
| 424 | kill S; |
---|
| 425 | for(j=1;j<=size(B);j++) |
---|
| 426 | { |
---|
| 427 | //=== the minimal associated primes of I |
---|
| 428 | if(B[j][1]!=1) |
---|
| 429 | { |
---|
| 430 | K=B[j],p; |
---|
| 431 | K=stdZ(K); |
---|
| 432 | P[size(P)+1]=K; |
---|
| 433 | } |
---|
| 434 | } |
---|
| 435 | setring Rhelp; |
---|
| 436 | } |
---|
| 437 | setring R; |
---|
| 438 | return(P); |
---|
| 439 | } |
---|
| 440 | //==== the ideal intersected with Z is zero |
---|
| 441 | rl[1]=0; |
---|
| 442 | def Rhelp=ring(rl); |
---|
| 443 | setring Rhelp; |
---|
| 444 | ideal J=imap(R,J); |
---|
| 445 | J=std(J); |
---|
[ea87a9] | 446 | //=== the primary decomposition over Q which gives the primary |
---|
[d69ff5] | 447 | //=== decomposition of I:h for a suitable integer h |
---|
[7ef5b6] | 448 | list pr=minAssGTZ(J); |
---|
| 449 | for(i=1;i<=size(pr);i++) |
---|
| 450 | { |
---|
| 451 | pr[i]=std(pr[i]); |
---|
| 452 | } |
---|
| 453 | setring R; |
---|
| 454 | list pr=imap(Rhelp,pr); |
---|
| 455 | //=== intersection with Z[variables] |
---|
| 456 | for(i=1;i<=size(pr);i++) |
---|
| 457 | { |
---|
| 458 | pr[i]=coefZ(pr[i])[1]; |
---|
| 459 | } |
---|
| 460 | //=== find h in Z such that I is the intersection of I:h and I,h |
---|
| 461 | //=== and I:h =IQ[variables] intersected with Z[varables] |
---|
| 462 | list H=coefZ(J); |
---|
| 463 | int h=H[2]; |
---|
| 464 | J=J,h; |
---|
| 465 | //=== call associated primes over Z for I,h |
---|
| 466 | list M; |
---|
| 467 | if(h!=1) |
---|
| 468 | { |
---|
| 469 | M=minAssZ(J); |
---|
| 470 | //=== remove non-minimal primes |
---|
| 471 | j=0; |
---|
| 472 | while(j<size(M)) |
---|
| 473 | { |
---|
| 474 | j++; |
---|
| 475 | M[j]=stdZ(M[j]); |
---|
| 476 | for(i=1;i<=size(pr);i++) |
---|
| 477 | { |
---|
| 478 | if(size(reduce(pr[i],M[j]))==0) |
---|
| 479 | { |
---|
| 480 | M=delete(M,j); |
---|
| 481 | j--; |
---|
| 482 | break; |
---|
| 483 | } |
---|
| 484 | } |
---|
| 485 | } |
---|
| 486 | for(i=1;i<=size(M);i++) |
---|
| 487 | { |
---|
| 488 | pr[size(pr)+1]=M[i]; |
---|
| 489 | } |
---|
| 490 | } |
---|
| 491 | return(pr); |
---|
| 492 | } |
---|
| 493 | example |
---|
| 494 | { "EXAMPLE:"; echo = 2; |
---|
| 495 | ring R=integer,(a,b,c,d),dp; |
---|
| 496 | ideal I1=9,a,b; |
---|
| 497 | ideal I2=3,c; |
---|
| 498 | ideal I3=11,2a,7b; |
---|
| 499 | ideal I4=13a2,17b4; |
---|
| 500 | ideal I5=9c5,6d5; |
---|
| 501 | ideal I6=17,a15,b15,c15,d15; |
---|
[049b78] | 502 | ideal I=intersectZ(I1,I2); |
---|
| 503 | I=intersectZ(I,I3); |
---|
| 504 | I=intersectZ(I,I4); |
---|
| 505 | I=intersectZ(I,I5); |
---|
| 506 | I=intersectZ(I,I6); |
---|
[7ef5b6] | 507 | minAssZ(I); |
---|
[049b78] | 508 | ideal J=intersectZ(ideal(17,a),ideal(17,a2,b)); |
---|
[7ef5b6] | 509 | minAssZ(J); |
---|
[049b78] | 510 | ideal K=intersectZ(ideal(9,a+3),ideal(9,b+3)); |
---|
[7ef5b6] | 511 | minAssZ(K); |
---|
| 512 | } |
---|
| 513 | |
---|
[d69ff5] | 514 | //////////////////////////////////////////////////////////////////////////////// |
---|
[7ef5b6] | 515 | |
---|
| 516 | proc heightZ(ideal I) |
---|
| 517 | "USAGE: heightZ(I); I ideal |
---|
| 518 | RETURN: the height of the input ideal |
---|
| 519 | EXAMPLE: example heightZ; shows an example |
---|
| 520 | " |
---|
| 521 | { |
---|
| 522 | if(size(I)==0){return(0);} |
---|
| 523 | if(deg(I[1])==0) |
---|
| 524 | { |
---|
| 525 | ideal J=I; |
---|
| 526 | } |
---|
| 527 | else |
---|
| 528 | { |
---|
| 529 | ideal J=stdZ(I); |
---|
| 530 | } |
---|
| 531 | ideal K=1; |
---|
| 532 | def R=basering; |
---|
| 533 | list rl=ringlist(R); |
---|
| 534 | int i,j,p,m; |
---|
| 535 | list P; |
---|
| 536 | ideal B; |
---|
| 537 | if(deg(J[1])==0) |
---|
| 538 | { |
---|
| 539 | //=== I intersected with Z is not zero |
---|
| 540 | m=nvars(R); |
---|
| 541 | list rp=rl; |
---|
| 542 | rp[1]=0; |
---|
| 543 | number q=leadcoef(J[1]); |
---|
| 544 | def Rhelp=ring(rp); |
---|
| 545 | setring Rhelp; |
---|
| 546 | number q=imap(R,q); |
---|
| 547 | //=== computes the primes occuring in a generator of I intersect Z |
---|
[2ae57f] | 548 | //list L=PollardRho(q,5000,1); |
---|
| 549 | list L=primefactors(q)[1]; |
---|
[7ef5b6] | 550 | for(i=1;i<=size(L);i++) |
---|
| 551 | { |
---|
| 552 | //=== computes for all p in L the std of IZ/p[variables] |
---|
| 553 | p=int(L[i]); |
---|
| 554 | setring R; |
---|
| 555 | rp[1]=p; |
---|
| 556 | def S=ring(rp); |
---|
| 557 | setring S; |
---|
| 558 | ideal J=imap(R,J); |
---|
| 559 | j=nvars(R)-dim(std(J)); |
---|
| 560 | if(j<m){m=j;} |
---|
| 561 | setring Rhelp; |
---|
| 562 | kill S; |
---|
| 563 | } |
---|
| 564 | setring R; |
---|
| 565 | return(m+1); |
---|
| 566 | } |
---|
| 567 | //==== the ideal intersected with Z is zero |
---|
| 568 | rl[1]=0; |
---|
| 569 | def Rhelp=ring(rl); |
---|
| 570 | setring Rhelp; |
---|
| 571 | ideal J=imap(R,J); |
---|
| 572 | J=std(J); |
---|
| 573 | m=nvars(R)-dim(J); |
---|
| 574 | //=== the height over Q |
---|
| 575 | //=== of I:h for a suitable integer h |
---|
| 576 | setring R; |
---|
| 577 | //=== find h in Z such that I is the intersection of I:h and I,h |
---|
| 578 | //=== and I:h =IQ[variables] intersected with Z[varables] |
---|
| 579 | list H=coefZ(J); |
---|
| 580 | int h=H[2]; |
---|
| 581 | J=J,h; |
---|
| 582 | //=== call height over Z for I,h |
---|
| 583 | if(h!=1) |
---|
| 584 | { |
---|
| 585 | j=heightZ(J); |
---|
| 586 | if(j<m){m=j;} |
---|
| 587 | } |
---|
| 588 | return(m); |
---|
| 589 | } |
---|
| 590 | example |
---|
| 591 | { "EXAMPLE:"; echo = 2; |
---|
| 592 | ring R=integer,(a,b,c,d),dp; |
---|
| 593 | ideal I1=9,a,b; |
---|
| 594 | ideal I2=3,c; |
---|
| 595 | ideal I3=11,2a,7b; |
---|
| 596 | ideal I4=13a2,17b4; |
---|
| 597 | ideal I5=9c5,6d5; |
---|
| 598 | ideal I6=17,a15,b15,c15,d15; |
---|
[049b78] | 599 | ideal I=intersectZ(I1,I2); |
---|
| 600 | I=intersectZ(I,I3); |
---|
| 601 | I=intersectZ(I,I4); |
---|
| 602 | I=intersectZ(I,I5); |
---|
| 603 | I=intersectZ(I,I6); |
---|
[7ef5b6] | 604 | heightZ(I); |
---|
| 605 | } |
---|
| 606 | |
---|
[d69ff5] | 607 | //////////////////////////////////////////////////////////////////////////////// |
---|
[7ef5b6] | 608 | |
---|
| 609 | proc radicalZ(ideal I) |
---|
| 610 | "USAGE: radicalZ(I); I ideal |
---|
| 611 | RETURN: the radcal of the input ideal |
---|
| 612 | EXAMPLE: example radicalZ; shows an example |
---|
| 613 | " |
---|
| 614 | { |
---|
| 615 | if(size(I)==0){return(ideal(0));} |
---|
| 616 | if(deg(I[1])==0) |
---|
| 617 | { |
---|
| 618 | ideal J=I; |
---|
| 619 | } |
---|
| 620 | else |
---|
| 621 | { |
---|
| 622 | ideal J=stdZ(I); |
---|
| 623 | } |
---|
| 624 | ideal K=1; |
---|
| 625 | def R=basering; |
---|
| 626 | list rl=ringlist(R); |
---|
| 627 | int i,j,p,m; |
---|
| 628 | list P; |
---|
| 629 | ideal B; |
---|
| 630 | if(deg(J[1])==0) |
---|
| 631 | { |
---|
| 632 | //=== I intersected with Z is not zero |
---|
| 633 | list rp=rl; |
---|
| 634 | rp[1]=0; |
---|
| 635 | number q=leadcoef(J[1]); |
---|
| 636 | def Rhelp=ring(rp); |
---|
| 637 | setring Rhelp; |
---|
| 638 | number q=imap(R,q); |
---|
| 639 | //=== computes the primes occuring in a generator of I intersect Z |
---|
[2ae57f] | 640 | //list L=PollardRho(q,5000,1); |
---|
| 641 | list L=primefactors(q)[1]; |
---|
[7ef5b6] | 642 | for(i=1;i<=size(L);i++) |
---|
| 643 | { |
---|
| 644 | //=== computes for all p in L the radical of IZ/p[variables] |
---|
| 645 | p=int(L[i]); |
---|
| 646 | setring R; |
---|
| 647 | rp[1]=p; |
---|
| 648 | def S=ring(rp); |
---|
| 649 | setring S; |
---|
| 650 | ideal J=imap(R,J); |
---|
| 651 | ideal A=radical(J); |
---|
| 652 | setring R; |
---|
| 653 | B=imap(S,A); |
---|
| 654 | kill S; |
---|
| 655 | B=B,p; |
---|
| 656 | B=stdZ(B); |
---|
[049b78] | 657 | K=stdZ(intersectZ(K,B)); |
---|
| 658 | //K=stdZ(intersect(K,B)); |
---|
[7ef5b6] | 659 | setring Rhelp; |
---|
[2e7410] | 660 | } |
---|
[7ef5b6] | 661 | setring R; |
---|
| 662 | return(K); |
---|
| 663 | } |
---|
| 664 | //==== the ideal intersected with Z is zero |
---|
| 665 | rl[1]=0; |
---|
| 666 | def Rhelp=ring(rl); |
---|
| 667 | setring Rhelp; |
---|
| 668 | ideal J=imap(R,J); |
---|
| 669 | J=std(J); |
---|
| 670 | //=== the radical over Q which gives the radical |
---|
| 671 | //=== of I:h for a suitable integer h |
---|
| 672 | ideal K=std(radical(J)); |
---|
| 673 | setring R; |
---|
| 674 | K=imap(Rhelp,K); |
---|
| 675 | //=== intersection with Z[variables] |
---|
| 676 | K=coefZ(K)[1]; |
---|
| 677 | //=== find h in Z such that I is the intersection of I:h and I,h |
---|
| 678 | //=== and I:h =IQ[variables] intersected with Z[varables] |
---|
| 679 | list H=coefZ(J); |
---|
| 680 | int h=H[2]; |
---|
| 681 | J=J,h; |
---|
| 682 | //=== call radical over Z for I,h |
---|
| 683 | if(h!=1) |
---|
| 684 | { |
---|
| 685 | ideal M=radicalZ(J); |
---|
[049b78] | 686 | K=intersectZ(K,M); |
---|
| 687 | //K=intersect(K,M); |
---|
[7ef5b6] | 688 | } |
---|
| 689 | return(K); |
---|
| 690 | } |
---|
| 691 | example |
---|
| 692 | { "EXAMPLE:"; echo = 2; |
---|
| 693 | ring R=integer,(a,b,c,d),dp; |
---|
| 694 | ideal I1=9,a,b; |
---|
| 695 | ideal I2=3,c; |
---|
| 696 | ideal I3=11,2a,7b; |
---|
| 697 | ideal I4=13a2,17b4; |
---|
| 698 | ideal I5=9c5,6d5; |
---|
| 699 | ideal I6=17,a15,b15,c15,d15; |
---|
[049b78] | 700 | ideal I=intersectZ(I1,I2); |
---|
| 701 | I=intersectZ(I,I3); |
---|
| 702 | I=intersectZ(I,I4); |
---|
| 703 | I=intersectZ(I,I5); |
---|
| 704 | I=intersectZ(I,I6); |
---|
[7ef5b6] | 705 | radicalZ(I); |
---|
[049b78] | 706 | ideal J=intersectZ(ideal(17,a),ideal(17,a2,b)); |
---|
[7ef5b6] | 707 | radicalZ(J); |
---|
| 708 | } |
---|
| 709 | |
---|
[d69ff5] | 710 | //////////////////////////////////////////////////////////////////////////////// |
---|
[7ef5b6] | 711 | |
---|
| 712 | proc equidimZ(ideal I) |
---|
| 713 | "USAGE: equidimZ(I); I ideal |
---|
| 714 | RETURN: the part of minimal height |
---|
| 715 | EXAMPLE: example equidimZ; shows an example |
---|
| 716 | " |
---|
| 717 | { |
---|
| 718 | if(size(I)==0){return(ideal(0));} |
---|
| 719 | if(deg(I[1])==0) |
---|
| 720 | { |
---|
| 721 | ideal J=I; |
---|
| 722 | } |
---|
| 723 | else |
---|
| 724 | { |
---|
| 725 | ideal J=stdZ(I); |
---|
| 726 | } |
---|
| 727 | int he=heightZ(J); |
---|
| 728 | ideal K,N; |
---|
| 729 | def R=basering; |
---|
| 730 | number s; |
---|
| 731 | list rl=ringlist(R); |
---|
| 732 | int i,j,p,m,ex; |
---|
| 733 | list P,IS,B; |
---|
| 734 | ideal Q,JJ,E; |
---|
| 735 | ideal TQ=1; |
---|
| 736 | if(deg(J[1])==0) |
---|
| 737 | { |
---|
| 738 | //=== I intersected with Z is not zero |
---|
| 739 | list rp=rl; |
---|
| 740 | rp[1]=0; |
---|
| 741 | //=== generator of I intersect Z |
---|
| 742 | number q=leadcoef(J[1]); |
---|
| 743 | def Rhelp=ring(rp); |
---|
| 744 | setring Rhelp; |
---|
| 745 | number q=imap(R,q); |
---|
| 746 | number s; |
---|
| 747 | //=== computes the primes occuring in a generator of I intersect Z |
---|
[2ae57f] | 748 | //list L=PollardRho(q,5000,1); |
---|
| 749 | list L=primefactors(q)[1]; |
---|
[7ef5b6] | 750 | list Le; |
---|
| 751 | for(i=1;i<=size(L);i++) |
---|
| 752 | { |
---|
| 753 | L[i]=int(L[i]); |
---|
| 754 | p=int(L[i]); |
---|
| 755 | j=0; |
---|
| 756 | s=q; |
---|
| 757 | while((s mod p)==0) |
---|
| 758 | { |
---|
| 759 | j++; |
---|
| 760 | s=s/p; |
---|
| 761 | } |
---|
| 762 | Le[i]=j; |
---|
| 763 | } |
---|
| 764 | for(i=1;i<=size(L);i++) |
---|
| 765 | { |
---|
[ea87a9] | 766 | //=== computes for all p in L the minimal associated primes of |
---|
[d69ff5] | 767 | //=== IZ/p[variables] |
---|
[7ef5b6] | 768 | p=int(L[i]); |
---|
| 769 | j=Le[i]; |
---|
| 770 | setring R; |
---|
| 771 | //=== maximal power of p dividing q, generator of I intersect Z |
---|
| 772 | s=p^j; |
---|
| 773 | rp[1]=p; |
---|
| 774 | def S=ring(rp); |
---|
| 775 | setring S; |
---|
| 776 | ideal J=imap(R,J); |
---|
| 777 | J=std(J); |
---|
| 778 | if(nvars(R)-dim(J)+1==he) |
---|
| 779 | { |
---|
| 780 | if(j>1) |
---|
| 781 | { |
---|
| 782 | //=== p is of multiplicity >1 in q |
---|
| 783 | list A=minAssGTZ(J); |
---|
| 784 | j=0; |
---|
| 785 | while(j<size(A)) |
---|
| 786 | { |
---|
| 787 | j++; |
---|
| 788 | if(dim(std(A[j]))!=nvars(R)-he+1) |
---|
| 789 | { |
---|
| 790 | A=delete(A,j); |
---|
| 791 | j--; |
---|
| 792 | } |
---|
| 793 | } |
---|
| 794 | setring R; |
---|
| 795 | B=imap(S,A); |
---|
| 796 | for(j=1;j<=size(B);j++) |
---|
| 797 | { |
---|
| 798 | //=== the minimal associated primes of I |
---|
| 799 | K=B[j],p; |
---|
| 800 | K=stdZ(K); |
---|
| 801 | B[j]=K; |
---|
| 802 | } |
---|
| 803 | for(j=1;j<=size(B);j++) |
---|
| 804 | { |
---|
| 805 | K=B[j]; |
---|
| 806 | //=== compute maximal independent set for KZ/p[variables] |
---|
| 807 | setring S; |
---|
| 808 | J=imap(R,K); |
---|
| 809 | J=simplify(J,2); |
---|
| 810 | attrib(J,"isSB",1); |
---|
| 811 | IS=maxIndependSet(J); |
---|
| 812 | setring R; |
---|
| 813 | //=== computing the pseudo primary and extract it |
---|
| 814 | N=J,s; |
---|
| 815 | N=stdZ(N); |
---|
| 816 | Q=extractZ(N,j,IS,B); |
---|
[049b78] | 817 | TQ=intersectZ(TQ,Q); |
---|
| 818 | //TQ=intersect(TQ,Q); |
---|
[7ef5b6] | 819 | } |
---|
| 820 | setring Rhelp; |
---|
| 821 | } |
---|
| 822 | else |
---|
| 823 | { |
---|
| 824 | //=== p is of multiplicity 1 in q we can compute the |
---|
| 825 | //=== equidimensional part directly |
---|
| 826 | ideal E=equidimMax(J); |
---|
| 827 | setring R; |
---|
| 828 | E=imap(S,E); |
---|
| 829 | E=E,p; |
---|
| 830 | E=stdZ(E); |
---|
[049b78] | 831 | TQ=intersectZ(TQ,E); |
---|
| 832 | //TQ=intersect(TQ,E); |
---|
[7ef5b6] | 833 | } |
---|
| 834 | } |
---|
[e6651bb] | 835 | kill S; |
---|
| 836 | setring Rhelp; |
---|
[7ef5b6] | 837 | } |
---|
| 838 | setring R; |
---|
| 839 | return(TQ); |
---|
| 840 | } |
---|
| 841 | //==== the ideal intersected with Z is zero |
---|
| 842 | rl[1]=0; |
---|
| 843 | def Rhelp=ring(rl); |
---|
| 844 | setring Rhelp; |
---|
| 845 | ideal J=imap(R,J); |
---|
| 846 | J=std(J); |
---|
[ea87a9] | 847 | //=== the equidimensional part over Q which gives the equdimensional |
---|
[d69ff5] | 848 | //=== part of I:h for a suitable integer h |
---|
[7ef5b6] | 849 | ideal E=1; |
---|
| 850 | if(nvars(R)-he==dim(J)) |
---|
| 851 | { |
---|
| 852 | E=std(equidimMax(J)); |
---|
| 853 | } |
---|
| 854 | setring R; |
---|
[e6651bb] | 855 | E =imap(Rhelp,E); |
---|
[7ef5b6] | 856 | //=== intersection with Z[variables] |
---|
| 857 | E=coefZ(E)[1]; |
---|
| 858 | //=== find h in Z such that I is the intersection of I:h and I,h |
---|
| 859 | //=== and I:h =IQ[variables] intersected with Z[varables] |
---|
| 860 | int h =coefZ(J)[2]; |
---|
| 861 | J=J,h; |
---|
| 862 | //=== call equidimensional part over Z for I,h |
---|
| 863 | ideal M; |
---|
| 864 | if(h!=1) |
---|
| 865 | { |
---|
| 866 | M=equidimZ(J); |
---|
| 867 | if(he==heightZ(M)) |
---|
| 868 | { |
---|
[049b78] | 869 | E=intersectZ(M,E); |
---|
| 870 | //E=intersect(M,E); |
---|
[7ef5b6] | 871 | } |
---|
| 872 | } |
---|
| 873 | return(E); |
---|
| 874 | } |
---|
| 875 | example |
---|
| 876 | { "EXAMPLE:"; echo = 2; |
---|
| 877 | ring R=integer,(a,b,c,d),dp; |
---|
| 878 | ideal I1=9,a,b; |
---|
| 879 | ideal I2=3,c; |
---|
| 880 | ideal I3=11,2a,7b; |
---|
| 881 | ideal I4=13a2,17b4; |
---|
| 882 | ideal I5=9c5,6d5; |
---|
| 883 | ideal I6=17,a15,b15,c15,d15; |
---|
[049b78] | 884 | ideal I=intersectZ(I1,I2); |
---|
| 885 | I=intersectZ(I,I3); |
---|
| 886 | I=intersectZ(I,I4); |
---|
| 887 | I=intersectZ(I,I5); |
---|
| 888 | I=intersectZ(I,I6); |
---|
[7ef5b6] | 889 | equidimZ(I); |
---|
| 890 | } |
---|
| 891 | |
---|
[d69ff5] | 892 | //////////////////////////////////////////////////////////////////////////////// |
---|
| 893 | |
---|
[049b78] | 894 | proc intersectZ(ideal I, ideal J) |
---|
| 895 | "USAGE: intersectZ(I,J); I,J ideals |
---|
| 896 | RETURN: the intersection of the input ideals |
---|
| 897 | NOTE: this is needed because intersect(I,J) does not work, should be replaced |
---|
| 898 | by intersect later |
---|
| 899 | EXAMPLE: example intersectZ; shows an example |
---|
| 900 | { |
---|
| 901 | def R = basering; |
---|
| 902 | execute("ring S=integer,(t,"+varstr(R)+"),(dp(1),dp(nvars(R)));"); |
---|
| 903 | ideal I=imap(R,I); |
---|
| 904 | ideal J=imap(R,J); |
---|
| 905 | ideal K=addIdealZ(t*I,(1-t)*J); |
---|
| 906 | K=stdZ(K); |
---|
| 907 | int i; |
---|
| 908 | ideal L; |
---|
| 909 | for(i=1;i<=size(K);i++) |
---|
| 910 | { |
---|
| 911 | if(lead(K[i])/t==0){L[size(L)+1]=K[i];} |
---|
| 912 | } |
---|
| 913 | setring R; |
---|
| 914 | ideal L=imap(S,L); |
---|
| 915 | return(L); |
---|
| 916 | } |
---|
| 917 | example |
---|
| 918 | { "EXAMPLE:"; echo = 2; |
---|
| 919 | ring R=integer,(a,b,c,d),dp; |
---|
| 920 | ideal I1=9,a,b; |
---|
| 921 | ideal I2=3,c; |
---|
| 922 | ideal I3=11,2a,7b; |
---|
| 923 | ideal I4=13a2,17b4; |
---|
| 924 | ideal I5=9c5,6d5; |
---|
| 925 | ideal I6=17,a15,b15,c15,d15; |
---|
| 926 | ideal I=intersectZ(I1,I2); I; |
---|
| 927 | I=intersectZ(I,I3); I; |
---|
| 928 | I=intersectZ(I,I4); I; |
---|
| 929 | I=intersectZ(I,I5); I; |
---|
| 930 | I=intersectZ(I,I6); I; |
---|
| 931 | } |
---|
| 932 | |
---|
| 933 | //////////////////////////////////////////////////////////////////////////////// |
---|
| 934 | |
---|
[2e7410] | 935 | static proc modp(ideal J, int p, int nu) |
---|
| 936 | { |
---|
[ea87a9] | 937 | //=== computes the minimal associated primes (if nu > 1) resp. the primary |
---|
[f9ca02] | 938 | //=== decomposition (else) of J in Z/p and maps the result back to the basering |
---|
[2e7410] | 939 | def R = basering; |
---|
[7ef5b6] | 940 | list rp = ringlist(R); |
---|
| 941 | rp[1] = p; |
---|
| 942 | def Rp = ring(rp); |
---|
| 943 | setring Rp; |
---|
| 944 | ideal J = imap(R,J); |
---|
| 945 | if(nu > 1) |
---|
| 946 | { |
---|
| 947 | //=== p is of multiplicity > 1 in q |
---|
| 948 | list A = minAssGTZ(J); |
---|
[2e7410] | 949 | setring R; |
---|
| 950 | list A = imap(Rp,A); |
---|
| 951 | return(list(A,p,nu)); |
---|
| 952 | } |
---|
| 953 | else |
---|
| 954 | { |
---|
| 955 | list A = primdecGTZ(J); |
---|
| 956 | setring R; |
---|
| 957 | list A = imap(Rp,A); |
---|
| 958 | return(list(A,p,nu)); |
---|
[7ef5b6] | 959 | } |
---|
| 960 | } |
---|
| 961 | |
---|
| 962 | //////////////////////////////////////////////////////////////////////////////// |
---|
| 963 | |
---|
| 964 | static proc coefPrimeZ(ideal I) |
---|
| 965 | { |
---|
[ea87a9] | 966 | //=== computes the primes occuring in the product of the leading coefficients |
---|
[d69ff5] | 967 | //=== of I |
---|
[7ef5b6] | 968 | number h=1; |
---|
| 969 | int i; |
---|
| 970 | for(i=1;i<=size(I);i++) |
---|
| 971 | { |
---|
[ea87a9] | 972 | h=h*leadcoef(I[i]); // besser machen (gleich zerlegen, |
---|
[d69ff5] | 973 | // nicht ausmultiplizieren) |
---|
[7ef5b6] | 974 | } |
---|
| 975 | def R=basering; |
---|
| 976 | ring Rhelp=0,x,dp; |
---|
| 977 | number h=imap(R,h); |
---|
[2ae57f] | 978 | //list L=PollardRho(h,5000,1); |
---|
| 979 | list L=primefactors(h)[1]; |
---|
[7ef5b6] | 980 | for(i=1;i<=size(L);i++){L[i]=int(L[i]);} |
---|
| 981 | setring R; |
---|
| 982 | return(L); |
---|
| 983 | } |
---|
| 984 | |
---|
[d69ff5] | 985 | //////////////////////////////////////////////////////////////////////////////// |
---|
[7ef5b6] | 986 | |
---|
| 987 | static proc coefZ(ideal I) |
---|
| 988 | { |
---|
[f9ca02] | 989 | //=== assume IQ[variables]=<g_1,...,g_s>, Groebner basis, g_i in Z[variables] |
---|
| 990 | //=== computes an integer h such that |
---|
[ea87a9] | 991 | //=== <g_1,...,g_s>Z[variables]:h^infinity = IQ[variables] intersected |
---|
[d69ff5] | 992 | //=== with Z[variables] |
---|
[f9ca02] | 993 | //=== returns a list with IQ[variables] intersected with Z[variables] and h |
---|
[7ef5b6] | 994 | int h=1; |
---|
| 995 | int i,e; |
---|
| 996 | ideal K=1; |
---|
[687272a] | 997 | attrib(I,"isSB",1); |
---|
[7ef5b6] | 998 | list L=coefPrimeZ(I); |
---|
| 999 | if(size(L)==0){return(list(I,1));} |
---|
| 1000 | int d=1; |
---|
| 1001 | while(d!=0) |
---|
| 1002 | { |
---|
| 1003 | i++; |
---|
| 1004 | K=quotientOneZ(I,L[i]); |
---|
| 1005 | if(size(reduce(K,I))!=0) |
---|
| 1006 | { |
---|
| 1007 | h=h*L[i]; |
---|
| 1008 | I=stdZ(K); |
---|
| 1009 | e=1; |
---|
| 1010 | } |
---|
| 1011 | if(i==size(L)) |
---|
| 1012 | { |
---|
| 1013 | i=0; |
---|
| 1014 | if(e) |
---|
| 1015 | { |
---|
| 1016 | e=0; |
---|
| 1017 | } |
---|
| 1018 | else |
---|
| 1019 | { |
---|
| 1020 | d=0; |
---|
| 1021 | } |
---|
| 1022 | } |
---|
| 1023 | } |
---|
| 1024 | if(h<0){h=-h;} |
---|
| 1025 | return(list(K,h)); |
---|
| 1026 | } |
---|
| 1027 | |
---|
[d69ff5] | 1028 | //////////////////////////////////////////////////////////////////////////////// |
---|
[7ef5b6] | 1029 | |
---|
| 1030 | static proc specialPowerZ(ideal I, int m) |
---|
| 1031 | { |
---|
| 1032 | //=== computes the ideal generated by the m-th power of the generators of I |
---|
| 1033 | int i; |
---|
| 1034 | for(i=1;i<=size(I);i++) |
---|
| 1035 | { |
---|
| 1036 | I[i]=I[i]^m; |
---|
| 1037 | } |
---|
| 1038 | return(I); |
---|
| 1039 | } |
---|
| 1040 | |
---|
[d69ff5] | 1041 | //////////////////////////////////////////////////////////////////////////////// |
---|
[7ef5b6] | 1042 | |
---|
| 1043 | static proc separatorsZ(int j, list B) |
---|
| 1044 | { |
---|
| 1045 | //=== computes s such that s is not in B[j] but s is in B[i] for all i!=j |
---|
| 1046 | int i,k; |
---|
| 1047 | poly s=1; |
---|
| 1048 | for(i=1;i<=size(B);i++) |
---|
| 1049 | { |
---|
| 1050 | if(i!=j) |
---|
| 1051 | { |
---|
| 1052 | for(k=1;k<=size(B[i]);k++) |
---|
| 1053 | { |
---|
| 1054 | if(reduce(B[i][k],B[j])!=0) |
---|
| 1055 | { |
---|
| 1056 | s=s*B[i][k]; |
---|
| 1057 | break; |
---|
| 1058 | } |
---|
| 1059 | } |
---|
| 1060 | } |
---|
| 1061 | } |
---|
| 1062 | return(s); |
---|
| 1063 | } |
---|
| 1064 | |
---|
[d69ff5] | 1065 | //////////////////////////////////////////////////////////////////////////////// |
---|
[7ef5b6] | 1066 | |
---|
| 1067 | static proc extractZ(ideal J, int j, list L, list B) |
---|
| 1068 | { |
---|
[ea87a9] | 1069 | //=== P is an associated prime of J, the corresponding primary ideal is |
---|
[d69ff5] | 1070 | //=== computed, |
---|
[7ef5b6] | 1071 | //=== L is a list of maximal independent sets for P in Z/p[variables] |
---|
| 1072 | def R=basering; |
---|
| 1073 | ideal P=B[j]; |
---|
| 1074 | |
---|
| 1075 | //=== first compute a pseudo primary ideal I, radical of I is P |
---|
| 1076 | //=== method of Eisenbud |
---|
| 1077 | //ideal I=addIdealZ(J,specialPowerZ(P,20)); |
---|
| 1078 | |
---|
| 1079 | //=== method of Shimoyama-Yokoyama |
---|
| 1080 | poly s=separatorsZ(j,B); |
---|
| 1081 | ideal I=satZ(J,s); |
---|
| 1082 | //=== size(L)=0 means P is maximal ideal and I is primary |
---|
| 1083 | if(size(L)>0) |
---|
| 1084 | { |
---|
| 1085 | if(L[1][3]!=0) |
---|
| 1086 | { |
---|
[d69ff5] | 1087 | //=== if u in x is an independent set of L then we compute a Groebner |
---|
| 1088 | //=== Basis in Z[u][x-u] |
---|
[7ef5b6] | 1089 | execute("ring S=integer,("+L[1][1]+"),lp;"); |
---|
| 1090 | ideal I=imap(R,I); |
---|
| 1091 | I=stdZ(I); |
---|
| 1092 | list rl=ringlist(S); |
---|
| 1093 | rl[1]=0; |
---|
| 1094 | def Shelp =ring(rl); |
---|
| 1095 | setring Shelp; |
---|
| 1096 | ideal I=imap(S,I); |
---|
| 1097 | I[1]=0; |
---|
| 1098 | I=simplify(I,2); |
---|
| 1099 | //=== this is our way to obtain the coefficients in Z[u] of the |
---|
| 1100 | //=== leading terms of the Groebner basis above |
---|
| 1101 | string quotring=prepareQuotientring(nvars(basering)-L[1][3]); |
---|
| 1102 | execute(quotring); |
---|
| 1103 | ideal I=imap(Shelp,I); |
---|
| 1104 | list C; |
---|
| 1105 | int i; |
---|
| 1106 | for(i=1;i<=size(I);i++) |
---|
| 1107 | { |
---|
| 1108 | C[i]=leadcoef(I[i]); |
---|
| 1109 | } |
---|
| 1110 | setring Shelp; |
---|
| 1111 | list C=imap(quring,C); |
---|
| 1112 | |
---|
| 1113 | setring R; |
---|
| 1114 | list C=imap(Shelp,C); |
---|
| 1115 | } |
---|
| 1116 | else |
---|
| 1117 | { |
---|
| 1118 | I=stdZ(I); |
---|
| 1119 | list C; |
---|
| 1120 | int i; |
---|
| 1121 | for(i=1;i<=size(I);i++) |
---|
| 1122 | { |
---|
| 1123 | C[i]=I[i]; |
---|
| 1124 | } |
---|
| 1125 | list rl=ringlist(R); |
---|
| 1126 | rl[1]=0; |
---|
| 1127 | def Shelp =ring(rl); |
---|
| 1128 | } |
---|
| 1129 | poly h=1; |
---|
| 1130 | for(i=1;i<=size(C);i++) |
---|
| 1131 | { |
---|
[d69ff5] | 1132 | if(deg(C[i])>0){h=h*C[i];} // das muss noch besser gemacht werden, |
---|
| 1133 | // nicht ausmultiplizieren! |
---|
[7ef5b6] | 1134 | } |
---|
| 1135 | setring Shelp; |
---|
| 1136 | poly h=imap(R,h); |
---|
| 1137 | ideal fac=factorize(h,1); |
---|
| 1138 | setring R; |
---|
| 1139 | ideal fac=imap(Shelp,fac); |
---|
| 1140 | for(i=1;i<=size(fac);i++) |
---|
| 1141 | { |
---|
| 1142 | I=satZ(I,fac[i]); |
---|
| 1143 | } |
---|
| 1144 | } |
---|
| 1145 | I=stdZ(I); |
---|
| 1146 | return(I); |
---|
| 1147 | } |
---|
[d69ff5] | 1148 | //////////////////////////////////////////////////////////////////////////////// |
---|
[7ef5b6] | 1149 | |
---|
| 1150 | static proc normalizeZ(ideal I) |
---|
| 1151 | { |
---|
[ea87a9] | 1152 | //=== if I[1]=q in Z, it replaces all other coeffs of polys in I by there value |
---|
[d69ff5] | 1153 | //=== mod q, std should do this automatically and then this procedure should be |
---|
| 1154 | //=== removed |
---|
[7ef5b6] | 1155 | if(deg(I[1])>0){return(I);} |
---|
| 1156 | int i,j; |
---|
| 1157 | number n; |
---|
| 1158 | poly p; |
---|
| 1159 | for(i=2;i<=size(I);i++) |
---|
| 1160 | { |
---|
| 1161 | j=1; |
---|
| 1162 | while(j<=size(I[i])) |
---|
| 1163 | { |
---|
| 1164 | n=leadcoef(I[i][j]) mod leadcoef(I[1]); |
---|
| 1165 | p=n*leadmonom(I[i][j]); |
---|
| 1166 | I[i]=I[i]-I[i][j]+p; |
---|
| 1167 | if(p!=0){j++;} |
---|
| 1168 | } |
---|
| 1169 | } |
---|
| 1170 | return(I); |
---|
| 1171 | } |
---|
| 1172 | |
---|
[d69ff5] | 1173 | //////////////////////////////////////////////////////////////////////////////// |
---|
[7ef5b6] | 1174 | |
---|
| 1175 | static proc satZ(ideal I,poly h) |
---|
| 1176 | { |
---|
| 1177 | //=== saturates I by h |
---|
| 1178 | ideal J=quotientOneZ(I,h); |
---|
| 1179 | while(size(reduce(J,stdZ(I)))!=0) |
---|
| 1180 | { |
---|
[f9ca02] | 1181 | I=J; |
---|
| 1182 | J=quotientOneZ(I,h); |
---|
| 1183 | J=normalizeZ(J); |
---|
[7ef5b6] | 1184 | } |
---|
| 1185 | return(J); |
---|
| 1186 | } |
---|
| 1187 | |
---|
[d69ff5] | 1188 | //////////////////////////////////////////////////////////////////////////////// |
---|
[7ef5b6] | 1189 | |
---|
| 1190 | static proc prepareQuotientring (int nnp) |
---|
| 1191 | { |
---|
[ea87a9] | 1192 | //=== this is from primdec.lib, it is static there, should be imported later |
---|
[f9ca02] | 1193 | //=== if it is no more static |
---|
[7ef5b6] | 1194 | ideal @ih,@jh; |
---|
| 1195 | int npar=npars(basering); |
---|
| 1196 | int @n; |
---|
| 1197 | |
---|
| 1198 | string quotring= "ring quring = ("+charstr(basering); |
---|
| 1199 | for(@n=nnp+1;@n<=nvars(basering);@n++) |
---|
| 1200 | { |
---|
| 1201 | quotring=quotring+",var("+string(@n)+")"; |
---|
| 1202 | @ih=@ih+var(@n); |
---|
| 1203 | } |
---|
| 1204 | |
---|
| 1205 | quotring=quotring+"),(var(1)"; |
---|
| 1206 | @jh=@jh+var(1); |
---|
| 1207 | for(@n=2;@n<=nnp;@n++) |
---|
| 1208 | { |
---|
[f9ca02] | 1209 | quotring=quotring+",var("+string(@n)+")"; |
---|
| 1210 | @jh=@jh+var(@n); |
---|
[7ef5b6] | 1211 | } |
---|
| 1212 | quotring=quotring+"),(C,lp);"; |
---|
| 1213 | |
---|
| 1214 | return(quotring); |
---|
| 1215 | } |
---|
| 1216 | |
---|
[d69ff5] | 1217 | //////////////////////////////////////////////////////////////////////////////// |
---|
[7ef5b6] | 1218 | |
---|
| 1219 | static proc maxIndependSet (ideal j) |
---|
| 1220 | { |
---|
[ea87a9] | 1221 | //=== this is from primdec.lib, it is static there, should be imported later |
---|
[f9ca02] | 1222 | //=== if it is no more static |
---|
[7ef5b6] | 1223 | int n,k,di; |
---|
| 1224 | |
---|
| 1225 | list resu,hilf; |
---|
| 1226 | if(size(j)==0) |
---|
| 1227 | { |
---|
| 1228 | resu[1]=varstr(basering); |
---|
| 1229 | resu[2]=ordstr(basering); |
---|
| 1230 | resu[3]=0; |
---|
| 1231 | return(list(resu)); |
---|
| 1232 | } |
---|
| 1233 | string var1,var2; |
---|
| 1234 | list v=indepSet(j,0); |
---|
| 1235 | |
---|
| 1236 | for(n=1;n<=size(v);n++) |
---|
| 1237 | { |
---|
| 1238 | di=0; |
---|
| 1239 | var1=""; |
---|
| 1240 | var2=""; |
---|
| 1241 | for(k=1;k<=size(v[n]);k++) |
---|
| 1242 | { |
---|
| 1243 | if(v[n][k]!=0) |
---|
| 1244 | { |
---|
| 1245 | di++; |
---|
| 1246 | var2=var2+"var("+string(k)+"),"; |
---|
| 1247 | } |
---|
| 1248 | else |
---|
| 1249 | { |
---|
| 1250 | var1=var1+"var("+string(k)+"),"; |
---|
| 1251 | } |
---|
| 1252 | } |
---|
| 1253 | if(di>0) |
---|
| 1254 | { |
---|
| 1255 | var1=var1+var2; |
---|
| 1256 | var1=var1[1..size(var1)-1]; |
---|
| 1257 | hilf[1]=var1; |
---|
| 1258 | hilf[2]="lp"; |
---|
| 1259 | hilf[3]=di; |
---|
| 1260 | resu[n]=hilf; |
---|
| 1261 | } |
---|
| 1262 | else |
---|
| 1263 | { |
---|
| 1264 | resu[n]=varstr(basering),ordstr(basering),0; |
---|
| 1265 | } |
---|
| 1266 | } |
---|
| 1267 | return(resu); |
---|
| 1268 | } |
---|
| 1269 | |
---|
[d69ff5] | 1270 | //////////////////////////////////////////////////////////////////////////////// |
---|
[7ef5b6] | 1271 | |
---|
| 1272 | static proc quotientOneZ(ideal I, poly f) |
---|
| 1273 | { |
---|
[ea87a9] | 1274 | //=== this is needed because quotient(I,f) does not work properly, should be |
---|
[f9ca02] | 1275 | //=== replaced by quotient later |
---|
[7ef5b6] | 1276 | def R=basering; |
---|
| 1277 | int i; |
---|
[049b78] | 1278 | ideal K=intersectZ(I,ideal(f)); |
---|
| 1279 | //ideal K=intersect(I,ideal(f)); |
---|
[ea87a9] | 1280 | //=== K[i]/f; does not work in rings with integer! This should be replaced |
---|
[d69ff5] | 1281 | //=== later |
---|
[7ef5b6] | 1282 | execute("ring Rhelp=0,("+varstr(R)+"),dp;"); |
---|
| 1283 | ideal K=imap(R,K); |
---|
| 1284 | poly f=imap(R,f); |
---|
| 1285 | for(i=1;i<=size(K);i++) |
---|
| 1286 | { |
---|
| 1287 | K[i]=K[i]/f; |
---|
| 1288 | } |
---|
| 1289 | setring R; |
---|
| 1290 | K=imap(Rhelp,K); |
---|
| 1291 | return(K); |
---|
| 1292 | } |
---|
| 1293 | |
---|
[d69ff5] | 1294 | //////////////////////////////////////////////////////////////////////////////// |
---|
[7ef5b6] | 1295 | |
---|
| 1296 | static proc quotientZ(ideal I, ideal J) |
---|
| 1297 | { |
---|
[ea87a9] | 1298 | //=== this is needed because quotient(I,J) does not work properly, should be |
---|
[f9ca02] | 1299 | //=== replaced by quotient later |
---|
[7ef5b6] | 1300 | int i; |
---|
| 1301 | ideal K=quotientOneZ(I,J[1]); |
---|
| 1302 | for(i=2;i<=size(J);i++) |
---|
| 1303 | { |
---|
[049b78] | 1304 | K=intersectZ(K,quotientOneZ(I,J[i])); |
---|
| 1305 | //K=intersect(K,quotientOneZ(I,J[i])); |
---|
[7ef5b6] | 1306 | } |
---|
| 1307 | return(K); |
---|
| 1308 | } |
---|
| 1309 | |
---|
[d69ff5] | 1310 | //////////////////////////////////////////////////////////////////////////////// |
---|
[7ef5b6] | 1311 | |
---|
| 1312 | static proc reduceZ(poly f, ideal I) |
---|
| 1313 | { |
---|
[ea87a9] | 1314 | //=== this is needed because reduce(f,I) does not work properly, should be |
---|
[f9ca02] | 1315 | //=== replaced by reduce later |
---|
[7ef5b6] | 1316 | if(f==0){return(f);} |
---|
| 1317 | def R=basering; |
---|
| 1318 | execute("ring Rhelp=0,("+varstr(R)+"),dp;"); |
---|
| 1319 | ideal I=imap(R,I); |
---|
| 1320 | poly f=imap(R,f); |
---|
| 1321 | int i,j; |
---|
| 1322 | poly m; |
---|
| 1323 | number n; |
---|
| 1324 | while(!i) |
---|
| 1325 | { |
---|
| 1326 | i=1; |
---|
| 1327 | j=0; |
---|
| 1328 | while(j<size(I)) |
---|
| 1329 | { |
---|
| 1330 | j++; |
---|
| 1331 | m=leadmonom(f)/leadmonom(I[j]); |
---|
| 1332 | if(m!=0) |
---|
| 1333 | { |
---|
[f9ca02] | 1334 | n=leadcoef(f) mod leadcoef(I[j]); |
---|
| 1335 | if(n==0) |
---|
| 1336 | { |
---|
| 1337 | f=f-leadcoef(f)/leadcoef(I[j])*m*I[j]; |
---|
| 1338 | if(f==0){setring R;return(0);} |
---|
| 1339 | i=0; |
---|
| 1340 | break; |
---|
| 1341 | } |
---|
| 1342 | if(n!=leadcoef(f)) |
---|
| 1343 | { |
---|
| 1344 | f=f+(n-leadcoef(f))/leadcoef(I[j])*m*I[j]; |
---|
| 1345 | i=0; |
---|
| 1346 | break; |
---|
| 1347 | } |
---|
| 1348 | } |
---|
[7ef5b6] | 1349 | } |
---|
| 1350 | } |
---|
| 1351 | setring R; |
---|
| 1352 | f=imap(Rhelp,f); |
---|
| 1353 | return(lead(f)+reduceZ(f-lead(f),I)); |
---|
| 1354 | } |
---|
| 1355 | |
---|
[d69ff5] | 1356 | //////////////////////////////////////////////////////////////////////////////// |
---|
[7ef5b6] | 1357 | |
---|
| 1358 | static proc stdZ(ideal I) |
---|
| 1359 | { |
---|
| 1360 | //=== this is needed because we want the leading coefficients to be positive |
---|
[f9ca02] | 1361 | //=== otherwhise reduce gives wrong results! should be replaced later by std |
---|
[7ef5b6] | 1362 | I=simplify(I,2); |
---|
| 1363 | I=normalizeZ(I); |
---|
| 1364 | ideal J=std(I); |
---|
| 1365 | int i; |
---|
| 1366 | for(i=1;i<=size(J);i++) |
---|
| 1367 | { |
---|
| 1368 | if(leadcoef(J[i])<0){J[i]=-J[i];} |
---|
| 1369 | } |
---|
| 1370 | J=normalizeZ(J); |
---|
| 1371 | attrib(J,"isSB",1); |
---|
| 1372 | return(J); |
---|
| 1373 | } |
---|
| 1374 | |
---|
[d69ff5] | 1375 | //////////////////////////////////////////////////////////////////////////////// |
---|
[7ef5b6] | 1376 | |
---|
| 1377 | static proc addIdealZ(ideal I,ideal J) |
---|
| 1378 | { |
---|
| 1379 | //=== this is needed because I+J does not work, should be replaced by + later |
---|
| 1380 | int i; |
---|
| 1381 | for(i=1;i<=size(J);i++) |
---|
| 1382 | { |
---|
| 1383 | I[size(I)+1]=J[i]; |
---|
| 1384 | } |
---|
| 1385 | return(I); |
---|
| 1386 | } |
---|
| 1387 | |
---|
[d69ff5] | 1388 | //////////////////////////////////////////////////////////////////////////////// |
---|
[7ef5b6] | 1389 | |
---|
| 1390 | static proc testPrimaryZ(ideal I, list L) |
---|
| 1391 | { |
---|
| 1392 | //=== test whether I is the intersection of the primary ideals in L |
---|
| 1393 | int i; |
---|
| 1394 | ideal K=L[1][1]; |
---|
| 1395 | for(i=2;i<=size(L);i++) |
---|
| 1396 | { |
---|
[049b78] | 1397 | K=intersectZ(K,L[i][1]); |
---|
| 1398 | //K=intersect(K,L[i][1]); |
---|
[7ef5b6] | 1399 | } |
---|
| 1400 | i=size(reduce(K,stdZ(I)))+size(reduce(I,stdZ(K))); |
---|
| 1401 | if(!i){return(1);} |
---|
| 1402 | return(0); |
---|
[2e7410] | 1403 | } |
---|
[7ef5b6] | 1404 | |
---|
[d69ff5] | 1405 | //////////////////////////////////////////////////////////////////////////////// |
---|
[7ef5b6] | 1406 | |
---|
| 1407 | /* |
---|
[f9ca02] | 1408 | Examples: |
---|
[7ef5b6] | 1409 | |
---|
| 1410 | //=== IQ[a,b,c,d,e,f,g] intersect Z[a,b,c,d,e,f,g] = I (takes some time) |
---|
| 1411 | ring R1=integer,(a,b,c,d,e,f,g),dp; |
---|
| 1412 | ideal I=a2+2de+2cf+2bg+a, |
---|
[602b552] | 1413 | 2ab+e2+2df+2cg+b, |
---|
| 1414 | b2+2ac+2ef+2dg+c, |
---|
| 1415 | 2bc+2ad+f2+2eg+d, |
---|
| 1416 | c2+2bd+2ae+2fg+e, |
---|
| 1417 | 2cd+2be+2af+g2+f, |
---|
| 1418 | d2+2ce+2bf+2ag+g; |
---|
[7ef5b6] | 1419 | |
---|
| 1420 | ring R2=integer,(a,b,c,d,e,f,g),dp; |
---|
| 1421 | ideal I=181*32003, |
---|
| 1422 | a2+2de+2cf+2bg+a, |
---|
[602b552] | 1423 | 2ab+e2+2df+2cg+b, |
---|
| 1424 | b2+2ac+2ef+2dg+c, |
---|
| 1425 | 2bc+2ad+f2+2eg+d, |
---|
| 1426 | c2+2bd+2ae+2fg+e, |
---|
| 1427 | 2cd+2be+2af+g2+f, |
---|
| 1428 | d2+2ce+2bf+2ag+g; |
---|
| 1429 | |
---|
[7ef5b6] | 1430 | ring R3=integer,(w,z,y,x),dp; |
---|
| 1431 | ideal I=xzw+(-y^2+y)*z^2, |
---|
[d69ff5] | 1432 | (-x^2+x)*w^2+yzw, |
---|
| 1433 | ((y^4-2*y^3+y^2)*x-y^4+y^3)*z^3, |
---|
| 1434 | y2z2w+(-y*4+2*y^3-y^2)*z3; |
---|
[7ef5b6] | 1435 | |
---|
| 1436 | ring R4=integer,(w,z,y,x),dp; |
---|
| 1437 | ideal I=-2*yxzw+(-yx-y^2+y)*z^2, |
---|
[d69ff5] | 1438 | xw^2-yz^2, |
---|
| 1439 | (yx^2-(2*y^2+2*y)*x+y^3-2*y^2+y)*z^3, |
---|
| 1440 | (-2*y^2+2*y)*z^2*w+(yx-3*y^2-y)*z^3; |
---|
[7ef5b6] | 1441 | |
---|
| 1442 | ring R5=integer,(x,y,z),dp; |
---|
| 1443 | ideal I=x2-y2-z2, |
---|
| 1444 | xy-z2, |
---|
| 1445 | y3+xz2-yz2+2z3+xy-z2, |
---|
| 1446 | -y2z2+2z4+x2-y2+z2, |
---|
| 1447 | y3z9+3y2z10+3yz11+z12-y2z2+2z4; |
---|
| 1448 | |
---|
| 1449 | ring R6=integer,(h, l, s, x, y, z),dp; //takes some time |
---|
| 1450 | ideal I=hl-l2-4ls+hy, |
---|
| 1451 | h2s-6ls3+h2z, |
---|
| 1452 | xh2-l2s-h3; |
---|
| 1453 | |
---|
| 1454 | ring R7=integer,(x,y,z),dp; |
---|
| 1455 | ideal I=x2-y2-(z+2)^2, |
---|
| 1456 | xy-(z+2)^2, |
---|
| 1457 | y3+x*(z+2)^2-y*(z+2)^2+2*(z+2)^3+xy-(z+2)^2, |
---|
| 1458 | -y^2*(z+2)^2+2*(z+2)^4+x2-y2+(z+2)^2, |
---|
| 1459 | y3z9+3y2z10+3yz11+z12-y2z2+2z4; |
---|
| 1460 | |
---|
| 1461 | ring R8=integer,(x,y,z),dp; |
---|
| 1462 | ideal I=x2-y2-(z+2)^2, |
---|
| 1463 | xy-(z+2)^2, |
---|
| 1464 | y3+x*(z+2)^2-y*(z+2)^2+2*(z+2)^3+xy-(z+2)^2, |
---|
| 1465 | -y^2*(z+2)^2+2*(z+2)^4+x2-y2+(z+2)^2, |
---|
| 1466 | y3z9+3y2z10+3yz11+z12-y2z2+2z4; |
---|
| 1467 | |
---|
| 1468 | ring R9=integer,(w,z,y,x),dp; |
---|
| 1469 | ideal I=630, |
---|
| 1470 | ((y^2-y)*x-y^3+y^2)*z^2, |
---|
| 1471 | (x-y)*zw, |
---|
| 1472 | (x-y^2)*zw+(-y^2+y)*z^2, |
---|
| 1473 | (-x^2+x)*w^2+(-yx+y)*zw; |
---|
| 1474 | |
---|
| 1475 | ring R10=integer,(w,z,y,x),dp; |
---|
| 1476 | ideal I=1260, |
---|
| 1477 | -yxzw+(-y^2+y)*z^2, |
---|
| 1478 | (-x^2+x)*w^2-yxzw, |
---|
| 1479 | ((-y^2+y)*x-y^3+2*y^2-y)*z^3, |
---|
| 1480 | (y^2-y)*z^2*w+(-y^2+y)*z^2*w+(-y^2+y)*z^3; |
---|
| 1481 | |
---|
| 1482 | ring R11=integer,(w,z,y,x),dp; |
---|
| 1483 | ideal I=(4*y^2*x^2+(4*y^3+4*y^2-y)*x-y^2-y)*z^2, |
---|
[602b552] | 1484 | (x+y+1)*zw+(-4*y^2*x-4*y^3-4*y^2)*z^2, |
---|
| 1485 | (-x-2*y^2 - 2*y - 1)*zw + (8*y^3*x + 8*y^4 + 8*y^3 + 2*y^2+y)*z^2, |
---|
[d69ff5] | 1486 | ((y^3 + y^2)*x - y^2 - y)*z^2, |
---|
| 1487 | (y +1)*zw + (-y^3 -y^2)*z^2, |
---|
| 1488 | (x + 1)*zw +(- y^2 -y)*z^2, |
---|
| 1489 | (x^2 +x)*w^2 + (-yx - y)*zw; |
---|
[7ef5b6] | 1490 | |
---|
| 1491 | ring R12=integer,(w,z,y,x),dp; |
---|
| 1492 | ideal I=72, |
---|
| 1493 | ((y^3 + y^2)*x - y^2 - y)*z^2, |
---|
| 1494 | (y + 1)*zw + (-y^3 -y^2)*z^2, |
---|
| 1495 | (x + 1)*zw + (-y^2 -y)*z^2, (x^2 + x)*w^2 + (-yx - y)*zw; |
---|
| 1496 | |
---|
| 1497 | ring R13=integer,(w,z,y,x),dp; |
---|
[d69ff5] | 1498 | ideal I=(((12*y+8)*x^2 +(2*y+2)*x)*zw +((-15*y^2 -4*y)*x-4*y^2 -y)*z^2, |
---|
[7ef5b6] | 1499 | -x*w^2 +((-12*y -8)*x+2*y)*zw +(15*y^2+4*y)*z^2, |
---|
[602b552] | 1500 | (81*y^4*x^2 +(-54*y^3 -12*y^2)*x-12*y^3 -3*y^2)*z^3, |
---|
[7ef5b6] | 1501 | (-24*yx+6*y^2-6*y)*z^2*w + (-81*y^4*x + 81*y^3 + 24*y^2)*z^3, |
---|
[602b552] | 1502 | (48*x^2 + (-30*y + 12)*x - 6*y)*z^2*w + ((81*y^3 -54*y^2 -24*y)*x |
---|
[d69ff5] | 1503 | -21*y^2 -6*y)*z^3, |
---|
| 1504 | (-96*yx-18*y^3 +18*y^2-24*y)*z^2*w +(243*y^5*x-243*y^4 +72*y^3 |
---|
| 1505 | +48*y^2)*z^3, |
---|
| 1506 | 6*y*z^2*w^2 +((576*y+384)*x^2 + (-81*y^3 -306*y^2 -168*y+96)*x+81*y^2 |
---|
| 1507 | -18*y)*z^3*w +((-720*y^2 - 192*y)*x + 450*y^3 - 60*y^2 - 48*y)*z^4); |
---|
[7ef5b6] | 1508 | |
---|
| 1509 | ring R14=integer,(x(1),x(2),x(3),x(4)),dp; |
---|
[d69ff5] | 1510 | ideal I=181*49^2, |
---|
| 1511 | x(4)^4, |
---|
| 1512 | x(1)*x(4)^3, |
---|
| 1513 | x(1)*x(2)*x(4)^2, |
---|
| 1514 | x(2)^2*x(4)^2, |
---|
| 1515 | x(2)^2*x(3)*x(4), |
---|
| 1516 | x(1)*x(2)*x(3)*x(4), |
---|
| 1517 | x(1)*x(3)^2*x(4), |
---|
| 1518 | x(3)^3*x(4); |
---|
[7ef5b6] | 1519 | |
---|
| 1520 | |
---|
[602b552] | 1521 | ring R15=integer,(x,y,z),dp; |
---|
[7ef5b6] | 1522 | ideal I=32003*181*64, |
---|
| 1523 | ((z^2-z)*y^2 + (z^2 -z)*y)*x; (z*y^3 + z*y^2)*x, |
---|
| 1524 | (y^4 - y^2)*x, (z^2 - z)*y*x^2, (y^3 - y^2)*x^2, |
---|
| 1525 | (z^3 - z^2)*x^4 + (2*z^3 -2*z^2)*x^3 + (z^3 -z^2)*x^2, |
---|
| 1526 | z*y^2*x^2, z*y*x^4 +z*y*x^3, |
---|
[ea87a9] | 1527 | 2*y^2*x^4 +6*y^2*x^3 +6*y^2*x^2 + (y^3 +y^2)*x, z*x^5 + (z^2 +z)*x^4 |
---|
[d69ff5] | 1528 | + (2*z^2 -z)*x^3 + (z^2 -z)*x^2, |
---|
[7ef5b6] | 1529 | y*x^6 + 3*y*x^5 + 3*y*x^4 + y*x^3; |
---|
| 1530 | |
---|
| 1531 | |
---|
| 1532 | ring R16=integer,(x(1),x(2),x(3),x(4),x(5)),dp; |
---|
| 1533 | ideal I=x(5)^5, |
---|
| 1534 | x(1)*x(5)^4, |
---|
| 1535 | x(1)*x(2)*x(5)^3, |
---|
| 1536 | x(2)^2*x(5)^3, |
---|
| 1537 | x(2)^2*x(3)*x(5)^2, |
---|
| 1538 | x(1)*x(2)*x(3)*x(5)^2, |
---|
[602b552] | 1539 | x(1)*x(3)^2*x(5)^2, |
---|
[7ef5b6] | 1540 | x(3)^3*x(5)^2, |
---|
| 1541 | x(3)^3*x(4)*x(5), |
---|
| 1542 | x(1)*x(3)^2*x(4)*x(5), |
---|
| 1543 | x(1)*x(2)*x(3)*x(4)*x(5), |
---|
| 1544 | x(2)^2*x(3)*x(4)*x(5), |
---|
[602b552] | 1545 | x(2)^2*x(4)^2*x(5), |
---|
[7ef5b6] | 1546 | x(1)*x(2)*x(4)^2*x(5), |
---|
| 1547 | x(1)*x(4)^3*x(5), |
---|
| 1548 | x(4)^4*x(5); |
---|
[049b78] | 1549 | I=intersectZ(I,ideal(64*181,x(1)^2)); |
---|
[7ef5b6] | 1550 | |
---|
[602b552] | 1551 | ring R17=integer,(x,y,z),dp; |
---|
[7ef5b6] | 1552 | ideal I=374, |
---|
| 1553 | (z+2)^8-140z6+2622*(z+2)^4-1820*(z+2)^2+169, |
---|
[602b552] | 1554 | 17y*(z+2)^4-374*y*(z+2)^2+221y+2z7-281z5+5240z3-3081z, |
---|
| 1555 | 204y2+136yz3-3128yz+z6-149z4+2739z2+117, |
---|
| 1556 | 17xz4-374xz2+221x+2z7-281z5+5240z3-3081z, |
---|
| 1557 | 136xy-136xz-136yz+2z6-281z4+5376z2-3081, |
---|
| 1558 | 204x2+136xz3-3128xz+z6-149z4+2739z2+117; |
---|
[7ef5b6] | 1559 | |
---|
| 1560 | ring R18=integer,(B,D,F,b,d,f),dp; |
---|
| 1561 | ideal I=6, |
---|
| 1562 | (b-d)*(B-D)-2*F+2, |
---|
| 1563 | (b-d)*(B+D-2*F)+2*(B-D), |
---|
| 1564 | (b-d)^2-2*(b+d)+f+1, |
---|
| 1565 | B^2*b^3-1, |
---|
| 1566 | D^2*d^3-1, |
---|
| 1567 | F^2*f^3-1; |
---|
| 1568 | |
---|
| 1569 | ring R19=integer,(a,b,c,d,e,f),dp; |
---|
| 1570 | ideal I=24, |
---|
| 1571 | 2*(f+2)*b+2ec+d2+a2+a, |
---|
| 1572 | 2*(f+2)*c+2ed+2ba+b, |
---|
| 1573 | 2*(f+2)*d+e2+2ca+c+b2, |
---|
| 1574 | 2*(f+2)*e+2da+d+2cb, |
---|
| 1575 | (f+2)^2+2ea+e+2db+c2, |
---|
| 1576 | 2*(f+2)*a+f+2eb+2dc; |
---|
| 1577 | |
---|
| 1578 | ring R20=integer,(x,y,z,w,u),dp; |
---|
| 1579 | ideal I=24, |
---|
| 1580 | 2x2-2y2+2z2-2w2+2u2-1, |
---|
| 1581 | 2x3-2y3+2z3-2w3+2u3-1, |
---|
| 1582 | 2x4-2y4+2z4-2w4+2u4-1, |
---|
| 1583 | 2x5-2y5+2z5-2w5+2u5-1, |
---|
| 1584 | 2x6-2y6+2z6-2w6+2u6-1; |
---|
| 1585 | |
---|
| 1586 | ring R21=integer,(x,y,z,t,u,v,h),dp; |
---|
| 1587 | ideal I=66, |
---|
| 1588 | 2x2+2y2+2z2+2t2+2u2+v2-vh, |
---|
| 1589 | xy+yz+2zt+2tu+2uv-uh, |
---|
| 1590 | 2xz+2yt+2zu+u2+2tv-th, |
---|
| 1591 | 2xt+2yu+2tu+2zv-zh, |
---|
| 1592 | t2+2xv+2yv+2zv-yh, |
---|
| 1593 | 2x+2y+2z+2t+2u+v-h, |
---|
| 1594 | x3+y3+z3+t3+u3+v3; |
---|
| 1595 | |
---|
[602b552] | 1596 | ring R22=integer,(s,p,S,P,T,F,f),dp; |
---|
[7ef5b6] | 1597 | ideal I=35, |
---|
| 1598 | 2*T-S*s-2*F+2, |
---|
| 1599 | 8*F*p-4*p*S-2*F*s^2+S*s^2+4*T-2*S*s, |
---|
| 1600 | -2*s-4*p+s^2+f+1, |
---|
| 1601 | s*T^2-p*s*P-p*S*T-2, |
---|
| 1602 | p^3*P^2-1, |
---|
| 1603 | F^2*f^3-1; |
---|
| 1604 | */ |
---|