home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #16 / NN_1992_16.iso / spool / sci / math / 9677 < prev    next >
Encoding:
Text File  |  1992-07-30  |  4.1 KB  |  106 lines
  1. Newsgroups: sci.math
  2. Path: sparky!uunet!wupost!cs.utexas.edu!sun-barr!ames!agate!linus!linus.mitre.org!gauss!bs
  3. From: bs@gauss.mitre.org (Robert D. Silverman)
  4. Subject: Re: ALGEBRAIC NUMBER ARITHMETIC
  5. Message-ID: <1992Jul30.163746.21362@linus.mitre.org>
  6. Keywords: algebraic numbers, arithmetic
  7. Sender: news@linus.mitre.org (News Service)
  8. Nntp-Posting-Host: gauss.mitre.org
  9. Organization: Research Computer Facility, MITRE Corporation, Bedford, MA
  10. References: <1992Jul30.151149.12688@ugle.unit.no>
  11. Date: Thu, 30 Jul 1992 16:37:46 GMT
  12. Lines: 92
  13.  
  14. In article <1992Jul30.151149.12688@ugle.unit.no> ap@levangerhs.no (Andrei Prasolov) writes:
  15. >Answering to <aet.712408532@munagin> 
  16. >in <1992Jul29.163830.6443@ugle.unit.no> 
  17. >I made a mistake. If we represent algebraic numbers
  18. >only by their minimal polynomials, we cannot construct
  19. >a correct arithmetic. Let us take the main root x of
  20.                     ^^^^
  21.  
  22. There is no such animal as a 'main root'. There is only a
  23. root and its conjugates. If alpha is a root of a polynomial,
  24. then the field Q(alpha) is isomorphic to Q(alpha') where
  25. alpha' is any of alpha's conjugates.  The map is controlled by the
  26. Galois group.
  27.  
  28. Your assertion that one cannot construct a correct arithmetic if all
  29. one has is the minimal polynomial is FALSE.
  30.  
  31. >        2                              
  32. >f(X) = X -2 and the main root y of
  33. >
  34. >        4                
  35. >g(Y) = Y -2. The algorythm says that z = x+y is 
  36.  
  37. The fields Q(x), Q(y) are different. The field Q(x+y) is an extension
  38. of Q(x) and also an extension of Q(y). 
  39.  
  40. >a root of h(Z) = h_1(Z) * h_2(Z) where
  41. >h_1(Z) = (Z^2+2)^2-2(2Z+1)^2 
  42. >     has roots x+y, x-y, -x+iy, -x-iy, and
  43. >h_2(Z) = (Z^2+2)^2-2(2Z-1)^2
  44. >     has roots x+iy, x-iy, -x+y, -x-y.
  45.  
  46. Which algorithm? I'm afraid I don't follow you when you say "the" algorithm.
  47.  
  48. >The algorythm cannot determine, which polynomial
  49. >from the two the number x+y is a root of.
  50.  
  51. So? This is totally irrelevent if working in Q(x+y). Your polynomial
  52. h(Z) is not irreducible. You further confuse the issues involved by writing
  53. terms like x + iy because the field Q(x) is purely real, while Q(y) is
  54. imaginary.
  55.  
  56.  
  57. I must confess that I don't understand what you are trying to say.
  58.  
  59. >   So the representation by pairs (irr. polynomial, interval)
  60. >seems to be reasonable. One needs, however, the following
  61. >two algorythms:
  62. >  1. Separation of roots of a polynomial 
  63. >           (there exists a lot of algorythms).
  64. >  2. Decomposition of polynomials over Q into
  65. >     prime factors (I am not aware of any). 
  66.  
  67. This is totally irrelevent.
  68.  
  69. Let me try to give a simple overview, along with an example.
  70.  
  71. Let f(x) be the minimal (irreducible) polynomial of alpha. Assume
  72. f has degree d.
  73.  
  74. Any element of the (algebraic extension) field Q(alpha) may be represented
  75. by a1 + a2 * alpha + a3* alpha^2 + ....  a_d alpha^(d-1).  This element is
  76. an algebraic number. I use the notation a = [a1,a2,...a_d] to represent
  77. one such number. Now, to perform arithmetic [let's say multiplication] on
  78. a and b [a*b = [a1,a2,...a_d] * [b1,b2... b_d] ] one does this as one would
  79. ordinary multiplication of two polynomials in alpha subject to the simplifying
  80. side condition f(alpha) = 0.
  81.  
  82. For example. Consider Q(alpha = sqrt(2)) with f(x) = x^2 - 2. 
  83. Now, (a1 + a2 alpha)*(b1 + b2 alpha) = a1 b1 + (a2 b1 + a1 b2) alpha + a2 b2 alpha^2.
  84.  
  85. Use the fact that alpha^2 = 2 and this simplifies to:
  86.  
  87. a1 b1 + 2 a2 b2 + (a2 b1 + a1 b2) alpha.
  88.  
  89.  
  90. Where's the problem???? Basic arithmetic in algebraic number fields [e.g.
  91. addition subtraction, multiplication] is trivial. Division is a little more
  92. complicated because one must find a representation for an inverse via (say)
  93. the extended Euclidean algorithm or by linear algebra.
  94.  
  95. Now arithmetic in the ring of integers of an extension field Q(alpha) can
  96. get more complicated, because one must find an integral basis for the ring.
  97. It is currently an open field of study to find good algorithms for doing so
  98. when the field discriminant is large.
  99.  
  100. I hope this clarifies things.
  101. --
  102. Bob Silverman
  103. These are my opinions and not MITRE's.
  104. Mitre Corporation, Bedford, MA 01730
  105. "You can lead a horse's ass to knowledge, but you can't make him think"
  106.