Analytic Number Theory: An Overview

A 'dead' piece of 19th-century mathematics turned out to be very much alive. The Riemann zeta function - an equation on paper from 1859 - governs the distribution of primes in the 21st century. Its zeros determine how accurately Li(x) approximates π(x), which directly informs cryptographic security estimates for RSA key sizes. Every HTTPS connection is an indirect descendant of Riemann's work.

• **RSA security estimates:** key size recommendations assume PNT; if Riemann's hypothesis were violated in a specific range, some estimates would need revision
• **Safe primes for DH:** Dirichlet's theorem guarantees infinitely many primes p = 2q+1; this underpins the existence of strong DH and DSA parameters at any bit length
• **Sieve factorization algorithms:** the quadratic sieve and GNFS rely on analytic density estimates for B-smooth numbers - a direct application of analytic number theory

Предварительные знания

• Algebraic Number Theory: An Overview

The Riemann Zeta Function and Euler's Product

Euler discovered in 1737 a formula connecting a sum over all positive integers to a product over all primes - an analytic encoding of the fundamental theorem of arithmetic. Riemann extended it to the complex plane in 1859 and found a deep connection between the zeros of ζ(s) and the distribution of primes.

**Riemann zeta function:** ζ(s) = Σₙ₌₁^∞ 1/nˢ = 1 + 1/2ˢ + 1/3ˢ + ... **Euler product formula:** ζ(s) = ∏_p (1 − p⁻ˢ)⁻¹ (product over all primes p) **Special values:** - ζ(2) = π²/6 ≈ 1.6449 (Basel problem, Euler 1734) - ζ(4) = π⁴/90 - ζ(−1) = −1/12 (analytic continuation) **Connection to PNT:** zeros of ζ(s) in the strip 0 < Re(s) < 1 control the error in π(x) ~ Li(x).

The Euler product ζ(s) = ∏(1−p⁻ˢ)⁻¹ is the analytic incarnation of unique factorization. Expanding each factor as a geometric series and multiplying gives exactly one term 1/nˢ for every positive integer n - because every n has a unique prime factorization.

Dirichlet Characters and L-Functions

Dirichlet proved in 1837 that every arithmetic progression a, a+d, a+2d, ... with gcd(a,d)=1 contains infinitely many primes. The proof uses L-functions - 'colored' versions of ζ(s) that track primes in individual residue classes.

**Dirichlet character χ mod q:** a completely multiplicative function χ: ℤ → ℂ with period q and χ(n)=0 when gcd(n,q)>1. **Dirichlet L-function:** L(s, χ) = Σ χ(n)/nˢ = ∏_p (1 − χ(p)·p⁻ˢ)⁻¹ **Dirichlet's theorem:** for gcd(a,q)=1, infinitely many primes satisfy p ≡ a (mod q). **Key step:** L(1, χ) ≠ 0 for any non-principal χ → all coprime residue classes receive their share of primes. **Application:** the prime number theorem for arithmetic progressions: primes are equidistributed among coprime residue classes.

Dirichlet's theorem guarantees that primes of special forms - safe primes p = 2q+1, primes p ≡ 3 (mod 4) needed for Tonelli-Shanks, Sophie Germain primes - are infinitely abundant. This is the mathematical foundation for cryptographic parameter selection in DH and DSA.

Chebyshev Functions and the Road to PNT

Chebyshev introduced the functions θ(x) and ψ(x) in 1850 as more analytically tractable alternatives to π(x). They paved the road to the rigorous proof of the prime number theorem in 1896.

**Chebyshev functions:** θ(x) = Σ_{p≤x} ln p (sum of logs of primes ≤ x) ψ(x) = Σ_{pᵏ≤x} ln p (includes prime powers) **Equivalences:** - ψ(x) = θ(x) + O(√x · ln x) - θ(x) ~ x ⟺ ψ(x) ~ x ⟺ π(x) ~ x/ln x (all equivalent to PNT) **Chebyshev proved (1850):** 0.92·x/ln x < π(x) < 1.11·x/ln x - before the full PNT. **Explicit formula (Riemann-von Mangoldt):** ψ(x) = x − Σ_ρ x^ρ/ρ − ln(2π) − ... where the sum runs over nontrivial zeros ρ of ζ(s).

The functions θ(x) and ψ(x) are easier to connect to ζ(s) than π(x) is. The key tool is the Mellin transform: ψ(x) is recovered from ζ(s) by a contour integral, making the zeros of ζ(s) directly visible as oscillation frequencies in ψ(x).

Key Ideas

• **Euler product:** ζ(s) = ∏(1−p⁻ˢ)⁻¹ encodes the fundamental theorem of arithmetic analytically; zeros govern π(x)
• **Dirichlet L-functions:** generalize ζ(s) to residue classes; L(1,χ)≠0 proves infinitely many primes in each coprime class
• **Chebyshev θ(x), ψ(x):** analytically equivalent to PNT; ψ(x) is linked directly to ζ(s) zeros via the explicit formula
• **Explicit formula:** ψ(x) = x − Σ_ρ x^ρ/ρ − ...; zeros ρ are the 'frequencies' of oscillation of π(x) around Li(x)

Related Topics

Analytic number theory is the capstone of the mathematical structure in this course:

• Distribution of Primes — PNT is the central theorem; ζ(s) and L-functions are its instruments
• Algebraic Number Theory — Dedekind zeta functions generalize ζ(s) to number fields and encode their prime ideal distribution
• Number Theory in Cryptography — RSA key size analysis, DH parameter selection, and factorization attack bounds all use analytic results

Вопросы для размышления

• The Euler product ζ(s) = ∏(1−p⁻ˢ)⁻¹ converges for Re(s) > 1. What happens as s → 1⁺? How does this connect to the infinitude of primes?
• The explicit formula ψ(x) = x − Σ_ρ x^ρ/ρ − ... contains a sum over zeros of ζ. Why does the Riemann hypothesis (zeros on Re=1/2) give the best possible error bound for π(x)?
• Dirichlet L-functions track primes in specific residue classes. How does this relate to choosing safe primes p = 2q+1 for Diffie-Hellman, where both p and q must be prime?

Связанные уроки

• calc-03-limits-intro