7 Ring homomorphisms
  
  A  ring  homomorphism  is  a linear function f: R -> S that maps between two
  rings  R  and  S  and  which  preserves the operations of multiplication and
  addition:
  
  
       f(a + b) = f(a) + f(b) f(ab) = f(a)f(b) f(1) = 1
  
  
  
  7.1 The HAPRingHomomorphism datatype
  
  The  HAPRingHomomorphism  datatype  represents  a  particular  class of ring
  homomorphisms  (in  fact  usually  ring  isomorphisms), namely those between
  rings  presented as quotient rings of polynomial rings, where the source and
  target rings have the same coefficient ring. They represent the mapping
  
  
       R/I -> S/J
  
  
  where  R  = k[x_1, ..., x_n] and S = k[y_1, ..., x_m] and I and J are ideals
  in R and S respectively.
  
  Such a ring homomorphism may be specified by the following information
  
  --    a polynomial ring R
  
  --    a list of polynomials in R that generate the ideal I
  
  --    a  list  Q = [q_1, ..., q_n] where each q_i in S/J is the image of the
        indeterminate x_i in R under the homomorphism.
  
  The target ideal J is assumed to be the image of I under the homomorphism.
  
  
  7.1-1 Implementation details
  
  Various  different  internal representations are used for ring homomorphisms
  in  HAPprime,  depending on the source and target ring. The user need not be
  concerned  with  the different representations, which correspond to the five
  constructors              HAPRingToSubringHomomorphism              (7.2-1),
  HAPSubringToRingHomomorphism  (7.2-2), HAPRingHomomorphismByIndeterminateMap
  (7.2-3),  HAPRingReductionHomomorphism  (7.2-4)  and HAPZeroRingHomomorphism
  (7.2-6), and which are hopefully largely self-explanatory.
  
  Most of the provided representations of ring homomorphisms use Gröbner bases
  and  polynomial  reduction  to  perform  the mapping. This uses the singular
  package 'singular: singular: the GAP interface to Singular' which gives good
  speed  and  access  to  improved monomial orderings. This datatype cannot be
  used without the singular package.
  
  
  7.1-2 Elimination orderings
  
  Using  Gröbner bases to map from one polynomial ring R to another polynomial
  ring  S  relies on applying a global ordering to the joint ring R cup S. For
  all  polynomials  p  in R and q in S, this ordering must give p > q, so that
  terms   involving  elements  of  R  will  be  replaced  by  those  in  S.  A
  straightforward  solution  is  to  use  a  lexicographic term ordering which
  orders the indeterminates of R before those of S. However, computing Gröbner
  bases  using  a  lexicographic ordering can be much more expensive that with
  other  orderings,  or sometimes even a change of the order of indeterminates
  is enough change the order of the computation. A range of different ordering
  can  be requested by using the GAP options stack 'Reference: Options Stack',
  and  setting  the options EliminationIndexOrder and EliminationBlockOrdering
  as described below.
  
  The  option  EliminationIndexOrder  determines the indeterminate ordering to
  use. Possible values are the following strings:
  
  --    "Forward" (default) Indeterminates are ordered as in the definition of
        R and S: p_1 > p_2 > ... > p_n > q_1 > q_2 > ... > q_m.
  
  --    "Reverse"  Lexicographic  ordering  in  reverse  order  to that in the
        definition  of  R and S: p_n > p_n-1 > ... > p_1 > q_m > q_m-1 > ... >
        q_1.
  
  --    "Shuffle"  Lexicographic  ordering  using  a  random  shuffle  of  the
        indeterminates in R and S.
  
  --    "ShuffleNN" where NN is some non-negative integer. This is the same as
        Shuffle,  but  using  the value of NN as the random seed (and hence is
        deterministic).
  
  When  comparing  two  monomials,  the  elimination ordering ensures that the
  parts  of the two monomials involving the indeterminates from R are compared
  first,  and  then in the event of a tie, the part involving those from S are
  compared.   The  option  EliminationBlockOrdering  determines  the  monomial
  ordering to use for each of these two comparisons. This is given as a string
  which  is  the concatenation of the two required orderings. For example, the
  default  ordering  is "LexGrlex" which means lexicographic ordering over the
  indeterminates of R, and graded lexicographic over the indeterminates of S.
  
  --    "Lex"  Lexicographic  ordering,  the  equivalent  of  the GAP ordering
        MonomialLexOrdering (Reference: MonomialLexOrdering)).
  
  --    "Grlex"    Graded    lexicographic   ordering,   the   equivalent   of
        MonomialGrlexOrdering (Reference: MonomialGrlexOrdering).
  
  --    "Grevlex"  Graded  reverse  lexicographic  ordering, the equivalent of
        MonomialGrevlexOrdering (Reference: MonomialGrevlexOrdering).
  
  
  7.2 Construction functions
  
  7.2-1 HAPRingToSubringHomomorphism
  
  > HAPRingToSubringHomomorphism( Rring, Rrels, Simages ) ___________operation
  Returns:  HAPRingHomomorphism
  
  Creates  a  HAPRingHomomorphism  which represents the mapping R/I -> S/J. In
  this  form, Rring a polynomial ring R and Rrels an ideal I in that ring. The
  image of the indeterminates of R under this mapping are given in Simages and
  generate the ring S, while the relations Rrels are mapped to generate J. The
  ring S may be a subring of the full polynomial ring in its indeterminates.
  
  
  7.2-2 HAPSubringToRingHomomorphism
  
  > HAPSubringToRingHomomorphism( Rgens, Rrels, Sring ) _____________operation
  > HAPSubringToRingHomomorphism( Rgens, Sring, Srels ) _____________operation
  Returns:  HAPRingHomomorphism
  
  Creates  a  HAPRingHomomorphism which represents the mapping R/I -> S/J. The
  ring  R is generated by a set of polynomials Rgens (so R may be a subring of
  the  full  polynomial ring in its indeterminates). The images of Rgens under
  the  mapping  are  the indeterminates of the polynomial ring given in Sring.
  The ideals can be specified either as a set of relations Srels in the target
  ring  S,  or  as a set of relations Rrels in the source ring. In this second
  case,  Rrels  can  be polynomials in the full polynomial ring, in which case
  the  ideal I is the intersection of the ideal they generate in the full ring
  with  the  subring generated by Rgens. In both cases, the specified ideal is
  mapped  with  the  homomorphism  (or  its inverse) to find the corresponding
  ideal in the other ring.
  
  This  ring  homomorphism  uses Gröbner bases to perform the mapping, and the
  time  taken to calculate the basis in this function can be influenced by the
  choice of monomial ordering. See 7.1-2 for more details.
  
  7.2-3 HAPRingHomomorphismByIndeterminateMap
  
  > HAPRingHomomorphismByIndeterminateMap( R, Rrels, S ) ____________operation
  Returns:  HAPRingHomomorphism
  
  Creates a HAPRingHomomorphism which represents the map R/I -> S/J which is a
  simple  relabelling of indeterminates: the image of the ith indeterminate of
  R  under  the mapping is taken to be the ith indeterminate of S. The ideal I
  is generated by Rrels and are mapped using the homomorphism to generate J.
  
  7.2-4 HAPRingReductionHomomorphism
  
  > HAPRingReductionHomomorphism( R, Rrels[, avoid] ) _______________operation
  > HAPRingReductionHomomorphism( phi[, avoid] ) ____________________operation
  Returns:  HAPRingHomomorphism
  
  For  a polynomial ring R and ideal I generated by Rrels, this function finds
  an  isomorphic  ring in fewer indeterminates (or the same number, if this is
  not  possible).  This  new  ring  will avoid the indeterminates of R and any
  further indeterminates listed in avoid. The function returns the map between
  R/I and the new ring.
  
  In  the  second  form,  this  function  reduces  the target ring of the ring
  homomorphism phi and returns the map between this and the reduced ring. This
  map will also avoid the indeterminates in the source ring of phi.
  
  7.2-5 PartialCompositionRingHomomorphism
  
  > PartialCompositionRingHomomorphism( M, N ) ______________________operation
  Returns:  HAPRingHomomorphism
  
  Creates  a  HAPRingHomomorphism  which  represents  the  composition  of the
  HAPRingHomomorphism  maps  M followed by N. The source of N may be a subring
  of the target of M.
  
  Note   that,  unlike  the  other  HAPRingHomomorphism  representations,  the
  generators  listed  by  SourceGenerators (7.3-1) and ImageGenerators (7.3-4)
  are  not  in  correspondance.  Also,  this  is  not  an  isomorphism, so the
  relations reported by SourceRelations (7.3-2) and ImageRelations (7.3-5) are
  simply  the  relations  of  the source and image rings, and are not the same
  ideal.  Because  this is not an isomorphism, InverseRingHomomorphism (7.2-7)
  will  return  fail,  although PreimageOfRingHomomorphism (7.4-2) can be used
  (and will return fail if no preimage exists).
  
  7.2-6 HAPZeroRingHomomorphism
  
  > HAPZeroRingHomomorphism( R, Rrels ) _____________________________operation
  Returns:  HAPRingHomomorphism
  
  Creates  a  HAPRingHomomorphism  which  maps  from the ring R, with an ideal
  generated by Rrels, into the trival ring generated by zero.
  
  7.2-7 InverseRingHomomorphism
  
  > InverseRingHomomorphism( phi ) __________________________________attribute
  Returns:  HAPRingHomomorphism
  
  Returns (as a ring homomorphism) the inverse of the ring homomorphism phi.
  
  If the inverse homomorphism requires an elimination Gröbner basis to perform
  the mapping (for example when computing the inverse of a HAPRingHomomorphism
  constructed with HAPRingToSubringHomomorphism (7.2-1)) then the ordering can
  be specified using the options stack. See 7.1-2 for more details.
  
  7.2-8 CompositionRingHomomorphism
  
  > CompositionRingHomomorphism( phiA, phiB ) _______________________operation
  Returns:  HAPRingHomomorphism
  
  Returns   the  ring  homomorphism  that  is  the  composition  of  the  ring
  homomorphisms  phiA  and  phiB. The source ring of phiB must be in the image
  ring of phiA.
  
  
  7.3 Data access functions
  
  7.3-1 SourceGenerators
  
  > SourceGenerators( phi ) _________________________________________attribute
  Returns:  List
  
  A list of generators for the source ring R/I of the ring homomorphism. phi.
  
  7.3-2 SourceRelations
  
  > SourceRelations( phi ) __________________________________________attribute
  Returns:  List
  
  A  list  of the relations that generate the ideal I of in the source ring of
  the ring homomorphism phi.
  
  7.3-3 SourcePolynomialRing
  
  > SourcePolynomialRing( phi ) _____________________________________attribute
  Returns:  PolynomialRing
  
  Returns  the  polynomial  ring  which  contains  the source ring of the ring
  homomorphism phi. Polynomials to be mapped by phi must be in this ring.
  
  7.3-4 ImageGenerators
  
  > ImageGenerators( phi ) __________________________________________attribute
  Returns:  List
  
  A list of generators for the image ring S/J of the ring homomorphism phi.
  
  7.3-5 ImageRelations
  
  > ImageRelations( phi ) ___________________________________________attribute
  Returns:  List
  
  A  list  of  the relations that generate the ideal J of in the image ring of
  the ring homomorphism phi.
  
  7.3-6 ImagePolynomialRing
  
  > ImagePolynomialRing( phi ) ______________________________________attribute
  Returns:  PolynomialRing
  
  Returns   the   polynomial  ring  which  contains  the  image  of  the  ring
  homomorphism phi>. All polynomials mapped by phi will be in this ring.
  
  
  7.4 General functions
  
  
  7.4-1 ImageOfRingHomomorphism
  
  > ImageOfRingHomomorphism( phi, poly ) ____________________________operation
  > ImageOfRingHomomorphism( phi, coll ) ____________________________operation
  Returns:  Polynomial or list
  
  Returns  the  image  of the polynomial poly under the ring homomorphism phi.
  The   input   must  be  an  element(s)  of  the  source  ring  of  phi  (see
  SourcePolynomialRing (7.3-3)).
  
  
  7.4-2 PreimageOfRingHomomorphism
  
  > PreimageOfRingHomomorphism( phi, poly ) _________________________operation
  > PreimageOfRingHomomorphism( phi, coll ) _________________________operation
  Returns:  Polynomial or list
  
  Returns the preimage of the polynomial poly under the ring homomorphism phi.
  The   input   must   be  an  element(s)  of  the  image  ring  of  phi  (see
  ImagePolynomialRing    (7.3-6)).    This   function   is   a   synonym   for
  ImageOfRingHomomorphism(InverseRingHomomorphism(phi), poly).
  
  
  7.5 Example: Constructing and using a HAPRingHomomorphism
  
  As  an  initial  example, we shall construct a ring homomorphism phi: k[x_1,
  x_2]  -> k[x_3, x_4] (i.e. ideal) with the mapping x_1 -> x_3 and x_2 -> x_3
  +  x_4.  In  all  these  examples,  we  shall  take k to be the field of two
  elements,  GF(2).  We  demonstrate  that this is an isomorphism by mapping a
  polynomial from the source ring to the target and back again.
  
  ---------------------------  Example  ----------------------------
    gap> R := PolynomialRing(GF(2), 2);;
    gap> S := PolynomialRing(GF(2), 2, IndeterminatesOfPolynomialRing(R));;
    gap> phi := HAPRingToSubringHomomorphism(R, [], [S.1, S.1+S.2]);
    <Ring homomorphism>
    gap> p := ImageOfRingHomomorphism(phi, R.1^3+R.1*R.2+R.2);
    x_3^3+x_3^2+x_3*x_4+x_3+x_4
    gap> PreimageOfRingHomomorphism(phi, p);
    x_1^3+x_1*x_2+x_2
  ------------------------------------------------------------------
  
  Some ring presentations are not in minimal form: there is an isomorphic ring
  in  fewer  indeterminates. The HAPRingReductionHomomorphism (7.2-4) function
  can  find  and  return  an  isomorphism  that maps to this reduced ring. For
  example,  the  ring  k[x_1,  x_2,  x_3]/(x_1^2  + x_2^3, x_2^2 + x_3) has an
  isomorphic  presentation  in  only  two  indeterminates, as this computation
  shows:
  
  ---------------------------  Example  ----------------------------
    gap> R := PolynomialRing(GF(2), 3);;
    gap> I := [R.1^2+R.2^3, R.2^2+R.3];
    [ x_2^3+x_1^2, x_2^2+x_3 ]
    gap> phi := HAPRingReductionHomomorphism(R, I);
    <Ring homomorphism>
    gap> ImagePolynomialRing(phi);
    GF(2)[x_4,x_5]
    gap> ImageRelations(phi);
    [ x_5^3+x_4^2 ]
  ------------------------------------------------------------------
  
  The source and target of HAPRingHomomorphisms can be quotient rings, and any
  relations  can  be  specified  at  the source of target. When mapping from a
  subring  to  a full ring, the source relations do not necessarily need to be
  specified  in  the source ring, but could instead be given in its containing
  ring.  For example, consider the ring R/I where R = k[x_1, x_2, x_3] and I =
  x_1^3+x_3  and  the  subring  generated  by (x_1, x_2, x_3^2). If we wish to
  specify the homomorphism phi: R/I -> S/J where S = k[x_4, x_5, x_6] with the
  natural map from the generators of R to those of S then we only need specify
  the original ideal I, even though it is not in the subring. The intersection
  between  I  and the subring is found to be x_1^4+x_3^2, and it is this ideal
  that is used in the homomorphism, as this example shows:
  
  ---------------------------  Example  ----------------------------
    gap> R := PolynomialRing(GF(2), 3);;
    gap> I := [R.1^2+R.3];
    [ x_1^2+x_3 ]
    gap> S := PolynomialRing(GF(2), 3, IndeterminatesOfPolynomialRing(R));;
    gap> phi := HAPSubringToRingHomomorphism([R.1, R.2, R.3^2], I, S);
    <Ring homomorphism>
    gap> Display(phi);
    Ring homomorphism
      x_1 -> x_4
      x_2 -> x_5
      x_3^2 -> x_6
    with relations
      [ x_1^2+x_3 ]
    and
      [ x_4^4+x_6 ]
    gap> Display(InverseRingHomomorphism(phi));
    Ring homomorphism
      x_4 -> x_1
      x_5 -> x_2
      x_6 -> x_3^2
    with relations
      [ x_4^4+x_6 ]
    and
      [ x_1^4+x_3^2 ]
  ------------------------------------------------------------------
  
  Ring homomorphisms can also be composed with each other. For example, we can
  take  the  HAPSubringToRingHomomorphism  (7.2-2) above and change the target
  indeterminates         by         composing        this        with        a
  HAPRingHomomorphismByIndeterminateMap (7.2-3):
  
  ---------------------------  Example  ----------------------------
    gap> R := PolynomialRing(GF(2), 3);;
    gap> I := [R.1^2+R.3];
    [ x_1^2+x_3 ]
    gap> S := PolynomialRing(GF(2), 3, IndeterminatesOfPolynomialRing(R));;
    gap> phi := HAPSubringToRingHomomorphism([R.1, R.2, R.3^2], I, S);
    <Ring homomorphism>
    gap> #
    gap> T := PolynomialRing(GF(2), 3, [R.1, R.2, R.3, S.1, S.2, S.3]);;
    gap> phi2 := HAPRingHomomorphismByIndeterminateMap(
    >   ImagePolynomialRing(phi), ImageRelations(phi), T);
    <Ring homomorphism>
    gap> Display(CompositionRingHomomorphism(phi, phi2));
    Ring homomorphism
      x_1 -> x_7
      x_2 -> x_8
      x_3^2 -> x_9
    with relations
      [ x_1^2+x_3 ]
    and
      [ x_7^4+x_9 ]
  ------------------------------------------------------------------