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(logx)Aq \leq (\log x)^A: ψ(x;q,a)=xϕ(q)+O ⁣(xexp ⁣(C(A)logx))\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)χmodqχ(a)ψ(x,χ)\psi(x; q, a) = \frac{1}{\phi(q)} \sum_{\chi \bmod q} \overline{\chi(a)} \psi(x, \chi) where ψ(x,χ)=nxχ(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(log2(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 σ>1c/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βx1c/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(logx)T = \exp(\sqrt{\log x}): the contribution is O(xexp(clogx))O(x\exp(-c'\sqrt{\log x})) for q(logx)Aq \leq (\log x)^A.

Step 5: Handling the Siegel zero. Siegel's theorem: for any ε>0\varepsilon > 0, β1<1c(ε)qε\beta_1 < 1 - c(\varepsilon)q^{-\varepsilon}. For q(logx)Aq \leq (\log x)^A and ε\varepsilon small enough: xβ1xxc(ε)qεxexp(c(ε)(logx)1Aε)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(clogx)\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(logx)1/2/logq)|\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 qexp(c(logx)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 (logx)A(\log x)^A. Siegel-Walfisz provides exactly this, which suffices for the "level of distribution" D=(logx)AD = (\log x)^A needed in basic sieve arguments.