Generalised Riemann Hypothesis

Complex Projective 4-Space 2018-03-12

You are probably familiar with the Riemann hypothesis. This concerns the behaviour of the Riemann zeta function, which is defined on the complex plane by analytic continuation of the following series:

$\zeta(s) := \sum\limits_{n=1}^{\infty} n^{-s}$

The behaviour of the zeroes of the function outside the strip $0 < \Re(s) < 1$ is well-known: they are precisely at the even negative integers. The Riemann hypothesis states that within this strip, the only zeroes have real part exactly equal to ½. It is customary to include, at this point, an entirely gratuitous plot of the real part of the zeta function near the origin:

rzeta

Whilst interesting enough for the Clay Mathematics Institute to offer a prize of $10^6$ USD for its resolution, the generalised Riemann hypothesis has far more far-reaching implications. This states that for every Dirichlet L-function, all of its zeroes within the critical strip have real part exactly equal to ½. Since the Riemann zeta function is the simplest example of a Dirichlet L-function, the ordinary Riemann hypothesis is subsumed by the generalised Riemann hypothesis.

What is a Dirichlet L-function?

A Dirichlet L-function is specified by a positive integer k and a completely multiplicative function $\chi : \mathbb{Z} \rightarrow \mathbb{C}$ satisfying:

χ(n) = 0 if and only if gcd(n, k) ≠ 1;
Periodicity: χ(n + k) = χ(n) for all integers n;
Complete multiplicativity: χ(m) χ(n) = χ(mn) for all integers m, n.

Given such a Dirichlet character χ (there are finitely many choices, namely φ(k), for any given k), the corresponding L-function is defined as:

$L_{k, \chi}(s) := \sum\limits_{n=1}^{\infty} \chi(n) n^{-s}$

When k = 1, the unique Dirichlet character is the constant function 1, whence we recover the original Riemann hypothesis.

Knottedness is in NP, modulo GRH

This is the title of a very interesting paper by Greg Kuperberg. It has been proved that an unknotted knot diagram can be disentangled into a simple closed loop in a number of Reidemeister moves polynomial in the number of crossings in the original diagram. It follows that unknottedness is in NP, as an optimal disentangling sequence is a polynomial-time-checkable certificate of unknottedness.

Kuperberg’s paper proves that unknottedness is in co-NP, i.e. knottedness is in NP. However, the proof relies on the unproven generalised Riemann hypothesis in a very interesting way. Specifically, if the fundamental group of the complement of the knot is non-Abelian — as is the case for any non-trivial knot — then it has a non-Abelian representation over SU(2). If the generalised Riemann hypothesis holds, it is possible to find a reasonably small prime p for which there is such a modulo-p representation; in this case, the images of the generators under this representation (expressed as 2-by-2 matrices with entries modulo p) form a certificate for knottedness. It then suffices to check that they do not all commute, and that they satisfy the relations of the knot group presentation.

ab + bc + ca

Which positive integers cannot be expressed in the form ab + bc + ca, where a, b, c are positive integers? There are either 18 or 19 such numbers, the first 18 of which are enumerated in A025052:

1, 2, 4, 6, 10, 18, 22, 30, 42, 58, 70, 78, 102, 130, 190, 210, 330, 462

There may be a 19th such number, which must necessarily be greater than 10^11, and can only exist provided the generalised Riemann hypothesis is false. In particular, Jonathan Borwein proved that the existence of this 19th number requires a Dirichlet L-function to have a Siegel zero, which would contradict GRH.

The positive integers inexpressible in this form with a, b, c distinct positive integers are called idoneal numbers, and there are either 65 or 66 of them. The 65 known examples are sequence A000926:

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 12, 13, 15, 16, 18, 21, 22, 24, 25, 28, 30, 33, 37, 40, 42, 45, 48, 57, 58, 60, 70, 72, 78, 85, 88, 93, 102, 105, 112, 120, 130, 133, 165, 168, 177, 190, 210, 232, 240, 253, 273, 280, 312, 330, 345, 357, 385, 408, 462, 520, 760, 840, 1320, 1365, 1848

Idoneal numbers have an equivalent definition of being the positive integers D such that any number uniquely expressible in the form $x^2 \pm D y^2$ , with $x^2$ and $D y^2$ coprime, is necessarily either a prime, a prime power, or twice a prime power.

Deterministic Miller-Rabin

The fastest known deterministic algorithm for determining if a number is prime is AKS, which takes time $O(\log(n)^{6 + \varepsilon})$ . This is, unfortunately, rather slow.

The Miller-Rabin probabilistic test tells you whether a number is prime in time $O(\log(n)^{2 + \varepsilon})$ . If the number is prime, it correctly claims that it is prime. If it is composite, however, it can lie with probability 1/4. In practice, running this test with many randomly-chosen initial parameters will give a result with sufficiently high probability that it is useful in practice (e.g. in cryptography).

Assuming GRH, it can be shown that $2 \log(n)^2$ applications of Miller-Rabin are sufficient to guarantee primality, and therefore that there exists a deterministic algorithm with running time $O(\log(n)^{4 + \varepsilon})$ , noticeably faster than AKS. The Shanks-Tonelli algorithm for finding square-roots modulo a prime will also run deterministically in polynomial time as a result of the same idea.

Artin’s conjecture on primitive roots

This states that every integer a which is neither −1 nor a perfect square is a primitive root modulo infinitely many primes. In 1967, Hooley proved this conditional on the Generalised Riemann Hypothesis, establishing that the set of primes for which a is a primitive root has positive density (among the set of all primes).