Advanced Topics in Computational Number Theory, 2000
Graduate Texts in Mathematics Series, Vol. 193

1. Fundamental Results and Algorithms in Dedekind Domains.- 1.1 Introduction.- 1.2 Finitely Generated Modules Over Dedekind Domains.- 1.2.1 Finitely Generated Torsion-Free and Projective Modules.- 1.2.2 Torsion Modules.- 1.3 Basic Algorithms in Dedekind Domains.- 1.3.1 Extended Euclidean Algorithms in Dedekind Domains.- 1.3.2 Deterministic Algorithms for the Approximation Theorem.- 1.3.3 Probabilistic Algorithms.- 1.4 The Hermite Normal Form Algorithm in Dedekind Domains.- 1.4.1 Pseudo-Objects.- 1.4.2 The Hermite Normal Form in Dedekind Domains.- 1.4.3 Reduction Modulo an Ideal.- 1.5 Applications of the HNF Algorithm.- 1.5.1 Modifications to the HNF Pseudo-Basis.- 1.5.2 Operations on Modules and Maps.- 1.5.3 Reduction Modulo p of a Pseudo-Basis.- 1.6 The Modular HNF Algorithm in Dedekind Domains.- 1.6.1 Introduction.- 1.6.2 The Modular HNF Algorithm.- 1.6.3 Computing the Transformation Matrix.- 1.7 The Smith Normal Form Algorithm in Dedekind Domains.- 1.8 Exercises for Chapter 1.- 2. Basic Relative Number Field Algorithms.- 2.1 Compositum of Number Fields and Relative and Absolute Equations.- 2.1.1 Introduction.- 2.1.2 Étale Algebras.- 2.1.3 Compositum of Two Number Fields.- 2.1.4 Computing (?1 and ?2.- 2.1.5 Relative and Absolute Defining Polynomials.- 2.1.6 Compositum with Normal Extensions.- 2.2 Arithmetic of Relative Extensions.- 2.2.1 Relative Signatures.- 2.2.2 Relative Norm, Trace, and Characteristic Polynomial.- 2.2.3 Integral Pseudo-Bases.- 2.2.4 Discriminants.- 2.2.5 Norms of Ideals in Relative Extensions.- 2.3 Representation and Operations on Ideals.- 2.3.1 Representation of Ideals.- 2.3.2 Representation of Prime Ideals.- 2.3.3 Computing Valuations.- 2.3.4 Operations on Ideals.- 2.3.5 Ideal Factorization and Ideal Lists.- 2.4 The Relative Round 2 Algorithm and Related Algorithms.- 2.4.1 The Relative Round 2 Algorithm.- 2.4.2 Relative Polynomial Reduction.- 2.4.3 Prime Ideal Decomposition.- 2.5 Relative and Absolute Representations.- 2.5.1 Relative and Absolute Discriminants.- 2.5.2 Relative and Absolute Bases.- 2.5.3 Ups and Downs for Ideals.- 2.6 Relative Quadratic Extensions and Quadratic Forms.- 2.6.1 Integral Pseudo-Basis, Discriminant.- 2.6.2 Representation of Ideals.- 2.6.3 Representation of Prime Ideals.- 2.6.4 Composition of Pseudo-Quadratic Forms.- 2.6.5 Reduction of Pseudo-Quadratic Forms.- 2.7 Exercises for Chapter 2.- 3. The Fundamental Theorems of Global Class Field Theory.- 3.1 Prologue: Hilbert Class Fields.- 3.2 Ray Class Groups.- 3.2.1 Basic Definitions and Notation.- 3.3 Congruence Subgroups: One Side of Class Field Theory.- 3.3.1 Motivation for the Equivalence Relation.- 3.3.2 Study of the Equivalence Relation.- 3.3.3 Characters of Congruence Subgroups.- 3.3.4 Conditions on the Conductor and Examples.- 3.4 Abelian Extensions: The Other Side of Class Field Theory.- 3.4.1 The Conductor of an Abelian Extension.- 3.4.2 The Frobenius Homomorphism.- 3.4.3 The Artin Map and the Artin Group Am(L/K).- 3.4.4 The Norm Group (or Takagi Group) Tm(L/K).- 3.5 Putting Both Sides Together: The Takagi Existence Theorem 154.- 3.5.1 The Takagi Existence Theorem.- 3.5.2 Signatures, Characters, and Discriminants.- 3.6 Exercises for Chapter 3.- 4. Computational Class Field Theory.- 4.1 Algorithms on Finite Abelian groups.- 4.1.1 Algorithmic Representation of Groups.- 4.1.2 Algorithmic Representation of Subgroups.- 4.1.3 Computing Quotients.- 4.1.4 Computing Group Extensions.- 4.1.5 Right Four-Term Exact Sequences.- 4.1.6 Computing Images, Inverse Images, and Kernels.- 4.1.7 Left Four-Term Exact Sequences.- 4.1.8 Operations on Subgroups.- 4.1.9 p-Sylow Subgroups of Finite Abelian Groups.- 4.1.10 Enumeration of Subgroups.- 4.1.11 Application to the Solution of Linear Equations and Congruences.- 4.2 Computing the Structure of (?K/m)*.- 4.2.1 Standard Reductions of the Problem.- 4.2.2 The Use of p-adic Logarithms.- 4.2.3 Computing (?K/pk)* by Induction.- 4.2.4 Representation of Elements of (?K/m)*.- 4.2.5 Computing (?K/m)*.- 4.3 Computing Ray Class Groups.- 4.3.1 The Basic Ray Class Group Algorithm.- 4.3.2 Size Reduction of Elements and Ideals.- 4.4 Computations in Class Field Theory.- 4.4.1 Computations on Congruence Subgroups.- 4.4.2 Computations on Abelian Extensions.- 4.4.3 Conductors of Characters.- 4.5 Exercises for Chapter 4.- 5. Computing Defining Polynomials Using Kummer Theory.- 5.1 General Strategy for Using Kummer Theory.- 5.1.1 Reduction to Cyclic Extensions of Prime Power Degree.- 5.1.2 The Four Methods.- 5.2 Kummer Theory Using Hecke’s Theorem When ?? ? K.- 5.2.1 Characterization of Cyclic Extensions of Conductor m and Degree ?.- 5.2.2 Virtual Units and the ?-Selmer Group.- 5.2.3 Construction of Cyclic Extensions of Prime Degree and Conductor m.- 5.2.4 Algorithmic Kummer Theory When ?? ? K Using Hecke.- 5.3 Kummer Theory Using Hecke When ?? ? K.- 5.3.1 Eigenspace Decomposition for the Action of ?.- 5.3.2 Lift in Characteristic 0.- 5.3.3 Action of ? on Units.- 5.3.4 Action of ? on Virtual Units.- 5.3.5 Action of ? on the Class Group.- 5.3.6 Algorithmic Kummer Theory When ?? ? K Using Hecke.- 5.4 Explicit Use of the Artin Map in Kummer Theory When ?n ? K.- 5.4.1 Action of the Artin Map on Kummer Extensions.- 5.4.2 Reduction to ? ? US(K)/US(K)n for a Suitable S.- 5.4.3 Construction of the Extension L/K by Kummer Theory.- 5.4.4 Picking the Correct ?.- 5.4.5 Algorithmic Kummer Theory When ?n ? K Using Artin.- 5.5 Explicit Use of the Artin Map When ?n ? K.- 5.5.1 The Extension Kz/K.- 5.5.2 The Extensions Lz/Kz and Lz/K.- 5.5.3 Going Down to the Extension L/K.- 5.5.4 Algorithmic Kummer Theory When ?n ? K Using Artin.- 5.5.5 Comparison of the Methods.- 5.6 Two Detailed Examples.- 5.6.1 Example 1.- 5.6.2 Example 2.- 5.7 Exercises for Chapter 5.- 6. Computing Defining Polynomials Using Analytic Methods.- 6.1 The Use of Stark Units and Stark’s Conjecture.- 6.1.1 Stark’s Conjecture.- 6.1.2 Computation of ?K,S?(0, ?).- 6.1.3 Real Class Fields of Real Quadratic Fields.- 6.2 Algorithms for Real Class Fields of Real Quadratic Fields.- 6.2.1 Finding a Suitable Extension N / K.- 6.2.2 Computing the Character Values.- 6.2.3 Computation of W(?).- 6.2.4 Recognizing an Element of ?K.- 6.2.5 Sketch of the Complete Algorithm.- 6.2.6 The Special Case of Hilbert Class Fields.- 6.3 The Use of Complex Multiplication.- 6.3.1 Introduction.- 6.3.2 Construction of Unramified Abelian Extensions.- 6.3.3 Quasi-Elliptic Functions.- 6.3.4 Construction of Ramified Abelian Extensions Using Complex Multiplication.- 6.4 Exercises for Chapter 6.- 7. Variations on Class and Unit Groups.- 7.1 Relative Class Groups.- 7.1.1 Relative Class Group for iL/K.- 7.1.2 Relative Class Group for NL/K.- 7.2 Relative Units and Regulators.- 7.2.1 Relative Units and Regulators for iL/K.- 7.2.2 Relative Units and Regulators for NL/K.- 7.3 Algorithms for Computing Relative Class and Unit Groups.- 7.3.1 Using Absolute Algorithms.- 7.3.2 Relative Ideal Reduction.- 7.3.3 Using Relative Algorithms.- 7.3.4 An Example.- 7.4 Inverting Prime Ideals.- 7.4.1 Definitions and Results.- 7.4.2 Algorithms for the S-Class Group and S-Unit Group.- 7.5 Solving Norm Equations.- 7.5.1 Introduction.- 7.5.2 The Galois Case.- 7.5.3 The Non-Galois Case.- 7.5.4 Algorithmic Solution of Relative Norm Equations.- 7.6 Exercises for Chapter 7.- 8. Cubic Number Fields.- 8.1 General Binary Forms.- 8.2 Binary Cubic Forms and Cubic Number Fields.- 8.3 Algorithmic Characterization of the Set U.- 8.4 The Davenport-Heilbronn Theorem.- 8.5 Real Cubic Fields.- 8.6 Complex Cubic Fields.- 8.7 Implementation and Results.- 8.7.1 The Algorithms.- 8.7.2 Results.- 8.8 Exercises for Chapter 8.- 9. Number Field Table Constructions.- 9.1 Introduction.- 9.2 Using Class Field Theory.- 9.2.1 Finding Small Discriminants.- 9.2.2 Relative Quadratic Extensions.- 9.2.3 Relative Cubic Extensions.- 9.2.4 Finding the Smallest Discriminants Using Class Field Theory.- 9.3 Using the Geometry of Numbers.- 9.3.1 The General Procedure.- 9.3.2 General Inequalities.- 9.3.3 The Totally Real Case.- 9.3.4 The Use of Lagrange Multipliers.- 9.4 Construction of Tables of Quartic Fields.- 9.4.1 Easy Inequalities for All Signatures.- 9.4.2 Signature (0,2): The Totally Complex Case.- 9.4.3 Signature (2, 1): The Mixed Case.- 9.4.4 Signature (4, 0): The Totally Real Case.- 9.4.5 Imprimitive Degree 4 Fields.- 9.5 Miscellaneous Methods (in Brief).- 9.5.1 Euclidean Number Fields.- 9.5.2 Small Polynomial Discriminants.- 9.6 Exercises for Chapter 9.- 10. Appendix A: Theoretical Results.- 10.1 Ramification Groups and Applications.- 10.1.1 A Variant of Nakayama’s Lemma.- 10.1.2 The Decomposition and Inertia Groups.- 10.1.3 Higher Ramification Groups.- 10.1.4 Application to Different and Conductor Computations.- 10.1.5 Application to Dihedral Extensions of Prime Degree.- 10.2 Kummer Theory.- 10.2.1 Basic Lemmas.- 10.2.2 The Basic Theorem of Kummer Theory.- 10.2.3 Hecke’s Theorem.- 10.2.4 Algorithms for ?th Powers.- 10.3 Dirichlet Series with Functional Equation.- 10.3.1 Computing L-Functions Using Rapidly Convergent Series.- 10.3.2 Computation of Fi(s, x).- 10.4 Exercises for Chapter 10.- 11. Appendix B: Electronic Information.- 11.1 General Computer Algebra Systems.- 11.2 Semi-general Computer Algebra Systems.- 11.3 More Specialized Packages and Programs.- 11.4 Specific Packages for Curves.- 11.5 Databases and Servers.- 11.6 Mailing Lists, Websites, and Newsgroups.- 11.7 Packages Not Directly Related to Number Theory.- 12. Appendix C: Tables.- 12.1 Hilbert Class Fields of Quadratic Fields.- 12.1.1 Hilbert Class Fields of Real Quadratic Fields.- 12.1.2 Hilbert Class Fields of Imaginary Quadratic Fields.- 12.2 Small Discriminants.- 12.2.1 Lower Bounds for Root Discriminants.- 12.2.2 Totally Complex Number Fields of Smallest Discriminant.- Index of Notation.- Index of Algorithms.- General Index.