Fact-checked by Grok 2 weeks ago

Dirichlet's theorem on arithmetic progressions

Dirichlet's theorem on arithmetic progressions states that for any two positive coprime integers a and d, there are infinitely many prime numbers of the form a + nd where n is a non-negative integer.^[1] This result generalizes Euclid's ancient theorem on the infinitude of primes, which corresponds to the special case a = 1 and d = 1.^[2] Proved by Peter Gustav Lejeune Dirichlet in 1837, the theorem marked a pivotal advancement in analytic number theory, introducing key tools such as Dirichlet characters and L-functions to analyze the distribution of primes.^[2] Dirichlet's proof relies on constructing Dirichlet L-functions L(s, \chi) = \sum_{n=1}^\infty \chi(n) n^{-s}, where \chi is a character modulo d, and demonstrating that the non-principal L-functions do not vanish at s=1, ensuring the logarithmic divergence necessary for infinitely many primes in the progression.^[1] These techniques, blending complex analysis and group theory, predated later developments like the Riemann zeta function's analytic continuation.^[2] The theorem's importance lies in its revelation of the equidistribution of primes among the \phi(d) residue classes coprime to d, where \phi is Euler's totient function, with each class containing asymptotically equal proportions of primes (density $1/\phi(d)).^[2] It forms a cornerstone of modern number theory, influencing studies on prime gaps, sieve methods, and generalizations to number fields via Artin L-functions, while inspiring ongoing research into effective bounds and exceptions under the generalized Riemann hypothesis.^[3]

Statement of the Theorem

Formal Statement

Dirichlet's theorem on arithmetic progressions states that if a and d are positive integers with \gcd(a,d)=1, then the arithmetic progression a, a+d, a+2d, \dots contains infinitely many prime numbers.^[2] Equivalently, there are infinitely many prime numbers p such that p \equiv a \pmod{d}.^[2] In set-theoretic notation, the intersection of the set of natural numbers congruent to a modulo d, \{n \in \mathbb{N} \mid n \equiv a \pmod{d}\}, with the set of prime numbers is infinite.^[2] The theorem asserts the existence of infinitely many such primes but does not provide an explicit construction for generating them or effective bounds on the size of the smallest prime in the progression.^[2]

Key Conditions and Implications

The coprimality condition in Dirichlet's theorem requires that \gcd(a, d) = 1, where a and d are positive integers defining the arithmetic progression a + nd for n = 0, 1, 2, \dots. This ensures that the residue class a \pmod{d} is coprime to the modulus d, meaning no prime dividing d divides a. Without this condition, all terms share a common divisor greater than 1, leading to only finitely many primes (as detailed below). The theorem's proof relies on the equidistribution properties within the multiplicative group of units modulo d, which only applies to coprime residues.^[2] A key implication of the theorem is that each of the \phi(d) residue classes modulo d coprime to d contains infinitely many primes, where \phi denotes Euler's totient function, which counts the number of integers from 1 to d that are coprime to d. This prevents any such coprime progression from being "depleted" of primes. Further details on asymptotic densities and equidistribution are discussed in later sections.^[2] If \gcd(a, d) > 1, the condition fails, and the progression contains at most finitely many primes (often none beyond a possible initial term). In this case, every term shares the common divisor g = \gcd(a, d) > 1, so for sufficiently large n, the terms exceed g and are composite. For instance, when a is even and d is even, all terms are even and greater than 2, hence composite.^[4]

Illustrative Examples

Basic Examples

A fundamental illustration of Dirichlet's theorem arises in the arithmetic progression consisting of numbers congruent to 1 modulo 4, where the first term a = 1 and common difference d = 4, satisfying \gcd(1, 4) = 1. The theorem asserts that there are infinitely many primes in this sequence, including 5, 13, 17, 29, 37, and 41.^[2] Another straightforward case is the progression of numbers congruent to 3 modulo 10, with a = [3](/page/3) and d = 10, where \gcd([3](/page/3), 10) = 1. Dirichlet's theorem guarantees infinitely many primes here, such as 3, 13, 23, 43, 53, and 73.^[1] To highlight the role of the coprimality condition, consider the progression with a = 2 and d = 4, where \gcd(2, 4) = 2 > 1. This generates the sequence 2, 6, 10, 14, 18, ..., which contains only one prime, namely 2, since all later terms are even and greater than 2, rendering them composite.^[5] These instances underscore the theorem's prediction: infinite primes populate arithmetic progressions when the initial term and difference are coprime, but only finitely many (often just one) appear otherwise, emphasizing the condition's necessity for the result to hold.^[1]

Advanced Illustrations

One notable application of Dirichlet's theorem arises in the arithmetic progression of primes congruent to 1 modulo 6, where a = 1 and d = 6. Since \gcd(1, 6) = 1, the theorem guarantees infinitely many such primes, including examples like 7, 13, 19, 31, 37, and 43.^[6] These primes are connected to quadratic residues: specifically, -3 is a quadratic residue modulo an odd prime p if and only if p \equiv 1 \pmod{6}, which relates to the splitting behavior of such primes in the ring of Eisenstein integers \mathbb{Z}[\omega], where \omega is a primitive cube root of unity.^[7]^[8] The theorem also underpins the study of finite arithmetic progressions consisting entirely of primes, illustrating the density of primes within broader progressions. For instance, the longest known such progression contains 27 primes, discovered in 2023 by Michael Kwok and the PrimeGrid project, of the form (2712706938 + 155368778 \cdot n) \cdot 23\# + 50516201 for n = 0 to 26, where $23\# denotes the primorial of 23.^[9] While these finite sequences are remarkable, Dirichlet's theorem emphasizes the infinitude of primes in the underlying progression, as long as the initial term and difference are coprime, providing a foundational assurance beyond any finite example.^[6] Sophie Germain primes offer another illustration, defined as primes p such that $2p + 1 is also prime. The infinitude of such primes remains conjectural, but Dirichlet's theorem applies directly to suitable arithmetic progressions for p; for example, by the Chinese remainder theorem, one can construct a modulus m such that primes p \equiv b \pmod{m} (with \gcd(b, m) = 1) ensure $2p + 1 avoids divisibility by small primes like 3, 5, or 7, yielding infinitely many prime candidates p where $2p + 1 has a chance to be prime.^[10]^[6] A related unique implication of the theorem is the existence of infinitely many primes in progressions designed to avoid small moduli, creating candidates for twin primes—pairs (p, p+2) both prime—without proving their infinitude. For instance, there are infinitely many primes p \equiv 5 \pmod{6}, ensuring neither p nor p+2 is divisible by 3, thus generating endless potential twin prime pairs subject to further checks for primality.^[6]

Foundational Concepts

Arithmetic Progressions

An arithmetic progression in the integers is a sequence of the form a, a + d, a + 2d, \dots , where a and d are fixed positive integers, with a denoting the first term and d > 0 the common difference between consecutive terms.^[11] This sequence can be extended indefinitely in the positive direction and, if desired, bidirectionally as \dots, a - d, a, a + d, \dots.^[11] The general term of such a progression, indexed starting from n = 1, is given by

a_n = a + (n-1)d

for each positive integer n.^[12] This formula allows direct computation of any term without listing predecessors, facilitating analysis in number-theoretic contexts. A key property of an arithmetic progression with common difference d is its asymptotic density within the positive integers, which equals $1/d. Specifically, the number of terms not exceeding x is \lfloor (x - a)/d \rfloor + 1 \sim x/d as x \to \infty.^[13] Thus, the progression occupies a positive proportion $1/d of all integers up to x. Another important property concerns divisibility: if g = \gcd(a, d) > 1, then g divides every term in the progression, since a_n = a + (n-1)d is a linear combination of a and d with integer coefficients.^[13] In such cases, the terms share a common divisor greater than 1, which restricts their primality; sieving methods can identify potential primes, but only finitely many may occur beyond the initial terms. In the context of prime numbers, arithmetic progressions with \gcd(a, d) = 1 play a central role, as Dirichlet's theorem guarantees infinitely many primes under this coprimality condition, contrasting with the finite primality in non-coprime cases.^[13]

Dirichlet Characters and Moduli

A Dirichlet character modulo d is a complex-valued function \chi: \mathbb{Z} \to \mathbb{C} that is completely multiplicative, meaning \chi(mn) = \chi(m)\chi(n) for all integers m, n, and periodic with period d, so \chi(n + d) = \chi(n) for all n \in \mathbb{Z}. Additionally, \chi(n) = 0 whenever \gcd(n, d) > 1, ensuring the function vanishes on integers not coprime to the modulus. When \gcd(n, d) = 1, \chi(n) is nonzero and determined by the residue class n \mod d, specifically \chi(n) = \chi(n \mod d). These characters arise as homomorphisms from the multiplicative group (\mathbb{Z}/d\mathbb{Z})^* to the nonzero complex numbers \mathbb{C}^*, extended to all integers by the zero condition.^[14]^[15] The modulus d serves as the period of the character, but for primitive Dirichlet characters, d is precisely the conductor, defined as the smallest positive integer q such that \chi is periodic with period q. Non-primitive characters modulo d have conductors that properly divide d. The Euler totient function \phi(d) counts the number of integers from 1 to d coprime to d, which equals the order of the group (\mathbb{Z}/d\mathbb{Z})^* and thus the total number of Dirichlet characters modulo d. These \phi(d) characters take nonzero values exactly on the \phi(d) residue classes modulo d that are coprime to d.^[14]^[15] The principal Dirichlet character \chi_0 modulo d is defined by \chi_0(n) = 1 if \gcd(n, d) = 1 and \chi_0(n) = 0 otherwise; it corresponds to the trivial homomorphism on (\mathbb{Z}/d\mathbb{Z})^*. All remaining \phi(d) - 1 characters modulo d are non-principal (or non-trivial), exhibiting more varied behavior, such as taking values on the unit circle in \mathbb{C}. For example, modulo 4, the non-principal character is given by \chi(n) = 1 if n \equiv 1 \pmod{4}, \chi(n) = -1 if n \equiv 3 \pmod{4}, and \chi(n) = 0 if $2 \mid n.^[14]^[15] A fundamental property is the orthogonality relation for characters modulo d: for integers a, b with \gcd(a, d) = \gcd(b, d) = 1,

\sum_{\chi \pmod{d}} \overline{\chi}(a) \chi(b) = \begin{cases} \phi(d) & \text{if } b \equiv a \pmod{d}, \\ 0 & \text{otherwise}. \end{cases}

Additionally, \sum_{\chi \pmod{d}} \chi(a) = \phi(d) if \gcd(a, d) = 1 and a \equiv 1 \pmod{d}, while the sum is 0 otherwise (including when \gcd(a, d) > 1, since each \chi(a) = 0). These relations stem from the characters forming an orthogonal basis for the space of functions on the residue classes coprime to d.^[14]^[15] Dirichlet characters play a key role in analyzing arithmetic progressions by decomposing the indicator function of a residue class a \pmod{d} (with \gcd(a, d) = 1):

\mathbf{1}_{n \equiv a \pmod{d}}(n) = \frac{1}{\phi(d)} \sum_{\chi \pmod{d}} \overline{\chi}(a) \chi(n).

This inversion formula allows sums over primes in the progression n \equiv a \pmod{d} to be expressed as combinations of character sums, facilitating the application of analytic methods to Dirichlet's theorem.^[14]^[15]

Historical Development

Pre-Dirichlet Contributions

The study of primes in arithmetic progressions traces its origins to ancient efforts to understand the infinite nature of primes. Euclid, in Book IX, Proposition 20 of his Elements (c. 300 BCE), provided the first rigorous proof of the infinitude of prime numbers by assuming a finite set of primes and constructing a number larger than their product that is 1 more than a multiple of that product, which must have a prime factor not in the set, leading to a contradiction. This result confirms infinitely many primes in the trivial arithmetic progression of all natural numbers with common difference 1 but offers no insight into their distribution across other progressions.^[16] In the 18th century, Leonhard Euler advanced the understanding of prime infinitude through analytic means. In his 1737 paper "Variae observationes circa series infinitas," Euler showed that the harmonic series over primes diverges, ∑_{p prime} 1/p = ∞, by comparing it to the logarithm of the Euler product for the Riemann zeta function ζ(s) = ∏_p (1 - p^{-s})^{-1} for Re(s) > 1, implying infinitely many primes since a finite sum would converge. Euler's 1734 solution to the Basel problem, establishing ζ(2) = π²/6 via the infinite product for sin(πx), involved partial fraction expansions that effectively summed over residue classes modulo 4, foreshadowing the role of periodic functions in analyzing primes by residues, akin to early forms of character sums. Adrien-Marie Legendre contributed partial asymptotic estimates for prime counts that motivated further inquiry into progressions. In his 1798 Essai sur la théorie des nombres, Legendre approximated the number of primes up to x as ∫_2^x dt / ln t - (x / ln x) / 2 + ..., providing better error terms than earlier bounds and influencing estimates for primes in short intervals, such as between n² and (n+1)². In attempting a proof of quadratic reciprocity, Legendre assumed the existence of infinitely many primes in specific arithmetic progressions congruent to certain residues modulo the discriminant, a conjecture that highlighted the need for distribution results but remained unproven, later identified as a key gap by Gauss.^[17] Carl Friedrich Gauss, as a young student, formulated bold conjectures on prime distribution around 1792–1793 based on extensive numerical computations. He proposed that the primes up to x are asymptotically li(x) ≈ x / ln x in total, and moreover, that they are equidistributed among the φ(d) residue classes coprime to a fixed modulus d, each with asymptotic density 1/φ(d) relative to the total prime count. These ideas, including the equidistribution in progressions, were recorded in Gauss's private diary and letters but remained unpublished during his lifetime, surfacing publicly only in 1863 through references in editions of Dirichlet's lectures. Gauss's conjectures provided the precise motivational framework for Dirichlet's theorem, emphasizing uniform distribution across coprime classes without delving into proofs.^[18]^[19]

Dirichlet's Original Proof

In 1837, Peter Gustav Lejeune Dirichlet published his proof of the theorem asserting infinitely many primes in arithmetic progressions where the first term and common difference are coprime, in the paper "Recherches sur diverses applications de l'analyse infinitésimale à la théorie des nombres," which appeared in volumes 19 and subsequent issues of Crelle's Journal für die reine und angewandte Mathematik.^[20] This work represented a pivotal advancement, as Dirichlet was the first to successfully apply tools from mathematical analysis to establish a deep result in arithmetic, extending earlier conjectures such as those by Carl Friedrich Gauss on the distribution of primes in progressions.^[21]^[6] The core innovation of Dirichlet's proof lay in the introduction of Dirichlet L-series, defined using Dirichlet characters—homomorphisms from the multiplicative group of integers modulo the common difference d to the unit circle in the complex plane—which generalized the Riemann zeta function \zeta(s) to L(s, \chi) = \sum_{n=1}^\infty \chi(n) n^{-s}.^[22] These characters enabled a Fourier analytic decomposition of arithmetic functions modulo d, leveraging the orthogonality of characters to isolate sums over specific residue classes. Dirichlet built on principles of Fourier analysis for finite abelian groups and a summation technique akin to the Poisson summation formula to evaluate the behavior of these series near s=1.^[23]^[24] Central to the proof was Dirichlet's demonstration that L(1, \chi) \neq 0 for all non-principal characters \chi modulo d, ensuring the L-series for the principal character (analogous to \zeta(s)) captures the full divergent behavior at s=1, while the contributions from other characters remain finite.^[21] Using the Euler product representation and logarithmic derivatives, he then showed that the sum \sum_{p \equiv a \pmod{d}} \frac{\log p}{p} diverges, mirroring Euler's argument for the infinitude of primes but adapted via character orthogonality to the arithmetic progression p \equiv a \pmod{d}.^[2] This divergence implies infinitely many such primes, as the terms are positive and decrease sufficiently slowly. Despite its elegance, Dirichlet's proof offered no explicit error bounds on the prime distribution or estimates for the smallest such prime, rendering it non-effective for computational purposes and highlighting the challenges of bridging analysis and arithmetic without modern refinements.^[25] The approach required careful handling of character sums and convergence, but succeeded in proving positive logarithmic density for primes in the progression.^[21]

Proof Techniques

Analytic Number Theory Foundations

The Riemann zeta function, a cornerstone of analytic number theory, is initially defined for complex numbers s with \operatorname{Re}(s) > 1 by the Dirichlet series

\zeta(s) = \sum_{n=1}^\infty \frac{1}{n^s}.

This series converges absolutely in the specified half-plane, reflecting the harmonic nature of the sum over reciprocals of integers raised to the power s.^[26] The function admits a meromorphic continuation to the entire complex plane, holomorphic everywhere except for a simple pole at s=1 with residue 1, which corresponds to the divergent harmonic series in the limit.^[26] This analytic continuation, established through the functional equation involving the gamma function, enables the study of \zeta(s) in regions where the original series diverges, such as the critical strip $0 < \operatorname{Re}(s) < 1.^[26] Dirichlet series generalize the zeta function, taking the form

F(s) = \sum_{n=1}^\infty \frac{a_n}{n^s},

where a_n is a sequence of complex coefficients, often arising from arithmetic functions. Convergence occurs in a right half-plane \operatorname{Re}(s) > \sigma_c, with \sigma_c denoting the abscissa of convergence, beyond which the series behaves like a power series in $1/n.^[27] For multiplicative arithmetic functions—those satisfying a_{mn} = a_m a_n when \gcd(m,n)=1—such series admit Euler products over primes:

F(s) = \prod_p \left( \sum_{k=0}^\infty \frac{a_{p^k}}{p^{ks}} \right),

provided the local factors converge, mirroring the Euler product for \zeta(s) = \prod_p (1 - p^{-s})^{-1}.^[27] This product structure encodes multiplicative properties, facilitating analysis of number-theoretic sums via prime factorization. A key tool for extracting partial sums from Dirichlet series is Perron's formula, which links the sum \sum_{n \leq x} a_n to a contour integral of F(s). For F(s) analytic in \operatorname{Re}(s) > \sigma_c and c > \sigma_c, the formula states

\sum_{n \leq x} a_n = \frac{1}{2\pi i} \int_{c - iT}^{c + iT} F(s) \frac{x^s}{s} \, ds + O\left( \sum_{n \leq x + 1} |a_n| \cdot \frac{x}{T} + \frac{x^{c+1}}{T} \max_{c - iT \leq \operatorname{Im}(s) \leq c + iT} |F(s)| \right),

with the error term vanishing as T \to \infty.^[28] In the idealized case without error bounds, it approximates as

\sum_{n \leq x} a_n \approx \frac{1}{2\pi i} \oint F(s) \frac{x^s}{s} \, ds,

over a suitable contour enclosing the region of convergence.^[28] This inversion technique, akin to the inverse Mellin transform, shifts summation from discrete arithmetic progressions to complex integrals, leveraging residue theorem applications for asymptotic evaluation. These analytic foundations—zeta function properties, Dirichlet series with Euler products, and Perron's summation formula—provide the machinery to analyze sums over primes restricted to residue classes modulo a fixed integer, by incorporating Dirichlet characters to orthogonally decompose the indicator function of such classes.^[27]

Non-Vanishing of L-Functions

The Dirichlet L-function L(s, \chi) for a Dirichlet character \chi modulo q is defined for \operatorname{Re}(s) > 1 by the Dirichlet series

L(s, \chi) = \sum_{n=1}^\infty \frac{\chi(n)}{n^s},

which converges absolutely in this half-plane and admits an Euler product representation

L(s, \chi) = \prod_p \left(1 - \frac{\chi(p)}{p^s}\right)^{-1},

where the product runs over all primes p (with the understanding that terms vanish if \chi(p) = 0).^[2] For non-principal characters \chi, the function L(s, \chi) admits an analytic continuation to an entire function on the complex plane, holomorphic everywhere including at s = 1, where it has no pole.^[2] In contrast, the principal character yields a simple pole at s = 1 with residue \phi(q)/q, where \phi is Euler's totient function.^[29] The non-vanishing of L(1, \chi) \neq 0 for non-principal \chi is a pivotal step in Dirichlet's proof. This is shown using partial summation to establish convergence of the series at s=1 and further arguments involving auxiliary Dirichlet series with non-negative coefficients. For instance, considering \zeta(s)^3 L(s, \chi)^4 L(s, \chi^2), whose Dirichlet series has non-negative terms, the simple pole from \zeta(s)^3 implies the product cannot vanish at s=1, as the positive coefficients prevent cancellation. Similar constructions apply based on whether \chi^2 is principal.^[3]^[30] Taking the logarithm yields

\log L(s, \chi) = \sum_p \frac{\chi(p)}{p^s} + \sum_p \sum_{k \geq 2} \frac{\chi(p^k)}{k p^{k s}},

where the double sum over higher powers is bounded for \operatorname{Re}(s) \geq 1.^[29] As s \to 1^+, the non-vanishing L(1, \chi) \neq 0 ensures \log L(s, \chi) approaches a finite nonzero value, implying the convergence of \sum_p \chi(p) p^{-s} at s=1 without complete phase cancellation across residue classes. This non-vanishing ensures that the partial sum \sum_{p \equiv a \pmod{q}} \frac{1}{p} diverges logarithmically as the upper limit grows, directly implying the infinitude of primes in the arithmetic progression n \equiv a \pmod{q} with \gcd(a, q) = 1.^[2]

Prime Distribution Results

Asymptotic Density

The asymptotic density result implied by Dirichlet's theorem on arithmetic progressions extends the prime number theorem to specify the distribution of primes within residue classes. For positive integers d and a with \gcd(a, d) = 1, let \pi(x; d, a) denote the number of primes p \leq x such that p \equiv a \pmod{d}. Then,

\pi(x; d, a) \sim \frac{\mathrm{Li}(x)}{\phi(d)}

as x \to \infty, where \phi is Euler's totient function and \mathrm{Li}(x) = \int_2^x \frac{dt}{\log t} is the logarithmic integral.^[31]^[32] This asymptotic, known as the prime number theorem for arithmetic progressions, was established by de la Vallée Poussin in 1896 using analytic methods involving Dirichlet L-functions.^[33] Equivalently, the formula can be expressed as

\sum_{\substack{p \leq x \\ p \equiv a \pmod{d}}} 1 \sim \frac{1}{\phi(d)} \sum_{p \leq x} 1 = \frac{\pi(x)}{\phi(d)},

reflecting that \pi(x) \sim \mathrm{Li}(x).^[32] This demonstrates the equidistribution of primes among the \phi(d) residue classes modulo d that are coprime to d, meaning primes are asymptotically equally likely to occur in each such class.^[31] The proportion of primes up to x in any fixed such progression is thus $1/\phi(d), providing a precise measure of their natural density in the sequence of all primes. The derivation of this asymptotic relies on the non-vanishing of Dirichlet L-functions L(s, \chi) for non-principal characters \chi modulo d on the line \mathrm{Re}(s) = 1, combined with Tauberian theorems such as the Wiener-Ikehara theorem to extract the main term from the analytic behavior of the associated von Mangoldt sums.^[33] This framework ensures the uniform distribution across coprime classes without favoring any particular one. The prime number theorem for arithmetic progressions provides the leading asymptotic term \pi(x; d, a) \sim \frac{\mathrm{Li}(x)}{\phi(d)} as x \to \infty, where \gcd(a, d) = 1, but refinements focus on bounding the error term E(x; d, a) = \pi(x; d, a) - \frac{\mathrm{Li}(x)}{\phi(d)}. In 1899, de la Vallée Poussin established an initial explicit bound of the form

|E(x; d, a)| \ll x \exp\left(-c \sqrt{\log x}\right)

for some absolute constant c > 0, valid uniformly for fixed d.^[34] This result, extending his contemporaneous proof of the prime number theorem, relies on a zero-free region for Dirichlet L-functions near \mathrm{Re}(s) = 1.^[35] Siegel's theorem provides an effective approach to the non-vanishing of L(1, \chi) for non-principal real primitive characters \chi modulo d, stating that L(1, \chi) \gg \exp(-c \sqrt{\log d}) for some absolute c > 0, though the implied constant is ineffective due to reliance on class number estimates.^[36] This bound controls potential exceptional real zeros close to s = 1, enabling explicit versions of the prime number theorem in arithmetic progressions, albeit with limitations on uniformity in d. As a consequence, for any A > 1, there exists a constant C = C(A, d) such that

|E(x; d, a)| < C \frac{x}{(\log x)^A},

with the dependence on d arising from the ineffective constants in Siegel's estimate.^[37] Modern unconditional improvements leverage wider zero-free regions for L-functions. The Vinogradov-Korobov zero-free region, established in the 1950s, implies a bound of the form

|E(x; d, a)| \ll x \exp\left(-c \frac{(\log x)^{3/5}}{(\log \log x)^{1/5}}\right)

for some absolute c > 0, valid for d \leq (\log x)^B with sufficiently large B.^[38] This refinement significantly strengthens de la Vallée Poussin's estimate for large x, though it remains subpolynomial in the exponent. Under the Generalized Riemann Hypothesis (GRH), sharper control is possible, with

|E(x; d, a)| \ll \sqrt{x} \log(x d)

uniformly in d.^[39] This bound reflects the expected location of zeros on the critical line \mathrm{Re}(s) = 1/2. The Bombieri-Vinogradov theorem addresses discrepancies across moduli by averaging errors, stating that for any A > 0,

\sum_{d \leq x^{1/2 - \epsilon}} \max_{\substack{a \leq d \\ \gcd(a,d)=1}} |E(x; d, a)| \phi(d) \ll \frac{x}{(\log x)^A}

for some \epsilon > 0, where the implied constant depends on A and \epsilon.^[40] This result, proved in 1965, shows that exceptions to GRH-like error terms are rare on average up to moduli near \sqrt{x}, with applications to sieve methods and elliptic curves.^[41]

Extensions and Generalizations

Effective Versions

Linnik's theorem provides the first effective uniform bound on the smallest prime in an arithmetic progression, stating that for any integers a and d > 0 with \gcd(a, d) = 1, there exists an absolute constant L such that the least prime p \equiv a \pmod{d} satisfies p \ll d^L.^[42] This result, proved by Yuri Linnik in 1944, addresses the ineffectivity inherent in Dirichlet's original proof by establishing an explicit power-saving bound independent of potential exceptional zeros.^[43] The exponent L, known as Linnik's constant, has been progressively refined through advanced zero-free region estimates for Dirichlet L-functions. Significant improvements to Linnik's constant came from D. R. Heath-Brown, who in 1992 established L \leq 5.5 using explicit zero-free regions that handle both the generic case and the possible presence of a Siegel zero.^[44] Further optimization by Triantafyllos Xylouris in 2009 reduced the bound to L \leq 5.2, representing the current best unconditional value.^[45] Under these bounds, the theorem guarantees the existence of a prime p = a + nd in the progression with n < d^5 (absorbing constants into the implicit factor), providing a concrete, computable upper limit on the gap to the first prime for any modulus d. Heath-Brown's and related Siegel-based methods for effective non-vanishing of L(1, \chi) at the edge of the critical strip yield slightly weaker but still explicit bounds on the smallest prime, such as p < d^{c \log d} for some small absolute c > 0, by exploiting partial zero-free regions near s=1.^[44] These approaches separate the analysis into cases with and without a Landau-Siegel zero—a potential real zero \beta of some L(s, \chi) close to 1 for real primitive characters \chi—allowing effective control in the generic case while bounding the exceptional scenario separately.^[36] While explicit computations for fixed small d often reveal the smallest prime in much shorter intervals (typically on the order of (\log d)^2), the uniform ineffectivity of Dirichlet's original theorem arises precisely from the possible existence of a Landau-Siegel zero, which could render L(1, \chi) exceptionally small and disrupt asymptotic prime counts without effective error control.^[46] Effective versions like Linnik's circumvent this by deriving absolute power bounds that hold regardless, ensuring practical applicability across all moduli.

Broader Conjectures

The Bunyakovsky conjecture, proposed in 1857, posits that if f(x) is an irreducible polynomial with integer coefficients, positive leading coefficient, and degree at least 1, such that the values f(n) for positive integers n have no fixed prime divisor (i.e., the greatest common divisor of all f(n) is 1), then f(n) takes prime values for infinitely many n.^[47] This conjecture generalizes Dirichlet's theorem, which corresponds precisely to the linear case where f(x) = a + d x with \gcd(a, d) = 1, but remains unproven for polynomials of degree greater than 1. A prominent example is f(x) = x^2 + 1, where it is unknown whether there are infinitely many primes of this form, despite extensive computational evidence supporting the infinitude up to large bounds.^[47] Schinzel's hypothesis H, formulated in 1958, extends these ideas to systems of polynomials by conjecturing that if f_1(x), \dots, f_k(x) are irreducible polynomials with integer coefficients and positive leading coefficients, and there is no prime p such that p divides all f_i(n) for every integer n, then there are infinitely many integers n such that all f_1(n), \dots, f_k(n) are simultaneously prime. This hypothesis encompasses the Bunyakovsky conjecture as the case k=1 and includes Dirichlet's theorem as the special instance of a single linear polynomial; it also implies results like the twin prime conjecture when applied to the pair f_1(x) = x and f_2(x) = x + 2. While partial progress has been made under additional assumptions, the full hypothesis remains open, highlighting the challenges in extending arithmetic progression results to multivariate or nonlinear prime distributions.^[48] The Bateman–Horn conjecture, introduced in 1962, provides a quantitative refinement by predicting the asymptotic density of such prime values for systems of polynomials. Specifically, for distinct irreducible polynomials f_1(x), \dots, f_k(x) with integer coefficients and no fixed prime divisor, it asserts that the number of n \leq X for which all f_i(n) are prime is asymptotically \mathfrak{S} \int_2^X \frac{dt}{(\log t)^k}, where \mathfrak{S} is a constant depending on the polynomials, derived from the Hardy–Littlewood conjectures. This conjecture implies Schinzel's hypothesis H (by the infinitude following from the positive density) and quantifies the distribution in cases like Bunyakovsky polynomials, but like its predecessors, it awaits proof beyond the linear regime.^[48]

References

[1]
[PDF] Dirichlet's Theorem on Arithmetic Progressions - Rice University
Dirichlet's theorem on arithmetic progressions is a gem of number theory. A great part of its beauty lies in the simplicity of its statement.
[2]
[PDF] 18 Dirichlet L-functions, primes in arithmetic progressions
Nov 10, 2016 · We begin with Dirichlet's theorem on primes in arithmetic progressions, a result that predates the prime number theorem by sixty years. Theorem ...
[3]
[PDF] Section 3, Dirichlet's theorem 1 Introduction. - NYU Courant
If a and n are not relatively prime, then there are not infinitely many primes. Dirichlet's theorem is important because if its intrinsic interest, ...
[4]
[PDF] A Computational Introduction to Number Theory and Algebra (BETA ...
Theorem 5.39 (Dirichlet's Theorem) For any positive integer d and any integer a rel- atively prime to d, there are infinitely many primes p with p ≡ a (mod ...
[5]
[PDF] Dirichlet's theorem about primes in arithmetic progressions
Dirichlet's theorem states that if q and l are two relatively prime positive integers, there are infinitely many primes of the form l+kq. Dirichlet's theorem is ...
[6]
Dirichlet's Theorem -- from Wolfram MathWorld
Given an arithmetic progression of terms an+b, for n=1, 2, ..., the series contains an infinite number of primes if a and b are relatively prime.
[7]
Quadratic Congruences with Prime Moduli - IMOMath
Theorem 10 (a)-2 is a quadratic residue modulo p if and only if p ≡ 1 or p ≡ 3 (mod 8); (b) -3 is a quadratic residue modulo p if and only if p ≡ 1 (mod 6);
[8]
[PDF] On Special Cases of Dirichlet's Theorem on Arithmetic Progressions
3.3 Splitting of primes ≡ 1 mod 6 in the ring of Eisenstein integers . 21 ... The cases a = 1 and n = 4, 6, 8 are proved using quadratic residues. The.
[9]
Primes in Arithmetic Progression Records
Before that the longest known AP was 23 primes in arithmetic progression by Markus Frind, Paul Jobling & Paul Underwood in 2004.
[10]
[PDF] a83 integers 25 (2025) a note on sophie germain primes
Sep 17, 2025 · Since gcd(p, (p − 1)/2) = 1 for an odd prime p, Dirichlet's theorem on arithmetic progressions states that there are infinitely many primes in.
[11]
[PDF] An Lntroduction To The Theory Of Numbers Third Edition
Our purpose is to present a reasonably complete introduction to the theory of numbers within the compass of a single volume The basic concepts are.
[12]
[PDF] Arithmetic and geometric progressions - Mathcentre
We have found the sum of an arithmetic progression in terms of its first and last terms, a and ℓ, ... common difference d. To do this, we just substitute ...
[13]
Primes in arithmetic progressions - Kiran S. Kedlaya
Theorem 5.2. Dirichlet. Any eligible arithmetic progression of positive integers contains infinitely many primes.. Proof.
[14]
Introduction to Analytic Number Theory - SpringerLink
Book Title: Introduction to Analytic Number Theory · Authors: Tom M. · Series Title: Undergraduate Texts in Mathematics · Publisher: Springer New York, NY · eBook ...
[15]
[PDF] 11. Dirichlet characters
Definition 11.7. (1) Let q ∈ N. A Dirichlet character mod q is a character of the multiplicative group (Z/qZ)∗. (2) If χ is a Dirichlet character mod q, we ...
[16]
[1202.3670] Euclid's theorem on the infinitude of primes - math - arXiv
Feb 16, 2012 · We provide a comprehensive historical survey of 200 different proofs of famous Euclid's theorem on the infinitude of prime numbers (300 {\small BC}--2022)}.
[17]
https://www.maths.ed.ac.uk/~v1ranick/papers/legendre.pdf
[18]
A History of the Prime Number Theorem - jstor
primes is contained in an 1849 letter to the astronomer Encke. We have included a translation of Gauss' letter. In his letter Gauss describes his numerical ...Missing: source | Show results with:source
[19]
The Origin of the Prime Number Theorem: A Primary Source Project ...
As early as 1792 or 1793, Gauss claimed, he had conjectured that the number of primes below a bound n was, in his notation, ∫dnlogn. Today we know that Gauss ...
[20]
Recherches sur diverses applications de l'Analyse infinitesimale à la ...
Recherches sur diverses applications de l'Analyse infinitesimale à la théorie des Nombres. · Volume: 19, page 324-369 · ISSN: 0075-4102; 1435-5345/e ...Missing: 1837 | Show results with:1837
[21]
[PDF] Dirichlet's Theorem and Functions as Objects - andrew.cmu.ed
Theorem. Let m and k be relatively prime. Then the arithmetic progression m,m + k,m + 2k,... contains infinitely many primes.Missing: coprimality | Show results with:coprimality
[22]
[0808.1408] There are infinitely many prime numbers in all ... - arXiv
Aug 10, 2008 · Dirichlet's proof of infinitely many primes in arithmetic progressions was published in 1837, introduced L-series for the first time, and it is said to have ...
[23]
[PDF] Primes in arithmetic progressions 1. Dirichlet's theorem
Sep 26, 2015 · Dirichlet's 1837 theorem combines Euler's argument for the infinitude of primes with harmonic analysis on finite abelian groups, and subtler ...Missing: paper details
[24]
[PDF] 6:13a.m. November 16, 2009 Dirichlet's calculation of Gauss sums ...
Nov 16, 2009 · that Dirichlet's proof is just a form of the Poisson summation formula. There is some truth to that, but it doesn't tell the whole story ...
[25]
How constructive is Dirichlet on primes in progressions?
Jul 29, 2013 · Bounds on Linnik's constant answer this for the first prime in each progression. Is there a known analogue for an n-th prime in a progression?How do estimates on $N_\chi(\alpha,T)$ lead to the Dirichlet prime ...Consequences of the Riemann hypothesis - MathOverflowMore results from mathoverflow.netMissing: original no
[26]
[PDF] Math 259: Introduction to Analytic Number Theory The Riemann zeta ...
It follows that ζ also extends to a meromorphic function on C, which is regular except for a simple pole at s = 1, and that this analytic continuation of ζ has.
[27]
[PDF] 1 Dirichlet series - Kiran S. Kedlaya
The quantity L is called the abscissa of absolute convergence of the Dirichlet series; it is an analogue of the radius of convergence of a power series. (In ...Missing: 1837 paper
[28]
[PDF] m3pm16l21.tex Lecture 21. 1.3.2012 5. PERRON'S FORMULA ...
Mar 1, 2012 · PERRON'S FORMULA (Oskar Perron (1880-1975) in 1908). As before, f(s) ... H(s) s(s − 1) ds = 0. The first statement follows, dividing both sides by ...Missing: 1921 paper URL
[29]
[PDF] Dirichlet L-functions, primes in arithmetic progressions
Sep 21, 2019 · The subtle element is non-vanishing of L-functions L(s, χ) at s = 1. For expediency, a first proof of this nonvanishing is given in a Supplement ...
[30]
[PDF] Nonvanishing of Dirichlet L-functions at s=1
In the proof of Dirichlet's theorem on arithmetic progressions, after the various sums and products are unwound, and after what amounts to a simple piece of.
[31]
[PDF] 1 Dirichlet's theorem 2 Asymptotic density and ... - Kiran S. Kedlaya
Dirichlet's idea was to prove, in some appropriate quan- titative sense, that the primes distribute themselves equally among the eligible arithmetic.
[32]
[PDF] arXiv:1204.0708v3 [math.NT] 17 Jul 2012
Jul 17, 2012 · coprime to Q, the number of primes p ≤ X with p = A mod Q is asymptot- ically π(x)/φ(Q), where π(X) is the number of primes up to X and φ(Q).<|control11|><|separator|>
[33]
[PDF] A simple proof of the Wiener–Ikehara Tauberian Theorem
Mar 11, 2024 · Similarly, one can derive instantly the prime number theorem for arithmetic progressions once analytic continuations to Re(s) = 1 of the ...Missing: source | Show results with:source
[34]
[PDF] Chapter 1 Introduction to prime number theory
The central result is the Prime Number. Theorem: Theorem 1.1 (Prime Number Theorem, Hadamard, de la Vallée Poussin, 1896). let π(x) denote the number of ...
[35]
[PDF] The Prime Number Theorem - Penn State University
The classical zero-free region of Theorem 6.6 was established first by de la Vallée Poussin (1899). The estimates (6.6) and (6.8) of Theorem 6.7 were first ...
[36]
[PDF] On Siegel exceptional zeros and Siegel's theorem
Let's first recall the definitions of Dirichlet character and Dirichlet L-functions. The following definitions are taken from [1] chapter 4 and chapter 1.
[37]
The Siegel-Walfisz theorem - Joni's Math Notes
Jan 30, 2015 · We shall prove this result and deduce Siegel's theorem, stating that L(s,\chi) has no zeros with s>1-C(\varepsilon)q^{-\varepsilon} for any ...
[38]
Vinogradov-Korobov bound | What's new - Terry Tao - WordPress.com
Feb 7, 2015 · Exercise 5 (Vinogradov-Korobov in arithmetic progressions) ... . (iii) Obtain the prime number theorem in arithmetic progressions with error term.Missing: unconditional primes
[39]
Chapter 11 Error bounds for primes in arithmetic progressions
Chapter 11 Error bounds for primes in arithmetic progressions. In this chapter, we summarize how to derive a form of the prime number theorem in arithmetic ...Missing: refinements Vallée Poussin
[40]
254A, Notes 3: The large sieve and the Bombieri-Vinogradov theorem
Jan 10, 2015 · A fundamental and recurring problem in analytic number theory is to demonstrate the presence of cancellation in an oscillating sum.
[41]
[PDF] the bombieri–vinogradov theorem
Jul 29, 2016 · Vinogradov [20] states that averaging. E∗(x;q) over a range of q gives an asymptotic order of growth that is more in line with the error term ( ...
[42]
254A, Notes 7: Linnik's theorem on primes in arithmetic progressions
Feb 22, 2015 · It turns out that a more sophisticated version of this type of argument also works to obtain prime number theorems in arithmetic progressions.
[43]
[PDF] linnik's theorem math 613e ubc
Abstract. This report will describe in detail the proof of Linnik's theorem re- garding the least prime in an arithmetic progression.
[44]
Zero‐Free Regions for Dirichlet L‐Functions, and the Least Prime in ...
Zero-free regions for dirichlet L-functions, and the least prime in an arithmetic progression. DR Heath-Brown, DR Heath-Brown Magdalen College, Oxford, OX1 4AU.
[45]
[0906.2749] On Linnik's constant - arXiv
Jun 15, 2009 · Title:On Linnik's constant. Authors:Triantafyllos Xylouris. View a PDF of the paper titled On Linnik's constant, by Triantafyllos Xylouris.
[46]
[PDF] Landau-Siegel zeros and their illusory consequences - eGrove
May 20, 2019 · ▷ Why prove illusory results? ▷ Many results, like Linnik's theorem, require bifurcation: case where Landau-Siegel zero exists, and case where ...<|separator|>
[47]
Bouniakowsky Conjecture -- from Wolfram MathWorld
The Bouniakowsky conjecture states that f(x) is prime for an infinite number of integers x (Bouniakowsky 1857).Missing: arithmetic progressions
[48]
the Bateman–Horn Conjecture? - American Mathematical Society
The Bateman–Horn conjecture with 𝑓1(𝑥) = 𝑥 and 𝑓2(𝑥) = 2𝑥 + 1 yields the same prediction as in the twin-prime case; see Figure 2. The Bateman–Horn even.