// $Id: noethernormal.lib,v 1.3 1999-07-06 15:32:53 Singular Exp $
//(GP, last modified 15.08.98)
///////////////////////////////////////////////////////////////////////////////

version="$Id: noethernormal.lib,v 1.3 1999-07-06 15:32:53 Singular Exp $";
info="
LIBRARY:  noetherNormal.lib    PROCEDURE FOR NOETHERNORMALIZATION
PROCEDURES:
 noetherNormal(id);   noether normalization of ideal id
";

LIB "ring.lib";
LIB "random.lib";
///////////////////////////////////////////////////////////////////////////////
proc noetherNormal(ideal i)
"USAGE:  noetherNormal(id);  id ideal
RETURN:  two ideals i1,i2. is is an ideal generated by a subset of the
         variables, i1 defines a map: map phi=basering,i1 such that
         k[var(1),...,var(n)]/phi(id) is finite over k[i2]
EXAMPLE: noetherNormal; shows an example
"
{
   def r=basering;
   int n=nvars(r);

   //a procedure from ring.lib changing the order to lp creating a new
   //basering s
   changeord("s","lp");

   //creating lower triangular random generators for the maximal ideal
   //a procedure form random.lib
   ideal m=ideal(sparsetriag(n,n,0,100)*transpose(maxideal(1)));

   map phi=r,m;
   ideal i=std(phi(i));

   //from theoretical point of view noether normalization should be
   //o.k. but we need a test whether the coordinate change was random enough
   list l=finitenessTest(i);

   setring r;
   list l=imap(s,l);

   if(l[1]==1)
   {
      //the generic case
      return(list(fetch(s,m),l[2]));
   }
   kill s;
   //the bad case
   return(noetherNormal(i));
}
example
{ "EXAMPLE:"; echo = 2;
   ring r=0,(x,y,z),dp;
   ideal i= xy,xz;
   noetherNormal(i);
}


proc finitenessTest(ideal i)
{
   intvec v,w;
   int j;
   for(j=1;j<=size(i);j++)
   {
      w=leadexp(i[j]);
      if(size(ideal(w))==1)
      {
         //the leading term of i[j] is a pure power of some variable
         v=v+w;
      }
   }
   //the nonzero entries of v correspond to variables which occur as
   //pure power in the leading term of some polynomial in i
   ideal k;
   for(j=1;j<=size(v);j++)
   {
      if(v[j]==0)
      {
         k[size(k)+1]=var(j);
      }
   }
   if(dim(i)<=size(k))
   {
      return(list(1,k));
   }
   return(list(0,k));
}


proc mapIsFinite(R, map phi, ideal I)
"USAGE:  mapIsFinite(R,phi,I); R a ring, phi:R--->basering a map and
         I an ideal in the basering
RETURN:  1 if R---->basering/I is finite and 0 else
EXAMPLE: mapIsFinite; shows an example
"
{
  int n=nvars(R);
  def S=basering;

  setring R;
  ideal jj=maxideal(1);
  setring S;
  ideal jj=phi(jj);

  def T=S+R;
  setring T;
  changeord("@rr","lp");
//  ideal j=imap(S,phi(jj));
  ideal j=imap(S,jj);

  int i;
  for(i=1;i<=nvars(S);i++)
  {
    j[i]=j[i]-var(i+n);
  }
  j=j+imap(S,I);
  int l=finitenessTest(std(j))[1];
  setring S;
  kill(@rr);
  return(l);
}
example
{ "EXAMPLE:"; echo = 2;
   ring r=0,(a,b,c),dp;
   ring s=0,(x,y,z),dp;
   ideal i= xy;
   map phi=r,(xy)^3+x2+z,y2-1,z3;

   mapIsFinite(r,phi,i);
}