Fact-checked by Grok 2 weeks ago

Prime number theorem

The Prime Number Theorem (PNT) is a cornerstone of analytic number theory that quantifies the distribution of prime numbers among the positive integers, stating that the prime-counting function π(x), which gives the number of primes less than or equal to a positive real number x, is asymptotically equivalent to x / ln(x) as x approaches infinity, or π(x) ∼ x / ln(x).^[1] This asymptotic relation captures the intuitive observation that primes become sparser as numbers grow larger, with their density roughly 1 / ln(x) at magnitude x.^[1] The theorem originated from empirical observations and conjectures in the late 18th and early 19th centuries. Carl Friedrich Gauss, based on computations starting around 1792, conjectured in an 1849 letter to Johann Encke that π(x) ≈ Li(x), the logarithmic integral of x, which is asymptotically equivalent to x / ln(x).^[2] Independently, Adrien-Marie Legendre proposed in 1808, in his Théorie des nombres, a similar formula π(x) ≈ x / (ln x - 1.08366) for large x, derived from tables of primes.^[3] Bernhard Riemann advanced the theoretical foundation in his 1859 paper "On the Number of Primes Less Than a Given Magnitude," linking the distribution of primes to the zeros of the Riemann zeta function ζ(s) via an explicit formula involving π(x).^[4] The PNT was rigorously proved independently in 1896 by Jacques Hadamard in his paper "Sur la distribution des zéros de la fonction ζ(s) et ses conséquences arithmétiques" and by Charles Jean de la Vallée Poussin in "Recherches analytiques sur la théorie des nombres premiers," both employing complex analysis to show that ζ(s) has no zeros on the line Re(s) = 1, ensuring the asymptotic behavior.^[5]^[6] These non-elementary proofs marked a triumph of Riemann's ideas, though an elementary proof without complex functions was later provided by Atle Selberg and Paul Erdős in 1949.^[7] The theorem has profound implications, including connections to the Riemann Hypothesis, which posits that all non-trivial zeros of ζ(s) lie on Re(s) = 1/2 and would imply sharper error bounds like π(x) = Li(x) + O(√x ln(x)).^[4]

Core Formulation

Statement of the Theorem

The prime-counting function \pi(x) is defined as the number of prime numbers less than or equal to the real number x.^[8] The Prime Number Theorem states that

\pi(x) \sim \frac{x}{\log x}

as x \to \infty, where the notation f(x) \sim g(x) means that \lim_{x \to \infty} f(x)/g(x) = 1.^[9] This asymptotic relation indicates that the density of primes near x decreases like $1/\log x, providing a precise measure of how primes become sparser among the integers as numbers grow larger.^[10] Equivalent formulations of the theorem involve the Chebyshev functions. The first Chebyshev function is defined as

\theta(x) = \sum_{p \leq x} \log p,

and the Prime Number Theorem is equivalent to \theta(x) \sim x as x \to \infty.^[11] Similarly, the second Chebyshev function is

\psi(x) = \sum_{n \leq x} \Lambda(n),

where \Lambda is the von Mangoldt function satisfying \Lambda(n) = \log p if n = p^k for a prime p and integer k \geq 1, and \Lambda(n) = 0 otherwise; the theorem is also equivalent to \psi(x) \sim x as x \to \infty.^[12]^[13] The Prime Number Theorem was proved independently by Jacques Hadamard and Charles Jean de la Vallée Poussin in 1896, and the term itself was coined by Edmund Landau in 1909.^[12]^[14]

Prime-Counting Function and Logarithmic Integral

The prime-counting function, denoted \pi(x), is defined as the number of prime numbers less than or equal to a positive real number x.^[15] It is a non-decreasing step function that remains constant between consecutive primes and increases by exactly 1 at each prime number p, so that \pi(p) = \pi(p^-) + 1, where p^- denotes the value just before p.^[15] For example, \pi(2) = 1, \pi(3) = 2, and \pi(4) = 2, reflecting the jump at 3 and constancy up to 4. The average order of \pi(x), which describes its typical growth rate, is given asymptotically by the prime number theorem as approximately x / \ln x.^[1] A more precise approximation to \pi(x) is provided by the logarithmic integral function, denoted \mathrm{li}(x), defined as the Cauchy principal value of the integral

\mathrm{li}(x) = \lim_{\epsilon \to 0^+} \left( \int_0^{1-\epsilon} \frac{dt}{\ln t} + \int_{1+\epsilon}^x \frac{dt}{\ln t} \right)

for x > 1.^[16] This definition addresses the singularity at t=1, where \ln t = 0 and the integrand diverges; the principal value ensures convergence by symmetrically excluding the pole. Equivalently, \mathrm{li}(x) can be expressed as \int_2^x \frac{dt}{\ln t} + C, where C incorporates constant terms from the lower limit adjustments, such as \mathrm{li}(2) and contributions near the singularity.^[16] The function \mathrm{li}(x) asymptotically satisfies \mathrm{li}(x) \sim x / \ln x as x \to \infty, with a more refined expansion

\mathrm{li}(x) \sim \frac{x}{\ln x} + \frac{x}{(\ln x)^2} + \frac{2x}{(\ln x)^3} + \cdots = \sum_{k=0}^\infty \frac{k! \, x}{(\ln x)^{k+1}}.

^[16] This series arises from repeated integration by parts and captures higher-order corrections to the leading term. The prime number theorem asserts that \pi(x) \approx \mathrm{li}(x), and in fact, the theorem is equivalent to the statement \pi(x) \sim \mathrm{li}(x).^[1] The logarithmic integral outperforms the simpler x / \ln x as an approximation to \pi(x) because it incorporates the next-order term x / (\ln x)^2 in the asymptotic expansion. The difference \mathrm{[li](/page/Li)}(x) - \pi(x) exhibits oscillatory behavior due to the non-trivial zeros of the Riemann zeta function.^[17]

Historical Context

Early Conjectures and Motivations

The awareness of prime numbers dates back to ancient times, with Euclid providing the first rigorous proof of their infinitude around 300 BCE in his Elements. In Book IX, Proposition 20, Euclid demonstrated that no finite list of primes can exhaust all such numbers by constructing a new prime from the product of existing ones plus one, implying an unending supply without specifying a precise density. This result established that primes are unbounded but offered no quantitative insight into their distribution among the naturals.^[18] In the 18th century, Leonhard Euler advanced understanding by proving the divergence of the sum of reciprocals of primes, \sum_p \frac{1}{p} = \infty, in his 1737 paper "Variae observationes circa series infinitas." Euler linked this to the harmonic series via the Euler product for the Riemann zeta function at s=1, showing that the primes' "density" must grow sufficiently to make the sum diverge, akin to \log \log x for partial sums up to x. This suggested primes occur with frequency roughly $1/\log x, motivating deeper asymptotic studies.^[19] By the late 18th and early 19th centuries, empirical observations fueled precise conjectures. In 1792, at age 15, Carl Friedrich Gauss, based on tables of primes, hypothesized that the prime-counting function \pi(x) approximates the logarithmic integral \mathrm{li}(x) = \int_0^x \frac{dt}{\log t}. Independently, Adrien-Marie Legendre proposed a similar form \pi(x) \approx \frac{x}{\log x - 1.08366} in his 1808 Essai sur la théorie des nombres, refining estimates from prime lists up to 3 million. These conjectures, rooted in numerical evidence rather than proof, pointed to \pi(x) \sim \frac{x}{\log x} as the asymptotic density.^[20] Pafnuty Chebyshev's 1850 memoir "Mémoire sur les nombres premiers" provided the first rigorous bounds, establishing constants c_1 \approx 0.921 and c_2 \approx 1.106 such that c_1 \frac{x}{\log x} < \pi(x) < c_2 \frac{x}{\log x} for sufficiently large x. This confirmed the conjectured order of magnitude without proving the exact asymptotic. Such results were motivated by broader number theory challenges, including Joseph Bertrand's 1845 postulate that a prime exists between n and $2n for n > 1, which Chebyshev proved in 1852 using similar techniques to bound prime gaps and support density estimates.^[21]^[22]

Development and Proofs

Bernhard Riemann laid the foundational groundwork for the analytic study of prime distribution in his 1859 paper "Ueber die Anzahl der Primzahlen unter einer gegebenen Grösse," where he introduced the Riemann zeta function and outlined an explicit formula linking the prime-counting function to the non-trivial zeros of the zeta function, implicitly suggesting an asymptotic behavior for the density of primes without formally stating the Prime Number Theorem.^[23] This work built on earlier bounds established by Chebyshev in the 1850s, which demonstrated that the prime-counting function π(x) satisfies c₁ x / log x < π(x) < c₂ x / log x for suitable constants c₁ and c₂.^[24] The first rigorous proofs of the Prime Number Theorem emerged in 1896, independently provided by Jacques Hadamard and Charles Jean de la Vallée Poussin, who established that π(x) ∼ x / log x through complex analytic methods centered on the zeta function.^[25]^[6] Hadamard's proof, detailed in his paper "Sur la distribution des zéros de la fonction ζ(s) et ses conséquences arithmétiques," utilized contour integration to show that the zeta function has no zeros on the critical line Re(s) = 1, thereby deriving the asymptotic equivalence.^[25] Similarly, de la Vallée Poussin's comprehensive memoir "Recherches analytiques sur la théorie des nombres premiers" employed analogous techniques, including estimates on the growth of the zeta function, to confirm the theorem and provide initial error term bounds.^[6] These proofs marked a culmination of efforts in complex analysis applied to number theory, resolving a conjecture that had persisted since the late 18th century. In the early 20th century, further advancements refined the theorem's implications and equivalences. Edmund Landau's 1909 treatise "Handbuch der Lehre von der Verteilung der Primzahlen" articulated several equivalent formulations of the Prime Number Theorem, including connections to the summatory function of the von Mangoldt function and explicit criteria involving the zeta function's behavior near s = 1. These equivalences facilitated broader applications in analytic number theory. Meanwhile, the development of tauberian theorems provided alternative pathways to the result; the Wiener-Ikehara theorem, formulated in the 1930s by Norbert Wiener and Kiyoshi Ikehara, established a general tauberian principle under which limits of Dirichlet integrals imply asymptotic behaviors, offering a unified framework for deriving PNT-like results from analytic continuations.^[26] Albert Ingham's 1932 monograph "The Distribution of Prime Numbers" synthesized and extended these analytic developments, providing sharper estimates on the error term in the Prime Number Theorem and exploring conditional improvements under assumptions about the zeta function's zeros.^[27] Ingham's work emphasized the role of zero-free regions in the critical strip, building directly on the 1896 proofs to advance quantitative aspects of prime distribution.^[28]

Analytic Approaches

Riemann Zeta Function and Complex Analysis

The Riemann zeta function \zeta(s) is initially defined for complex numbers s with real part \operatorname{Re}(s) > 1 by the infinite series

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

This series converges absolutely in that half-plane, representing the function as a Dirichlet series. Bernhard Riemann extended \zeta(s) via analytic continuation to a meromorphic function on the entire complex plane, with a single simple pole at s=1 and residue 1 there; the continuation preserves the analyticity elsewhere, including at the trivial zeros at negative even integers.^[23] A fundamental representation linking \zeta(s) directly to the primes is the Euler product formula, valid for \operatorname{Re}(s) > 1:

\zeta(s) = \prod_p \left(1 - p^{-s}\right)^{-1},

where the product runs over all prime numbers p. This infinite product arises from the unique prime factorization of integers, as expanding each geometric series \sum_{k=0}^\infty p^{-ks} and multiplying yields the original series for \zeta(s); the formula underscores the intimate connection between the zeta function and the distribution of primes.^[29] The functional equation relates values of \zeta(s) across the complex plane:

\zeta(s) = 2^s \pi^{s-1} \sin\left(\frac{\pi s}{2}\right) \Gamma(1-s) \zeta(1-s),

where \Gamma denotes the gamma function. This symmetric relation, derived using the gamma function's integral representation and contour integration techniques, facilitates the analytic continuation and reveals the function's behavior in the critical strip $0 < \operatorname{Re}(s) < 1, including the locations of its non-trivial zeros.^[23] An explicit formula expressing the prime powers in terms of the zeros of \zeta(s) is given by von Mangoldt for the Chebyshev function \psi(x) = \sum_{n \leq x} \Lambda(n), where \Lambda(n) = \log p if n = p^k for prime p and integer k \geq 1, and \Lambda(n) = 0 otherwise:

\psi(x) = x - \sum_\rho \frac{x^\rho}{\rho} - \log(2\pi) - \frac{1}{2} \log(1 - x^{-2}),

with the sum over all non-trivial zeros \rho of \zeta(s). This formula quantifies the deviation of \psi(x) from x as a sum over the zeros, highlighting their role in prime distribution; the logarithmic terms account for contributions from the pole at s=1 and trivial zeros.^[30] The analytic proof of the prime number theorem relies on Perron's formula, which inverts Dirichlet series to express partial sums like \sum_{n \leq x} \Lambda(n) as a contour integral:

\sum_{n \leq x} \Lambda(n) = \frac{1}{2\pi i} \int_{c - iT}^{c + iT} -\frac{\zeta'(s)}{\zeta(s)} \frac{x^s}{s} \, ds + O\left(\frac{x \log x}{T}\right),

for c > 1 and large T. Shifting the contour leftward into the critical strip captures the residue at the pole s=1 of -\zeta'(s)/\zeta(s), yielding the main term x; remaining contributions from zeros and the shifted integral provide the error term, whose size depends on the distribution of zeros near \operatorname{Re}(s) = 1. This approach was employed in the original proofs by Hadamard and de la Vallée Poussin in 1896.^[31]

Non-Vanishing on the Line Re(s) = 1

The non-vanishing of the Riemann zeta function \zeta(s) on the line \operatorname{Re}(s) = 1 is essential for establishing the asymptotic \pi(x) \sim x / \log x in the Prime Number Theorem, as a zero at s = 1 + it with t \neq 0 would introduce persistent oscillations in the prime-counting function \pi(x) via the Perron formula or inverse Mellin transform, disrupting the main term.^[5]^[6] Jacques Hadamard proved this non-vanishing in 1896 by applying the argument principle to a rectangular contour that avoids the line \operatorname{Re}(s) = 1 but encircles potential zeros, combined with precise growth estimates for \zeta(s) and its derivative in the half-plane \operatorname{Re}(s) > 1/2, showing that the change in argument along the boundary implies no zeros on the line.^[5] Independently, Charles-Jean de la Vallée Poussin established the same result in 1896 by analyzing \log |\zeta(1 + it)|, which approximates \sum_p \cos(t \log p)/p plus contributions from higher prime powers that are negligible for large t. To demonstrate that this sum cannot diverge to -\infty (indicating a zero), de la Vallée Poussin bounded it from below using the non-negativity of the trigonometric polynomial $3 + 4 \cos \theta + \cos 2\theta \geq 0, applied to the distribution of \{\log p / (2\pi)\} modulo 1, leveraging the density of primes to ensure the phases t \log p \mod 2\pi cannot align excessively negatively.^[6] de la Vallée Poussin further proved a zero-free region \zeta(s) \neq 0 for \sigma > 1 - c / \log(|t| + 2) with c > 0 an absolute constant, obtained by perturbing the argument around the line \operatorname{Re}(s) = 1 and controlling the real part via similar prime sum estimates.^[6] Hadamard derived an analogous zero-free region using comparable growth and contour techniques.^[5] This zero-free region yields an effective Prime Number Theorem: \pi(x) = \operatorname{li}(x) + O\left( x \exp\left( -c \sqrt{\log x} \right) \right) for some c > 0, where the error bound follows from integrating over the zero-free domain in the Tauberian theorem applied to [\zeta(s)](/page/Riemann_zeta_function).^[5]^[6]

Newman's Simplified Proof

In 1980, Donald J. Newman published a streamlined analytic proof of the prime number theorem that significantly simplifies the classical approaches by Hadamard and de la Vallée Poussin. The proof assumes the non-vanishing of the Riemann zeta function on the line \operatorname{Re}(s) = 1, ensuring that the function h(s) = -\frac{\zeta'(s)}{\zeta(s)} - \frac{1}{s-1} is analytic in \operatorname{Re}(s) > 1 and extends continuously to the boundary \operatorname{Re}(s) = 1. By establishing a uniform bound |h(s)| \leq \frac{K}{\sigma - 1} for \operatorname{Re}(s) = \sigma > 1 with an absolute constant K, Newman applies a tauberian theorem to derive the desired asymptotic. This method bypasses the need for detailed zero-free region estimates deeper in the critical strip, relying instead on basic complex analysis and Fourier techniques for the bound. The central result is the asymptotic \sum_{n \leq x} \frac{\Lambda(n)}{n} = \log x + O(1), where \Lambda(n) is the von Mangoldt function. This follows from applying Ikehara's tauberian theorem to the Dirichlet series -\frac{\zeta'(s)}{\zeta(s)} = \sum_{n=1}^\infty \frac{\Lambda(n)}{n^s} = \frac{1}{s-1} + h(s). The theorem states that if a(n) \geq 0 for all n, the associated Dirichlet series G(s) = \sum a(n) n^{-s} equals \frac{c}{s-1} + H(s) for \operatorname{Re}(s) > 1, where H(s) is analytic in this half-plane and satisfies |H(s)| \leq \frac{A}{\sigma - 1} for $1 < \sigma \leq 2 with constants A, c > 0, then \sum_{n \leq x} a(n) \sim c \log x as x \to \infty. In this context, a(n) = \Lambda(n), c = 1, and H(s) = h(s), yielding the sum with error O(1). Newman employs a specialized, elementary version of this theorem tailored to the prime number theorem, proved via integration by parts and positivity without invoking the full Wiener-Ikehara machinery. Newman's key innovation lies in proving the bound on h(s) using Fourier analysis on \log |\zeta(1 + it)|^2. Specifically, for $1 < \sigma \leq 2, the real part \operatorname{Re} h(\sigma + it) is expressed as an integral transform involving the Fourier coefficients derived from \log |\zeta(1 + it)|^2 = \sum_{n=1}^\infty \frac{\Lambda(n)}{n} \left(1 - \cos(t \log n)\right), or more precisely, through Parseval's identity applied to the expansion. The growth estimate \log |\zeta(1 + it)|^2 = O(\log |t|) and the positivity of the spectral measure ensure that the contributions from the oscillatory terms average out, yielding |\operatorname{Re} h(\sigma + it)| \leq \frac{4}{\sigma - 1}. A similar argument bounds the imaginary part using the boundedness of \arg \zeta(1 + it), resulting in the uniform bound |h(s)| \leq \frac{8}{\sigma - 1}. This direct spectral approach replaces cumbersome contour shifts and growth estimates in prior proofs. From \sum_{n \leq x} \frac{\Lambda(n)}{n} = \log x + O(1), the Chebyshev function satisfies \psi(x) \sim x. This is obtained via partial summation: \sum_{n \leq x} \frac{\Lambda(n)}{n} = \frac{\psi(x)}{x} + \int_1^x \frac{\psi(t)}{t^2} \, dt. Setting the integral form equal to \log x + O(1) and applying a basic tauberian principle (or direct differentiation under the assumption of slower growth) implies \psi(x) = x + o(x). The prime-counting function then follows as \pi(x) \sim \frac{x}{\log x} by another partial summation step: \pi(x) = \int_2^x \frac{1}{\log t} \, d\psi(t). Newman's proof spans just four pages and requires only undergraduate-level complex analysis, making it more accessible than earlier versions while preserving rigor. Its elegance has inspired expositions, such as Don Zagier's 1997 presentation framing it as a sequence of five lemmas that highlight the interplay between analytic continuation, bounds, and tauberian inversion.

Elementary Proofs

Selberg-Erdős Method

The Selberg-Erdős method refers to the groundbreaking elementary proof of the prime number theorem developed independently by Atle Selberg and Paul Erdős in 1949, marking the first demonstration of the theorem without relying on complex analysis. This approach was particularly motivated by the challenges of World War II, during which Selberg, working in isolation in Norway, sought methods accessible without the full apparatus of analytic number theory that had become difficult to access due to wartime disruptions. At the heart of Selberg's proof lies his symmetry formula, an elementary identity relating sums involving the von Mangoldt function Λ(n), defined as log p if n is a power of a prime p and 0 otherwise. The formula states that

\sum_{n \leq x} \Lambda(n) \log n + \sum_{u v \leq x} \Lambda(u) \Lambda(v) = 2x \log x + O(x),

where the error term is bounded elementarily. This identity is derived using basic tools from arithmetic functions, such as Möbius inversion and properties of Dirichlet convolution, without invoking the Riemann zeta function. Selberg established it by considering the second moment of the Chebyshev function ψ(x) = ∑_{n ≤ x} Λ(n), showing that

\int_1^x \frac{\psi(t)^2}{t} \, dt = \frac{x^2}{2} + O\left(\frac{x^2}{\log x}\right),

which implies the average value of (ψ(x) - x)^2 / x is small, thereby yielding ψ(x) ∼ x asymptotically. The key steps involve first proving preliminary estimates on sums of Λ(n) using sieve-like techniques and partial summation, then applying the symmetry formula to control the variance of ψ(x) around x. By differentiating and integrating the resulting relations, Selberg extracts the main term, confirming that the number of primes up to x is asymptotically x / log x. His original paper presents this in a concise argument spanning roughly nine pages. Erdős contributed an independent elementary proof shortly after, building on Selberg's ideas but employing a distinct combinatorial approach with binomial coefficients and density arguments from sieve theory to bound the error in prime distribution. This method also avoids complex variables, emphasizing upper and lower bounds for ψ(x) through estimates on the number of integers free of small prime factors. The joint simplification by Selberg and Erdős further streamlined the proof, highlighting its accessibility using only undergraduate-level number theory. The significance of this method lies in its demonstration that the prime number theorem could be proved elementarily, without the zeta function's non-vanishing properties, inspiring subsequent developments in additive combinatorics and sieve methods in number theory.

Key Elementary Techniques

The hyperbola method is a fundamental combinatorial tool in elementary proofs of the prime number theorem, enabling the asymptotic evaluation of Dirichlet convolutions without complex analysis by partitioning sums based on the size of factors. In particular, Selberg applied this method to the sum \sum_{d \leq x} \Lambda(d) \lfloor x/d \rfloor = \sum_{n \leq x} \log n, where \Lambda is the von Mangoldt function, by splitting the sum into terms where d \leq \sqrt{x} (using direct summation) and d > \sqrt{x} (where \lfloor x/d \rfloor is small, allowing reversal to sum over small quotients).^[32] This yields \psi(x) = x + O(x^{1/2} \log^2 x), with \psi(x) = \sum_{n \leq x} \Lambda(n), providing an initial estimate that is refined further in the proof.^[32] A key identity derived via Dirichlet convolution in Selberg's approach is \sum_{mn \leq x} \Lambda(m) \Lambda(n) = \sum_{k \leq x} \mu(k) (\log (x/k))^2 + O(\sqrt{x} \log x), obtained by Möbius inversion of the relation (\log n)^2 = \sum_{d|n} \Lambda(d) \log (n/d) \cdot something, but more precisely from convolving the logarithmic identity twice and applying the hyperbola splitting to handle the double sum.^[32] This convolution identity, central to the Selberg-Erdős method, expresses the square of the Chebyshev function in terms of error terms controllable by elementary means, leading to improved bounds on \psi(x) - x. Estimates on weighted sums like \sum_{n \leq x} \Lambda(n) f(n) for smooth test functions f (e.g., f(n) = \log (x/n) or polynomials) are then obtained using integration by parts or density arguments, bounding the contribution from large prime powers via sieve-like exclusions.^[32] Erdős's complementary approach employs binomial coefficients to establish upper and lower bounds on the prime counting function, leveraging the expansion of (1+1)^{2m} = \sum_{k=0}^{2m} \binom{2m}{k} to count integers up to N = 2^{2m} that are products of small primes. Specifically, by showing that \binom{2m}{m} is not divisible by any prime p > m, one derives that the number of integers up to N divisible by primes larger than m is at least a positive proportion, implying \pi(N) \gg N / \log N and upper bounds via similar density estimates on smooth numbers. Common tools across these elementary techniques include partial summation (analogous to integration by parts for sums), which converts estimates on \psi(x) to those on \pi(x) via \pi(x) = \int_2^x \frac{d\psi(t)}{\log t}, yielding \pi(x) \sim x / \log x from \psi(x) \sim x, and Abel summation for handling oscillatory integrals in error terms. Density arguments, such as bounding the contribution of primes in short intervals or excluding composites via inclusion-exclusion with the Möbius function, further refine these without invoking contour integration.^[32] Despite their elegance, these elementary methods yield weaker error terms compared to analytic proofs, typically achieving \psi(x) = x + O(x \exp(-c \sqrt{\log x / \log \log x})) for some constant c > 0, rather than the sharper O(x \exp(-c \sqrt{\log x})) from Riemann's explicit formula.^[32]

Extensions

Arithmetic Progressions

The prime number theorem in arithmetic progressions provides an asymptotic formula for the distribution of prime numbers within specific residue classes. For positive integers a and q with \gcd(a, q) = 1, let \pi(x; q, a) denote the number of primes less than or equal to x that are congruent to a modulo q. The theorem states that

\pi(x; q, a) \sim \frac{x}{\phi(q) \log x}

as x \to \infty, where \phi is Euler's totient function. This result implies that primes are equidistributed among the \phi(q) residue classes coprime to q, each receiving approximately an equal share of the total primes up to x. The theorem extends Dirichlet's 1837 result on the infinitude of primes in such progressions by quantifying their density relative to the overall prime distribution.^[6] This asymptotic was established by Charles Jean de la Vallée Poussin in 1896, building on his proof of the classical prime number theorem. The proof employs complex analysis on Dirichlet L-functions, which are defined for each Dirichlet character \chi modulo q as

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

These functions generalize the Riemann zeta function (\zeta(s) = L(s, \chi_0), where \chi_0 is the principal character) and possess Euler products over primes, reflecting the multiplicative structure of characters. The prime power sum \sum_{p \leq x} \log p \cdot \chi(p) is analyzed via the logarithmic derivative of L(s, \chi), leading to an explicit formula involving the zeros of these L-functions. By establishing a zero-free region to the left of \Re(s) = 1 analogous to the zeta function case, de la Vallée Poussin derives the desired asymptotic for the non-principal characters, combining with the principal case to yield the equidistribution.^[6] A key ingredient is the non-vanishing of L(s, \chi) on the line \Re(s) = 1. For the principal character, this follows from the pole of \zeta(s) at s=1. For non-principal \chi, L(1, \chi) \neq 0; this was initially shown by Dirichlet for primitive real (quadratic) characters using properties of the Dedekind zeta function and the class number formula for imaginary quadratic fields, where L(1, \chi) = \frac{2\pi h}{w \sqrt{|D|}} with h the class number, w the number of units, and D the discriminant, so since h \geq 1, L(1, \chi) > 0^[33]. For general non-principal \chi, density arguments or extensions of these ideas confirm L(1, \chi) \neq 0, ensuring no zeros at s=1. Broader non-vanishing on \Re(s)=1 is obtained via contradiction arguments assuming a zero, leading to logarithmic singularities inconsistent with the convergence of L(s, \chi).^[34] Effective versions of the theorem quantify the error term E(x; q, a) = \pi(x; q, a) - \frac{\mathrm{li}(x)}{\phi(q)}, where \mathrm{li}(x) is the logarithmic integral. Unconditionally, the Siegel–Walfisz theorem provides

E(x; q, a) = O\left( x \exp\left( -c \sqrt{\log x} \right) \right)

uniformly for q \leq \exp\left( c' \sqrt{\log x} \right) and any c > 0, with explicit constants depending on c. Under the generalized Riemann hypothesis (GRH), which posits all non-trivial zeros of L(s, \chi) lie on \Re(s) = 1/2, sharper bounds hold: E(x; q, a) = O\left( \sqrt{x} (\log (x q))^2 \right), uniform in q and a. These improvements arise from truncating the explicit formula at height T \approx \sqrt{x}, leveraging the zero-free half-plane.^[35] The theorem also reveals subtle biases in the distribution of primes across residue classes, known as prime number races. For instance, Chebyshev observed that there appear to be more primes congruent to 3 modulo 4 than to 1 modulo 4 up to x, a phenomenon called Chebyshev's bias: \pi(x; 4, 3) > \pi(x; 4, 1) holds for the logarithmic density of x approaching about 0.9959. This bias, counterintuitive given equidistribution, stems from the low-lying zeros of the associated L-functions; the non-principal character modulo 4 has a real zero at the central point, skewing the race in favor of the 3 mod 4 class. Similar biases occur in other progressions, quantified via the distribution of zeros under assumptions like the linear independence of zero imaginaries.

Analogues in Finite Fields

In the context of function fields, the prime number theorem finds a natural analogue through the study of monic irreducible polynomials in the polynomial ring \mathbb{F}_q[T], where \mathbb{F}_q is the finite field with q elements and q is a prime power. These irreducible polynomials serve as the primes in this setting, and the analogy measures the "size" of polynomials by x = q^n, where n is the degree, corresponding to \log_q x = n in the classical case. The counting function \pi_q(n) denotes the number of such monic irreducibles of degree at most n.^[36] The prime polynomial theorem asserts that \pi_q(n) \sim \frac{q^n}{n} as n \to \infty. This asymptotic distribution parallels the classical prime number theorem \pi(x) \sim \frac{x}{\log x}. An exact formula for the number I_q(n) of monic irreducibles of precise degree n is I_q(n) = \frac{1}{n} \sum_{d \mid n} \mu(d) q^{n/d}, where \mu is the Möbius function defined on the positive integers via divisors of n. Summing these yields \pi_q(n) = \sum_{k=1}^n I_q(k), from which the leading asymptotic term emerges directly.^[36] The proof relies on the zeta function \zeta_q(s) of \mathbb{F}_q[T], defined for \Re(s) > 1 by the Dirichlet series \zeta_q(s) = \sum_{\substack{f \in \mathbb{F}_q[T] \\ f \text{ monic} \\ f \neq 0}} |f|^{-s}, with |f| = q^{\deg f}. This function factors as the Euler product \zeta_q(s) = \prod_P (1 - |P|^{-s})^{-1}, taken over all monic irreducibles P. Remarkably, it admits the explicit closed-form expression \zeta_q(s) = \frac{1}{1 - q^{1-s}}, which is meromorphic on \mathbb{C} with simple poles at the points s = 1 + \frac{2\pi i k}{\log q} for k \in \mathbb{Z}. The prime polynomial theorem follows from analyzing the logarithmic derivative -\frac{\zeta_q'(s)}{\zeta_q(s)} = \sum_P \sum_{m=1}^\infty \frac{1}{m} |P|^{-m s}, using partial summation or Tauberian methods to extract the sum over irreducibles.^[36] The analogue of the Riemann hypothesis holds unconditionally in this function field setting, as the explicit form of \zeta_q(s) reveals no zeros in the half-plane \Re(s) > 1/2; the poles lie entirely on the critical line \Re(s) = 1, and the function is otherwise holomorphic there. This yields a precise error term: \pi_q(n) = \frac{q^n}{n} + O\left( \frac{q^{n/2}}{n} \right). The Möbius inversion formula for I_q(n) provides an exact count without approximation, highlighting the stronger control available compared to the integer case.^[36] These analogues extend to applications in coding theory, where monic irreducible polynomials generate finite field extensions essential for constructing algebraic-geometric codes and cyclic codes like BCH and Reed-Solomon, enabling efficient error detection and correction in digital communications. They also inform finite geometry, particularly in counting irreducible components or points on varieties over \mathbb{F}_q.

Bounds and Approximations

Error Terms in the Prime-Counting Function

The error term in the prime number theorem quantifies the deviation between the prime-counting function \pi(x) and its asymptotic approximation \operatorname{li}(x). In 1899, Charles Jean de la Vallée Poussin established a classical zero-free region for the Riemann zeta function, leading to the bound |\pi(x) - \operatorname{li}(x)| = O\left(x \exp\left(-c \sqrt{\log x}\right)\right) for some positive constant c.^[37] This bound was significantly improved in 1958 by Nikolai Korobov and Ivan Vinogradov, who utilized advanced estimates on exponential sums to derive a stronger zero-free region. Their work yields |\pi(x) - \operatorname{li}(x)| = O\left(x \exp\left(-d (\log x)^{3/5} (\log \log x)^{-1/5}\right)\right) for some positive constant d, representing the state-of-the-art asymptotic form for unconditional error estimates.^[37] Subsequent refinements, including poly-logarithmic adjustments to the exponent up to around 0.6 in recent analyses as of 2025, have optimized the constants but preserved the essential structure of this bound.^[38] Assuming the Riemann hypothesis, the error term simplifies dramatically. In 1901, Helmut von Koch showed that the hypothesis implies |\pi(x) - \operatorname{li}(x)| = O(\sqrt{x} \log x). An explicit version of this was provided by Lowell Schoenfeld in 1976, stating that under the Riemann hypothesis, |\pi(x) - \operatorname{li}(x)| < \frac{\sqrt{x} \log x}{8\pi} for all x \geq 2657. The error term \operatorname{li}(x) - \pi(x) oscillates and changes sign infinitely often, as proved by John Edensor Littlewood in 1914 using properties of the zeta function's zeros. The first such sign change, where \pi(x) > \operatorname{li}(x), is known to occur before x < 1.397 \times 10^{316}, based on computational and analytic bounds by Carter Bays and Richard H. Hudson in 2000. For finite x, non-asymptotic inequalities provide practical lower bounds. Rosser and Schoenfeld established in 1962 that \pi(x) > \frac{x}{\log x} for all x \geq 17, ensuring the prime-counting function exceeds the simplest asymptotic form in this range.

Estimates for the nth Prime

The prime number theorem implies that the nth prime number p_n satisfies p_n \sim n \ln n as n \to \infty. This asymptotic equivalence follows directly from inverting the relation \pi(x) \sim x / \ln x, where \pi(p_n) = n, leading to n \approx p_n / \ln p_n and solving for p_n.^[39] Refined asymptotic expansions provide greater precision. One such expansion is

p_n = n \ln n + n \ln \ln n - n + O\left( \frac{n \ln \ln \ln n}{\ln \ln n} \right),

derived from higher-order terms in the inverse of the logarithmic integral function and verified through explicit estimates without assuming the Riemann hypothesis. This form captures the leading corrections to the basic asymptotic and stems from work by Pierre Dusart in the early 2010s.^[40] Explicit bounds offer practical inequalities for computation. For n \geq 6,

n (\ln n + \ln \ln n - 1) < p_n < n (\ln n + \ln \ln n).

These inequalities, established by Dusart, provide tight intervals that improve on earlier results and hold unconditionally.^[40] Under the Riemann hypothesis, sharper error bounds are possible. Specifically, |p_n - n \ln n| = O(\sqrt{n} (\ln n)^2), reflecting the improved error term O(\sqrt{x} \ln x) in the prime number theorem for \pi(x). This conditional estimate significantly narrows the gap around the main term for large n. Historically, such bounds have been progressively tightened through computational methods verifying the prime number theorem up to enormous scales, with recent advancements extending explicit guarantees to n exceeding $10^{23} via optimized sieving and zero-free region analyses.^[41]

Computational Verification

Tables and Numerical Data

The computation of the prime-counting function π(x) has a long history, beginning with manual calculations by Carl Friedrich Gauss in the late 18th century. Gauss estimated π(x) for x up to 10^8 using sieving methods documented in his mathematical diary from 1792–1793, providing early empirical evidence for the prime number theorem's asymptotic behavior. In the 19th century, Adrien-Marie Legendre contributed similar tables up to 10^7. Modern computations leverage advanced sieve algorithms and distributed computing, achieving values up to x = 10^{27} as of 2021 using tools like the primecount software by Kim Walisch, which employs combinatorial methods for efficiency.^[42] A key tool in these computations is the Meissel-Lehmer algorithm, originally developed by Ernst Meissel in 1870 and refined by Derrick Henry Lehmer in 1959. This combinatorial method reduces the counting of primes to evaluating inclusion-exclusion over prime factors, enabling fast calculation of π(x) for large x without enumerating all primes. It forms the basis for many contemporary implementations, allowing verification of the prime number theorem to extreme scales. The following table provides a sample of computed values for π(x), the approximation x / \ln x, and the offset logarithmic integral Li(x) at x = 10^k for k from 1 to 10. Here, \ln denotes the natural logarithm, and Li(x) is defined as \int_2^x \frac{dt}{\ln t}. The values demonstrate the increasing accuracy of these approximations as x grows, with Li(x) generally providing a closer fit than x / \ln x. Data for π(x) are from standard tabulations verified across multiple sources; Li(x) values are computed to high precision using series expansions.^[43] | k | x = 10^k | π(x) | x / \ln x | Li(x) | Relative error |π(x) - Li(x)| / x | |-----|--------------|---------------|---------------|---------------|----------------|-----------------------------| | 1 | 10 | 4 | 4.34 | 5.12 | 1.12 × 10^{-1} | | 2 | 100 | 25 | 21.71 | 29.08 | 4.08 × 10^{-2} | | 3 | 1,000 | 168 | 144.76 | 177.61 | 9.61 × 10^{-3} | | 4 | 10,000 | 1,229 | 1,085.74 | 1,248.43 | 1.94 × 10^{-3} | | 5 | 100,000 | 9,592 | 8,685.89 | 9,629.11 | 3.71 × 10^{-4} | | 6 | 1,000,000 | 78,498 | 72,382.41 | 78,628.17 | 1.30 × 10^{-4} | | 7 | 10,000,000 | 664,579 | 620,420.62 | 664,918.40 | 3.39 × 10^{-5} | | 8 | 100,000,000 | 5,761,455 | 5,428,630.42 | 5,762,139.82 | 6.85 × 10^{-6} | | 9 | 1,000,000,000| 50,847,534 | 48,254,942.57 | 50,849,601.18 | 2.07 × 10^{-6} | | 10 | 10,000,000,000| 455,052,511 | 434,294,481.90| 455,055,615.24| 3.10 × 10^{-7} | For larger x, such as up to 10^{25}, the patterns persist: π(10^{25}) = 172,669,445,638,873,604,178,630, with Li(10^{25}) ≈ 172,669,445,670,988,464,000,000, showing continued convergence.^[43] Empirical observations from these tables reveal that Li(x) slightly overestimates π(x) for small to moderate x, with the difference π(x) - Li(x) being negative but decreasing relatively. However, under the Riemann hypothesis, the first crossover where π(x) > Li(x) occurs near the Skewes number, an upper bound of approximately 10^{10^{10^{34}}} given by S. Skewes in 1933 assuming the negation of the Riemann hypothesis.^[44] These computations verify the prime number theorem empirically to remarkable precision. For instance, at x = 10^{24}, the relative error satisfies |π(10^{24}) - Li(10^{24})| / 10^{24} < 10^{-10}, consistent with bounds under the Riemann hypothesis derived by L. Schoenfeld in 1976. This holds for all verified x up to 10^{27}, confirming the asymptotic π(x) ∼ x / \ln x with extraordinary accuracy.

Prime Races and Oscillations

Prime races refer to the competitive behavior between the distributions of primes in different residue classes modulo a fixed integer q > 1. Specifically, for coprime integers a, b \in \{1, 2, \dots, q-1\}, the race compares the prime-counting functions \pi(x; q, a) and \pi(x; q, b), which count the number of primes up to x congruent to a and b modulo q, respectively. The difference \pi(x; q, a) - \pi(x; q, b) oscillates as x grows, reflecting subtle biases in the prime distribution predicted by the prime number theorem for arithmetic progressions.^[45] A prominent example is Chebyshev's bias, first observed by Chebyshev in 1853, which indicates that there are typically more primes congruent to 3 modulo 4 than to 1 modulo 4 up to large x. This bias arises from the non-vanishing of L(1, \chi) for the non-principal Dirichlet character \chi modulo 4, leading to a logarithmic preference for the non-residue class. Although Littlewood proved in 1914 that the lead reverses infinitely often under the Riemann Hypothesis, numerical evidence shows these reversals are rare. Rubinstein and Sarnak quantified this in 1994, demonstrating under the Riemann Hypothesis and the linear independence hypothesis for the zeros of Dirichlet L-functions that the logarithmic density of the set where \pi(x; 4, 3) > \pi(x; 4, 1) is approximately 0.9959, meaning the bias holds for about 99.59% of the time.^[45] Computational studies confirm the persistence of these biases to extraordinarily large scales. Early calculations by Bays and Hudson in 1978 identified the first reversal in the modulo 4 race at x \approx 26861, with subsequent ones occurring sporadically but infrequently. More extensive verifications, leveraging advanced algorithms, have extended these races up to x = 10^{27}, where the 3 modulo 4 class maintains its lead without further major reversals, aligning with the predicted densities. Recent distributed computing efforts continue to explore these biases at large scales.^[45] Beyond pairwise races, the oscillatory nature of prime distributions manifests in the error term of the prime number theorem itself, particularly in \pi(x) - \mathrm{Li}(x), where \mathrm{Li}(x) is the offset logarithmic integral. These oscillations are primarily driven by the low-lying zeros of the Riemann zeta function, with the spacing and imaginary parts of these zeros dictating the frequency and amplitude of sign changes. Littlewood established in 1914 that \pi(x) - \mathrm{Li}(x) changes sign infinitely often, with the first positive crossing (where \pi(x) > \mathrm{Li}(x)) estimated by Bays and Hudson in 2000 to occur near x \approx 1.397 \times 10^{316}, based on detailed analysis of zeta zero contributions. This huge scale underscores the subtle interplay between analytic number theory and computational verification in understanding prime oscillations.

References

[1]
Prime Number Theorem -- from Wolfram MathWorld
The prime number theorem gives an asymptotic form for the prime counting function pi(n), which counts the number of primes less than some integer n.
[2]
The Origin of the Prime Number Theorem: A Primary Source Project ...
Near the end of the eighteenth century, Adrien-Marie Legendre (1752–1833) and Carl Friedrich Gauss (1777–1855) seemingly independently began a study of the ...
[3]
[PDF] The Origin of the Prime Number Theorem - Ursinus Digital Commons
Mar 6, 2019 · (Essay on Number Theory) [Legendre, 1808] – the first number theory textbook ever written. Legendre's book covered a large number of topics ...
[4]
Riemann's 1859 Manuscript - Clay Mathematics Institute
This theorem, first conjectured by Gauss when he was a young man, states that the number of primes less than x is asymptotic to x/log(x). Very roughly speaking, ...
[5]
[PDF] Sur la distribution des zéros de la fonction (s) et ses conséquences ...
BULLETIN DE LA S. M. F.. J. HADAMARD. Sur la distribution des zéros de la fonction ζ(s) et ses conséquences arithmétiques. Bulletin de la S. M. F., tome 24 ( ...
[6]
Recherches analytiques sur la théorie des nombres premiers
Feb 4, 2008 · Recherches analytiques sur la théorie des nombres premiers. by: Charles Jean de La Vallée Poussin ... PDF download · download 1 file · SINGLE ...
[7]
[PDF] THE ELEMENTARY PROOF OF THE PRIME NUMBER THEOREM
The first proof of the prime number theorem was given by Hadamard [H1], [H2] and de la Vallée Poussin [VP] in 1896. The proof was not elementary and made use of.
[8]
The Classical Proof of the Prime Number Theorem
The first complete proof of the Prime Number Theorem was given (independently) by Hadamard and de la Vallé Poussin in 1896 [1,4]. It was the culmination of work ...Missing: original | Show results with:original
[9]
[PDF] A formally verified proof of the prime number theorem - andrew.cmu.ed
The prime number theorem. Let π(x) denote the number of primes less than or equal to x. The prime number theorem: π(x)/x is asymptotic to 1/ln x, i.e. lim x ...
[10]
[PDF] Prime Number Theorem - UChicago Math
Jul 20, 2012 · The prime number theorem estimates how many prime numbers exist under a given number, using a function π(x) to describe its behavior.
[11]
[PDF] simple proof of the prime number theorem
The corollary says in particular that the condition ϑ(x) = O(x) and the properties of D(s) combine to give θ(x) ∼ x. This proves the Prime Number Theorem.
[12]
[PDF] Prime Number Theorem - UC Davis Math
In 1896 the prime number theorem was finally proved by Jacques Hadamard [12] and also by Charles–Jean de la Vallée Poussin [6]. The first part of the proof is ...
[13]
[PDF] Math 213a (Fall 2024) Yum-Tong Siu 1 PRIME NUMBER THEOREM
Nov 5, 2024 · which is known as the von Mangoldt function. Let ψ(x) = P n<x. Λ ... the function ψ(x) so that the Prime Number Theorem π(x) ∼ x log x.
[14]
[PDF] The prime number theorem - OpenBU - Boston University
the process of proving the prime number theorem~ This theorem, so named by. E ... Hadama;rd of France and Charles de la Vallee-Poussin of Belgium. Other ...
[15]
Prime Counting Function -- from Wolfram MathWorld
This notation was introduced by number theorist Edmund Landau in 1909 and has now become standard. In the words of Derbyshire (2004, p. 38), "I am sorry about ...Missing: statement | Show results with:statement
[16]
Logarithmic Integral -- from Wolfram MathWorld
The logarithmic integral defined in this way is implemented in the Wolfram Language as LogIntegral[x]. is Soldner's constant (Edwards 2001, p. 34).
[17]
The origin of the logarithmic integral in the prime number theorem
Sep 30, 2013 · We establish why li(x) outperforms x/log x as an estimate for the prime counting function pi(x). The result follows from subdividing the natural numbers into ...
[18]
[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)}.
[19]
[PDF] euler and the partial sums of the prime harmonic series - Paul Pollack
Abstract. In a 1737 paper, Euler gave the first proof that the sum of the reciprocals of the prime numbers diverges. That paper can be considered as.
[20]
[PDF] A History of the Prime Number Theorem Author(s): L. J. Goldstein ...
We shall see below that Gauss anticipated what is known as the "Riemann hypothesis." Another feature of Gauss' letter is that he casts doubt on Legendre's.
[21]
[PDF] arXiv:2111.12551v1 [math.HO] 23 Nov 2021
Nov 23, 2021 · We survey briefly the life and work of P. L. Chebyshev, and his ongo- ing influence. We discuss his contributions to probability, number theory.
[22]
[PDF] chebyshev's theorem and bertrand's postulate - Williams College
Sep 25, 2019 · In 1845, Joseph Bertrand conjectured that there's always a prime between n and 2n for any integer n > 1. This was proved less than a decade ...
[23]
[PDF] On the Number of Prime Numbers less than a Given Quantity ...
(Ueber die Anzahl der Primzahlen unter einer gegebenen Grösse.) Bernhard Riemann. [Monatsberichte der Berliner Akademie,. November 1859.] Translated by David ...Missing: source | Show results with:source
[24]
THEORY OF PRIME NUMBERS. - Project Euclid
We proceed to prove that I' does not involve any operator whose order exceeds pmi whenever G does not involve more than p invariants which are equal to the ...
[25]
Sur la distribution des zéros de la fonction $\zeta (s)$ et ... - Numdam
Sur la distribution des zéros de la fonction ζ ( s ) et ses conséquences arithmétiques. Hadamard, J. Bulletin de la Société Mathématique de France, Tome 24 ( ...
[26]
the wiener–ikehara theorem by complex analysis
Aug 12, 2005 · The Tauberian theorem of Wiener and Ikehara provides the most direct way to the prime number theorem. Here it is shown how Newman's contour ...
[27]
The Distribution of Prime Numbers - Cambridge University Press
30-day returnsOriginally published in 1934 in the Cambridge Tracts this volume presents the theory of the distribution of the prime numbers in the series of natural numbers.
[28]
The distribution of prime numbers : Ingham, A. E. (Albert Edward)
Feb 27, 2023 · The distribution of prime numbers ; Publication date: 1964 ; Topics: Numbers, Prime, Functions, Zeta ; Publisher: New York, Stechert-Hafner Service ...
[29]
[PDF] Euler and the Zeta Function - Mathematics
Here for the first time he proved the famous Euler product decomposition in the form. 2s. 3s 5s 7s i f.. (2s 1)(3s 1)(5s -l)(7si 1)(1 l 1). One of his ...
[30]
[PDF] Sketch of the Riemann-von Mangoldt explicit formula
Formula does not yield a Prime Number Theorem, despite giving a precise relationship between primes and zeros of zeta. The idea is that the equality of the ...
[31]
[PDF] Analytic Number Theory - Lecture Notes - UC Berkeley math
We now prove Perron's formula for D(s) = 1. Consider the following contour, the Bronwich contour. Suppose first that x > 1. Then on Γ1 we have |x|s > ...
[32]
An Elementary Proof of the Prime-Number Theorem - jstor
ANNALS OF MATHEMATICS. Vol. 50, No. 2, April, 1949. AN ELEMENTARY PROOF OF THE PRIME-NUMBER THEOREM. ATLE SELBERG. (Received October 14, 1948). 1. Introduction.
[33]
[PDF] Nonvanishing of Dirichlet L-functions at s=1
NONVANISHING OF DIRICHLET L-FUNCTIONS AT s = 1. In the proof of Dirichlet's ... • The Dirichlet series D(s) converges on Re(s) > 1 to a function g(s) such.
[34]
[PDF] Chapter 7 The Prime number theorem for arithmetic progressions
We denote by π(x) the number of primes ⩽ x. We prove the Prime Number Theo- rem. Theorem 7.1. We have π(x) ∼ x log x.
[35]
None
- **Definition of Zeta Function for F_q[t]:** Defined for Re(s) > 1 as ζ_q(s) = Σ (1/|f|^s) over all non-zero monic f ∈ F_q[t].
[36]
DLMF: §27.12 Asymptotic Formulas: Primes ‣ Multiplicative Number ...
§27.12 Asymptotic Formulas: Primes ... p n is the n th prime, beginning with p 1 = 2 . π ⁡ ( x ) is the number of primes less than or equal to x . ... where the ...
[37]
[2411.13791] Zero-density estimates and the optimality of the error ...
Nov 21, 2024 · Zero-density estimates and the optimality of the error term in the prime number theorem. Authors:Daniel R. Johnston.
[38]
[PDF] The Prime Number Theorem - Uni Ulm
Jul 5, 2013 · In his paper he also proposed the study of the Zeta Function by means of complex analysis. Another important discovery on the way to the proof ...
[39]
Estimates of Some Functions Over Primes without R.H. - arXiv
Feb 2, 2010 · Get better effective estimates of number theory classical functions which are closely linked to zeta zeroes like psi(x), theta(x), pi(x) or the k-th prime ...
[40]
[PDF] New Estimates for the nth Prime Number
May 23, 2019 · In this paper we establish new upper and lower bounds for the nth prime number pn, which improve several existing bounds of similar shape. As ...
[41]
https://t5k.org/howmany.html
[42]
Chebyshev's Bias - Project Euclid
The title refers to the fact, noted by Chebyshev in 1853, that primes congruent to 3 modulo 4 seem to predominate over those congruent to 1.