# source:git/Singular/LIB/algebra.lib@0ae4ce

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