0
$\begingroup$

The Riemann Zeta Function is the analytic continuation of the following function: $$\zeta(s) = \sum_{n = 1}^\infty \frac{1}{n^s}$$ The Riemann Hypothesis states that the zeros of this in the critical strip, $0<\Re s<1$, are on the critical line $\Re s = 1/2$.

A Dirichlet Character $\chi$ is a completely multiplicative arithmetic function $\chi:\mathbb{N}\to\mathbb{C}$, such that there exists a $k\in\mathbb{N}$ such that $\chi(x+k) = \chi(x)\forall k$.

The Generalized Riemann Hypothesis defines a Dirichlet $L$-function: $$L(\chi,s) = \sum_{n = 1}^\infty \frac{\chi(n)}{n^s}$$ We can again analytically continue this, and ask if the all the zeros in the critical strip $0<\Re(z)<1$ fall on the critical line $\Re(z) = 1/2$.

I've read that there's been extensive computational searches for counterexamples to the Riemann Hypothesis. The failure of these may lead us to believe that the hypothesis is true. Of course, this isn't the only option (it could be unprovable, or the counterexamples could just be out of reach computationally).

Often, a conjecture can be thought to be true or false, even if it's unproven (such as the $P = NP$ conjecture).

My question is:

Are these conjectures widely thought to be true? Are they widely thought to be false?

This question, especially for the generalized Riemann hypothesis, has interesting computational consequences. As an example, assuming the GRH the Miller-Rabin Primality test can be made deterministic. Some computations in Sage, a CAS, can be 1000 times quicker if you assume the GRH.

So, for these computational purposes, are there "risks" with assuming the GRH?

$\endgroup$
  • $\begingroup$ The risk is that the calculation goes too slowly, in which case... you've disproven the GRH, which would be great! $\endgroup$ – Qiaochu Yuan Nov 21 '17 at 2:07
  • $\begingroup$ What is your question exactly ? Of course GRH is believed to be true and has been tested intensively for many Dirichlet characters. For more complicated L-functions I don't know, given the computation of the zeros should be quite harder. $\endgroup$ – reuns Nov 21 '17 at 2:24
  • $\begingroup$ @reuns If you had a citation for "GRH is believed to be true and has been tested a lot for many Dirichlet characters" that'd answer my question. I've been looking for such a discussion, and haven't been able to find it. $\endgroup$ – Mark Nov 21 '17 at 2:25
  • $\begingroup$ See things like Numerical Computations Concerning the GRH, at the end theorem 9.1 $\endgroup$ – reuns Nov 21 '17 at 2:27
  • $\begingroup$ If $\chi$ is a non-primitive character then $\chi(n) = \tilde{\chi}(n) 1_{\gcd(n,k)=1}$ where $\tilde{\chi}$ is a primitive character so that $L(s,\chi) = L(s,\tilde{\chi})\prod_{p | k} (1-\tilde{\chi}(p) p^{-s}) $ where RH is believed true for $L(s,\tilde{\chi})$ and $L(s,\chi)$ has infinitely many zeros on $\Re(s) = 0$. The functional equation for $L(s,\chi)$ has one more factor $\prod_{p | k} \frac{1-\tilde{\chi}(p) p^{-s}}{1-\tilde{\chi}(p) p^{s-1}}$. The discrete Fourier transform of $\tilde{\chi}$ is $G(\tilde{\chi}) \overline{\tilde{\chi}}$ which is true only for primitive characters. $\endgroup$ – reuns Nov 21 '17 at 2:31
0
$\begingroup$

Yes GRH is believed to be true. However, I think the question you ask at the end is more interesting.

When we say “this computation runs in time ____ assuming GRH” what we really mean is “we can prove that this computation runs in time ____ assuming GRH.”

Right now there is a fact of the mater as to if GRH is true. There is also a fact of the matter (modulo certain technicalities) as to the exact runtime of an algorithm. From the point of view of applying algorithms, it doesn’t matter if we can prove that the algorithm runs efficiently. Either it does or it doesn’t, but the discovery that it doesn’t would be such a big deal that being wrong about the algorithm wouldn’t really matter at all. Additionally, algorithms whose proven efficiency depends on a major conjecture tend to only have the potential to have long run-times in very unusual and hard to construct circumstances, as demonstrating inputs that show the algorithm is inefficient would solve a major open problem.

From a theoretical point of view this matters greatly however.

$\endgroup$
  • 1
    $\begingroup$ And GRH is true for $q,t,x$ not too large thus its consequences are true for everyday calculations. $\endgroup$ – reuns Nov 21 '17 at 2:37
  • $\begingroup$ @reuns That’s another good reason why it doesn’t matter in practice. $\endgroup$ – Stella Biderman Nov 21 '17 at 2:43

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.