{\huge The Amazing Zeta Code}

But can it encode itself? \vspace{.5in}

Sergei Voronin was an expert in analytic number theory, especially the Riemann zeta function. He proved a sense in which the Riemann Hypothesis ``ain't necessarily so.'' That is, he found complex analytic functions $latex {\zeta'}&fg=000000$ that obey functional equations similar to the one for $latex {\zeta}&fg=000000$, but where $latex {\zeta'}&fg=000000$ has greater deviations in the frequency of zeroes on the critical line than $latex {\zeta}&fg=000000$ can have if the hypothesis is true.

Today Ken and I want to discuss an older result of his---proved in 1975---about the Riemann zeta function that seems to be amazing.

Voronin proved that the zeta function is universal in the precise sense that it encodes all possible other functions, to any desired degree of precision. This seems like a complexity-theory result more than a number-theory result to me, and also seems like it should have complexity consequences. We share this opinion by Matthew Watkins, who maintains a page on number theory and physics: This extraordinary 1975 result receives surprisingly little coverage... He goes on to say, ``...it was difficult to find a clear and accurate statement anywhere on the WWW in March 2004.'' Let's turn now to discuss it in detail.

The Zeta Function

The zeta function is of course defined for complex numbers $latex {s}&fg=000000$ with real part greater than $latex {1}&fg=000000$ by the famous equation:

$latex \displaystyle \zeta(s) = \sum_{k=1}^{\infty} \frac{1}{n^s}. &fg=000000$

Of course the zeta function holds the key to our understanding of the distribution of the primes. The proof that it has no zeroes at $latex {1 +it}&fg=000000$ where $latex {t}&fg=000000$ is real is equivalent to the Prime Number Theorem (PNT). This is the statement that the number of primes less than $latex {x}&fg=000000$, denoted by $latex {\pi(x)}&fg=000000$, is approximately

$latex \displaystyle \mathsf{Li}(x) = \int_{2}^{x} \frac{1}{\ln t}dt \approx \frac{x}{\ln x}.&fg=000000$

$latex \displaystyle a+b, a+2b, \dots, a+mb, \dots &fg=000000$

The Amazing Property

Let $latex {U}&fg=000000$ be any compact set of complex numbers whose real parts $latex {x}&fg=000000$ satisfy $latex {\frac{1}{2} < x < 1}&fg=000000$. Because $latex {U}&fg=000000$ is closed and bounded, there exists a fixed $latex {r < \frac{1}{4}}&fg=000000$ such that $latex {\frac{3}{4} - r \leq x \leq \frac{3}{4} + r}&fg=000000$ for all $latex {z \in U}&fg=000000$ with real part $latex {x}&fg=000000$. The $latex {\frac{3}{4} - r}&fg=000000$ part can be as close as desired to the critical line $latex {x = \frac{1}{2}}&fg=000000$, but it must stay some fixed distance away.

We also need $latex {U}&fg=000000$ to have no ``holes,'' i.e., to be homeomorphic to a closed disk of radius $latex {r}&fg=000000$. Often $latex {U}&fg=000000$ is simply taken to be the disk of radius $latex {r}&fg=000000$ centered on the $latex {x}&fg=000000$-axis at $latex {\frac{3}{4}}&fg=000000$, but we'll also think of a square grid. Then Voronin proved:

Theorem 1 Given any analytic function $latex {f(z)}&fg=000000$ that is non-vanishing on $latex {U}&fg=000000$, and any $latex {\epsilon>0}&fg=000000$, we can find some real value $latex {t}&fg=000000$ such that for all $latex {z \in U}&fg=000000$,

$latex \displaystyle |\zeta(z+it)-f(z)| < \epsilon. &fg=000000$

That is, by translating $latex {U}&fg=000000$ upward by a distance of $latex {t}&fg=000000$, we find a region where $latex {\zeta}&fg=000000$ produces the same values as $latex {f}&fg=000000$ does on the original $latex {U}&fg=000000$, within a tolerance of $latex {\epsilon}&fg=000000$. Moreover, as $latex {\epsilon \longrightarrow 0}&fg=000000$ we can find more and more $latex {t}&fg=000000$'s for which the simulation is better and better. Watkins quotes this from Martin Gutzwiller's book Chaos in Classical and Quantum Mechanics (Springer-Verlag, 1990):

``Although the Riemann zeta-function is an analytic function with [a] deceptively simple definition, it keeps bouncing around almost randomly without settling down to some regular asymptotic pattern. {\sf The Riemann zeta-function displays the essence of chaos in quantum mechanics, analytically smooth, and yet seemingly unpredictable.}

In a more intuitive language, the Riemann zeta-function is capable of fitting any arbitrary smooth function over a finite disk with arbitary accuracy, and it does so with comparative ease, since it repeats the performance like a good actor infinitely many times on a designated set of stages.''

That is to say, even if we have a function $latex {g}&fg=000000$ that is analytic and nonzero on some compact region $latex {U'}&fg=000000$ well away from the critical strip, or even overlapping the critical line, we can map $latex {U'}&fg=000000$ conformally to some $latex {U}&fg=000000$ within the strip, and then $latex {\zeta}&fg=000000$ can approximate the resulting mapped function $latex {g'}&fg=000000$.

A ``Concrete'' View of the Proof

The reason we think this is relevant to complexity theory comes from a discrete explanation of how the theorem works. Given a $latex {\delta > 0}&fg=000000$, take $latex {D = 2\lfloor\frac{r}{\delta}\rfloor}&fg=000000$. Consider $latex {U}&fg=000000$ to be the $latex {D \times D}&fg=000000$ square grid centered on $latex {\frac{3}{4}}&fg=000000$ on the $latex {x}&fg=000000$-axis. We will use the $latex {D^2}&fg=000000$-many centers $latex {u}&fg=000000$ of each grid square. Note that in the leftmost grid boxes, the real part $latex {x}&fg=000000$ of $latex {u}&fg=000000$ is displaced from $latex {\frac{1}{2}}&fg=000000$ by about $latex {\frac{\delta}{2}}&fg=000000$ in addition to the fixed distance $latex {\frac{1}{4} - r}&fg=000000$ which is independent of $latex {\delta}&fg=000000$. If we really fix $latex {\delta}&fg=000000$, then we can allow the grid to extend all the way to the critical line $latex {x = \frac{1}{2}}&fg=000000$.

We also make a discrete set $latex {V}&fg=000000$ of allowed complex values $latex {v = x + iy}&fg=000000$ such that $latex {x}&fg=000000$ and $latex {y}&fg=000000$ are integral multiples of the target approximation goal $latex {\epsilon}&fg=000000$. More precisely we set $latex {E = \lceil\frac{2}{\epsilon}\rceil}&fg=000000$. Then $latex {x}&fg=000000$ and $latex {y}&fg=000000$ may have values $latex {j\frac{1}{E} + \frac{1}{2E}}&fg=000000$ for integer values $latex {j}&fg=000000$, $latex {-E^2 \leq j \leq E^2 - 1}&fg=000000$. Note that these values stay away from zero, this time by an amount that depends on $latex {\epsilon}&fg=000000$. To every grid center $latex {u}&fg=000000$, assign a value $latex {v_u}&fg=000000$ from $latex {V}&fg=000000$.

Now we could use polynomial interpolation over these $latex {D^2}&fg=000000$-many values to define an analytic function $latex {f}&fg=000000$ that has those values at those points of $latex {U}&fg=000000$, and apply Voronin's theorem to $latex {f}&fg=000000$. The way it works, however, is really the reverse: Given any $latex {f}&fg=000000$ that is analytic and non-zero on $latex {U}&fg=000000$, we observe two consequences of $latex {U}&fg=000000$ being compact:

$latex \displaystyle \begin{array}{rcl} &&(\exists \epsilon_0 > 0)(\forall z \in U): \epsilon_0 < |f(z)| < \frac{1}{\epsilon_0},\\ &&(\forall \epsilon > 0)(\exists \delta > 0)(\forall z,z' \in U): |z - z'| < \delta \implies |f(z) - f(z')| < \epsilon. \end{array} &fg=000000$

The key idea is that Leonhard Euler's product formula for $latex {\zeta(s)}&fg=000000$ enables one to do ``Zeta Interpolation'' on the resulting finite grid of values $latex {v_u}&fg=000000$. Well this could be the idea. The proof sketch given by Wikipedia seems to do the approximation more directly on $latex {f}&fg=000000$, using selections of primes and complex phase angles. It might be interesting to work it out as a discrete interpolation. Overall this shows how discrete structures emerge out of conditions in continuous mathematics such as compactness---a hallmark of what Ron Graham, Don Knuth, and Oren Patashnik promote as ``Concrete Mathematics.''

The Zeta Code

Take any string $latex {w}&fg=000000$ over some finite alphabet $latex {\Sigma}&fg=000000$. We can choose $latex {\epsilon,\delta}&fg=000000$ in some minimal manner so that the corresponding $latex {D,E,V}&fg=000000$ satisfy $latex {D \geq |w|}&fg=000000$ and $latex {|V| \geq |\Sigma|}&fg=000000$ with values spaced far enough to allow unique decoding from any $latex {\epsilon}&fg=000000$-approximation of those values. If $latex {w}&fg=000000$ is a binary string, we can take $latex {\Sigma = \{0,1\}^b}&fg=000000$ for some block length $latex {b}&fg=000000$ that optimizes the relation between $latex {D}&fg=000000$ and $latex {E}&fg=000000$. Then we can plug in the values encoding $latex {w}&fg=000000$ as the values $latex {v_u}&fg=000000$ for our grid---actually, for just one row of grid points $latex {u}&fg=000000$. It follows that we can find $latex {t}&fg=000000$ such that the values $latex {\zeta(u + it)}&fg=000000$ encode the string $latex {w}&fg=000000$. That is, rounding those values to the closest elements of $latex {V}&fg=000000$ decodes $latex {t}&fg=000000$ to yield $latex {w}&fg=000000$.

It is amazing enough that we can do this for just one row, one-dimensionally. That we can do this in two dimensions---say encoding a larger $latex {w}&fg=000000$ as a matrix and mapping blocks inside $latex {w}&fg=000000$ to single values $latex {v_u}&fg=000000$---is even more amazing. All of this gets encoded by a single numerical value $latex {t}&fg=000000$. Let's call this the Zeta Code.

Is the Zeta Code useful? We cannot expect $latex {t}&fg=000000$ to be a simple value---it must have Kolmogorov complexity at least as great as the $latex {w}&fg=000000$ it encodes. But this already speaks a connection to complexity theory. The code's performance is so good that the working $latex {t}&fg=000000$'s have positive limit density. That is, for any $latex {f}&fg=000000$ and $latex {U}&fg=000000$:

$latex \displaystyle (\forall \epsilon)(\exists \gamma)(\forall^{\infty}T)\frac{1}{T}\mu(\{t \leq T: (\forall z \in U) |\zeta(z+it) - f(z)| \leq \epsilon\}) \geq \gamma,&fg=000000$

Physician, Simulate Thyself?

Another way complex analysis could be like computational complexity is self-reference. The $latex {\zeta}&fg=000000$ function is analytic away from the unique pole at $latex {s = 1}&fg=000000$. It is non-zero away from the trivial zeroes on the negative $latex {x}&fg=000000$-axis and away from, well, the non-trivial zeroes which the Riemann Hypothesis asserts all have real part $latex {\frac{1}{2}}&fg=000000$.

Thus Voronin's theorem says that the $latex {\zeta}&fg=000000$-function on the critical strip can approximate the $latex {\zeta}&fg=000000$-function on disk-like regions sufficiently away from the critical line, to any degree of approximation. In that sense it is ``fractal.'' But can it simulate itself via the theorem within the strip, getting arbitrarily close to the critical line?

The question is equivalent to Riemann itself. For suppose the hypothesis were false. Then there would be a zero $latex {\frac{1}{2} + e_0 + i t_0}&fg=000000$ for some fixed $latex {e > 0}&fg=000000$. Now fix $latex {r}&fg=000000$ such that $latex {\frac{1}{4} - e_0 < r < \frac{1}{4}}&fg=000000$, and take $latex {U}&fg=000000$ of width $latex {r}&fg=000000$ and height $latex {t_0}&fg=000000$. This includes the zero, so the condition of Voronin's theorem does not apply. Thus if the condition applies for $latex {r}&fg=000000$ arbitrarily close to $latex {\frac{1}{4}}&fg=000000$, then Riemann must be true. The converse also holds: if Riemann is true then $latex {\zeta}&fg=000000$ is analytic arbitrarily close, and we can apply the theorem to produce infinitely many regions where $latex {\zeta}&fg=000000$ replicates itself within any desired precision.

This picture has been sharpened just this past summer in a paper by Johan Andersson, titled ``Non universality on the critical line.'' He shows that $latex {\zeta}&fg=000000$ definitely does not have analogous universal behavior on the line itself. Thus ideas of universal simulation, which we think of as Alan Turing's province, matter directly to the Riemann Hypothesis, which Turing himself worked on.

Open Problems

Can more be derived from this nexus of complexity and complex analysis? Can it help attack the Riemann Hypothesis itself?

I (Dick) find Voronin's universality theorem quite surprising. I also think that we should be able to use it to prove a lower bound on the computational complexity of computing the zeta function. One of the reasons I find this result cool is it seems to be linked---in some way---to the complexity of computing the zeta function. I cannot prove this yet, but the fact that "all'' functions are encoded should in principle yield a lower bound on the cost of evaluating the zeta function. Does anyone have an idea of how to make this precise?