TheoremComplete

Siegel-Walfisz Theorem

Theorem6.1Siegel-Walfisz Theorem

For any A>0A > 0, there exists C(A)>0C(A) > 0 such that for gcd⁡(a,q)=1\gcd(a, q) = 1 and q≤(log⁡x)Aq \leq (\log x)^A: ψ(x;q,a)=xϕ(q)+O ⁣(xexp⁡ ⁣(−C(A)log⁡x))\psi(x; q, a) = \frac{x}{\phi(q)} + O\!\left(x \exp\!\left(-C(A)\sqrt{\log x}\right)\right) The constant C(A)C(A) is ineffective (not explicitly computable) due to the possible existence of Siegel zeros.


Proof Outline

Proof

Step 1: Reduce to L-functions. By character orthogonality: ψ(x;q,a)=1ϕ(q)∑χ mod qχ(a)‾ψ(x,χ)\psi(x; q, a) = \frac{1}{\phi(q)} \sum_{\chi \bmod q} \overline{\chi(a)} \psi(x, \chi) where ψ(x,χ)=∑n≤xχ(n)Λ(n)\psi(x, \chi) = \sum_{n \leq x} \chi(n)\Lambda(n).

Step 2: Explicit formula for each χ\chi. For each character χ\chi mod qq: ψ(x,χ)=δχ=χ0x−∑ρxρρ+O(log⁡2(qx))\psi(x, \chi) = \delta_{\chi = \chi_0} x - \sum_\rho \frac{x^\rho}{\rho} + O(\log^2(qx)) where the sum is over nontrivial zeros of L(s,χ)L(s, \chi).

Step 3: Zero-free region. By the classical zero-free region: L(s,χ)≠0L(s, \chi) \neq 0 for σ>1−c/log⁡(q(∣t∣+2))\sigma > 1 - c/\log(q(|t|+2)), with at most one exceptional real zero β1\beta_1 (a Siegel zero) of a real character χ1\chi_1.

Step 4: Bounding the zero sum. For non-exceptional zeros, ∣xρ∣=xβ≤x1−c/log⁡(qT)|x^\rho| = x^\beta \leq x^{1-c/\log(qT)} for ∣γ∣≤T|\gamma| \leq T. Summing over zeros (using the zero-counting formula N(T,χ)≪Tlog⁡(qT)N(T, \chi) \ll T\log(qT)) and choosing T=exp⁡(log⁡x)T = \exp(\sqrt{\log x}): the contribution is O(xexp⁡(−c′log⁡x))O(x\exp(-c'\sqrt{\log x})) for q≤(log⁡x)Aq \leq (\log x)^A.

Step 5: Handling the Siegel zero. Siegel's theorem: for any ε>0\varepsilon > 0, β1<1−c(ε)q−ε\beta_1 < 1 - c(\varepsilon)q^{-\varepsilon}. For q≤(log⁡x)Aq \leq (\log x)^A and ε\varepsilon small enough: xβ1≤x⋅x−c(ε)q−ε≤xexp⁡(−c(ε)(log⁡x)1−Aε)x^{\beta_1} \leq x \cdot x^{-c(\varepsilon)q^{-\varepsilon}} \leq x \exp(-c(\varepsilon)(\log x)^{1-A\varepsilon}). Choosing ε=1/(2A)\varepsilon = 1/(2A) makes this ≤xexp⁡(−c′′log⁡x)\leq x\exp(-c''\sqrt{\log x}).

The constant c(ε)c(\varepsilon) (hence C(A)C(A)) is ineffective because Siegel's lower bound for L(1,χ1)L(1, \chi_1) is proved by contradiction: either there are few real zeros (and the bound is trivial) or a zero exists but forces L(1,χ2)>0L(1, \chi_2) > 0 for all other real characters via the Goldfeld-Gross-Zagier approach. □\square

■

RemarkEffective Results

An effective (but weaker) version: ∣ψ(x;q,a)−x/ϕ(q)∣≪xexp⁡(−c(log⁡x)1/2/log⁡q)|\psi(x;q,a) - x/\phi(q)| \ll x\exp(-c(\log x)^{1/2}/\log q) for an explicit c>0c > 0, valid uniformly for q≤exp⁡(c′(log⁡x)1/2)q \leq \exp(c'(\log x)^{1/2}). This avoids Siegel's theorem but gives a weaker range for qq.

ExampleApplication to Twin Primes

The Siegel-Walfisz theorem is used in sieve methods for problems like twin primes: to apply the Selberg sieve, one needs equidistribution of primes in progressions mod dd for dd up to (log⁡x)A(\log x)^A. Siegel-Walfisz provides exactly this, which suffices for the "level of distribution" D=(log⁡x)AD = (\log x)^A needed in basic sieve arguments.