As I do more number theory, and in particular analytic number theory, I keep hearing more about the Möbius function $\mu(n)$ and how it is supposedly "pseudorandom". The values of the Möbius function at $n$ are determined by a formula, so what does this mean? Also, why is it so important that the Möbius function behaves pseudorandomly?


Just to be entirely clear, I am defining $\mu(n)$ by


\begin{equation}
\mu(n)=
\begin{cases}
(-1)^{\omega(n)}& n \,\,\mathrm{squarefree}\\
0&\mathrm{otherwise}
\end{cases}
\end{equation}


CLARIFICATION: This question was made with the intention that I would answer it myself. Any criticism, commentary, or discussion is appreciated.



What's the deal with Möbius pseudorandomness?
As you point out in your question, there is no one good way to define pseudorandomness. The first approach is to try to solidify the condition that $\mu(n)$ is "equally likely" to be $\pm1$. We do this by using the property that for any $\epsilon>0$


\begin{equation}
\left|\sum\_{n<x}X\_n\right|=O\left(x^{1/2+\epsilon}\right)\tag{1}
\end{equation}


$100\%$ of the time, where $X\_n$ are i.i.d variables that take the values $\pm1$ with probability $\frac{1}{2}$. This should mean that, if $\mu(n)$ is equally likely to be $\pm1$, then


\begin{equation}
\left|\sum\_{n<x}\mu(n)\right|=O\left(x^{1/2+\epsilon}\right)\tag{2}
\end{equation}


Generally how you will see this in literature is $|M(x)|=O\left(x^{1/2+\epsilon}\right)$, where $M(x):=\sum\_{n<x}\mu(n)$ is the Mertens function. This form of Mobius pseudorandomness is considered the most important since (2) is [equivalent to the Riemann Hypothesis (RH)](https://en.wikipedia.org/wiki/Mertens_function), and anything which has any chance of leading to a proof of the RH is automatically of interest to mathematicians.


A second approach to solidifying Mobius pseudorandomness is by quantifying the "independently distributed" aspect of i.i.d random variables. This is generally done via the Chowla conjecture which states that for any fixed integer $m$ and exponents $a\_0,a\_2...a\_{m-1}\geq0$ we have that


\begin{equation}
\lim\_{x\to\infty}\sum\_{n<x}\mu(n)^{a\_0}\mu(n+1)^{a\_1}...\mu(n+m)^{a\_{m-1}}=o(x)\tag{3}
\end{equation}


where of course at least one $a\_i$ must be odd, since otherwise all the terms are positive and the sign cancellation is completely lost. This is saying, morally, that given one "coin flip" $\mu(n)$ we cannot determine the values of the successive flips $\mu(n+m)$ for a small fixed $m$. In some ways, Chowla's conjecture is even stronger than (2). For example, the special case


$$\sum\_{n<x}\mu(n)\mu(n+2)=o(x)$$


is "morally" equivalent to


$$\sum\_{n<x}\Lambda(n)\Lambda(n+2)=2\Pi\_2x+o(x)$$


Here, I say "morally" because actually proving one from the other requires a $O(\log^{-\epsilon}(x))$ error term. This second inequality is in turn equivalent to a strong version of the Twin Prime Conjecture, which I think that we can agree makes this a very major application of Mobius pseudorandomness.


There are lots of other measures of pseudorandomess too, like the Sarnak's conjecture that says that


\begin{equation}
\sum\_{n<x}\mu(n)f(n)=o(x)\tag{4}
\end{equation}


for any "simple enough" function $f(n)$, which can be made precise [here](https://terrytao.wordpress.com/2012/10/14/the-chowla-conjecture-and-the-sarnak-conjecture/), along with a discussion of the Chowla conjecture. A good example of a class of simple functions for which (4) holds is the case of [bounded depth/AC0 circuits](https://en.wikipedia.org/wiki/AC0). In conclusion, there is no one way to define Mobius pseudorandomess but there are lots of different ways to do so which all have their own interesting consequences.


