Consequences of the Riemann hypothesis - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T09:39:24Z http://mathoverflow.net/feeds/question/17209 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/17209/consequences-of-the-riemann-hypothesis Consequences of the Riemann hypothesis Andrea Ferretti 2010-03-05T20:11:50Z 2012-11-22T06:26:39Z <p>I assume a number of results have been proven conditionally on the Riemann hypothesis, of course in number theory and maybe in other fields. What are the most relevant you know?</p> <p>It would also be nice to include consequences of the generalized Riemann hypothesis (but specify which one is assumed).</p> http://mathoverflow.net/questions/17209/consequences-of-the-riemann-hypothesis/17218#17218 Answer by Álvaro Lozano-Robledo for Consequences of the Riemann hypothesis Álvaro Lozano-Robledo 2010-03-05T20:45:55Z 2010-03-05T20:45:55Z <p>From Wikipedia's page <a href="http://en.wikipedia.org/wiki/Riemann_hypothesis#Distribution_of_prime_numbers" rel="nofollow">on the consequences of the Riemann hypothesis</a></p> <p>"Riemann's explicit formula for the number of primes less than a given number in terms of a sum over the zeros of the Riemann zeta function says that the magnitude of the oscillations of primes around their expected position is controlled by the real parts of the zeros of the zeta function. [...] the Riemann hypothesis is equivalent to the "best possible" bound for the error of the prime number theorem."</p> http://mathoverflow.net/questions/17209/consequences-of-the-riemann-hypothesis/17228#17228 Answer by Igor Pak for Consequences of the Riemann hypothesis Igor Pak 2010-03-05T21:59:08Z 2010-03-06T00:38:43Z <p>As for GRH, the prettiest one I know is <a href="http://www.ams.org/era/1997-03-15/S1079-6762-97-00031-0/S1079-6762-97-00031-0.pdf" rel="nofollow">this</a> complete solution of the <em>odd Goldbach conjecture</em> (that every number greater than 5 is a sum of 3 primes). </p> http://mathoverflow.net/questions/17209/consequences-of-the-riemann-hypothesis/17232#17232 Answer by KConrad for Consequences of the Riemann hypothesis KConrad 2010-03-05T22:17:47Z 2012-11-22T06:26:39Z <p>I gave a talk on this topic a few months ago, so I assembled a list then which could be appreciated by a general mathematical audience. I'll reproduce it here. </p> <p>Let's start with three applications of RH for the Riemann zeta-function only.</p> <p>a) Sharp estimates on the remainder term in the prime number theorem: $\pi(x) = {\text{Li}}(x) + O(\sqrt{x}\log x)$, where ${\text{Li}}(x)$ is the logarithmic integral (the integral from 2 to $x$ of $1/\log t$). </p> <p>b) Comparing $\pi(x)$ and ${\text{Li}}(x)$. All the numerical data shows $\pi(x)$ &lt; ${\text{Li}}(x)$, and Gauss thought this was always true, but in 1914 Littlewood used the Riemann hypothesis to show the inequality reverses infinitely often. In 1933, Skewes used RH to show the inequality reverses for some $x$ below 10^10^10^34. In 1955 Skewes unconditionally (no need for RH) showed the inequality reverses for some $x$ below 10^10^10^963. Maybe this was the first example where something was proved first assuming RH and later proved unconditionally.</p> <p>c) Gaps between primes. In 1919, Cramer showed RH implies $p_{k+1} - p_k = O(\sqrt{p_k}\log p_k)$, where $p_k$ is the $k$th prime. (A conjecture of Legendre is that there's always a prime between $n^2$ and $(n+1)^2$ -- in fact there should be <em>a lot</em> of them -- and this would imply $p_{k+1} - p_k = O(\sqrt{p_k})$. This is better than Cramer's result, so it lies deeper than a consequence of RH. Cramer also conjectured that the gap is really $O((\log p_k)^2)$.)</p> <p>Now let's move on to applications involving more zeta and $L$-functions than just the Riemann zeta-function. Note that typically we will need to assume GRH for infinitely many such functions to say anything.</p> <p>d) Chebyshev's conjecture. In 1853, Chebyshev tabulated the primes which are $1 \bmod 4$ and $3 \bmod 4$ and noticed there are always at least as many $3 \bmod 4$ primes up to $x$ as $1 \bmod 4$ primes. He conjectured this was always true and also gave an analytic sense in which there are more $3 \bmod 4$ primes: $$\lim_{x \rightarrow 1^{-}} \sum_{p \not= 2} (-1)^{(p+1)/2}x^p = \infty.$$ Here the sum runs over odd primes $p$. In 1917, Hardy-Littlewood and Landau (independently) showed this second conjecture of Chebyshev's is equivalent to GRH for the $L$-function of the nontrivial character mod 4. (In 1994, Rubinstein and Sarnak used simplicity and linear independence hypotheses on zeros of $L$-functions to say something about Chebyshev's first conjecture, but as the posted question asked only about consequences of RH and GRH, I leave the matter there and move on.)</p> <p>e) The Goldbach conjecture (1742). The "even" version says all even integers $n \geq 4$ are a sum of 2 primes, while the "odd" version says all odd integers $n \geq 7$ are a sum of 3 primes. For most mathematicians, the Goldbach conjecture is understood to mean the even version, and obviously the even version implies the odd version. There has been progress on the odd version if we assume GRH. In 1923, assuming all Dirichlet $L$-functions are nonzero in a right half-plane ${\text{Re}}(s) \geq 3/4 - \varepsilon$, where $\varepsilon$ is fixed (independent of the $L$-function), Hardy and Littlewood showed the odd Goldbach conjecture is true for all sufficiently large odd $n$. In 1937, Vinogradov proved the same result unconditionally, so he was able to remove GRH as a hypothesis. In 1997, Deshouillers, Effinger, te Riele, and Zinoviev showed the odd Goldbach conjecture is true for all odd $n \geq 7$ assuming GRH. That is, the odd Goldbach conjecture is completely settled if GRH is true. </p> <p>f) Polynomial-time primality tests. By results of Ankeny (1952) and Montgomery (1971), if GRH is true for <em>all</em> Dirichlet $L$-functions then the first nonmember of a proper subgroup of any unit group $({\mathbf Z}/m{\mathbf Z})^\times$ is $O((\log m)^2)$, where the $O$-constant is independent of $m$. In 1985, Bach showed under GRH that you take the constant to be 2. That is, each proper subgroup of $({\mathbf Z}/m{\mathbf Z})^\times$ does not contain some integer from 1 to $2(\log m)^2$. Put differently, if a subgroup contains all positive integers below $2(\log m)^2$ then the subgroup is the whole unit group mod $m$. (If instead we knew <em>all</em> Dirichlet $L$-functions have no nontrivial zeros on ${\text{Re}}(s) > 1 - \varepsilon$ then the first nonmember of any proper subgroup is $O((\log m)^{1/\varepsilon})$. Set $\varepsilon = 1/2$ to get the previous result I stated using GRH.) In 1976, Gary Miller used such results to show on GRH for <em>all</em> Dirichlet $L$-functions that there is a polynomial-time primality test. (It involved deciding if a subgroup of units is proper or not.) Shortly afterwards Solovay and Strassen described a different test along these lines using Jacobi symbols which only involved subgroups containing $-1$, so their test would "only" need GRH for Dirichlet $L$-functions of even characters in order to be a polynomial-time primality test. (Solovay and Strassen described their test only as a probabilistic test.) </p> <p>In 2002 Agrawal, Kayal, and Saxena gave an unconditional polynomial-time primality test. This is a nice example showing how GRH guides mathematicians in the direction of what should be true and then you hope to find a proof of those results by other (unconditional) methods.</p> <p>g) Euclidean rings of integers. In 1973, Weinberger showed that if GRH is true for Dedekind zeta-functions then any number field with an infinite unit group (so ignoring the rationals and imaginary quadratic fields) is Euclidean if it has class number 1. As a special case, in concrete terms, if $d$ is a positive integer which is not a perfect square then the ring ${\mathbf Z}[\sqrt{d}]$ is a unique factorization domain only if it is Euclidean. There has been progress in the direction of unconditional proofs that class number 1 implies Euclidean by Ram Murty and others, but as a striking special case let's consider ${\mathbf Z}[\sqrt{14}]$. It has class number 1 (which must have been known to Gauss in the early 19th century, in the language of quadratic forms), so it should be Euclidean. This particular real quadratic ring was first proved to be Euclidean only in 2004 (by M. Harper). So this is a ring which was known to have unique factorization for over 100 years before it was proved to be Euclidean. </p> <p>h) Artin's primitive root conjecture. In 1927, Artin conjectured that any integer $a$ which is not $\pm 1$ or a perfect square is a generator of $({\mathbf Z}/p{\mathbf Z})^\times$ for infinitely many $p$, in fact for a positive proportion of such $p$. As a special case, taking $a = 10$, this says for primes $p$ the unit fraction $1/p$ has decimal period $p-1$ for a positive proportion of $p$. (For any prime $p$, the decimal period for $1/p$ is a factor of $p-1$, so this special case is saying the largest possible choice is realized infinitely often in a precise sense; a weaker version of this special case goes back to Gauss.) In 1967, Hooley showed Artin's conjecture follows from GRH. In 1984, R. Murty and Gupta showed unconditionally that the conjecture is true for infinitely many $a$, but the proof couldn't pin down a specific $a$ for which it is true, and in 1986 Heath-Brown showed the conjecture is true for all prime values of $a$ with at most two exceptions (and surely there are no exceptions). No definite $a$ is known for which Artin's conjecture is unconditionally true.</p> <p>i) First prime in an arithmetic progression. If $\gcd(a,m) = 1$ then there are infinitely many primes $p \equiv a \bmod m$. When does the first one appear, as a function of $m$? In 1934, assuming GRH Chowla showed the first prime $p \equiv a \bmod m$ is $O(m^2(\log m)^2)$. In 1944, Linnik unconditionally showed the bound is $O(m^L)$ for some universal exponent $L$. The latest unconditional choice for $L$ (Xylouris, 2009) is $L = 5.2$.</p> <p>j) Gauss' class number problem. Gauss (1801) conjectured in the language of quadratic forms that there are only finitely many imaginary quadratic fields with class number 1. (He actually conjectured more precisely that the 9 known examples are the only ones, but for what I want to say the weaker finiteness statement is simpler.) In 1913, Gronwall showed this is true if the $L$-functions of all imaginary quadratic Dirichlet characters have no zeros in some common strip $1- \varepsilon &lt; {\text{Re}}(s) &lt; 1$. That is weaker than GRH (we only care about $L$-functions of a restricted collection of characters), but it is still an unproved condition. In 1933, Deuring and Mordell showed Gauss' conjecture is true if the ordinary RH (for Riemann zeta-function) is <em>false</em>, and then in 1934 Heilbronn showed Gauss' conjecture is true if GRH is <em>false</em> for some Dirichlet $L$-function of an imaginary quadratic character. Since Gronwall proved Gauss' conjecture is true when GRH is true for the Riemann zeta-function and the Dirichlet $L$-functions of all imaginary quadratic Dirichlet characters and Deuring--Mordell--Heilbronn proved Gauss' conjecture is true when GRH is false for at least one of those functions, Gauss' conjecture is true by baby logic. In 1935, Siegel proved Gauss' conjecture is true unconditionally, and in the 1950s and 1960s Baker, Heegner, and Stark gave separate unconditional proofs of Gauss' precise "only 9" conjecture.</p> <p>k) Missing values of a quadratic form. Lagrange (1772) showed every positive integer is a sum of four squares. However, not every integer is a sum of three squares: $x^2 + y^2 + z^2$ misses all $n \equiv 7 \bmod 8$. Legendre (1798) showed a positive integer is a sum of three squares iff it is <em>not</em> of the form $4^a(8k+7)$. This can be phrased as a local-global problem: $x^2 + y^2 + z^2 = n$ is solvable in integers iff the congruence $x^2 + y^2 + z^2 \equiv n \bmod m$ is solvable for all $m$. More generally, the same local-global phenomenon applies to the three-variable quadratic form $x^2 + y^2 + cz^2$ for all integers $c$ from 2 to 10 <em>except</em> $c = 7$ and $c = 10$. What happens for these two special values? Ramanujan looked at $c = 10$. He found 16 values of $n$ for which there is local solvability (that is, we can solve $x^2 + y^2 + 10z^2 \equiv n \bmod m$ for all $m$) but not global solvability (no integral solution for $x^2 + y^2 + 10z^2 = n$). Two additional values of $n$ were found later, and in 1990 Duke and Schulze-Pillot showed that local solvability implies global solvability except for (ineffectively) finitely many positive integers $n$. In 1997, Ono and Soundarajan showed that, under GRH, the 18 known exceptions are the only ones.</p> <p>l) Euler's convenient numbers. Euler called an integer $n \geq 1$ <em>convenient</em> if any odd integer greater than 1 that has a unique representation as $x^2 + ny^2$ in positive integers $x$ and $y$, and which moreover has $(x,ny) = 1$, is a prime number. (These numbers were convenient for Euler to use to prove certain numbers that were large in his day, like $67579 = 229^2 + 2\cdot 87^2$, are prime.) Euler found 65 convenient numbers below 10000 (the last one being 1848). In 1934, Chowla showed there are finitely many convenient numbers. In 1973, Weinberger showed there is at most one convenient number not in Euler's list, and if the $L$-functions of all quadratic Dirichlet characters satisfy GRH then Euler's list is complete. What he needed from GRH is the lack of any real zeros in the interval $(53/54,1)$.</p> http://mathoverflow.net/questions/17209/consequences-of-the-riemann-hypothesis/17241#17241 Answer by Bruce Arnold for Consequences of the Riemann hypothesis Bruce Arnold 2010-03-05T22:48:54Z 2010-03-06T00:05:57Z <p>(Jeffrey C. Lagarias) The following is equivalent to RH. Let $H_n = \sum\limits_{j=1}^n \frac{1}{j}$ be the $n$-th harmonic number. For each $n \ge 1$ $$\sum\limits_{d|n} d \le H_n + \exp (H_n) \log (H_n),$$ with equality only for $n = 1.$ (<a href="http://de.arxiv.org/abs/math.NT/0008177" rel="nofollow">An Elementary Problem Equivalent to the Riemann Hypothesis</a>. See also OEIS A057641.)</p> http://mathoverflow.net/questions/17209/consequences-of-the-riemann-hypothesis/34875#34875 Answer by Jamie Weigandt for Consequences of the Riemann hypothesis Jamie Weigandt 2010-08-08T01:09:34Z 2010-08-08T01:09:34Z <p>Many class group computations are sped up tremendously by assuming the GRH. As I understand it this is done by computing upper bounds on the discriminants of potential abelian extensions. See this survey by Odlyzko for more details</p> <p><a href="http://archive.numdam.org/ARCHIVE/JTNB/JTNB_1990__2_1/JTNB_1990__2_1_119_0/JTNB_1990__2_1_119_0.pdf" rel="nofollow">http://archive.numdam.org/ARCHIVE/JTNB/JTNB_1990__2_1/JTNB_1990__2_1_119_0/JTNB_1990__2_1_119_0.pdf</a></p> <p>This is built into SAGE.</p> <pre><code>sage: J=JonesDatabase() sage: NFs=J.unramified_outside([2,3]) sage: time RHCNs = [K.class_number(proof=False) for K in NFs] CPU times: user 7.05 s, sys: 0.07 s, total: 7.13 s Wall time: 7.15 s sage: time CNs = [K.class_number() for K in NFs] CPU times: user 20.19 s, sys: 0.24 s, total: 20.43 s Wall time: 20.96 s </code></pre> http://mathoverflow.net/questions/17209/consequences-of-the-riemann-hypothesis/105602#105602 Answer by edumaz for Consequences of the Riemann hypothesis edumaz 2012-08-27T06:15:45Z 2012-08-27T06:40:36Z <p>No. See Sci. Am. column on the May 2012 issue. And I thank KConrad for point e).</p>