A.» “1- - ‘..—~v\- 3'04! ~.‘\ - q" o'Q-N‘F'WJ'T‘ u. x w c, .-g.. 43- u «L- wan:— w v‘> -‘. 5 ‘ m 23‘!) ‘ .7}- ”L27 v «9, WM ’4“; .,‘. ‘J‘C 1:335: . £1": “0““): «32’; ‘l; ’-I:; ' V I J:"'{’/ {1/’ ~- ,ua',“ n In]. -. I” I a", f fir .., .‘V a: #4:}, n < "v Uri-{"4 "”3... ,_ up __ .. 4",“???3": u.- w: ; . ' 7 x a ._ ~ :l-:;:i~;~.\_._$l . :4 . 4" - . :11 ... Mr: W?” ’f' I [.7r‘o'uf’3 ' I a?” -;Y,' 11’?“ v’vz'fil 23:35:11“ . £2. - -’~‘ 'x_ $04.": *“n. .‘T;-':'\“ . .- ». J31?’.-:¢:' mm ‘5‘";- 011:7 é'v'V/u , n—., av .. .-‘ 'f . , l . ' 7.1. '2 . " , 113.?“31'M' " ' in "1'. 33¢,” ;..’ p '5' ‘5'? if???” .4 if: £1,114 7-.) I5 " :1}; r/r‘f f;:?§;' 16:73:1'fi‘3fi vi." fiffi’ 9],! , jig! W91“ ' ‘ ‘. .i a- ,7 1L .. yawni- -. #:ngi,‘ ‘ ‘7 ¢ I 'wlwu “I" «£3253. ...1‘Lm."’-‘_‘ Manx». ‘ «4.. ‘V‘0\ .h\ - I '0']- «u . a y - |.| fay ' . . . :lrfwnnfi . —4- F4 4 r {.4 ”5.5/er r47...“ 9“ .’ ’3'2’ ‘ .1 7f‘ 12.4.!" m ' VHS-sag LIBRARY Michigan State University This is to certify that the dissertation entitled 1.. THE RING OF’CYCLOTOMIC INTEGERS OF MODULUS THIRTEEN IS NORM-EUCLIDEAN presented by Robert George McKenzie has been accepted towards fulfillment of the requirements for Ph . D . degree in Mathematics W‘W’HwM—x Major professor Date July 29, 1988 MS U i: an Affirmative Action/Equal Opportunity Institution , 0-12771 -——-——-—-——__ IV1531_J RETURNING MATERIALS: Place in book drop to LJBRARJES remove this checkout from —:—-. your record. FINES will be charged if book is retvrned after the date stamped below. THE RING OF CYCLOTOMIC INTEGERS OF MODULUS THIRTEEN IS NORM-EUCLIDEAN By Robert George McKenzie A DISSERTATION Submitted to Michigan State University in partial fulfillment of the requirements for the degree of DOCTOR OF PHILOSOPHY Department of Mathematics 1988 ABSTRACT THE RING OF CYCLOTOMIC INTEGERS OF MODULUS THIRTEEN IS NORM-EUCLIDEAN By Robert George McKenzie In this dissertation the ring of integers of the thirteenth cyclotomic field is shown to be euclidean with respect to the field norm. The basic method, in outline, is to cover the fundamental cell of the quotient field by numerous small subregions. Then, for each subregion, an integral point 4 is found such that Norm(x-q) < l for all points x in the subregion. The generation of subregions, the finding of integral points, and the bounding of the Norm were all done by a FORTRAN program written for an electronic computer. This dissertation is dedicated to Janice Marie Szur, who is both necessary and sufficient. ACKNOWLEDGMENTS I would like to acknowledge the contributions of the following people to this dissertation. Firstly, my dissertation advisor, Charles MacCluer, who taught me number theory. Secondly, my principal instructors in the many branches of Algebra: Jonathan Hall, Richard Phillips, William Brown, and Andrew Bailey. Thirdly, my principal insn'uctors in other branches of Mathematics: Sheldon Axler, Bruce Sagan, Peter Lappan, Steve Dragosh, Charles Seebeck, and Donna Carr. Next, those colleagues whose presence and efforts in seminars and committee have aided me: John Wolfskill, Capi Corrales, William Sledd, Lee Sonneborn, Edward Ingraham, Susan Schuur, Wei Kuan, Joseph Brennan, and Timothy Sauer. I owe a particular debt of gratitude to H. W. Lenstra, Jr., whose work has been an inspiration, and whose prompt and com'teous advice is deeply appreciated. Also, T. Ojala, M. Ram Murty, and Don Lewis have been helpful both in their work and elsewhere. The faculty and staff of the Mathematics Department at Michigan State have been invariably kind and helpful. Worthy of special thanks are the Chairmen, past and present, Joseph Adney and Kyung Whan Kwun, and the Associate Chairman, Douglas Hall. Also, Judith Miller, Barbara Miller, Berle Reiter, Velma DeMyers, and Sterling Tryon-Hartwig have exerted themselves on my behalf above and beyond the call of duty. Finally, I would like to thank all of my fellow graduate students. Of particular note are: Richard Hensh, Paul Hewitt, Michael Vernon, 1036 Geraldo, Kathy McKeon, John Long, Martin Bredeck, Kathy Dempsy, Richard Reynolds, and Joseph Spencer. TABLE OF CONTENTS page List of Tables ....................................................................................... vii Chapter 1 A Historical Perspective on the Euclidean Problem ............................ 1 §1 Euclidean Rings and the First Question .......................................... 1 §2 Number Fields and Two Further Questions ..................................... 2 §3 Quadratic Fields .................................................................... 4 §4 Cyclotomic Fields .................................................................. 6 §5 2 [C13] ................................................................................ 8 Chapter 2 The Theoretical Background ...................................................... 9 §O Introduction ......................................................................... 9 §1 Passable Points and Sufficient Sets .............................................. 9 §2 Standard Form, Reduced Points and Patterns ................................. 16 §3 The Fundamental Cell and Patterns ............................................. 21 §4 The Final Sufficient Set -- Points from Patterns ............................... 30 §5 Passing Points -- Finding a Nearby Integer .................................... 35 §6 Bounding the Norm \l’ on a Sphere ............................................. 37 Chapter 3 A Description of the Program and Its Algorithms ............................. 46 §0 Introduction ........................................................................ 46 §1 The Control Routine .............................................................. 46 §2 The Pattern Generator ............................................................. 48 §3 Checking The Fundamental Cell ......... t ........................................ 54 §4 The Point Generator ............................................................... 56 V The First Checker ................................................................. 62 §5 §6 The Second Checker .............................................................. 67 §7 The Third Checker ................................................................ 71 §8 Slick, the Point Passer ............................................................ 73 Chapter 4 Bounding the Growth of Floating Point Error ................................. 76 §O Introduction ........................................................................ 76 §1 Bounding size ...................................................................... 77 §2 A preliminary error estimation ................................................... 81 §3 Initializing the single precision routine checkl ................................. 82 §4 Point passing by the single precision routine checkl ......................... 93 §5 Initializing the double precision routine slick ................................ 101 §6 Point passing by the double precision routine slick ......................... 110 Chapter 5 Conclusions and Open Questions ............................................. 116 §1 A summary of runs .............................................................. 116 §2 Conclusions ...................................................................... 1 18 §3 Other attacks on Z[§13] ......................................................... 120 §4 Open cyclotomic questions ..................................................... 123 Appendix A The Program Listing ............................................................ 126 Appendix B Flowcharts ....................................................................... 159 Bibliography ..................................................................................... 168 Table \OOONIGLII-hUJN NNt—at—tu—ev—nt—sr—AHt—r—r— HOOWQO‘MhWNr—fio LIST OF TABLES page 81: the error on realxo) .................................................................... 84 82: the error on imagxo) .................................................................. 86 83: the error on realqu) .................................................................. 87 E4: the error on imagxq(i) ................................................................. 90 85: the error on (:0) ........................................................................ 91 85min: the error on cmin .................................................................. 92 85: the error on lower ......................................................... . ............ 93 87: the error on temp] (1) .................................................................. 94 83: the error on length ..................................................................... 97 89: the error on upper ...................................................................... 98 810: the error on temp2(/) .............................................................. '. 100 811: the relative error on ubound ....................................................... 100 the errors on angle, radius, and radsqd ................................................ 103 the error on reale(i,/) and image(i,/) .................................................... 103 617: the error on realed(i,i) .............................................................. 105 613: the error on imaged(i,]) ............................................................ 105 819: the error on realxo) ..... 106 820: the error on imagx(i) ............................................................... 107 821: the error on realxqo) ............................................................... 107 822: the error on imagxqo') .............................................................. 108 823: the error on 0(1) ..................................................................... 109 vii 22 23 24 25 26 27 28 29 30 3 1 32 33 34 £21m": the error on cmin ............................................................... 109 825: the error on temp2(]) when 824 = 0 ............................................... 112 £25 & 823: the errors on length and diff when 624: 0 ............................... 112 827: the relative error on bound when 824 = 0 ........................................ 112 824: the error on approx ................................................................. 1 14 825: the error on temp2(/) ............................................................... 115 827: the relative error on bound ........................................................ 115 Run summary (d =7) .................................................................... 117 Run summary (d = 6) .................................................................... 117 Runsummary(d=6,f=2) ............................................................ 118 The size ofSwhenm =13 .............................................................. 120 The size ofSwhenm =17 .............................................................. 124 The size ofSwhenm =19 .............................................................. 124 Chapter 1 A Historical Perspective on the Euclidean Problem §l Euclidean Rings and the First Question. Over two thousand years ago Euclid gave an algorithmic procedure (still used today) to compute the greatest common divisor of two positive integers [Eu, Book VII, Propositions 1-3]. This procedure is called Euclid's algorithm and can be applied to rings other than the integers. A ring for which Euclid's algorithm will give a greatest common divisor of two elements is thus known as a euclidean ring. The precise conditions needed to enable Euclid's algorithm to work are given in the following definition. Definition 1.1 A ring R is said to be a euclidean ring, or euclidean with respect to the algorithm v, if there exists a well ordered set W and a mapping w: R—)W, called a euclidean algorithm, such that for each pair of elements a, b e R, with b 96 0, there exists a pair of elements 4, r e R satisfying the following two properties: a=bq+r (1.2) WV) < Mb). (13) Thus there are three interrelated concepts. (i) A euclidean ring is a ring satisfying Definition 1.1. (ii) Euclid's algorithm is a process that can be used on a euclidean ring to find greatest common divisors. (iii) A euclidean algorithm is a mapping satisfying (1.2) and (1.3) above. A ring is euclidean when a euclidean algorithm exists for it, and in this case, Euclid's algorithm can be used (in conjunction with its euclidean algorithm) to find greatest common divisors. Note that the ring Z of integers is euclidean with respect to the usual absolute value w( x ) = l x I. The following nanual question can be asked about any ring. Question 1.4. Is R euclidean? This will be called the euclidean question. Note that this is a question about the existence of an algorithm and does not require the exhibition of any specific algorithm satisfying (1.2) and (1.3). §2 Number Fields and Two Further Questions. Because Z is the ring of integers in the algebraic number field Q it is naun'al to pose the euclidean question for the ring of integers of an arbin'ary number field. Because a number field is the quotient field of its ring of integers and because it is often difficult to describe the ring of integers simply, number theorists speak of the number field when they mean its ring of integers. We will use this abuse of language and speak of a number field as being or not being euclidean when we mean that its ring of integers is or is not euclidean. Henceforth we will let K be an arbitrary number field and R be its ring of integers -- that is, R consists of those elements of K that satisfy a monic polynomial with coefficients from Z. A natural generalization to R of the absolute value in Z is the absolute value of the field norm from K to Q. Thus we have the following definition and question. Definition 1.5. Let K be a number field with ring of integers R. If R is euclidean with respect to Mr) = l NormK/Q(x) l we say that K is norm-euclidean. 3 Question 1.6. Is K norm-euclidean? This will be called the norm-euclidean question. Note that the norm-euclidean question is much more detailed than the euclidean question, for we are asking that the ring he euclidean with respect to a very specific algorithm. Of course, if a field is norm-euclidean it is necessarily euclidean. The converse is an interesting open question: are there fields that are euclidean but not norm-euclidean? It is immediate that every euclidean ring is principal. Thus a euclidean number field necessarily has class number one. The following definition will make this more precise. Definition 1.7. Let K be a number field and I be the group of non-zero fractional ideals of K. Let P be the group of non-zero principal fractional ideals of K. The quotient group I/P is known as the class group. The order of UP is known as the class number of K. For more about fractional ideals and the class number see [Cu, Chapter III]. The class number of a number field is finite [Cu, Theorem 20.6], and the field has class number one if and only if the ring of integers is principal. That is, in a number field K, it is the class number that measures whether or not R is principal. This leads us to the final question we will ask about a number field. Question 1.8. Does K have class number one? This will be called the class number question. This question is the weakest of the three, for a norm-euclidean field is necessarily euclidean, and a euclidean field necessarily has class number one. There are class number one fields that are not euclidean, for example Q(\IT9) [Mo]. 4 For a given number field K, the comparative level of difficulty of these questions is as follows. The class number of K is reasonably easy to compute. When K has class number one, whether K is norm-euclidean is a more difficult matter to settle. Lastly, if K has class number one and is not norm-euclidean, it is extremely difficult to determine whether K is euclidean. §3 Quadratic Fields The above questions have been considered for many families of number fields. The family of fields quadratic over Q has been investigated successfully. For this section d will be a square free integer, K will be the quadratic field Q0171), and R will be the ring of integers of K. The cases with d > 0 and d < 0 are different and are dealt with separately. Let K ,._. Q0171), where d is negative. K is called an imaginary quadratic field. All three questions: the euclidean question; the norm-euclidean question; and the class number question, have been settled for all of the imaginary quadratic fields. It is a classical result that for imaginary quadratic fields K, the class number is one if d is one of the following nine integers: d = -1, -2, -3, -7, -11, -19, -43, -67, -163. K. F. Gauss conjectured that these are the only examples [C0, page 151]. This conjecture was finally shown to be correct in 1967 by H. Stark [S]. Thus these are the only possible imaginary quadratic candidates for euclidean and norm-euclidean fields. Historically, the norm-euclidean question and the euclidean question were answered for the imaginary quadratic fields before the class number question was. It is a classical result that R is norm-euclidean if and only if d is One of the following five numbers: d = -1, -2, -3, -7, -11. Finally, it is known that R is not euclidean under any algorithm for 5 the remaining four values: d = -19, -43, -67, -163. An excellent proof of all this can be found in [Lel]. Let K = Q0171), where d is positive. K is called a real quadratic field. The class number question and the euclidean question are both open in this case. The norm-euclidean question is completely settled for all real quadratic fields. The class number has been computed for all reasonable values of d. Gauss conjectured that there are infinitely many real quadratic fields that have class number one. This difficult question is still open. A good reference is [C0, chapter 9]. The norm-euclidean question is answered for all real quadratic fields. In particular, K is norm-euclidean if and only if d is one of the following sixteen numbers: d= 2, 3, 5, 6, 7, 11, 13, 17, 19, 21, 29, 33, 37, 41, 57, 73. For references that these fields are all norm-euclidean, see [Chl]. The difficult part of the previous result is that these are the only real quadratic norm-euclidean fields. That was settled in 1950 by H. Chatland and H. Davenport [Ch2]. Both of the above papers falsely list Q(\/9_7) as norm-euclidean. See [B, theorem 12, pages 318-322] for the truth in this matter. There are, however, real quadratic fields that do have class number one and that are not norm-euclidean. Indeed, if Gauss is correct, there are infinitely many of these. For example, there are twenty three values of d less than 100: d = 14, 22, 23, 31, 38, 41, 43, 46, 47, 53, 59, 61, 62, 67, 69, 71, 77, 83, 86, 89, 93, 94, 97. For each of these, the euclidean question is open. That is, it is unknown whether or not the field is euclidean with respect to some algorithm other than the norm (see [Le1]). 6 Definition 1.9. Let K be a number field and R be its ring of integers. The Dedekind zeta function, CK: is the meromorphic extension of 1 = , 1.13 CW) 1 ER ( Norm/Q0) ), ( ) where the sum runs over the non-zero ideals I C R and s is a complex number with Re(s) > 1. Definition 1.10. The generalized Riemann hypothesis is: for each number field K, all non-trivial (non real) zeros of CK satisfy Re(s) = l/ 2. P. J. Weinberger [We] showed that if (i) the generalized Riemann hypothesis is true, (ii) R has infinitely many units, and (iii) K has class number one, then K is euclidean. As the only number fields whose ring of integers has finitely many units are the imaginary quadratic fields, Weinberger's result says, subject to the generalized Riemann hypothesis, that all the class number one real quadratic fields are euclidean with respect to some algorithm. §4 Cyclotomic Fields The other major family of fields for which these questions have been posed is the family of cyclotomic fields. These fields were studied systematically in the middle of the nineteenth century in conjunction with Fermat's "last" theorem [Le4]. Thus the three above questions are classical in tone. Let m be a positive integer not congruent to 2 modulo 4, let Cm be a primitive rnm root of unity, and letK = Q(§m). K is known as a cyclotomic field with modulus m. 7 Here R = Z[Cm] is the ring of integers in K. It is known that K has class number one if and only ifm is one of the following thirty numbers: m= l, 3, 4, 5, 7, 8, 9, 11, 12, 13, 15, 16, 17, 19, 20, 21, 24, 25, 27, 28, 32, 33, 35, 36, 40, 44, 45, 48, 60, 84. Of course, for a particular value of m the class number is a relatively straightforward computation. The difficult portion of the above result is that these are the only values of m for which K has class number one. This was done by J. M. Masley and H. M. Montgomery in 1976 [Ma]. Thus the class number question has been settled for all cyclotomic fields. Of these thirty fields, the norm-euclidean question has been answered if m is one of the following fifteen numbers: m= l, 3, 4, 5, 7, 8, 9, ll, 12, 13, 15, 16, 20, 24, 32. It is known that Q[§32] is not norm-euclidean and that the other fourteen are. Whether Q[C32] is euclidean with respect to some algorithm other than the norm is not known. For the remaining fifteen values of m, both the norm-euclidean question and the euclidean question are open. Of course, Weinberger's aforementioned result says that all thirty of the above fields are euclidean if the generalized Riemann hypothesis holds. The case with m = 1 dates back to Euclid. The case m = 4 can be found in Gauss [Ga, pages 117-118]. The first published proof for m = 3 was given by P. L. Wantzel [Wa] in 1847. The case m = 8 was done by G. Eisenstein [Ei, pages 585-587] in 1850. The case rn = 5 was published by J. Ouspensky [On] in 1909. It is likely that m = 12 was done before, but the earliest published proof known is due to R. B. Lakien [La] in 1972. The cases rn = 7,9,11,15,20 were done in a landmark paper by H. W. Lenstra, Jr. [Le2] in 1975. Lenstra's techniques are fundamental to what follows in this work. T. Ojala [Oj] did the case m = 16 in 1977. we will also use some of Ojala's 8 techniques. Lenstra [Le3] also did the case m = 24 in 1978 using the lattice F3. Finally we have the case m = 13 which will be shown to be norm-euclidean in this dissertation. §5 ZIC13] In what follows in this work, the ring Z[§13] is shown to be norm-euclidean. To my knowledge, this is the highest degree (12) number field whose ring of integers has been shown to be norm-euclidean. Consequentially, the method is computationaly laborious. The basic method, in outline, is to cover F , a fundamental cell of the quotient field K, by numerous small subregions F 1;. Next, for each subregion F ,5, an integral point 4 e R is found. Finally, M x( q ) = max{ ut( z - q): z e Fx} is bounded above, where My) = l NormK/QQ’) I. Because for each subregion F, there exists an integral point 4 e R with M,( q) < l, R is norm-euclidean. Chapter 2 The Theoretical Background §0 Introduction The objective of this work is the following theorem. Theorem 2.1. Let C13 be a primitive 131h root of unity. Then Z[C13] is norm-euclidean. The method which we will use to prove Theorem 2.1 is reduction to a large, but finite, number of cases. A computer program is used to generate and do each case. This chapter will describe the theoretical background of both the reduction to cases and of what is done with each case. The next chapter will describe the computer program which implements the work of this chapter. Sections 1 through 4 of this chapter are in direct correspondence with sections 1 through 4 of the following chapter. §1 Passable Points and Sufficient Sets To prove Theorem 2.1 we will need to employ methods from linear algebra, combinatorics and analysis. We start by using linear algebra to translate the problem into the setting of an inner product space. The methods employed in this work will apply to any cyclotomic field of prime modulus, so we will work in that generality. From now on, m will be an odd prime number, C, = C». will be a primitive mth root of unity, R will denote Z [C], and K will denote 10 its quotient field Q(C). K is a vector space of dimension 2s over Q, where 2s = m-l. We will let d be a fixed positive integer. This number d will determine the size of the subdivision to be carried out. Let G be the Galois group of K/Q. G is isomorphic with the multiplicative group of Z/mZ, where we will write 6 = 0,- when o(§) = CI. Note that 0} 0;; = 0}], and that 0.1 is complex conjugation, so denoting the complex conjugate of x by x—, we have that O'.j(x) = o_j(x) = 0,-( 7). Definition 2.2. For each x e K define the norm map \II by 2s 3 s We) = Hojtx) = Haj-(mam = HI up) :2. j=1 j=1 j=1 Note that \ll(x) is positive definite: that is, w(x) 2 0 with w(x) = 0 only if x = 0. Further, if x e R, then w(x) e Z. Thus w(R) is contained in the set of non-negative integers, a well ordered set. We now define an inner product on K. Definition 2.3. For x, y e K we define the inner product of x and y, also called the trace form, by 2s (x.y)=TraceK/Q(x-y—) = 21 0'j( x-T). J: Note that the trace form is a rational bilinear symmetric positive definite form on K. Note also that for the elements C1, . . . , C", which span K as a vector space over Q, (C‘.U)=m5ij-l. (2.4) 11 where 5ij is the Kronecker delta. Definition 2.5. Let the fundamental cell, F, consist of those vectors in K which are closer to the origin than to any other point of R. That is: F = {xe K: forallqe R, llxllSllx-qll }, where Il-II is the distance metric induced by the trace form. Note that (4,4) T llxllSIIx-qll ifandonlyif(x,q)s (2.6) We also have the following elementary lemma which explains why the fundamental cell is called "fundamental". Lemma 2.7. For each x e K there exists p e R such that x—p e F. Proof. In the topology induced by the trace form on K, R is a discrete subset. Thus forx e K the set {llx - rll: re R} has a minimal element, say llx-p II. We will show that for this p, x-p e F. To do this, let q s R be arbitrary and set r = q+p. Then llx-pll s llx-rll = ||(x-p)-(r-p)l| = ||(x-p)-qll, so that the conditions of Definition 2.5 are satisfied and x-p e F. 12 Definition 2.8. Let S be a subset of K, a e Q and x e K. Define the sets (XS andS+xby 0tS={0ts: seS} and S+x={s+x: 565}. For our fixed positive integer d, we define translates of a shrunken fundamental cell. We are interested in bounding translates of the norm function w on each of these regions. Definition 2.9. For each x e K, define the set F; by F; = (d'1)F +x. The following definition is one of the two central concepts necessary to prove Theorem 2.1. Definition 2.10. We will say, for x e K, thatx is passable when there exists aqe Rsuchthatforallze waehavew(z-q)< 1. An immediate consequence of the above definitions is the following lemma which says that the property of passability is well behaved under translation by elements of R. Lemma 2.11. For each x e K and p e R, if x is passable then x + p is passable. Proof. Assume that x is passable and let r e R be chosen so that for each w e F x we have w( w-r ) < 1. Consider z e F x+p. As F (xv) = (Fx)+p, we have that z-p e Fx. Hence \II( (z-p) - r) < 1. Thus letting q = p+r, we have that there exists q e R such that for each 2 e Fx+p, w( z-q ) < 1. 13 We develop the concept of a sufficient set S. This is the second of the two central concepts necessary to prove Theorem 2.1. Given Such a set S we will reduce the proof of Theorem 2.1 to the proof that all elements of S are passable. Definition 2.12. Let S be a subset of K. We will say that S is sufficient when the following implication holds -- for R to be euclidean with respect to the algorithm w, it suffices that every element x e S is passable. For computational reasons, we are interested in finding a small sufficient set S. To start with we have: Proposition 2.13. 51 = (d'1)R is sufficient. Proof. Assume that each x e (d'1)R is passable. We need to show that R is euclidean. Let a e R and b e R be given with b ¢ 0. Let 2 = a/b. Noting that Lemma 2.7 says K = U{F+p: p e R}, we can choose p e R such that dze F+p. Then letting x = p/d we have x e (d'1)R and z 6 F1. As x is assumed to be passable, there exists a qe R such that w( z-q)< 1. Setting r =a-bq, then a = b q+r and z-q = (a/b) - q = (r/b) so that w( r/b)< 1. Since w is multiplicative, we have that ty( r) < ‘l’( b) and R is euclidean with respect to the algorithm w. Thus 51 is a sufficient set and Proposition 2.13 is proven. We can get a smaller sufficient set 52 in the following manner. Proposition 2.14. The following set, 32, is sufficient. $2 = (d-1)R (W F. 14 Proof. Suppose that each element of $2 is passable. We need to show that R is euclidean with respect to the algorithm w. Let 51 be the set of Proposition 2.13 and let x e 51. Using Lemma 2.7 select p e R such that x-p e F. As x-p e 52 then by hypothesis x-p is passable. Thus Lemma 2.11 says that x is passable. Hence all elements of 51 are passable. Since 51 is sufficient, we conclude that R is euclidean with respect to the algorithm \y and that $2 is sufficient. The following lemma, due to H. W. Lenstra, Jr., gives an upper bound for the radius of the fundamental cell for any prime modulus m. The bound given is the exact radius, although we will not need that fact. Lemma 2.15. [Le2, Proposition 3.1] For every x e F we have "X's/1171‘" (2.16) Note that Lemma 2.15 shows that F is a bounded set. Thus since S2 is a discrete subset of F, 52 is a finite set. Using (2.16) and the arithmetic-geometric mean inequality we can refine $2 to the next set S3 which is somewhat smaller. The following definition and lemma will be used to define S3. Definition 2.17. Define the real number L by _2___ L=~1m-1-13 m—D—l. (2.18) Lemma 2.19. Let x e K. If "x II < L, then x is passable. 15 Proof. Letx e K be such that llx II _ 0. Further, using (2.29), m m m x=x-0 = 2 YiCi-sz C‘ = 2n?- l=l t=1 i=1 Next we prove uniqueness. Suppose that x1, . . . , xme Q and y1, . . . , yme Q both satisfy (2.26), (2.27), and (2.28). Then by (2.26), m 0 = ,2“ xr-yt') Ci 3 = But since m is a prime number, (2.29) is the only relation which the zetas satisfy. Thus we have that (x1 -y1)=. . . =(xm-ym)- ' (2.30) 18 Since by (2.28) there exist j and k with x; = 0 and yk = 0, and since by (2.27) we have x,- 2 0 and y,- 2 0 for each i, we can conclude from (2.30) that (Xi'Yi)= (Xj‘Yj)=')’j50 and (Xi‘J’i ) = (Xk-Yk ) =sz 0. Thus x,- = y,-, and we have shown uniqueness. This concludes the proof of Lemma 2.25. Note that forx e K with x1, . . . , xm e Q satisfying (2.26), (2.27), and (2.28), xe Rifandonlyifxie Zforeachi. Definition 2.31. Let x e K and let x1, . . . , xm 6 Q satisfy (2.26), (2.27), and (2.28). When this holds, we say that x1, . . . , xm is the standard form for x. The following definition will be of use in generating elements of S3. Definition 2.32. Let x e K and let x1, . . . , xm be the standard form for x. We will call x reduced when x; < 1 for all i. - Note that by the uniqueness of the standard form, the concept of reduced depends only on x and not on its standard form. We have the following Lemma concerning reduced points and the fundamental cell Lemma 2.33. Let x e K. If x e F, then x is reduced. 19 Proof. Let x1 , . . . , xm be the standard form for x where xj =\0. Let p = -U. Then p e R, so that, applying Definition 2.5 and equation (2.6) for this p, we can conclude that m 211x,- s ”‘71. (2.34) Similarly, let p = 0* where k is chosen such that xk = max{ x,- }. Then, applying Definition 2.5 and equation (2.6) for this p, we have ' m mxk- 2 x; S $. (2.35) i=1 Combining (2.34) and (2.35) we have m mxk S [2 xi]+ "’4le m- 1, I: and thus x is reduced since xiSmax{xi] =ixk S 1-% . This concludes the proof of Lemma 2.33. The above results show that the sufficient set S3 is a subset of the set of reduced points belonging to (d‘1)R. Thus to generate all points of S3 it certainly suffices to generate all the reduced points belonging to (d'1)R. This is the technique which will be employed. 20 Next we introduce the concept of the pattern of a reduced point of (d1)R. Definition 2.36. Let x e (d‘1)R be reduced. Let x1,. . . , xm be the standard form for x. For j with 0 S j < d, define a} to be the number of indices 1' such that x,- = j/d. We will write a = (a0, . . . , ad-1) and say that a is the pattern for x. Note that by the definition of standard form there exists some index j with xj = 0, hence a0 2 1. It is also immediate that m 1 d-l 2 x. = 3 ,2 J a, l: I: and m 1 d—l 2 = _ 2 E1“ 42 £01 “1 (2.37) (2.38) (2.39) The length restriction from Definition 2.17 for membership in S3 can now be computed from the pattern of a point. 21 Lemma 2.40. Let x e (d'1)R have pattern 0. Then 1 d-l d—l llxllz=fi[m.z jzaj-[ ZjajT J. (2.41) 1=0 J=0 In particular, if x 6 S3 then a1 d1 2 - (dL)2 s m .2 1'2 a,- - [ 201' a,-]2 s. d2 "in—1. (2.42) 1=0 j= Proof. Since (2.4) gives (2.38) and (2.39) yield (2.41). Lemma 2.15 and the definition of S3 in (2.24) yield (2.42). §3 The Fundamental Cell and Patterns This section will establish that whether a reduced point, x e (d'1)R, belongs to the fundamental cell is determinable solely from the pattern, a, of x. Basic to working with patterns is the symmetric group I‘. We will define F and give important examples and elementary properties of these permutations next. 22 Definition 2.43. Let I‘ be the mth symmetric group, i.e., the set of permutations of {1, . . . , m}. The group F acts on the vector space K in the following manner: For xe KandPe l‘with m x = z xiCj, i=1 we define P(x) to be m p(x) = 2 xi (3P0), (2.44) i=1 Each P e I‘ acts linearly on K. This action is well defined, for it respects the relation (2.29). That is, m m P(0>= P( 2 U) = 2 W) = 0. (2.45) i=1 i=1 Finally, if Q 6 I‘ is such that Q = P4, then m P(x) = 2le ti. (2.46) 1 = This is to say that each P e F acts on K by permuting the spanning set C1, . . . , Cm, hence the coordinates of each x e K with respect to this spanning set are permuted by P4. 23 Note that the set of reduced x e (d'1)R with given pattern a is precisely an orbit under the action of I‘ on K. Patterns are invariant under permutations. In general, any property which is invariant under all permutations is a property which depends only on pattern. Note also that the galois group G acts on K as a group of permutations. In particular, recalling that O'flC) = C}, then for x e K with m x = 2 xi 0'. i= 1 we have that m 0,-(x) = 21x.- C01 1 = Thus as a permutation, 61(1) 5 ij modulo m. Hence we may think of G as embedded in F. The other important example of a permutation on K is multiplication by C. That is, forxe K with m x = inci, i=1 24 we have that m CI = 2 It Ci“- i= 1 Thus multiplication by I; can be realized as the permutation P e l‘ where P(i) .=. i + 1 modulo m. This can also be thought of as a circular shift of the coordinates xi. The above permutations generate the affine group modulo m. This group will play a significant role in the next section. Definition 2.47. We will define A, the affine group modulo m, to be the group of all P e I‘ satisfying, for a, B e Z, with (a,m) = 1, P(i) 5 ion 4» B (modulo m) (2.48) It is immediate that the affine group A is generated by the galois group G and multiplication by C. The following lemma concerning the symmetric group I‘ is of note. Lemma 2.49. I‘ is a group of isometries for the trace form. That is, for each x, y e KandPe I‘,(x,y)=(P(x),P(y)). Proof. Since C1, . . . , Cm span the vector space K, it suffices to show that (030') = (P(Ci).P(cj')). But (Pay), 13(0)) = ( ch’ CAD): mapwpo') ‘ 1: msij ' 1: (Ci: Q ) 25 We will uncover some relationships Jetween the fundamental cell F and the symmetric group 1". First we show that F is F-invariant Lemma 2.50. Ifx e F andP e I‘ then P(x) 6 F. Proof. Let x and P be as above and note that by the previous lemma we have II 1: II = II P(x) ll. Note also that R is invariant under P: that is, if q e R then P(q) e R and P'l(q) e R as well. Thus for an arbitrary q e R we have ||P(x) ll= le IlSlIx-P'1(q) ||= llP(x-P'l(q)) Il= IIP(x) -q|l. Thus from definition 2.5, P(x) must be an element of F, and the proof of Lemma 2.50 is complete. Next we shall work on a series of computational results which will enable us to determine membership in the fundamental cell entirely from a point's pattern. To start this process, we will need a better characterization of the fundamental cell. The following collection of elements of R, defined by H. W. Lenstra, Jr. in [Le2, p461], will be of use. Definition 2.51. For every subset A of {1, . . . , m}, define eA to be Q4: 2 Ci. £511 The relationship between the points eA and the symmetric group F is given in the following elementary lemma. 26 Lemma 2.52. For every subset A of { 1,. . . , m} and every P e I‘, P(eA) = eP(A)' Next we have the exact description of the fundamental cell. The following lemma states that the fundamental cell is the intersection of half spaces determined by the e A. Lemma 2.53. [Le2, Lemma 3.3] Let x e K. Then 1: e P if and only if for every subsetAof{1,. . . , m}, (x, eA) 3 9563—841. (2.54) The following two definitions and lemma give a preliminary computational method of determining membership in the fundamental cell. Definition 2.55. Let x e K, P e F, and y =P(x). Let yl, . . . ,ym be the standard form fory. Ifyl 2. . . Zym, we say thatP ordersx and thatyl 2 . . . 2y”, is an ordering of x. Note that by the uniqueness of standard form guaranteed by Lemma 2.25 and by the order relationship yl 2 . . . 2 ym, an ordering y1 2 . . . 2 ym is uniquely determined by the point x although the permutation P may not be. Definition 2.56. Let x e K and let yl 2. . . 2y", order x. For k with O S k S m, define the function gx(k) by m k ngt) = 1921” - ”1,21)’: +54% (257) 1 = l = h. .5“ u 27 Note that since the ordering yl 2 . . . 2 ym is unique, the function gx is dependent only on x and not on its ordering. Lemma 2.58. Letx e Kand letyl 2 . . . By”, order x. Then x e F if and only iffor each k with O S k S m, gx (k) 2 0. Proof. We will use Lemma 2.53. To this end, let A be a subset of {1, . . . , m} containing k elements. Then (eAaeA) =k(m’k)9 and m (x,eA) =m Z Xj-k.2 xi. je A "1 Thus, applying (2.54), we have that x e P if and only if for all subsets A of {1,. . . ,m} wehavethat But the yi's are a permutation of the xi's such that yr, . . . , y; are the k largest of the xi‘s. Further, the sum of all the xi's is the same as the sum of all the yi's. 'Ihus x e F if and only if (2.57) holds and the proof of Lemma 2.58 is complete. 28 In order to apply Lemma 2.58 to patterns, we will need the finite differences of the function gx(k). An elementary computation gives the following lemma whose proof is omitted. Lemma 2.59. For i with 0 S i S m - 1, we have m . - 1 . Agx(l ) = - m yi+1 + fl2—- l +'21Yj' (2.60) J: ForiwithOSiSm-Z, we have A281“) = m(y.-+1-y.-+2)-1. (2.61) Finally, we can translate the concept of belonging to the fundamental cell F into terms totally determinable from the point's pattern. Proposition 2.62. For x e (d'1)R reduced with pattern a, x e F if and only if gx(k) 2 O for the following d + 1 values of k = k,- d - 1 k,-= izjai’ OSde. (2.63) Further, 330:4) = g,(0) = o, gx(ko) = gx(m) = o, and for j with (1.1 s j s '1, , d- 1 8109'): wig-.1) + a,- [1391 “’31- 19.1 + 3,720: 0i} (2.64) I: 29 Proof. Note that kj 2 kj+1, so that k' - l 81:09) = gx(kj+l) + . 12 Ang). l=kj+1 Thus by using (2.60) we have k-l 1 m 8x(kj) = gx(kj+1) + . 2 [Wym + ’12— i + .EIYj} (2.65) 1: 1:16}... Also, for i with kj+1 + 1 S i+1 S kj , we have yi+1 = j/d. Then, since kj - kj+1 = aj, (2.65) yields . 1 m k--1 8x(kj) = gx(kj+i) + 0} [— afi- "L;— + 2 )7]: t i . (2.66) J=1 l=kj+1 andalso k--1 . 1 . '2, i. = 21,-(19.1 + “5—) (2.67) l=kj-i-l Combining (2.66) and (2.67) yields (2.64). Lastly, using Lemma 2.58, we need only show that gx(k) 2 0 for those k with k aé kj for any j. Thus we will suppose that k is such that k =fi kj and that 1 S k S m. But then there is aj with kj+1< k < k} and aj> 1. Also for those 1' with kj+1 < i S kj we have y: =j/d. 'Ihus Lemma 2.59 says that Azgxm = -1 forr' with kj+1 S iS kj-2. But this says 30 that g,(i) is concave downward for i with kj+1 S iS kj. Hence the minimum value of gx(i) must occur at the end points: i = kj+1 or i = kj. By hypothesis we have that gx(kj+1) 2 0 and gx(kj) 2 0. Thus gx(k) .>. O and this concludes the proof of Proposition 2.62. §4 The Final Sufficient Set -- Points from Patterns The preceding sections show that, given a reduced point x e (d'1)R, x is an element of the sufficient set S3 if and only if its pattern a satisfies (2.42), (2.63) and (2.64). These are the last of the checks for membership in the final sufficient set, S, which can be done at the pattern level. It is time to consider all points belonging to a specific pattern. Here the action of the affine group A of Definition 2.47 needs to be taken into account. We have the following lemma which explains our interest in the affine group A. Lemma 2.68. The norm map w is A-invariant. That is, for x e K and P e A we have \V( P00) = \V( x ). (269) Proof. Let 0t, [3 e Z be such that (0t,m) = 1. Let P e A be given by P(t)=ia+B. Then ifxe Kis m x= 211'?) i=1 31 we have that m P(x) = Z x.- CW5). i = 1 But if of e G, we have that m m 01(P(x)) = 2 xi 0'00”” = €13 2 xi CU“ = C15 016(x) i= 1 i= 1 So that, combining (2.70) with Definition 2.2, we have that J=1 23 23 23 mm» = H 01(P(x))= [[11:13] [[11101de Butas 23 =m-1 andm is odd, 23 2113 = B’%"'—1)so modulom. i=1 And, as ((1121) = l, 23 23 II one) = II 0,-(x) = \v(x). i=1 j=1 (2.70) (2.71) (2.72) (2.73) Then, combining (2.71), (2.72) and (2.73) we have ty(P(x))=\V(x) and the proof of Lemma 2.68 is concluded. 32 An immediate consequence of Lemma 2.68 is the following proposition. . Proposition 2.74. Let x e K and P e A. Then x is passable if and only if P(x) is passable. Proposition 2.74 says that the property of passability needs to be determined only modulo the action of the group A. In particular, if S is a A-invariant sufficient set, and S ' is a subset of S consisting of one representative of each orbit in S under the action of A, then S ' is sufficient. It is not clear how to pick a single representative of each A-orbit. However, since A is 2—transitive on {1, . . . , m}, each orbit contains a representative with selected first and last coordinates. These ideas will be made more precise in what follows. The following two definitions will be used to single out one representative of each A-orbit. Definition 2.75. Let a = (a0, . . . , 04.1) be a pattern and j' and j" be integers, not necessarily distinct, satisfying the following three conditions: 0 S j',j" < d, (2.76) aj'Z l & aj~2 1 (2.77) a," 2 2, ifj'=j". (2.78) Then we say that the pair (i'j’)a is a selection for the pattern a. 33 We will drop the subscript for the selection when it is clear which pattern is intended. Definition 2.79. Let (i’J') be a selection for the pattern 0. Suppose that y e (d'1)R is reduced with pattern a. If y = (y1, . . . , ym) in standard form with y1=j’/d and ym=j"/d, we say that y is (i'j") selected. The (1",1'”)a selected points are simply all those points, with a given pattern, which have first and last coordinates equal to j’ld and j"/d respectively. Given a pattern, a, and a selection, (i'J')a, the collection of (j'j")a selected points will be the representatives of the A-orbits. The following lemma says that for each A-orbit, there is a representative which is (i’J')a selected. Lemma 2.80. Let (i’j")a be a selection for the pattern 0. Then for each x e (d'1)R, reduced with pattern a, there exists a Q s A such that Q(x) is (1",1'")a selected. Definition 2.81. For each pattern a, let a selection (i'j”)a be fixed. Let 2: = { ye (d‘1)R: y has pattern a & is (i'j")a selected }. (2.82) This gives us our final sufficient set. . Proposition 2.83. The following set S is sufficient: s = (d-1)R F) F f) {xe K: man} 0 2. (2.84) 34 For any choices of selections, we get a sufficient set, S, in this manner. However, different selections will result in a larger or smaller set. For a fixed pattern, a = (a0, . . . , 04.1), whose points lie in $3, the number of such points is given by the multinomial coefficient: m d—l -1 ( =m! H of!) . (2.85) (10.. .ad,1 =0 Let UT)“ be a selection for the pattern a. Let bj be defined by: aj jaéj'andjaéj" bj= aj—l j=j'orj=j"whenj'=fij" (2.86) a,--2 j=j'=j" ' The number of (j'J")a selected points with pattern a is given by the following multinomial coefficient: d—l -2 '1 ( m ]=(m-2)! [11] 12,-t} . (2.87) b0. . . bd,1 '=o Thus the ratio of number of these elements of S3 to number of elements of S is 1114—) ifj'¢j" , (2.88) 01-: ajn 35 01' if j' = j" . (2.89) Thus, in both cases, we want to choose the selection (1",1'")a such that a," and a]... are minimal subject to (2.76), (2.77) and (2.78). §5 Passing Points -- Finding a Nearby Integer To prove Theorem 2.1, we need to show that all the points in our sufficient set S of (2.84) are passable. Recalling Definition 2.10, we have the following definition. Definition 2.90. Let x e K and q e R. We will say that x is passed by q when for all z e F, we have that w(z-q) < 1. Given an x e S, we can then split the problem of showing that x is passable into the following two parts: Find a q 6 R which might pass x.. (2.91) Given a q 6 R, does q pass x? (2.92) Combinatorial methods will be used to produce q's for (2.91). Analytic methods will be used to decide (2.92). We will discuss (2.91) in this section. To intelligently select q's which might pass a given point x, we will first note that the norm function w is continuous with respect to the trace form. The value of w at O is 36 MO) = 0. Thus \I’ is small in a neighborhood of O. In particular, the proof of Lemma 2.19 shows that if ll 2 l < rim-1, then “1(2) < 1. Thus if q 6 R is such that ll x-q II is small, we can expect that w(z-q) will be small for all z e F 3;. Of course, by Definition 2.5 we have that II x II S ll x-q II for all q e R. Thus 4 = 0 is the place to start. By Lemma 2.53, F is the intersection of the half spaces determined by the eA, where A is any subset of {1,. . . , m}. Thus q = (2,4 are reasonable second choices. However, there are 2'" subsets of {1, . . . , m}, and there are 2'" - 1 distinct such eA, so a certain degree of selectivity is indicated Lemma 2.58 says that to determine if a given x e K lies in F, we need only check gx(k) 2 0 for k = 0, . . . , m. This is equivalent to checking that (Lek) 5%. where ek = 341(k) and where A(k) is a subset of {1, . . . , m} which consists of the indices of the k largest coordinates of x in standard form. This gives the first set of points q 6 R for which (2.92) will be checked. Definition 2.93. Let x e S and suppose that P e F is such that y = P(x) orders x. Define the set N1(x,P) by O m N1(x,P)= {ek'pz ZCP’IU): ISkSm}. r=k+l Note that em}: = O, as the sum is empty. 37 While the actual ordering of any x e K is unique, the choice of permutation P e I‘ such that P(x) orders x is not necessarily unique. This leads to the second collection of "nearby" q 6 R. Definition 2.94. Let x e S. Define the set N2(x) by N2(x) = U{ N1(x,P): P(x) ordersx }. The final collection of q s R which might pass x will be selected more exhaustively. Recalling that the collection of (2,4 is the set of points which in standard form have coordinates chosen from the set {0,1}, we have the following definition. Definition 2.95. Let f be a positive integer. Define the set N3( f ) by: N3(f) = {qe R: q=(q1,. . . , q,n)instandardform&qiSf}. The set of all 424 is thus N3(1). §6 Bounding the Norm w on a Sphere We turn finally to the analytic portion of this work. Given a x e K and q s R, we wish to bound w(z-q) for all z e Fx. We will translate the question into one concerning a function from R3 to R. Our work is a generalization of the work of T. Ojala in [Oj]. First some preliminary definitions. Recall that the Galois group G consists of the isomorphisms O'j, where 01(C) = U and (i,m) = 1, and that 3 = (m-1)/2. 38 Definition 2.96. Let x e S and q 6 R. Define the real numbers C} by Cj = l 01(q-x) | for j where 1 S j S 3. Define the function f,” from R3—)R by S fx,q(21, . . . , 25) = 'H1(6j+2j). 1: Definition 2.97. Let the real number r be given by _ 1 \l m2 - 1 ' - a ‘22— - Definition 2.98. Let the real number M I“ be given by 3 M,“ = sup{ fx,q(z1,...,zs): .2192 S r2 }. I: The following lemma phrases passability in terms of the behavior of the real function fx,q. Lemma 2.99. Let x e S and q e R. IfMM < 1, then x is passed by q. Proof. Suppose that x is not passed by q. Thus there exists a z e P, such that ty(z-q)g 2 1. Since 2 e F, then z-x e Fx-x = (d'1)F. Hence Lemma 2.15 says that llz-xllSéV "Ln-l. 39 Then, noting that 23 S (z-x, z-x ) = 2,11 Oj(z—x) 12: 2121: oj(z-x)12, J: we can set 2,- = I Oj(Z-x) I. Then S .2 ij S r2. J = 1 Since by Definition 2.2 S 2 1 s war-q) = H I o, O for all j. Thus, as 21, . . . , 23 maximizes qu, we have that 2,-2 O and that s Mx'q= fx’q(21, . . . , ZS) = H1(Cj+Zj) > O. I: The gradient of qu is meoe. . . .y.) = ( II (c,-+y,-) . . . .. .l'I ). (2.110) J#1 J¢s Thus fo,q(zl, . . . , 23) at 0, and the maximum of fm must occur on the boundary of the sphere of radius r. Thus 2 z-2 = r2. i=1] La 3 801,. . . .ys)= (Zlyjzrrz. (2.111) J: Then 21, . . . , zs is the maximum of fm subject to the constraint g = 0. Thus there exists a Lagrange multiplier A if 0 with fo,q(z1,. . . , 25) = AVg(21, . . . , zs). 42 But this yields, for 1 S i S 3,-that H (Cj+zj')) = 212i. 1 So, forlSiSs, S Mm: fx,q(zl,. . . , 2,) = .H1(c,-+zj) = 27tz,(c,~+z,-). (2.112) J: As the left hand side of (2.112) is independent of i, (2.109) follows and Lemma 2.106 is proven. Next we have a proposition which will give an algorithm which is used in practice to compute an upper bound on M 1.4: Proposition 2.113. Let x e S and q 5 R be such that x-q if: 0. Let z1, . . . , 23 be real numbers such that 212 + . . . + 252 S r2 and fx,q(z1, . . . , 25) = M1“. Let the index k be chosen such that c = ck = min{cj} and let [3 be a positive real number. Let the positive real numbers [3} be defined by, for 1 S j S s, Bj(Bj+c,-)=B(B+c). (2.114) Let the positive real number 7 be defined by 1/2 s - _ 7: r13 [121512) . (2.115) 43 Then 2]: S [3 implies that 2k 2 y, and Zk 2 [3 implies that zk S 7. Proof. Using Lemma 2.106 we have that y = z}- and x = Z], satisfy the hyperbolic relation y(y+61)=X(X+c). (2.116) An elementary computation yields that $3: 723—; (2.117) £22- 0'2-62 dxz- 2W. (2.118) Since (:1: 2 c, the graph of (2.116) is increasing and concave upwards in the first quadrant. Further, (2.114) says that the point (x,y) = (13,131) also lies in the first quadrant on the graph of (2.116). If I]: S B, the above remarks show that the secant line from the point (0,0) to the point ([3,8]) passes above the point (stlj) on the curve. Thus “I? IV ale and hence Zj S ifm. But then sothat S -1 21:2 2 '25“ 2 1512) = 72- i=1 The remaining case is done by reversing the inequalities in the above argument. This concludes the proof of Proposition 2.113. Proposition 2.113 gives a method for translating upper bounds on 2k into lower bounds, and translating lower bounds into upper bounds. As each 2,- is an increasing function of 21:. this gives upper and lower bounds on all of the zfs. Thus we have both bounds on M m- Lastly, we have a proposition which will enable us, working from an arbitrary positive real number, to get bounds on Mm- Proposition 2.119. Let x, q, c, B, and B,- be as in Proposition 2.113. Let the positive real number A be defined by S 1/2 7t: (1'2 8,2] . (2.120) 1.er Athen Mx’q Sfx'q(B1, . . . , B3). conversely, iffZ 2.111611 Mx'q fo’q(Bl, . . . , B5). 45 Proof. Equation (2.114) defines each Bj as a continuous, strictly increasing function of B. Thus equation (2.120) defines A as a continuous, strictly increasing function of B. Since 21,-)0 as B—>O and 1-900 as B—)°°, there exists a unique value of B, call it Bo, such that the corresponding value of 3. is equal to r. Conversely, let 21, . . . , 25 be real numbers such that z12 + . . . + 232 S r2 and fx,q(21, . . . , 23) = MN]. Let 2 = max{Zj}. Then by equations (2.107) and (2.109), if k is an index such that z = 2k. then c = ck. Thus from equation (2.108), B0 = 2. Further, as A is an increasing function of B, B < 2 if and only if 3. < r. But equation (2.127) defines fx,q(B1, . . . , B.) as a function of B, and it is clear that this is also a continuous, strictly increasing function of B. Thus B < 2 if and only if fx,q(Bl. . . . . B5) O }. If 1' = (H then b is maximal. Else, when i< d—l, define the d-tuple C=(co.....Cd-1)by bj j>i+l bjil j=i+1 Cj: 0 O < j Si (3.08) bi-l j=0 Then c is the essential pattern that is the immediate successor of b. Proof: Ifi= d-l, then b= ( O, . . . , 0, m-l )which is clearly maximal. 52 For the other case, note that by the definition of i, b,- is positive, so that all of the cj's are non-negative integers. Further, from (3.08) and the definition of 1’, Ci: 0 for O i+ 1 and bi“ < cm, we have b < c. Thus c is a successor to b. We need show that it is the immediate successor. Thus suppose that e=(eo,. . . ,e44)isanessentialpatternwithbSeSc. Since bj = c; for j > H 1, we must have bj = e,- = C} by Definition 3.06. Similarly, since bi+1 + 1 = cm, we have two cases. Case 1. bi+1 = em. In this case we will show that b = e. To see this note that b}: e; forjz i+l. Hence since b S e, then b,- Seg. But forj < i, we have that bj=0. Thus d—l d1 2e}: S 2e} =m-1. d1 -1 - m-1= 2b}: 2111-5 ' =i J=l j=0 J=0 1' Hence equality holds throughout. In particular, 1-1 2 e; = 0. J=0 53 But as 8} .>. 0, this implies that for j < i we have e,- = 0 = bj. Thus we have that ej = bj for jqé iand hence ei= bi, and thus e = b. Case 2. ei+1= ci+1. In this case we will show that e = c. We will argue by contradiction and thus suppose that e < 0. Define k = max{ j: ej at cj }, so that ek < ck. Note that since both the refs and Cj'S add up to m-l, we have that k > 0. But by the case 2 assumption, k S 1'. Thus using (3.08) we have that 0 S ek < ck = 0 which is impossible. This completes the proof of Proposition 3.07. Proposition 3.07 gives the method used for computing the next pattern. First i=min{ j: bj> O} is computed. Then the next essential pattern is generated by incrementing bi“, setting bo equal to bi-l, and, if i > 0, setting bi equal to 0. We also have the relationship between the old and new values of sum and ssum, whose proof, being immediate, is omitted. Lemma 3.09. Let a be a pattern and let sum and ssum be defined by (3.01) and (3.02) respectively. Let b be the essential pattern for a, define 1': min[ j: bj > O }, and suppose i< d—l. Let the values of sum and ssum for the immediate successor to a be denoted by newsum and newssum respectively. Then newsum = sum + (i+1) - ibi (3.10) and newssum = ssum + (i+1)2 - izbi. (3.11) 54 Lemma 2.40, Definition 3.04, and Proposition 3.07 show that the pattern generator, when started with the machine starting pattern, returns the pattern of all points in our sufficient set. §3 Checking The Fundamental Cell The cell checker determines whether a pattern lies within the fundamental cell or not. Recall that the sufficient set S consists of points x e K which satisfy the four restrictions: (i) x e (d‘1)R, (ii) llx IIZL, (iii) x e F, and (iv) x e 2. As the pattern generator only returns patterns satisfying (i) and (ii), this cell restriction is the last one computable in terms of the pattern of a point. Further note that the pattern generator only returns patterns of reduced points. As Lemma 2.33 says that all members of the fundamental cell F are reduced, no points of our sufficient set S will be skipped by considering only reduced points. The cell checker is called with five input variables and one output variable. The input variables are: m, d, a, sum, and pflag. The meanings of m and d are as usual. The variables a and sum are defined in the pattern generator and have the same meanings here. The variable pflag is a logical variable to control the printing of debugging information. The output variable is flag. This is a logical variable whose value indicates whether the pattern lies in the ftmdamental cell or not. The cell routine has two entries: scell for initialization purposes and cell to perform the actual checking. The initialization section scell simply stores the values of m-l and (H in m! and d1 respectively. 55 The cell checking section cell is based on Proposition 2.62. The d-l values of k, defined in (2.63), are computed starting with kd-1 and ending with k1. Translating (2.63) into a recursive statement, we get ’9': of + kj+1. (3.12) In order to use only integer arithmetic, the routine calculates h = d*gx instead of g; (the division by 2 in the definition of gJr will be taken care of momentarily). As we need to check if gx is non-negative, this will not affect things. Writing h(j) = d*gx(k,-), equation (2.64) translates into h0')=h(i+1)+aj(3um + day-al- m j - d kj+1). Now using (3.12) we can recursively define h(/) by ho)=h(i+1)+91%"ifi’ll-ajmjmkj-sum). (3.13) Note that since m is odd, 0} ( m + aj) is even, so this is indeed a calculation which can be performed using integer arithmetic. Thus the cell checking routine initializes k and 1: equal to 0 and j equal to (11. Then it calculates the next values of k and h using (3.12) and (3.13). If his negative, then the pattern a cannot lie in the fundamental cell and the routine returns with flag set equal to .false.. Else j is decremented. If j is less than 1, all checks have been successfully passed and the pattern a does lie in the fundamental cell. Thus flag is set equal to .true. upon return. 56 §4 The Point Generator The point generator generates all points of the sufficient set S which have a given pattern. To do this, it first makes a selection for the pattern which is designed to minimize the number of points to be generated. Then the routine generates all points in lexicographic order with this pattern and selection. The final restriction on membership in the sufficient set is thus accounted for by this routine. Definition 3.15 and Proposition 3.21 are from [R, sect. 2.17, pp 65-67]. They have been slightly modified to handle the repetitions of coordinates in points with a given pattern. The proof given for Proposition 3.21 was suggested to us by B. Sagan. Additional sorting calculations have been intertwined with the combinatorial algorithm in order to minimize the running time of the program. The point generator is called with four input variables and three output variables. The four input variables are m, d, a, and pflag with their usual meanings. The pattern a has already been passed by the cell checker. The three output variables are x, sort, and flag. The integer array x holds the coordinates of the point returned. These coordinates are multiplied by (I so that they are integers. The integer array sort is used to order the coordinates of the point in x. The logical variable flag indicates if all points have been generated or not. The significant internal variable is mart. This is an integer array and is the inverse of sort. It is used to compute the new value of sort for the next point generated. The point generating routine has two entries: (i) spoint for initialization purposes, and (ii) point to generate the next point. 57 The initialization section spoint is called once for each pattern. It makes the selection for the pattern and generates the starting point. Recall that a selection ( j'. j " )a for a pattern a = ( a0, . . . , ad.1 ) is a pair of indices, not necessarily distinct, such that: aj’Z 1 & aj"21 "j'aéj" 'I' af22 j'=_] As remarked in the previous chapter, the number of points generated is minimized by choosing a selection ( j', j" ) which minimize a," and of subject to the above restriction. Thus the initialization section first searches for indices 3 and 33 such that as is the smallest positive of and ass is the second smallest positive a}. If as > 1, then the selection chosen is (j',j")= (s, s ). Else as =1 and the selection chosen is (j',j")= (s, 33). In both cases, x1 is set equal to j' and xm is set equal to j”. These coordinates remain fixed throughout the generation of all ( j', j ") selected points by the pattern generator. Next the middle coordinates x2, . . . , xm-1 are filled in in weakly increasing order: that is with sz. . . Sxm-1. Then the array sort is computed. This array orders the coordinates of the point x, such that xsort(1) 5 xsort(2) S . - - 5 xsort(m)- Next the inverse array mort is computed. The final action of the initialization section spoint is to set flag equal to .true. and return to the calling program. The next point section point generates the next point x and the new values of mort and sort for this point. The points are generated in lexicographic order. If there are no more points for this pattern, the variable flag is set equal to .false. and the program 58 returns. Else the next point is created by successively transposing coordinates. During the creation of the next point, the arrays mort and sort are updated. In order to verify that all points for the pattern a are considered, we will need the following ideas. Definition 3.14. Leta be a pattern and ( j ', j ") be a selection for the pattern a. The set of all x e (d'1)R which have pattern a and are ( j ', j ") selected will be denoted 9. Throughout the remainder of this section, for each x e 52 we will let x1, . . . , xm be the standard form for x. Note that for each x e 9, since x is ( j', j”) selected we have x1 = j'ld and xm = j"/d. In particular, each x e (2 is uniquely determined by the middle coordinatesxk for2Sk Sm-l. The following definition parallels that of Definition 3.06 and totally orders 9. Note that this ordering is, for no good reason, from the opposite end of the m-tuple. Definition 3.15. Let x e Q and y e D . If x #y we define k =min{ i: xnéy; }. Then ikaxg }. Note that since x,- < n+1, jx is a maximum over a non-empty set and hence well defined. Also we have is < jx < m. 60 Proposition 3.21. Let xe Qbenot maximal. Leti=ix andj=jx. Lety e K be defined by first interchanging the coordinates x,- and xj, and then by inverting the order of the (i+1)St through (m-l)St coordinates. That is, y= ( y1, . . . , ym ) where xk 1 S k 2. Hence 21' is an element of the tail of x larger than xi. It must be the smallest such, since any larger choice makes 2 > y. Thus zi =xj = y,- as claimed. Finally, in z we must arrange the remaining elements of x in weakly increasing order (if not, z > y as before). But the remaining elements of y are in weakly increasing order, since swapping x,- and x; leaves the tail in weakly decreasing order, and then y is 61 obtained by inverting the order of these elements. Hence 2;, = yk for k > i, and Proposition 3.21 is proved. Note also that inverting the order of the (i+1)St through (m-l)St coordinates can be accomplished by interchanging the (i+l)St and (m-l)“ coordinates, then interchanging the (i+2)"d and (m-2)"d, and so on. Proposition 3.21 gives the method used to compute the next pattern. First i = is and j = jx are computed. Then x,- and x; are swapped. Then the loop to invert the tail is initialized by setting i equal to i+1 and j equal to m-l. Then whilst i< j, x,- and x; are swapped, i is incremented, and j is decremented. Lastly, we handle the updating of the arrays sort and mort. First note that sort is a permutation of the indices { 1 , . . . , m }, and recall that the permutation group I‘ acts on K by permuting the C's -- not the coordinates xi. Thus, as mort is the inverse of sort, we have that mart is an ordering of x in the sense of Definition 2.55. We need to keep track of orderings under the action of the permutation group I‘. The following lemma is immediate. Lemma 3.23. Let x e K and Q e F be a permutation such that Q orders x. Let P e I‘ be any permutation. Then QP'1 orders P(x). A quick consequence of this is the following lemma which tells how to update sort and mort when two coordinates of the point are interchanged. 62 Lemma 3.24. Let x e Q. Let mart be a permutation which orders x. Let i and j be distinct integers with 1 < i, j < m. Let y 6 Q be obtained from x by interchanging x,- and xj. Let newmort be the permutation which orders y. Then mort(j) k = i newmort(k) = mort(i) k = j (3.25) mort(k) else Lemma 3.24 shows how to update mart and hence sort as x is changed, since x is modified by repeated transpositions. Then the inverse relationship sort is updated by setting sart(mart(i)) = i and sort(mort(])) = j. §5 The First Checker The first checker attempts to pass the point x. It uses the ordering computed by the point generator to create the set of m "nearby" integers N1 of Definition 2.93. It uses single precision complex arithmetic and a single iteration of the algorithm implicit in Proposition 2.113 to bound the M“, of Definition 2.98 for each q 6 N1. As a starting value for Proposition 2.113 it uses B = rNE where r is defined in Definition 2.97. To account for floating point error, it will pass x only if it computes that MM < 0.99. The code for the first checker has been written with a view towards minimizing execution time. Thus many invariant calculations are performed outside of loops and stored in temporary locations. The first checker is called with five input variables and two output variables. The five input variables are m, d, x, sort, and pflag. The meanings of m, d, and pflag are as usual. The integer arrays x and sort contain the point to be passed and sorting 63 information respectively. They were created by the point generator. The two output variables are flag and count. The logical variable flag indicates if the point x is passed. The integer variable count counts the number of times M m is bounded. The first checker can be entered at schekl for initialization purposes, or at checkl to try to pass a particular point. The initialization section schekl computes internal constants for use with all points and then returns. The eight significant internal constants are radius, lower, lawer4, lowrad, bound, bndZs, e, and ed. The double precision constant radius is set equal to the r of Definition 2.97 . The real constant lower is set equal to rNE, the starting lower bound for Proposition 2.113. The real constants (mean! and lowrad are set equal to 4*Iower and 2*lower*radius respectively. These are computed here as they are used inside loops later. The real constant bound is set equal to 0.99. This is the upper bound used to pass points. The real constant bnd23 is set equal to bound*2~", as, to speed execution, what is actually bounded is (23mm. The complex array e is set equal to the 11" conjugate of the ith power of C: 803/) = 01(0) = C”- The complex array cd is set equal to e/d. The point passing section checkl is called to try to pass the point x. The first task is to convert the integer array x into a complex array xq, where xq(i) = cfix-q), and q = O. 64 Recall that the integer array x consists of the coordinates of x multiplied times d. That is, x(i) = d-x; where x1 , . . . , xm is the standard form for x. Thus for j with lSjSa m m xq(i) = 0,-(x-0) = 2 xiCif = 2 x(i)*ed(i,j). i=1 i=1 Next comes the main loop. This computes an upper bound on (25)Mx,q for q 5 N 1. At the head of the loop count is incremented. Next xq is updated to handle the next qe N1. To understand how to get the next q 5 N1, recall that mart orders x in the sense of Definition 2.55 and that sort is the inverse of mart. Recall also that, N1=13i,mart315i5mi where m ei,mort= 2 930"“)- ' k=i+l Thus we have the recursive relationship, for i < m, of ei,mort = ei+l,mort '1' Csort(i+l) - (3.26) 65 Thus if it is not the first time through the loop, the new value for xq(j) is computed from the old by subtracting oj(C30"(i+1)). That is, if i < m, the first checker redefines 1:40) by xq(j) := xq(j) - e(sort(i+l),j). Next c(i). the magnitude of xq(j), is computed. Concurrently with this computation, the minimal c(j) is determined and stored in cmin. Next comes the calculation applying Proposition 2.113. This computes an upper bound for 2):. Recall that k is an index such that 2k = max{Zj}. Thus 21‘ 2 lower. Solving (2.114) for B} yields that 13‘ _ '6')“ + ‘1 612 + 4*lower*(cmin+lower) J - 2 We store in temp] the value independent of j: temp] := 4*lawer*(cmin+lawer) = lower4*(cmin+lawer). What is computed is not Bj but temp2 = 2B,; Thus we set temp2 := -c(j) + \/ c(j)*c(j) + temp] 66 Define length by S S length: 201392 = 2 (temp2)2, j: 1 j: 1 then Proposition 2.113 says that 2*lower*r _ lawrad \(length - 1] length ' This upper bound for Zk is called upper. Next upper bounds for the zjs are calculated along with an upper bound, ubound, for the value of (20%“. This can be done as (2.109) defines zj as an increasing function of 21;: ._ -ci + \( c;2 + 4*zk*(cmin+zk) Z] — f . Using temp] as before, temp] = 4*upper*(cmin+upper), we conclude that 2(2j + 6}) S ej+ \/ (:12 + temp] . 67 Thus, defining ubound by ' s ubound= H ( c(j) + \/ c(j)*c(j) + temp] ), j=1 we have that S (2S)Mx,q= (2%,,(21 , . . . ,zs) = [I 2(zj+c,-) s abound. 1' = 1 Finally, if abound is less than bndZs, the point passes. That is, flag is set equal to .true. and the first checker returns to the calling program. Else the first checker loops for the next q 6 N1. IfN1 has been exhausted the point has not passed. Thus flag is set equal to .false. before the first checker returns. §6 The Second Checker The second checker attempts to pass the point x. It computes the set N2 of Definition 2.94. Then, for each q 6 N2, the actual bounding of M x.q is done in the separate routine named slick. The strategy of using separate checkers minimizes the running time of the program. The earlier, less exhaustive, checkers are also faster. Only when it is clear, by flunking the previous checker, that more attention is needed to pass a given point, is that point turned over to the next checker for a more detailed examination. 68 The second checker is called with four input variables and two output variables. The four input variables are m, d, x, and pflag, and the two output variables are flag and count; all with the usual meaning. The initialization section schek2 computes two internal constants for later use and then returns. To understand the operation of the point checking section check2 we will need the following ideas. Throughout the rest of this section, the point x e S will be fixed, with x1 , . . . , xm being its standard form. We start with a definition. Definition 3.27. Let j be such that 0 S j < d. Define the set A] by A}: {1: xi=§ } Note that if x has pattern a = (00 , . . . , as“ ), then a,- is the number of elements in The following pair of definitions will result in the set N2 of Definition 2.94. Definition 3.28. Let j be such that OSj< d. Define pie R and, for each subsetA :Aj, pi“; e R by pj= EC" and FLA: ZU- ieAj ieA 69 Definition 3.29. Let j be such that 0 S j< (1. Define qje R and, for each subset A :Aj, 41,11 6 R by qj= 2p: and qj,.4=pj.A+ 2m. iZj i>j Note that for any two subsets A c; A; and B c A}, we have qjsq - q”; =pjs4 - P133. It is also evident that qo = 0. It is this collection of q's which forms the set N2. Proposition 3.30. N2={qj,A: OSj 1 + 1045, (ii) the algorithm of Proposition 2.113 fails to converge, or (iii) if the algorithm of Proposition 2.113 converges to a value in between 1 - 10'6 and l + 1045. The point passer is called with five input variables, m, d, x, q, and pflag; and one output variable, flag. The integer array q contains the integer q 6 R with respect to which x is to be passed. The point passer has three entries: (i) sslick for global initialization purposes, (ii) xslick for initialization purposes for a particular x, and (iii) slick to try to pass a particular point x with respect to a particular integer q. The global initialization section sslick computes internal constants for use with all points x and integers q and then returns. The eight significant internal constants are radius, radsqd, difbnd, cntbnd, akbnd, nokbnd, e, and ed. _ The double precision constant radius is set equal to the r of Definition 2.97. The double precision constant radsqd is set equal to r2. The double precision constant difbnd is set equal to 1040, a bound to indicate that convergence has occurred. The integer constant cntbnd is set equal to 100, a bound to indicate that convergence has not occurred. The double precision constants okbnd and nokbnd are set equal to 0.999999 and 74 1.000001 respectively. These are the upper and lower bounds used to respectively pass or flunk points. The double precision complex array e is set equal to the 11" conjugate of the :1“ power of C, and the double precision complex array ed is set equal to e/d as in the first checker. Each array is stored as two double precision arrays containing the real and imaginary parts separately. The initialization section xslick is called once for each point x. Its task is to convert the integer array x into double precision arrays realx and imagx. Here the parts of the 11" conjugate of the point x are given by realx(j) := real(oj(x)) & imagx(i) := imag(oj(x)). After the initialization section xslick has been called, the point passing section slick can be called repeatedly for differing q's to try to pass the point x e S. First c(j), the magnitude of oj(x-q), is computed. Concurrently with this computation, the minimal c(j) is determined and stored in cmin. Finally, the starting value of B = r is stored in the variable approx and the number of iterations in count is iniu'alized at 0. Next comes the calculation applying Proposition 2.119. The values of B; are computed and kept in the variable temp2. Simultaneously, the values for length and bound are computed. Here 3 length: 2 B12 i=1 75 and S bound: H ( Cj+ Bj ) =fx.q(Bl ’ - - - i (33) i=1 Then the variable diff is set equal to length- radsqd. This is tested in accordance to Proposition 2.119 to see if we have an upper bound on M x.q or a lower bound. To allow simultaneously for convergence to the true value, we check for an upper bound when diff is greater than or equal to -dijbnd, and for a lower bound when diff is less than or equal to +difbnd. If bound is less than akbnd, then the point passes, flag is set equal to .true., and the routine returns to the calling program. If bound is greater than nokbnd, then the point flunks and flag is set equal to .false. before the routine returns. Lastly, the absolute value of diff is checked. If this is greater than diflmd, then convergence has not yet occurred. Thus a new value of approx is computed, in accordance with Proposition 2.113, by approx "' radius ‘1 length approx := Then the routine loops. Of course, there is a fail-safe limit on the number of iterations so that the routine cannot loop forever. This is stored in cntbnd. On the other hand, if the absolute value of diff is less than or equal to difbnd, then the routine has converged and the value of bound is approximately 1 -- that is, is greater than akbnd and less than nokbnd. As these cases are not decidable, the point is flunked if this occurs. Thus flag is set equal to .false. and the routine returns. Chapter 4 Bounding the Growth of Floating Point Error §0 Introduction The program written to pass all the points of the sufficient set S involves arithmetic of two kinds. The generation of points and patterns uses only integer arithmetic. Thus it is not subject to floating point error. The estimation of the maximum M14 is done in an s-dimensional real vector space and may induce floating point error. The algorithms used in the routines checkl and slick make allowance for floating point error. The purpose of this chapter is to prove that those allowances are sufficient. First some notation to be used throughout this chapter. Real numbers will be denoted by Latin letters (with the exception of our mth root of unity, which will still be denoted by C). Their machine floating point approximations will be denoted by bold Latin letters. In general, the program's names for quantities will be used. For example, the r of Definition 2.97 will be denoted radius, with its machine representation denoted radius. The errors in the machine approximations will be denoted by subscripted e's. The symbol 8 will stand for machine erro -- for the machine on which the program ran, the single precision value of 6 is 2‘24 while the double precision value of 8 is 2‘53 . Subscripted 8’s will stand for arbitrary errors smaller, in absolute value, than the machine error 8. It is assumed that all operations are carried out with extra precision, and that the error occurs when quantities are rounded back to the machine word length. Quadratic error 76 77 terms will be neglected throughout. For the sake of brevity of exposition, equalities will be used when approximations are (technically) meant. A certain amount of preliminary processing of invariant quantities was removed from within loops in order to minimize the running time of the program. For the purpose of analyzing the growth of floating point error, we will assume that these calculations are performed within the loops. Also, the variable names in the following discussion have been slightly modified from the actual names in the program for the sake of clarity of exposition. This chapter will start with two preliminary sections. The first bounds the size of various quantities. The second gives a general error estimation used extensively later. The last four sections deal with the actual numerical calculations. §l Bounding size We assume throughout this chapter that x e S (see Proposition 2.83) and that x1, . . . , xm is its standard form. We will let x(i) be the machine representative for d-xi. Recall that this means that each x(i) is an integer. We will assume throughout this section that q 6 N30) (see Definition 2.95). We first wish to bound lo,(x) I, where of is an element of the Galois group G. Lemma 4.01. 16,-(x) I s %‘1' . (4.02) 78 Proof. Since x e F, lemma 2.15 says ’m2 -l “x H S T. (4.03) But, from the definition of the Trace form, 23 3 ||xll2= Z 16,-(x) 12:2 21610012. j: 1 j: 1 Hence, for each j, 16,-(x) I sLuxn , \/_2 and equation (4.02) follows. Next we wish to bound 6": Icy-(x - q) I. Lemma 4.04. 61.5 Tm '1 .111, (4.05) ‘18 Proof. By Definition 2.93, m 0j(q)= 2 WC". i=1 79 where qi e Z with 0 S q,- Sf. Setting y,- = qi-f/2, we have m Oj(4)= 2 )’i C”. i=1 where Iyi I Sf/2. Thus, 2 m m 2 m2 II o,(q ) II = m .21in - ( fly.) 5 . (4.06) I: l = Thus, combining (4.03) and (4.06), we have that llx-q us \/-’"—1-2'—1—+%i. Hence, in a similar manner as in Lemma 4.01, equation (4.05) follows and lemma 4.04 is proven. A slight modification of the proof of Lemma 4.04 yields the following lemma, whose proof will be omitted. Lemma 4.07. Let cmin = min{cJ-: 1 SjS 3 }. Then cm s N / fi‘ml— s»??? (4.08) Lastly, we need to bound the output of Proposition 2.113. 80 Lemma 4.09. Let approx be a positive real number. Define tem __ —cj + \j c} + 4-approx-(approx+cmg,,) p} ‘ 2 7 3 length: 2 temp ,2 , j: 1 and newa rox _ approx- radius pp \I length Then 92“,“ approx S temp ,- S approx , J 2 2 (approx) S length S s-(approx) , and radius «1? S newapprox S radius . (4.10) (4.11) (4.12) (4.13) (4.14) (4.15) Proof. Letting y = tempj, we have that y is the positive solution to equation (2.116) where x= approx and c = Cmin- Using equations (2.117) and (2.118), we have that the secant line from (0,0) to (x,y) has greater slope than the tangent line at (0,0). Thus 81 the left-most inequality of (4.13) follows. The right-most inequality of (4.13) is clear from (4. l 0). Noting that, for some j, of = ems-n, (4.14) follows from (4.13). Equation (4.15) is a direct consequence of (4.14). Thus Lemma 4.09 is proven. §2 A preliminary error estimation Lemma 4.16. Let a1, . . . , an and b1,. . . , bu be real numbers. Let a(l), . . . , a(n) and b(l), . . . , b(n) be their machine representations with errors given by a(i) - a5: a; and b(i) - bi: 131‘- Let the partial sums be recursively defined by si = 5121+ aibi, s(i) = s(i-1)+ a(i)*b(i), 31 = a1b1, and s(l) = a(1)*b(1). Then the error, s(n) - 3", on the summation can be approximated by: n , n 2 (brat + 0431' + arbi51,i) + 2: 81:52,): (4.17) i= 1 k = 2 Proof: Let t,- = aibi. There exist real numbers 81;, with l 81,,- IS 8, such that: 1(1')=ll(i)"I b(i)=(0i+0li)(bi+l5i)(1+51,i)- Thus, if we define t,- by t,- = t(i) - t;, we have ’t,‘ = aiBi + bias + ‘i51,i . (4.18) Define a,- by 0;: s(i) - 3;. Then, for some 82,,- with l 82,,- IS 8 s(i)=3(i-l)+t(i) =(si-1+0i-1+ti+1:i)(l +521). 82 Thus, O',‘ =O'i-1 + Ii + 3152,; . A simple induction gives n n on: 2 1,4 2 ska”. (4.19) i=1 k=2 Combining (4.18) and (4.19) yields (4.17), and Lemma 4.16 is proven. §3 Initializing the single precision routine checkl We will assume throughout the next two sections that q 6 N1(x,mort) (see Definition 2.93). Note that N1(x,mart) : N3(f) with f = 1. The subroutine checkl does two different things. It runs through those q which belong to N1(x,mart). Secondly, it puts an upper bound on the value of Mm]. It is this process which will be analyzed in the next two sections. A summary of the initializing stages of the algorithm follows. We refer the reader to §5 of Chapter 3 for a more precise description and to Appendix A for the program listing. This section will analyze the following steps. First is an initialization, which is done in double precision with the results rounded back into single precision variables. Next the conjugates of x and of x- q are computed as complex numbers. Then the magnitudes, Cj , are computed. 83 We will follow each result with the values for m = 13, when d = 6 and d = 7. These are the values of m and d for which the program was run. These values will be expressed, except as otherwise stated, in multiples of machine error, 8. We will start with the error on x as a complex number. In order to make the estimate as sharp as possible, we will use the following definitions. Definition 4.20. Let the real number 0 be defined by 0 = 27t/m. Definition 4.21. Let k and j be integers with lSk Sm and 1S sz. We define the real numbers P”, N”, and M I: J by P” = 2 cos(ij0) , (4.22) l 1 S i S k cos(ij0) > 0 Nu = 2 cos(ij0) , (4.23) l l S i S k cos(ij0) < 0 and MAI: max{ Pu; -NkJ'} . (4.24) Lemma 4.25. Let realx(j) be the machine representation of Re(oj(x)). Let 51.}: realx(j)- Re(oj(x)). Then m m teljls%l(2 2 |cos(i0)l+ Z Mk,,)6 Table 1. 81: the error on realx(j). i=1 j d=6 d=7 1 43. 6844 1168 44. 9325 3773 2 40. 6735 2500 41. 8356 2572 3 40. 1307 0182 41. 2772 9330 4 39. 5999 1409 40. 7313 4020 5 39. 1547 1817 40. 2734 2440 6 38. 9436 4966 40. 0563 2537 Proof. We use Lemma 4.16. If the real part of ed(ij) is given by realed(i,j), then the error on this is given by (d'1)cos(ij0) 81,“, as cd is calculated with double precision and the result rounded back to a single precision quantity. Thus, as m realx(j) = 2 x(i) "' realed(isi) . i= 1 the error on the summation can be approximated by m m k 2 xicos(ij0)(81,iJ+82,iJ)+ 2 [2 xicos(ije)]83,kj. (4.27) i=1 k=2 i=1 85 Now, the first term of equation (4.27) is bounded by i=1 d1 m 27}[ 2 lcos(i0)| ]8 (4.28) To bound the second term of equation (4.27), we need to bound the quantity k | 2 x,- cos(ij0) I (4.29) i=1 But (4.29) is maximized when there is no additive cancellation within the summation. That is, for some choice (+ or -) of sign, x; is (d-1)/d for those values of i when cos(ij0) has that sign, and x,- is 0 for those values of i when cos(ij0) has the opposite sign. Then Definition 4.21 yields that the second term is bounded by m £314 2: MN) 5- (4°30) k=2 Combining the bounds (4.28) and (4.30) with the error (4.27) yields (4.26). Thus Lemma 4.25 is proven. Definition 4.31. Let k and j be integers with lSkSm and 1S sz. We define the real numbers I"); °, N '2 , and M 'kJ as in Definition 4.21 by replacing cosine with sine throughout. Now the result analogous to Lemma 4.25 can be given. 86 Lemma 4.32. Let imagx(j) be the machine representation of Im(oj(x)). Let 82‘): imagx(j) - Im(oj(x)). Then "I m |€2J|S%L(2 2 lsin(i0)|+ Z M'kJ') 5 (4.33) i=1 k=2 Table 2. 82: the error on imagx(j). j d=6 d=7 1 50. 0637 9637 51. 4941 9055 2 44. 0401 0265 45. 2983 9131 3 41. 9722 6918 43. 1714 7687 4 41. 0932 3891 42. 2673 3145 5 40. 8378 3755 42. 0046 3290 6 40. 9792 7505 42. 1501 1148 The next task of the routine checkl is to compute x- q. Again, we will do the real part and simply give the result for the imaginary part. Also, to sharpen the estimate, we will use the following definitions. Definition 4.34. Let k be an integer with IS k Sm. We define the real numbers Pk, N k, and M k by Pk=max{ 2cos(i9)2 K<;{l,...,m}and#K=k}, (4.35) ieK Nk=min{ Zeosae): K;{1,...,m}and#K=k}, (4.36) ieK 87 and Mk = max{ Pk, - N), }. (4.37) Lemma 4.38. Let realxq(i) be the machine representation of Re(o,(x-q)). Let 83‘,- = realxq(l') - Re(oj(x-q)). Then m m-l |83J|S|£1JI+((m-l)‘\/m7i-l- + 2 lcos(i0)l+ ZMk)-8 (4.39) =1 i=1 k Table 3. 83: the error on realxq(j). j d=6 d=7 1 118. 1433 718 119. 3914 978 2 115. 1324 851 116. 2945 858 3 114. 5896 619 115. 7362 534 4 114. 0588 742 115. 1903 003 5 113. 6136 782 114. 7323 845 6 113. 4026 097 114. 5152 854 Proof. We use a modification of Lemma 4.16, as realxq(i) is obtained from realx(j) by repeated subtraction of the terms which comprise the conjugates of q. In particular, there exists a permutation P e I‘ such that for each q, there is an integer k with l S k < m and k realxq(i) = realx(j) - 2 reale(P(i)sj). i=1 88 Thus we define the partial sums by n s(nsj) = realx(j) - 2 reale(P(i),j) i=1 and n s”: Re(oj(x)) - 2 cos( P(i)j0 ). i=1 Then an = 3,.-1j - cos(P(n)j0) and s(nj) = s(n-lJ) - 8(1’ (HM). Thus if the error O‘n.j is defined by any: s(nJ) - 5N, we have s(no) = ( 6.1,,- + 0.1,,- - (1+81,.,;)'cos<1+83> 2"”‘”""'“d‘“‘ . (4.69) length + £3 Letting f(u) ___ 2-101‘tJI—e;_-radiu3 ’ we have that df= - lowe'fli‘“ du . (4.70) u-xl u and upper=f+Af+(81+82+83)-f (4.71) 99 Letting u = length and Au = 83, we need a lower bound on length. We use Lemma 4.09 with approx = lower and temp,- = temij/Z. Equation (4.14) says 4-lower2 S length . (4.72) Thus, applying this to (4.70), we have lAflS—rflé-ui-legI-J—— — | 83 | . 8-lower2 8-radiu3 Directly from Lemma 4.09, we have that upper S radius. Applying this and (4.72) to (4.71) yields (4.68) and Lemma 4.67 is proven. Next, the routine checkl calculates values for temp2(i). These are only slightly modified from the calculations for tempIO'). so we will simply give the bound on the error and omit the proof. Lemma 4.73. Define temij by temp2j=cj +\l cjz + 4'lowers( lower + 0min) . (4.74) Let tempZ (j) be the machine representation of temij and define the error 810‘} by 810J=temp2(j) - temp2j. Then |810J|S2|£9|+2|85j|+Iesmin|+(8-radius+4cj-+cmi,,) (4.75) Table 11. 810: the error on temp2(j). 100 k. GNU-bWND-e d=6 8738. 7906 26 8725. 9346 74 8722. 2215 37 8720. 2248 85 8719. 2356 04 8719. 1405 09 d=7 8815. 6799 90 8802. 4551 84 8798. 6354 85 8796. 5817 13 8795. 5642 06 8795. 4664 78 Lastly, the routine checkl computes the value of ubound. The relative error in this calculation is bounded in the following proposition. We use relative error here as we are looking for an error of less than 0.01 on M x.q when it is close to 1, and we actually compute 23M“). Proposition 4.76. Let £11=(ubound- ubound)/ubound. Then S leulS( ‘5. Elam-tunes) (4.77) 2-rad1us J 1 Table 12. 611: the relative error on ubound. d=6 d=7 811 14 5392. 6810 8-811 0. 0086 6608 17 1110. 7572 0. 0101 9900 101 Proof. Define ubound(0) = 1 and ubound(n) = ubound(n-l) "' temp2(n) Let pa = ubound(n) - uboundn. Then ubound(n) = ( uboundn-1 + Pn-l )( temPZn + 810,» )( 1 + 5n ). so that p1: 810,1 and Pa = (tempznmn-l + (uboundn-l)310,n + (uboundn)5n - Inductively, n e . n pn=uboundn( 2 #35]— + 2 81-) . (4.78) j: 1 j: 2 Thus we need a lower bound on temij. From (4.74), it is clear that temp2j2 2-upper. But from Lemma 4.09, upperz radius/43. Combining this with (4.7 8) yields (4.77), and Proposition 4.76 is proven. Proposition 4.76 shows that when the routine checkl computes that ubound is less than 0.9923, then ubound is less than 23. As Proposition 2.113 shows that ZSMM is less than or equal to ubound, we can conclude in this case thatnebassedm §5 Initializing the double precision routine slick Throughout the next two sections, we assume that q e N3(f) (see Definition 2.95). 102 The subroutine slick is concerned solely with determining Ms”. It is called from the two latter checkers: check2 and check3. It uses Proposition 2.119 to compute either an upper or lower bound on M “I, and it uses Proposition 2.113 to obtain the next approximation. A summary of the preliminary stages of the algorithm follows. We refer the reader to §8 of Chapter 3 for a more precise description and to Appendix A for the program listing. First the constants angle, radius, and radsqd are computed. Next the arrays e and ed are computed. After this initialization, the conjugates of x and x- q and the magnitudes, Cj , are computed. As before, we will follow each result with two sets of values: (i) m = 13, d = 6, f= 2; and (ii) m =13, d= 7, f=1. These are the values of m, d, andf for which the program was run. We start with three elementary preliminaries, whose proofs will be omitted. Lemma 4.79. Let 812 = angle - 0. Then |812 IS 205 . Lemma 4.80. Let 813 = radius - radius. Then 1813 IS 2-radiu3-8. Lemma 4.81. Let 814 = radsqd- (radius)2. Then I 814 l s 2-radius-l £13 I + (radius)2-8 . 103 Table 13. the errors on angle, radius, and radsqd. 812 813 514 d=6 0. 9666 4389 0. 8819 1710 0. 9722 2222 d=7 0. 9666 4389 0. 7559 2894 0. 7142 8571 The errors for £17 and d'ICij will be bounded next. As the calculations for the imaginary parts are entirely analogous to those for the real parts, those results will be given without proofs. First, the error in representing CU. Note that this is independent of d and f. Lemma 4.82. Let 815,”: reale(i,j) - Re(CiJ'). Let h be the integer satisfying: (i) 0 S h < m, (ii) h 2 ij (modulo m). Then I e15,”- | s h-I sin(h0) I .( 1212 I + 0-5) + | cos(h0) 1-5 . Ilfable 14. the error on reale(i,i) and image(i,j). §~ ‘OflQQUt-hdfiNr—b 815 1. 5592 8875 2. 9546 6173 4. 4387 1855 5. 7775 7133 5. 5560 3676 3. 0529 3905 3. 3999 3858 8. 4405 5237 12. 5562 7939 14. 5144 7625 13. 6943 4816 8. 9714 4872 l. 0000 0000 816 1. 7486 0416 2. 4703 3282 1. 5170 3108 2. 9916 7613 6. 0896 9774 8. 6863 1047 10. 0941 4294 9. 3456 4278 5. 5625 0100 2. 7404 4956 9. 8834 0312 15. 87.12 9505 0.00000000 (4.83) 104 Proof. reale(i,j) = (1+51,,- J) cos( (1+82,gJ)h(0+812) ) . Lettingf(u) = cos(u), u = M9, and Au = h£12 + 12082,”; we have that reale(isi) = (1+51,i J) ( cos(he) - (11812 + h952,i‘,‘)sin(h0) ) . Equation (4.83) follows immediately. Lemma 4.84. Let £15,”: image(i,j) - Im(Cii). Let h be as above. Then I 8:15,,- J- l s h-I cos(h0) I -( I 212 I + 6-8) +1 sin(h0)l-8 . (4.85) Next, the error in representing d'lfiil'. Lemma 4.86. Let £17“- J= realed(i,i)- Re(d'lcii). Let h be as above. Then 1817,1'JIS%( 1215);,- I + I cos(h0) I-8) . (4.87) Table 15. 817: the error on realed(i,j). 105 :- \OOOQO‘UJIkUJNt—t d=6f=2 0. 4074 5746 3 0. 5871 2108 0 0. 7598 7587 2 l. 0220 2937 0 l. 0507 5791 8 O. 6706 4681 1 0. 7284 8006 7 l. 5315 1051 9 2. 1518 1404 7 2. 4391 6882 1 2. 3770 6881 9 1. 6428 1745 8 0. 3333 3333 3 d=zf=1 0.3492 4925 4 0.5032 4664 0 0.6513 2217 6 0.8760 2517 4 0.9006 4964 4 0.5748 4012 3 0.6244 1148 6 1.3127 2330 2 1.8444 1204 0 2.0907 1613 2 2.0374 8755 9 1.4081 2924 9 0.2857 1428 6 Lemma 4.88. Let 813,”: imaged(i,j) - Im(d'1§ii). Let h be as before. Then |813JJ|S12( |815,iJ'I + I Sin(h0) l-5) . IableJfi. 813: the error on imaged(i,j). - fi" \OOOQQUIhUJNt—s d=6f=2 0.3688 8788 9 0.5488 8611 5 0.4182 8999 2 0.6544 4873 0 1.1254 7006 6 1.4876 0435 6 1.7222 4310 1 1.6681 2757 4 1.0829 1954 0 0.6221 9307 3 1.7843 9783 1 2.7226 6970 4 0. 0000 0000 0 d=zf=1 0. 3161 8961 9 0. 4704 7381 2 0. 3585 3427 9 0. 5609 5605 4 0. 9646 8862 8 1. 2750 8944 8 l. 4762 0837 2 1. 4298 2363 5 0. 9282 1674 9 0. 5333 0834 8 1. 5294 8385 5 2. 3337 1688 9 0. 0000 0000 0 (4.89) 106 The following computations on the errors of realx(i). imagx(i). realxq(fl, imagxq(i), and c(j) exactly parallels the work in the third section of this chapter. Thus we will give only the results and omit the proofs. We start with a bound on the machine representations of (SJ-(x). Lemma 4.90. Let realx(j) be the machine representation of Re(oj(x)). Let 819‘,- = realx(i)- Re(oj(x)). Then ”1 m m |£19J|S(d-l) 2 Iel7s-Jl+d7:1-( Z lcos(i0)|+ ZMkJ)8 (4.91) i= 1 1': 1 k = 2 1.3M. 819: the error on realx(j). d=df=2 d=lf=l 115. 2812 947 118. 5750 460 112. 2704 080 115. 4781 340 awhuwu \ 111. 7275 848 111. 1967 971 110. 7516 012 110. 5405 327 114. 9198 016 114. 3738 485 113. 9159 327 113. 6988 336 Lemma 4.92. Let imagx(i) be the machine representation of Im(oj(x)). Let 82w: imagx(i) — Im(0',(x)). Then m m m |e2oJlS(d-l) Z 1e13,,JI+%1( 2 Isin(i0)|+ 2 M'u) 8 (4.93) i=1 ' k= Table 18. 820: the error on imagx(j). 107 omawww \ d=6,f=2 114. 2313 688 108. 2076 751 106. 1398 416 105. 2608 113 105. 0054 099 105. 1468 474 d=7,f=l 117. 4951 222 111. 2993 229 109. 1724 085 108. 2682 631 108. 0055 645 108. 1510 431 Next we bound the error in the machine representation of o,(x-q). Lemma 4.94. Let realxq(i) be the machine representation of Re(oj(x-q)). Let 821‘,- = realxq(j) - Re(o,(x-q)). Then m T |€21J| S |£19J° l+f2(l 811ml + 81 cos(ie) |+ 5M”) + 5-m-‘\/ %41 (4.95) i=1 Table 12. 821: the error on realxq(j). j d=6f=2 d=zf=1 1 411. 5296 215 283. 8965 929 2 400. 6578 243 276. 8692 256 3 397. 9171 693 275. 2119 773 4 396. 5806 274 274. 2631 472 5 395. 8547 730 273. 6649 021 6 395. 5820 022 273. 4169 519 108 Lemma 4.96. Let'imagxqfi) be the machine representation of Im(oj(x-q)). Let 822‘,- = imagqu') - Im(o,(x-q)). Then m 2. |£22J l S l 820‘,- l +fZ(l £16,1'J'I + 8| sin(i0) |+ 8M',-J-) + 8-m-‘\/ r_nfl_1 (4.97) i= 1 Table 20. 822: the error on imagxq(j). j d=6f=2 d=zf=1 1 407. 2393 853 281. 1965 139 2 387. 4753 480 268. 1305 429 3 380. 7841 642 263. 6919 533 4 377. 6800 760 261. 6752 789 5 376. 2679 242 260. 8342 052 6 375. 9011 978 260. 7256 018 Lastly, bounds on the error in the machine representation of the Cj's. Lemma 4.98. Let C] = loj(x- q) I. Let c(j) be the machine representation of c]: and let 8233': c(j) - Cj . Then |£23JIS'\[(821J) 2 + (£22J) 2 + 2(‘\’ r%_l_ + mT{)8 (4.99) Iablell. 823: the error on c(j). j d=6,f=2 d=7,f=1 1 602. 6413 438 414. 0696 199 2 581.0485 401 399. 9064 591 3 574. 4345 320 395. 6335 710 4 571. 3243 721 393. 5541 026 5 569. 8251 159 392. 5407 135 6 569. 3747 589 392. 2863 114 Lemma 4.100. Let 823”). = cmin - Cmin- Then - 2 _ . 1823,»... I $me 1 \/ (621j)2+(€22.;)2} +%( \/%+%) (4.101) W. 823mg": the error on cmin. d=6,f=2 d=zf=1 l 588. 6308 652 405. 4987 528 This completes the beginning error analysis on the algorithm of the routine slick. It determines, in effect, how far the algorithm implemented by slick has been perturbed from the theoretical algorithms of Proposition 2.113 and Proposition 2.119 that slick is designed to implement. l 10 §6 Point passing by the double precision routine slick A summary of the concluding stages of the algorithm of the routine slick follows. We refer the reader to §8 of Chapter 3 for a more precise description and to Appendix A for the program listing. Given a value for approx, the routine slick computes the corresponding values of temp2(i). Simultaneously, the values of bound and length are computed. Then, length and bound are tested. If the point has neither passed nor flunked, a new value of approx is computed and the routine loops. Next will follow a sequence of conditional results, based on the quantity 624 = approx - approx . (4.102) We first bound the error on temp2(i). as in Lemma 4.55. As the prOof is entirely analogous, it is omitted Lemma 4.103. Let E25J= temp2(i) - temij. Then IE25JIS|824|+l823j|+%-le23,ninl+(5-radius+c,- +é-cmin )8 (4.104) Next we bound the error on length, as in Lemma 4.65. Again, as the proof is entirely analogous, it is omitted Lemma 4.105. Let e26=length - length. Then 2+3 3 H525 IS 2-radius- 2 |e25 J1 + s——-212(radius)2-8 (4.106) i=1 111 Next we bound the relative error on bound, as in Lemma 4.76, omitting the proof. Lemma 4.107. Let 827 = (bound- bound)/bound. Then S I827|S (ra‘elitgus Z( IE23J| + |825J|+Cj8)+(3-1)8) (4.108) 1=1 Finally, we bound the error on diff. The proof, being elementary, is omitted. Lemma 4.109. Let £23 =diff— diff. Then 1223 I s I 614 I + I e26 I + 23-(radius)2-8 (4.110) Finally, we can show that the algorithm of the routine slick is correct. The first step is to show that if I diff l is large, then the sign of diff accurately reflects the sign of diff, and hence the appropriate conclusions on the order relationship between bound and Mm can be drawn. Proposition 4.111. If diffz 10'10 and baund< 1-10'5, then Mx,q< 1. In particular. slamming. Proof. We will first show that if diffz 10'“), then diff> 0, so that length > (radius)2. To do this, it suffices to show that if 824 = 0, then |e23 |< 1040. Applying Lemmas 4.103, 4.105, and 4.109 with 824 = 0, we get the following values of 825;. 826. and 828- Table 23. 825: the error on temp2(j) when 824 = 0. j d=6f=2 o=zf=1 1 913. 4161 587 627. 4290 200 2 891. 8233 550 613. 2658 591 3 885. 2093 470 608. 9929 710 4 882. 0991 870 606. 9135 027 5 880. 5999 309 605. 9001 136 6 880. 1495 738 605. 6457 114 Table 24. £25 & 823: the errors on length and diff when 824 = 0. d=df=2 d=1f=l £25 4708. 5818 86 2776. 5729 16 223 4711. 8874 72 2779. 0014 87 5-823 5. 2312-10'13 3. 0853-10‘13 As this shows that, in both cases, 1823 IS 10‘“), we can conclude that length > (radius)2. Thus we have, by Proposition 2.119, that Mx,q< bound. Thus, to prove Proposition 4.111, it suffices to show that 1827 IS 10'6 when 624 = 0. Using Lemma 4.107, the following table gives the relative error on bound -- first as multiples of machine error, 8, secondly as a real number. IableZi. 827: the relative error on bound when 824 = 0. d=6f=2 d=zf=1 £27 4 9293. 6718 9 3 9534. 8587 4 5-227 5. 4727-10-12 4. 389310-12 113 Thus Proposition 4.111 is proven. The following result, dual to Proposition 4.111, is proven in the same way. Thus its proof is omitted. Proposition 4.112. If diff S — 10-10 and baund> 1 + 105, then MM> 1. In Particular. W Lastly, we show that when ldiff I is small, the temp2 (j)'s are good approximations to the solution of (2.107), (2.108), and (2.109), and hence bound is a good approximation to Mm]. More precisely, we have the following proposition. Proposition 4.113. Suppose that ldiffl S 1040. If bound< 1 -10'5, then Mx,q< 1. In particular, W Conversely, if bound) 1 + 1045, then Ms,q> 1. In particular. amalgam“ Proof. Each temp2j is an increasing function of approx. Thus length is an increasing function of approx. Setting x= approx, yj = temij, and l = length we have that dl s d - a? 2 29 fi‘ - J' = 1 Further, as yj = x for some j, and all of the yj's are positive, we have that 51:22:. 114 Let x0 be the solution to l(x) = (radius)? Then we have radius 51,700) 2 240 2 2 (4.114) In particular, suppose that I diff | S 10'“). Then, taking approx to be exactly equal to approx, Table 24 shows that I diff - difir I S 1040, so that I diffl < 210'“). But diff: length - (radius)2= l(x) - l(xo) . (4.115) Thus we have a bound on the change in the function value of 1. Using the lower bound (4.114) on the derivative, we can conclude that _‘IS_. . 2-10-10 . (4.116) 2-radtus Ix-onS Now let us analyze the calculations which the routine slick performs from a slightly different viewpoint. Rather than assuming that approx is an exact value, let us view it as an approximation to xo. That is, we suppose that we have the same value in approx, but approx = x0 and 824 = approx - x0. Thus equation (4.116) gives an upper bound on 824 which is summarized in the following table. Iablelfi. 824: the error on approx. d=6f=2 d=zf=1 8224 1.111010-9 1.2961-10'9 £24 1000 6855. 34 1167 4664.56 115 As l(xo) = (radius)2, the temij's are the exact solutions to equations (2.107), (2.108), and (2.109). Thus using the bounds on 824 of Table 26 and Lemma 4.103, the differences between the exact tempZJ-‘s and the computed temp2(j)'s are given in the following table. jljable 27. 825: the error on temp2(j). j d=6f=2 d=1f=l 1 1000 7768. 75 1167 5291. 99 2 1000 7747. 16 1167 5277. 82 3 1000 7740. 54 1167 5273. 55 4 1000 7737. 43 1167 5271. 47 5 1000 7735. 94 1167 5270. 46 6 1000 7735. 48 1167 5270. 20 Finally, as the temij's solve equations (2.107 ), (2.108), and (2.109), bound = Mm- Thus to prove our Proposition, we need only show that the relative error on bound is less than 105. But, for the values of 824 given in Table 26, Lemma 4.107 gives the following values for 827. m. 827: the relative error on bound. d=6f=2 d=mf=1 227 3 3357 3014. 6 4 5400 2377. 3 64:27 3. 7034-10-8 5. 0404-10-8 As both values are less than 10‘, Proposition 4.113 is proven. Chapter 5 Conclusions and Open Questions §1 A summary of runs The program written to implement the work of the previous three chapters has been run three times. All three runs were on a Sun 3/160 minicomputer of the Mathematics Department at Michigan State University. From January 16, 1988 to January 25, 1988, a preliminary version of this program ran with m = 13 and d = 7. There were three principal differences between the preliminary version and the final version described in this dissertation: (i) The preliminary checkl did all of its calculations, including initialization, in single precision arithmetic. (ii) In the preliminary version, the routine check3 was run separately from the main program. (iii) The preliminary slick only applied Proposition 2.113 and not 2.119, and thus had somewhat different logic. During this run, the pattern generator considered 18,110 patterns and reported back 7,887 as potentially lying within the fundamental cell. The cell checker determined that 1,486 of these patterns did indeed lie within the fundamental cell. The disposition of the points generated is summarized in the following table. 116 1 17 Table 22. Run summary (d = 7). checker points estimations passed 1 90,980,978 154,100,673 90,709,723 2 271,255 1,301,787 269,414 3 1,841 212,136 1,841 In February 1988, another preliminary version of the program ran with m = 13, d = 6, and f = 1. There were two main differences between this version and the previous version: (i) For this run, the routine check3 was incorporated within the main program. (ii) The sufficient set used was the set of all reduced points with a given selection whose norms were larger than the L of Definition 2.17. This second modification was undertaken due to our temporary lack of a proof of Lemma 2.33, as it is relatively easy to show that the set of reduced points is sufficient. This resulted in a larger than necessary sufficient set. During this second run, the pattern generator considered 6,098 patterns and returned 4,931 as having norm larger than L. The disposition of the points generated is summarized in the following table. Note that the third checker was run twice, with differing values off. M30. Run summary (d = 6). checker points estimations passed 1 110,782,378 469,070,258 108,554,018 2 2,228,360 18,013,137 2,176,783 3 (f=1) 51,577 24,619,110 51,570 3 (f = 2) 7 323,802 7 118 Finally, the exact program described in this dissertation and whose listing appears in Appendix A, was run with m = 13, d = 6, and f = 2. The run started on July 20, 1988 and finished on July 21, 1988. During this final run, the pattern generator considered 6,098 patterns and reported back 2,806 as potentially lying within the fundamental cell. The cell checker determined that 661 patterns did belong to the fundamental cell. The disposition of the points generated is summarized in the following table. Table 31. Run summary (d: 6,f= 2). checker points estimations passed 1 20,450,056 86,045,968 15,200,578 2 5,249,478 22,093,825 5,237,325 3 12,153 5,338,621 12,153 In addition, a run was made with m =11 on ztgu]. With J: 5 andf: 2, all 105,918 points were passed, with only 671 being reported to the second checker and 4 to the third. Of course this is no surprise, as Lenstra [Le2] proved in 1975 that this ring was norm-euclidean. §2 Conclusions The basic method of proof described in this dissertation of subdividing the quotient field into regions and working analytically on each region is not ours. However, the ideas of using shrunken copies of the fundamental cell of the trace form and a single subdivision are. These techniques have two principal advantages: (i) Only a single subdivision of the quotient field is necessary, so that the number of cases is computable beforehand (ii) The 119 fundamental cell of the trace form is quite closely approximated by its circumscribed sphere, so that the bound on the norm computed on the sphere is quite likely to be very close to the true bound on the shrunken copy of the cell in question. Of course, the greatest difficulty in any attack along this line lies in its computational complexity. That is, considerable effort must be expended in order to both reduce the total number of cases and to handle each case as efficiently as possible. For the method of proof employed in this dissertation, it is the size of the variable d which governs how well the algorithm runs. In particular, extreme values of d are ill advised. As the value of d becomes smaller, it becomes more difficult to pass points. In addition, as d decreases, the hunt for an appropriate "nearby" q becomes more extensive and the number of unsuccessful norm estimations grows, and hence the running time increases. This occurs because the regions on which the norm must be bounded become too large. In particular, for different portions of one region, different "nearby" integers q must be chosen. This is seen most easily in the extreme case, when d = 1. For this case, the sufficient set consists of only one point, x = 0, and thus the only region is the fundamental cell itself. Now for each q 6 R, two-q) = Mp) 2 1 unless q = 0. Thus q = 0 is the only hope of passing the fundamental cell. However, there are elements of the fundamental cell whose norm is strictly larger than 1. However, as (1 tends towards infinity, the size of the sufficient set S tends towards infinity. Thus running time also will increase without bound The following table gives the size of the sufficient set S as a function of the size of d , for the case m = 13. 120 Table 32. The size of S when m = 13. d #S 3 22,407 4 384.802 5 3,109,997 6 20,450,056 7 90,980,978 8 384,695,212 9 1,246,250,676 Thus we need to choose d minimal, subject to the restriction that points still pass. Trial runs have shown that a value of d = 6 is optimal when m = 13. Lastly, some comments concerning the bounds on numerical error obtained in Chapter 4. As shown in Table 12, the relative error on ubound is somewhat high in the d = 7 case. This, however, should not be grounds for concern. On one hand, such error analysis as was performed always assumed the worst case. In practice, error almost never reinforces itself throughout a large calculation, and it is the fundamental stability (or lack thereof) of the underlying algorithm which determines the size of the error. On the other hand, the estimations used in the proofs were not as absolutely sharp as they might have been. Thus we feel confidant that a considerably more exhaustive analysis would bring the critical figure down from 0.0102 to below 0.01. §3 Other attacks on ZlC13] The method of attack described in this dissertation is not the only method which we used to try to prove that Z[C13] is norm-euclidean. It is instead the cumulation of many different attempts which were made. 121 The first attempt made was very similar to the method presented In essence, it was the method which T. Ojala [Oj] used on Z[C16]. It is outlined below. The field Q(Cm) is represented as a n = (p( m ) dimensional vector space over Q. A fundamental cube, C, is given by C={ (x1,... ,xn): 0st-S1}. Then the norm function is maximized on the circumscribed sphere containing this cube. If the maximum is found to be too large, the parent cube is subdivided by bisecting each of its bounding hyper-surfaces, and the norm bounding process is repeated on the 2" resulting offspring cubes. When all of the offspring cubes of a given parent pass the norm bounding, then the parent cell also passes. There are two principal benefits of this process: (i) As the number of subdivisions increase, the size of the cell shrinks. Thus the norm bounding process becomes more accurate. (ii) For a given cube Co, what is maximized is not I Norm(z) l for z e Co, but rather INorm(z-q) I for z 6 Co and some integer q 6 R. Thus for different cubes, one can choose different q's. There are, however, drawbacks to this method which rendered it unworkable on Z [C13]. The first and most obvious difficulty is the potential combinatorial explosion inherent in repeated subdivisions. From each parent cube, 4096 (212) offspring are generated. Ojala [Oj] reported that in his simpler ring, up to five levels of subdivisions were carried out. It seems likely that the situation would be much worse here. The second drawback to this method is geometric. The analytic techniques used here to bound the norm function work on a sphere. One would expect that the supremum of the norm function on a cube would be significantly less than the supremum of the same function on the circumscribed sphere. A rough measure of the difference might be the ratio 122 of the volumes of the cube and its circumscribed sphere. It is well known that, as dimension increases, this ratio tends to zero. In particular, the fit in a twelve dimensional space is sure to be quite poor. We also made a second, quite different, attempt on Z [C13]. As previously mentioned, P. J. Weinberger [We] showed, subject to the generalized Riemann hypothesis, that all class-one fields with infinitely many units are euclidean. The basic method of proof is an induction using the minimal algorithm (for reference on the minimal algorithm, see [Lel], as [Mo] is unreadable). The generalized Riemann hypothesis is used in a starting stage of the induction. Several attempts have been made to remove the dependence of this argument on the generalized Riemann hypothesis. Lenstra [LeS] has isolated the difficulty, and the work of Gupta, Murty, and Murty [Gu] showed promise of proving Weinberger's result independent of any unproven hypothesis. However, technical difficulties arose and the result which Gupta, Murty, and Murty arrived at does not apply to the ring of integers of a number field It seemed to us that the difficulties which impeded Gupta, Murty, and Murry came about, in part, from the generality of their approach. Thus, working on a very specific and very well behaved ring such as Z[§13] might be easier. Unfortunately, this proved not to be the case. We believe, however, that the real truth in these matters lies with an attack along these lines 123 Thirdly, we tried an attack based on a bootstrapping method The basic idea was, in outline, to select an intermediate field O, with Q c O c K. Then, treating K as an extension of degree n over O, we attempt to prove that K is euclidean with respect to the map \ll, where 1V(x) = II NonnK/¢(x) II , and II" is the trace form from O to Q. For example, if O is chosen so that n = 2, we could hope that methods devised to work on quadratic fields would work in this case, as K is quadratic over O. That is, we are pretending that O is Q, and that |I~|l is the usual absolute value. We were unable to carry this attack through to conclusion. In particular, for a cyclotomic field of prime modulus, the maximal real quadratic subfield, K+, is the unique subfield with (K:O)=2. Here, INormK/K+(x) I= Ix I2, so that, in some sense,-the "absolute value" properties of Il-Il have already been exhausted in dropping from K to K+. In general, if we choose O to be too close to K, then O is too complicated to behave like Q. Conversely, if we choose O to be too close to Q, then the degree of K over O is too high for simple methods to apply. However, some modification of this line of approach might work. §4 Open cyclotomic questions There are, as was mentioned in Chapter 1, fifteen class-one cyclotomic fields for which the norm-euclidean question is still open. Of these, only two have prime modulus -- m = 17 and m = 19. The techniques used here can be applied directly to these fields. A reasonable choice of d for these fields would seem to be approximately half of the 124 modulus. However, the size of the sufficient sets in these cases is significantly larger than the m = 13 case. The following tables give the size of the sufficient set for various values of d for the two Open prime moduli. Table 33. The size ofS when m = 17. #3 2,280,738 95,996,878 160,374,512 22,821,184,489 201 ,443,970,380 l,487,745,013,098 8,248,634,581,516 chQth N Table 34. The size of S when m = 19. d #S 3 19,974,286 4 1,563,544,538 5 39,334,715,702 6 742,913,975,156 7 8,870,097,807,556 8 83,105;562,335,066 9 578,304,732,608,758 Thus we could expect the running time in the m = 17 case to be about 70,000 times that in the m = 13 case, and the m =19 case to be perhaps 400 times beyond that. Further, as m increases so does 3, so that the time consuming floating point operations will be correspondingly more complex. Allin all, we suspect that simply stepping up to a super computer would prove insufficient to overcome the added complexity. 125 Attacking the composite moduli with our methods presents different problems. For the prime modulus m , we made but little use of any relations on the roots of unity, as there was only one. For composite moduli there are more relations, as the dimension of Q(Cm) as a vector space over Q is (p(m ). If for no other reasons than that of computational complexity, it seems necessary to exploit these additional relations. It does not seem necessary to abandon the ideas of patterns and generating selected points from them. Instead it seems advisable to modify the pattern and point generation algorithms to exploit the additional relations -- perhaps while continuing to work with points expressed in terms of m -tuples. We hope to be able to successfully handle some, if not all, of the remaining cyclotomic fields at some future date. APPENDICIES 0000000 C PROGRAM MAC9 126 Appendix A The Program Listing ************************************************* * * VERSION * * 9.2 * * * * ************************************************* TUESDAY, 26 JULY, 1988 C23456789012345678901234567890123456789012345678901234567890123456 C 2500 2600 2700 2800 2900 2950 0 00000000 1 2 3 IMPLICIT INTEGER (A-Z) DIMENSION A(0:20), X(20), SORT(20) DIMENSION PFLAG(10), CFLAG(10), XFLAG(10) LOGICAL FLAGl, FLAGZ, FLAG3, FLAG4, FLAGS, FLAG6 LOGICAL PFLAG INITIALIZE FILE FILE FILE OPEN (1, OPEN (9, OPEN (3, WRITE (*,2500) FORMAT (' INPUT READ (*, 2600) M FORMAT (I8) WRITE (*,2700) FORMAT (' INPUT READ (*,2800) D FORMAT (18) WRITE (*,2900) FORMAT (' INPUT READ (*,2950) F FTfidflTP (I8) MEANINGS OF THE COUNTl COUNT2 COUNT3 COUNT4 COUNTS COUNT6 COUNT7 COUNT8 'FLUNK' ) 'RUNINFO' 'BUGINFO' 4 5 6 ) ) THE MODULUS NOW') THE TILING MESH NOW') CHECK3 BOUND NOW') COUNTS: NUMBER NUMBER NUMBER NUMBER NUMBER NUMBER NUMBER NUMBER OF OF OF OF OF OF OF OF PATTERNS PGEN LOOKS AT PATTERNS PGEN REPORTS PATTERNS PASSING ALL CHECKS POINTS GENERATED FIRST CHECKS MADE POINTS FLUNKING FIRST CHECKER SECOND CHECKS MADE POINTS FLUNKING SECOND CHECKER 126 00000000000 3000 3100 10 127 COUNT9 NUMBER OF THIRD CHECKS MADE COUNlO NUMBER OF POINTS FLUNKING THIRD CHECKER COUNTl COUNT2 COUNT3 COUNT4 COUNTS COUNT6 COUNT7 COUNT8 COUNT9 COUNlO OOOOOOOOOO MEANING OF THE PRINT FLAGS PFLAG = PRINT ON/OF CFLAG = NUMBER OF PRINTS XFLAG = NUMBER OF PRINTS (STORED FOR RUNINFO PRINT) PATTERN GENERATOR CELL BOUND CHECKER POINT GENERATOR FIRST CHECKER SECOND CHECKER THIRD CHECKER SLICK \IQUDWNH DO 2, I=l, 7 ‘WRITE (*,3000) I FORMAT (' INPUT COUNT NUMBER',I4) READ (*,3100) XFLAG(I) FORMAT (I8) CFLAG(I) = XFLAG(I) PFLAG(I) = (XFLAG(I).GT.0) CONTINUE INITIALIZE SUBROUTINES CALL SCELL (M,D,A,SUM,FLAG2,PFLAG(2)) CALL SCHEKl (M,D,X,SORT,FLAG4,COUNT5,PFLAG(4)) CALL SCHEK2 (M,D,X,FLAGS,COUNT7,PFLAG(5),CFLAG(7)) CALL SSLICK (M,D,X,X,FLAGS,PFLAG(7)) NOTE: CHECK3 DOESN'T NEED TO BE INITIALIZED TOP OF PATTERN GENERATION LOOP CALL SPGEN (M,D,A,SUM,FLAG1,COUNT1,PFLAG(1)) CONTINUE IF (FLAGl) THEN INCREMENT PATTERN COUNTER COUNT2 = COUNT2 + 1 CHECK TO SEE IF PATTERN IS WITHIN FUNDAMENTAL CELL CALL CELL (M,D,A,SUM,FLAG2,PFLAG(2)) IF (PFLAG(2)) THEN CFLAG(Z) = CFLAG(2)-1 1000 20 128 PFLAG(Z) = (CFLAG(Z).GT.0) ENDIF ' IF (FLAGZ) THEN INCREMENT WITHIN CELL COUNTER COUNT3 = COUNT3 + l WRITE (9,1000) COUNT3, COUNT4, COUNT6, COUNT8, COUNlO, ( A(I), I=0, D-l ) FORMAT (5I10,3X, 9I3) TOP OF POINT GENERATION LOOP CALL SPOINT (M,D,A,X, SORT,FLAG3,PFLAG(3)) CONTINUE IF (FLAG3) THEN INCREMENT POINT COUNTER COUNT4 == COUNT4 + 1 INVOKE FIRST CHECKER CALL CHECKl (M, D, X, SORT, FLAG4 , COUNTS, PFLAG (4) ) IF (PFLAG(4)) THEN CFLAG(4) = CFLAG(4)-1 PFLAG(4) = (CFLAG(4).GT.0) ENDIF IF (.NOT.FLAG4) THEN WE HAVE FLUNKED FIRST CHECK INCREMENT COUNTER COUNT6 = COUNT6 + 1 INVOKE SECOND CHECKER CALL CHECKZ (M, D: X: FLAGS, COUNT7, PFLAG (5) , CFLAG (7)) IF (PFLAG(5)) THEN CFLAG(S) = CFLAG(5)-1 PFLAG(S) = (CFLAG(S) .GT.0) ENDIF IF (.NOT.FLAG5) THEN WE HAVE FLUNKED SECOND CHECK INCREMENT COUNTER COUNT8 = COUNT8 + l INVOIG THIRD CHECKER CALL CHECK3 (M,D,F,X, FLAG6,COUNT9,PFLAG(6) ,CFLAG(7)) IF (PFLAG(6)) THEN CFLAG(6) = CFLAG(6)-1 PFLAG(6) = (CFLAG(6) .GT.0) ENDIF IF (.NOT.FLAG6) THEN 1100 1300 1400 1500 1600 1700 1800 1900 129 WE HAVE FLUNKED EVERYTHING! INCREMENT COUNTER & WRITE POINT COUNlO = COUN10 + 1 WRITE (1,1100) (X(I), I=1,M) FORMAT (20I3) ENDIF END THIRD CHECK FAIL ENDIF END SECOND CHECK FAIL ENDIF END FIRST CHECK FAIL GET NEXT POINT CALL POINT (M,D,A,X,SORT,FLAG3,PFLAG(3)) IF (PFLAG(3)) THEN CFLAG(3) = CFLAG(3)-1 PFLAG(3) = (CFLAG(3).GT.0) ENDIF GOTO 20 ENDIF END POINT LOOP ENDIF END PASS CELL CHECK -- GO TO NEXT PATTERN CALL PGEN (M,D,A,SUM,FLAG1,COUNT1,PFLAG(1)) IF (PFLAG (1) ) THEN CFLAG(1) = CFLAG(1)-1 PFLAG(l) = (CFLAG(l).GT.0) ENDIF GOTO 10 ENDIF END PATTERN GENERATION LOOP WRITE (9,1300) M,D,F FORMAT (' MODULUS / DIVISION / CHECK3 BOUND ',5X,3I5) WRITE (9,1400) (XFLAG(I), I=1,7) FORMAT (' PRINT COUNTS ',7I5) WRITE (9,1500) COUNTl, COUNT2 FORMAT (' PATTERNS LOOKED AT / REPORTED ',2I10) WRITE (9,1600) COUNT3, COUNT4 FORMAT (' PATTERNS PASSED / POINTS GENERATED',2I10) WRITE (9,1700) COUNTS, COUNT6 FORMAT (' CHECK #1 -- CHECKS / FLUNKS ',2110) WRITE (9,1800) COUNT7, COUNT8 FORMAT (' CHECK #2 -- CHECKS / FLUNKS ',2I10) WRITE (9,1900) COUNT9, COUNlO FORMAT (' CHECK #3 -- CHECKS / FLUNKS ',2110) IF (COUN10.EQ.0) THEN 130 WRITE (9,2000) 2000 FORMAT (' \CONGRATULATIONS, \DR. \BOB! \ALL POINTS PASS.') ELSE WRITE (9,2100) 2100 FORMAT (' \CURSES, FOILED AGAIN! \SOME POINTS FLUNK.') ENDIF CLOSE (1) CLOSE (9) CLOSE (3) END SUBROUTINE SPGEN (M,D,A,SUM,FLAG,COUNT,PFLAG) c PATTERN GENERATOR. RETURNS THE RESULT IN THE ARRAY A(I). c THE MULTISET \(\( 0**A(0), 1**A(1), ... \)\) CORRESPONDS TO A c AND THE POINT x = (1/D) SUM \( X(I)*E(I) \). WHERE c A(I) = #\( J: X(J) = I \). c SINCE THE PATTERNS ARE FOR POINTS IN STANDARD FORM, c WE ALWAYS HAVE A(0)>0 c \THUS WE INTERNALLY GENERATE PATTERNS B(J) ON M—l DIGITS c AND RETURN A(J)=B(J) WHERE A(0)=B(0)+1 c THE METHOD USED TO GENERATE PATTERNS Is TO CARRY A 1 FROM THE c FIRST NON ZERO 3(1) TO B(I+1) AND IF I>0, DROP THE REST c OF B(I) TO 3(0). C23456789012345678901234567890123456789012345678901234567890123456 C 1 2 3 4 5 6 IMPLICIT INTEGER (A-Z) DIMENSION A(0:20), B(0:20) LOGICAL FLAG, TFLAG, PFLAG REAL RM, RD, TEMP SAVE C LBOUND AND UBOUND DETERMINE A SHELL OUTSIDE OF WHICH THE C PATTERNS DO NOT NEED TO BE CONSIDERED. C IF X IS WITHIN THE SPHERE DETERMINED BY LBOUND, THEN C THE (1/M) CELL HAS NORM .LT. 1 BY ARITH-GEOMETRIC MEAN. C THE SPHERE DETERMINED BY UBOUND IS THE CIRCUMSCRIBED SPHERE C CONTAINING THE FUNDAMENTAL CELL. C INITIALIZE M1 3 M-1 D1 = D-l RM = REAL(M) RD = REAL(D) TEMP = SQRT(RM-1.) * ( RD - SQRT( (RM+1.)/12. ) ) LBOUND = TEMP * TEMP UBOUND = D*D * ( (M*Mr1)/12 ) IF (PFLAG) THEN WRITE (3,5000) TEMP,LBOUND,UBOUND 5000 5010 1000 1100 1200 1300 100 1400 1500 1600 131 FORMAT (' INIT PGEN: TEMP,LBOUND,UBOUND',F12.8,2I8) WRITE (3,5010) FORMAT (' ') ENDIF IF TFLAG THEN INPUT A STARTING PATTERN WRITE (*,1000) FORMAT (' I WISH TO INPUT A STARTING VALUE T/F') READ (*,1100) TFLAG FORMAT (L8) BYPASS STARTING PATTERN INPUT TFLAG = .FALSE. IF (TFLAG) THEN GET PATTERN FROM HUMAN DO 2, I=0,D1 WRITE (*,1200) I FORMAT (' INPUT THE MULTIPLICITY OF #',I3) READ (*,1300) A(I) FORMAT (I8) CONTINUE TOP OF VERIFICATION LOOP CONTINUE DISPLAY AND CHECK THE PATTERN WRITE (*,1400) (A(I), I=0,Dl) FORMAT (20I3) SUM=0 SSUM=0 WSUM=0 DO 4, I=0,D1 IF (A(I).LT.0 .OR. A(I).GT.M) THEN FAULTY PATTERN GOTO 150 ENDIF WSUM = A(I)+WSUM SUM = I*A(I)+SUM SSUM = I*I*A(I)+SSUM CONTINUE IF (WSUM.EQ.M .AND. A(0).GT.0) THEN PATTERN IS OKAY -- DOUBLE CHECK WITH HUMAN WRITE (*,1500) FORMAT (' THIS IS CORRECT T/F') READ (*,1600) TFLAG FORMAT (L8) IF (TFLAG) THEN EVERYTHING COOL -- RETURN 150 1700 1800 1900 2000 5100 5200 200 132 B(O) = A(O) - 1 DO 5, J=1, D1 B(J) = A(J) CONTINUE FLAG = .TRUE. RETURN ENDIF ENDIF FIX A USER SELECTED NUMBER IN THE PATTERN CONTINUE WRITE (*,1700) FORMAT (' INPUT THE INDEX OF THE ONE TO FIX NOW. ') READ (*,1800) I FORMAT (18) WRITE (*,1900) FORMAT (' INPUT THE CORRECT VALUE NOW. ') READ (*,2000) A(I) FORMAT (I8) GOTO 100 END OF PATTERN VERIFICATION LOOP ENDIF END OF HUMAN INPUTED PATTERN SECTION COMPUTER GENERATED FIRST PATTERN DO 6, I=0,D1 A(I) = 0 B(I) = 0 CONTINUE SUM = 0 SSUM = 0 A(O) = M 3(0) = M1 FLAG = .TRUE. ENTRY PGEN (M, D, A, SUM, FLAG, COUNT, PFLAG) IF (PFLAG) THEN WRITE (3,5100) (A(I), I=0,Dl) FORMAT (' PGEN: OLD PATTERN ',ZOI3) WRITE (3,5200) (B(I), I=0,Dl) FORMAT (' PGEN: OLD B PATTERN ’,2013) ENDIF COUNT = COUNT+1 I=0 FIND A NON ZERO B(I) 5300 5400 5500 5600 133 DO WHILE (B(I) .EQ.0) CONTINUE . IF (B(I) .EQ.0) THEN I=I+1 GOTO 12 ENDIF REPEAT IF (PFLAG) THEN WRITE (3,5300) I FORMAT (' PGEN: NON ZERO SLOT',I3) ENDIF IF (I.EQ.Dl) THEN OUT OF PATTERNS (DON'T NEED NO X(I) .GE. FLAG = .FALSE. IF (PFLAG) THEN WRITE (3, 5400) WRITE (3, 5400) FORMAT (' ') ENDIF RETURN ENDIF CARRY THE 1 UPWARDS AND DROP THE REST DOWN. COMPUTE NEW SUM & SSUM SUM = -I*B(I) + I + 1 + SUM SSUM = -I*I*B(I) + (I+1)*(I+1) + SSUM B(I+1) = B(I+1)+1 B(O) = B(I)-1 IF I .GT. 0 THEN ZERO A(I) IF (I.GT.0) THEN B(I) = 0 ENDIF MNORM = M*SSUM - SUM*SUM IF (PFLAG) THEN WRITE (3,5500) (B(I), I=0,Dl) FORMAT (' PGEN: NEW B PATTERN',20I3) WRITE (3, 5600) SUM, SSUM, MNORM FORMAT ( ' PGEN: SUM, SSUM, MNORM' , 3I8) ENDIF D!) CHECK OF X LYING WITHIN THE SHELL TWEEN LBOUND & UBOUND IF ( ( MNORM .LE. LBOUND ) .OR. ( MNORM .GT. THIS PATTERN UNACCEPTABLE GET ANOTHER GOTO 200 UBOUND) ) THEN 14 5700 5800 000 000 0000 134 ENDIF A(O) = 8(0) + 1 DO 14, J=1, D1 A(J) = B(J) CONTINUE IF (PFLAG) THEN WRITE (3,5700) (A(I), I=0,Dl) FORMAT (' PGEN: NEW PATTERN',20I3) WRITE (3,5800) WRITE (3,5800) FORMAT (' ') ENDIF RETURN END SUBROUTINE SCELL (M, D, A, SUM, FLAG, PFLAG) GIVEN A POINT X'S PATTERN A WHERE X = SUM \( X(I)*E(I)/D \) A(I) = #\(X(J): X(J)=I\) SUM = SUM \( X(I) \) THIS SUBROUTINE WILL RETURN: FLAG — .TRUE. IF POINT IS IN THE FUNDAMENTAL CELL FLAG .FALSE. IF POINT IS NOT IN THE FUNDAMENTAL CELL. NEW VERSION 16 \MARCH 1988 USES CONCAVITY & ONLY PERFORMS D-l CHECKS THE VARIABLE H IS D*G FROM CHAPTER 2 C23456789012345678901234567890123456789012345678901234567890123456 C 5000 1 2 3 4 5 6 IMPLICIT INTEGER (A-Z) DIMENSION A(0:20) LOGICAL FLAG, PFLAG SAVE M1 D1 M-l D-l RETURN ENTRY CELL (M, D, A, SUM, FLAG, PFLAG) IF (PFLAG) THEN WRITE (3,5000) (A(I), I=0,Dl) FORMAT (' CELL: CHECKING PATTERN',20I3) 5100 5200 10 5300 0000 135 DO 10' J = D1, 1' —1 K H K + A(J) ((A(J)+M)*A(J)*D)/2 + H - (M*J+D*K-SUM)*A(J) IF (PFLAG) THEN WRITE (3,5100) J,K,H FORMAT (' CELL: J/K/H',3I8) ENDIF IF ( H .LT. 0 ) THEN THE POINT IS OUTSIDE OF THE CELL. IF (PFLAG) THEN WRITE (3,5200) WRITE (3,5200) FORMAT (' ') ENDIF FLAG = .FALSE. RETURN ENDIF CONTINUE THE POINT HAS PASSED ALL TESTS & IS WITHIN THE CELL. FLAG = .TRUE. IF (PFLAG) THEN WRITE (3,5300) WRITE (3,5300) FORMAT (' ') ENDIF RETURN END SUBROUTINE SPOINT (M,D,A,X,SORT,FLAG,PFLAG) THIS ROUTINE CONVERTS THE PATTERN IN A INTO THE POINT IN X. IT HAS BEEN MODIFIED TO NOT GENERATE UNNECESSARY POINTS. IT SEARCHES FOR THE TWO DIGITS USED WITH THE LEAST MULTIPLICITY AND PUTS THESE IN X(l) & X(M). IMPLICIT INTEGER.(A-Z) DIMENSION A(0:20) ,B (0:20) ,X(20) ,SORT (20) ,MORT (20) LOGICAL FLAG,SFLAG,SSFLAG,PFLAG SAVE SFLAG = .TRUE. MEANS NO SMALLEST YET, SSFLAG = .TRUE. MEANS NO SECOND SMALLEST YET. 136 C23456789012345678901234567890123456789012345678901234567890123456 C 5000 5100 1 2 3 4 5 6 M1 = M-l Dl = D-1 SFLAG = .TRUE. SSFLAG = .TRUE. FIRST STORE THE PATTERN IN B SO WE CAN WORK WITH IT. DO 2, I=0,D1 B(I) = A(I) CONTINUE IF (PFLAG) THEN WRITE (3,5000) (A(I), I=0,Dl) FORMAT (' SPOINT: A ',20I3) WRITE (3,5100) (B(I), I=0,Dl) FORMAT (' SPOINT: B ',20I3) ENDIF S = DIGIT WITH SMALLEST NON ZERO MULTIPLICITY SS = DIGIT WITH SECOND SMALLEST. START LOOP THROUGH THE DIGITS DO 4, I=0,Dl IF (B(I).GT.0) THEN DIGIT I HAS NON ZERO MULTIPLICITY IF (SFLAG) THEN NO SMALLEST SAVED YET, SO THIS IS IT. S = I SFLAG = .FALSE. ELSE IF (B(I).LE.B(S)) THEN A NEW SMALLEST. SS = S SSFLAG = .FALSE. S = I ELSE IF (SSFLAG) THEN NO SECOND SMALLEST SAVED YET. SS=I SSFLAG = .FALSE. 5200 137 ELSE IF (B(I).LT.B(SS)) THEN A NEW SECOND SMALLEST SS=I ENDIF END NEW SECOND SMALLEST ENDIF END NO SECOND SMALLEST ENDIF END NEW SMALLEST ENDIF END NO SMALLEST ENDIF END DIGIT I HAS NON ZERO MULTIPLICITY CONTINUE END LOOP ON DIGITS IF (PFLAG) THEN WRITE (3,5200) S,SS FORMAT (' SPOINT: S/SS ',2I4) ENDIF IF (B(S).GT.1) THEN SMALLEST MULTIPLICITY IS .GE. 2 8(8) = B(S)-2 X(l) = S X(M) = S ELSE SMALLEST MULTIPLICITY IS 1 3(3) = B(S)-1 B(SS) = B(SS)-1 X(l) = S X(M) = SS ENDIF END FIX FIRST & LAST DIGITS BEGIN INITIALIZE THE POINT J = 1 DO 8, I=0,D1 DO 6, XX=1,B(I) J = J+1 X(J) = I CONTINUE CONTINUE 5300 5400 5500 5600 138 END INITIALIZE THE POINT (MIDDLE DIGITS) NOW SORT THE POINTS SO X(SORT(1)) <= X(SORT(2)) <= ... DO 10, I=2,Ml SORT(I) = I CONTINUE I=2 CONTINUE DO WHILE ( ( I.LE.M1 ) .AND. ( X(l).GT.X(SORT(I)) ) IF ( I.LE.Ml ) THEN IF ( X(l).GT.X(SORT(I)) ) THEN SORT(I-l) = SORT(I) I = I+l GOTO 11 ENDIF ENDIF END DO WHILE SORT(I-l) = 1 I=Ml CONTINUE DO WHILE ( ( I.GE.1 ) .AND. ( X(M).LT.X(SORT(I)) ) ) IF ( I.GE.1 ) THEN IF ( X(M).LT.X(SORT(I)) ) THEN SORT(I+1) = SORT(I) I = I-l GOTO 12 ENDIF ENDIF END DO WHILE SORT(I+1) = M END SORTING OF POINTS BEGIN MORT, THE INVERSE OF SORT. DO 16, I=1,M MORT(SORT(I)) = I CONTINUE END MORT, THE INVERSE OF SORT IF (PFLAG) THEN WRITE (3,5300) (X(I),I=1,M) FORMAT (' SPOINT: X ',20I3) WRITE (3,5400) (SORT(I),I=1,M) FORMAT (' SPOINT: SORT ',20I3) WRITE (3,5500) (MORT(I),I=1,M) FORMAT (' SPOINT: MORT ',20I3) WRITE (3,5600) WRITE (3,5600) FORMAT (' ') ENDIF FLAG = .TRUE. ) 5700 5800 N0 00 139 HAVE THE FIRST POINT & RETURN RETURN ENTRY POINT (M,D,A,X,SORT,FLAG,PFLAG) GET NEXT POINT IF (PFLAG) THEN WRITE (3,5700) (X(I), I=1,M) FORMAT (' POINT: X ',20I3) ENDIF FIRST FIND X(I) SUCH THAT X(I) < X(I+1) >= X(I+2) >= ... >= X(Ml) I = Ml-l DO WHILE ( X(I) .GE. X(I+1) ) CONTINUE IF ( X(I) .GE. X(I+1) ) THEN IF (I.EQ.2) THEN POINT IN INVERSE LEXICOGRAPHICAL ORDER. RETURN FLAG = .FALSE. IF (PFLAG) THEN WRITE (3,5800) WRITE (3,5800) FORMAT (' ') ENDIF RETURN ENDIF I = I-l GOTO 20 ENDIF REPEAT J = I+l FIND COORDINATE X(J) SUCH THAT X(J) > X(I) AND X(J+1) <= X(I) THAT IS, THE MINIMAL X(J) > X(I) WITH J > I. DO WHILE (J.LT.M1) CONTINUE IF (J.LT.M1) THEN IF ( X(J+1) .LE. X(I) ) THEN EXIT GOTO 23 ENDIF J=J+1 GOTO 22 6000 6100 6200 6300 140 ENDIF REPEAT CONTINUE IF (PFLAG) THEN WRITE (3,5900) I,J FORMAT (' POINT: I,J ',214) ENDIF NOW SWAP X(I) & X(J) NOTE: X(I) IS THE MORT(I)TH SMALLEST & ETC. K = X(I) X(I) = X(J) X(J) = K K = MORT(I) MORT(I) = MORT(J) MORT(J) = K SORT(MORT(I)) = I SORT(MORT(J)) = J NOW INVERT TAIL OF THE LIST: PUT IN INCREASING ORDER. I+1 Ml I J DO WHILE (I.LT.J) CONTINUE IF (I.LT.J) THEN K = X(I) X(I) = X(J) X(J) = K K = MORT (I) MORT(I) = MORT(J) MORT(J) = K SORT(MORT(I)) = I SORT(MORT(J)) = J I=I+1 J=J-1 GOTO 24 ENDIF REPEAT IF (PFLAG) THEN WRITE (3,6000) (X(I), I=1,M) FORMAT (' POINT: NEW X ',20I3) WRITE (3,6100) (SORT(I), I=1,M) FORMAT (' POINT: SORT ',2013) WRITE (3,6200) (MORT(I), I=1,M) FORMAT (’ POINT: MORT ',20I3) WRITE (3,6300) WRITE (3,6300) FORMAT (' ') ENDIF ""l 141 RETURN END SUBROUTINE SCHEKl (M,D,X,SORT,FLAG,COUNT,PFLAG) IMPLICIT INTEGER (A-Z) DIMENSION X(20), SORT(20) DIMENSION XQ(10), C(10) DIMENSION E(20,10), ED(20,10) LOGICAL FLAG, PFLAG REAL C, CMIN REAL UPPER, UBOUND, LOWER, LENGTH REAL TEMPl, TEMPZ REAL LOWER4, LOWRAD, BOUND, BNDZS COMPLEX E, ED, XQ DOUBLE PRECISION ANGLE, RADIUS DOUBLE PRECISION DTEMP, REALE, IMAGE, REALED, IMAGED SAVE ERROR DISCOVERED IN RADIUS: (TS, 5 JAN, 1988) SINCE WE NEED USE ONLY ONE OF EACH CONJUGATE PAIR OF COMPLEX ISOMORPHISMS, WE CAN DIVIDE THE RADIUS BY THE SQUARE ROOT OF 2. 23456789012345678901234567890123456789012345678901234567890123456 1 2 3 4 5 6 00 0000 M1 M-1 D1 D-1 s = M1/2 ANGLE = 6.28318 53071 79586 D0 / DBLE(M) RADIUS = DSQRT( DBLE((M?Mr1)/24) ) / DBLE(D) DTEMP = RADIUS / DSQRT( DBLE(S) ) LOWER = REAL( DTEMP ) LOWER4 REAL( 4.0D0 * DTEMP ) LOWRAD REAL( 2.0D0 * DTEMP * RADIUS ) BOUND = .99 BNDZS = BOUND * 2**s DO 4, I=1,M DO 2, J=1,S DTEMP REALE IMAGE E(I,J) ANGLE*MOD(I*J,M) DCOS( DTEMP ) DSIN( DTEMP ) CMPLX( REALE, IMAGE ) REALED REALE / DBLE(D) IMAGED IMAGE / DBLE(D) ED(I,J) = CMPLX ( REALED, IMAGED ) 2 CONTINUE 4 CONTINUE IF (PFLAG) THEN WRITE (3,5000) ANGLE,RADIUS,BND2$ 5000 5100 5200 5300 5400 5500 10 12 142 FORMAT (' SCHEKl: ANGLE,RADIUS,BND28',3F12.6) WRITE (3,5100) WRITE (3, 5200) J FORMAT (' ') FORMAT (' SCHEKl: CONJUGATE NUMBER', 12) DO 6, I=1,M WRITE (3,5300) E(I,J),ED(I,J) FORMAT (' SCHEKl: E/ED',2(2(F12.6,1X),4X)) CONTINUE CONTINUE WRITE (3,5400) WRITE (3,5400) FORMAT (' ') ENDIF RETURN ENTRY CHECKl (M,D,X,SORT,FLAG,COUNT,PFLAG) XQ(J) = JTH CONJUGATE OF X AS A COMPLEX NUMBER IF (PFLAG) THEN WRITE (3,5500) (X(I), I=1,M) FORMAT (' CHECKl: X ',20I3) ENDIF DO 12, J%1,S XQ(J) = ( 00' 0. ) DO 10, I=1,M XQ(J) = X(I)*ED(I,J) + XQ(J) CONTINUE CONTINUE THE MAIN LOOP DO 30, I=M,1,-1 COUNT = COUNT+1 IF (I.LT.M) THEN SUBTRACT OFF A NEARBY LATTICE POINT DO 20, J=1,S 20 22 5600 5700 5800 5900 6000 6100 6200 24 26 143 XQ(J) = XQ(J) - E(SORT(I+1),J) CONTINUE ENDIF FIND THE MINIMAL C(J) = \!XQ(J)\! CMIN = 999999. DO 22, J=1,S C(J) = ABS(XQ(J)) IF ( C(J) .LT. CMIN ) THEN CMIN = C(J) ENDIF CONTINUE TEMPl = (LOWER+CMIN)*LOWER4 LENGTH = 0. IF (PFLAG) THEN WRITE (3,5600) FORMAT (' ') WRITE (3,5700) I FORMAT (' CHECKl: I ',I4) WRITE (3,5800) (J,XQ(J), J=1,S) FORMAT (' CHECKl: J, XQ ',I4,2F12.6) WRITE (3,5900) CMIN FORMAT (' CHECKl: CMIN ',F10.6) WRITE (3,6000) (J,C(J), J=1,S) FORMAT (' CHECKl: J, C ',I4,F12.6) WRITE (3,6100) LOWER FORMAT (' CHECKl: LOWER ',F12.6) ENDIF DO 24, J:1,S TEMP2 = ( SQRT( C(J)*C(J)+TEMP1 ) - C(J) ) LENGTH = TEMP2*TEMP2 + LENGTH IF (PFLAG) THEN WRITE (3,6200) J,TEMP2 FORMAT (' CHECKl: J,TEMP2 'I4,F12.6) ENDIF CONTINUE UPPER LOWRAD / SQRT(LENGTH) TEMPl (UPPER+CMIN)*UPPER*4. UBOUND = 1. DO 26, J=1,S UBOUND = ( SQRT( C(J)*C(J)+TEMP1 .) + C(J) ) * UBOUND CONTINUE IF (PFLAG) THEN 6300 6400 30 6500 C C 144 WRITE (3, 6300) LENGTH, UPPER, UBOUND FORMAT ( ' CHECKl: LENGTH, UPPER, UBOUND ' , 3F12 . 6) ENDIF IF ( UBOUND .LT. BNDZS ) THEN FLAG = .TRUE. IF (PFLAG) THEN WRITE (3, 6400) WRITE (3,6400) FORMAT (' ' ) ENDIF RETURN ENDIF CONTINUE FLAG = .FALSE. IF (PFLAG) THEN WRITE (3,6500) WRITE (3,6500) FORMAT (' ') ENDIF RETURN END SUBROUTINE SCHEKZ (M, D, X, FLAG, COUNT, PFLAG, CFLAG) IMPLICIT INTEGER (A-Z) LOGICAL FLAG, PFLAG, PFLAGl DIMENSION A(0:20) ,B(0:20,20) ,II (20) DIMENSION X (20) ,Q(20) SAVE THIS ROUTINE HANDLES REPETITIONS IN THE DIGITS OF X SLICK IS USED TO CHECK THE POINT C23456789012345678901234567890123456789012345678901234567890123456 C 1 2 3 4 5 6 M1 = M - 1 D1 = D - 1 PFLAGl = (CFLAG.GT.0) RETURN ENTRY CHECK2 (M, D , X, FLAG, COUNT, PFLAG, CFLAG) 145 C INITIALIZE SLICK FOR THIS POINT CALL XSLICK (M,D,X,Q,FLAG,PFLAG1) DO 10, I=0, D1 A(I) = 0 10 CONTINUE C GET PATTERN & LOCATION C ALSO ZERO 'NEARBY LATTICE POINT' Q DO 12, I=1, M Q(I) = 0 J = X(I) A(J) = A(J)+1 B( J. A(J) ) = I 12 CONTINUE IF (PFLAG) THEN WRITE (3,5000) (X(I), I=1,M) 5000 FORMAT (' CHECK2: X ',20I3) WRITE (3,5100) 5100 FORMAT (' CHECK2: I A B') DO 14, I=0,D1 WRITE (3,5200) I,A(I),( B(I,J), J=1,A(I) ) 5200 FORMAT (8X,2I4,2X,20I3) 14 CONTINUE IF (PFLAGl) THEN WRITE (3,5250) 5250 FORMAT (' ') ENDIF ENDIF C INVOKE CHECKER FOR Q = 0 FIRST! CALL SLICK (M,D,X,Q,FLAG,PFLAG1) IF (PFLAGl) THEN CFLAG = CFLAG-1 PFLAGl = (CFLAG.GT.O) ENDIF C BEGIN DOES X PASS WITH 0? IF (FLAG) THEN IF (PFLAG) THEN WRITE (3,6500) 6500 FORMAT (' CHECK2: PASSES WITH 0') WRITE (3,6600) ‘ WRITE (3,6600) 6600 FORMAT (' ') ENDIF C YES! THE POINT PASSES! BRAVO! RETURN 11F“ 6700 6750 100 20 200 26 5300 5400 5450 146 ELSE POINT DOES NOT PASS IF (PFLAG) THEN WRITE (3, 6700) FORMAT (' CHECK2: WRITE (3, 6750) FORMAT (' ' ) ENDIF FLUNKS WITH 0') ENDIF END DOES X PASS WITH 0? BEGIN COMPUTE J = D1 'NEARBY LATTICE POINT' Q BEGIN LOOP ON DIGITS J CONTINUE IF (J.GE.0) THEN DO 20, I=1,M II(I) = 0 CONTINUE K=1 BEGIN FETCH NEXT Q CONTINUE IF ( K.LE.A(J) ) THEN INCREMENT THE KTH SPOT II (K) = II (K)+1 BEGIN HAVE NEXT Q OR NEED TO CARRY IF ( II(K).LE.1 ) THEN BEGIN HAVE NEXT Q INCREMENT COUNTER COUNT = COUNT + 1 FINALIZE THE 'NEARBY LATTICE POINT' DO 26, I=1,A(J) Q(B(J,I)) = II(I) CONTINUE IF (PFLAG) THEN WRITE (3,5300) (II(I), I=1,A(J)) FORMAT (' CHECK2: II ',20I3) WRITE (3,5400) (Q(I), I=1,M) FORMAT (' CHECK2: Q ',20I3) IF (PFLAGl) THEN WRITE (3,5450) FORMAT (' ') ENDIF ENDIF Q 5500 5600 5700 5750 147 INVOKE CHECKER CALL SLICK (M,D,X,Q,FLAG,PFLAG1) IF (PFLAGl) THEN CFLAG = CFLAG-1 PFLAGl = (CFLAG.GT.0) ENDIF BEGIN DOES X PASS? IF (FLAG) THEN IF (PFLAG) THEN WRITE (3,5500) FORMAT (' CHECK2: THIS POINT PASSES.') WRITE (3,5600) WRITE (3,5600) FORMAT (' ') ENDIF YES! THE POINT PASSES! RETURN ELSE POINT DOESN'T PASS IF (PFLAG) THEN WRITE (3,5700) FORMAT (' CHECK2: FLUNKS WITH Q.') WRITE (3,5750) FORMAT ( ' ' ) ENDIF ENDIF END DOES X PASS? K = 1 END HAVE NEXT Q ELSE BEGIN NEED TO CARRY II(K) = 0 K = K+1 END NEED TO CARRY ENDIF END HAVE NEXT Q OR NEED TO CARRY? GOTO 200 ENDIF END FETCH NEXT Q J = J-l GOTO 100 148 ENDIF C END LOOP ON DIGITS C HAVE RUN THROUGH OUR LIST OF 'NEARBY LATTICE POINTS' C THIS POINT HAS NOT PASSED IF (PFLAG) THEN WRITE (3,5800) 5800 FORMAT (' CHECK2: THE POINT HAS FLUNKED ALL TESTS. ') WRITE (3,5900) WRITE (3, 5900) 5900 FORMAT (' ') ENDIF RETURN END SUBROUTINE CHECK3 (M,D,F,X,FLAG,COUNT,PFLAG1,CFLAG2) A PROGRAM TO CHECK POINTS IN THE 1/D LATTICE THE METHOD IS TO GENERATE ALL INTEGERS WITH COORDINATES BOUNDED ABOVE BY SOME NUMBER 'F' & TO BOUND THE NORM OF X-Q ON THE l/D CELL VIA 'SLICK' . 000 0 C23456789012345678901234567890123456789012345678901234567890123456 C 1 2 3 4 5 6 IMPLICIT INTEGER (A-Z) DIMENSION A(0:20), X(20), Q(20) LOGICAL FLAG, FLAGl, FLAG2, PFLAGl, PFLAG2 SAVE PFLAG2 = (CFLAG2.GT.0) IF (PFLAGl) THEN WRITE (3,5000) (X(I), I=1, M) 5000 FORMAT (' CHECK3: X ',2013) ENDIF CALL XSLICK (M, D, X, Q, FLAG, PFLAG2) CALL SPGEN3 (M, F, A, FLAGl , PFLAGl) C START OF PATTERN LOOP 12 CONTINUE IF (FLAGl) THEN IF (PFLAGl) THEN WRITE (3,5100) (A(I), I=0, F) 5100 FORMAT (' CHECK3: A ',2013) ENDIF CALL SPOIN3 (M, F, A, Q, FLAG2 , PFLAGl) 5200 5300 5400 5500 5550 149 START OF 'NEARBY LATTICE POINT' Q LOOP CONTINUE IF (FLAG2) THEN IF (PFLAGl) THEN WRITE (3,5200) (Q(I), I=1, M) FORMAT (' CHECK3: Q ',2013) ENDIF INCREMENT COUNTER & PERFORM CHECK COUNT = COUNT + 1 CALL SLICK (M,D,X,Q,FLAG,PFLAG2) IF (PFLAG2) THEN CFLAGZ = CFLAG2-1 PFLAG2 = (CFLAG2.GT.0) ENDIF IF (FLAG) THEN IF (PFLAGl) THEN WRITE (3,5300) FORMAT (' CHECK3: THIS POINT PASSES.') WRITE (3,5400) WRITE (3,5400) FORMAT (' ') ENDIF POINT X PASSES -- RETURN (FLAG WILL BE .TRUE.) RETURN ENDIF GET NEXT 'NEARBY LATTICE POINT' Q IF (PFLAGl) THEN WRITE (3,5500) FORMAT (' CHECK3: POINT FLUNKS WITH THIS 0') WRITE (3,5550) FORMAT (' ') ENDIF CALL POINT3 (M,F,A,Q,FLAG2,PFLAG1) GOTO 14 ENDIF END OF 'NEARBY LATTICE POINT' Q LOOP GET NEXT PATTERN CALL PGEN3 (M,F,A,FLAG1,PFLAG1) GOTO 12 ENDIF END OF PATTERN LOOP IF WE REACH HERE, WE HAVE CHECKED AS MANY Q AS THE BOUND 'F' ALLOWS. THUS, THE POINT X FAILS. 150 IF (PFLAGl) THEN ‘ WRITE (3,5600) 5600 FORMAT (' CHECK3: POINT HAS FLUNKED ALL TESTS') WRITE (3,5700) WRITE (3,5700) 5700 FORMAT (' ') ENDIF C POINT X FAILS -- RETURN (FLAG WILL BE .FALSE.) RETURN END SUBROUTINE SPGEN3 (M,F,A,FLAG,PFLAG) C PATTERN GENERATOR. RETURNS THE RESULT IN THE ARRAY A(I). C . THE MULTISET \(\( 0**A(0), 1**A(1), ... \)\) CORRESPONDS TO A c AND THE POINT x = SUM \( X(I)*E(I) \). WHERE C A(I) = #\( J: X(J) = I \). UNDER THE ASSUMPTION THAT ‘ c A(0) = #\( J: X(J) = 0 \) 1. C METHOD USED TO GENERATE PATTERNS IS TO CARRY A 1 FROM.THE C FIRST NON ZERO A(I) TO A(I+1) AND IF I>0, DROP THE REST C OF A(I) TO A(0). - C23456789012345678901234567890123456789012345678901234567890123456 c 1 2 3 4 5 6 IMPLICIT INTEGER (AeZ) DIMENSION A(0:20), B(0:20) LOGICAL FLAG,PFLAG SAVE C INITIALIZE A(0)=M 3(0) =M- 1 DO 6, I=1, F A(I) = 0 B(I) = 0 6 CONTINUE FLAG = .TRUE. RETURN ENTRY PGEN3 (M,F,A,FLAG,PFLAG) IF (PFLAG) THEN WRITE (3,5000) (A(I), I=0, F) 5000 FORMAT (' PGEN3: OLD PATTERN',20I3) ENDIF I=0 C FIND A NON ZERO B(I) 5100 5200 5300 5400 5500 5600 151 DO WHILE (B(I).EQ.0) CONTINUE IF (B(I).EQ.0) THEN I = I+1 GOTO 12 ENDIF REPEAT IF (I.EQ.F) THEN IF (PFLAG) THEN ‘WRITE (3,5100) I FORMAT (' PGEN3: INDEX I',I4) WRITE (3,5200) FORMAT (' PGEN3: NO MORE PATTERNS') WRITE (3,5300) WRITE (3,5300) FORMAT (' ') ENDIF OUT OF PATTERNS FLAG = .FALSE. RETURN ENDIF CARRY THE 1 UPWARDS AND DROP THE REST DOWN. B(I+1) = B(I+1)+1 A(I+1) a B(I+1) B(O) = B(I)-1 A(O) = B(0)+1 IF I .GT. 0 THEN ZERO A(I) & B(I) IF (I.NE.0) THEN B(I) = 0 A(I) = 0 ENDIF IF (PFLAG) THEN WRITE (3,5400) I FORMAT (' PGEN3: INDEX I',I4) WRITE (3,5500) (A(I), I=0,F) FORMAT (' PGEN3: NEW PATTERN',2013) WRITE (3,5600) WRITE (3,5600) FORMAT ( ' ' ) ENDIF RETURN END 152 SUBROUTINE SPOIN3 (M,F,A,X,FLAG,PFLAG) C HIS ROUTINE CONVERTS THE PATTERN IN A INTO THE POINT IN X. C23456789012345678901234567890123456789012345678901234567890123456 C 1 2 3 4 5 6 IMPLICIT INTEGER (A-Z) DIMENSION A(0:20), X(20) LOGICAL FLAG, PFLAG SAVE M1 = M-1 C INITIALIZE THE POINT J = 0 DO 8, I=0,F DO 6, XX=1, A(I) J = J+1 X(J) = I 6 CONTINUE 8 CONTINUE IF (PFLAG) THEN WRITE (3,5000) (A(I), I = 0, F) 5000 FORMAT (' SPOIN3: A ',2013) WRITE (3,5200) (X(I),I=1, M) 5200 FORMAT (' SPOIN3: x ',2013) WRITE (3.5300) WRITE (3,5300) 5300 FORMAT (' ') ENDIF FLAG = .TRUE. C HAVE THE FIRST POINT & RETURN RETURN ENTRY POINT3 (M,F,A,X,FLAG,PFLAG) C GET NEXT POINT IF (PFLAG) THEN WRITE (3,5400) (X(I), I=1,M) 5400 FORMAT (' POINT3: OLD x ',2013) ENDIF C FIRST FIND X(I) SUCH THAT C X(I) < X(I+1) >= X(I+2) >= ... >= X(M) I = M1 C DO WHILE ( X(I) .GE. X(I+1) ) 20 CONTINUE 5500 5600 N0 00 5700 153 IF ( X(I) .GE. X(I+1) ) THEN IF (I.EQ.1) THEN IF (PFLAG) THEN WRITE (3,5500) FORMAT (' POINT3: END POINT GENERATION!) WRITE (3,5600) WRITE (3,5600) FORMAT (' ') ENDIF POINT IN INVERSE LEXICOGRAPHICAL ORDER. RETURN FLAG = .FALSE. RETURN ENDIF I = I-1 GOTO 20 ENDIF REPEAT J = I+l FIND J SUCH THAT X(J) > X(I) AND X(J+1) <= X(I) THAT IS, THE MINIMAL X(J) > X(I) WITH J > I. DO WHILE ( (J.LT.M) .AND. (X(I).LT.X(J+1)) ) CONTINUE IF (J.LT.M) THEN IF ( X(I).LT.X(J+1) ) THEN J=J+1 GOTO 22 REPEAT ENDIF ENDIF IF (PFLAG) THEN’ WRITE (3,5700) I,J FORMAT (' POINT3: POINTERS I,J', 214) ENDIF NOW SWAP X(I) & X(J) K = X(I) X(I) = X(J) X(J) = K NOW INVERT TAIL OF THE LIST: PUT IN INCREASING ORDER. I J I+l b4 -130! 5800 5900 00 00 154 DO WHILE (I.LT.J) CONTINUE IF (I.LT.J) THEN K = X(I) X(I) = X(J) X(J) = K I=I+1 J=J-1 GOTO 2 4 ENDIF REPEAT IF (PFLAG) THEN WRITE (3,5800) (X(I), I=1,M) FORMAT (' POINT3: NEW X ',2013) WRITE (3,5900) WRITE (3,5900) FORMAT (' ') ENDIF RETURN END SUBROUTINE SSLICK (M, D, X, Q, FLAG, PFLAG) IMPLICIT INTEGER (A-Z) LOGICAL FLAG, PFLAG DIMENSION X(20) , Q(20) , C(10) DIMENSION REALX(10), IMAGX(10) DIMENSION REALE(20,10) , IMAGE (20,10) DIMENSION REALED(20,10) , IMAGED (20,10) DOUBLE PRECISION RM, RD, ANGLE, C, CMIN, RADIUS, RADSQD DOUBLE PRECISION REALE, IMAGE, REALED, IMAGED, REALX, IMAGX DOUBLE PRECISION APPROX, BOUND, LENGTH, DIFF DOUBLE PRECISION TEMPl, TEMP2 DOUBLE PRECISION OKBND, NOKBND, DIFBND SAVE THE ARITHMETIC IS SLICKED UP TO DOUBLE PRECISION &. CQ4PLEX NUMBERS HAVE REAL & IMAGINARY. PARTS SEPARATED . THIS ROUTINE IS UPGRADED WITH AN ITERATIVE PROCEDURE TO FIND THE MAXIMUM. C23456789012345678901234567890123456789012345678901234567890123456 C 1 2 3 4 5 6 RM=DBLE(M) RD = DBLE(D) M1 = M - 1 5000 5100 5200 5300 5400 5500 5600 155 D1 = D 1 S = M]. 2 ANGLE = 6.28318 53071 79586 DO / RM \ I RADSQD = DBLE( (M*M - 1) / 24) RADIUS = DSQRT( RADSQD ) / RD RADSQD=RADSQD/ (RD*RD) DIFBND = 1D-10 CNTBND = 100 OKBND = 1 - 1D-6 NOKBND = 1 + 1D—6 NOTE E = ZETA ** (I*J) ED = E / D DO 4, I=1,M DO 2, J=1,S REALE(I,J) = DCOS( ANGLE * MOD(I*J,M) ) IMAGE(I,J) = DSIN( ANGLE * MOD(I*J,M) ) REALED(I,J) = REALE(I,J) / RD IMAGED(I,J) = IMAGE(I,J) / RD CONTINUE CONTINUE IF (PFLAG) THEN WRITE (3,5000) RADIUS, RADSQD FORMAT (' SSLICK: RADIUS, RADSQD ',2F16.12) WRITE (3,5100) OKBND,NOKBND FORMAT (' SSLICK: OKBND,NOKBND ',2F16.12) WRITE (3,5200) FORMAT (' ') WRITE (3,5300) J FORMAT (' SSLICK: CONJUGATE NUMBER', I4) WRITE (3,5400) (REALE(I,J), IMAGE(I,J), - REALED(I,J), IMAGED(I,J), I=1,M) FORMAT (' SSLICK: E,ED',4F16.12) WRITE (3,5500) FORMAT (' ') CONTINUE WRITE (3, 5600) WRITE (3, 5600) FORMAT (' ') ENDIF RETURN ENTRY XSLICK (M, D, X, Q, FLAG, PFLAG) 16 18 5700 5800 5900 6000 6100 20 156 REALX(J) = REAL PART OF JTH CONJUGATE OF x. IMAGX(J) = IMAGINARY PART OF JTH CONJUGATE OF x. DO 18, J=1, S 0D0 ODO REALX(J) IMAGX(J) DO 16, I=1,M REALX(J) = X(I)*REALED(I,J) + REALX(J) IMAGX(J) = X(I)*IMAGED(I,J) + IMAGX(J) CONTINUE CONTINUE IF (PFLAG) THEN WRITE (3,5700) (X(I), I=1,M) FORMAT (' XSLICK: X ',20I3) WRITE (3,5800) (J,REALX(J),IMAGX(J), J=1,S) FORMAT (' XSLICK: J,REALX,IMAGX ',I4,2F16.12) WRITE (3,5900) WRITE (3,5900) FORMAT (' ') ENDIF RETURN ENTRY SLICK (M, D, X, Q, FLAG, PFLAG) IF (PFLAG) THEN WRITE (3,6000) (X(I), I=1,M) FORMAT (' SLICK: X ',2013) WRITE (3,6100) (Q(I), I=1,M) FORMAT (' SLICK: Q ',20I3) ENDIF DETERMINE THE C(J) = \!Z(J)\! & FIND THE MINIMAL ONE. CMIN = 1D10 DO 22' J=1,S TEMPl TEMP2 REALX(J) IMAGX(J) DO 20, I=1,M TEMPl = TEMPl - Q(I)*REALE(I,J) TEMP2 = TEMPZ - Q(I)*IMAGE(I,J) CONTINUE C(J) = DSQRT( TEMP1*TEMP1 + TEMP2*TEMP2 ) IF ( C(J) .LT. CMIN) THEN CMIN = C(J) ENDIF IF (PFLAG) THEN 6200 22 6300 42 6400 6450 6500 6600 157 WRITE (3,6200) J,TEMP1,TEMP2,C(J) FORMAT (' SLICK: J,TEMP1,TEMP2,C',I4,3F16.12) ENDIF CONTINUE IF (PFLAG) THEN WRITE (3,6300) CMIN FORMAT (' SLICK: CMIN ',F16.12) ENDIF APPROX = RADIUS COUNT = 0 ITERATION LOOP TO COMPUTE MAXIMUM DO WHILE (COUNT.LT.CNTBND) CONTINUE IF (COUNT.LT.CNTBND) THEN COUNT = COUNT + 1 TEMPl = (APPROX+CMIN)*APPROX*4DO LENGTH = 0D0 BOUND = 1D0 COMPUTE A NEW BOUND & LENGTH DO 42, J21,S J TEMP2 (DSQRT(C(J)*C(J)+TEMP1)-C(J))*.5D0 BOUND ( TEMP2+C(J) ) * BOUND LENGTH = TEMP2*TEMP2 + LENGTH CONTINUE DIFF = LENGTH - RADSQD IF (PFLAG) THEN WRITE (3,6400) APPROX, BOUND FORMAT (' SLICK: APPROX, BOUND',2F16.12) WRITE (3,6450) LENGTH, DIFF FORMAT (' SLICK: LENGTH, DIFF ',2F16.12) ENDIF IF (DIFF.GE.-DIFBND) THEN IF (BOUND.LT.OKBND) THEN IF (PFLAG) THEN WRITE (3,6500) FORMAT (' SLICK: THIS POINT PASSES.') WRITE (3,6600) WRITE (3,6600) FORMAT (' ') ENDIF FLAG = .TRUE. RETURN ENDIF 6800 6900 7000 7100 158 ENDIF IF (DIFF.LE.DIFBND) THEN IF (BOUND.GT.NOKBND) THEN IF (PFLAG) THEN WRITE (3,6800) FORMAT (' SLICK: THIS POINT FLUNKS.') WRITE (3,6900) WRITE (3,6900) FORMAT (' ') ENDIF THIS ONE FLUNKS. RETURN. FLAG = .FALSE. RETURN ENDIF ENDIF APPROX= APPROX*RADIUS/DSQRT(LENGTH) LOOP BACK & REITERATE BOUNDS IF ( ABS(DIFF).GT.DIFBND ) THEN GOTO 40 ENDIF ENDIF IF (PFLAG) THEN WRITE (3,7000) FORMAT (' SLICK: THIS POINT FLUNKS.') WRITE (3,7100) WRITE (3,7100) FORMAT (' ') ENDIF FLAG = .FALSE. RETURN C23456789012345678901234567890123456789012345678901234567890123456 C 1 2 3 4 5 6 END Appendix B Flowcharts @ W MAM. , V , initialize I DO get first pattern I l inc. count 2 finalize DO cell check write all counts inc. count 3 more V” DO get first point oints‘? inc. count10 D 7 'n inc. count4 write failed pt. ("DI Oeetpmt l I DOcheck1 DO check 2 inc. count 6 DO check 3 159 increment count Choose i minimal with b(i) at O compute new sum & ssum .L get next pattern .L compute new mnorm mnorm s bound or mnorm > ubound? 160 flag := more patterns I awy=an l I all) := b(i) (M e A 219nm: fl flag 2: true I l h := h + d*a(j)*(a(j)+m)/2 - a(j)*(m‘j+d*k-sum) l h <0 ? ”s W flag := false I If decrementj J 161 b:=a i 2= 0 3mm 51'39 3‘ "“9 W ssflag := true yes ”9 [ increment i 4 ® b(s) := b(s)-2 . no yes x(1) := s 03 x(m) := s V G_ s := i { ¢ v sflag := false (m 3.. bis) := b(SH b(ss) := b(ss)-1 v x(1) := 5 ss 1:? x(m) 2: ss Q— s :=i 4 ® ssflag := false yes "0 <1— 3 .. < ¢ ssflag := false (m. raise Y Q— 35 := i 4 W m m l l decrement i l I j 2: 1+1 I | flag I: no a f more points i increment] ] -. . * swap x(i) 8. X(1') I .I .= | +1 k.— swap mort(i) & MM!) 7 j := m -1 7 update sort I .& . . , . . swasgvfiipoftg) 81mm) ——q incrementi J update sort decrementj flag := more ’ points 163 ‘ V C(J) = | XQ(J) l cmin = min{c(j)} 164 w W W V initialize a & b q I: 0 j I: d"! I decrementj ¢ ¢.. 13 I increment ii(k) I I incrementk I T ii(k) := o I increment count H DO check point qlbli.i)) == “6) 165 w W W V initialize a & b q I: 0 j I: d-1 A 7 I'D I decrement j ¢ ii := 0 I yes 1E r. .1 I I increment ii(k) I I incrementk I I increment count H DO check point q(b(j,i)) :-.-ii(i) i 166 w mm W V initialize a 8: b q I: 0 j 2= (1"! I decrementj ¢ ®., 1 I increment ii(k) I I increment k I T I increment count I.__H DO check point albirdil :=ll(l) _ f 167 BIBLIOGRAPHY [13] [C111] [(3112] [CO] [CD] [Ei] [Eu] [Ga] [GU] [Ln] BIBLIOGRAPHY E. S. Barnes, H. P. F. Swinnerton-Dyer, The inhomogeneous minima of binary quadratic forms, Acts Math. 87 (1952) 259-323. H. Chatland, 0n the euclidean algorithm in quadratic number fields, Bull. AMS 55 (1949) 948-953. H. Chatland, H. Davenport, Euclid's algorithm in real quadratic fields, Canad. J. Math. 2 (1950) 289-296. H. Cohn, Advanced number theory, Dover Publications, Inc., New York, 1962. C. W. Curtis, 1. Reiner, Representation Theory of Finite Groups and Associative Algebras, Interscience Publishers, New York, 1962. G. Eisenstein, Mathematische Werke Band II, Chelsea Publishing Company, New York, 1975. Euclid, Elements. K. F. Gauss, Werlce Zweiter Band, Georg Olms Verlag, Hildesheim and New York, 1973. R. Gupta, M. R. Murry, V. K. Murry, The Euclidean algorithm for S-integers, Numbgr theory (Montreal, Que., 1985), CMS Conference Proceedings, 7, (A M 1987). R. B. Lakein, Euclid's algorithm in complex quartic fields, Acta Arith. 20 (1972), 393-400. H. W. Lenstra, Jr., Lectures on euclidean rings, Bielfeld, 1974. H. W. Lenstra, Jr., Euclid's algorithm in cyclotomicfields, J. London Math. Soc. (2) 10 (1975), 457-465. H. W. Lenstra, Jr., Quelques exemples d'anneaux euclidiens, C. R. Acad. Sc. Paris, 861'. A, 286 (1978), 683-685. H. W. Lenstra, Jr., Euclidean number fields I, Math. Intell. 2 (1979), 6-15. H. W. Lenstra, Jr., 0n Artin's Conjecture and Euclid's Algorithm in Global Fields, Inventiones Math. 42 (1977), 201-224 J. M. Masley, H. L. Mont om , Cyclotomic fields with unique factorization, J. Reine Angew. Math. 286 287 ( 976), 248-256. 168 [M0] [N1 [Oj] [On] [R] [3] [W3] 169 T. Motzkin, The Euclidean algorithm, Bull. A. M. S. SS (1949), 1142-1146. A. Nijenhuis, H. S. Wilf, Combinatorial Algorithms, Academic Press, New York, 1975. T. Ojala, Euclid's algorithm in the cyclotomic field Q(C16), Math. Comp. 31 (1977), 268-273. J. Ouspensky, Note sur les nombres entiers dependant d'une racine cinquieme de l'unité, Math. Ann. 66 (1909), 109-112. F. S. Roberts, Applied Combinatorics, Prentice-Hall, New Jersey, 1975. H. M. Stark, A complete determination fo the complex quadratic fields of calss-number one, Mich. Math. J. 14 (1967), 1-24. P. L. Wantzel, Comptes Rendus l‘Académe des Sciences 24 (1847). P. J. Weinberger, 0n euclidean rings of algebraic integers, Proc. Symp. Pure Math., 24 (Analytic Number Theory). 321-332 (A.M.S., 1973). 4 145 54 1111111