Skip to main content
Theoretical Computer Science

Return to Answer

edited body
Source Link
Emil Jeřábek
Emil Jeřábek
  • 18.6k
  • 3
  • 64
  • 97

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

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 Dirichlet $L$-functions of quadratic 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).

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

Source Link
Emil Jeřábek
Emil Jeřábek
  • 18.6k
  • 3
  • 64
  • 97

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 Dirichlet $L$-functions of quadratic 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).