Peter Sarnak is Coming to Town – Let’s Celebrate it with a Post on Möbius Randomness, Computational Complexity, and AI

Combinatorics and more 2024-12-15

Peter Sarnak will give the Gordon memorial lectures at the Hebrew University of Jerusalem.

At the end of December 2024, Peter Sarnak will deliver the Mark Gordon memorial lecture series on Spectra of locally symmetric geometries at the Hebrew University of Jerusalem. This event will be part of a workshop focusing on the same theme. The lecture series will feature additional talks by esteemed mathematicians, including Omri Solan, Nattalie Tamam, Uri Shapira, Alex Gamburd, Elon Lindenstrauss, Zeev Rudnick, Borys Kadets, Alex Smith, Barak Weiss, Menny Aka, Amos Nevo, Lior Bary-Soroker, Snir Ben Ovadia, and Bryce Orloski.

You are warmly invited to attend!

If you cannot make it to Jerusalem but are curious about the subject, consider watching Peter Sarnak’s Chern’s lecture at Berkeley on a related topic. I looked at the slides of the first lecture, and while the mathematics was new to me, Peter’s familiar handwriting raised fond memories of previous lectures.

Oh, and if you are looking for my previous post, here is the link : The Case Against Google’s Claims of “Quantum Supremacy”: A Very Short Introduction.

Möbius Randomness and Computational Complexity

A few months ago I decided to celebrate Peter’s 70 birthday conference with a new Möbius randomness conjecture. At the same time, I also decided to celebrate Richard Stanley’s 80 birthday conference with a new conjecture about Stanley-Reisner rings. Progress on both projects was slower than anticipated, and the conjectures were not ready in time for the conferences.

We will use algebraic circuits. Here is a link to Ramprasad Saptharishi’s A survey of lower bounds in arithmetic circuit complexity. I am thankful to several colleagues and especially to Ben Lee Volk for helpful conversations on arithmetic circuits.

Here is a tentative version of the conjecture for Peter:

The arithmetic Bounded-Depth Prime Number Conjecture (tentative version): The correlation between the Möbius function and any complex function $e^{\pi i f(n)}$ so that $f$ can be described by a bounded depth polynomial size arithmetic circuit in the binary digits of $n$ , tends to zero.

Let me state the “pre-conjecture” that was my starting point:

Complexity theoretic Möbius Randomness pre-conjecture: Formulate a Möbius randomness conjecture based on computational complexity notions that:

a) It should be potentially feasible from the perspective of computational complexity theory.

b) It should include the Davenport theorem (regarding polynomials), the Green-Tao theorem (on bracket polynomials; see this post) and other known concrete Möbius Randomness theorems.

Remark: We regard “Möbius randomness” and “a prime number theorem” as synonymous because the classical PNT is equivalent to the Möbius randomness of the constant one function. However, in more general cases, the precise connections between statements about the Möbius function and assertions about primes can be subtle.

AI?

Of course, once we have a vague idea like my pre-conjecture maybe AI can lead us to useful mathematical conjectures? I asked (free-version) ChatGPT the following. Question: Please, formulate seven Möbius randomness conjectures based on computational complexity notions that will be potentially feasible from the point of view of computational complexity.

I found the answer striking. (You can try it yourself or look here.)

Background

For background on Möbius randomness, see this 2010 videotaped lecture by Peter Sarnak, A further lecture by Peter Möbius randomness and dynamics six years later; and Tamar Ziegler – Sign Patterns of the M ö bius Function.

From the computational complexity side, this line of research has roots in the late 90s in works by Bernasconi, Damm, Shparlinski, Saks, and others. I will add some links at the end of the post. In the meantime, let me offer you Igor Shparlinski’s paper: Problems on Exponential and Character Sums (it looks great!).

The Story of the $AC_0$ Prime Number Theorem:

In February 2011 I proposed over here the following conjecture: 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.

This conjecture was inspired by a lecture of Peter Sarnak in our math colloquium and by some comments made in real time by me and by other participants of the colloquium (including Dorit Aharonov and Michael Ben-Or). A few days later, in March 2011, I proposed over MathOverflow three related problems that relate Möbius randomness with Fourier-Walsh coefficients of the Möbius function.

Problems posted on MathOverflow

My MO post included three questions. In these questions, I considered $n$ -digit binary numbers, setting $N=2^n$ . The problems were

Fourier-Walsh Coefficients (Full): Show that all Fourier-Walsh coefficients $\hat \mu (S)$ of the Möbius function $\mu$ , regarded as a function of the $n$ -binary digits of numbers between 1 and between 1 and $2^n-1$ are small.
Fourier-Walsh Coefficients (Restricted): Prove the above for coefficients $\mu (S)$ where $|S|$ is polylogarithmic in $n$ . By the Linial-Mansour-Nisan theorem, this implies Möbius randomness for AC0 functions.
Fourier-Walsh Coefficients under GRH (Still Open): Assuming the Generalized Riemann Hypothesis (GRH), prove that $\hat \mu(S) \le N^{-c}$ for some constant $c>0$ . It is plausible to conjecture that for every $\epsilon >0$ , $\max_{S} |\hat \mu(S)| \le N^{-1/2+\epsilon}$ , consistent with the RH for $S = \emptyset$ .

Results by Green and Bourgain

The second MO question and with it the $AC_0$ Prime Number Conjecture was settled by Ben Green (five days after my posting) in his paper On (not) computing the Möbius function using bounded depth circuits.

The first MO question was solved in the positive by Jean Bourgain in the paper: Möbius-Walsh correlation bounds and an estimate of Mauduit and Rivat. Bourgain proved a uniform bound of the form $2^{-n^{1/10}}$ ; For further results see Bourgain’s paper On the Fourier-Walsh Spectrum on the Möbius Function. Bourgain’s results imply also the following theorem:

Theorem (Bourgain): Möbius Randomness for monotone Boolean functions: The correlation between the Möbius function and any function $f$ so that $f$ can be described by a monotone Boolean function in terms of its binary digits, tends to zero.

Circuit Complexity and Möbius Randomness – the Frontiers

Let me state together four plausible conjectures; except for the third one they could be realistic:

1) Möbius Randomness conjecture for ACC(p): The correlation between the Möbius function $\mu (n)$ and any function $f$ computable by a circuit in ACC(p) (constant-depth circuits with modular counting gates for prime $p$ ), tends to zero.

2) Möbius Randomness conjecture for low degree polynomials: The correlation between $\mu (n)$ and every polynomials over $\mathbb Z/2 \mathbb Z$ of degree at most ${\rm polylog} (n)$ , tends to zero.

For linear polynomials this is the conjecture about Fourier-Walsh coefficients of the Mobius function proved by Bourgain.
A special case of degree-2 polynomials is the Rudin-Shapiro sequence. I asked about this special case over MO and it was proved by Terry Tao . His solution relies on the Katai-Bourgain-Sarnak-Ziegler orthogonality criterion.
A key connection is a theorem by Razborov’s that implies that the conjecture for polylog-degree polynomials implies the conjecture for ACC(2).

3) Möbius Randomness conjecture for TC0: The correlation between the Möbius function and any function $f$ so that $f$ can be described by a circuit in TC0, tends to zero.

TC0 is a fairly law complexity class but there are good reasons to think it is already intractable for lowers bounds. It will still be interesting to examine which interesting functions can be described by TC0 circuits.

Returning to the arithmetic Bounded-Depth Prime Number Conjecture, let me state it again with a couple comments.

4) Möbius Randomness conjecture for arithmetic AC0 (tentative version): The correlation between the Möbius function and any complex function $e^{\pi i f(n)}$ so that $f$ can be described by a bounded depth polynomial size arithmetic circuit in the binary digits of $n$ , tends to zero.

There is a well-developed theory about algebraic properties of functions in arithmetic AC0, allowing to prove that certain functions are not in this class. (This is a long story that I will not attempt to describe here.) Much like in the Boolean AC0 setting, this framework might offer a pathway toward proving the conjecture—or at least suggesting additional conjectures and approaches.
Ramprasad Saptharishi’s A survey of lower bounds in arithmetic circuit complexity is a comprehensive survey with an added chapter about a recent breakthrough: the super-polynomial constant-depth lower bound of Limaye, Srinivasan and Tavenas.