Siegel-Walfisz Theorem
For any , there exists such that for and : The constant is ineffective (not explicitly computable) due to the possible existence of Siegel zeros.
Proof Outline
Step 1: Reduce to L-functions. By character orthogonality: where .
Step 2: Explicit formula for each . For each character mod : where the sum is over nontrivial zeros of .
Step 3: Zero-free region. By the classical zero-free region: for , with at most one exceptional real zero (a Siegel zero) of a real character .
Step 4: Bounding the zero sum. For non-exceptional zeros, for . Summing over zeros (using the zero-counting formula ) and choosing : the contribution is for .
Step 5: Handling the Siegel zero. Siegel's theorem: for any , . For and small enough: . Choosing makes this .
The constant (hence ) is ineffective because Siegel's lower bound for is proved by contradiction: either there are few real zeros (and the bound is trivial) or a zero exists but forces for all other real characters via the Goldfeld-Gross-Zagier approach.
An effective (but weaker) version: for an explicit , valid uniformly for . This avoids Siegel's theorem but gives a weaker range for .
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 for up to . Siegel-Walfisz provides exactly this, which suffices for the "level of distribution" needed in basic sieve arguments.