Hunting Complexity in Zeta

Anatoly Karatsuba and Sergei Voronin wrote a book on Bernhard Riemann’s zeta function. The book was translated into English by Neal Koblitz in 1992. Among its special content is expanded treatment of an amazing universality theorem about the classic zeta function proved by Voronin in 1975. We covered it four years ago.

Today Ken and I take a second look and explore a possible connection to complexity theory.

Although the theorem has been known for over forty years there is more to say about it. Voronin extended it to other Dirichlet -functions in ways improved by Bhaskar Bagchi, who also proved universality for the derivative of zeta. Within the past fifteen years, Ramūnas Garunkštis wrote two papers improving the effectiveness of the bounds in the theorem, and Jörn Steuding wrote two papers bounding the density of real values such that approximates a given complex function . Both were part of a 2010 followup paper. Steuding also wrote a wonderful set of notes on the theorem. A 2011 paper by Chris King with beautiful graphic images expands a short 1994 preprint by Max See Chin Woon on how encodes universal information, an aspect highlighted in our earlier post and on Matthew Watkins’s nice page on Voronin’s theorem.

I have known about the theorem for much of this time, but just recently thought there might be some natural way to exploit it to get computational complexity information about the zeta function. Is it surprising to think of such a link? Karatsuba himself emblemizes it, because he devised the first algorithm for multiplying two -digit integers that beats the grade-school method. The study of is so rich that a wider translation of complexity aspects could have profound impact.

The Zeta Function

Recall the famous zeta function is defined for complex with real part by the summation:

And the zeta is extended to all complex numbers except at where it has a pole, via the Riemann functional equation.

The zeta function holds the secrets to the global behavior of the primes. Even the seemingly weak statement that it does not vanish on complex with is enough to prove the Prime Number Theorem. This theorem says that the number of primes less than is approximately equal to .

The critical section of the zeta function is the strip of with real part between and . The critical line is the middle part where .

The famous Riemann Hypothesis states that all complex zeroes of the zeta function lie on the critical line. This problem remains wide open, although it has been claimed many times. Even proving that no zero lies in the region with real part in seem hopeless. But we can all hope for surprises. Perhaps 2017 will be the magical year for a breakthrough, since it is prime and the only prime between 2011 and 2027.

The Zeta Function Is Universal

Let’s turn to a formal statement of Voronin’s Theorem (VT):

Theorem 1 Let there exists such that

Voronin’s book with Karatsuba starts by proving this with the natural logarithm in place of , taking the branch of that is real for real . Then is allowed to have zeroes on the disc. Antanas Laurinčikas has extended universality to some other functions besides .

Really Voronin proved even more: for every :

where is Lebesgue measure, with a similar statement for .

§

If the above statements seem a bit technical let’s try a more informal notion of what VT says. Let be some infinite binary string:

We might agree to call it “universal” provided for any finite string there is a so that

Clearly such universal strings easily exist. Even stronger we could insist that there not only be one that makes the above true, but that there are an infinite number of ‘s. Even stronger we could insist that the set

has positive lower density. That is, there is some such that for all sufficiently large , the number of in the set that occur in the interval is at least .

What VT says is essentially a modification of this simple fact about strings. The infinite string is the values of the zeta function of the form where runs over real numbers. The finite string is replaced by a smooth function defined on a fixed size disc. And exact equality becomes approximation up to some .

What is exciting is not that this is possible but that it happens for a natural and very important particular function: the zeta function. Although universality was long known as an existential phenomenon of power series in analysis, Steuding’s notes remark (emphasis ours):

The Riemann zeta-function and its relatives are so far the only known explicit examples of universal objects.

An Effective Book of Zeta?

One easy application of universality is that with positive density in the critical strip one can compute to within any in time . This is simply because one can take to be the constant function on the disk. Or one can take or for any fixed constant .

Well, just not : if could approximate arbitrarily closely in a disk centered on the real part being then by analyticity the Riemann Hypothesis would be false. One can, however, use to stand for when is given, or handle directly using in the strip. Perhaps what follows is better understood using after all, which is how Karatsuba and Voronin develop the proofs in their book.

For different constants we get different sets of such that approximates within . And we get different sets such that approximates within . Our first question is:

How do the sets relate to each other? Likewise the sets ?

Most in particular, can we “add” these sets? What we mean is that there should be an effective procedure such that given specifications for and for outputs a specifier for . The specifiers could just be members of the sets. Using enables us to do this for , though the following purpose can work with positive integers only.

Next, can we “multiply”? That is, can we find an effective procedure that given and outputs a specifier for ?

Now we can tell where this is going. We will build up arithmetical formulas and circuits for functions and using constants and gates. Given specifiers and , we want:

We will need to start with some basic functions beginning with the identity function . Our functions are formally defined on the complex disc but it is easy to represent functions on over this domain. The main limitation noted by Garunkštis is that his effectivizations for apply only to discs of small radius , but any radius seems good for encoding discrete functions.

We certainly expect to be available. The proofs of universality all work by representing as an infinite series. One can add the terms for and to get a series for . The multiplication case would then involve products of infinite series but perhaps they are well-behaved. The hardest challenge may be to make this work neatly when the tokens give only partial information about and . We may also wish to implement some recursion operations besides and . But once we have—if we have—a rich enough set of effective operations, we can program the whole panoply of computable functions into . Note that these representations are already known to exist for any ; we are just talking about how easy it is to program them.

The potential payoff is, perhaps questions about whether certain complex arithmetic functions have small circuits or formulas can be attacked via the resulting constraints on the behavior of . Ultimately what is going on is a kind of discrete programming using the prime numbers that go into product formulas for . For and arguments with there is the particularly nice summation formula

where ranges over all primes, which is then continued inside the strip. The point is that channels a “natural” way to do the programming. Lots of tools of analysis might be available for complexity questions framed this way.

Well, this might be a pipe dream—especially since we can’t yet even tell whether blows up in the kind of discs we are considering—but this is the week when Santa smokes his pipe preparing for a long journey and lots of children have dreams.

Open Problems

Does our “book of zeta” idea seem feasible to compile?