6

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.

YCor
  • 60,149
Milo Moses
  • 2,819
  • 10
  • 36
  • 5
    I think you misunderstand this site. You are supposed to ask a question for which you don't know the answer. One that is important to you and came up in your research. For disseminating your thoughts on a topic, please use a blog. – GH from MO Nov 24 '20 at 10:34
  • 5
    @GHfromMO On the official StackOverflow site https://stackoverflow.blog/2011/07/01/its-ok-to-ask-and-answer-your-own-questions/, they say directly "To be crystal clear, it is not merely OK to ask and answer your own question, it is explicitly encouraged" when discussing the Q&A feature I used. However, I do understand your point and in the future I will make a blog. – Milo Moses Nov 24 '20 at 17:00
  • 8
    Different sites on the SE network developed different customs, and this is particularly pronounced in the case of MO due to its history (it didn’t start as a part of SE, but as an independent site, which was only integrated in the SE network when Fog Creek ended the original hosting arrangement, and it still maintains a degree of autonomy). Thus, while some sites on the network welcome self-answered questions to “share your knowledge”, this is virtually unheard of on MO, and as you can see, the reaction of site regulars to this idea is (besides being confused by it) not very enthusiastic. – Emil Jeřábek Nov 24 '20 at 17:27
  • 2
    @EmilJeřábek thank you for this piece of history. I really appreciate this. – Milo Moses Nov 24 '20 at 17:52
  • The pseudorandomness of $\mu(n)$ is a consequence of that, for $n$ taken uniformly in $[1,N]$, then the random variables $n\bmod p_j$ for $j\le \pi(\sqrt{N})$ are almost independent. The distribution of $n\bmod p_j$ is almost the uniform distribution. When forgetting about those almost we get most conjectures about primes: GRH, asymptotic of twin primes and $k$-upples, Goldbach for large enough integers, primes in polynomial values. – reuns Nov 25 '20 at 02:02

2 Answers2

7

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), 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, 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. 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.

Milo Moses
  • 2,819
  • 10
  • 36
  • 8
    It appears that you asked and answered your own question, and moreover at nearly the same time. What was the reason for doing this here? – KConrad Nov 24 '20 at 03:37
  • 6
    @KConrad there is a feature called "share your knowledge Q@A style", and I have been thinking a lot about Mobius pseudorandomnes a lot recently but I don't really have anyone to talk to about it so I decided to make this question. It was also to see if people agreed/disagreed with my presentation of the concept, since the answer I gave was an amalgamation of lots of different sources and I would consider original to myself. Hopefully this isn't frowned upon – Milo Moses Nov 24 '20 at 04:08
  • 7
    Generally, if you're going to do that, it's a good idea to say so right off the bat in the body of your question, so other users know what they're getting into, Milo. – Gerry Myerson Nov 24 '20 at 05:28
  • @GerryMyerson I don't really know how to phrase it in a good way, but I'll try. Thank you for the advice Gerry – Milo Moses Nov 24 '20 at 05:50
  • 4
    What's there to phrase? "It's my intention to post my own answer to this question. Criticism, commentary, and better answers will be welcome." – Gerry Myerson Nov 24 '20 at 05:56
  • @GerryMyerson thank you – Milo Moses Nov 24 '20 at 06:00
  • 8
    Okay, I was unaware of such a "feature". In the past some others have answered their own questions soon after asking them frequently enough that they were reminded that the site should not serve as a substitute for a personal blog page. Anyway, one suggestion I have is to provide links in your answer to references that give more details on all of the various results or equivalences in your answer in order to make it more useful for a reader unfamiliar with the general theme. – KConrad Nov 24 '20 at 06:16
  • 3
    You should mention that Sarnak’s conjecture has been proven for $\mathrm{AC}^0$ functions $f$ by Ben Green. See https://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-m%C3%B6bius-function . – Emil Jeřábek Nov 24 '20 at 07:23
  • 5
    Btw, why do you call yourself “you” in the answer? It sounds a bit schizophrenic. – Emil Jeřábek Nov 24 '20 at 07:30
  • 9
    No, it's not schizophrenic, it's just supposed to be question+answer, in a way that others might find interesting to read. Don't be too harsh with the guy. – Kurisuto Asutora Nov 24 '20 at 08:39
  • lol, anyway this is related to sarnak' conjecture, a naive one is $\sum_{n \leq x} \Lambda(n)\sim x \Leftrightarrow \sum_{n \leq x} \mu(n)=o(x) $, so if we gain a result $\sum_{n \leq x} \mu(n)f(n)=o(x)$, we can roughly understand it as prime is distribute as the normal ''measure" $x/\log x$ in equivalence class generate by ${f(n), n\in \mathbb{N}^*}$. – katago Nov 24 '20 at 11:06
2

Here are a few (maybe helpful?) tidbits. In papers of 1931 and 1964 in the Comptes Rendus, Denjoy surmised that RH is true if the Mobius function was random for then your condition at (2) would be met. Also: true randomness would probably mean that the sequence needs to pass any statistical test that would be passed with probability one if the sequence consisted of statistically mutually independent random variables. In this latter case the order term in your condition (2) could actually be replaced by the square root of (x log log x) since the Law of the Iterated Logarithm would apply to it. There is also a time series character to this issue and for this recent work by Matomaki, Radziwill, Tao, Sarnak and others is relevant. Much remains unknown.

AndreyF
  • 171