Experimental Number Theory

by Fernando Villegas

Overview

This graduate text is intended for first or second year graduate students in pure mathematics. The main goal of the text is to show how the computer can be used as a tool for research in Number Theory through numerical experimentation. The book contains many examples of experiments in elementary class field theory, binary quadratic forms, sequences, combinatorics, p-adic numbers and polynomials, along with exercises and selected remarks and solutions. The numerous routines used in the examples are written in GP, the scripting language of the computational package PARI, and are available for download from the author's website.

Product Details

ISBN-13:	9780198528227
Publisher:	Oxford University Press, USA
Publication date:	06/29/2007
Series:	Oxford Graduate Texts in Mathematics Series
Pages:	300
Product dimensions:	9.10(w) x 6.10(h) x 0.70(d)

Table of Contents

1 Basic examples 1

1.1 How things vary with p 1

1.1.1 Quadratic Reciprocity Law 1

1.1.2 Sign functions 5

1.1.3 Checking modularity of sign functions 6

1.1.4 Examples 7

1.2 Recognizing numbers 10

1.2.1 Rational numbers in R 10

1.2.2 Rational numbers modulo m 14

1.2.3 Algebraic numbers 15

1.3 Bernoulli polynomials 19

1.3.1 Definition and properties 19

1.3.2 Calculation 20

1.3.3 Related questions 21

1.3.4 Proofs 23

1.4 Sums of squares 27

1.4.1 k = 1 28

1.4.2 k = 2 28

1.4.3 k > 3 29

1.4.4 The numbers <$$$>(n) 31

1.4.5 Theta functions 36

1.5 Exercises 36

2 Reciprocity 40

2.1 More variation with p 40

2.1.1 Local zeta functions 40

2.1.2 Formulation of reciprocity 41

2.1.3 Global zeta functions 43

2.2 The cubic case 44

2.2.1 Two examples 45

2.2.2 A modular case 46

2.2.3 A non-modular case 48

2.3 The Artin map 50

2.3.1 A Galois example 50

2.3.2 A non-Galois example 53

2.4 Quantitative version 55

2.4.1 Application of a theorem of Tchebotarev 55

2.4.2 Computing densities numerically 56

2.5 Galois groups 59

2.5.1 Tchebotarev's theorem 63

2.5.2 Trink's example 64

2.5.3 An example related to Trink's 65

2.6 Exercises 69

3 Positive definite binary quadratic forms 71

3.1 Basic facts 71

3.1.1 Reduction 72

3.1.2 Cornachia's algorithm 73

3.1.3 Class number 75

3.1.4 Composition 76

3.2 Examples of reciprocity for imaginary quadratic fields 77

3.2.1 Dihedral group of order 6 77

3.2.2 Theta functions again 79

3.2.3 Dihedral group of order 10 82

3.2.4 An example of F. Voloch 84

3.2.5 Final comments 90

3.3 Exercises 91

4 Sequences 92

4.1 Trinomial numbers 92

4.1.1 Formula 92

4.1.2 Differentialequation and linear recurrence 93

4.1.3 Algebraic equation 98

4.1.4 Hensel's lemma and Newton's method 99

4.1.5 Continued fractions 103

4.1.6 Asymptotics 107

4.1.7 More coefficients in the asymptotic expansion 109

4.1.8 Can we sum the asymptotic series? 111

4.2 Recognizing sequences 113

4.2.1 Values of a polynomial 113

4.2.2 Values of a rational function 114

4.2.3 Constant term recursion 115

4.2.4 A simple example 117

4.3 Exercises 119

5 Combinatorics 123

5.1 Description of the basic algorithm 123

5.2 Partitions 127

5.2.1 The number of partitions 128

5.2.2 Dual partition 130

5.3 Irreducible representations of <$$$> 131

5.3.1 Hook formula 132

5.3.2 The Murnaghan-Nakayama rule 133

5.3.3 Counting solutions to equations in <$$$> 138

5.3.4 Counting homomorphism and subgroups 139

5.4 Cyclotomic polynomials 143

5.4.1 Values of φ below a given bound 143

5.4.2 Computing cyclotomic polynomials 145

5.5 Exercises 148

6 p-adic numbers 151

6.1 Basic functions 151

6.1.1 Mahler's expansion 151

6.1.2 Hensel's lemma and Newton's method (again) 152

6.2 The p-adic gamma function 155

6.2.1 The multiplication formula 158

6.3 The logarithmic derivative of <$$$> 159

6.3.1 Application to harmonic sums 161

6.3.2 A formula of J. Diamond 163

6.3.3 Power series expansion of <$$$>(x) 164

6.3.4 Application to congruences 167

6.4 Analytic continuation 168

6.4.1 An example of Dwork 169

6.4.2 A generalization 170

6.4.3 Dwork's exponential 170

6.5 Gauss sums and the Gross-Koblitz formula 172

6.5.1 The case of <$$$> 172

6.5.2 An example 174

6.6 Exercises 175

7 Polynomials 177

7.1 Mahler's measure 177

7.1.1 Simple search 178

7.1.2 Refining the search 179

7.1.3 Counting roots on the unit circle 182

7.2 Applications of the Graeffe map 182

7.2.1 Detecting cyclotomic polynomials 182

7.2.2 Detecting cyclotomic factors 184

7.2.3 Wedge product polynomial 184

7.2.4 Interlacing roots of unity 185

7.3 Exercises 188

8 Remarks on selected exercises 189

References 205

Index 211