home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / doc / ring.tex < prev    next >
Encoding:
Text File  |  1993-05-05  |  36.1 KB  |  921 lines
  1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  2. %%
  3. %A  ring.tex                    GAP documentation            Martin Schoenert
  4. %%
  5. %A  @(#)$Id: ring.tex,v 3.7 1993/02/19 10:48:42 gap Exp $
  6. %%
  7. %Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. %%
  9. %%  This file describes the polymorphic functions for rings.
  10. %%
  11. %H  $Log: ring.tex,v $
  12. %H  Revision 3.7  1993/02/19  10:48:42  gap
  13. %H  adjustments in line length and spelling
  14. %H
  15. %H  Revision 3.6  1993/02/15  10:15:08  felsch
  16. %H  more examples fixed
  17. %H
  18. %H  Revision 3.5  1993/02/12  17:20:54  felsch
  19. %H  examples adjusted to line length 72
  20. %H
  21. %H  Revision 3.4  1992/04/06  15:03:15  martin
  22. %H  fixed some more typos
  23. %H
  24. %H  Revision 3.3  1992/04/06  00:10:10  martin
  25. %H  removed the chapter about polynomials
  26. %H
  27. %H  Revision 3.2  1992/03/11  16:06:31  sam
  28. %H  renamed chapter "Number Fields" to "Subfields of Cyclotomic Fields"
  29. %H
  30. %H  Revision 3.1  1992/03/11  09:28:07  martin
  31. %H  added an example of a ring record
  32. %H
  33. %H  Revision 3.0  1991/12/27  16:10:27  martin
  34. %H  initial revision under RCS
  35. %H
  36. %%
  37. \Chapter{Rings}
  38.  
  39. Rings are important algebraic  domains.  Mathematically a *ring* is a set
  40. $R$ with two operations  '+' and '\*' called addition and multiplication.
  41. $(R,+)$ must  be an abelian group.  The  identity of this group is called
  42. $0_R$.   $(R-\{0_R\},\*)$  must be  a  monoid.   If  this  monoid has  an
  43. identity element it is called $1_R$.
  44.  
  45. Important examples  of  rings   are the  integers (see "Integers"),   the
  46. Gaussian  integers (see "Gaussians"), the integers of  a cyclotomic field
  47. (see "Subfields of Cyclotomic Fields"), and matrices (see "Matrices").
  48.  
  49. This chapter contains sections that describe how to test whether a domain
  50. is  a  ring (see "IsRing"), and how to find the smallest and  the default
  51. ring in which a list of elements lies (see "Ring" and "DefaultRing").
  52.  
  53. The next  sections describe the  operations  applicable  to ring elements
  54. (see  "Comparisons of  Ring  Elements", "Operations for Ring   Elements",
  55. "Quotient").
  56.  
  57. The  next sections describe  the functions that test whether a  ring  has
  58. certain      properties      ("IsCommutativeRing",      "IsIntegralRing",
  59. "IsUniqueFactorizationRing", and "IsEuclideanRing").
  60.  
  61. The next sections describe functions that  are related to  the units of a
  62. ring  (see  "IsUnit", "Units",   "IsAssociated", "StandardAssociate", and
  63. "Associates").
  64.  
  65. Then come the  sections  that describe the functions that   deal with the
  66. irreducible and prime elements of a ring (see "IsIrreducible", "IsPrime",
  67. and "Factors").
  68.  
  69. Then come the sections that describe the functions that are applicable to
  70. elements   of  rings  (see   "EuclideanDegree",   "Mod",   "QuotientMod",
  71. "PowerMod", "Gcd", "GcdRepresentation", "Lcm").
  72.  
  73. The  last section describes  how ring records  are represented internally
  74. (see "Ring Records").
  75.  
  76. Because  rings are  a category of  domains  all  functions  applicable to
  77. domains are also applicable to rings (see chapter "Domains") .
  78.  
  79. All functions described in this chapter are in 'LIBNAME/\"ring.g\"'.
  80.  
  81. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  82. \Section{IsRing}
  83.  
  84. 'IsRing( <domain> )'
  85.  
  86. 'IsRing'  returns  'true' if  the  object  <domain>   is  a ring  record,
  87. representing a ring (see "Ring Records"), and 'false' otherwise.
  88.  
  89. More precisely  'IsRing'  tests whether <domain>  is a ring  record  (see
  90. "Ring Records").   So for example a  matrix group may in fact  be a ring,
  91. yet 'IsRing' would return 'false'.
  92.  
  93. |    gap> IsRing( Integers );
  94.     true
  95.     gap> IsRing( Rationals );
  96.     false    # 'Rationals' is a field record not a ring record
  97.     gap> IsRing( rec( isDomain := true, isRing := true ) );
  98.     true    # it is possible to fool 'IsRing' |
  99.  
  100. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  101. \Section{Ring}
  102.  
  103. 'Ring( <r>, <s>... )'\\
  104. 'Ring( <list> )'
  105.  
  106. In the first form 'Ring' returns the smallest ring  that contains all the
  107. elements <r>, <s>... etc.  In the second form 'Ring' returns the smallest
  108. ring that contains all the  elements in the list <list>.   If any element
  109. is not an element of a ring or if the elements  lie in no  common ring an
  110. error is raised.
  111.  
  112. |    gap> Ring( 1, -1 );
  113.     Integers
  114.     gap> Ring( [10..20] );
  115.     Integers |
  116.  
  117. 'Ring' differs from 'DefaultRing' (see "DefaultRing") in  that it returns
  118. the  smallest  ring in which  the elements  lie, while 'DefaultRing'  may
  119. return a larger ring if that makes sense.
  120.  
  121. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  122. \Section{DefaultRing}
  123.  
  124. 'DefaultRing( <r>, <s>... )' \\
  125. 'DefaultRing( <list> )'
  126.  
  127. In the  first form 'DefaultRing' returns the  default  ring that contains
  128. all  the elements  <r>,  <s>...  etc.   In the  second form 'DefaultRing'
  129. returns  the default  ring that contains all  the elements  in  the  list
  130. <list>.  If any element  is not an element of a ring or  if  the elements
  131. lie in no common ring an error is raised.
  132.  
  133. The ring returned by 'DefaultRing' need not be the smallest ring in which
  134. the  elements  lie.  For   example   for elements from  cyclotomic fields
  135. 'DefaultRing' may return the ring of integers of  the smallest cyclotomic
  136. field  in which the elements  lie,  which need not  be  the smallest ring
  137. overall, because the elements may in  fact lie in  a smaller number field
  138. which is not a cyclotomic field.
  139.  
  140. For  the  exact  definition of  the  default  ring  of a certain type  of
  141. elements read the chapter describing this type.
  142.  
  143. 'DefaultRing' is used by  the ring functions like  'Quotient', 'IsPrime',
  144. 'Factors', or 'Gcd' if no explicit ring is given.
  145.  
  146. |    gap> DefaultRing( 1, -1 );
  147.     Integers
  148.     gap> DefaultRing( [10..20] );
  149.     Integers |
  150.  
  151. 'Ring' (see "Ring") differs  from 'DefaultRing' in   that it  returns the
  152. smallest ring in which the elements lie, while 'DefaultRing' may return a
  153. larger ring if that makes sense.
  154.  
  155. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  156. \Section{Comparisons of Ring Elements}
  157.  
  158. '<r> =   <s>' \\
  159. '<r> \<> <s>'
  160.  
  161. The equality operator '=' evaluates to 'true' if  the  two  ring elements
  162. <r> and <s> are equal, and to 'false' otherwise.  The inequality operator
  163. '\<>' evaluates to 'true' if the two ring  elements <r> and <s>  are  not
  164. equal, and to 'false' otherwise.   Note that any two ring elements can be
  165. compared, even if they do not lie in compatible rings.  In this case they
  166. can, of course, never  be  equal.  For each type of rings the equality of
  167. those ring elements is given in the respective chapter.
  168.  
  169. Ring  elements can  also be  compared with  objects of other  types.   Of
  170. course they are never equal.
  171.  
  172. '<r> \<\ <s>' \\
  173. '<r> \<= <s>' \\
  174. '<r> >   <s>' \\
  175. '<r> >=  <s>'
  176.  
  177. The operators '\<', '\<=', '>', and  '>=' evaluate  to 'true' if the ring
  178. element <r> is less than, less than or equal to, greater than, or greater
  179. than or equal  to the  ring  element <s>, and to  'false' otherwise.  For
  180. each type of rings the definition of the ordering  of those ring elements
  181. is given in the respective chapter.  The ordering  of ring elements is as
  182. follows.  Rationals  are  smallest,  next are  cyclotomics,  followed  by
  183. finite ring elements.
  184.  
  185. Ring elements can also be compared with objects of other types.  They are
  186. smaller than everything else.
  187.  
  188. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  189. \Section{Operations for Ring Elements}
  190.  
  191. The following  operations   are always available  for ring  elements.  Of
  192. course the operands must lie in compatible rings, i.e., the rings must be
  193. equal, or at least have a common superring.
  194.  
  195. '<r> + <s>'
  196.  
  197. The operator '+' evaluates to  the sum of  the two ring elements <r> and
  198. <s>, which must lie in compatible rings.
  199.  
  200. '<r> - <s>'
  201.  
  202. The operator  '-'  evaluates to the difference of  the two ring elements
  203. <r> and <s>, which must lie in compatible rings.
  204.  
  205. '<r> \*\ <s>'
  206.  
  207. The operator '\*' evaluates to the product  of the two ring elements <r>
  208. and <s>, which must lie in compatible rings.
  209.  
  210. '<r> \^\ <n>'
  211.  
  212. The operator '\^' evaluates to the <n>-th power of the ring element <r>.
  213. If <n> is a  positive  integer  than  '<r>\^<n>'  is  '<r>\*<r>\*..\*<r>'
  214. (<n> factors).  If <n> is a negative integer  '<r>\^<n>'  is  defined  as
  215. $1 / {<r>^{-<n>}}$.   If 0 is  raised  to  a negative power   an error is
  216. signalled.  Any ring element, even 0, raised to the 0-th power yields 1.
  217.  
  218. For the precedence of the operators see "Operations".
  219.  
  220. Note that the quotient operator '/' usually performs  the division in the
  221. quotient  field of the  ring.  To compute a quotient   in  a ring use the
  222. function 'Quotient' (see "Quotient").
  223.  
  224. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  225. \Section{Quotient}
  226.  
  227. 'Quotient( <r>, <s> )' \\
  228. 'Quotient( <R>, <r>, <s> )'
  229.  
  230. In  the first  form  'Quotient'  returns  the quotient  of  the  two ring
  231. elements <r> and <s> in  their default ring  (see "DefaultRing").  In the
  232. second form 'Quotient' returns the quotient of the  two ring elements <r>
  233. and  <s> in the  ring <R>.  It  returns 'false' if the quotient  does not
  234. exist.
  235.  
  236. |    gap> Quotient( 4, 2 );
  237.     2
  238.     gap> Quotient( Integers, 3, 2 );
  239.     false |
  240.  
  241. 'Quotient'  calls '<R>.operations.Quotient( <R>,  <r>, <s> )' and returns
  242. the value.
  243.  
  244. The default function called  this  way is 'RingOps.Quotient',  which just
  245. signals an error,  because  there is  no generic method  to  compute  the
  246. quotient  of two ring elements.  Thus  special categories of  rings  must
  247. overlay this default function with other functions.
  248.  
  249. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  250. \Section{IsCommutativeRing}
  251.  
  252. 'IsCommutativeRing( <R> )'
  253.  
  254. 'IsCommutativeRing' returns 'true' if   the ring  <R> is  commutative and
  255. 'false' otherwise.
  256.  
  257. A ring $R$ is called *commutative* if for all elements $r$ and $s$ of $R$
  258. we have $r s = s r$.
  259.  
  260. |    gap> IsCommutativeRing( Integers );
  261.     true |
  262.  
  263. 'IsCommutativeRing'  first tests whether the flag '<R>.isCommutativeRing'
  264. is  bound.  If the flag is bound,  it returns this value.   Otherwise  it
  265. calls '<R>.operations.IsCommutativeRing(  <R> )', remembers  the returned
  266. value in '<R>.isCommutativeRing', and returns it.
  267.  
  268. The  default  function called  this  way is  'RingOps.IsCommutativeRing',
  269. which  tests  whether  all  the  generators   commute  if  the  component
  270. '<R>.generators'  is  bound,  and  tests  whether  all  elements  commute
  271. otherwise,  unless <R>  is infinite.   This function is seldom  overlaid,
  272. because most rings already have the flag bound.
  273.  
  274. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  275. \Section{IsIntegralRing}
  276.  
  277. 'IsIntegralRing( <R> )'
  278.  
  279. 'IsIntegeralRing' returns 'true' if the ring <R>  is integral and 'false'
  280. otherwise.
  281.  
  282. A ring $R$ is  called *integral* if it  is   commutative and if  for  all
  283. elements $r$ and $s$ of $R$ we have $r s = 0_R$  implies  that either $r$
  284. or $s$ is $0_R$.
  285.  
  286. |    gap> IsIntegralRing( Integers );
  287.     true |
  288.  
  289. 'IsIntegralRing'  first tests whether  the  flag  '<R>.isIntegralRing' is
  290. bound.  If the flag is bound, it returns  this value.  Otherwise it calls
  291. '<R>.operations.IsIntegralRing( <R> )',  remembers the returned value  in
  292. '<R>.isIntegralRing', and returns it.
  293.  
  294. The default function called this  way is  'RingOps.IsIntegralRing', which
  295. tests  whether the product of each pair of nonzero elements is unequal to
  296. zero, unless <R> is infinite.  This function is  seldom overlaid, because
  297. most rings already have the flag bound.
  298.  
  299. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  300. \Section{IsUniqueFactorizationRing}
  301.  
  302. 'IsUniqueFactorizationRing( <R> )'
  303.  
  304. 'IsUniqueFactorizationRing'    returns   'true'   if  <R>  is  a   unique
  305. factorization ring and 'false' otherwise.
  306.  
  307. A ring <R> is  called a *unique factorization ring* if it is an  integral
  308. ring,  and  every element has  a  unique  factorization into  irreducible
  309. elements, i.e., a  unique representation as product  of irreducibles (see
  310. "IsIrreducible").  Unique in this context means unique up to permutations
  311. of  the factors  and  up  to multiplication of the factors by units  (see
  312. "Units").
  313.  
  314. |    gap> IsUniqueFactorizationRing( Integers );
  315.     true |
  316.  
  317. 'IsUniqueFactorizationRing' tests whether '<R>.isUniqueFactorizationRing'
  318. is bound.  If the flag is bound, it returns this value.  If this flag has
  319. no      assigned       value      it       calls       the       function
  320. '<R>.operations.IsUniqueFactorizationRing( <R> )', remembers the returned
  321. value in '<R>.isUniqueFactorizationRing', and returns it.
  322.  
  323. The      default       function      called       this       way       is
  324. 'RingOps.IsUniqueFactorizationRing', which  just signals  an error, since
  325. there  is  no  generic  method  to  test  whether  a  ring  is  a  unique
  326. factorization ring.  Special  categories of  rings thus must  either have
  327. the flag bound or overlay this default function.
  328.  
  329. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  330. \Section{IsEuclideanRing}
  331.  
  332. 'IsEuclideanRing( <R> )'
  333.  
  334. 'IsEuclideanRing' returns 'true' if the ring  <R> is a Euclidean ring and
  335. 'false' otherwise.
  336.  
  337. A ring $R$ is called a Euclidean ring if it is an integral ring and there
  338. exists a function $\delta$, called the Euclidean degree, from $R-\{0_R\}$
  339. to the nonnegative integers,  such  that for  every pair $r \in R$ and $s
  340. \in  R-\{0_R\}$ there  exists an element $q$ such  that either $r - q s =
  341. 0_R$ or $\delta(r - q s) \< \delta( s )$.  The existence of this division
  342. with remainder implies that  the Euclidean algorithm  can  be  applied to
  343. compute a greatest common divisor of two elements, which in turn  implies
  344. that $R$ is a unique factorization ring.
  345.  
  346. |    gap> IsEuclideanRing( Integers );
  347.     true |
  348.  
  349. 'IsEuclideanRing' first  tests whether the flag '<R>.isEuclideanRing'  is
  350. bound.  If the flag is bound, it returns this value.   Otherwise it calls
  351. '<R>.operations.IsEuclideanRing(  <R> )', remembers the returned value in
  352. '<R>.isEuclideanRing', and returns it.
  353.  
  354. The default function called  this way is 'RingOps.IsEuclideanRing', which
  355. just signals an  error, because there is no generic way to test whether a
  356. ring is a Euclidean ring.  This function is seldom overlaid because  most
  357. rings already have the flag bound.
  358.  
  359. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  360. \Section{IsUnit}
  361.  
  362. 'IsUnit( <r> )'\\
  363. 'IsUnit( <R>, <r> )'
  364.  
  365. In the first form  'IsUnit'  returns 'true' if the  ring element <r> is a
  366. unit in  its default  ring   (see  "DefaultRing").   In  the  second form
  367. 'IsUnit' returns 'true' if <r> is a unit in the ring <R>.
  368.  
  369. An element $r$ is called a *unit* in a ring $R$, if $r$ has an inverse in
  370. $R$.
  371.  
  372. |    gap> IsUnit( Integers, 2 );
  373.     false
  374.     gap> IsUnit( Integers, -1 );
  375.     true |
  376.  
  377. 'IsUnit' calls '<R>.operations.IsUnit( <R>, <r> )' and returns the value.
  378.  
  379. The default function called this way is 'RingOps.IsUnit', which  tries to
  380. compute the inverse of  <r> with '<R>.operations.Quotient(  <R>, <R>.one,
  381. <r>  )' and returns  'true' if  the result  is not  'false',  and 'false'
  382. otherwise.   Special categories   of rings overlay this  default function
  383. with more efficient functions.
  384.  
  385. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  386. \Section{Units}
  387.  
  388. 'Units( <R> )'
  389.  
  390. 'Units' returns the group of units of the  ring <R>.   This may either be
  391. returned as a   list  or as  a  group   described by a group record  (see
  392. "Groups").
  393.  
  394. An element $r$ is called a *unit* of a ring $R$, if $r$ has an inverse in
  395. $R$.   It is easy  to  see that the  set of  units forms a multiplicative
  396. group.
  397.  
  398. |    gap> Units( Integers );
  399.     [ -1, 1 ] |
  400.  
  401. 'Units' first  tests whether the component '<R>.units' is bound.   If the
  402. component  is  bound,  it   returns  this  value.   Otherwise  it   calls
  403. '<R>.operations.Units(  <R>   )',   remembers   the  returned  value   in
  404. '<R>.units', and returns it.
  405.  
  406. The default function called this  way is 'RingOps.Units', which runs over
  407. all elements  of  <R> and tests for each whether it is a  unit,  provided
  408. that <R> is  finite.  Special  categories  of rings overlay this  default
  409. function with more efficient functions.
  410.  
  411. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  412. \Section{IsAssociated}
  413.  
  414. 'IsAssociated( <r>, <s> )' \\
  415. 'IsAssociated( <R>, <r>, <s> )'
  416.  
  417. In the first form 'IsAssociated' returns 'true' if the  two ring elements
  418. <r> and <s> are associated in their default ring  (see "DefaultRing") and
  419. 'false' otherwise.   In the second form  'IsAssociated' returns 'true' if
  420. the two ring  elements <r> and <s> are   associated  in the ring <R>  and
  421. 'false' otherwise.
  422.  
  423. Two elements  $r$ and $s$ of a ring $R$  are called *associates* if there
  424. is a unit $u$ of $R$ such that $r u = s$.
  425.  
  426. |    gap> IsAssociated( Integers, 2, 3 );
  427.     false
  428.     gap> IsAssociated( Integers, 17, -17 );
  429.     true |
  430.  
  431. 'IsAssociated' calls '<R>.operations.IsAssociated( <R>,  <r>, <s>  )' and
  432. returns the value.
  433.  
  434. The default  function  called this  way  is 'RingOps.IsAssociated', which
  435. tries to compute  the quotient of  <r> and <s> and  returns 'true' if the
  436. quotient exists and is a unit.  Special categories of  rings overlay this
  437. default function with more efficient functions.
  438.  
  439. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  440. \Section{StandardAssociate}
  441.  
  442. 'StandardAssociate( <r> )' \\
  443. 'StandardAssociate( <R>, <r> )'
  444.  
  445. In the first form  'StandardAssociate' returns  the standard associate of
  446. the ring element  <r> in  its default  ring (see  "DefaultRing").  In the
  447. second form  'StandardAssociate'  returns  the standard  associate of the
  448. ring element <r> in the ring <R>.
  449.  
  450. The  *standard associate* of an ring  element $r$ of $R$ is an associated
  451. element of $r$ which is, in a ring dependent way, distinguished among the
  452. set  of  associates  of  $r$.  For example, in the ring  of integers  the
  453. standard associate is the absolute value.
  454.  
  455. |    gap> StandardAssociate( Integers, -17 );
  456.     17 |
  457.  
  458. 'StandardAssociate' calls '<R>.operations.StandardAssociate( <R>, <r> )'
  459. and returns the value.
  460.  
  461. The   default  function called this  way  is 'RingOps.StandardAssociate',
  462. which  just signals an error,  because there  is no  generic  way even to
  463. define the standard associate.   Thus  special categories  of rings  must
  464. overlay this default function with other functions.
  465.  
  466. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  467. \Section{Associates}
  468.  
  469. 'Associates( <r> )' \\
  470. 'Associates( <R>, <r> )'
  471.  
  472. In the first form 'Associates' returns the set of associates of the ring
  473. element <r> in its default ring (see "DefaultRing").  In the second form
  474. 'Associates' returns the set of associates of <r> in the ring <R>.
  475.  
  476. Two elements $r$ and $s$ of a ring $R$ are called *associate* if there is
  477. a unit  $u$ of  $R$ such  that $r u = s$.
  478.  
  479. |    gap> Associates( Integers, 17 );
  480.     [ -17, 17 ] |
  481.  
  482. 'Associates' calls  '<R>.operations.Associates( <R>,  <r> )' and  returns
  483. the value.
  484.  
  485. The  default function    called this way   is 'RingOps.Associates', which
  486. multiplies the set of units of <R> with the element  <r>, and returns the
  487. set of those elements.  Special categories of rings overlay  this default
  488. function with more efficient functions.
  489.  
  490. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  491. \Section{IsIrreducible}
  492.  
  493. 'IsIrreducible( <r> )'\\
  494. 'IsIrreducible( <R>, <r> )'
  495.  
  496. In the first form 'IsIrreducible' returns  'true' if the ring element <r>
  497. is irreducible in  its default  ring   (see "DefaultRing")  and   'false'
  498. otherwise.  In the second form 'IsIrreducible' returns 'true' if the ring
  499. element <r> is irreducible in the ring <R> and 'false' otherwise.
  500.  
  501. An element  $r$  of a ring  $R$ is called  *irreducible*  if  there is no
  502. nontrivial  factorization   of  $r$ in  $R$,    i.e., if  there     is no
  503. representation of $r$ as product $s t$ such that neither $s$ nor $t$ is a
  504. unit (see "IsUnit").  Each prime element (see "IsPrime") is irreducible.
  505.  
  506. |    gap> IsIrreducible( Integers, 4 );
  507.     false
  508.     gap> IsIrreducible( Integers, 3 );
  509.     true |
  510.  
  511. 'IsIrreducible'   calls '<R>.operations.IsIrreducible(   <R>,  <r> )' and
  512. returns the value.
  513.  
  514. The  default function called this  way is  'RingOps.IsIrreducible', which
  515. justs signals an error, because there is no  generic  way to test whether
  516. an element is irreducible.  Thus special categories of rings must overlay
  517. this default function with other functions.
  518.  
  519. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  520. \Section{IsPrime}
  521.  
  522. 'IsPrime( <r> )' \\
  523. 'IsPrime( <R>, <r> )'
  524.  
  525. In the first form 'IsPrime' returns 'true'  if the ring  element <r> is a
  526. prime in its default ring (see "DefaultRing") and  'false' otherwise.  In
  527. the second form 'IsPrime'  returns 'true' if  the  ring element <r>  is a
  528. prime in the ring <R> and 'false' otherwise.
  529.  
  530. An element $r$ of a ring $R$ is called *prime* if for  each pair  $s$ and
  531. $t$ such  that $r$ divides  $s t$ the element  $r$  divides either $s$ or
  532. $t$.  Note that there are rings where not every  irreducible element (see
  533. "IsIrreducible") is a prime.
  534.  
  535. |    gap> IsPrime( Integers, 4 );
  536.     false
  537.     gap> IsPrime( Integers, 3 );
  538.     true |
  539.  
  540. 'IsPrime' calls   '<R>.operations.IsPrime( <R>, <r>  )' and  returns  the
  541. value.
  542.  
  543. The  default function called this way is  'RingOps.IsPrime',  which  just
  544. signals an error,  because there is no generic  way  to test  whether  an
  545. element is  prime.  Thus special  categories  of  rings must overlay this
  546. default function with other functions.
  547.  
  548. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  549. \Section{Factors}
  550.  
  551. 'Factors( <r> )' \\
  552. 'Factors( <R>, <r> )'
  553.  
  554. In the first form 'Factors' returns the factorization of the ring element
  555. <r>  in  its default  ring  (see   "DefaultRing").   In the  second  form
  556. 'Factors' returns the factorization of the ring element  <r> in  the ring
  557. <R>.  The factorization is returned as a list of primes  (see "IsPrime").
  558. Each  element   in   the  list     is    a   standard    associate   (see
  559. "StandardAssociate") except the first one,  which is multiplied by a unit
  560. as necessary to have 'Product( Factors( <R>, <r> )  )  = <r>'.  This list
  561. is usually also sorted, thus smallest prime factors come  first.   If <r>
  562. is a unit or zero, 'Factors( <R>, <r> ) = [ <r> ]'.
  563.  
  564. |    gap> Factors( -Factorial(6) );
  565.     [ -2, 2, 2, 2, 3, 3, 5 ]
  566.     gap> Set( Factors( Factorial(13)/11 ) );
  567.     [ 2, 3, 5, 7, 13 ]
  568.     gap> Factors( 2^63 - 1 );
  569.     [ 7, 7, 73, 127, 337, 92737, 649657 ]
  570.     gap> Factors( 10^42 + 1 );
  571.     [ 29, 101, 281, 9901, 226549, 121499449, 4458192223320340849 ] |
  572.  
  573. 'Factors' calls  '<R>.operations.Factors(  <R>, <r>  )' and   returns the
  574. value.
  575.  
  576. The  default function called  this way is   'RingOps.Factors', which just
  577. signals an   error, because there    is no  generic  way to  compute  the
  578. factorization of ring elements.  Thus special categories of ring elements
  579. must overlay this default function with other functions.
  580.  
  581. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  582. \Section{EuclideanDegree}
  583.  
  584. 'EuclideanDegree( <r> )' \\
  585. 'EuclideanDegree( <R>, <r> )'
  586.  
  587. In the first form 'EuclideanDegree'  returns the Euclidean degree of  the
  588. ring  element  <r>     in  its    default  ring.  In    the   second form
  589. 'EuclideanDegree' returns the Euclidean degree of the ring element in the
  590. ring    <R>.    <R>   must   of course  be    an    Euclidean  ring  (see
  591. "IsEuclideanRing").
  592.  
  593. A  ring $R$ is called a Euclidean  ring,  if it  is an integral ring, and
  594. there exists  a function  $\delta$,  called the  Euclidean  degree,  from
  595. $R-\{0_R\}$ to the nonnegative integers, such  that for every pair $r \in
  596. R$ and $s \in R-\{0_R\}$ there exists an element $q$ such that either  $r
  597. -  q s = 0_R$ or $\delta(r - q s) \< \delta( s )$.  The existence of this
  598. division  with remainder  implies  that  the Euclidean algorithm  can  be
  599. applied to compute a greatest common divisors  of  two elements, which in
  600. turn implies that $R$ is a unique factorization ring.
  601.  
  602. |    gap> EuclideanDegree( Integers, 17 );
  603.     17
  604.     gap> EuclideanDegree( Integers, -17 );
  605.     17 |
  606.  
  607. 'EuclideanDegree' calls '<R>.operations.EuclideanDegree(  <R>, <r> )' and
  608. returns the value.
  609.  
  610. The default function called this way is  'RingOps.EuclideanDegree', which
  611. justs signals an error,  because there is no default  way  to compute the
  612. Euclidean degree  of an element.  Thus Euclidean  rings must overlay this
  613. default function with other functions.
  614.  
  615. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  616. \Section{Mod}
  617.  
  618. 'Mod( <r>, <m> )' \\
  619. 'Mod( <R>, <r>, <m> )'
  620.  
  621. In the first form  'Mod' returns the  remainder  of the  ring element <r>
  622. modulo the  ring  element <m> in their default ring.  In the second  form
  623. 'Mod' returns  the remainder  of the ring  element  <r>  modulo  the ring
  624. element <m> in the ring <R>.  The  ring <R> must be a Euclidean ring (see
  625. "IsEuclideanRing") otherwise an error is signalled.
  626.  
  627. A ring $R$ is called a Euclidean  ring, if it  is an  integral ring,  and
  628. there  exists  a function $\delta$,  called  the Euclidean  degree,  from
  629. $R-\{0_R\}$ to the  nonnegative integers, such that for every pair $r \in
  630. R$ and $s \in R-\{0_R\}$ there exists an element $q$ such that either  $r
  631. - q s = 0_R$ or  $\delta(r - q s) \< \delta( s )$.  The existence of this
  632. division with  remainder  implies  that the  Euclidean algorithm  can  be
  633. applied to compute a greatest common divisors of two  elements,  which in
  634. turn implies that $R$ is a unique factorization ring.  'Mod' returns this
  635. remainder $r - q s$.
  636.  
  637. |    gap> Mod( 16, 3 );
  638.     1
  639.     gap> Mod( Integers, 201, 11 );
  640.     3 |
  641.  
  642. 'Mod' calls '<R>.operations.Mod( <R>, <r>, <m> )' and returns the value.
  643.  
  644. The default function called this way is 'RingOps.Mod', which just signals
  645. an error, because there is  no default function  to compute the remainder
  646. of  one ring element modulo another.   Thus  Euclidean rings must overlay
  647. this default function with other functions.
  648.  
  649. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  650. \Section{QuotientMod}
  651.  
  652. 'QuotientMod( <r>, <s>, <m> )' \\
  653. 'QuotientMod( <R>, <r>, <s>, <m> )'
  654.  
  655. In the first form 'QuotientMod' returns the quotient of the ring elements
  656. <r> and <s>   modulo the  ring  element <m>  in their  default  ring (see
  657. "DefaultRing").  In the second form 'QuotientMod' returns the quotient of
  658. the ring  elements <r> and  <s> modulo the ring element  <m>  in the ring
  659. <R>.  <R> must be a  Euclidean ring (see "IsEuclideanRing") so that 'Mod'
  660. (see "Mod")  can be  applied.  If the  modular quotient   does not exist,
  661. 'false' is returned.
  662.  
  663. The quotient $q$ of $r$ and $s$ modulo $m$ is an element of $R$ such that
  664. $q s = r$ modulo $m$, i.e., such that $q s - r$  is divisable  by $m$  in
  665. $R$ and  that  $q$  is  either  0 (if  $r$ is divisable  by $m$)  or  the
  666. Euclidean  degree of $q$ is strictly smaller than the Euclidean degree of
  667. $m$.
  668.  
  669. |    gap> QuotientMod( Integers, 13, 7, 11 );
  670.     5
  671.     gap> QuotientMod( Integers, 13, 7, 21 );
  672.     false |
  673.  
  674. 'QuotientMod'  calls '<R>.operations.QuotientMod( <R>,  <r>,  <s>, <m> )'
  675. and returns the value.
  676.  
  677. The  default function  called  this  way  is 'RingOps.QuotientMod', which
  678. applies the  Euclidean gcd algorithm to  compute the gcd  <g>  of <s> and
  679. <m>, together with  the  representation of this gcd as linear combination
  680. in <s> and <m>, '<g> = <a>  \*\ <s> + <b> \*\ <m>'.  The modular quotient
  681. exists if and only if <r> is divisible by <g>, in which case the quotient
  682. is '<a> \*\ Quotient( <R>, <r>, <g> )'.  This default function is  seldom
  683. overlaid, because there is seldom a better way to compute the quotient.
  684.  
  685. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  686. \Section{PowerMod}
  687.  
  688. 'PowerMod( <r>, <e>, <m> )' \\
  689. 'PowerMod( <R>, <r>, <e>, <m> )'
  690.  
  691. In the first form 'PowerMod' returns the <e>-th power of the ring element
  692. <r>     modulo  the   ring  element   <m>  in their     default ring (see
  693. "DefaultRing").  In the second  form  'PowerMod' returns the <e>-th power
  694. of the ring element <r> modulo the ring element <m> in the ring <R>.  <e>
  695. must be an integer.  <R> must be a Euclidean ring (see "IsEuclideanRing")
  696. so that 'Mod' (see "Mod") can be applied to its elements.
  697.  
  698. If $e$ is  positive the  result is $r^e$ modulo $m$.  If $e$  is negative
  699. then 'PowerMod' first tries to find the  inverse of $r$ modulo $m$, i.e.,
  700. $i$ such  that $i r  =  1$  modulo $m$.  If the inverse does not exist an
  701. error  is  signalled.   If  the  inverse  does exist  'PowerMod'  returns
  702. 'PowerMod( <R>, <i>, -<e>, <m> )'.
  703.  
  704. 'PowerMod'  reduces   the  intermediate  values  modulo   $m$,  improving
  705. performance drastically when <e> is large and <m>  small.
  706.  
  707. |    gap> PowerMod( Integers, 2, 20, 100 );
  708.     76        # $2^{20} = 1048576$
  709.     gap> PowerMod( Integers, 3, 2^32, 2^32+1 );
  710.     3029026160        # which proves that $2^{32}+1$ is not a prime
  711.     gap> PowerMod( Integers, 3, -1, 22 );
  712.     15        # 3\*15 = 45 = 1 modulo 22 |
  713.  
  714. 'PowerMod' calls  '<R>.operations.PowerMod( <R>,  <r>, <e>, <m>    )' and
  715. returns the value.
  716.  
  717. The  default function called this way is  'RingOps.PowerMod',  which uses
  718. 'QuotientMod' (see "QuotientMod")  if  necessary to  invert <r>, and then
  719. uses a right-to-left repeated squaring, reducing the intermediate results
  720. modulo <m> in each step.  This function is seldom overlaid, because there
  721. is seldom a better way of computing the power.
  722.  
  723. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  724. \Section{Gcd}
  725.  
  726. 'Gcd( <r1>, <r2>... )' \\
  727. 'Gcd( <R>, <r1>, <r2>... )'
  728.  
  729. In the first form 'Gcd' returns the greatest common  divisor  of the ring
  730. elements  <r1>, <r2>... etc.  in their default  ring (see "DefaultRing").
  731. In the second form  'Gcd' returns the greatest common divisor of the ring
  732. elements <r1>, <r2>... etc. in the  ring <R>.  <R>  must be  a  Euclidean
  733. ring (see "IsEuclideanRing") so that 'Mod' (see "Mod")  can be applied to
  734. its     elements.     'Gcd'  returns   the    standard   associate   (see
  735. "StandardAssociate") of the greatest common divisors.
  736.  
  737. A greatest common divisor of the elements  $r_1$, $r_2$...  etc.   of the
  738. ring   $R$   is   an   element   of   largest   Euclidean   degree   (see
  739. "EuclideanDegree") that is a  divisor of $r_1$,  $r_2$... etc.  We define
  740. $gcd( r, 0_R  ) = gcd( 0_R, r ) = StandardAssociate( r )$  and $gcd( 0_R,
  741. 0_R ) = 0_R$.
  742.  
  743. |    gap> Gcd( Integers, 123, 66 );
  744.     3 |
  745.  
  746. 'Gcd' calls '<R>.operations.Gcd' repeatedly, each time passing the result
  747. of the previous call and the next argument,  and returns the value of the
  748. last call.
  749.  
  750. The default function called this way  is 'RingOps.Gcd', which applies the
  751. Euclidean  algorithm to  compute the  greatest  common divisor.   Special
  752. categories  of rings overlay this  default   function with more efficient
  753. functions.
  754.  
  755. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  756. \Section{GcdRepresentation}
  757.  
  758. 'GcdRepresentation( <r1>, <r2>... )' \\
  759. 'GcdRepresentation( <R>, <r1>, <r2>... )'
  760.  
  761. In the first  form 'GcdRepresentation' returns the representation  of the
  762. greatest common divisor of the ring elements <r1>, <r2>... etc.  in their
  763. default ring (see "DefaultRing").  In the second form 'GcdRepresentation'
  764. returns  the representation of  the greatest  common  divisor of the ring
  765. elements <r1>, <r2>... etc.  in  the ring <R>.  <R>  must be a  Euclidean
  766. ring (see "IsEuclideanRing") so that 'Gcd'  (see "Gcd") can be applied to
  767. its elements.  The representation is returned as a list of ring elements.
  768.  
  769. The representation of the gcd  $g$ of  the elements $r_1$, $r_2$...  etc.
  770. of a ring $R$ is  a  list of ring  elements $s_1$,  $s_2$... etc. of $R$,
  771. such that $g = s_1 r_1 + s_2  r_2 ...$.  That this  representation exists
  772. can be shown using the  Euclidean algorithm,  which in fact  can  compute
  773. those coefficients.
  774.  
  775. |    gap> GcdRepresentation( 123, 66 );
  776.     [ 7, -13 ]    # 3 = 7\*123 - 13\*66
  777.     gap> Gcd( 123, 66 ) = last * [ 123, 66 ];
  778.     true |
  779.  
  780. 'GcdRepresentation'  calls '<R>.operations.GcdRepresentation' repeatedly,
  781. each  time  passing  the gcd result  of the previous  call  and  the next
  782. argument, and returns the value of the last call.
  783.  
  784. The default    function called  this way  is 'RingOps.GcdRepresentation',
  785. which applies the   Euclidean algorithm  to  compute the greatest  common
  786. divisor and its representation.  Special categories of rings overlay this
  787. default function with more efficient functions.
  788.  
  789. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  790. \Section{Lcm}
  791.  
  792. 'Lcm( <r1>, <r2>... )'\\
  793. 'Lcm( <R>, <r1>, <r2>... )'
  794.  
  795. In the first  form 'Lcm' returns  the  least common multiple of the  ring
  796. elements <r1>, <r2>...  etc.  in  their default ring (see "DefaultRing").
  797. In the second  form 'Lcm' returns the least  common  multiple of the ring
  798. elements <r1>, <r2>,... etc.  in the ring  <R>.  <R> must be a  Euclidean
  799. ring (see "IsEuclideanRing") so that 'Gcd' (see "Gcd") can be  applied to
  800. its    elements.    'Lcm'   returns    the   standard     associate  (see
  801. "StandardAssociate") of the least common multiples.
  802.  
  803. A least common multiple of  the elements  $r_1$, $r_2$...   etc.  of  the
  804. ring   $R$   is   an   element   of   smallest   Euclidean   degree  (see
  805. "EuclideanDegree") that is a multiple of $r_1$, $r_2$...  etc.  We define
  806. $lcm( r,  0_R ) = lcm( 0_R, r ) =  StandardAssociate( r )$ and $Lcm( 0_R,
  807. 0_R ) = 0_R$.
  808.  
  809. 'Lcm' uses the equality $lcm(m,n) = m\*n / gcd(m,n)$ (see "Gcd").
  810.  
  811. |    gap> Lcm( Integers, 123, 66 );
  812.     2706 |
  813.  
  814. 'Lcm' calls '<R>.operations.Lcm' repeatedly, each time passing the result
  815. of the previous call and the next argument,  and returns the value of the
  816. last call.
  817.  
  818. The  default  function called  this  way is 'RingOps.Lcm',  which  simply
  819. returns the  product of <r>  with the  quotient  of <s> and the  greatest
  820. common divisor of <r> and <s>.   Special categories of rings overlay this
  821. default function with more efficient functions.
  822.  
  823. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  824. \Section{Ring Records}
  825.  
  826. A ring <R> is represented by a record with the following entries.
  827.  
  828. 'isDomain':\\
  829.         is of course always the value 'true'.
  830.  
  831. 'isRing': \\
  832.         is of course always the value 'true'.
  833.  
  834. 'isCommutativeRing': \\
  835.         is 'true' if  the  multiplication  is  known to  be  commutative,
  836.         'false' if the multiplication is known  to be noncommutative, and
  837.         unbound otherwise.
  838.  
  839. 'isIntegralRing': \\
  840.         is  'true' if  <R> is  known  to be a commutative  domain  with 1
  841.         without zero divisor, 'false' if <R> is  known  to  lack  one  of
  842.         these properties, and unbound otherwise.
  843.  
  844. 'isUniqueFactorizationRing': \\
  845.         is   'true'  if <R>   is    known to be   a   domain with  unique
  846.         factorization into primes,  'false' if  <R> is   known to have  a
  847.         nonunique factorization, and unbound otherwise.
  848.  
  849. 'isEuclideanRing': \\
  850.         is 'true' if <R> is known to be a Euclidean domain, 'false' if it
  851.         is known not to be a Euclidean domain, and unbound otherwise.
  852.  
  853. 'zero': \\
  854.         is the additive neutral element.
  855.  
  856. 'units': \\
  857.         is the list of units of the ring if it is known.
  858.  
  859. 'size': \\
  860.         is the size  of the ring if it is  known.  If  the  ring  is  not
  861.         finite this is the string \"infinity\".
  862.  
  863. 'one': \\
  864.         is the  multiplicative  neutral element,  if the ring has one.
  865.  
  866. 'integralBase': \\
  867.         if the ring is,  as  additive  group, isomorphic  to  the  direct
  868.         product of a finite number of copies of $Z$ this contains a base.
  869.  
  870. As an example of a ring record, here is the definition of the ring record
  871. 'Integers'.
  872.  
  873. |    rec(
  874.  
  875.         # category components
  876.         isDomain                    := true,
  877.         isRing                      := true,
  878.  
  879.         # identity components
  880.         generators                  := [ 1 ],
  881.         zero                        := 0,
  882.         one                         := 1,
  883.         name                        := "Integers",
  884.  
  885.         # knowledge components
  886.         size                        := "infinity",
  887.         isFinite                    := false,
  888.         isCommutativeRing           := true,
  889.         isIntegralRing              := true,
  890.         isUniqueFactorizationRing   := true,
  891.         isEuclideanRing             := true,
  892.         units                       := [ -1, 1 ],
  893.  
  894.         # operations record
  895.         operations                  := rec(
  896.             ...
  897.             IsPrime                 := function ( Integers, n )
  898.                 return IsPrimeInt( n );
  899.             end,
  900.             ...
  901.             'mod'                   := function ( Integers, n, m )
  902.                 return n mod m;
  903.             end,
  904.             ... ) ) |
  905.  
  906.  
  907. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  908. %%
  909. %E  Emacs . . . . . . . . . . . . . . . . . . . . . local Emacs variables
  910. %%
  911. %%  Local Variables:
  912. %%  mode:               outline
  913. %%  outline-regexp:     "\\\\Chapter\\|\\\\Section"
  914. %%  fill-column:        73
  915. %%  eval:               (hide-body)
  916. %%  End:
  917. %%
  918.  
  919.  
  920.  
  921.