6
$\begingroup$

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.

$\endgroup$
5
  • 5
    $\begingroup$ 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. $\endgroup$
    – GH from MO
    Commented Nov 24, 2020 at 10:34
  • 5
    $\begingroup$ @GHfromMO On the official StackOverflow site stackoverflow.blog/2011/07/01/…, 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. $\endgroup$
    – Milo Moses
    Commented Nov 24, 2020 at 17:00
  • 8
    $\begingroup$ 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. $\endgroup$ Commented Nov 24, 2020 at 17:27
  • 2
    $\begingroup$ @EmilJeřábek thank you for this piece of history. I really appreciate this. $\endgroup$
    – Milo Moses
    Commented Nov 24, 2020 at 17:52
  • $\begingroup$ 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. $\endgroup$
    – reuns
    Commented Nov 25, 2020 at 2:02

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
11
  • 8
    $\begingroup$ 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? $\endgroup$
    – KConrad
    Commented Nov 24, 2020 at 3:37
  • 6
    $\begingroup$ @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 $\endgroup$
    – Milo Moses
    Commented Nov 24, 2020 at 4:08
  • 7
    $\begingroup$ 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. $\endgroup$ Commented Nov 24, 2020 at 5:28
  • 8
    $\begingroup$ 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. $\endgroup$
    – KConrad
    Commented Nov 24, 2020 at 6:16
  • 10
    $\begingroup$ 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. $\endgroup$ Commented Nov 24, 2020 at 8:39
2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

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