---
tag: XEPW251A97
kind: statement
role: theorem
name: Siegel–Walfisz theorem
msc: [11N13, 11M20]
uses: [B8AKSVBE5Z, 0NK8JTE1NN, 0DAMHCT17R, 0TGV80E6A4, 0EHBY5Y84N, 9D2Z543EJQ, DNKA4WBKDS]
about: [0GNVN3CA2P, 5VBZBXSFDQ]
sources:
  - url: https://en.wikipedia.org/wiki/Siegel–Walfisz_theorem
same_as:
  wikidata: Q7510574
  wikipedia: Siegel–Walfisz theorem
---

## Statement

Let $q \ge 1$ and $a$ be integers, and let $x \ge 2$ be real.
Let
$$\psi(x; q, a) = \sum_{\substack{n \le x \\ n \equiv a \pmod q}} \Lambda(n),$$
where $\Lambda$ is the [[von Mangoldt function|0NK8JTE1NN]], and let $\varphi$ be [[Euler's totient function|0DAMHCT17R]].
For every real number $N > 0$ there is a constant $C_N > 0$ such that
$$\psi(x; q, a) = \frac{x}{\varphi(q)} + O\!\left(x\, e^{-C_N \sqrt{\log x}}\right)$$
for all $x \ge 2$, all $q \le (\log x)^N$ and all $a$ coprime to $q$.
The constant $C_N$ and the implied constant in the [[big O|0TGV80E6A4]] depend only on $N$.

## Remarks

The proof follows the proof of the [[prime number theorem|0EHBY5Y84N]] for each [[Dirichlet L-function|9D2Z543EJQ]] $L(s, \chi)$ with $\chi$ modulo $q$.
The classical zero-free region handles all zeros except a possible [[Siegel zero|5VBZBXSFDQ]].
Siegel's theorem says that for every $\varepsilon > 0$ such a real zero $\beta$ satisfies $\beta < 1 - c(\varepsilon) q^{-\varepsilon}$, and for $q \le (\log x)^N$ this is enough to make its contribution small.
Siegel's theorem is ineffective, so $C_N$ cannot be computed from the proof.
For example, with $N = 2$ and $q = 4$, the theorem gives $\psi(x; 4, 1) = x/2 + O(x e^{-c\sqrt{\log x}})$, a strong form of [[Dirichlet's theorem on primes in arithmetic progressions|0GNVN3CA2P]] for primes $p \equiv 1 \pmod 4$.
The range $q \le (\log x)^N$ is very short; for larger $q$ one has only average results such as the [[Bombieri–Vinogradov theorem|B3JMY54GJF]].

## Explanations

### L1 human

Primes are spread evenly over the residue classes modulo $q$ that they can reach.
This theorem gives a precise error bound for that fact, valid as long as the modulus $q$ is small compared to $x$, at most a power of $\log x$.
It is the prime number theorem for arithmetic progressions, uniform in small moduli.

### L2 human

The Siegel–Walfisz theorem is the standard input for the "small moduli" part of many arguments in analytic number theory.
In proofs of the [[Bombieri–Vinogradov theorem|B3JMY54GJF]] and in the circle method for [[Vinogradov's theorem|C01Z9QRGZY]], the major arcs with small denominators are handled by it.
Its constants are ineffective because of the possible [[Siegel zero|5VBZBXSFDQ]]; this is why results that rely on it, such as Vinogradov's theorem in its first form, give no explicit bound.
Under the [[generalized Riemann hypothesis|DNKA4WBKDS]], the error improves to $O(x^{1/2} (\log x)^2)$ for all $q \le x$.