Editing Prime number (section)

== Analytic properties ==
[[Analytic number theory]] studies number theory through the lens of [[continuous function]]s, [[Limit (mathematics)|limits]], [[Series (mathematics)|infinite series]], and the related mathematics of the infinite and [[infinitesimal]].

This area of study began with [[Leonhard Euler]] and his first major result, the solution to the [[Basel problem]].
The problem asked for the value of the infinite sum <math>1+\tfrac{1}{4}+\tfrac{1}{9}+\tfrac{1}{16}+\dots,</math>
which today can be recognized as the value <math>\zeta(2)</math> of the [[Riemann zeta function]]. This function is closely connected to the prime numbers and to one of the most significant unsolved problems in mathematics, the [[Riemann hypothesis]]. Euler showed that {{tmath|1= \zeta(2)=\pi^2/6 }}.<ref>{{harvnb|Sandifer|2007}}, [https://books.google.com/books?id=sohHs7ExOsYC&pg=PA205 Chapter 35, Estimating the Basel problem, pp. 205–208].</ref>
The reciprocal of this number, {{tmath|6/\pi^2}}, is the limiting probability that two random numbers selected uniformly from a large range are [[coprime integers|relatively prime]] (have no factors in common).<ref>{{cite book | last1 = Ogilvy | first1 = C.S. | author1-link = C. Stanley Ogilvy | last2 = Anderson | first2 = J.T. | isbn = 978-0-486-25778-5 | pages = 29–35 | publisher = Dover Publications Inc. | title = Excursions in Number Theory | url = https://books.google.com/books?id=efbaDLlTXvMC&pg=PA29 | year = 1988}}</ref>

The distribution of primes in the large, such as the question how many primes are smaller than a given, large threshold, is described by the [[prime number theorem]], but no efficient [[formula for primes|formula for the {{tmath|n}}-th prime]] is known. [[Dirichlet's theorem on arithmetic progressions]], in its basic form, asserts that linear polynomials
: <math>p(n) = a + bn</math>
with relatively prime integers {{tmath|a}} and {{tmath|b}} take infinitely many prime values. Stronger forms of the theorem state that the sum of the reciprocals of these prime values diverges, and that different linear polynomials with the same {{tmath|b}} have approximately the same proportions of primes.
Although conjectures have been formulated about the proportions of primes in higher-degree polynomials, they remain unproven, and it is unknown whether there exists a quadratic polynomial that (for integer arguments) is prime infinitely often.

=== Analytical proof of Euclid's theorem ===
[[Divergence of the sum of the reciprocals of the primes|Euler's proof that there are infinitely many primes]] considers the sums of [[Multiplicative inverse|reciprocals]] of primes,
: <math>\frac 1 2 + \frac 1 3 + \frac 1 5 + \frac 1 7 + \cdots + \frac 1 p.</math>

Euler showed that, for any arbitrary [[real number]] {{tmath|x}}, there exists a prime {{tmath|p}} for which this sum is greater than {{tmath|x}}.<ref>{{harvnb|Apostol|1976}}, Section 1.6, Theorem 1.13</ref> This shows that there are infinitely many primes, because if there were finitely many primes the sum would reach its maximum value at the biggest prime rather than growing past every&nbsp;{{tmath|x}}.
The growth rate of this sum is described more precisely by [[Mertens' theorems|Mertens' second theorem]].<ref>{{harvnb|Apostol|1976}}, Section 4.8, Theorem 4.12</ref> For comparison, the sum
: <math>\frac 1 {1^2} + \frac 1 {2^2} + \frac 1 {3^2} + \cdots + \frac 1 {n^2}</math>
does not grow to infinity as {{tmath|n}} goes to infinity (see the [[Basel problem]]). In this sense, prime numbers occur more often than squares of natural numbers,
although both sets are infinite.<ref name="mtb-invitation">{{cite book|title=An Invitation to Modern Number Theory|first1=Steven J.|last1=Miller|first2=Ramin|last2=Takloo-Bighash|publisher=Princeton University Press|year=2006|isbn=978-0-691-12060-7|pages=43–44|url=https://books.google.com/books?id=kLz4z8iwKiwC&pg=PA43}}</ref> [[Brun's theorem]] states that the sum of the reciprocals of [[twin prime]]s,
: <math> \left( {\frac{1}{3} + \frac{1}{5}} \right) + \left( {\frac{1}{5} + \frac{1}{7}} \right) + \left( {\frac{1}{{11}} + \frac{1}{{13}}} \right) +  \cdots, </math>
is finite. Because of Brun's theorem, it is not possible to use Euler's method to solve the [[twin prime conjecture]], that there exist infinitely many twin primes.<ref name="mtb-invitation"/>

=== Number of primes below a given bound ===
{{Main|Prime number theorem|Prime-counting function}}
[[File:Prime-counting relative error.svg|thumb|upright=1.6|The [[Approximation error|relative error]] of <math>\tfrac{n}{\log n}</math> and the logarithmic integral <math>\operatorname{Li}(n)</math> as approximations to the [[prime-counting function]]. Both relative errors decrease to zero as {{tmath|n}} grows, but the convergence to zero is much more rapid for the logarithmic integral.]]
The [[prime-counting function]] <math>\pi(n)</math> is defined as the number of primes not greater than {{tmath|n}}.<ref>{{harvnb|Crandall|Pomerance|2005}}, [https://books.google.com/books?id=RbEz-_D7sAUC&pg=PA6 p.&nbsp;6].</ref> For example, {{tmath|1= \pi(11)=5 }}, since there are five primes less than or equal to&nbsp;11. Methods such as the [[Meissel–Lehmer algorithm]] can compute exact values of <math>\pi(n)</math> faster than it would be possible to list each prime up to {{tmath|n}}.<ref>{{harvnb|Crandall|Pomerance|2005}}, [https://books.google.com/books?id=ZXjHKPS1LEAC&pg=PA152 Section 3.7, Counting primes, pp. 152–162].</ref> The [[prime number theorem]] states that <math>\pi(n)</math> is asymptotic to {{tmath| n/\log n }}, which is denoted as
: <math>\pi(n) \sim \frac{n}{\log n},</math>
and means that the ratio of <math>\pi(n)</math> to the right-hand fraction [[convergent sequence|approaches]] 1 as {{tmath|n}} grows to infinity.<ref name="cranpom10">{{harvnb|Crandall|Pomerance|2005}}, [https://books.google.com/books?id=RbEz-_D7sAUC&pg=PA10 p.&nbsp;10].</ref> This implies that the likelihood that a randomly chosen number less than {{tmath|n}} is prime is (approximately) inversely proportional to the number of digits in&nbsp;{{tmath|n}}.<ref>{{cite book|title=The Number Mysteries: A Mathematical Odyssey through Everyday Life|first=Marcus|last=du Sautoy|author-link=Marcus du Sautoy|publisher=St. Martin's Press|year=2011|isbn=978-0-230-12028-0|pages=50–52|contribution=What are the odds that your telephone number is prime?|contribution-url=https://books.google.com/books?id=snaUbkIb8SEC&pg=PA50}}</ref>
It also implies that the {{tmath|n}}th prime number is proportional to <math>n\log n</math><ref>{{harvnb|Apostol|1976}}, Section 4.6, Theorem 4.7</ref>
and therefore that the average size of a prime gap is proportional to {{tmath| \log n }}.<ref name="riesel-gaps">{{harvnb|Riesel|1994}}, "[https://books.google.com/books?id=ITvaBwAAQBAJ&pg=PA78 Large gaps between consecutive primes]", pp. 78–79.</ref>
A more accurate estimate for <math>\pi(n)</math> is given by the [[offset logarithmic integral]]<ref name="cranpom10"/>
: <math>\pi(n)\sim \operatorname{Li}(n) = \int_2^n \frac{dt}{\log t}.</math>

=== Arithmetic progressions ===
{{main|Dirichlet's theorem on arithmetic progressions|Green–Tao theorem}}
An [[arithmetic progression]] is a finite or infinite sequence of numbers such that consecutive numbers in the sequence all have the same difference.<ref>{{cite book |last1=Gelfand |first1=Israel M. |author1-link=Israel Gelfand |url=https://books.google.com/books?id=Z9z7iliyFD0C&pg=PA37 |title=Algebra |last2=Shen |first2=Alexander |publisher=Springer |year=2003 |isbn=978-0-8176-3677-7 |page=37}}</ref> This difference is called the [[Modular arithmetic|modulus]] of the progression.<ref>{{cite book|title=Fundamental Number Theory with Applications|series=Discrete Mathematics and Its Applications|first=Richard A.|last=Mollin|publisher=CRC Press|year=1997|isbn=978-0-8493-3987-5|page=76|url=https://books.google.com/books?id=Fsaa3MUUQYkC&pg=PA76}}</ref> For example,
: <math>3, 12, 21, 30, 39, ...,</math>
is an infinite arithmetic progression with modulus 9. In an arithmetic progression, all the numbers have the same remainder when divided by the modulus; in this example, the remainder is 3. Because both the modulus 9 and the remainder 3 are multiples of 3, so is every element in the sequence. Therefore, this progression contains only one prime number, 3 itself. In general, the infinite progression
: <math>a, a+q, a+2q, a+3q, \dots</math>
can have more than one prime only when its remainder {{tmath|a}} and modulus {{tmath|q}} are relatively prime. If they are relatively prime, [[Dirichlet's theorem on arithmetic progressions]] asserts that the progression contains infinitely many primes.<ref>{{harvnb|Crandall|Pomerance|2005}}, [https://books.google.com/books?id=ZXjHKPS1LEAC&pg=PA Theorem 1.1.5, p. 12].</ref>
{{Wide image|Prime numbers in arithmetic progression mod&nbsp;9 zoom in.png|815px|Primes in the arithmetic progressions modulo 9. Each row of the thin horizontal band shows one of the nine possible progressions mod 9, with prime numbers marked in red. The progressions of numbers that are 0, 3, or 6 mod 9 contain at most one prime number (the number 3); the remaining progressions of numbers that are 2, 4, 5, 7, and 8 mod 9 have infinitely many prime numbers, with similar numbers of primes in each progression.|alt=Prime numbers in arithmetic progression mod 9}}
The [[Green–Tao theorem]] shows that there are arbitrarily long finite arithmetic progressions consisting only of primes.<ref name="neale-18-47"/><ref>{{cite journal|first1=Ben|last1=Green|author1-link=Ben J. Green|first2=Terence|last2=Tao|author2-link=Terence Tao|title=The primes contain arbitrarily long arithmetic progressions|journal=[[Annals of Mathematics]]|volume=167|issue=2|year=2008|pages=481–547|doi=10.4007/annals.2008.167.481|arxiv=math.NT/0404188|s2cid=1883951}}</ref>

=== Prime values of quadratic polynomials ===
[[File:Ulam 2.png|thumb|upright=1.1|The [[Ulam spiral]]. Prime numbers (orange) cluster on some diagonals and not others. Prime values of <math>4n^2 - 2n + 41</math> are shown in blue.|alt=The Ulam spiral]]
Euler noted that the function
: <math>n^2 - n + 41</math>
yields prime numbers for {{tmath| 1\le n\le 40 }}, although composite numbers appear among its later values.<ref>{{cite book |last1=Hua |first1=L. K. |title=Additive Theory of Prime Numbers |publisher=American Mathematical Society |year=2009 |isbn=978-0-8218-4942-2 |series=Translations of Mathematical Monographs |volume=13 |location=Providence, RI |pages=176–177 |mr=0194404 |oclc=824812353 |orig-year=1965}}</ref><ref>The sequence of these primes, starting at <math>n=1</math> rather than {{tmath|1= n=0 }}, is listed by {{cite book|title=103 curiosità matematiche: Teoria dei numeri, delle cifre e delle relazioni nella matematica contemporanea|language=it|first1=Paolo Pietro|last1=Lava|first2=Giorgio|last2=Balzarotti|publisher=Ulrico Hoepli Editore S.p.A.|year=2010|isbn=978-88-203-5804-4|page=133|contribution-url=https://books.google.com/books?id=YfsSAAAAQBAJ&pg=PA133|contribution=Chapter 33. Formule fortunate}}</ref> The search for an explanation for this phenomenon led to the deep [[algebraic number theory]] of [[Heegner number]]s and the [[class number problem]].<ref>{{cite book|title=Single Digits: In Praise of Small Numbers|first=Marc|last=Chamberland|publisher=Princeton University Press|year=2015|isbn=978-1-4008-6569-7|contribution=The Heegner numbers|pages=213–215|contribution-url=https://books.google.com/books?id=n9iqBwAAQBAJ&pg=PA213}}</ref> The [[Hardy–Littlewood conjecture F]] predicts the density of primes among the values of [[quadratic polynomial]]s with integer [[coefficient]]s in terms of the logarithmic integral and the polynomial coefficients. No quadratic polynomial has been proven to take infinitely many prime values.<ref name="guy-a1">{{cite book|title=Unsolved Problems in Number Theory|series=Problem Books in Mathematics|edition=3rd|first=Richard|last=Guy|author-link=Richard K. Guy|publisher=Springer|year=2013|isbn=978-0-387-26677-0|pages=7–10|contribution-url=https://books.google.com/books?id=1BnoBwAAQBAJ&pg=PA7|contribution=A1 Prime values of quadratic functions}}</ref>

The [[Ulam spiral]]<ref>{{Cite journal |last1=Stein |first1=M.L. |last2=Ulam |first2=S.M. |last3=Wells |first3=M.B. |date=1964 |title=A Visual Display of Some Properties of the Distribution of Primes |url=https://www.jstor.org/stable/2312588 |journal=The American Mathematical Monthly |volume=71 |issue=5 |pages=516–520 |doi=10.2307/2312588|jstor=2312588 }}</ref> arranges the natural numbers in a two-dimensional grid, spiraling in concentric squares surrounding the origin with the prime numbers highlighted. Visually, the primes appear to cluster on certain diagonals and not others, suggesting that some quadratic polynomials take prime values more often than others.<ref name="guy-a1"/>

=== Zeta function and the Riemann hypothesis ===
{{Main|Riemann hypothesis}}
[[File:Riemann zeta function absolute value.png|thumb|upright=1.5|Plot of the absolute values of the zeta function, showing some of its features|alt=Plot of the absolute values of the zeta function]]
One of the most famous unsolved questions in mathematics, dating from 1859, and one of the [[Millennium Prize Problems]], is the [[Riemann hypothesis]], which asks where the [[zero of a function|zeros]] of the [[Riemann zeta function]] <math>\zeta(s)</math> are located.
This function is an [[analytic function]] on the [[complex number]]s. For complex numbers {{tmath|s}} with real part greater than one it equals both an [[series (mathematics)|infinite sum]] over all integers, and an [[infinite product]] over the prime numbers,
: <math>\zeta(s)=\sum_{n=1}^\infty \frac{1}{n^s}=\prod_{p \text{ prime}} \frac 1 {1-p^{-s}}.</math>
This equality between a sum and a product, discovered by Euler, is called an [[Euler product]].<ref>{{cite book |last=Patterson |first=S. J. |url=https://books.google.com/books?id=IdHLCgAAQBAJ&pg=PA1 |title=An introduction to the theory of the Riemann zeta-function |publisher=Cambridge University Press, Cambridge |year=1988 |isbn=978-0-521-33535-5 |series=Cambridge Studies in Advanced Mathematics |volume=14 |page=1 |doi=10.1017/CBO9780511623707 |mr=933558}}</ref> The Euler product can be derived from the fundamental theorem of arithmetic, and shows the close connection between the zeta function and the prime numbers.<ref>{{cite book | last1 = Borwein | first1 = Peter | author1-link = Peter Borwein | last2 = Choi | first2 = Stephen | last3 = Rooney | first3 = Brendan | last4 = Weirathmueller | first4 = Andrea | doi = 10.1007/978-0-387-72126-2 | isbn = 978-0-387-72125-5 | location = New York | mr = 2463715 | pages = 10–11 | publisher = Springer | series = CMS Books in Mathematics/Ouvrages de Mathématiques de la SMC | title = The Riemann hypothesis: A resource for the afficionado and virtuoso alike | url = https://books.google.com/books?id=Qm1aZA-UwX4C&pg=PA10 | year = 2008 }}</ref>
It leads to another proof that there are infinitely many primes: if there were only finitely many,
then the sum-product equality would also be valid at {{tmath|1= s=1 }}, but the sum would diverge (it is the [[Harmonic series (mathematics)|harmonic series]] {{tmath|1+\tfrac{1}{2}+\tfrac{1}{3}+\dots}}) while the product would be finite, a contradiction.<ref>{{harvnb|Sandifer|2007}}, [https://books.google.com/books?id=sohHs7ExOsYC&pg=PA191 pp. 191–193].</ref>

The Riemann hypothesis states that the [[zero of a function|zeros]] of the zeta-function are all either negative even numbers, or complex numbers with [[real part]] equal to 1/2.<ref>{{harvnb|Borwein|Choi|Rooney|Weirathmueller|2008}}, [https://books.google.com/books?id=Qm1aZA-UwX4C&pg=PA15 Conjecture 2.7 (the Riemann hypothesis), p. 15].</ref> The original proof of the [[prime number theorem]] was based on a weak form of this hypothesis, that there are no zeros with real part equal to 1,<ref>{{harvnb|Patterson|1988}}, p. 7.</ref><ref name="bcrw18">{{harvnb|Borwein|Choi|Rooney|Weirathmueller|2008}}, [https://books.google.com/books?id=Qm1aZA-UwX4C&pg=PA18 p. 18.]</ref> although other more elementary proofs have been found.<ref>{{harvnb|Nathanson|2000}}, [https://books.google.com/books?id=sE7lBwAAQBAJ&pg=PA289 Chapter 9, The prime number theorem, pp. 289–324].</ref> The prime-counting function can be expressed by [[Riemann's explicit formula]] as a sum in which each term comes from one of the zeros of the zeta function; the main term of this sum is the logarithmic integral, and the remaining terms cause the sum to fluctuate above and below the main term.<ref>{{cite journal | last = Zagier | first = Don | author-link = Don Zagier | doi = 10.1007/bf03351556 | issue = S2 | journal = [[The Mathematical Intelligencer]] | pages = 7–19 | title = The first 50 million prime numbers | volume = 1 | year = 1977| s2cid = 37866599 }} See especially pp. 14–16.</ref> In this sense, the zeros control how regularly the prime numbers are distributed. If the Riemann hypothesis is true, these fluctuations will be small, and the
[[asymptotic distribution]] of primes given by the prime number theorem will also hold over much shorter intervals (of length about the square root of {{tmath|x}} for intervals near a number {{tmath|x}}).<ref name="bcrw18"/>