List of results implied by the Riemann Hypothesis

This is a partial list of potentially useful results conditional on the Riemann Hypothesis (RH) or the Generalized Riemann Hypothesis (GRH).

Conditional on RH

All of the results listed below are known to be true assuming the Riemann hypothesis. It should be stressed that none of these results are known to be true unconditionally, although weaker versions of most of them are known.

Prime gaps. Let [math]\displaystyle{ p_n }[/math] denote the nth prime. Then [math]\displaystyle{ p_{n+1}-p_n = O(\sqrt{p_n} log(p_n)) }[/math].

Primes in intervals. Related to the above result. There is always a prime in the interval [math]\displaystyle{ [n, n + O(\sqrt{n} log(n))] }[/math].

Strong-form algorithm. As a result of the above, there is an algorithm with running time [math]\displaystyle{ O(k(10^k)^{1/2}) }[/math] that locates a prime number with at least k digits (with an oracle for testing primality).

Distribution of prime logarithms. Let K be the set of logarithms of the primes in the interval [math]\displaystyle{ [S, 2S] }[/math]. Then the Fourier coefficients of K have size at most about [math]\displaystyle{ S^{-1/2} }[/math] up to logarithmic factors.

Distribution of square-free numbers. Let [math]\displaystyle{ Q(n) }[/math] be the number of square-free numbers less than or equal to n. Then [math]\displaystyle{ Q(n) - \frac{6}{\pi^2}n = O(n^{17/45 + \epsilon}) }[/math] for all [math]\displaystyle{ \epsilon \gt 0 }[/math].

Conditional on GRH

All of the results listed below are known to be true assuming the generalized Riemann hypothesis. Again, we stress that none of these results are known to be true unconditionally, nor even assuming the (standard) Riemann hypothesis.

Strong-form algorithm. It may be possible, using the W-trick, to obtain a slightly faster algorithm that locates a prime number of at least k digits than the one assuming the standard RH.

Primitive roots. Let p be an odd prime. Then the smallest primitive root (mod p) has order [math]\displaystyle{ O(log^6(p)) }[/math].

Generating the multiplicative group (mod p). Let p be an odd prime. Then the multiplicative group (mod p) [math]\displaystyle{ (Z/pZ)* }[/math] is generated by its elements of size [math]\displaystyle{ O(log^2(n)) }[/math]. If the logarithm is natural, we can take 2 as the implied constant.

Primality testing. As a result of the above, there is a deterministic polynomial-time form of the Miller-Rabin primality test. Until the AKS algorithm was discovered, this was the best known candidate for a deterministic polynomial-time algorithm to test primality.

Square roots mod p. Let p be an odd prime and n be a quadratic residue (mod p). Then the Shanks-Tonelli algorithm is a deterministic polynomial-time algorithm to compute a solution to [math]\displaystyle{ x^2 \equiv n \pmod{p} }[/math].

References

1. Bach, Eric; Shallit, Jeffrey (1996), Algorithmic Number Theory (Vol I: Efficient Algorithms), Cambridge: The MIT Press, ISBN 0-262-02045-5
2. Jia, Chao Hua. "The distribution of square-free numbers", Science in China Series A: Mathematics 36:2 (1993), pp. 154–169.