<p>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: 
<a href="http://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art.pdf">http://www.math.leidenuniv.nl/~hwl/PUBLICATIONS/1986a/art.pdf</a></p>

CC BY-SA 3.0
2014-11-30T01:59:57.783Z
2014-11-30T01:59:57.783Z
Lin Bingkai
<p>First, I’m not aware of any CS application of Riemann’s hypothesis as such. There are various applications of <em>generalizations</em> of RH.</p>

<p>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).</p>

<p>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.</p>

<p>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.</p>

<p>As far as I know, RH is <em>not</em> 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).</p>

CC BY-SA 3.0
2014-12-01T21:07:01.680Z
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.
François G. Dorais
CC BY-SA 3.0
2014-12-01T21:15:20.263Z
@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).
Emil Jeřábek
CC BY-SA 4.0
2018-09-24T13:56:14.190Z
Isn't FACTORING in PPA an interesting implication? https://arxiv.org/abs/1207.5220
domotorp
CC BY-SA 4.0
2018-09-24T15:21:07.753Z
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.
Emil Jeřábek
CC BY-SA 3.0
2014-11-29T18:15:10.023Z
2014-11-29T18:22:15.340Z
2014-11-29T18:22:15.340Z
Emil Jeřábek
<p>The over ~1½ century old <a href="http://en.m.wikipedia.org/wiki/Riemann_hypothesis" rel="noreferrer">Riemann Hypothesis</a> 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,</p>

<blockquote>
  <p>what are the major implications of the Riemann hypothesis in TCS?</p>
</blockquote>

<p>As a start here is an example from a recent paper, <a href="http://eccc.hpi-web.de/report/2014/163/" rel="noreferrer">Homomorphism Polynomials complete for VP</a> by Durand, Mahajan, Malod, de Rugy-Altherre, and Saurab. From the paper's introduction: </p>

<blockquote>
  <p>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]).</p>
</blockquote>

CC BY-SA 3.0
2014-11-29T16:22:19.633Z
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.
usul
CC BY-SA 3.0
2014-11-29T16:26:30.697Z
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.
usul
CC BY-SA 3.0
2014-11-29T18:59:58.967Z
@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 http://arxiv.org/abs/1009.3956. I believe a better deterministic algorithm to find primes assuming RH would be a significant result.
Sasho Nikolov
CC BY-SA 3.0
2014-12-02T23:40:41.507Z
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 http://www.shoup.net/ntb/ntb-v2.pdf).
Alex Golovnev
<cc.complexity-theory><algebraic-complexity><arithmetic-circuits>
Implications of Riemann Hypothesis variants in TCS
vzn
# Implications of Riemann Hypothesis variants in TCS

(Asked by: username_0 on 2014-11-29)

The over ~1½ century old [Riemann Hypothesis](http://en.m.wikipedia.org/wiki/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](http://eccc.hpi-web.de/report/2014/163/) 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]).

**Tags:** cc.complexity-theory, algebraic-complexity, arithmetic-circuits
> **Comments:**
> **username_1**: 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.  
> **username_1**: 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.  
> **username_2**: @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 http://arxiv.org/abs/1009.3956. I believe a better deterministic algorithm to find primes assuming RH would be a significant result.  
> **username_3**: 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 http://www.shoup.net/ntb/ntb-v2.pdf).  

---

## 2 answers

### Answer by username_5 on 2014-11-29. Score: 14 | Accepted answer

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).

> **Comments:**
> **username_6**: 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.  
> **username_5**: @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).  
> **username_7**: Isn't FACTORING in PPA an interesting implication? https://arxiv.org/abs/1207.5220  
> **username_5**: 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.  

---

### Answer by username_4 on 2014-11-30. Score: 7

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>


---

