Numerical Algorithms for Number Theory: Using Pari/GP (Mathematical Surveys and Monographs, 254)

✍ Scribed by Karim Belabas, Henri Cohen

• Publisher: American Mathematical Society
• Year: 2021
• Tongue: English
• Leaves: 442
• Category: Library

✦ Table of Contents

Preface
Chapter 1. Introduction
1.1. Subject matter
1.2. Experimental protocols
1.3. Multiprecision algorithms and working accuracy
1.4. Comments on the GP language
1.4.1. Functions and closures
1.4.2. Variable scope
1.4.3. Inexact objects, precision issues
1.4.4. Infinity
1.4.5. Parallelism
1.5. Warnings
1.5.1. Mathematical rigor
1.5.2. Endpoints of basic methods
1.6. Examples
Chapter 2. Numerical extrapolation
2.1. Introduction
2.1.1. Generalities on basic numerical methods
2.1.2. Extrapolation goals
2.1.3. Behavior of 𝑢(𝑛)
2.2. Richardson extrapolation
2.2.1. The basic method
2.2.2. Variant: 𝑢(𝑛) is essentially a sum
2.2.3. Other variants
2.3. Interlude: Estimating the number 𝑁 of nodes
2.3.1. Introduction
2.3.2. Easy cases: The Lambert 𝑊 function
2.3.3. Harder cases: Dependence on the 𝑛th derivative
2.3.4. Use of a multiplier and/or a translation
2.4. Extrapolating by interpolation: Lagrange
2.4.1. The basic method
2.4.2. Variant 1: Behavior in 1/𝑛^{𝛼𝑚}
2.4.3. Variant 2: Behavior in 𝑓(𝑛)/𝑛^{𝛼𝑚}
2.4.4. Variant 3: Recursions and sums
2.4.5. Zagier’s interpretation
2.5. Extrapolation using Sidi’s mW algorithm
2.6. Computing asymptotic expansions
2.6.1. The rational case
2.6.2. The general case
2.6.3. Example: Zeros of 𝐽 and 𝑌-Bessel functions
2.7. Sample timings for Limit programs
2.8. Conclusion
Chapter 3. Numerical integration
3.1. Numerical differentiation
3.2. Integration of rational functions
3.3. Generalities on numerical integration
3.3.1. Introduction
3.3.2. Dealing with singularities
3.3.3. Dealing with poles and large intervals
3.4. Newton–Cotes type methods
3.4.1. Trapezes, Simpson, etc
3.4.2. Chebyshev nodes
3.4.3. Romberg integration
3.5. Orthogonal polynomials
3.5.1. Definition and basic properties
3.5.2. Using moments to compute 𝑃_{𝑛}(𝑋)
3.5.3. The Christoffel–Darboux formula
3.5.4. Using moment matrices
3.5.5. Further properties of orthogonal polynomials
3.5.6. Computing orthogonal polynomials: Cholesky
3.5.7. Computing orthogonal polynomials: Continued fractions
3.5.8. Computing the roots of 𝑃_{𝑛}
3.6. Gaussian integration methods
3.6.1. General Gaussian integration
3.6.2. Gaussian integration: Gauss–Legendre
3.6.3. Gaussian integration: Gauss–Chebyshev
3.6.4. Gaussian integration: Gauss–Laguerre
3.6.5. Gaussian integration: Gauss–Hermite
3.6.6. General Gaussian integration
3.6.7. General Gaussian integration: Examples
3.7. Gaussian Integration on [𝑎,∞]
3.7.1. Using Gauss–Legendre
3.7.2. Gaussian integration with polynomials in 1/𝑥
3.8. Doubly-exponential integration methods (DE)
3.8.1. Introduction
3.8.2. Cursory analysis of the DE
3.8.3. DE over compact intervals [𝑎,𝑏]
3.8.4. DE over ]-∞,∞[
3.8.5. DE over [𝑎,∞[ or ]-∞,𝑎]
3.8.6. Contour integration and double integrals
3.9. Integration of oscillatory functions
3.9.1. The DE for periodic functions
3.9.2. Integration of oscillatory functions: Sums
3.9.3. Integration of oscillatory functions: Extrapolation
3.9.4. Summary of the possible programs
3.10. Sample timings for integrals on [𝑎,𝑏]
3.10.1. Conclusion for integration on a compact interval
3.11. Sample timings for integrals on [0,∞]
3.11.1. Functions tending to 0 slowly
3.11.2. Conclusion for integrals tending to 0 slowly at ∞
3.11.3. Functions tending to 0 like 𝑒^{-𝑥}
3.11.4. Conclusion for integrals tending to 0 as 𝑒^{-𝑥}
3.12. Sample timings for oscillatory integrals
3.13. Final conclusion on numerical integration
Chapter 4. Numerical summation
4.1. Introduction
4.1.1. Aim of this chapter
4.1.2. Important remarks
4.2. Euler–Maclaurin summation methods
4.2.1. Bernoulli polynomials and Bernoulli numbers
4.2.2. The basic Euler–Maclaurin formula
4.2.3. The constant 𝑧(𝑓;𝑎)
4.2.4. The Abel–Plana formulas
4.2.5. Variant: 𝜒-Euler–Maclaurin
4.2.6. Variant: Δ-Euler–Maclaurin
4.2.7. Euler–Maclaurin and 𝜁(𝑠)
4.2.8. Definite integrals coming from Euler–Maclaurin
4.2.9. Definite integrals involving fractional parts
4.2.10. Other applications of Euler–Maclaurin
4.3. Pinelis summation
4.4. Sums and products of rational functions
4.5. Summation of oscillating series
4.5.1. Summation of alternating series: The CVZ method
4.5.2. Variant for Fourier series
4.5.3. Variant for periodic functions
4.5.4. Non-periodic oscillating series
4.6. Summing by extrapolation
4.7. Van Wijngaarden’s method
4.8. Monien summation
4.8.1. A naïve approach
4.8.2. The basic method
4.8.3. Generalized Monien summation
4.8.4. Monien summation with other weights
4.8.5. Monien summation for alternating series
4.9. Summing functions defined only on integers
4.10. Multiple sums and multizeta values
4.10.1. Double sums
4.10.2. Multizeta values
4.11. Sample timings for summation programs
4.12. Sample timings for Sumalt programs
Chapter 5. Euler products and Euler sums
5.1. Euler sums
5.2. Euler products
5.3. Variants involving log(𝑝) or log(log(𝑝))
5.4. Variants involving quadratic characters
5.5. Variants involving congruences
5.6. Hardy–Littlewood constants: Quadratic polynomials
5.7. Hardy–Littlewood constants: General polynomials
5.7.1. Cubic polynomials
5.7.2. 𝐶_{ℓ} polynomials
5.7.3. General polynomials
Chapter 6. Gauss and Jacobi sums
6.1. Gauss and Jacobi sums over 𝔽_{𝕢}
6.1.1. Basic definitions: Finite fields and Gauss sums
6.1.2. Finite fields and Jacobi sums
6.1.3. Applications of 𝐽(𝜒,𝜒)
6.1.4. The Hasse–Davenport relations
6.2. Practical computations of Gauss and Jacobi sums
6.2.1. Introduction and motivation
6.2.2. Elementary methods
6.2.3. Implementations
6.2.4. Using theta functions
6.3. Using the Gross–Koblitz formula
6.3.1. Introduction
6.3.2. Preliminaries to the Gross–Koblitz formula
6.3.3. The Gross–Koblitz formula: Statement and applications
6.4. Gauss and Jacobi sums over ℤ/ℕℤ
6.4.1. Definitions
6.4.2. Reduction to prime Gauss sums: Odoni’s theorem
6.4.3. Other complete exponential sums
Chapter 7. Numerical computation of continued fractions
7.1. Generalities
7.2. Naïve numerical computation
7.3. Speed of convergence of infinite continued fractions
7.4. Examples of each convergence case
7.5. Convergence acceleration of continued fractions
7.6. The quotient-difference algorithm
7.7. Evaluation of the quotient-difference output
Chapter 8. Computation of inverse Mellin transforms
8.1. Introduction
8.2. Gamma products
8.2.1. The Gamma function
8.2.2. Elementary cases and reductions
8.2.3. The asymptotic formula
8.3. Compendium of possible methods
8.4. Using the power series around 𝑥=0
8.5. Using the asymptotic expansion
8.5.1. Computing the coefficients 𝑀_{𝑛}
8.5.2. Using the quotient-difference algorithm
8.5.3. The main heuristic assumption
8.5.4. Putting everything together
8.6. Generalized incomplete Gamma functions
Chapter 9. Computation of 𝐿-functions
9.1. The basic setting and goals
9.2. The associated Theta function
9.2.1. Definition and basic properties
9.2.2. Computer representation of 𝐿-functions
9.2.3. Computing the Theta function
9.2.4. Computing the root number 𝑤 and the residue 𝑅
9.2.5. Computing the conductor 𝑁
9.3. Computing Λ(𝑠) and 𝐿(𝑠)
9.3.1. The “approximate” functional equation
9.3.2. The smoothed approximate functional equation
9.4. Booker–Molin’s idea for computing Λ(𝑠): Poisson summation
9.5. The Fourier error
9.6. The truncation errors
9.7. Implementation
9.7.1. Improvement of the precomputation speed
9.7.2. Improvement of the speed of computation of 𝑤 and 𝑅
9.7.3. Improvement of the evaluation speed
9.8. A possible program for computing Λ(𝑠) and 𝐿(𝑠)
9.9. Applications
9.9.1. Direct applications
9.9.2. Important classical 𝐿-functions
9.10. Examples
9.10.1. Computing the conductor
9.10.2. Computation of 𝐿-functions
9.10.3. Computing unknown Euler factors
9.10.4. Additional fun
9.11. Shifting the line of integration in the Booker–Molin method
9.12. Computing 𝐿(𝑠) for large ℑ(𝑠)
9.12.1. Computing 𝜁(𝑠) by Euler–Maclaurin
9.12.2. Computing ∑_{1≤𝑛≤𝑁}𝑛^{-𝑠}
9.12.3. The Riemann–Siegel formula
9.12.4. The Zetafast algorithm
9.12.5. Two fun applications
9.12.6. Sample timings for 𝜁(1/2+𝑖𝑇)
9.13. Explicit formulas
9.13.1. The basic theorem
9.13.2. Application I: Sums over nontrivial zeros
9.13.3. Application II: 𝑏=0 for true 𝐿-functions
9.13.4. Application III: Discriminant bounds
Appendix A. List of relevant GP programs
Bibliography
Index of Programs
General Index