Math Solutions 1995 October

home *** CD-ROM | disk | FTP | other *** search

/ Math Solutions 1995 October / Math_Solutions_CD-ROM_Walnut_Creek_October_1995.iso / pc / mac / discrete / doc / gaussian.tex < prev next >

Wrap

Text File | 1993-05-05 | 13.9 KB | 370 lines

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %A gaussian.tex GAP documentation Martin Schoenert %% %A @(#)$Id: gaussian.tex,v 3.5 1993/02/01 13:25:57 felsch Exp $ %% %Y Copyright 1990-1992, Lehrstuhl D fuer Mathematik, RWTH Aachen, Germany %% %% This file describes Gaussian integers and rationals and their functions. %% %H $Log: gaussian.tex,v $ %H Revision 3.5 1993/02/01 13:25:57 felsch %H example fixed %H %H Revision 3.4 1992/04/06 16:54:53 martin %H fixed some more typos %H %H Revision 3.3 1992/04/02 21:06:23 martin %H changed *domain functions* to *set theoretic functions* %H %H Revision 3.2 1992/03/11 15:51:46 sam %H renamed chapter "Number Fields" to "Subfields of Cyclotomic Fields" %H %H Revision 3.1 1992/01/08 11:41:10 martin %H initial revision under RCS %H %% \Chapter{Gaussians}% \index{type!gaussian rationals} \index{type!gaussian integers} If we adjoin a square root of -1, usually denoted by $i$, to the field of rationals we obtain a field that is an extension of degree 2. This field is called the *Gaussian rationals* and its ring of integers is called the *Gaussian integers*, because C.F. Gauss was the first to study them. In {\GAP} Gaussian rationals are written in the form '<a> + \*E(4)', where <a> and are rationals, because 'E(4)' is {\GAP}\'s name for $i$. Because 1 and $i$ form an integral base the Gaussian integers are written in the form '<a> + \*E(4)', where <a> and are integers. The first sections in this chapter describe the operations applicable to Gaussian rationals (see "Comparisons of Gaussians" and "Operations for Gaussians"). The next sections describe the functions that test whether an object is a Gaussian rational or integer (see "IsGaussRat" and "IsGaussInt"). The {\GAP} object 'GaussianRationals' is the field domain of all Gaussian rationals, and the object 'GaussianIntegers' is the ring domain of all Gaussian integers. All set theoretic functions are applicable to those two domains (see chapter "Domains" and "Set Functions for Gaussians"). The Gaussian rationals form a field so all field functions, e.g., 'Norm', are applicable to the domain 'GaussianRationals' and its elements (see chapter "Fields" and "Field Functions for Gaussian Rationals"). The Gaussian integers form a Euclidean ring so all ring functions, e.g., 'Factors', are applicable to 'GaussianIntegers' and its elements (see chapter "Rings", "Ring Functions for Gaussian Integers", and "TwoSquares"). The field of Gaussian rationals is just a special case of cyclotomic fields, so everything that applies to those fields also applies to it (see chapters "Cyclotomics" and "Subfields of Cyclotomic Fields"). All functions are in the library file 'LIBNAME/\"gaussian.g\"'. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Comparisons of Gaussians}% \index{equality!of gaussians}% \index{ordering!of gaussians} '<x> = <y>' \\ '<x> \<> <y>' The equality operator evaluates to 'true' if the two Gaussians <x> and <y> are equal, and to 'false' otherwise. The inequality operator '\<>' evaluates to 'true' if the two Gaussians <x> and <y> are not equal, and to 'false' otherwise. It is also possible to compare a Gaussian with an object of another type, of course they are never equal. Two Gaussians '<a> + \*E(4)' and '<c> + <d>\*E(4)' are considered equal if '<a> = <c>' and ' = <d>'. | gap> 1 + E(4) = 2 / (1 - E(4)); true gap> 1 + E(4) = 1 - E(4); false gap> 1 + E(4) = E(6); false | '<x> \< <y>' \\ '<x> \<= <y>' \\ '<x> > <y>' \\ '<x> >= <y>' The operators '\<', '\<=', '>', and '>=' evaluate to 'true' if the Gaussian <x> is less than, less than or equal to, greater than, and greater than or equal to the Gaussian <y>, and to 'false' otherwise. Gaussians can also be compared to objects of other types, they are smaller than anything else, except other cyclotomics (see "Comparisons of Cyclotomics"). A Gaussian '<a> + \*E(4)' is considered less than another Gaussian '<c> + <d>\*E(4)' if <a> is less than <c>, or if <a> is equal to <c> and is less than <d>. | gap> 1 + E(4) < 2 + E(4); true gap> 1 + E(4) < 1 - E(4); false gap> 1 + E(4) < 1/2; false | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Operations for Gaussians}% \index{sum!of gaussians}\index{difference!of gaussians}% \index{product!of gaussians}\index{quotient!of gaussians}% \index{power!of gaussians} '<x> + <y>' \\ '<x> - <y>' \\ '<x> \*\ <y>' \\ '<x> / <y>' The operators '+', '-', '\*', and '/' evaluate to the sum, difference, product, and quotient of the two Gaussians <x> and <y>. Of course either operand may also be an ordinary rational (see "Rationals"), because the rationals are embedded into the Gaussian rationals. On the other hand the Gaussian rationals are embedded into other cyclotomic fields, so either operand may also be a cyclotomic (see "Cyclotomics"). Division by 0 is as usual an error. '<x> \^\ <n>' The operator '\^' evaluates to the <n>-th power of the Gaussian rational <x>. If <n> is positive, the power is defined as the <n>-fold product '<x>\*<x>\*...<x>'; if <n> is negative, the power is defined as '(1/<x>)\^(-<n>)'; and if <n> is zero, the power is 1, even if <x> is 0. | gap> (1 + E(4)) * (E(4) - 1); -2 | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsGaussRat}% \index{test!for gaussian rational} 'IsGaussRat( <obj> )' 'IsGaussRat' returns 'true' if <obj>, which may be an object of arbitrary type, is a Gaussian rational and 'false' otherwise. Will signal an error if <obj> is an unbound variable. | gap> IsGaussRat( 1/2 ); true gap> IsGaussRat( E(4) ); true gap> IsGaussRat( E(6) ); false gap> IsGaussRat( true ); false | 'IsGaussInt' can be used to test whether an object is a Gaussian integer (see "IsGaussInt"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{IsGaussInt}% \index{test!for gaussian integer} 'IsGaussInt( <obj> )' 'IsGaussInt' returns 'true' if <obj>, which may be an object of arbitrary type, is a Gaussian integer, and false otherwise. Will signal an error if <obj> is an unbound variable. | gap> IsGaussInt( 1 ); true gap> IsGaussInt( E(4) ); true gap> IsGaussInt( 1/2 + 1/2*E(4) ); false gap> IsGaussInt( E(6) ); false | 'IsGaussRat' can be used to test whether an object is a Gaussian rational (see "IsGaussRat"). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Set Functions for Gaussians}% \index{membership test!for gaussians}\index{in!for gaussians}% \index{Random!for gaussians}% As already mentioned in the introduction of this chapter the objects 'GaussianRationals' and 'GaussianIntegers' are the domains of Gaussian rationals and integers respectively. All set theoretic functions, i.e., 'Size' and 'Intersection', are applicable to these domains and their elements (see chapter "Domains"). There does not seem to be an important use of this however. All functions not mentioned here are not treated specially, i.e., they are implemented by the default function mentioned in the respective section. \vspace{5mm} 'in' The membership test for Gaussian rationals is implemented via 'IsGaussRat' ("IsGaussRat"). The membership test for Gaussian integers is implemented via 'IsGaussInt' (see "IsGaussInt"). \vspace{5mm} 'Random' A random Gaussian rational '<a> + \*E(4)' is computed by combining two random rationals <a> and (see "Set Functions for Rationals"). Likewise a random Gaussian integer '<a> + \*E(4)' is computed by combining two random integers <a> and (see "Set Functions for Integers"). | gap> Size( GaussianRationals ); "infinity" gap> Intersection( GaussianIntegers, [1,1/2,E(4),-E(6),E(4)/3] ); [ 1, E(4) ] | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Field Functions for Gaussian Rationals}% \index{Conjugates!for gaussians}% \index{Norm!for gaussians}% \index{Trace!for gaussians} As already mentioned in the introduction of this chapter, the domain of Gaussian rationals is a field. Therefore all field functions are applicable to this domain and its elements (see chapter "Fields"). This section gives further comments on the definitions and implementations of those functions for the the Gaussian rationals. All functions not mentioned here are not treated specially, i.e., they are implemented by the default function mentioned in the respective section. \vspace{5mm} 'Conjugates' The field of Gaussian rationals is an extension of degree 2 of the rationals, its prime field. Therefore there is one further conjugate of every element '<a> + \*E(4)', namely '<a> - \*E(4)'. \vspace{5mm} 'Norm', 'Trace' According to the definition of conjugates above, the norm of a Gaussian rational '<a> + \*E(4)' is '<a>\^2 + \^2' and the trace is '2\*<a>'. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{Ring Functions for Gaussian Integers}% \index{IsUnit!for gaussians}\index{Units!for gaussians}% \index{IsAssociated!for gaussians}\index{Associates!for gaussians}% \index{StandardAssociate!for gaussians}% \index{mod!for gaussians}% \index{IsPrime!for gaussians}\index{IsIrreducible!for gaussians}% \index{Factors!for gaussians} As already mentioned in the introduction to this chapter, the ring of Gaussian integers is a Euclidean ring. Therefore all ring functions are applicable to this ring and its elements (see chapter "Rings"). This section gives further comments on the definitions and implementations of those functions for the Gaussian integers. All functions not mentioned here are not treated specially, i.e., they are implemented by the default function mentioned in the respective section. \vspace{5mm} 'IsUnit', 'Units', 'IsAssociated', 'Associates' The units of 'GaussianIntegers' are '[ 1, E(4), -1, -E(4) ]'. \vspace{5mm} 'StandardAssociate' The standard associate of a Gaussian integer <x> is the associated element <y> of <x> that lies in the first quadrant of the complex plane. That is <y> is that element from '<x> \*\ [1,-1,E(4),-E(4)]' that has positive real part and nonnegative imaginary part. \vspace{5mm} 'Mod' Define the integer part of the quotient of <x> and <y> as the point of the lattice spanned by 1 and 'E(4)' that lies next to the rational quotient of <x> and <y>, rounding towards the origin if there are several such points. Then 'Mod( <x>, <y> )' is defined as '<x> - \*\ <y>'. With this definition the ordinary Euclidean algorithm for the greatest common divisor works, whereas it does not work if you always round towards the origin. \vspace{5mm} 'IsPrime', 'IsIrreducible' Since the Gaussian integers are a Euclidean ring, primes and irreducibles are equivalent. The primes are the elements '1 + E(4)' and '1 - E(4)' of norm 2, the elements '<a> + \*E(4)' and '<a> - \*E(4)' of norm ' = <a>\^2 + \^2' with a rational prime congruent to 1 mod 4, and the elements of norm '\^2' with a rational prime congruent to 3 mod 4. \vspace{5mm} 'Factors' The list returned by 'Factors' is sorted according to the norms of the primes, and among those of equal norm with respect to '\<'. All elements in the list are standard associates, except the first, which is multiplied by a unit as necessary. The above characterization already shows how one can factor a Gaussian integer. First compute the norm of the element, factor this norm over the rational integers and then split 2 and the primes congruent to 1 mod 4 with 'TwoSquares' (see "TwoSquares"). | gap> Factors( GaussianIntegers, 30 ); [ -1-E(4), 1+E(4), 3, 1+2*E(4), 2+E(4) ] | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \Section{TwoSquares}% \index{representation!as a sum of two squares} 'TwoSquares( <n> )' 'TwoSquares' returns a list of two integers $x\<=y$ such that the sum of the squares of $x$ and $y$ is equal to the nonnegative integer <n>, i.e., $n = x^2+y^2$. If no such representation exists 'TwoSquares' will return 'false'. 'TwoSquares' will return a representation for which the gcd of $x$ and $y$ is as small as possible. If there are several such representations, it is not specified which one 'TwoSquares' returns. Let $a$ be the product of all maximal powers of primes of the form $4k+3$ dividing $n$. A representation of $n$ as a sum of two squares exists if and only if $a$ is a perfect square. Let $b$ be the maximal power of $2$ dividing $n$, or its half, whichever is a perfect square. Then the minimal possible gcd of $x$ and $y$ is the square root $c$ of $a b$. The number of different minimal representations with $x\<=y$ is $2^{l-1}$, where $l$ is the number of different prime factors of the form $4k+1$ of $n$. | gap> TwoSquares( 5 ); [ 1, 2 ] gap> TwoSquares( 11 ); false # no representation exists gap> TwoSquares( 16 ); [ 0, 4 ] gap> TwoSquares( 45 ); [ 3, 6 ] # 3 is the minimal possible gcd because 9 divides 45 gap> TwoSquares( 125 ); [ 2, 11 ] # not [ 5, 10 ] because this has not minimal gcd gap> TwoSquares( 13*17 ); [ 5, 14 ] # [10,11] would be the other possible representation gap> TwoSquares( 848654483879497562821 ); [ 6305894639, 28440994650 ] # 848654483879497562821 is prime | %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %E Emacs . . . . . . . . . . . . . . . . . . . . . local Emacs variables %% %% Local Variables: %% mode: outline %% outline-regexp: "\\\\Chapter\\|\\\\Section" %% fill-column: 73 %% eval: (hide-body) %% End: %%