home *** CD-ROM | disk | FTP | other *** search
/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / doc / cyclotom.tex < prev    next >
Encoding:
Text File  |  1993-05-05  |  22.8 KB  |  600 lines
  1. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  2. %%
  3. %A  cyclotom.tex                GAP documentation               Thomas Breuer
  4. %%
  5. %A  @(#)$Id: cyclotom.tex,v 3.11 1993/02/19 10:48:42 gap Exp $
  6. %%
  7. %Y  Copyright 1990-1992,  Lehrstuhl D fuer Mathematik,  RWTH Aachen,  Germany
  8. %%
  9. %H  $Log: cyclotom.tex,v $
  10. %H  Revision 3.11  1993/02/19  10:48:42  gap
  11. %H  adjustments in line length and spelling
  12. %H
  13. %H  Revision 3.10  1993/02/12  15:45:43  felsch
  14. %H  more examples fixed
  15. %H
  16. %H  Revision 3.9  1993/02/01  13:16:16  felsch
  17. %H  examples fixed
  18. %H
  19. %H  Revision 3.8  1992/04/07  23:05:55  martin
  20. %H  changed the author line
  21. %H
  22. %H  Revision 3.7  1992/03/27  13:56:54  sam
  23. %H  removed "'" in index entries
  24. %H
  25. %H  Revision 3.6  1992/03/11  15:48:05  sam
  26. %H  renamed chapter "Number Fields" to "Subfields of Cyclotomic Fields"
  27. %H
  28. %H  Revision 3.5  1992/02/13  15:37:26  sam
  29. %H  renamed 'Automorphisms' to 'GaloisGroup'
  30. %H
  31. %H  Revision 3.4  1992/01/14  14:37:27  martin
  32. %H  changed an overlong line
  33. %H
  34. %H  Revision 3.3  1992/01/14  14:01:12  sam
  35. %H  adjusted citations
  36. %H
  37. %H  Revision 3.2  1991/12/30  09:37:48  martin
  38. %H  changed two section titles slightly
  39. %H
  40. %H  Revision 3.1  1991/12/30  08:07:00  sam
  41. %H  initial revision under RCS
  42. %H
  43. %%
  44. \Chapter{Cyclotomics}\index{type!cyclotomic}\index{irrationalities}
  45.  
  46. {\GAP} allows computations in abelian extension fields of the rational
  47. field  $Q$, i.e., fields with  abelian Galois group  over $Q$.   These
  48. fields  are  described  in  chapter "Subfields of Cyclotomic  Fields".
  49. They are subfields  of *cyclotomic fields* $Q_n = Q(e_n)$ where $e_n =
  50. e^{\frac{2\pi i}{n}}$  is a primitive  $n$--th root  of  unity.  Their
  51. elements are called *cyclotomics*.
  52.  
  53. The  internal representation  of a  cyclotomic  does not refer  to the
  54. smallest number field but the smallest cyclotomic  field containing it
  55. (the so--called *conductor*).  This is because it is easy to embed two
  56. cyclotomic fields in a larger one that contains both, i.e., there is a
  57. natural way to get the sum or the product of two arbitrary cyclotomics
  58. as  element  of a cyclotomic field.   The  disadvantage  is  that  the
  59. arithmetical operations are too expensive to do arithmetics  in number
  60. fields, e.g.,  calculations in a matrix ring over a number field.  But
  61. it  suffices to deal  with irrationalities  in  character  tables (see
  62. "Character Tables").  (And in fact, the comfortability of working with
  63. the natural embeddings is used  there in many situations which did not
  64. actually afford it \ldots)
  65.  
  66. All functions that take  a field  extension as ---possibly optional---
  67. argument, e.g., 'Trace' or 'Coefficients'  (see chapter "Fields"), are
  68. described in chapter "Subfields of Cyclotomic Fields".
  69.  
  70. This chapter informs about:\\
  71.     the representation of cyclotomics in {\GAP} (see
  72.        "More about Cyclotomics"),\\
  73.     access to the internal data (see "NofCyc", "CoeffsCyc")\\
  74.     integral elements of number fields (see "Cyclotomic Integers",
  75.        "IntCyc", "RoundCyc"),\\
  76.     characteristic functions (see "IsCyc", "IsCycInt"),\\
  77.     comparison and arithmetical operations of cyclotomics (see
  78.     "Comparisons of Cyclotomics", "Operations for Cyclotomics"),\\
  79.     functions concerning Galois conjugacy of cyclotomics (see "GaloisCyc",
  80.        "StarCyc"), or lists of them (see "GaloisMat", "RationalizedMat"),\\
  81.     some special cyclotomics, as defined in \cite{CCN85}
  82.        (see "ATLAS irrationalities", "Quadratic")
  83.  
  84. The external functions are in the file 'LIBNAME/\"cyclotom.g\"'.
  85.  
  86. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  87. \Section{More about Cyclotomics}\index{cyclotomic field elements}
  88. \index{E}\index{roots of unity}
  89.  
  90. Elements  of  number  fields  (see  chapter  "Subfields of  Cyclotomic
  91. Fields"),  cyclotomics  for  short,  are  arithmetical  objects   like
  92. rationals  and  finite  field  elements;  they are not implemented  as
  93. records ---like  groups--- or e.g. with respect  to a character  table
  94. (although  character  tables  may be the main  interest for cyclotomic
  95. arithmetics).
  96.  
  97. 'E( <n> )'
  98.  
  99. returns  the  primitive <n>-th  root  of unity  $e_n  =  e^{\frac{2\pi
  100. i}{n}}$.   Cyclotomics  are   usually  entered   as   (and  irrational
  101. cyclotomics  are  always displayed  as) sums of  roots of  unity  with
  102. rational   coefficients.    (For  special   cyclotomics,   see  "ATLAS
  103. irrationalities".)
  104.  
  105. |    gap> E(9); E(9)^3; E(6); E(12) / 3; 
  106.     -E(9)^4-E(9)^7    # the root needs not to be an element of the base
  107.     E(3)
  108.     -E(3)^2
  109.     -1/3*E(12)^7|
  110.  
  111. For the  representation  of  cyclotomics  one  has  to recall that the
  112. cyclotomic  field  $Q_n  =  Q(e_n)$  is a  vector  space  of dimension
  113. $\varphi(n)$  over  the rationals  where  $\varphi$  denotes  Euler\'s
  114. phi-function (see "Phi").
  115.  
  116. Note that the set  of all $n$-th  roots of unity is linearly dependent
  117. for $n > 1$, so  multiplication is not the multiplication of the group
  118. ring $Q\langle e_n \rangle$; given a $Q$-basis of $Q_n$ the  result of
  119. the  multiplication  (computed  as  multiplication of  polynomials  in
  120. $e_n$, using $(e_n)^n = 1$) will be converted to the base.
  121.  
  122. |    gap> E(5) * E(5)^2; ( E(5) + E(5)^4 ) * E(5)^2;
  123.     E(5)^3
  124.     E(5)+E(5)^3
  125.     gap> ( E(5) + E(5)^4 ) * E(5);
  126.     -E(5)-E(5)^3-E(5)^4|
  127.  
  128. Cyclotomics  are always  represented in  the smallest cyclotomic field
  129. they are contained in.  Together with  the choice of a fixed base this
  130. means that two cyclotomics are equal if and only if  they are  equally
  131. represented.
  132.  
  133. Addition  and multiplication of  two  cyclotomics represented in $Q_n$
  134. and $Q_m$, respectively,  is computed in the smallest cyclotomic field
  135. containing  both\:\ $Q_{'Lcm'(n,m)}$.  Conversely,  if  the result  is
  136. contained in a smaller cyclotomic field the representation  is reduced
  137. to the minimal such field.
  138.  
  139. The  base,  the  base conversion  and the  reduction  to  the  minimal
  140. cyclotomic field  are  described in~\cite{Zum89},  more about the base
  141. can be found in "ZumbroichBase".
  142.  
  143. Since $n$  must  be  a 'short integer',  the  maximal cyclotomic field
  144. implemented in {\GAP} is not really the  field $Q^{ab}$.  The  biggest
  145. allowed (though not very useful) $n$ is 65535.
  146.  
  147. There  is  a  global  variable 'Cyclotomics'  in {\GAP}, a record that
  148. stands for  the domain of  all  cyclotomics (see chapter "Subfields of
  149. Cyclotomic Fields").
  150.  
  151. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  152. \Section{Cyclotomic Integers}
  153.  
  154. A  cyclotomic is called  *integral*  or  *cyclotomic integer*  if  all
  155. coefficients  of its minimal  polynomial are integers. Since  the base
  156. used  is  an  integral  base  (see "ZumbroichBase"),  the  subring  of
  157. cyclotomic  integers  in  a  cyclotomic  field  is  formed   by  those
  158. cyclotomics  which have not only rational but integral coefficients in
  159. their representation as  sums of roots of unity.   For example, square
  160. roots   of   integers   are   cyclotomic    integers    (see    "ATLAS
  161. irrationalities"),  any  root  of  unity   is  a  cyclotomic  integer,
  162. character values  are always cyclotomic  integers,  but  all rationals
  163. which are not integers are not cyclotomic integers.  (See "IsCycInt")
  164.  
  165. |    gap> ER( 5 );                # The square root of 5 is a cyclotomic
  166.     E(5)-E(5)^2-E(5)^3+E(5)^4    # integer, it has integral coefficients.
  167.     gap> 1/2 * ER( 5 );          # This is not a cyclotomic integer, \ldots
  168.     1/2*E(5)-1/2*E(5)^2-1/2*E(5)^3+1/2*E(5)^4
  169.     gap> 1/2 * ER( 5 ) - 1/2;    # \ldots but this is one.
  170.     E(5)+E(5)^4|
  171.  
  172. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  173. \Section{IntCyc}
  174.  
  175. 'IntCyc( <z> )'
  176.  
  177. returns  the  cyclotomic  integer  (see  "Cyclotomic  Integers")  with
  178. Zumbroich base coefficients  (see "ZumbroichBase") 'List( <zumb>, x ->
  179. Int( x ) )' where <zumb> is the  vector of Zumbroich base coefficients
  180. of the cyclotomic <z>; see also "RoundCyc".
  181.  
  182. |    gap> IntCyc( E(5)+1/2*E(5)^2 ); IntCyc( 2/3*E(7)+3/2*E(4) );
  183.     E(5)
  184.     E(4)|
  185.  
  186. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  187. \Section{RoundCyc}
  188.  
  189. 'RoundCyc( <z> )'
  190.  
  191. returns  the  cyclotomic  integer  (see  "Cyclotomic  Integers")  with
  192. Zumbroich base coefficients (see "ZumbroichBase") 'List( <zumb>,  x ->
  193. Int(  x+1/2  )  )' where  <zumb>  is  the  vector  of  Zumbroich  base
  194. coefficients of the cyclotomic <z>; see also "IntCyc".
  195.  
  196. |    gap> RoundCyc( E(5)+1/2*E(5)^2 ); RoundCyc( 2/3*E(7)+3/2*E(4) );
  197.     E(5)+E(5)^2
  198.     -2*E(28)^3+E(28)^4-2*E(28)^11-2*E(28)^15-2*E(28)^19-2*E(28)^23
  199.      -2*E(28)^27|
  200.  
  201. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  202. \Section{IsCyc}\index{test!for a cyclotomic}
  203.  
  204. 'IsCyc( <obj> )'
  205.  
  206. returns 'true' if <obj> is a cyclotomic, and 'false'  otherwise.  Will
  207. signal an error if <obj> is an unbound variable.
  208.  
  209. |    gap> IsCyc( 0 ); IsCyc( E(3) ); IsCyc( 1/2 * E(3) ); IsCyc( IsCyc );
  210.     true
  211.     true
  212.     true
  213.     false|
  214.  
  215. 'IsCyc' is an internal function.
  216.  
  217. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  218. \Section{IsCycInt}\index{test!for a cyclotomic integer}
  219.  
  220. 'IsCycInt( <obj> )'
  221.  
  222. returns  'true'  if  <obj>  is a cyclotomic integer  (see  "Cyclotomic
  223. Integers"), 'false'  otherwise.  Will signal  an  error if <obj> is an
  224. unbound variable.
  225.  
  226. |    gap> IsCycInt( 0 ); IsCycInt( E(3) ); IsCycInt( 1/2 * E(3) );
  227.     true
  228.     true
  229.     false|
  230.  
  231. 'IsCycInt' is an internal function.
  232.  
  233. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  234. \Section{NofCyc}
  235.  
  236. 'NofCyc( <z> )'\\
  237. 'NofCyc( <list> )'
  238.  
  239. returns the smallest positive integer $n$ for which the cyclotomic <z>
  240. is resp.\ for  which all  cyclotomics in the list <list> are contained
  241. in $Q_n = Q( e^{\frac{2 \pi i}{n}} ) = Q( 'E(<n>)' )$.
  242.  
  243. |    gap> NofCyc( 0 ); NofCyc( E(10) ); NofCyc( E(12) );
  244.     1
  245.     5
  246.     12|
  247.  
  248. 'NofCyc' is an internal function.
  249.  
  250. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  251. \Section{CoeffsCyc}\index{coefficients!for cyclotomics}
  252.  
  253. 'CoeffsCyc( <z>, <n> )'
  254.  
  255. If <z> is a cyclotomic which is contained in  $Q_n$, 'CoeffsCyc(  <z>,
  256. <n> )' returns a list <cfs> of length  <n> where the entry at position
  257. <i>  is  the   coefficient   of   $'E(<n>)'^{i-1}$   in  the  internal
  258. representation  of  <z> as element  of the cyclotomic field $Q_n$ (see
  259. "More  about  Cyclotomics",  "ZumbroichBase")\:\
  260. $<z> = <cfs>[1] + <cfs>[2]\ 'E(<n>)'^1 + \ldots + <cfs>[n]\
  261. 'E(<n>)'^{n-1}$.
  262.  
  263. *Note*  that  all  positions which do not belong to  base  elements of
  264. $Q_n$ contain zeroes.
  265.  
  266. |    gap> CoeffsCyc( E(5), 5 ); CoeffsCyc( E(5), 15 );
  267.     [ 0, 1, 0, 0, 0 ]
  268.     [ 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0, -1, 0 ]
  269.     gap> CoeffsCyc( 1+E(3), 9 ); CoeffsCyc( E(5), 7 );
  270.     [ 0, 0, 0, 0, 0, 0, -1, 0, 0 ]
  271.     Error, no representation of <z> in 7th roots of unity|
  272.  
  273. 'CoeffsCyc' calls the internal function 'COEFFSCYC'\:
  274.  
  275. 'COEFFSCYC( <z> )'
  276.  
  277. is equivalent to 'CoeffsCyc( <z>, NofCyc( <z> ) )', see "NofCyc".
  278.  
  279. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  280. \Section{Comparisons of Cyclotomics}\index{operators!for cyclotomics}
  281.  
  282. To compare  cyclotomics, the operators '\<', '\<=', '=', '>=', '>' and
  283. '\<>' can  be used, the result will be  'true' if the first operand is
  284. smaller, smaller or equal, equal, larger or equal, larger, or inequal,
  285. respectively, and 'false' otherwise.
  286.  
  287. Cyclotomics are ordered as follows\:\ 
  288. The relation between rationals is as usual,  and rationals are smaller
  289. than irrational cyclotomics. For two irrational cyclotomics <z1>, <z2>
  290. which  lie in different  minimal cyclotomic  fields,  we have $<z1> \<
  291. <z2>$  if  and   only  if   $'NofCyc(<z1>)'  \<  'NofCyc(<z2>)'$);  if
  292. $'NofCyc(<z1>)'  = 'NofCyc(<z2>)'$), that one  is smaller that has the
  293. smaller coefficient vector, i.e.,  $<z1>  \leq <z2>$  if  and  only if
  294. $'COEFFSCYC(<z1>)' \leq 'COEFFSCYC(<z2>)'$.
  295.  
  296. You  can compare  cyclotomics with objects of other types; all objects
  297. which are not cyclotomics are larger than cyclotomics.
  298.  
  299. |    gap> E(5) < E(6);     # the latter value lies in $Q_3$
  300.     false
  301.     gap> E(3) < E(3)^2;    # both lie in $Q_3$, so compare coefficients
  302.     false
  303.     gap> 3 < E(3); E(5) < E(7);
  304.     true
  305.     true
  306.     gap> E(728) < (1,2);
  307.     true|
  308.  
  309. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  310. \Section{Operations for Cyclotomics}
  311. \index{operators!for cyclotomics}
  312.  
  313. The  operators '+', '-', '\*', '/' are used for addition, subtraction,
  314. multiplication and division of two cyclotomics; note that  division by
  315. 0 causes an error.
  316.  
  317. '+' and '-' can also be used as unary operators;
  318.  
  319. '\^' is used for exponentiation of a cyclotomic with an integer;
  320.      this is in general *not* equal to Galois conjugation.
  321.  
  322. |    gap> E(5) + E(3); (E(5) + E(5)^4) ^ 2; E(5) / E(3); E(5) * E(3);
  323.     -E(15)^2-2*E(15)^8-E(15)^11-E(15)^13-E(15)^14
  324.     -2*E(5)-E(5)^2-E(5)^3-2*E(5)^4
  325.     E(15)^13
  326.     E(15)^8|
  327.  
  328. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  329. \Section{GaloisCyc}\index{galois conjugation}\index{galois automorphism}
  330.  
  331. 'GaloisCyc( <z>, <k> )'
  332.  
  333. returns  the cyclotomic obtained on raising the roots  of unity in the
  334. representation of  the cyclotomic <z> to  the <k>-th power.  If <z> is
  335. represented in the  field $Q_n$ and <k>  is  a  fixed integer relative
  336. prime to <n>, 'GaloisCyc( ., <k> )'  acts as a  Galois automorphism of
  337. $Q_n$  (see   "GaloisGroup  for   Number  Fields");   to   get  Galois
  338. automorphisms as functions, use "GaloisGroup" 'GaloisGroup'.
  339.  
  340. |    gap> GaloisCyc( E(5) + E(5)^4, 2 );
  341.     E(5)^2+E(5)^3
  342.     gap> GaloisCyc( E(5), -1 );           # the complex conjugate
  343.     E(5)^4
  344.     gap> GaloisCyc( E(5) + E(5)^4, -1 );  # this value is real
  345.     E(5)+E(5)^4
  346.     gap> GaloisCyc( E(15) + E(15)^4, 3 );
  347.     E(5)+E(5)^4|
  348.  
  349. 'GaloisCyc' is an internal function.
  350.  
  351. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  352. \Section{ATLAS irrationalities}\index{$b_N$}\index{$c_N$}\index{$d_N$}
  353. \index{$e_N$}\index{$f_N$}\index{$g_N$}\index{$h_N$}\index{$i_N$}
  354. \index{$j_N$}\index{$k_N$}\index{$l_N$}\index{$m_N$}\index{$r_N$}
  355. \index{$s_N$}\index{$t_N$}\index{$u_N$}\index{$v_N$}\index{$w_N$}
  356. \index{$x_N$}\index{$y_N$}\index{$n_k$}\index{atomic irrationalities}
  357. \index{EB}\index{EC}\index{ED}\index{EE}\index{EF}\index{EG}\index{EH}
  358. \index{EI}\index{EJ}\index{EK}\index{EL}\index{EM}\index{ER}\index{ES}
  359. \index{ET}\index{EU}\index{EV}\index{EW}\index{EX}\index{EY}\index{NK}
  360.  
  361. 'EB( <N> )', 'EC( <N> )', \ldots, 'EH( <N> )',\\
  362. 'EI( <N> )', 'ER( <N> )',\\
  363. 'EJ( <N> )', 'EK( <N> )', 'EL( <N> )', 'EM( <N> )',\\
  364. 'EJ( <N>, <d> )', 'EK( <N>, <d> )', 'EL( <N>, <d> )', 'EM( <N>, <d> )',\\
  365. 'ES( <N> )', 'ET( <N> )', \ldots, 'EY( <N> )',\\
  366. 'ES( <N>, <d> )', 'ET( <N>, <d> )', \ldots, 'EY( <N>, <d> )',\\
  367. 'NK( <N>, <k>, <d> )'
  368.  
  369. For $N$ a positive integer, let $z = 'E(<N>)' = e^{2 \pi i / N}$.  The
  370. following   so-called  atomic  irrationalities  (see~\cite[Chapter  7,
  371. Section 10]{CCN85}) can be entered by functions (Note that the  values
  372. are not necessary irrational.)\:
  373.  
  374. \[\begin{array}{llllll}
  375. 'EB(<N>)' & = & b_N & = & \frac{1}{2}\sum_{j=1}^{N-1}z^{j^{2}} &
  376.  (N\equiv 1\bmod 2)\\
  377.  
  378. 'EC(<N>)' & = & c_N & = & \frac{1}{3}\sum_{j=1}^{N-1}z^{j^{3}} &
  379.  (N\equiv 1\bmod 3)\\
  380.  
  381. 'ED(<N>)' & = & d_N & = & \frac{1}{4}\sum_{j=1}^{N-1}z^{j^{4}} &
  382.  (N\equiv 1\bmod 4)\\
  383.  
  384. 'EE(<N>)' & = & e_N & = & \frac{1}{5}\sum_{j=1}^{N-1}z^{j^{5}} &
  385.  (N\equiv 1\bmod 5)\\
  386.  
  387. 'EF(<N>)' & = & f_N & = & \frac{1}{6}\sum_{j=1}^{N-1}z^{j^{6}} &
  388.  (N\equiv 1\bmod 6)\\
  389.  
  390. 'EG(<N>)' & = & g_N & = & \frac{1}{7}\sum_{j=1}^{N-1}z^{j^{7}} &
  391.  (N\equiv 1\bmod 7)\\
  392.  
  393. 'EH(<N>)' & = & h_N & = & \frac{1}{8}\sum_{j=1}^{N-1}z^{j^{8}} &
  394.  (N\equiv 1\bmod 8)
  395. \end{array}\]
  396.  
  397. (Note that in $c_N, \ldots, h_N$, <N> must be a prime.)
  398.  
  399. \[\begin{array}{lllll}
  400. 'ER(<N>)' & = & \sqrt{N}\\
  401. 'EI(<N>)' & = & i \sqrt{N} & = & \sqrt{-N}\\
  402. \end{array}\]
  403.  
  404. From a theorem of Gauss we know that
  405. \[ b_N = \left\{ \begin{array}{llll}
  406.           \frac{1}{2}(-1+\sqrt{N}) & {\rm if} & N\equiv 1 & \bmod 4 \\
  407.           \frac{1}{2}(-1+i\sqrt{N}) & {\rm if} & N\equiv -1 & \bmod 4
  408.           \end{array}\right. ,\]
  409.  
  410. so $\sqrt{N}$ can be (and in fact is) computed from $b_N$.
  411.  
  412. For  given  <N>,  let  $n_k  =  n_k(N)$  be  the  first  integer  with
  413. multiplicative order  exactly <k>  modulo <N>, chosen  in the order of
  414. preference
  415. \[ 1, -1, 2, -2, 3, -3, 4, -4, \ldots\ .\]
  416.  
  417. We have
  418. \[\begin{array}{llllll}
  419. 'EY(<N>)' & = & y_n & = & z+z^n &(n = n_2)\\
  420. 'EX(<N>)' & = & x_n & = & z+z^n+z^{n^2} &(n=n_3)\\
  421. 'EW(<N>)' & = & w_n & = & z+z^n+z^{n^2}+z^{n^3} &(n=n_4)\\
  422. 'EV(<N>)' & = & v_n & = & z+z^n+z^{n^2}+z^{n^3}+z^{n^4} &(n=n_5)\\
  423. 'EU(<N>)' & = & u_n & = & z+z^n+z^{n^2}+\ldots +z^{n^5} &(n=n_6)\\
  424. 'ET(<N>)' & = & t_n & = & z+z^n+z^{n^2}+\ldots +z^{n^6} &(n=n_7)\\
  425. 'ES(<N>)' & = & s_n & = & z+z^n+z^{n^2}+\ldots +z^{n^7} &(n=n_8)
  426. \end{array}\]
  427.  
  428. \[\begin{array}{llllll}
  429. 'EM(<N>)' & = & m_n & = & z-z^n &(n=n_2)\\
  430. 'EL(<N>)' & = & l_n & = & z-z^n+z^{n^2}-z^{n^3} &(n=n_4)\\
  431. 'EK(<N>)' & = & k_n & = & z-z^n+\ldots -z^{n^5} &(n=n_6)\\
  432. 'EJ(<N>)' & = & j_n & = & z-z^n+\ldots -z^{n^7} &(n=n_8)
  433. \end{array}\]
  434.  
  435. Let  $n_k^{(d)}  =  n_k^{(d)}(N)$  be   the   $d+1$-th  integer   with
  436. multiplicative order exactly <k> modulo  <N>,  chosen  in the order of
  437. preference          defined          above;          we          write
  438. $n_k=n_k^{(0)},n_k^{\prime}=n_k^{(1)}, n_k^{\prime\prime} = n_k^{(2)}$
  439. and  so  on.  These  values can be  computed  as 'NK(<N>,<k>,<d>)'$  =
  440. n_k^{(d)}(N)$; if there is no integer with the required multiplicative
  441. order, 'NK' will return 'false'.
  442.  
  443. The algebraic numbers
  444. \[y_N^{\prime}=y_N^{(1)},y_N^{\prime\prime}=y_N^{(2)},\ldots,
  445. x_N^{\prime},x_N^{\prime\prime},\ldots,
  446. j_N^{\prime},j_N^{\prime\prime},\ldots\]
  447. are obtained on replacing $n_k$ in the above
  448. definitions by $n_k^{\prime},n_k^{\prime\prime},\ldots$; they
  449. can be entered as
  450.  
  451. \[\begin{array}{lll}
  452. 'EY(<N>,<d>)' & = & y_N^{(d)}\\
  453. 'EX(<N>,<d>)' & = & x_N^{(d)}\\
  454.  & \vdots \\
  455. 'EJ(<N>,<d>)' & = & j_n^{(d)}
  456. \end{array}\]
  457.  
  458. |    gap> EW(16,3); EW(17,2); ER(3); ER(-3); EY(5); EB(9);
  459.     0
  460.     E(17)+E(17)^4+E(17)^13+E(17)^16
  461.     -E(12)^7+E(12)^11
  462.     E(3)-E(3)^2
  463.     E(5)+E(5)^4
  464.     1|
  465.  
  466. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  467. \Section{StarCyc}\index{galois conjugate!unique}
  468.  
  469. 'StarCyc( <z> )'
  470.  
  471. If <z> is an irrational  element of a  quadratic number field (i.e. if
  472. <z> is a quadratic irrationality), 'StarCyc( <z> )' returns the unique
  473. Galois  conjugate  of <z> that is different from  <z>;  this is  often
  474. called  $<z>\ast$   (see  "DisplayCharTable").  Otherwise  'false'  is
  475. returned.
  476.  
  477. |    gap> StarCyc( EB(5) ); StarCyc( E(5) );
  478.     E(5)^2+E(5)^3
  479.     false|
  480.  
  481. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  482. \Section{Quadratic}\index{quadratic irrationalities}
  483. \index{quadratic number fields}
  484.  
  485. 'Quadratic( <z> )'
  486.  
  487. If <z> is a cyclotomic integer that is contained in a quadratic number
  488. field over  the rationals, it can  be written as $<z> = \frac{  a +  b
  489. \sqrt{n} }{d}$  with integers  $a$, $b$, $n$  and $d$,  where  $d$  is
  490. either 1 or 2.  In this case 'Quadratic( <z>  )' returns a record with
  491. fields 'a', 'b', 'root', 'd' and 'ATLAS' where the first four mean the
  492. integers mentioned above, and the last one is a string that is a  (not
  493. necessarily  shortest)  representation of <z> by $b_m$, $i_m$ or $r_m$
  494. for $m = '\|root\|'$ (see "ATLAS irrationalities").
  495.  
  496. If <z>  is not a quadratic irrationality  or not a cyclotomic integer,
  497. 'false' is returned.
  498.  
  499. |    gap> Quadratic( EB(5) ); Quadratic( EB(27) );
  500.     rec(
  501.       a := -1,
  502.       b := 1,
  503.       root := 5,
  504.       d := 2,
  505.       ATLAS := "b5" )
  506.     rec(
  507.       a := -1,
  508.       b := 3,
  509.       root := -3,
  510.       d := 2,
  511.       ATLAS := "1+3b3" )
  512.     gap> Quadratic(0); Quadratic( E(5) );
  513.     rec( 
  514.       a := 0,
  515.       b := 0,
  516.       root := 1,
  517.       d := 1,
  518.       ATLAS := "0" )
  519.     false|
  520.  
  521. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  522. \Section{GaloisMat}\index{galois conjugate characters}
  523.  
  524. 'GaloisMat( <mat> )'
  525.  
  526. <mat>  must  be  a matrix of  cyclotomics (or  possibly unknowns,  see
  527. "Unknown").  The conjugate of a row in <mat> under a particular Galois
  528. automorphism is  defined  pointwise.  If <mat> consists of full orbits
  529. under this action then the Galois group of its entries acts  on  <mat>
  530. as a permutation group, otherwise the orbits must be completed before.
  531.  
  532. 'GaloisMat( <mat> )' returns a record  with fields 'mat', 'galoisfams'
  533. and 'generators'\:
  534.  
  535. 'mat':\\
  536.       a list with initial  segment <mat> (*not* a  copy of <mat>); the
  537.       list  consists of  full  orbits under the  action of  the Galois
  538.       group  of the entries of  <mat> defined above. The last  entries
  539.       are those rows  which had to be added to complete the orbits; so
  540.       if  they were already complete, <mat> and 'mat'  have  identical
  541.       entries.
  542.  
  543. 'galoisfams':\\
  544.       a list that has the same length as 'mat'; its entries are either
  545.       1, 0, -1 or lists\:\\ $'galoisfams[i]'  = 1$ means that 'mat[i]'
  546.       consists of rationals,  i.e. $[ 'mat[i]'  ]$  forms  an orbit.\\
  547.       $'galoisfams[i]' =-1$  means that 'mat[i]' contains unknowns; in
  548.       this case $[ 'mat[i]'  ]$ is regarded as  an orbit, too, even if
  549.       'mat[i]' contains irrational entries.\\ If $'galoisfams[i]' =  [
  550.       l_1, l_2 ]$ is  a list then 'mat[i]' is the first element of its
  551.       orbit in  'mat'; $l_1$  is  the list of positions  of rows which
  552.       form  the orbit, and $l_2$ is the  list of  corresponding Galois
  553.       automorphisms  (as  exponents,  not  as  functions); so  we have
  554.       $'mat'[  l_1[j] ][k]  =  'GaloisCyc'(  'mat'[i][k], l_2[j] )$.\\
  555.       $'galoisfams[i]' =  0$  means that  'mat[i]'  is an element of a
  556.       nontrivial orbit but not the first element of it.
  557.  
  558. 'generators':\\
  559.       a  list  of  permutations  generating  the   permutation   group
  560.       corresponding  to the  action of the Galois group on the rows of
  561.       'mat'.
  562.  
  563. Note  that <mat> should be a set,  i.e. no  two rows should be  equal.
  564. Otherwise only the first row of some equal rows is  considered for the
  565. permutations, and a warning is printed.
  566.  
  567. |    gap> GaloisMat( [ [ E(3), E(4) ] ] );
  568.     rec(
  569.       mat := [ [ E(3), E(4) ], [ E(3), -E(4) ], [ E(3)^2, E(4) ], 
  570.           [ E(3)^2, -E(4) ] ],
  571.       galoisfams := [ [ [ 1, 2, 3, 4 ], [ 1, 7, 5, 11 ] ], 0, 0, 0 ],
  572.       generators := [ (1,2)(3,4), (1,3)(2,4) ] )
  573.     gap> GaloisMat( [ [ 1, 1, 1 ], [ 1, E(3), E(3)^2 ] ] );
  574.     rec(
  575.       mat := [ [ 1, 1, 1 ], [ 1, E(3), E(3)^2 ], [ 1, E(3)^2, E(3) ] ],
  576.       galoisfams := [ 1, [ [ 2, 3 ], [ 1, 2 ] ], 0 ],
  577.       generators := [ (2,3) ] )|
  578.  
  579. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  580. \Section{RationalizedMat}\index{rational characters}
  581.  
  582. 'RationalizedMat( <mat> )'
  583.  
  584. returns the set  of rationalized rows of <mat>, i.e. the  set  of sums
  585. over  orbits under the action  of the Galois  group of the elements of
  586. <mat> (see "GaloisMat").
  587.  
  588. This may be viewed as a kind of trace operation for the rows.
  589.  
  590. Note that <mat> should be a set, i.e. no two rows should be equal.
  591.  
  592. |    gap> mat:= CharTable( "A5" ).irreducibles;
  593.     [ [ 1, 1, 1, 1, 1 ], [ 3, -1, 0, -E(5)-E(5)^4, -E(5)^2-E(5)^3 ], 
  594.       [ 3, -1, 0, -E(5)^2-E(5)^3, -E(5)-E(5)^4 ], [ 4, 0, 1, -1, -1 ], 
  595.       [ 5, 1, -1, 0, 0 ] ]
  596.     gap> RationalizedMat( mat );
  597.     [ [ 1, 1, 1, 1, 1 ], [ 6, -2, 0, 1, 1 ], [ 4, 0, 1, -1, -1 ], 
  598.       [ 5, 1, -1, 0, 0 ] ]|
  599.  
  600.