home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / lib / field.g < prev    next >
Encoding:
Text File  |  1993-05-05  |  30.5 KB  |  1,088 lines
  1. #############################################################################
  2. ##
  3. #A  field.g                     GAP library                  Martin Schoenert
  4. ##
  5. #A  @(#)$Id: field.g,v 3.9 1993/01/20 11:14:52 fceller Rel $
  6. ##
  7. #Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. ##
  9. ##  This file contains  those  functions  that  are  dispatcher  for  fields.
  10. ##
  11. #H  $Log: field.g,v $
  12. #H  Revision 3.9  1993/01/20  11:14:52  fceller
  13. #H  added generic 'Polynomial' and 'PolynomialRing'
  14. #H
  15. #H  Revision 3.8  1992/12/16  19:47:27  martin
  16. #H  replaced quoted record names with escaped ones
  17. #H
  18. #H  Revision 3.7  1992/11/16  12:22:40  fceller
  19. #H  added Laurent polynomials
  20. #H
  21. #H  Revision 3.6  1992/08/13  13:11:09  fceller
  22. #H  add 'Indeterminate'
  23. #H
  24. #H  Revision 3.5  1992/04/05  14:50:49  martin
  25. #H  changed 'Field' slightly
  26. #H
  27. #H  Revision 3.4  1992/03/27  11:14:51  martin
  28. #H  changed mapping to general mapping and function to mapping
  29. #H
  30. #H  Revision 3.3  1992/02/11  14:16:36  martin
  31. #H  added 'GaloisGroup'
  32. #H
  33. #H  Revision 3.2  1991/12/04  09:07:01  martin
  34. #H  changed 'Field' and 'DefaultField' to use 'Domain', removed 'FieldDomain'
  35. #H
  36. #H  Revision 3.1  1991/10/10  12:38:50  martin
  37. #H  changed everything for new domain concept
  38. #H
  39. #H  Revision 3.0  1991/08/08  15:30:29  martin
  40. #H  initial revision under RCS
  41. #H
  42. ##
  43.  
  44.  
  45. #############################################################################
  46. ##
  47. #F  IsField(<D>)  . . . . . . . . . . . . . . . . test if a domain is a field
  48. ##
  49. IsField := function ( D )
  50.     return IsRec( D )  and IsBound( D.isField )  and D.isField;
  51. end;
  52.  
  53.  
  54. #############################################################################
  55. ##
  56. #V  FieldOps  . . . . . . . . . . . . . . . . . . operations record for field
  57. ##
  58. ##  'FieldOps' is the operations record for fields.
  59. ##
  60. ##  The operations records for special fields are created by making a copy of
  61. ##  this record and overlaying some functions.  This way those fields inherit
  62. ##  the default methods.
  63. ##
  64. FieldOps := Copy( DomainOps );
  65.  
  66.  
  67. #############################################################################
  68. ##
  69. #F  FieldOps.\=( <F>, <G> )  . . . . . . . . . . . . . comparisons of fields
  70. ##
  71. FieldOps.\= := function ( F, G )
  72.     local   isEql;
  73.     if IsField( F ) and IsFinite( F )  then
  74.         if IsField( G ) and IsFinite( G )  then
  75.             isEql :=     ( Size( F ) = Size( G ) )
  76.                      and ForAll( F.generators, g -> g in G )
  77.                      and ForAll( G.generators, g -> g in F );
  78.         elif IsField( G )  then
  79.             isEql := false;
  80.     else
  81.             isEql := DomainOps.\=( F, G );
  82.         fi;
  83.     elif IsField( F )  then
  84.         if IsField( G )  and IsFinite( G )  then
  85.             isEql := false;
  86.         elif IsField( G )  then
  87.             isEql :=     ForAll( F.generators, g -> g in G )
  88.                      and ForAll( G.generators, g -> g in F );
  89.     else
  90.             isEql := DomainOps.\=( F, G );
  91.         fi;
  92.     else
  93.         isEql := DomainOps.\=( F, G );
  94.     fi;
  95.     return isEql;
  96. end;
  97.  
  98.  
  99. #############################################################################
  100. ##
  101. #F  FieldOps.IsSubset(<F>,<G>)  . .  test if something is a subset of a field
  102. ##
  103. FieldOps.IsSubset := function ( F, G )
  104.     local   isSub;
  105.     if IsField( F ) and IsFinite( F )  then
  106.         if IsField( G ) and IsFinite( G )  then
  107.             isSub :=     Size( F ) mod Size( G ) = 0
  108.                      and (Size( F ) - 1) mod (Size( G ) - 1) = 0
  109.                      and ForAll( G.generators, g -> g in F );
  110.         elif IsField( G )  then
  111.             isSub := false;
  112.     else
  113.             isSub := DomainOps.\=( F, G );
  114.         fi;
  115.     elif IsField( F )  then
  116.         if IsField( G )  then
  117.             isSub := ForAll( G.generators, g -> g in F );
  118.     else
  119.             isSub := DomainOps.\=( F, G );
  120.         fi;
  121.     else
  122.         isSub := DomainOps.\=( F, G );
  123.     fi;
  124.     return isSub;
  125. end;
  126.  
  127.  
  128. #############################################################################
  129. ##
  130. #F  FieldOps.Print( <F> ) . . . . . . . . . . . . . . . . . . . print a field
  131. ##
  132. FieldOps.Print := function ( F )
  133.     local   i;
  134.     if IsBound( F.name )  then
  135.         Print( F.name );
  136.     else
  137.         Print( "Field( ");
  138.         for i  in [1..Length(F.generators)-1]  do
  139.             Print( F.generators[i], ", " );
  140.         od;
  141.         Print( F.generators[Length(F.generators)], " )" );
  142.         if IsBound( F.field )  then
  143.             Print( "/", F.field );
  144.         fi;
  145.     fi;
  146. end;
  147.  
  148.  
  149. #############################################################################
  150. ##
  151. #F  FieldOps.\/( <F>, <G> )  . . . . . . . . . . . .  quotient of two fields
  152. ##
  153. FieldOps.\/ := function ( F, G )
  154.     local   Q;
  155.  
  156.     # check the arguments
  157.     if IsField(F)  and IsField(G)  and IsSubset(F,G)  then
  158.  
  159.         # make the domain
  160.         Q := rec();
  161.         Q.isDomain      := true;
  162.         Q.isField       := true;
  163.  
  164.         # enter the identification
  165.         Q.char          := F.char;
  166.         Q.degree        := F.degree;
  167.         Q.generators    := F.generators;
  168.         Q.zero          := F.zero;
  169.         Q.one           := F.one;
  170.  
  171.         # enter the knowledge
  172.         Q.size          := F.size;
  173.         Q.isFinite      := F.isFinite;
  174.  
  175.         # enter the subfield
  176.         Q.field         := G;
  177.         Q.dimension     := F.degree / G.degree;
  178.  
  179.         # and finally the operations record
  180.         Q.operations    := F.operations;
  181.  
  182.     else
  183.         Error("<G> must be a subfield of <F>");
  184.     fi;
  185.  
  186.     # return the quotient
  187.     return Q;
  188. end;
  189.  
  190.  
  191. #############################################################################
  192. ##
  193. #F  FieldOps.\^( <F>, <n> )  . . . . . . . . . . . .  row space over a field
  194. ##
  195. FieldOps.\^ := function ( F, n )
  196.     local   V;
  197.     if IsField(F)  and IsInt(n)  and 0 <= n  then
  198.         V := RowSpace( n, F );
  199.     else
  200.         Error("power of <F> and <n> is not defined");
  201.     fi;
  202.     return V;
  203. end;
  204.  
  205.  
  206. #############################################################################
  207. ##
  208. #F  GaloisGroup( <F> )  . . . . . . . . . . . . . . . Galois group of a field
  209. ##
  210. GaloisGroup := function ( F )
  211.  
  212.     # check the argument
  213.     if not IsField( F )  then
  214.         Error("<F> must be a field");
  215.     fi;
  216.  
  217.     # compute the Galois group
  218.     if not IsBound( F.galoisGroup )  then
  219.         F.galoisGroup := F.operations.GaloisGroup( F );
  220.     fi;
  221.  
  222.     # return the Galois group
  223.     return F.galoisGroup;
  224. end;
  225.  
  226. FieldOps.GaloisGroup := function ( F )
  227.     Error("sorry, no generic method to compute the Galois group");
  228. end;
  229.  
  230. FieldOps.AutomorphismGroup := function ( F )
  231.     return GaloisGroup( F );
  232. end;
  233.  
  234.  
  235. #############################################################################
  236. ##
  237. #F  Conjugates([<F>,]<z>) . . . . . . . . . . . conjugates of a field element
  238. ##
  239. Conjugates := function ( arg )
  240.     local   F,          # field <F>, optional first argument
  241.             z;          # element <z>, second argument
  242.  
  243.     # get and check the arguments
  244.     if Length(arg) = 1  then
  245.         F := DefaultField( arg[1] );
  246.         z := arg[1];
  247.     elif Length(arg) = 2  then
  248.         F := arg[1];
  249.         if not IsField(F)  then Error("<F> must be a field");  fi;
  250.         z := arg[2];
  251.         if not z in F      then Error("<z> must lie in <F>");  fi;
  252.     else
  253.         Error("usage: Conjugates( [<F>,] <z> )");
  254.     fi;
  255.  
  256.     # return the conjugates
  257.     return F.operations.Conjugates( F, z );
  258. end;
  259.  
  260. FieldOps.Conjugates := function ( F, z )
  261.     local   cnjs,       # conjugates of <z> in <F>, result
  262.             aut;        # automorphism of <F>
  263.  
  264.     # compute the conjugates simply by applying all the automorphisms
  265.     cnjs := [];
  266.     for aut  in Elements( GaloisGroup( F ) )  do
  267.         Add( cnjs, z ^ aut );
  268.     od;
  269.  
  270.     # return the conjugates
  271.     return cnjs;
  272. end;
  273.  
  274.  
  275. #############################################################################
  276. ##
  277. #F  Norm([<F>,]<z>) . . . . . . . . . . . . . . . . . norm of a field element
  278. ##
  279. Norm := function ( arg )
  280.     local   F,          # field <F>, optional first argument
  281.             z;          # element <z>, second argument
  282.  
  283.     # get and check the arguments
  284.     if Length(arg) = 1  then
  285.         F := DefaultField( arg[1] );
  286.         z := arg[1];
  287.     elif Length(arg) = 2  then
  288.         F := arg[1];
  289.         if not IsField(F)  then Error("<F> must be a field");  fi;
  290.         z := arg[2];
  291.         if not z in F      then Error("<z> must lie in <F>");  fi;
  292.     else
  293.         Error("usage: Norm( [<F>,] <z> )");
  294.     fi;
  295.  
  296.     # return the norm
  297.     return F.operations.Norm( F, z );
  298. end;
  299.  
  300. FieldOps.Norm := function ( F, z )
  301.     return Product( Conjugates( F, z ) );
  302. end;
  303.  
  304.  
  305. #############################################################################
  306. ##
  307. #F  Trace([<F>,]<z>)  . . . . . . . . . . . . . . .  trace of a field element
  308. ##
  309. Trace := function ( arg )
  310.     local   F,          # field <F>, optional first argument
  311.             z;          # element <z>, second argument
  312.  
  313.     # get and check the arguments
  314.     if Length(arg) = 1  then
  315.         F := DefaultField( arg[1] );
  316.         z := arg[1];
  317.     elif Length(arg) = 2  then
  318.         F := arg[1];
  319.         if not IsField(F)  then Error("<F> must be a field");  fi;
  320.         z := arg[2];
  321.         if not z in F      then Error("<z> must lie in <F>");  fi;
  322.     else
  323.         Error("usage: Trace( [<F>,] <z> )");
  324.     fi;
  325.  
  326.     # return the trace
  327.     return F.operations.Trace( F, z );
  328. end;
  329.  
  330. FieldOps.Trace := function ( F, z )
  331.     return Sum( Conjugates( F, z ) );
  332. end;
  333.  
  334.  
  335. #############################################################################
  336. ##
  337. #F  CharPol([<F>,]<z>)  . . . . . . characteristic polynom of a field element
  338. ##
  339. CharPol := function ( arg )
  340.     local   F,          # field <F>, optional first argument
  341.             z;          # element <z>, second argument
  342.  
  343.     # get and check the arguments
  344.     if Length(arg) = 1  then
  345.         F := DefaultField( arg[1] );
  346.         z := arg[1];
  347.     elif Length(arg) = 2  then
  348.         F := arg[1];
  349.         if not IsField(F)  then Error("<F> must be a field");  fi;
  350.         z := arg[2];
  351.         if not z in F      then Error("<z> must lie in <F>");  fi;
  352.     else
  353.         Error("usage: CharPol( [<F>,] <z> )");
  354.     fi;
  355.  
  356.     # return the characteristic polynom
  357.     return F.operations.CharPol( F, z );
  358. end;
  359.  
  360. FieldOps.CharPol := function ( F, z )
  361.     local   pol,        # characteristic polynom of <z> in <F>, result
  362.             deg,        # degree of <pol>
  363.             con,        # conjugate of <z> in <F>
  364.             i;          # loop variable
  365.  
  366.     # compute the trace simply by multiplying $x-cnj$
  367.     pol := [ F.one ];
  368.     deg := 0;
  369.     for con  in Conjugates( F, z )  do
  370.         pol[deg+2] := pol[deg+1];
  371.         for i  in Reversed([2..deg+1])  do
  372.             pol[i] := pol[i-1] -  con * pol[i];
  373.         od;
  374.         pol[1] := F.zero - con * pol[1];
  375.         deg := deg + 1;
  376.     od;
  377.  
  378.     # return the characteristic polynom
  379.     return pol;
  380. end;
  381.  
  382.  
  383. #############################################################################
  384. ##
  385. #F  MinPol([<F>,]<z>) . . . . . . . . . .  minimal polynom of a field element
  386. ##
  387. MinPol := function ( arg )
  388.     local   F,          # field <F>, optional first argument
  389.             z;          # element <z>, second argument
  390.  
  391.     # get and check the arguments
  392.     if Length(arg) = 1  then
  393.         F := DefaultField( arg[1] );
  394.         z := arg[1];
  395.     elif Length(arg) = 2  then
  396.         F := arg[1];
  397.         if not IsField(F)  then Error("<F> must be a field");  fi;
  398.         z := arg[2];
  399.         if not z in F      then Error("<z> must lie in <F>");  fi;
  400.     else
  401.         Error("usage: MinPol( [<F>,] <z> )");
  402.     fi;
  403.  
  404.     # return the minimal polynom
  405.     return F.operations.MinPol( F, z );
  406. end;
  407.  
  408. FieldOps.MinPol := function ( F, z )
  409.     local   pol,        # minimal polynom of <z> in <F>, result
  410.             deg,        # degree of <pol>
  411.             con,        # conjugate of <z> in <F>
  412.             i;          # loop variable
  413.  
  414.     # compute the trace simply by multiplying $x-cnj$
  415.     pol := [ F.one ];
  416.     deg := 0;
  417.     for con  in Set( Conjugates( F, z ) )  do
  418.         pol[deg+2] := pol[deg+1];
  419.         for i  in Reversed([2..deg+1])  do
  420.             pol[i] := pol[i-1] -  con * pol[i];
  421.         od;
  422.         pol[1] := F.zero - con * pol[1];
  423.         deg := deg + 1;
  424.     od;
  425.  
  426.     # return the minimal polynom
  427.     return pol;
  428. end;
  429.  
  430.  
  431. #############################################################################
  432. ##
  433. #V  FieldElements . . . . . . . . . . . . . . .  domain of all field elements
  434. #V  FieldElementsOps  . operations record of the domain of all field elements
  435. ##
  436. ##  'FieldElements' is   the domain of all  field  elements, i.e., rationals,
  437. ##  cyclotomics, finite  field  elements,  and  record that  implement  field
  438. ##  elements.  Note that 'FieldElements' is not a field.
  439. ##
  440. ##  'FieldElementsOps'  is  the operations  record   for  the 'FieldElements'
  441. ##  domain.  The  operations       record  of other  field    domains    like
  442. ##  'FiniteFieldElements' inherit default methods from this record.
  443. ##
  444. ##  Those domains are known  to 'FieldDomain', and they  know how to create a
  445. ##  field that contains a given list of elements.
  446. ##
  447. ##  If you think this domain is superfluous I shall have to agree.  It exists
  448. ##  mainly to check the feasibility of this concept, which is convenient with
  449. ##  groups, for categories besides groups.
  450. ##
  451. FieldElementsOps         := Copy( DomainOps );
  452.  
  453. FieldElementsOps.\in    := function ( z, FieldElements )
  454.     return IsRat( z )
  455.         or IsCyc( z )
  456.         or IsFFE( z )
  457.         or IsRec( z )  and IsBound(z.isFieldElement)  and z.isFieldElement;
  458. end;
  459.  
  460. FieldElementsOps.Order   := function ( F, z )
  461.     local   ord, elm;
  462.     if z = F.zero  then
  463.         ord := 0;
  464.     else
  465.         elm := z;
  466.         ord := 1;
  467.         while elm <> F.one  do
  468.             elm := elm * z;
  469.             ord := ord + 1;
  470.         od;
  471.     fi;
  472.     return ord;
  473. end;
  474.  
  475.  
  476. FieldElements            := rec();
  477. FieldElements.isDomain   := true;
  478.  
  479. FieldElements.name       := "FieldElements";
  480.  
  481. FieldElements.isFinite   := false;
  482. FieldElements.size       := "infinity";
  483.  
  484. FieldElements.operations := FieldElementsOps;
  485.  
  486.  
  487. #############################################################################
  488. ##
  489. #F  Field(<z>,...)  . . . . . . . . . . . field containing a list of elements
  490. ##
  491. Field := function ( arg )
  492.     local   F,          # field containing the elements of <arg>, result
  493.             D;          # domain containing the elements of <arg>
  494.  
  495.     # if called with one domain argument look in the operations record
  496.     if Length(arg) = 1  and IsDomain(arg[1])  then
  497.         F := arg[1].operations.Field( arg[1] );
  498.  
  499.     # special case for one square matrix
  500.     elif    Length(arg) = 1
  501.         and IsMat(arg[1])  and Length(arg[1]) = Length(arg[1][1])
  502.     then
  503.         D := Domain( arg );
  504.         F := D.operations.Field( arg );
  505.  
  506.     # special case for list of elements
  507.     elif Length(arg) = 1  and IsList(arg[1])  then
  508.         D := Domain( arg[1] );
  509.         F := D.operations.Field( arg[1] );
  510.  
  511.     # other cases
  512.     else
  513.         D := Domain( arg );
  514.         F := D.operations.Field( arg );
  515.     fi;
  516.  
  517.     # return the field
  518.     return F;
  519. end;
  520.  
  521. FieldElementsOps.Field := function ( arg )
  522.     Error("sorry, there is no default way to construct a field");
  523. end;
  524.  
  525.  
  526. #############################################################################
  527. ##
  528. #F  DefaultField(<z>,...) . . . . default field containing a list of elements
  529. ##
  530. DefaultField := function ( arg )
  531.     local   F,          # field containing the elements of <arg>, result
  532.             D;          # domain containing the elements of <arg>
  533.  
  534.     # special case for one square matrix
  535.     if    Length(arg) = 1
  536.         and IsMat(arg[1])  and Length(arg[1]) = Length(arg[1][1])
  537.     then
  538.         D := Domain( arg );
  539.         F := D.operations.DefaultField( arg );
  540.  
  541.     # special case for list of elements
  542.     elif Length(arg) = 1  and IsList(arg[1])  then
  543.         D := Domain( arg[1] );
  544.         F := D.operations.DefaultField( arg[1] );
  545.  
  546.     # other cases
  547.     else
  548.         D := Domain( arg );
  549.         F := D.operations.DefaultField( arg );
  550.     fi;
  551.  
  552.     # return the default field
  553.     return F;
  554. end;
  555.  
  556. FieldElementsOps.DefaultField := function ( arg )
  557.     Error("sorry, there is no default way to construct a default field");
  558. end;
  559.  
  560.  
  561. #############################################################################
  562. ##
  563. #F  FieldOps.Polynomial( <R>, <coeffs>, <val> )    .  polynomial over a ring <R>
  564. ##
  565. FieldOps.Polynomial := function( R, coeffs, val )
  566.     local  i,  k,  l,  c;
  567.  
  568.     # remove leading zeros
  569.     k := Length( coeffs );
  570.     while 0 < k and coeffs[k] = R.zero  do
  571.         k := k - 1;
  572.     od;
  573.  
  574.     # remove trailing zeros
  575.     i := 0;
  576.     while i < k and coeffs[i+1] = R.zero  do
  577.     i := i + 1;
  578.     od;
  579.  
  580.     # now really remove zeros
  581.     c := [];
  582.     for l  in [ i+1 .. k ]  do
  583.     c[l-i] := coeffs[l];
  584.     od;
  585.     if i < k  then
  586.         val := val + i;
  587.     else
  588.         val := 0;
  589.     fi;
  590.  
  591.     # is vector might fail, but we ignore this
  592.     IsVector(c);
  593.  
  594.     # return polynomial
  595.     if val < 0  then
  596.         return rec( coefficients := c,
  597.                     baseRing     := R,
  598.                     isPolynomial := true,
  599.             valuation    := val,
  600.                     domain       := LaurentPolynomials,
  601.                     operations   := PolynomialOps );
  602.     else
  603.         return rec( coefficients := c,
  604.                     baseRing     := R,
  605.                     isPolynomial := true,
  606.             valuation    := val,
  607.                     domain       := Polynomials,
  608.                     operations   := PolynomialOps );
  609.     fi;
  610.  
  611. end;
  612.  
  613.  
  614. #############################################################################
  615. ##
  616. #F  FieldOps.PolynomialRing( <R> )  . . . . . . . . . .  full polynomial ring
  617. ##
  618. FieldOps.PolynomialRing := function( F )
  619.     local   P;
  620.  
  621.     # construct a new ring domain
  622.     P := rec();
  623.     P.isDomain := true;
  624.     P.isRing   := true;
  625.  
  626.     # show that this a polynomial ring
  627.     P.isPolynomialRing := true;
  628.  
  629.     # set known properties
  630.     P.isFinite := false;
  631.     P.size     := "infinity";
  632.  
  633.     # add known properties of polynom ring over a field
  634.     P.isCommutativeRing         := true;
  635.     P.isIntegralRing            := true;
  636.     P.isUniqueFactorizationRing := true;
  637.     P.isEuclideanRing           := true;
  638.  
  639.     # set one and zero
  640.     P.one  := Polynomial( F, [ F.one ] );
  641.     P.zero := Polynomial( F, [] );
  642.  
  643.     # 'P.baseRing' contains <R>
  644.     P.baseRing := F;
  645.  
  646.     # set operations record and return
  647.     P.operations := PolynomialRingOps;
  648.     return P;
  649.  
  650. end;
  651.  
  652.  
  653. #############################################################################
  654. ##
  655. #F  FieldOps.LaurentPolynomialRing( <F> ) . . .  full Laurent polynomial ring
  656. ##
  657. FieldOps.LaurentPolynomialRing := function( F )
  658.     local   P;
  659.  
  660.     # construct a new ring domain
  661.     P := rec();
  662.     P.isDomain := true;
  663.     P.isRing   := true;
  664.  
  665.     # show that this a Laurent polynomial ring
  666.     P.isLaurentPolynomialRing := true;
  667.  
  668.     # set known properties
  669.     P.isFinite := false;
  670.     P.size     := "infinity";
  671.  
  672.     # add properties of laurent polynom ring over a field
  673.     P.isCommutativeRing         := true;
  674.     P.isIntegralRing            := true;
  675.     P.isUniqueFactorizationRing := true;
  676.     P.isEuclideanRing           := true;
  677.  
  678.     # set one and zero
  679.     P.one  := Polynomial( F, [ F.one ] );
  680.     P.zero := Polynomial( F, [] );
  681.  
  682.     # 'P.baseRing' contains <F>
  683.     P.baseRing := F;
  684.  
  685.     # set operations record and return
  686.     P.operations := FieldLaurentPolynomialRingOps;
  687.     return P;
  688.  
  689. end;
  690.  
  691.  
  692. #############################################################################
  693. ##
  694. #F  FieldOps.Indeterminate( <F> ) . . . . . . . .  indeterminate over a field
  695. ##
  696. FieldOps.Indeterminate := function( F )
  697.     return Polynomial( F, [ F.zero, F.one ] );
  698. end;
  699.  
  700.  
  701. #############################################################################
  702. ##
  703. #F  IsFieldHomomorphism(<fun>)  .  test if a function is a field homomorphism
  704. ##
  705. IsFieldHomomorphism := function ( fun )
  706.     if not IsBound( fun.isFieldHomomorphism )  then
  707.         fun.isFieldHomomorphism := fun.operations.IsFieldHomomorphism( fun );
  708.     fi;
  709.     return fun.isFieldHomomorphism;
  710. end;
  711.  
  712.  
  713. #############################################################################
  714. ##
  715. #F  FieldOps.IsHomomorphism(<fun>) test if a function is a field homomorphism
  716. ##
  717. FieldOps.IsHomomorphism := IsFieldHomomorphism;
  718.  
  719.  
  720. #############################################################################
  721. ##
  722. #F  MappingOps.IsFieldHomomorphism(<fun>) . . . test if a function is a field
  723. #F                                                               homomorphism
  724. ##
  725. MappingOps.IsFieldHomomorphism := function ( fun )
  726.     local   isHom;      # 'true' if <fun> is a homomorphism, result
  727.  
  728.     # check that <fun> is a function
  729.     if not IsMapping( fun )  then
  730.         Error("<fun> must be a single valued mapping");
  731.     fi;
  732.  
  733.     # test that source and range are fields
  734.     if not IsField( fun.source )  then
  735.         Error("'<fun>.source' must be a field");
  736.     fi;
  737.     if not IsField( fun.range )  then
  738.         Error("'<fun>.range' must be a field");
  739.     fi;
  740.  
  741.     # test the linearity explicitely if the source is finite
  742.     if IsFinite( fun.source )  then
  743.         isHom := ForAll( Elements(fun.source),
  744.                         x -> ForAll( Elements(fun.source),
  745.                                   y -> Image( fun, x * y )
  746.                                      = Image( fun, x ) * Image( fun, y )
  747.                                    and Image( fun, x + y )
  748.                                      = Image( fun, x ) + Image( fun, y ) ) );
  749.  
  750.     # otherwise give up
  751.     else
  752.         Error("sorry, can not test if <fun> is a hom., infinite source");
  753.     fi;
  754.  
  755.     # return the result
  756.     return isHom;
  757. end;
  758.  
  759.  
  760. #############################################################################
  761. ##
  762. #F  KernelFieldHomomorphism(<fun>)  . . . . .  kernel of a field homomorphism
  763. ##
  764. KernelFieldHomomorphism := function ( fun )
  765.     if not IsBound( fun.kernelFieldHomomorphism )  then
  766.         fun.kernelFieldHomomorphism
  767.             := fun.operations.KernelFieldHomomorphism(fun);
  768.     fi;
  769.     return fun.kernelFieldHomomorphism;
  770. end;
  771.  
  772.  
  773. #############################################################################
  774. ##
  775. #F  FieldOps.Kernel(<fun>)  . . . . . . . . .  kernel of a field homomorphism
  776. ##
  777. FieldOps.Kernel := KernelFieldHomomorphism;
  778.  
  779.  
  780. #############################################################################
  781. ##
  782. #F  MappingOps.KernelFieldHomomorphism(<hom>)  kernel of a field homomorphism
  783. ##
  784. MappingOps.KernelFieldHomomorphism := function ( hom )
  785.  
  786.     # check that <hom> is a homomorphism
  787.     if not IsHomomorphism(hom)  then
  788.         Error("<hom> must be a homomorphism");
  789.     fi;
  790.  
  791.     # return the kernel
  792.     return [ hom.source.zero ];
  793. end;
  794.  
  795.  
  796. #############################################################################
  797. ##
  798. #F  FieldHomomorphismOps  . . . . . operations record for field homomorphisms
  799. ##
  800. FieldHomomorphismOps := Copy( MappingOps );
  801.  
  802.  
  803. #############################################################################
  804. ##
  805. #F  FieldHomomorphismOps.IsInjective(<hom>) . . . . .  test if a homomorphism
  806. #F                                                               is injective
  807. ##
  808. FieldHomomorphismOps.IsInjective := function ( hom )
  809.     return true;
  810. end;
  811.  
  812.  
  813. #############################################################################
  814. ##
  815. #F  FieldHomomorphismOps.IsSurjective(<hom>)  . . . .  test if a homomorphism
  816. #F                                                              is surjective
  817. ##
  818. FieldHomomorphismOps.IsSurjective := function ( hom )
  819.     return Size( hom.range ) = Size( Image( hom ) );
  820. end;
  821.  
  822.  
  823. #############################################################################
  824. ##
  825. #F  FieldHomomorphismOps.IsFieldHomomorphism(<hom>) . . . . . . . always true
  826. ##
  827. FieldHomomorphismOps.IsFieldHomomorphism := function ( hom )
  828.     return true;
  829. end;
  830.  
  831.  
  832. #############################################################################
  833. ##
  834. #F  FieldHomomorphismOps.\=(<hom1>,<hom2>) . . . comparison of homomorphisms
  835. ##
  836. FieldHomomorphismOps.\= := function ( hom1, hom2 )
  837.     local   isEql;
  838.  
  839.     # if <hom1> is a homomorphisms
  840.     if IsHomomorphism( hom1 )  then
  841.  
  842.         # and if <hom2> is a homomorphisms
  843.         if IsHomomorphism( hom2 )  then
  844.  
  845.             # maybe the properties we already know determine the result
  846.             if (IsBound(hom1.isInjective) and IsBound(hom2.isInjective)
  847.                 and hom1.isInjective <> hom2.isInjective)
  848.             or (IsBound(hom1.isSurjective) and IsBound(hom2.isSurjective)
  849.                 and hom1.isSurjective <> hom2.isSurjective)
  850.             then
  851.                 isEql := false;
  852.  
  853.             # otherwise we must really test the equality
  854.             else
  855.                 isEql := hom1.source = hom2.source
  856.                     and hom1.range  = hom2.range
  857.                     and ForAll( hom1.source.generators,
  858.                            elm -> Image(hom1,elm) = Image(hom2,elm) );
  859.             fi;
  860.  
  861.         # a homomorphism and an object of another type are never equal
  862.         else
  863.             isEql := false;
  864.         fi;
  865.  
  866.     # if <hom1> is not a homomorphism
  867.     else
  868.  
  869.         # a homomorphism and an object of another type are never equal
  870.         if IsHomomorphism( hom2 )  then
  871.             isEql := false;
  872.  
  873.         # at least one argument must be a mapping
  874.         else
  875.             Error("panic, either <hom1> or <hom2> must be a mapping");
  876.         fi;
  877.  
  878.     fi;
  879.  
  880.     # return the result
  881.     return isEql;
  882. end;
  883.  
  884.  
  885. #############################################################################
  886. ##
  887. #F  FieldHomomorphismOps.ImagesSet(<hom>,<elms>)  images of a set under a hom
  888. ##
  889. FieldHomomorphismOps.ImagesSet := function ( hom, elms )
  890.     if IsField( elms )  and IsSubset( hom.source, elms )  then
  891.         return Field( List( elms.generators, gen -> Image( hom, gen ) ) );
  892.     else
  893.         return MappingOps.ImagesSet( hom, elms );
  894.     fi;
  895. end;
  896.  
  897.  
  898. #############################################################################
  899. ##
  900. #F  FieldHomomorphismOps.PreImagesElm(<hom>,<elm>)  . . .  preimage of an elm
  901. ##
  902. FieldHomomorphismOps.PreImagesElm := function ( hom, elm )
  903.     return [ PreImagesRepresentative( hom, elm ) ];
  904. end;
  905.  
  906.  
  907. #############################################################################
  908. ##
  909. #F  FieldHomomorphismOps.PreImagesSet(<hom>,<elm>)  . . . . preimage of a set
  910. ##
  911. FieldHomomorphismOps.PreImagesSet := function ( hom, elms )
  912.     if IsField( elms )  and IsSubset( hom.range, elms )  then
  913.         return Field( List( elms.generators,
  914.                             gen -> PreImagesRepresentative( hom, gen ) ) );
  915.     else
  916.         return MappingOps.PreImagesSet( hom, elms );
  917.     fi;
  918. end;
  919.  
  920.  
  921. #############################################################################
  922. ##
  923. #F  FieldHomomorphismOps.CompositionMapping(<map1>,<map2>)composition of homs
  924. ##
  925. FieldHomomorphismOps.CompositionMapping := function ( map1, map2 )
  926.     local   com;        # composition of <map1> and <map2>, result
  927.  
  928.     # handle the composition of two homomorphisms
  929.     if IsFieldHomomorphism( map1 )  and IsFieldHomomorphism( map2 )  then
  930.  
  931.         # make the mapping record
  932.         com := rec();
  933.         com.isGeneralMapping := true;
  934.  
  935.         # enter the source and the range
  936.         com.source          := map2.source;
  937.         com.range           := map1.range;
  938.  
  939.         # maybe we know that the mapping is a function
  940.         com.isMapping       := true;
  941.         com.isHomomorphism  := true;
  942.  
  943.         # enter the identifying information
  944.         com.map1            := map1;
  945.         com.map2            := map2;
  946.  
  947.         # enter the operations record
  948.         com.operations      := CompositionFieldHomomorphismOps;
  949.  
  950.     # handle other mappings
  951.     else
  952.  
  953.         com := MappingOps.CompositionMapping( map1, map2 );
  954.  
  955.     fi;
  956.  
  957.     # return the composition
  958.     return com;
  959. end;
  960.  
  961. CompositionFieldHomomorphismOps := Copy( CompositionMappingOps );
  962.  
  963. CompositionFieldHomomorphismOps.IsInjective :=
  964.            FieldHomomorphismOps.IsInjective;
  965.  
  966. CompositionFieldHomomorphismOps.IsSurjective :=
  967.            FieldHomomorphismOps.IsSurjective;
  968.  
  969. CompositionFieldHomomorphismOps.IsFieldHomomorphism :=
  970.            FieldHomomorphismOps.IsFieldHomomorphism;
  971.  
  972. CompositionFieldHomomorphismOps.\= :=
  973.            FieldHomomorphismOps.\=;
  974.  
  975. CompositionFieldHomomorphismOps.ImageElm := function ( com, elm )
  976.     return com.map1.operations.ImageElm( com.map1,
  977.                com.map2.operations.ImageElm( com.map2,
  978.                    elm ) );
  979. end;
  980.  
  981. CompositionFieldHomomorphismOps.PreImagesElm :=
  982.            FieldHomomorphismOps.PreImagesElm;
  983.  
  984. CompositionFieldHomomorphismOps.KernelFieldHomomorphism := function ( com )
  985.     return [ com.map2.source.zero ];
  986. end;
  987.  
  988. CompositionFieldHomomorphismOps.Print := function ( com )
  989.     Print( "(", com.map2, " * ", com.map1, ")" );
  990. end;
  991.  
  992.  
  993. #############################################################################
  994. ##
  995. #F  FieldOps.IdentityMapping(<G>) . . . . . . . . identity mapping on a field
  996. ##
  997. FieldOps.IdentityMapping := function ( G )
  998.     local   id;         # identity mapping on <G>, result
  999.  
  1000.     # make the mapping
  1001.     id := rec();
  1002.     id.isGeneralMapping         := true;
  1003.  
  1004.     # enter the identification
  1005.     id.isIdentity               := true;
  1006.     id.source                   := G;
  1007.     id.range                    := G;
  1008.  
  1009.     # enter usefull information
  1010.     id.isMapping                := true;
  1011.     id.isInjective              := true;
  1012.     id.isSurjective             := true;
  1013.     id.isFieldHomomorphism      := true;
  1014.     id.image                    := G;
  1015.     id.preImage                 := G;
  1016.  
  1017.     # enter the operations record
  1018.     id.operations               := IdentityFieldHomomorphismOps;
  1019.  
  1020.     # return the mapping
  1021.     return id;
  1022. end;
  1023.  
  1024. IdentityFieldHomomorphismOps := Copy( MappingOps );
  1025.  
  1026. IdentityFieldHomomorphismOps.ImageElm := function ( id, elm )
  1027.     return elm;
  1028. end;
  1029.  
  1030. IdentityFieldHomomorphismOps.ImagesElm := function ( id, elm )
  1031.     return [ elm ];
  1032. end;
  1033.  
  1034. IdentityFieldHomomorphismOps.ImagesSet := function ( id, elms )
  1035.     return elms;
  1036. end;
  1037.  
  1038. IdentityFieldHomomorphismOps.PreImageElm := function ( id, elm )
  1039.     return elm;
  1040. end;
  1041.  
  1042. IdentityFieldHomomorphismOps.PreImagesElm := function ( id, elm )
  1043.     return [ elm ];
  1044. end;
  1045.  
  1046. IdentityFieldHomomorphismOps.PreImagesSet := function ( id, elms )
  1047.     return elms;
  1048. end;
  1049.  
  1050. IdentityFieldHomomorphismOps.\= := FieldHomomorphismOps.\=;
  1051.  
  1052. IdentityFieldHomomorphismOps.\< := FieldHomomorphismOps.\<;
  1053.  
  1054. IdentityFieldHomomorphismOps.CompositionMapping := function ( map1, map2 )
  1055.     if IsBound( map1.isIdentity )  then
  1056.         return map2;
  1057.     elif IsBound( map2.isIdentity )  then
  1058.         return map1;
  1059.     else
  1060.         Error("panic, neither <map1> nor <map2> is the identity");
  1061.     fi;
  1062. end;
  1063.  
  1064. IdentityFieldHomomorphismOps.InverseMapping := function ( id )
  1065.     return id;
  1066. end;
  1067.  
  1068. IdentityFieldHomomorphismOps.Print := function ( id )
  1069.     Print("IdentityMapping( ",id.source," )");
  1070. end;
  1071.  
  1072.  
  1073. #############################################################################
  1074. ##
  1075. #E  Emacs . . . . . . . . . . . . . . . . . . . . . . . local emacs variables
  1076. ##
  1077. ##  Local Variables:
  1078. ##  mode:               outline
  1079. ##  outline-regexp:     "#F\\|#V\\|#E"
  1080. ##  fill-column:        73
  1081. ##  fill-prefix:        "##  "
  1082. ##  eval:               (hide-body)
  1083. ##  End:
  1084. ##
  1085.  
  1086.  
  1087.  
  1088.