10
$\begingroup$

The over ~1½ century old Riemann Hypothesis has deep implications in mathematics and a large edifice of math theory is now proved conditionally on it and numerous variants. I recently came across a reference to a conditional result in TCS based on the Riemann hypothesis. I am therefore wondering,

what are the major implications of the Riemann hypothesis in TCS?

As a start here is an example from a recent paper, Homomorphism Polynomials complete for VP by Durand, Mahajan, Malod, de Rugy-Altherre, and Saurab. From the paper's introduction:

One of the most important open questions in algebraic complexity theory is to decide whether the classes VP and VNP are distinct. These classes, first defined by Valiant in [13, 12], are the algebraic analogues of the Boolean complexity classes P and NP, and separating them is essential for separating P from NP (at least non-uniformly and assuming the generalised Riemann Hypothesis, over the field $\mathbb{C}$, [3]).

$\endgroup$
  • 3
    $\begingroup$ Well-known is that the generalized RH implies that we can derandomize the Miller-Rabin primality test. But I don't know if there is anything deeper or broader related to that. $\endgroup$ – usul Nov 29 '14 at 16:22
  • 1
    $\begingroup$ Hmm, I think there is also some relation to the problem of deterministically quickly finding a large prime (i.e. given $n$ in binary, find a prime number larger than $n$). Hope someone knowledgeable can comment. $\endgroup$ – usul Nov 29 '14 at 16:26
  • 1
    $\begingroup$ @usul RH implies that for all large $n$, there is a prime in $[n, n + n^{0.5 + o(1)}]$, which does give a somewhat non-trivial deterministic algorithm, but is very far from what we want. Moreover, we do know how to achieve the same running time without RH, see the polymath project paper arxiv.org/abs/1009.3956. I believe a better deterministic algorithm to find primes assuming RH would be a significant result. $\endgroup$ – Sasho Nikolov Nov 29 '14 at 18:59
  • $\begingroup$ Also, an extension of RH gives a good upper bound on the least prime in arithmetic progressions (see, e.g., Section 5.5.4 in shoup.net/ntb/ntb-v2.pdf). $\endgroup$ – Alex Golovnev Dec 2 '14 at 23:40
15
$\begingroup$

First, I’m not aware of any CS application of Riemann’s hypothesis as such. There are various applications of generalizations of RH.

Second, a terminological note: contrary to popular belief, there is no such thing as “the generalized Riemann hypothesis” or “the extended Riemann hypothesis”. Both of these terms are used more-or-less interchangeably in the literature as a loose denotation of any kind of generalizations of the RH to some class of $L$-functions. They have no fixed specific meaning, or at least none consistent across papers of different authors (or even different papers of the same author).

The result mentioned in the OP is based on a result of Koiran that the existential theory of $\mathbb C$ (which commonly goes under the confusing name “Hilbert’s Nullstellensatz”) is in AM, and therefore in the polynomial hierarchy. It assumes the RH for Dedekind $\zeta$-functions; specifically, it relies on an effective version of the Chebotarev density theorem.

Another class of CS applications exploit the fact that every nontrivial quadratic Dirichlet character modulo $m$ assumes $\chi(x)=-1$ for some $x=O((\log m)^2)$, originally due to Ankeny, often stated with a reference to Bach who improved the constant in the $O$-notation. It relies on the RH for $L$-functions of quadratic Dirichlet characters, which is weaker than the one for Dedekind $\zeta$-functions. (The result actually holds more generally for finite-order Hecke characters, and in full generality it needs the RH for $L$-functions of said Hecke characters, which is in fact equivalent to the RH for Dedekind $\zeta$-functions. However, the CS applications I’m aware of do not need this.) The consequences are that one can derandomize several algorithms, such as the Miller–Rabin primality testing algorithm, or the Shanks–Tonelli algorithm for computing square roots modulo primes.

As far as I know, RH is not useful to deterministically find primes in a given interval, as alluded to in a comment above. This would follow from Cramér’s conjecture or a similar bound on prime gaps, but the RH is too weak to prove such bounds (the error term in the prime number theorem is at least of order roughly $\sqrt x$ no matter what).

$\endgroup$
  • $\begingroup$ I agree the usage of GRH/ERH is not entirely consistent (and it is a terminological faux-pas to have "extended" and "generalized" mean different specific things). However, I was always taught that the GRH is the extension to $L$-functions associated to Dirichlet characters and that the ERH is the extension to $\zeta$-functions of number fields. $\endgroup$ – François G. Dorais Dec 1 '14 at 21:07
  • $\begingroup$ @François: I am also personally used to that terminology. But for example, the fairly well known book by Bach and Shallit defines it in exactly the opposite way (which incidentally contradicts Bach’s own usage in his “Explicit bounds...” paper). $\endgroup$ – Emil Jeřábek Dec 1 '14 at 21:15
  • $\begingroup$ Isn't FACTORING in PPA an interesting implication? arxiv.org/abs/1207.5220 $\endgroup$ – domotorp Sep 24 '18 at 13:56
  • $\begingroup$ Maybe. This is an instance of “The consequences are that one can derandomize several algorithms, such as ...” in the penultimate paragraph, and I don’t think it’s necessary to advertise my own work in the answer. $\endgroup$ – Emil Jeřábek Sep 24 '18 at 15:21
7
$\begingroup$

Assuming an extended Riemann Hypothesis, L. M. Adleman and H. W. Lenstra gave a polynomial time algorithm to find an irreducible polynomial of a desired degree over a finite field: http://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art.pdf

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.