How to show that the Riemann hypothesis, random walks and the Möbius function are related or even equivalent?

I was reading the paper Randomness and Pseudorandomness by Avi Wigderson, but to me the most interesting thing wasn't discussed there.


2 Answers 2


The fact that the Riemann Hypothesis and the Mobius function are related has its origin in the formula $$\frac{1}{\zeta(s)} = \sum_{n=1}^\infty \mu(n)n^{-s}.$$

The relation to random walks is that the Riemann Hypothesis implies that the cumulative sum of the Mobius function $$ M(x) =\sum_{n\le x}\mu(n)$$ has random walk-like asymptotics $M(x) = O(x^{1/2+\epsilon}).$ The naive guess is that if the Mobius function were a random walk, the order of growth would be $\sqrt{x\log\log(x)}$ (the law of iterated logarithm) so the Riemann hypothesis gets us fairly close to this.

The identity relating the zeta function and the Mobius function is straightforward and can be understood by a person without much background with little work. It has to do with Euler's identity $$ \zeta(s) = \prod_p\frac{1}{1-p^{-s}}.$$ You can find derivations of this identity in a lot of places. Basically you expand the factor in a geometric series and multiply out. The identity to the sum form $ \zeta(s) = \sum_{n=1}^\infty n^{-s}$ then follows from the fundamental theorem of arithmetic. Then if you flip over Euler's identity and multiply it out, thinking about which terms are present and whether they have plus and minus signs will lead you to the identity $$ \frac{1}{\zeta(s)} = \prod_p (1-p^{-s}) = \sum_{n=1}^\infty \mu(n) n^{-s}$$ A good for-the-layman treatment of Euler's identity as well as more advanced stuff and connections to randomness can be found in Prime Obsession by (the regrettably somewhat disgraced) Derbyshire.

But the latter fact relating the Mobius function to a random walk requires some more heavy lifting.

In brief, the $1/2$ power and the fact that the zeros have $s=1/2$ are intimately related. The origin is that cumulative functions $F(x) = \sum_{n\le x}f(n)$ are related to Dirichlet series $\tilde f (s)=\sum f(n)n^{-s}$ by a Mellin transform $$ \frac{\tilde f(s)}{s} = \int_1^\infty x^{-(s+1)}F(x)dx$$ which can then be inverted to $$ F(x) = \frac{1}{2\pi i}\int_{a-i\infty}^{a+i\infty}\frac{\tilde f(s)}{s}x^sds.$$

If you use Cauchy's theorem to do the transform integral, you will see that the poles of $\tilde f(s)$ with largest real part contribute the leading order terms in the asymptotic series for $F(x)$. Since here we have $\tilde f = \frac{1}{\zeta(s)}$ we see that, assuming the Riemann Hypothesis, the largest poles of the integrand (i.e. the zeros of the zeta function) have real part $s=1/2$ so contribute a leading term $\sim x^{1/2}$ with oscillations from the imaginary parts

This of course sweeps a lot of details under the rug, but gives a basic outline of the relationship.

To see demonstrations of these facts one can consult an introductory treatment of analytic number theory. (Notes by Hildebrand are available free online and are quite good.)


These three concepts are not equivalent as such, but there is an interesting connection.

We can think of a simple symmetric random walk on $\mathbb{Z}$ as a sequence of random variables $Z_{1},Z_{2},...$ where each $Z_{k}$ takes the value $+1$ or $-1$, each with probability $1/2$. We can then define $S_{n}=\sum_{k=1}^{n}Z_{k}$ to be the position after $n$ steps of the random walk. One can then ask about what can be said about $E(|S_{n}|)$, the expected distance of the walk from the origin after $n$ steps. As is noted in the article, $E(|S_{n}|)$ is "about $\sqrt{n}$". More precisely $$\lim_{n\rightarrow\infty}\frac{E(|S_{n}|)}{\sqrt{n}}=\sqrt{\frac{2}{\pi}}$$

In particular, we can see that $E(|S_{n}|)=O(n^{\epsilon+\frac{1}{2}})$ for any $\epsilon>0$.

How does this relate to the Riemann Hypothesis? Well there is a formulation of the Riemann Hypothesis which bares a striking resemblance to the above statement. The idea is outlined in the article in the following way. Instead of using random variables $Z_{k}$ to determine each step, use $\mu(k)$. Here $\mu$ is the Mobius function, which is defined by setting $\mu(k)=+1$ if $k$ is a product of an even number of distinct primes, $\mu(k)=-1$ if $k$ is a product of an odd number of distinct primes, and $\mu(k)=0$ otherwise. Again we can think of using $\mu$ to tell us how to walk along $\mathbb{Z}$.

Now define the Mertens function $M(n)=\sum_{k=1}^{n}\mu(k)$. This function tells us where we are after $n$ steps using this method. Note that, unlike with the random walk, this walk is deterministic so we are looking at $M(n)$ directly and not some expectation. So, as with the random walk, what can we say about $M(n)$? Well, as is hinted at in the article, it turns out that the Riemann Hypothesis is equivalent to the conjecture that $$M(n)=O(n^{\epsilon+\frac{1}{2}})$$ holds for all $\epsilon>0$. Compare this with what was said about the random walk.

  • 1
    $\begingroup$ Could you explain where the $\epsilon$ is coming from in your big Oh notation? $$\lim_{n\to\infty}\frac{E(|S_n|)}{\sqrt{n}} = \sqrt{\frac{2}{\pi}}$$ gives us that there exists an $N$ such that for all $n> N$, $$E(|S_n|) < 2\sqrt{\frac{2}{\pi}}\sqrt{n}$$ and so $E(|S_n|)=O(n^{\tfrac{1}{2}})$ $\endgroup$
    – adfriedman
    Jul 8, 2017 at 9:35
  • $\begingroup$ @adfriedman This might somewhat depend on your definition of $O$. We write $f=O(g)$ to mean that there is some absolute positive constant $C$ such that $f(n)\leqslant C\cdot g(n)$ holds for all $n$. As you mention, it can be shown that $E(|S_n|)=O(n^{\frac{1}{2}})$. However, since for all $\epsilon>0$ we have $n^{\frac{1}{2}}\leqslant n^{\epsilon+\frac{1}{2}}$, we also have $E(|S_{n}|)=O(n^{\epsilon+\frac{1}{2}})$ for any $\epsilon>0$. I admit it seems strange to look at this weaker statement, but this is done to compare with the conjecture for $M(n)$. $\endgroup$
    – JonCC
    Jul 8, 2017 at 13:35
  • $\begingroup$ I use the same definition, I guess I just tend to expect the best upper bound an author can produce unless otherwise stated, so I was concerned that I was missing something. Using it to draw a comparison makes sense. $\endgroup$
    – adfriedman
    Jul 8, 2017 at 17:22
  • $\begingroup$ @JonCC, can you please add this to your answer? $\endgroup$
    – 0x90
    Jul 9, 2017 at 0:48
  • $\begingroup$ I like the description given in the introduction to this article: faculty.math.illinois.edu/~hildebr/ugresearch/…. It asserts that we can model $M(x)$ as a $\{-1,0,1\}$-weighted random walk on the integer line whose values at each step are encoded by the number of distinct prime factors of each $n \geq 2$ -- effectively, the values of $\lambda(n)$ on the squarefree integers, which correspond to a pseudo-random "digital coin flip". Nice! $\endgroup$
    – mds
    Sep 24, 2021 at 21:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .