The AC0 Prime Number Conjecture

Posted on February 21, 2011 by Gil Kalai

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 AC_0 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 AC^0 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 \sum_{m=1}^{X}\mu(m) W_S(m) \le X \cdot e^{-(\log X)^{1/10}}. In other words, \hat \mu(S) \le e^{-(\log X)^{1/10}}.

Jean also showed that under GRH \sum_{m=1}^X\mu(m)W_S(m) \le X^{1-(c/(\log\log X)^2)}. In other words, \hat \mu(S) \le X^{-(c/\log \log X)^2}. 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 \mu(3x)^2 has correlation >0.8 with the 0(mod 3) function. So we have a simple argument showing that (for n 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 f(n) be a function from the natural numbers to {-1,+1}. Let \mu be the classical Möbius function. Namely, \mu(n) is 0 unless n is a square-free integer and \mu (n)=(-1)^r if n is the product of r distinct primes.

Consider the sum \mu(f) = \sum_{i=1}^N f(i)\mu (i).

Conjecture: For fixed d and c there is a  function u(n;d,c) such that u(n;d,c)/2^n tends to zero as n tends to infinity, and such that the following assertion holds:

Consider a function f from \{1,2,\dots,2^n-1\} to {-1,1}, which can be described by a depth-d size n^c Boolean circuit C. (I.e., f(i) is defined by applying the circuit to the binary digits of i.)

Then \mu(f) \le u(n;d,c).

When f 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 AC_0 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 f(x_1,x_2,\dots,x_n) where the variables x_k take the values +1 and -1 and the value of f 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 r is a single gate leading to the output of the circuit.

The depth of the circuit is this number r. 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. AC_0

AC_0 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 n^c of the number of variables. Much is known about Boolean functions described by such functions.

This entry was posted in Computer Science and Optimization, Number theory and tagged , , , , , , , . Bookmark the permalink.

16 Responses to The AC0 Prime Number Conjecture

  1. reference says:
    February 22, 2011 at 2:19 am

    Allender Saks Shparlinski: detecting squarefree numbers is hard for AC0

    Reply
  2. Kea says:
    February 22, 2011 at 2:32 am

    Well, 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!

    Reply
    • Prof. George Purdy says:
      February 27, 2011 at 2:15 am

      Dear 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

      Reply
      • Prof. George Purdy says:
        February 27, 2011 at 7:13 am

        I’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

      • Kea says:
        February 28, 2011 at 9:15 pm

        The 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.

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

  4. John Sidles says:
    February 25, 2011 at 9:53 pm

    Gil please let me say that I read, admire, and enjoy Combinatorics and More very 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.

    Reply

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

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

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

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

  9. Pingback: Cody Murray and Ryan Williams’ new ACC breakthrough: Updates from Oded Goldreich’s Choices | Combinatorics and more

  10. Pingback: To cheer you up in difficult times 5: A New Elementary Proof of the Prime Number Theorem by Florian K. Richter | Combinatorics and more

  11. Pingback: Sarnak의 Mobius 추측에 대한 반례로 효율적으로 계산 가능한 기능 ( k는 ) - How IT

Leave a reply to John Sidles Cancel reply