Fact-checked by Grok 2 weeks ago

Bertrand's postulate

Bertrand's postulate is a theorem in number theory stating that for every integer n > 1, there exists at least one prime number p such that n < p < 2n.^[1] This result provides a quantitative bound on the distribution of prime numbers, ensuring that primes occur with sufficient frequency to bound the gaps between them relative to their magnitude.^[2] The postulate was conjectured in 1845 by the French mathematician Joseph Bertrand, who verified it computationally for all n < 3,000,000.^[3] It was first rigorously proved in 1852 by the Russian mathematician Pafnuty Chebyshev using analytic methods involving estimates on the prime-counting function and Chebyshev's functions \theta(x) and \psi(x).^[1] Chebyshev's proof established bounds showing \theta(x) - \theta(x/2) > 0 for x \geq 2, which implies the existence of primes in the desired interval.^[3] Later, simpler elementary proofs were developed independently by Paul Erdős in 1932 and Srinivasa Ramanujan around 1920, avoiding advanced analytic tools by using properties of binomial coefficients and the fundamental theorem of arithmetic.^[4]^[5] These proofs rely on showing that the central binomial coefficient \binom{2n}{n} cannot be divisible solely by primes less than or equal to n, forcing a prime factor in (n, 2n).^[3] Bertrand's postulate serves as an early milestone in the study of prime distribution, predating the prime number theorem by nearly half a century, and it implies that the n-th prime p_n satisfies p_{n+1} - p_n < p_n, highlighting controlled prime gaps.^[2] The theorem has practical applications in theoretical computer science, such as constructing primes for algorithms and probabilistic primality testing.^[6]

Statement and History

The Postulate

Bertrand's postulate asserts that for every integer n > 1, there exists at least one prime number p such that n < p \leq 2n.^[7] This statement is equivalent to the condition that for n > 3, there is a prime p satisfying n < p < 2n, since $2n is even and greater than 2, hence composite.^[7] The conjecture was proposed by Joseph Bertrand in 1845 based on computational evidence up to large values of n.^[7] The postulate can be verified directly for small integers n, demonstrating its validity in initial cases. For example:

n	Primes p with n < p \leq 2n
2	3
3	5
4	5, 7
5	7
6	7, 11
7	11, 13
8	11, 13
9	11, 13, 17
10	11, 13, 17, 19

These examples align with the sequence of the number of primes in (n, 2n], which begins 1, 1, 2, 1, 2, 2, 2, 3, 4, ... for n = 2, 3, \dots.^[8] Equivalent formulations include the condition that if p_k denotes the k-th prime number, then p_{k+1} < 2 p_k for all k \geq 1.^[7] Another is \pi(2n) - \pi(n) \geq 1 for all integers n \geq 2, where \pi(x) counts the number of primes less than or equal to x.^[7] The postulate provides key insight into prime distribution by guaranteeing that prime gaps are bounded above by the magnitude of the primes themselves, ensuring primes occur with sufficient frequency relative to their size.^[7]

Historical Development

In 1845, the French mathematician Joseph Bertrand formulated what is now known as Bertrand's postulate, conjecturing that for every integer n > 1, there exists at least one prime number p such that n < p < 2n.^[9] This idea emerged from Bertrand's empirical investigations into the distribution of prime numbers, where he manually verified the conjecture for all integers up to n = 3,000,000.^[3] His work built on earlier observations about prime gaps, such as those noted by Euler a century prior, but Bertrand's specific formulation provided a concrete bound on the interval guaranteeing a prime.^[9] Progress toward proving the conjecture came soon after through the efforts of the Russian mathematician Pafnuty Chebyshev. In his 1852 memoir "Mémoire sur les nombres premiers" (presented to the academy in 1850), Chebyshev established bounds on the prime-counting function \pi(x), demonstrating the existence of primes in the interval (n, 2n) for certain finite ranges of n.^[1] These bounds, involving logarithmic estimates, fell short of a complete proof but highlighted the conjecture's plausibility and influenced subsequent analytic approaches to prime distribution.^[10] Chebyshev completed the proof in 1852, rigorously establishing Bertrand's postulate for all n > 1 using advanced estimates on \pi(x) and properties of the logarithm.^[7] This result, often called the Bertrand-Chebyshev theorem, marked a pivotal milestone in number theory, transitioning the statement from an empirically supported conjecture to a proven theorem and inspiring further research into prime gaps.^[1] A notable simplification appeared in 1919 with Srinivasa Ramanujan's elegant proof, which used approximations from Stirling's formula to bound the Chebyshev function and show that there is at least one prime between x and $2x for x \geq 162 (with direct verification for smaller values).^[11] Ramanujan's approach verified the postulate and contributed to the study of the prime-counting function, leading to the concept of Ramanujan primes: the smallest prime R_n such that \pi(x) - \pi(x/2) \geq n for all x \geq R_n.^[12] This contribution underscored the postulate's deeper connections to analytic number theory by the early 20th century.^[13]

Proofs

Chebyshev's Proof

Chebyshev provided the first proof of Bertrand's postulate in his 1852 memoir, employing elementary analytic techniques to derive bounds on the prime-counting function through the Chebyshev function \theta(x) = \sum_{p \leq x} \log p, where the sum is over primes p. He established that for sufficiently large x, \theta(x) satisfies $0.921 x < \theta(x) < 1.105 x. These inequalities imply \theta(2n) - \theta(n) > 0 for large n, since \theta(2n) > 0.921 \cdot 2n = 1.842 n and \theta(n) < 1.105 n, yielding \theta(2n) - \theta(n) > 0.737 n > 0, confirming the existence of at least one prime in (n, 2n).^[14]^[1] Central to the proof is the estimation of factorials using integral approximations akin to Stirling's formula, where \log(n!) \approx n \log n - n + O(\log n). More precisely, Chebyshev bounded \log(n!) = \sum_{k=2}^n \log k by integrals: \int_1^n \log t \, dt < \log(n!) < \log n + \int_1^{n-1} \log t \, dt, yielding \log(n!) > n \log n - n + 1 and an upper bound of similar form. This relates directly to \theta(x) via the prime factorization of n!, as \log(n!) = \sum_p \log p \sum_{j \geq 1} \lfloor n / p^j \rfloor = \psi(n), where \psi(x) is the second Chebyshev function accounting for higher powers. Chebyshev obtained key inequalities by bounding these sums, such as \log((2n)!) > A \cdot 2n \log(2n) - 2n and similar upper bounds, leading to estimates on \theta(x) and \pi(x).^[14] The core argument leverages the central binomial coefficient \binom{2n}{n}, whose logarithm is \log \binom{2n}{n} = \log((2n)!) - 2 \log(n!). Using the factorial estimates, this yields a lower bound \log \binom{2n}{n} > 2n \log 2 - O(\log n), or equivalently, \binom{2n}{n} > 4^n / (c \sqrt{n}) for some constant c > 0. Assuming no prime exists in (n, 2n), the prime factors of \binom{2n}{n} are restricted to those \leq n, and the p-adic valuation v_p(\binom{2n}{n}) = \sum_{j \geq 1} (\lfloor 2n / p^j \rfloor - 2 \lfloor n / p^j \rfloor) \leq \sum_{j \geq 1} 1 for terms where p^j \leq 2n, bounded by \log(2n) / \log p. Thus, \log \binom{2n}{n} < \sum_{p \leq n} (\log(2n) / \log p) \log p = \pi(n) \log(2n). From Chebyshev's bounds on \theta(n) < 1.105 n, partial summation gives an upper bound \pi(n) < 1.105 \frac{n}{\log n} + O\left(\frac{n}{(\log n)^2}\right), so \log \binom{2n}{n} < \left(1.105 \frac{n}{\log n} + o\left(\frac{n}{\log n}\right)\right) \log(2n) \approx 1.105 n \cdot \frac{\log(2n)}{\log n}. For large n, \frac{\log(2n)}{\log n} \to 1, yielding an upper bound asymptotically less than $1.105 n, which contradicts the lower bound exceeding $1.386 n - o(n) when refined constants are applied.^[14]^[15]^[1] The proof holds for n > 160 (or more conservatively n \geq 468 in some expositions), with smaller cases verified by direct computation of primes. This approach, while involving asymptotic estimates, remains elementary as it avoids complex analysis.^[14]

Erdős's Elementary Proof

In 1932, Paul Erdős published an elementary proof of Bertrand's postulate at the age of 19, marking one of his first major contributions to number theory. The proof relies on combinatorial arguments involving the central binomial coefficient \binom{2n}{n} and basic bounds on prime exponents, avoiding any analytic tools beyond logarithms. It demonstrates that for every integer n \geq 1, there exists at least one prime p such that n < p \leq 2n, by deriving a contradiction from the assumption that no such prime exists.^[16]^[3] The core method begins with a lower bound on the binomial coefficient: \binom{2n}{n} \geq \frac{4^n}{2n+1}, obtained by summing the binomial expansion of $4^n = (1+1)^{2n} = \sum_{k=0}^{2n} \binom{2n}{k} and noting that the central term is at least as large as the average of the $2n+1 terms. Assuming no prime lies in (n, 2n], all prime factors of \binom{2n}{n} must be at most n. Erdős further classifies primes into ranges and shows that the exponent v_p(\binom{2n}{n}) vanishes for primes in (\sqrt{2n}, 2n/3] and for primes in (2n/3, n]. Specifically, for p > 2n/3, \lfloor 2n/p \rfloor = 2 and \lfloor n/p \rfloor = 1, so v_p(\binom{2n}{n}) = \sum_{k \geq 1} (\lfloor 2n/p^k \rfloor - 2 \lfloor n/p^k \rfloor) = 0. For primes in (\sqrt{2n}, 2n/3], a similar carry-over analysis in base p addition confirms v_p = 0. Thus, only primes p \leq \sqrt{2n} can divide \binom{2n}{n}.^[16]^[5] For these small primes, the exponent satisfies v_p(\binom{2n}{n}) \leq \log(2n) / \log p, implying p^{v_p(\binom{2n}{n})} \leq 2n. With at most \pi(\sqrt{2n}) < \sqrt{2n} such primes, the upper bound follows: \binom{2n}{n} \leq (2n)^{\sqrt{2n}}. Alternatively, some expositions incorporate an elementary bound on the primorial \prod_{p \leq 2n/3} p \leq 4^{2n/3}, derived from factorial estimates or induction, yielding \binom{2n}{n} \leq (2n)^{\sqrt{2n}} \cdot 4^{2n/3}. In either case, for sufficiently large n (e.g., n \geq 468), the lower bound exceeds the upper bound, yielding a contradiction. This implies \theta(2n) - \theta(n) > 0, where \theta(x) = \sum_{p \leq x} \log p, since the assumption forces all contributions to \log \binom{2n}{n} to come from primes \leq n, underestimating the true value. An elementary upper bound on \theta(x) \leq x \log 4 follows from the primorial estimate \prod_{p \leq x} p \leq 4^x.^[16]^[3]^[17] The proof's innovation lies in these sieve-like restrictions on prime contributions and the crude yet effective bounds, which echo an elementary form of Mertens' theorem without asymptotic analysis. It requires only verifying the postulate for small n < 468 (e.g., up to the prime 631), achievable by direct computation. This fully elementary approach proves the result for all n \geq 1 using no calculus beyond properties of logarithms and binomial expansions, contrasting with earlier analytic methods.^[16]^[3]

Connection to Analytic Number Theory

Relation to the Prime Number Theorem

The prime number theorem (PNT) asserts that the prime counting function satisfies \pi(x) \sim \frac{x}{\log x} as x \to \infty.^[18] This result was proved independently in 1896 by Jacques Hadamard and Charles Jean de la Vallée Poussin.^[19] The PNT provides a precise asymptotic description of the distribution of primes, far exceeding the qualitative guarantee of Bertrand's postulate. A direct consequence of the PNT is a strengthening of Bertrand's postulate: \pi(2n) - \pi(n) \sim \frac{n}{\log n} as n \to \infty, which tends to infinity and thus ensures infinitely many primes in each interval (n, 2n), rather than merely at least one.^[18] More explicitly, the asymptotic approximation yields \pi(2n) - \pi(n) \approx \frac{2n}{\log(2n)} - \frac{n}{\log n} \approx \frac{n}{\log n}.^[18] Historically, Bertrand's postulate served as an early precursor to the PNT, with Chebyshev's 1850 work establishing bounds of the form a \frac{x}{\log x} < \pi(x) < A \frac{x}{\log x} for constants a, A > 0 (specifically, a \approx 0.921 and A \approx 1.105 in his refined estimates), providing the first evidence for the logarithmic order of \pi(x).^[1] These bounds demonstrated that \pi(x) grows asymptotically like \frac{x}{\log x} if a limit exists, paving the way for the full PNT.^[1] Although Bertrand's postulate, equivalent to \pi(2n) - \pi(n) \geq 1 for n \geq 1, aligns with the prime density suggested by the PNT, it is a much weaker statement and does not imply the theorem's precise asymptotic equivalence.^[20] Instead, it merely confirms a minimal consistent density of primes without establishing the exact rate of growth.^[1]

Proofs Using Complex Analysis

Proofs of Bertrand's postulate employing complex analysis leverage the analytic properties of the Riemann zeta function \zeta(s), particularly its non-vanishing on the critical line \operatorname{Re}(s) = 1. This non-vanishing, established independently by Jacques Hadamard and Charles Jean de la Vallée Poussin in 1896, is pivotal for deriving effective asymptotic estimates for the distribution of primes that imply the postulate for sufficiently large integers.^[21]^[22] Hadamard and de la Vallée Poussin demonstrated that \zeta(s) \neq 0 for \operatorname{Re}(s) = 1 and s \neq 1, using contour integration and growth estimates for \zeta(s) in the critical strip. This result enables a zero-free region to the left of \operatorname{Re}(s) = 1, such as \operatorname{Re}(s) > 1 - \frac{c}{\log |t|} for some c > 0 and large |t| = |\operatorname{Im}(s)|, which controls the error in approximations involving primes. De la Vallée Poussin specifically obtained the bound \psi(x) = x + O\left(x \exp\left(-c \sqrt{\log x}\right)\right) for the Chebyshev function \psi(x) = \sum_{p^k \leq x} \log p, where the constant c > 0 arises from the width of this zero-free region.^[22] This error term ensures \psi(2x) - \psi(x) > 0 for large x, as the main term x dominates the oscillatory error, guaranteeing at least one prime power (and thus a prime) between x and $2x. Direct verification handles small x.^[22] A related technique employs the explicit formula for \psi(x), obtained via Perron's formula or contour integration of -\frac{\zeta'(s)}{\zeta(s)} \frac{x^s}{s} around a suitable contour enclosing the poles and zeros of \zeta(s):

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

where the sum runs over the non-trivial zeros \rho of \zeta(s). The non-vanishing on \operatorname{Re}(s) = 1 prevents zeros from contributing excessively large terms near the line, bounding the sum's magnitude by the zero-free region and yielding an error sufficient to show \psi(2x) - \psi(x) > 0 unconditionally. Under the Riemann hypothesis, the error improves to O(\sqrt{x} \log x), but the weaker unconditional bound from 1896 suffices for the postulate.^[22] These analytic proofs are non-constructive, relying on global properties of \zeta(s) like its meromorphic continuation to the complex plane and the residue theorem, rather than combinatorial constructions. They highlight the postulate's connection to the zeta function's zero distribution, explaining its validity through the balanced spacing of primes implied by analytic continuation. However, the complexity of these 1896 results contrasts with later elementary proofs, though they laid foundational insights for analytic number theory.^[21]^[22]

Generalizations

To Multiplicative Intervals

A key generalization of Bertrand's postulate extends its scope to shorter intervals of the form (n, n + n^\theta) for \theta \in (0,1), ensuring the existence of at least one prime in such intervals for sufficiently large n. This result implies that prime gaps are asymptotically smaller than n^\theta for any fixed \theta < 1, providing a bridge to denser prime distribution estimates. The theorem states that for any \theta \in (0,1), there exists an N such that for all n > N, the interval (n, n + n^\theta) contains a prime; unconditionally, this holds for \theta > 0.52, with ongoing improvements narrowing the threshold.^[23] Historically, the first unconditional proof of such a result for some \theta < 1 was given by Hoheisel in 1930, who established the existence using estimates from the zero-free region of the Riemann zeta function, achieving \theta = 1 - 1/33000 \approx 0.99997.^[23] In 1937, Ingham improved this to \theta > 5/8 by incorporating zero-density estimates for zeta function zeros, building on the prime number theorem to control error terms in the explicit formula for the prime-counting function.^[24] Subsequent refinements, such as those by Tchudakoff (1940) to \theta > 3/4 and later works, progressively lowered the bound; unconditional results for \theta > 1/2 became feasible through enhanced zero-density theorems, with the current best at \theta > 0.52 due to Runbo Li (2023) via sieve methods combined with Bombieri-Vinogradov-type theorems.^[25]^[23]^[26] Another extension concerns Ramanujan primes, which generalize Bertrand's postulate by ensuring multiple primes within multiplicative intervals of the form (n, 2n). A Ramanujan prime R_k is defined as the smallest integer such that \pi(2n) - \pi(n) \geq k for all n \geq R_k, where \pi is the prime-counting function; equivalently, these are primes p such that Bertrand's postulate holds uniformly for all intervals starting from the k-th prime up to the next. Ramanujan himself computed the first few: R_1 = 2, R_2 = 11, R_3 = 17, R_4 = 29, R_5 = 41, and proved their existence using asymptotic estimates akin to those in his proof of the original postulate. This construction highlights how the postulate scales to guarantee k primes in (n, 2n) for large enough n, with R_k \sim 2 k \log k asymptotically by the prime number theorem.^[27] Specific multiplicative intervals like (kn, (k+1)n) for fixed integers k \geq 1 represent direct analogs of Bertrand's postulate, asserting a prime in each such segment for all sufficiently large n. For k=1, this recovers the original (n, 2n). For k=2, i.e., (2n, 3n), El Bachraoui proved in 2006 that there is always at least one prime for n > 1, employing a combinatorial sieve to bound the product of primes in the interval and show it exceeds unity.^[28] Similarly, for k=3, (3n, 4n), Hanson established the result in 1973 by analyzing the product of primes up to $4n relative to factorials, yielding an elementary demonstration without analytic tools.^[25] These proofs extend up to small fixed k (e.g., k \leq 4) using similar factorial or binomial coefficient arguments, though larger k require more advanced sieves; in general, for any fixed k, the prime number theorem implies the existence for large n.^[29]

To Arithmetic Progressions

One extension of Bertrand's postulate concerns the existence of primes in arithmetic progressions within doubling intervals. Specifically, for any integers a and d > 0 with \gcd(a, d) = 1, there is at least one prime p \equiv a \pmod{d} in the interval (n, 2n) for all sufficiently large n. This follows from the prime number theorem for arithmetic progressions, which establishes that the number of such primes up to x is asymptotically \frac{1}{\phi(d)} \mathrm{li}(x), ensuring the count in (n, 2n) exceeds 1 for large n. An elementary proof of this result, building on Erdős's methods for the original postulate, was given by Moree, who showed that the bound holds with an explicit dependence on d, where the threshold n_0(d) grows with d. For fixed d, unconditional results confirm the existence, though the effective constants depend on the modulus and rely on zero-free regions for associated L-functions. For instance, in the arithmetic progression of primes congruent to 1 modulo 4, there is always such a prime in (n, 2n) for sufficiently large n. A stronger average version arises from the Bombieri-Vinogradov theorem, which implies that for moduli d \ll \sqrt{n}, the primes in (n, 2n) are equidistributed among the residue classes modulo d coprime to d, on average over such d. This provides evidence for the postulate holding simultaneously for many moduli up to nearly \sqrt{n}, though individual guarantees for large d remain conditional on stronger hypotheses like the Elliott-Halberstam conjecture.

Sylvester's Theorem

Sylvester's theorem states that for any positive integer k \geq 1 and any integer n > k, the product of the k consecutive integers n(n+1)\cdots(n+k-1) is divisible by some prime p > k. This result was established by James Joseph Sylvester in 1892 as part of his work on arithmetical series. The theorem strengthens Bertrand's postulate by ensuring not just the existence of primes in short intervals but a large prime factor in products of consecutive integers, which has broader implications for prime distribution. The original proof is elementary yet intricate, drawing on the divisibility properties of binomial coefficients \binom{n+k-1}{k} (noting that the product equals k! \binom{n+k-1}{k}) and bounds on the prime factors of factorials to show that no such product can avoid a prime divisor exceeding k. This approach is longer and more involved compared to direct elementary proofs of Bertrand's postulate, such as those by Chebyshev or Erdős. Sylvester's theorem directly implies Bertrand's postulate. Consider the specific case with starting integer n = k+1: the product (k+1)(k+2)\cdots(2k) is then divisible by a prime p > k. Since each factor in this product is at most $2k and p > k divides one of them, say m with k+1 \leq m \leq 2k, the only possible multiple of p in this range is p itself (as $2p > 2k). Thus, m = p, yielding a prime in the interval (k, 2k].

Erdős's Extensions

Paul Erdős proved several extensions related to the number of primes in doubling intervals. In particular, he showed that for n > 7, there are at least two primes in (n, 2n).^[30] More generally, Erdős established that for any positive integer k, there exists a natural number N = N(k) such that for all n > N, the interval (n, 2n) contains at least k primes. This result establishes that the number of primes in doubling intervals grows without bound, providing a qualitative strengthening of the original postulate by guaranteeing arbitrarily many primes in such intervals for sufficiently large n. The proof builds on Erdős's elementary approach from his 1932 demonstration of Bertrand's postulate, centering on the central binomial coefficient \binom{2n}{n}, which satisfies $2^{2n} / (2n+1) < \binom{2n}{n} \leq 4^n. By analyzing the prime factorization of \binom{2n}{n} using bounds from the sieve of Eratosthenes on the exponents v_p(\binom{2n}{n}) = \sum_{j \geq 1} \left( \lfloor 2n / p^j \rfloor - 2 \lfloor n / p^j \rfloor \right) \leq \lfloor 2n / (p-1) \rfloor / p^{j-1} for each prime p, Erdős derives upper limits on the contribution of small primes (p \leq n) to the size of \binom{2n}{n}. Assuming fewer than the required number of primes in (n, 2n), the product over those large primes would be insufficient to reach the lower bound on \binom{2n}{n}, leading to a contradiction. This ensures that \pi(2n) - \pi(n) exceeds any fixed k for large n. Erdős's innovations in this work included integrating upper sieve estimates, akin to those developed in collaboration with Paul Turán, to control the density of integers sieved out by small primes, thereby sharpening the bounds on prime multiplicity in intervals. Later, in joint work with Mark Kac in 1940, Erdős connected these ideas to the normal order of the number of distinct prime factors \omega(m) for integers m \leq x, showing \omega(m) \sim \log \log x on average, which ties into expectations for prime multiplicity across doubling intervals by relating local densities to global factor distributions.^[31]

Stronger Results

Early Improvements

The early improvements to Bertrand's postulate sought to guarantee the existence of primes in intervals shorter than (n, 2n), leveraging advances in analytic number theory to establish unconditional bounds of the form π(n + n^θ) - π(n) ≥ 1 for θ < 1 and sufficiently large n. These results marked a transition from elementary methods to more sophisticated techniques involving the Riemann zeta function and its zero-free regions, providing a bridge to error term estimates in the prime number theorem (PNT).^[32] In 1930, Guido Hoheisel achieved the first such unconditional result, proving that there exists θ < 1 with π(n + n^θ) - π(n) ≥ 1 for large n, specifically taking θ = 32999/33000 (or equivalently, prime gaps bounded by O(n^{1 - 1/33000})). This breakthrough relied on a zero-free region for the zeta function to the left of the critical line, yielding sublinear upper bounds on prime gaps and confirming Bertrand's postulate asymptotically with a strict improvement over the linear interval length. Hoheisel's method highlighted the connection to PNT error terms, as stronger zero-free regions directly imply smaller θ.^[33]^[34] Subsequent refinements in the 1930s further reduced θ. A. E. Ingham, in 1937, improved the exponent to θ = 5/8 + ε for any ε > 0, using enhanced estimates on the distribution of zeta zeros to bound prime gaps by O(n^{5/8 + ε}). This represented a substantial advance, halving the effective exponent from Hoheisel's near-1 value and underscoring the role of mean-value theorems for the zeta function in tightening PNT approximations. Around the same time, N. G. Tchudakoff (1936) had achieved θ = 3/4 + ε. These works collectively demonstrated how progress on zeta's zero distribution translates to explicit control over prime spacing.^[34]^[35] By the 1950s, attention turned to explicit versions with small intervals and verifiable starting points. In 1952, Jitsuro Nagura proved that for all n ≥ 25, there is at least one prime in (n, (6/5)n), a concrete strengthening of Bertrand's (n, 2n) to a 20% relative length, verified computationally for small n and analytically for larger ones using Chebyshev-type estimates. This result, while retaining θ = 1 in the asymptotic sense, offered practical utility and inspired further explicit checks, such as ensuring π(n + n^θ) - π(n) ≥ 1 for θ ≈ 0.999 with modest explicit N around 10^6 in related extensions. Nagura's approach balanced elementary sieving with PNT bounds, exemplifying how early analytic insights enabled verifiable improvements without full reliance on deep zero estimates.^[36]

Modern Bounds

In 1976, Lowell Schoenfeld established explicit bounds on the Chebyshev functions under the Riemann hypothesis, leading to the result that for all x > 2,010,760, the interval (x, x + x/16{,}597) contains at least one prime. This improvement significantly tightens the interval length relative to earlier theoretical results, relying on error terms from the prime number theorem assuming the Riemann hypothesis. Pierre Dusart provided unconditional explicit estimates for primes in short intervals. In 1999, he showed related bounds for the distribution of primes, with further refinements in subsequent works. By 2010, Dusart proved that for x \geq 396{,}738, there is at least one prime in (x, x(1 + 1/(25 \ln^2 x))). Updating these in 2016–2017, Dusart established that for x \geq 3{,}550{,}618, the interval (x, x(1 + 1/\ln^2 x)) contains a prime, and strengthened it to (x, x(1 + 1/\ln^3 x)) for x \geq 89{,}693. These results stem from precise estimates of \pi(x) and \psi(x) without assuming the Riemann hypothesis, verified computationally for the base cases. For asymptotic upper bounds on prime gaps, Baker, Harman, and Pintz (2001) proved that there exists a prime in (x - x^{0.525}, x) for sufficiently large x, implying gaps of size O(x^{0.525}). This unconditional result advances earlier exponents but remains above the square-root barrier. More recent developments include Adrian Dudek's 2016 work showing an explicit version of Ingham's theorem: for n \geq \exp(\exp(33.3)), there is a prime in (n^3, (n+1)^3). No major new explicit bounds specific to Bertrand's postulate have emerged since Dusart's 2016–2017 results, though general unconditional gap bounds near O(x^{0.5}) have been confirmed asymptotically, such as through refinements in sieve methods. A 2023 arXiv preprint generalizes related ideas to sums involving primes but does not directly improve interval guarantees for individual primes. Under the Riemann hypothesis, stronger explicit forms hold, such as \pi(x + \sqrt{x} \log x) - \pi(x) \geq 1 for x \geq 1{,}398{,}179, derived from sieve estimates and zero-free regions. However, unconditional coverage for intervals like (n^2, (n+1)^2) in Legendre's conjecture remains unsolved.

Applications

In Prime Distribution

Bertrand's postulate plays a foundational role in understanding the distribution of prime numbers, particularly as a precursor to more advanced results like the prime number theorem (PNT). The postulate guarantees at least one prime in the interval (n, 2n) for n > 1, providing a rudimentary lower bound of 1 for π(2n) - π(n), where π(x) denotes the number of primes up to x. This contrasts with the PNT, which asserts that π(x) ∼ li(x), where li(x) is the logarithmic integral, implying that li(2n) - li(n) ≈ n / \log n—a significantly stronger estimate for the density of primes in (n, 2n). The proof of the postulate by Chebyshev in 1852 was part of his broader estimates on π(x), establishing bounds such as 0.92129 \frac{x}{\log x} < π(x) < 1.10555 \frac{x}{\log x} for sufficiently large x, which served as early steps toward the PNT by demonstrating that primes are asymptotically dense in a controlled manner.^[37]^[38] In sieve theory, Bertrand's postulate provides preliminary support for methods like Brun's sieve by ensuring the existence of primes in short doubling intervals, which aids in applications such as bounding the number of primes in arithmetic progressions without depleting residue classes.^[39] The postulate also yields important implications for prime gaps, bounding the differences between consecutive primes. It implies that if p_k is the k-th prime, then the gap g_k = p_{k+1} - p_k < p_k, because otherwise the interval (p_k, 2p_k) would contain no primes, contradicting the postulate. For primes around n, this establishes an upper bound on gaps of less than n, which is weaker than the average gap of approximately \log n predicted by the PNT but provides a concrete limit contrasting with unconditional upper bounds of O(n^{0.525}), and conjectured maximal gaps of \sim (\log n)^2 (Cramér's conjecture). The Riemann hypothesis implies a stronger upper bound of O(\sqrt{n} \log n). This bound highlights the postulate's role in controlling local irregularities in prime distribution while underscoring the need for stronger results to capture average behavior.^[35] Furthermore, Bertrand's postulate contributes to bounds on the Jacobsthal function j(n), defined as the largest integer m such that there exists a sequence of m consecutive integers each sharing a common factor with n. For n the primorial, the postulate ensures the presence of primes coprime to n within doubling intervals, which limits the length of sequences fully covered by the small primes dividing n. This application connects the postulate to problems in additive number theory, where controlling such maximal coprime-free runs modulo n informs broader distribution questions. In contemporary computational efforts, the postulate facilitates verification of the PNT up to extraordinarily large scales, such as x = 10^{27}, where π(10^{27}) = 16,352,460,426,841,680,446,427,399 has been computed and compared to li(10^{27}) to confirm the asymptotic agreement within explicit error bounds. Such verifications not only test the theorem's accuracy but also refine explicit versions of prime distribution estimates.

Combinatorial Consequences

Bertrand's postulate has significant implications in combinatorial number theory, particularly in constructing partitions of initial segments of the natural numbers with specific prime-related properties. One notable consequence is that the set \{1, 2, \dots, 2k\} can be partitioned into k pairs \{a_i, b_i\} such that a_i + b_i is prime for each i = 1, \dots, k. This result follows directly from the postulate, as it guarantees the existence of sufficiently many primes to pair with the odds and evens in a way that their sums are odd primes.^[40] Such partitions demonstrate how primes can "cover" sumsets in discrete structures, providing a foundation for studying additive properties in combinatorial settings. In the context of additive bases, this partitioning ensures that primes play a role in Goldbach-like representations within bounded intervals. This has broader implications for understanding how primes facilitate partitions in additive combinatorics, akin to bases for representing numbers via sums.^[40] Another combinatorial application arises in the study of primality around factorials. It is well-known that n! + k is composite for each k = 2, 3, \dots, n, as k divides this expression. However, Bertrand's postulate guarantees a prime in the interval (n!, 2n!]. Since $2n! < (n+1)! = (n+1) \cdot n! for all n > 1, this prime lies within (n!, (n+1)!). Thus, the postulate bounds the location of the smallest prime greater than n! to be at most $2n!, providing a concrete upper limit on the prime gap immediately following n!.^[1]

References

[1]
[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 ...Missing: history | Show results with:history
[2]
[PDF] Lecture 4: Number Theory - Harvard Mathematics Department
Bertrand's postulate assures that pn+1 − pn < pn. Goldbach. Every even integer n > 2 is a sum of two primes. The Goldbach conjecture has been verified ...<|control11|><|separator|>
[3]
[PDF] Erd˝os's proof of Bertrand's postulate - University of Notre Dame
May 1, 2015 · In 1845 Bertrand postulated that there is always a prime between n and 2n, and he verified this for n < 3 × 106. Tchebychev gave an analytic ...
[4]
[PDF] Bertrand's postulate
For every natural number n ≥ 2, Bertrand's postulate says that there is a prime between n and 2n. Bertrand checked this numerically for many values of n, ...
[5]
[PDF] Ramanujan's Proof of Bertrand's Postulate
To prove Bertrand's postulate, it suffices to show that θ(x) − θ(x/2) > 0, for any x ≥ 2. Theorem 3. For x > 1, there is at least one prime between x and 2x.
[6]
[PDF] The Weak Prime Number Theorem - UMD Computer Science
This was proven by Chebyshev (1850). Bertrand's Postulate is used in Theoretical. Computer Science since you often need to find a prime. We give two examples. 1 ...
[7]
Bertrand's Postulate -- from Wolfram MathWorld
### Summary of Bertrand's Postulate from Wolfram MathWorld
[8]
https://oeis.org/A060715
[9]
Joseph Bertrand (1822 - 1900) - Biography - MacTutor
In 1845 Bertrand conjectured that there is at least one prime between n and 2 n − 2 2n - 2 2n−2 for every n > 3 n > 3 n>3. This conjecture, similar to one ...
[10]
[PDF] CHEBYSHEV (TCHEBYCHEFF) - ON THE TOTALITY OF PRimes
the Memoir 2, Chebyshev obtains rather narrow limits for the ratio (x): which provide a proof for the famous Bertrand postulate: “If x ≥ 2, there is at ...
[11]
[PDF] A proof of Bertrand's postulate
Thus Bertrand's Postulate is proved for all values of x not less than 162; and, by actual verification, we find that it is true for smaller values. (18) ...
[12]
Ramanujan prime - PlanetMath.org
Mar 22, 2013 · These primes arise from Srinivasa Ramanujan's proof of Bertrand's postulate. The first few are 2, 11, 17, 29, 41, 47, 59, 67, 71, 97, 101 ...
[13]
[PDF] Ramanujan's Proof of Bertrand's Postulate
In 1845, Joseph Bertrand conjectured that between x and 2x, there is always a prime number for every x > 1. Chebyshev proved this in 1850, and his proof is ...
[14]
[PDF] Mémoire sur les nombres premiers - Numdam
Mémoire sur les nombres premiers. Journal de mathématiques pures et appliquées 1re série, tome 17 (1852), p. ... k nombres premiers dans les limites Ζ et L ...
[15]
[PDF] Chapter 1 Introduction to prime number theory
However, Chebyshev came rather close, by showing that there is an x0, such that for all x ⩾ x0,. 0.921 x log x. < π(x) < 1.056 x log x .
[16]
Bertrand's Postulate - Paul Ërdos' First Published Paper
The statement of the "postulate" was conjectured in 1845 by Joseph Bertrand and first proved by Pafnuty Chebyshev in 1850.Missing: citation | Show results with:citation
[17]
[PDF] Erd˝os's proof of Bertrand's postulate - Mathematics
number theorem. ... As mentioned in the introduction, a consequence of Bertrand's postulate is the appeal- ing Theorem 1.2. ... number theory related to Bertrand's ...
[18]
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.
[19]
[PDF] Newman's Short Proof of the Prime Number Theorem
The prime number theorem, that the number of primes < x is asymptotic to x/log x, was proved (independently) by Hadamard and de la Vallee Poussin in. 1896.
[20]
[PDF] Bertrand's Postulate - Rutgers University
May 14, 2021 · Bertrand's postulate: θ(x) − θ. (x. 2. ) > 0, for any x ≥ 2. Define. T ... Apostol (1976). Introduction to Analytic Number Theory. Springer ...<|control11|><|separator|>
[21]
[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 ( ...
[22]
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. Publication date: 1897. Publisher: Hayez.
[23]
[PDF] Primes in Short Intervals - Rutgers University
This result is also called Bertrand's postulate. Next we will prove Hoheisel's theorem which allows for better results and which makes a link with zero density ...
[24]
[PDF] The number of primes in short intervals and numerical ... - arXiv
unconditional result of this asymptotic formula with some θ < 1 was proved by Hoheisel [26] in 1930 with θ ⩾ 1 −. 1. 33000 . After the works of Hoheisel [26] ...
[25]
ON THE PRODUCT OF THE PRIMES - Cambridge University Press
Let B(n) denote the least common multiple of the integers 1, 2,..., n. Then B(n) <3n. Note that for a given prime p, if ap is such that pap is the ...
[26]
[PDF] Explicit Estimates in the Theory of Prime Numbers - arXiv
Nov 22, 2016 · Specifi- cally, he showed that one could take a = 0.921 and A = 1.106. ... To begin the proof of Theorem 3.1, we define the Chebyshev θ-function ...
[27]
Ramanujan Primes and Bertrand's Postulate - NASA ADS
For example, Bertrand's postulate is $R_1 = 2$. Ramanujan proved that $R_n$ exists and gave the first five values as 2, 11, 17, 29, 41.Missing: introducing | Show results with:introducing
[28]
[PDF] Primes in the Interval [2n, 3n] - m-hikari.com
El Bachraoui. School of Science and Engineering. Al Akhawayn University in ... Consequently, the prod- uct T3 of primes between 2n and 3n is greater than 1 and ...
[29]
(PDF) Primes in the interval [2n,3n] - ResearchGate
Feb 16, 2017 · In [10], Hanson has shown that there is a prime between 3n and 4n, while El Bachraoui [2] has shown that there is a prime between 2n and 3n for ...
[30]
[PDF] prime factors of arithmetic progressions and binomial coefficients
It is a generalization of Bertrand's Postulate that there is a prime among k+1,k+2,..., 2k. (Take x = k + 1.) The assumption x>k can not be removed since x ...
[31]
[PDF] Prime factors of consecutive integers
Abstract. This note contains a new algorithm for computing a function f(k) introduced by Erd˝os to measure the minimal gap size in the sequence of integers.
[32]
[PDF] An alternative proof of Sylvester's theorem and variations for more ...
Abstract: This document presents an alternative proof of Sylvester's theorem stating that ”the product of n consecutive numbers strictly greater than n is ...Missing: original | Show results with:original<|control11|><|separator|>
[33]
[PDF] Some Theorems and Applications of Ramsey Theory - UChicago Math
We present here certain theorems in Ramsey theory and some of their applications. First is Ramsey's Theorem, which concerns the existence of monochromatic ...
[34]
[PDF] Biography of Paul Erd˝os and discussion of his proof of Bertrand's ...
Sep 28, 2021 · After proving Bertrand's. Postulate, Erd˝os extended his work to prove that for n > 7, there are at least two primes p1,p2 ∈ (n,2n).
[35]
Paul Erdős and the Difference of Primes - SpringerLink
In the present work we discuss several problems concerning the difference of primes, primarily regarding the difference of consecutive primes.Missing: multiple | Show results with:multiple
[36]
[PDF] Lower bounds on maximal determinants
Sep 26, 2012 · ▻ Hoheisel (1930) showed that λ(n) nc for some c < 1. His result had c = 1 − 1/33000. ▻ Many papers improved Hoheisel's result by reducing the.<|control11|><|separator|>
[37]
[PDF] The Gap gn Between Two Consecutive Primes Satisfies gn = O(pn
Jun 7, 2020 · Among these where θ is close to 1/2 are namely from [8] θ = 7/12, Dr Brown gave an alternative proof, [5] θ = 7/12,. [12] θ = 1051/1920, [15] θ ...
[38]
[PDF] ON THE DIFFERENCE BETWEEN CONSECUTIVE PRIMES
ON THE DIFFERENCE BETWEEN CONSECUTIVE. PRIMES. By A. E. INGHAM {Cambridge). [Received 3 August 1937]. 1. LET pn denote the nth. prime, and 77(2;) ...
[39]
[PDF] Large Gaps Between Primes - University of Warwick
... 1930 by Hoheisel [49], who proved that there exists θ < 1 such that. G(x) xθ, whilst specifically obtaining the possible value θ = 1 − 1. 33000 . He achieved ...
[40]
[PDF] On The Prime Numbers In Intervals - arXiv
Jun 4, 2017 · In 2006, Mohamed El Bachraoui [1] showed that for n > 1 there is a prime number between 2n and 3n. This similar result to Bertrand's postulate ...
[41]
https://link.springer.com/content/pdf/10.1007/978-1-4684-0507-1_5.pdf
[42]
3. Prime Numbers
From. Bertrand's Postulate, there exists a prime number between pk and 2pk, in which case pk+1 < 2pk, and the result is proved. (141) It is enough to show that ...
[43]
[PDF] An upper bound in Goldbach's conjecture - Dartmouth Mathematics
To see the relevance of Bertrand's postulate to our problem, we first deal ... Either Brun's sieve or Selberg's sieve may be used to prove the estimate g(n) ...
[44]
An Introduction to Sieve Methods and Their Applications ...
The first chapter involves a nice presentation of some preliminaries, including Chebyshev's Theorem, Bertrand's postulate, and the Prime Number Theorem.
[45]
[PDF] AN UPPER BOUND ON JACOBSTHAL'S FUNCTION
We give a new computational method for calculating strong upper bounds on h(k). Letting pi be the ith prime and Pk be the product of the all primes up to pk, ...Missing: Bertrand postulate
[46]
http://dalspace.library.dal.ca/handle/10222/60524
[47]
Problems of number theory related to Bertrand's postulate
This Dirichlet condition does not imply the CB property, however ... Prime Number Theorem states that there are about K/(log K) primes less than ...
[48]
On a Theorem of Sylvester and Schur - ResearchGate
Aug 6, 2025 · Applying the Sylvester-Schur theorem, we conclude that there is a number s, m − k + 1 ≤ s ≤ m, such that P( m k ) = P(s) = p > k. Moreover, if s ...