Quadratic forms and quaternion algebras: algorithms and arithmetic by John Michael Voight B.S. (Gonzaga University) 1999 A dissertation submitted in partial satisfaction of the requirements for the degree of Doctor of Philosophy in Mathematics in the Graduate Division of the University of California at Berkeley Committee in charge: Professor Hendrik Lenstra, Chair Professor Bjorn Poonen Professor Roger Purves Spring 2005 The dissertation of John Michael Voight is approved: Chair Date Date Date University of California at Berkeley Spring 2005 Quadratic forms and quaternion algebras: algorithms and arithmetic Copyright 2005 by John Michael Voight 1 Abstract Quadratic forms and quaternion algebras: algorithms and arithmetic by John Michael Voight Doctor of Philosophy in Mathematics University of California at Berkeley Professor Hendrik Lenstra, Chair This thesis comes in two parts which can be read independently of one another. In the first part, we prove a result concerning representation of primes by quadratic forms. Jagy and Kaplansky exhibited a table of 68 pairs of positive definite binary quadratic forms that represent the same odd primes and conjectured that their list is complete outside of “trivial”pairs. Weconfirmtheirconjecture,andinfactfindallpairsofsuchformsthatrepresent the same primes outside of a finite set. In the second part, we investigate a constellation of results concerning algorithms for quaternionalgebrasandtheirapplicationtoShimuracurves. LetAbeaquaternionalgebraover a number field F. We discuss the computational complexity and, in many cases, give effective algorithms to solve the following problems: Determine if A=M (F), and if so, exhibit an isomorphism; • ∼ 2 Find a maximal order A; and • O ⊂ Determine if a right ideal I is principal, and if so, exhibit a generator ξ. • ⊂O Wethenpresentfastmethodsforcomputingthevalueofhypergeometricseriestolargeprecision. Putting these together, we are able to compute special values of the map j :Γ H P1 for Γ a \ → C 2 compacttrianglegroup,whichwemayrecognizeasputativealgebraicnumbersbyalsocomputing their Galois conjugates. We apply this to construct the canonical polynomial Φ (x,y) for the N curve X (N) and to find nontorsion points on some elliptic curves over number fields. 0 i To the memory of those who stood by me and are now gone ii Contents I Quadratic forms 1 1 Primes represented by quadratic forms 2 1.1 Fields of definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2 Ring class fields . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3 Characterizing equivalence via class groups . . . . . . . . . . . . . . . . . . . . . 20 2 Finding the list of forms 26 2.1 Forms with the same fundamental discriminant . . . . . . . . . . . . . . . . . . . 26 2.2 Bounding class groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.3 Computing class groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 2.4 Finding the pairs of quadratic forms . . . . . . . . . . . . . . . . . . . . . . . . . 37 3 Tables 39 II Quaternion algebras 49 4 Quaternion algebras 50 4.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 4.2 Fundamental algorithms for quaternion algebras . . . . . . . . . . . . . . . . . . 58 4.3 Computing a maximal order . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.4 Class group computations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 5 Shimura curves 84 5.1 Triangle groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 5.2 Computing hypergeometric series . . . . . . . . . . . . . . . . . . . . . . . . . . . 91 5.3 CM points and Shimura reciprocity . . . . . . . . . . . . . . . . . . . . . . . . . . 104 5.4 Examples and applications. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 6 Tables 117 Bibliography 125 iii Acknowledgements I am very grateful to my thesis adviser, Hendrik Lenstra, for patiently guiding my intellectual developmentin innumerablewaysandprovidingsupportwhile writing this dissertation. I would like to thank Bjorn Poonen and Bernd Sturmfels for teaching me so much; Peter Stevenhagen, Pete Clark, and Jared Weinstein for their helpful comments on portions of this thesis; Samit Dasgupta and Noam Elkies for their incredible insights and encouragement; Ronald van Luijk forhisconstantcompanionship;andWilliamSteinandtheMECCAHclusterforcomputertime. SurvivingtheprocessofwritingthisdissertationwasonlymadepossiblebyPaulBerg. Finally,I wouldlike to givemy sincerestgratitudeto AaronMinnis, DavidMichaels,KristinOlson,Missy Longshore, Mary Weaver, my mother, and the rest of my family and friends for their love and understanding. 1 Part I Quadratic forms 2 Chapter 1 Primes represented by quadratic forms The forms x2 +9y2 and x2 +12y2 represent the same set of prime numbers, namely, thoseprimespwhichcanbe writtenp=12n+1. Whatotherlikepairsofformsexist? Jagyand Kaplansky[27] performeda computer searchfor pairs that representthe same set of odd primes andfound certain“trivial”pairswhichoccur infinitely often andlisted othersporadic examples. They conjecture that their list is complete. In this part, using the tools of class field theory we give a provably complete list of such pairs. By a form Q we mean an integral positive definite binary quadratic form Q = ax2 +bxy +cy2 Z[x,y]; the discriminant of Q is b2 4ac = D = df2 < 0, where d is the ∈ − discriminant of Q(√D), the fundamental discriminant, and f 1. We will often abbreviate ≥ Q= a,b,c . h i Throughout, we look for forms that represent the same primes outside of a finite set— we say then that they represent almost the same primes. A form represents the same primes as