## Möbius randomness and computational complexity

Last spring Peter Sarnak gave a thought-provoking lecture in Jerusalem. (Here are the very interesting slides of a similar lecture at I.A.S.)

Here is a variation of the type of questions Peter has raised.

The Prime Number Conjecture:The correlation between the Möbius function and any function f from the natural numbers to {-1,1}, so that f can be described by a bounded depth polynomial size circuit, tends to zero!

**Updates:** (**March**) The conjecture made it to major league blogs as a very interesting blog post describing the conjecture appeared on Dick Lipton’s blog, and let to some interesting discussion. I posted two related Mathoverflow problems . The first

is about the discrete Fourier coefficients of the Mobius function and the second

is about Walsh-Fourier coefficients of the Mobius function. **Ben Green** have posted an answer to my Mathoverflow question indicating an affarmative solution for the Prime Number Conjecture. The proof is based on combining the Linial-Mansour-Nisan theorem with Results and techniques by Glyn Harman and Imre Kátai, (From the paper Primes with preassigned digits. II. Acta Arith. 133 (2008), 171–184.)

Ben have written ~~some ~~~~rough notes on this~~ a short paper giving the solution here. (An earlier note by Ben assumed GRH and the full paper contain the extra work is needed to prove it unconditionally.) This is a **very nice **result. Ben is also optimistic that showing that all Walsh-Fourier functions are orthogonal to Mobius (which is a more general result) is within reach by combining the above result with results by Mauduit-Rivat.

Of course, the next logical step is the ACC[2]-Prime number conjecture. This includes as a very special case the question if all Walsh-Fourier functions are orthogonal asymptotically to the Mobius function. The “Walsh-Fourier” functions are high degree monomials over the real but they can be considered as *linear* functions over Z/2Z. For that, replace the values {-1,+1} by {0,1} both in the domain and range of our Boolean functions? What about low degree polynomials instead of linear polynomials? If we can extend the results to polynomials over Z/2Z of degree at most polylog (n) this will imply by a result of Razborov Mobius randomness for AC0[2] circuits. (This is interesting also under GRH).

(**April**) **Jean Bourgain** proved (private communication) that for every Walsh function $W_S$ we have In other words,

Jean also showed that under GRH In other words, This result suffices to show under GRH the “monotone prime number conjecture.”

While the questions about polylog degree polynomials over Z/2Z and about AC0(2) circuits are still open, Jean Bourgain was able to prove Mobius randomness for AC0(2) circuits of certain sublinear size.

Jean also noted that to show that the Mobius function itself is non-approximable by a AC0[2) circuit (namely you cannot reach correlation say of 0.99) can easily be derived from Razborov Smolensky theorem, since an easy computation shows that has correlation >0.8 with the 0(mod 3) function. So we have a simple argument showing that (for large) an ACC(2) function (or even a polylog degree polynomial)) cannot have correlation larger than 0.99 with the Mobius function, but showing that it cannot have correlation larger than 0.01 with the Mobius function seems at present very difficult. (More update: as it turned out, this last observation can be found already in Allender-Saks-Shparlinski’s paper.)

**End of updates.**

Let me state the conjecture more precisely. Let be a function from the natural numbers to {-1,+1}. Let be the classical Möbius function. Namely, is 0 unless is a square-free integer and if is the product of distinct primes.

Consider the sum = .

Conjecture:For fixed and there is a function such that tends to zero as tends to infinity, and such that the following assertion holds:Consider a function from to {-1,1}, which can be described by a depth- size Boolean circuit C. (I.e., is defined by applying the circuit to the binary digits of .)

Then .

When is the constant one function this is just the prime number theorem. Trying to extend the prime number theorem via functions defined by low complexity classes seems interesting and within reach.

This conjecture looks to me as a good topic for open discussion which may benefit from casual chat between people familiar with Boolean functions in and people familiar with standard methods related to the prime number theorem.

## Mobius randomness and the class P.

Peter’s lecture started (see the picture above) with the analogous much more difficult question involving the complexity class P. (In fact, he challenged the audience to find a counterexample.) Finding a function in P with bounded-away-from-zero correlation with the Möbius function is in the direction of a polynomial algorithm for factoring – a problem which is entirely beyond our horizon. Peter then moved to describe other ways to study “Möbius randomness” which are based not on computational complexity but rather on certain notions of randomness (or, more precisely, of determinism) that arise in ergodic theory.

## A reminder about bounded depth Boolean circuits

### 1. Boolean functions

A Boolean function of n variables is simply a function where the variables take the values +1 and -1 and the value of itself is also either +1 or-1.

### 2. Boolean circuits

A Boolean circuit is a gadget that computes Boolean functions. It is built from **inputs**, **gates** and an **output. **We can think about these circuits as follows: On level 0 there are the variables. On level 1 there are gates acting on the variables. On level 2 there are gates acting on the outputs of the gates on level 1. And on level is a single gate leading to the output of the circuit.

The **depth** of the circuit is this number . The **size** of the circuit is the total number of gates. The gates perform Boolean operations: They can take an input bit and negate it. They can take several input bits and compute their OR – this means that the output will be ’1′ iff one of them is ’1′. They can take several input bits and compute their AND – this means that the output will be ’-1′ iff one of them is ‘-1′.

### 3.

is the class of “bounded depth polynomial size circuits”. Namely, these are classes of circuits for which the depth $d$ is bounded by a constant and the size is bounded by a fixed polynomial of the number of variables. Much is known about Boolean functions described by such functions.

referenceAllender Saks Shparlinski: detecting squarefree numbers is hard for AC0

Gil KalaiPost authorHere is the link http://web.science.mq.edu.au/~igor/SF_ACo-STACS.ps Indeed it looks highly relevant.

KeaWell, remember that the Mobius function is a fermionic operator for states obeying the Pauli exclusion principle. Without a Mobius numerator in a zeta function series, we have the ordinary (bosonic gas) Riemann zeta function. So the Mobius operator is a basic supersymmetry transformation for zeta functions. In contrast, you mention characteristic functions, for a topos like Set, which obeys classical logic. Is the Mobius inversion of f bounded as required? From a physics perspective this is an axiomatic question for quantum gravity, and unlikely to be solved within set theory. It would be very, very interesting if it was!

Prof. George PurdyDear Kea,

(Is this a New Zealand bird?)

Would you please elaborate? Does the Mobius function occur in quantum theory? I suppose one could look this up. I like your question about whether Summation mu(k)f(k) is bounded.

George

Prof. George PurdyI’m sorry. I meant your question as to whether the Mobius inversion of f is bounded. Of course Sigma mu(k)f(k) must be Omega(sqrt(x)).

George

KeaThe early papers on this topic are from around 1990. Today, Connes et al use noncommutative geometry (which is supposed to reformulate QFT) to study zeta functions. The Riemann gas is itself simple enough, and defines $\zeta$ as a physical partition function. This is where the Mobius function must be inserted to make the physics fermionic, rather than bosonic.

Now Connes et al take partition functions straight from standard 20th century physics, with no modification. I believe that physical ideas from quantum gravity are needed to understand how these zeta functions can arise from motivic cohomology (and generalizations). One aspect of this is something that I think of as Constructive Number Theory. Since the right language for gravity is higher dimensional topos theory (not necessarily a la Lurie), one cannot just take the reals or complex numbers as given. One must carefully choose their axioms in terms of physical operators using non standard analysis, say through introducing the surreals.

In the end, the use of the Mobius function in physics remains as stated, because there is supersymmetry between fermions and bosons (not the stringy kind though). The problem is the physical construction of the complex numbers, which takes us outside set theory. In other words, I don’t believe that the questions here are that well posed.

Pingback: The Depth Of The Möbius Function « Gödel’s Lost Letter and P=NP

John SidlesGil please let me say that I read, admire, and enjoy

Combinatorics and Morevery much. Quite often (as with Möbius functions) the subject matter is too deep for me to see any immediate engineering applications … still I store these ideas away, because they are beautiful, and in the confident expectation that someday their utility will be manifest. So thank you for the many wonderfully creative posts on this wonderful weblog.Gil KalaiPost authorMany thanks, John

Pingback: The Collatz Conjecture : Unsolved but Useless | Gaurav Happy Tiwari

Pingback: The Bourne Factor « Gödel’s Lost Letter and P=NP

Pingback: Do Gaps Between Primes Affect RSA Keys? « Gödel’s Lost Letter and P=NP

Pingback: Efficiently computable function as a counter-example to Sarnak's Mobius conjecture | Q&A System