Fact-checked by Grok 2 weeks ago

Legendre's conjecture

Legendre's conjecture states that for every positive integer n, there is at least one prime number p such that n^2 < p < (n+1)^2.^[1] Proposed by the French mathematician Adrien-Marie Legendre (1752–1833) in his 1808 work Essai sur la théorie des nombres, the conjecture addresses the distribution of prime numbers within quadratic intervals.^[1] It posits that the gap between consecutive squares, which has length $2n + 1, always contains a prime, implying that prime gaps near x are bounded by O(\sqrt{x}).^[1] The conjecture remains unproven despite extensive efforts and is one of the four famous unsolved problems on prime numbers posed by Edmund Landau at the 1912 International Congress of Mathematicians.^[2] No counterexamples have been found, and computational verifications have confirmed its validity for all n up to approximately $7 \times 10^{13} as of 2024.^[3] Partial progress includes results showing that the interval always contains either a prime or a product of two primes, as established by Jingrun Chen in 1975.^[1] The conjecture's resolution would advance understanding of prime gaps and connect to broader analytic number theory.^[1]

Statement and History

Formal Statement

Legendre's conjecture asserts that for every positive integer n, there exists at least one prime number p satisfying n^2 < p < (n+1)^2.^[1] This statement is equivalent to the claim that the open interval (n^2, (n+1)^2) contains at least one prime for all positive integers n. The length of this interval is $2n + 1, which grows linearly with n, providing a sequence of intervals of increasing but controlled size where primes are hypothesized to appear.^[1] The conjecture has fundamental implications for the distribution of prime numbers, guaranteeing the presence of primes within quadratic intervals between consecutive perfect squares. This ensures that prime-free regions cannot extend indefinitely around perfect squares, bridging potential gaps in the prime sequence and contrasting with the overall thinning density of primes as numbers increase.^[1]

Origin and Development

Adrien-Marie Legendre proposed what is now known as Legendre's conjecture in the second edition of his seminal work Essai sur la théorie des nombres, published in 1808. This treatise advanced the field of number theory, particularly through Legendre's explorations of prime numbers and their properties in relation to quadratic forms and reciprocity laws. The conjecture emerged within this broader context, reflecting Legendre's efforts to understand the distribution of primes amid his investigations into arithmetic progressions and Diophantine equations. In 1912, the conjecture gained prominence when Edmund Landau highlighted it as one of four fundamental unsolved problems concerning prime numbers during his address at the International Congress of Mathematicians in Cambridge.^[4] Landau's presentation elevated Legendre's idea to a landmark status in analytic number theory, alongside the Goldbach conjecture, the twin prime conjecture, and the question of primes of the form n^2 + 1. This recognition underscored the conjecture's deep ties to the ongoing quest to characterize prime gaps and the density of primes. Despite extensive efforts over the subsequent century, Legendre's conjecture remains unproven as of 2025, preserving its place among the most enduring open problems in mathematics.^[1] It has withstood rigorous computational verification up to extraordinarily large values of n, yet no general proof has emerged, highlighting the challenges in bounding prime gaps theoretically.^[1]

Relation to Prime Gaps

Definition of Prime Gaps

In number theory, the prime gap between two consecutive prime numbers p_n and p_{n+1}, where p_n denotes the n-th prime, is defined as g_n = p_{n+1} - p_n. This difference quantifies the spacing between successive primes in the sequence of prime numbers. All prime gaps greater than 1 are even, as one of any two consecutive integers greater than 2 must be even and thus composite.^[5]^[6] The study of prime gaps emerged in the context of early investigations into the distribution of prime numbers, with roots tracing back to Euclid's proof of the infinitude of primes around 300 BCE, which implicitly demonstrated the existence of gaps by constructing a new prime beyond any finite list. Systematic analysis intensified in the 19th and early 20th centuries alongside efforts to understand prime density, including pioneering work by mathematicians like Viggo Brun on small gaps around 1915.^[7]^[8] The prime number theorem, independently proved by Jacques Hadamard and Charles Jean de la Vallée Poussin in 1896, establishes that the average length of prime gaps near a number x is asymptotically \ln x, reflecting the thinning density of primes as numbers grow larger. This average arises from the theorem's assertion that the number of primes up to x, denoted \pi(x), satisfies \pi(x) \sim x / \ln x, implying typical spacings of order \ln x.^[9]^[10] Prime gaps exhibit varied behaviors, including bounded gaps—such as those of length 2, known as twin primes, where pairs like (3, 5) or (11, 13) occur—and arbitrarily large gaps, whose existence Paul Erdős proved in 1935 by constructing sequences of composites using factorial-based sieving techniques to force extended runs without primes. These constructions show that for any positive integer k, there exist consecutive primes separated by at least k composites.^[11]^[12] Prime gaps serve as a key measure of prime scarcity across the integers, highlighting regions where primes become sparser; conjectures like Legendre's conjecture propose upper bounds on the largest such gaps within defined intervals, such as between consecutive squares.^[5] Although the prime number theorem precisely characterizes average gap sizes, it offers no control over maximal gaps, which can exceed the average by significant margins, motivating ongoing research into both upper and lower bounds on gap extremes.^[7]

Legendre's Conjecture in Terms of Gaps

Legendre's conjecture asserts the existence of at least one prime in the interval (n^2, (n+1)^2) for every positive integer n, which has length $2n + 1. In terms of prime gaps, the conjecture is equivalent to the statement that no prime gap exceeds $2n + 1 in a way that fully skips the interval (n^2, (n+1)^2). This ensures that the maximal prime gap around numbers of size x \approx n^2 is at most O(\sqrt{x}).^[3] This perspective highlights the conjecture's strength relative to earlier results on prime distribution. For instance, Bertrand's postulate guarantees a prime between m and $2m for any integer m > 1, bounding gaps to at most m around m, but Legendre's conjecture implies a tighter relative bound for large n, as the interval length $2n + 1 \approx 2\sqrt{x} for x \approx n^2 is asymptotically smaller than x itself.^[13] Thus, it posits smaller gaps in quadratic-positioned intervals compared to the linear intervals of Bertrand's postulate. The conjecture suggests that prime gaps grow slower than linearly near perfect squares, specifically o(n) in the scale of n, contrasting with known constructions of large gaps elsewhere among the primes. For example, it is established that there exist prime gaps of size \gg \log x \cdot \frac{\log \log x \cdot \log \log \log \log x}{\log \log \log x} below x.^[14] This underscores how Legendre's conjecture, if true, would enforce unusually small gaps in specific regions despite the possibility of much larger gaps in other areas. Intuitively, the conjecture guarantees primes in progressively widening intervals positioned at quadratic distances: for n=1, the interval (1,4) contains primes 2 and 3; for n=2, (4,9) contains 5 and 7; and for n=3, (9,[16](/page/16)) contains 11 and 13. As n increases, these intervals ensure at least one prime despite the sparser distribution of primes at larger scales.^[3]

Partial Results and Evidence

Theoretical Bounds

Early theoretical efforts focused on the existence of primes in linear intervals, with Bertrand conjecturing in 1845 that there is always a prime between n and $2n for n > 1, a result later proved by Chebyshev in 1852 using elementary methods involving binomial coefficients and Stirling's approximation. Chebyshev's techniques laid the groundwork for analytic approaches to prime distribution, including extensions to quadratic intervals like those in Legendre's conjecture, though initial bounds remained coarse. Significant progress toward bounding prime gaps in shorter intervals, relevant to quadratic ranges, began with Hoheisel's 1930 theorem, which established that for some small \varepsilon > 0, there exists a prime between x and x + x^{1 - \varepsilon} for sufficiently large x, marking the first proof that prime gaps are o(x).^[15] This was refined by Ingham in 1937, who used zero-density estimates for the Riemann zeta function to improve the exponent to O(x^{5/8 + \varepsilon}) for any \varepsilon > 0, providing stronger control over gaps near quadratic scales. Specific applications to Legendre's conjecture leverage these general short-interval results. The seminal work of Baker, Harman, and Pintz in 2001 demonstrated that there is a prime in the interval (x, x + x^{0.525}) for all sufficiently large x, implying a prime between n^2 and n^2 + n^{1.05} for large n, a bound close to but exceeding the conjectured length of approximately $2n.^[16] This remains a cornerstone for unconditional progress, with the best current unconditional exponent improved slightly to $0.52 by Li in 2023, yielding gaps of order O(n^{1.04}) around n^2.^[17] Under the Riemann Hypothesis (RH), sharper conditional bounds are available. Cramér's 1919 analysis shows that RH implies prime gaps bounded by O(\sqrt{x} \log x), which for intervals starting at x = n^2 translates to O(n^{1/2 + \varepsilon}) for any \varepsilon > 0, sufficient to verify Legendre's conjecture for all sufficiently large n since the required interval length is \sim 2n = O(n^1). The Siegel-Walfisz theorem, proved in the 1930s, further aids these estimates by providing uniform error terms for the prime number theorem in arithmetic progressions with moduli up to (\log x)^A for any fixed A, enabling sieve methods to rule out composite obstructions in short intervals like those between consecutive squares.^[18] No full unconditional proof exists, though conditional results under the Generalized Riemann Hypothesis (GRH) similarly confirm the conjecture via effective versions of primes in progressions. As of 2025, the best unconditional bound for general short intervals stands at \theta = 0.52, with no verified improvements closing the gap to the conjectured O(\sqrt{x}). Recent arXiv preprints, such as a 2023 attempt using Newman's simplified prime number theorem method, claim full proofs but remain unverified and unaccepted by the mathematical community.^[19]

Numerical Verification

Numerical verification of Legendre's conjecture has progressed significantly since its proposal, relying on computational methods to check for the existence of primes in the intervals (n^2, (n+1)^2) for successive values of n. Early efforts in the 19th and early 20th centuries involved manual calculations, confirming the conjecture for small n up to approximately 1000 through exhaustive prime listings in mathematical tables. With the advent of electronic computers in the mid-20th century, verifications extended to larger ranges, such as up to n = 10^6 by the 1960s using basic programming on mainframes, though specific records from this era are sparse in the literature. Modern computations employ efficient sieving algorithms to scan the target intervals without generating all primes up to (n+1)^2. The segmented sieve of Eratosthenes, adapted for large sparse intervals, is a primary method, dividing the interval of length approximately $2n into manageable blocks to identify primes or confirm their presence. Challenges arise for large n due to the growing interval size and the need to handle numbers with up to 27 digits or more, requiring optimized parallel processing to manage memory and time constraints. No counterexamples have been found in any verification effort, providing empirical support for the conjecture. Key milestones include verification up to n = 2 \times 10^9 as a byproduct of a comprehensive prime enumeration up to $4 \times 10^{18}, achieved through distributed computing in 2014. This effort utilized highly optimized sieving on clusters to catalog all primes in that range, incidentally confirming Legendre's intervals for the corresponding n. By 2025, targeted computations extended the record to n = 7 \times 10^{13} using a parallel algorithm on multi-core processors, running for several months and focusing on sub-interval prime searches to bypass full enumeration. Earlier notable advances included checks up to around $10^{12} by the early 2000s via similar sieving techniques on workstations.^[3] Further extensions face substantial computational barriers, as verifying beyond $10^{14} demands immense resources—potentially years on supercomputers—due to the quadratic growth in interval positions and linear growth in lengths. While recent accelerations like GPU implementations have been explored for prime sieving in general, they have not yet pushed Legendre-specific records significantly higher. These empirical results complement theoretical bounds but do not constitute a proof, as exhaustive verification remains infeasible for all n.

Oppermann's Conjecture

Oppermann's conjecture, proposed by Danish mathematician Ludvig Oppermann in an unpublished lecture in 1877, asserts that for every integer n \geq 1, there exists at least one prime number in the open interval (n^2 - n, n^2) and at least one prime number in the open interval (n^2, n^2 + n).^[20]^[21] This statement strengthens Legendre's conjecture, as the union of the two intervals forms (n^2 - n, n^2 + n), which for n \geq 2 lies between (n-1)^2 and (n+1)^2 and guarantees primes in the latter half of ((n-1)^2, n^2) and the former half of (n^2, (n+1)^2), thereby implying a prime between consecutive squares.^[21] By positing the existence of at least two primes—one on each side of n^2—within each quadratic block of length approximately $2n, the conjecture offers a finer-grained assertion about prime distribution near perfect squares than Legendre's broader interval requirement.^[21] The conjecture remains unproven, but extensive computational verification has confirmed it holds for all n \leq 7.05 \times 10^{13}, achieved through parallel algorithms checking for primes in the specified intervals.^[3] Partial results include upper bounds on prime gaps under the Generalized Riemann Hypothesis (GRH), which establish that gaps are O(\sqrt{x} \log x) for primes near x, providing support for the conjecture in sufficiently large intervals around squares, though not sufficient for a full proof.^[22] Additionally, the conjecture connects to Dirichlet's theorem on primes in arithmetic progressions, as the target intervals can be covered by a set of residue classes modulo small primes up to n, ensuring the existence of primes in those progressions for large enough values.^[21] As of 2025, Oppermann's conjecture continues to be an open problem, with recent research examining subsets, such as the presence of multiple primes within the intervals, but no complete resolution has been achieved.^[23]

Connections to Other Prime Problems

Legendre's conjecture forms one of the four classical problems on prime numbers posed by Edmund Landau at the 1912 International Congress of Mathematicians in Cambridge, alongside the Goldbach conjecture, the twin prime conjecture, and the conjecture that there are infinitely many primes of the form n^2 + 1.^[2] These problems, often referred to as Landau's problems, all concern the distribution and spacing of primes and remain unsolved as of 2025, highlighting the enduring challenges in analytic number theory.^[2] A significant portion of the progress toward proving Legendre's conjecture relies on conditional results assuming the Riemann Hypothesis (RH). Under RH, the error term in the prime number theorem improves to \pi(x) = \mathrm{Li}(x) + O(\sqrt{x} \log x), which facilitates stronger estimates for the number of primes in short intervals.^[24] Specifically, RH implies the existence of primes in intervals of the form [x, x + O(\sqrt{x} \log^2 x)], sufficient to establish Legendre's conjecture for sufficiently large n, as the interval between n^2 and (n+1)^2 has length $2n + 1 \sim 2\sqrt{x}.^[24] However, even under RH, a full unconditional proof of the conjecture for all n eludes mathematicians, underscoring its depth.^[25] The conjecture also intersects with modern advances in bounded prime gaps. The breakthroughs by Yitang Zhang in 2013, establishing infinitely many prime pairs with gaps at most 70 million, and subsequent refinements by James Maynard and others, reducing the bound to 246, demonstrate that small gaps occur infinitely often. Legendre's conjecture complements these results by implying that, near perfect squares x = n^2, there exists at least one prime in an interval of length less than $2\sqrt{x}, thereby bounding gaps in these specific regions and contributing to understanding maximal gap behavior around quadratic landmarks. In the broader landscape of analytic number theory, Legendre's conjecture ties into investigations of zero-free regions for the Riemann zeta function \zeta(s). Estimates on \pi(x) - \pi(y) for intervals where y - x \sim \sqrt{x} depend on the extent of these zero-free regions, as wider regions yield sharper bounds on prime counts in such short intervals. Progress in enlarging classical zero-free regions, such as those beyond \sigma > 1 - c / \log t for \mathrm{Re}(s) = \sigma > 1/2, directly influences the viability of partial results for Legendre's conjecture by enhancing control over oscillatory terms in the explicit formula for \psi(x). As of 2025, Legendre's conjecture continues to inspire research without resolution, with recent preprints on arXiv and discussions in doctoral theses focusing on conditional frameworks—often building on RH or sieve methods—but reporting no unconditional breakthroughs or resolutions.

References

[1]
Legendre's Conjecture -- from Wolfram MathWorld
Legendre's conjecture asserts that for every n there exists a prime p between n^2 and (n+1)^2 (Hardy and Wright 1979, p. 415; Ribenboim 1996, pp. 397-398).
[2]
An algorithm and computation to verify Legendre's Conjecture up to ...
Jan 24, 2024 · Legendre's conjecture claims that for every positive integer n, there exists a prime between n^2 and (n+1)^2.
[3]
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 ...
[4]
Landau's Problems -- from Wolfram MathWorld
Landau's problems are the four "unattackable" problems mentioned by Landau in the 1912 Fifth Congress of Mathematicians in Cambridge.
[5]
An algorithm and computation to verify Legendre's conjecture up to
Dec 6, 2024 · We state a general purpose algorithm for quickly finding primes in evenly divided sub-intervals. Legendre's conjecture claims that for every positive integer n ...
[6]
[PDF] Landau's problems on primes - Numdam
At the 1912 Cambridge International Congress Lan- dau listed four basic problems about primes. These problems were characterised in his speech as ...
[7]
Prime Gaps -- from Wolfram MathWorld
A prime gap of length n is a run of n-1 consecutive composite numbers between two successive primes.
[8]
The Prime Glossary: gaps between primes
- **Definition**: Prime gap is the number of composites following a prime, e.g., gaps after 2, 3, 5, and 7 are 0, 1, 1, and 3 respectively. Some authors define it as the difference between consecutive primes (one larger than this definition).
[9]
[PDF] Gaps between primes: The story so far - Paul Pollack
Sep 24, 2014 · The story behind the story. GPY, Zhang, and Maynard do not study dn directly. Rather, they study a variant of the twin prime conjecture due to.
[10]
How Can Infinitely Many Primes Be Infinitely Far Apart?
Jul 21, 2022 · A simple result about the spaces between consecutive prime numbers, called prime gaps, says something quite surprising. Among the first 10 prime ...
[11]
[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.
[12]
The Gaps Between Primes
By the prime number theorem we know there are approximately n/log(n) (natural log) primes less than n, so the "average gap" between primes less than n is log(n) ...Introduction and definition of g(n) · Table and Graph of Record Gaps
[13]
Bounded gaps between primes - Annals of Mathematics
Our method is a refinement of the recent work of Goldston, Pintz and Yıldırım on the small gaps between consecutive primes.
[14]
Large gaps between consecutive prime numbers - Terry Tao
Aug 21, 2014 · in 1997 by Pintz. Erdös listed the problem of making {c} arbitrarily large one of his favourite open problems, even offering (“somewhat rashly”, ...
[15]
[PDF] The importance of finding the upper bounds for prime gaps in order ...
In this article, we have exposed a point of view that highlights the importance of finding the upper bounds for prime gaps and therefore solving the Legendre's ...
[16]
[PDF] Large gaps between consecutive prime numbers
Aug 3, 2015 · By Kevin Ford, Ben Green, Sergei Konyagin, and Terence Tao. Abstract. Let G(X) denote the size of the largest gap between consecutive primes.
[17]
[PDF] The Gap gn Between Two Consecutive Primes Satisfies gn = O(pn
Jun 7, 2020 · Ingham [9] made a signifi- cant progress that contributed to the first solutions surrounding the problem of existence of a prime between two ...
[18]
[PDF] Two statements that are equivalent to a conjecture related to ... - arXiv
Jun 19, 2014 · The well-known Bertrand's postulate states that for every integer n > 3 there always exists a prime number p such that n < p < 2n - 2 (another.
[19]
[2308.04458] The number of primes in short intervals and numerical ...
Aug 7, 2023 · The number of primes in short intervals and numerical calculations for Harman's sieve. Authors:Runbo Li.
[20]
[PDF] Elementary Proof Of The Siegel-Walfisz Theorem - arXiv
Apr 4, 2020 · This note supplies an elementary proof of the Siegel-Walfisz theorem. 1 = x ϕ(q) log x 1 + O ϕ(q) (log x)B−1 , where B>C + 1 is an arbitrary ...Missing: Legendre | Show results with:Legendre
[21]
[2307.08725] Real exponential sums over primes and prime gaps
Jul 17, 2023 · ... primes and prime gaps. ... Legendre's conjecture about the existence of at least two primes between two consecutive squares.
[22]
A Note on Oppermann's Conjecture[v4] - Preprints.org
Oppermann's conjecture is a prominent unsolved problem in pure mathematics concerning prime gaps. Despite verification for numerous primes, a general proof ...
[23]
[PDF] Small and large gaps in the primes - Terry Tao
Apr 9, 2015 · From the pigeonhole principle, this implies that one has pn+1 − pn ≤ (1 + o(1))logX for some prime gap in [X,2X]. This pigeonhole bound was ...
[24]
A Part of Oppermann's Conjecture, Legendre's Conjecture and ...
May 14, 2025 · In this paper we discuss a part of Oppermann's Conjecture "there is at least two primes between n2-n to n2 and at least another two primes ...
[25]
[PDF] Problems of the Millennium: the Riemann Hypothesis
In an epoch-making memoir published in 1859, Riemann [Ri] obtained an ana- lytic formula for the number of primes up to a preassigned limit. This formula is.
[26]
A conditional proof of Legendre's Conjecture and Andrica's ... - arXiv
Sep 27, 2018 · Abstract:The Legendre conjecture has resisted analysis over a century, even under assumption of the Riemann Hypothesis.Missing: bounds | Show results with:bounds