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