Return to Question

This question is related to this previous question where I asked about ordinary Fourier coefficients.

Start with the Mobius function $\mu (m)$. (Thus $\mu(m)=0$ unless all prime factors of $m$ appear once and $\mu (m)=(-1)^r$ if $m$ has $r$ distinct prime factors.) Now, for a n-digit positive number $m$ regard the Mobius function as a Boolean function $\mu(x_1,x_2,\dots,x_n)$ where $x_1,x_2,\dots,x_n$ are the binary digits of $m$.

For example $\mu (0,1,0,1)=\mu(2+8)=\mu(10)=1$. We write $\Omega_n$ as the set of 0-1 vectors $x=(x_1,x_2,x_m)$ of length $n$. We also write $[n]=\{1,2,\dots,n\}$, and $N=2^n$.

Next consider for some natural number $n$ the Walsh-Fourier transform

$$\hat \mu (S)= \frac{1}{2^n} \sum _{x\in \Omega_n} \mu(x_1,x_2,\dots,x_n)(-1)^{\sum\{x_i:i\in S\}}.$$

So $\sum_{S \subset [n]}|\hat \mu (S)|^2$ is roughly $6/\pi ^2$; and the Prime Number Theorem asserts that $\hat \mu(\emptyset)=o(1)$; In fact the known strong form of the Prime Number Theorem asserts that $|\hat \mu (\emptyset )|<n^{-A}$ (=($\log N)^A$) for every $A>0$. (Note that $|\hat \mu (\emptyset)=\sum_{k=0}^{N-1}\mu(k)$.)

My questions are:

1. Is it true that the individual coefficients tend to 0? Is it known even that $|\hat \mu (S)| \le n^{-A}$ for every $A>0$.

2. Is it the case that

$$(*) \sum \{ \hat \mu ^2(S)~:~|S|<(\log n)^A \} =o(1), $$ for every $A>0$.

(This does not seem to follow from bounds we can expect unconditionally on individual coefficients.)

3. The Riemann Hypothesis asserts that $$|\hat \mu (\emptyset )| < N^{-1/2+\epsilon}.$$

Does it follows from the GRH that for some $c>0$, $$| \hat \mu (S)| < N^{-c},$$ for every $S$?

An upper bound of $(\log N)^{-{\log \log N}^A}$ suffices to get the desired application.

The motivation for these questions from a certain computational complexity extension of the prime number theorem. It asserts that every function on the positive integers that can be represented by bounded depth Boolean circuit in terms of the binary expansion has diminishing correlation with the Mobius function. This conjecture that we can refer to as the $AC^0$- prime number conjecture is discussed here, on my blog and here, on Dick Lipton's blog. The conjecture follows from formula (***) by a result of Linial Mansour and Nisan on Walsh-Fourier coefficients of $AC^0$ functions.

Question 3 suggestes that perhaps we can deduce the $AC^0$ prime number conjecture from the GRH which would be of interest. Of course, it will be best to prove it unconditionally.

For polynomial size formulas, namely for functions expressible by depth-2 polynomial size circuits we may need even less. If an extension of a result of Mansour from characteristic functions of sets to functions whose domain is {-1,0,1} is true, it will show that the inequality $|\hat \mu (S)| \le n^{-(\log \log n)^A}$ for every $A>0$, would suffice. Moreover, if an extension of a conjecture of Mansour (which also follows from a more general conjecture called the Influence/Entropy conjecture, see this blog post for a description of both conjectures) to functions with values {0,1,-1} is correct, it will be enough to prove that $|\hat \mu (S)| \le n^{-A}$ for every $A>0$, to deduce the PNT for formulas.)

Let me mention that the question follows to a large extent a line of research associating $AC^0$ formulas with number theoretic questions. See the papers by Anna Bernasconi and Igor Shparlinski and the paper by Eric Allender Mike Saks Igor Shparlinski, and the paper COMPLEXITY OF SOME ARITHMETIC PROBLEMS FOR BINARY POLYNOMIALS by Eric Allender, Anna Bernasconi, Carsten Damm, Joachim von zur Gathen, Michael Saks, and Igor Shparlinski.

This question is related to this previous question where I asked about ordinary Fourier coefficients.

Start with the Mobius function $\mu (m)$. (Thus $\mu(m)=0$ unless all prime factors of $m$ appear once and $\mu (m)=(-1)^r$ if $m$ has $r$ distinct prime factors.) Now, for a n-digit positive number $m$ regard the Mobius function as a Boolean function $\mu(x_1,x_2,\dots,x_n)$ where $x_1,x_2,\dots,x_n$ are the binary digits of $m$.

For example $\mu (0,1,0,1)=\mu(2+8)=\mu(10)=1$. We write $\Omega_n$ as the set of 0-1 vectors $x=(x_1,x_2,x_m)$ of length $n$. We also write $[n]=\{1,2,\dots,n\}$, and $N=2^n$.

Next consider for some natural number $n$ the Walsh-Fourier transform

$$\hat \mu (S)= \frac{1}{2^n} \sum _{x\in \Omega_n} \mu(x_1,x_2,\dots,x_n)(-1)^{\sum\{x_i:i\in S\}}.$$

So $\sum_{S \subset [n]}|\hat \mu (S)|^2$ is roughly $6/\pi ^2$; and the Prime Number Theorem asserts that $\hat \mu(\emptyset)=o(1)$; In fact the known strong form of the Prime Number Theorem asserts that

$$|\hat \mu (\emptyset )| \lt n^{-A} =(\log N)^A,$$

for every $A>0$. (Note that $|\hat \mu (\emptyset)=\sum_{k=0}^{N-1}\mu(k)$.)

My questions are:

1. Is it true that the individual coefficients tend to 0? Is it known even that $|\hat \mu (S)| \le n^{-A}$ for every $A>0$.

2. Is it the case that

$$(*) \sum \{ \hat \mu ^2(S)~:~|S|<(\log n)^A \} =o(1), $$ for every $A>0$.

(This does not seem to follow from bounds we can expect unconditionally on individual coefficients.)

3. The Riemann Hypothesis asserts that $$|\hat \mu (\emptyset )| < N^{-1/2+\epsilon}.$$

Does it follows from the GRH that for some $c>0$, $$| \hat \mu (S)| < N^{-c},$$ for every $S$?

An upper bound of $(\log N)^{-{\log \log N}^A}$ suffices to get the desired application.

The motivation for these questions from a certain computational complexity extension of the prime number theorem. It asserts that every function on the positive integers that can be represented by bounded depth Boolean circuit in terms of the binary expansion has diminishing correlation with the Mobius function. This conjecture that we can refer to as the $AC^0$- prime number conjecture is discussed here, on my blog and here, on Dick Lipton's blog. The conjecture follows from formula (***) by a result of Linial Mansour and Nisan on Walsh-Fourier coefficients of $AC^0$ functions.

Question 3 suggestes that perhaps we can deduce the $AC^0$ prime number conjecture from the GRH which would be of interest. Of course, it will be best to prove it unconditionally.

For polynomial size formulas, namely for functions expressible by depth-2 polynomial size circuits we may need even less. If an extension of a result of Mansour from characteristic functions of sets to functions whose domain is {-1,0,1} is true, it will show that the inequality $|\hat \mu (S)| \le n^{-(\log \log n)^A}$ for every $A>0$, would suffice. Moreover, if an extension of a conjecture of Mansour (which also follows from a more general conjecture called the Influence/Entropy conjecture, see this blog post for a description of both conjectures) to functions with values {0,1,-1} is correct, it will be enough to prove that $|\hat \mu (S)| \le n^{-A}$ for every $A>0$, to deduce the PNT for formulas.)

Let me mention that the question follows to a large extent a line of research associating $AC^0$ formulas with number theoretic questions. See the papers by Anna Bernasconi and Igor Shparlinski and the paper by Eric Allender Mike Saks Igor Shparlinski, and the paper COMPLEXITY OF SOME ARITHMETIC PROBLEMS FOR BINARY POLYNOMIALS by Eric Allender, Anna Bernasconi, Carsten Damm, Joachim von zur Gathen, Michael Saks, and Igor Shparlinski.

This question is related to this previous question where I asked about ordinary Fourier coefficients.

Start with the Mobius function $\mu (m)$. (Thus $\mu(m)=0$ unless all prime factors of $m$ appear once and $\mu (m)=(-1)^r$ if $m$ has $r$ distinct prime factors.) Now, for a n-digit positive number $m$ regard the Mobius function as a Boolean function $\mu(x_1,x_2,\dots,x_n)$ where $x_1,x_2,\dots,x_n$ are the binary digits of $m$.

For example $\mu (0,1,0,1)=\mu(2+8)=\mu(10)=1$. We write $\Omega_n$ as the set of 0-1 vectors $x=(x_1,x_2,x_m)$ of length $n$. We also write $[n]=\{1,2,\dots,n\}$, and $N=2^n$.

Next consider for some natural number $n$ the Walsh-Fourier transform

$$\hat \mu (S)= \frac{1}{2^n} \sum _{x\in \Omega_n} \mu(x_1,x_2,\dots,x_n)(-1)^{\sum\{x_i:i\in S\}}.$$

So $\sum_{S \subset [n]}|\hat \mu (S)|^2$ is roughly $6/\pi ^2$; and the Prime Number Theorem asserts that $\hat \mu(\emptyset)=o(1)$; In fact the known strong form of the Prime Number Theorem asserts that $|\hat \mu (\emptyset )|<n^{-A}$ (=($\log N)^A$) for every $A>0$. (Note that $|\hat \mu (\emptyset)=\sum_{k=0}^{N-1}\mu(k)$.)

My questions are:

1. Is it true that the individual coefficients tend to 0? Is it known even that $|\hat \mu (S)| \le n^A$ for every $A>0$.

2. Is it the case that

$$(*) \sum \{ \hat \mu ^2(S)~:~|S|<(\log n)^A \} =o(1), $$ for every $A>0$.

(This does not seem to follow from bounds we can expect unconditionally on individual coefficients.)

3. The Riemann Hypothesis asserts that $$|\hat \mu (\emptyset )| < N^{1/2+\epsilon}.$$

Does it follows from the GRH that for some $c>0$, $$| \hat \mu (S)| < N^{-c},$$ for every $S$?

An upper bound of $(\log N)^{{\log \log N}^A}$ suffices to get the desired application.

The motivation for these questions from a certain computational complexity extension of the prime number theorem. It asserts that every function on the positive integers that can be represented by bounded depth Boolean circuit in terms of the binary expansion has diminishing correlation with the Mobius function. This conjecture that we can refer to as the $AC^0$- prime number conjecture is discussed here, on my blog and here, on Dick Lipton's blog. The conjecture follows from formula (***) by a result of Linial Mansour and Nisan on Walsh-Fourier coefficients of $AC^0$ functions.

Question 3 suggestes that perhaps we can deduce the $AC^0$ prime number conjecture from the GRH which would be of interest. Of course, it will be best to prove it unconditionally.

For polynomial size formulas, namely for functions expressible by depth-2 polynomial size circuits we may need even less. If an extension of a result of Mansour from characteristic functions of sets to functions whose domain is {-1,0,1} is true, it will show that the inequality $|\hat \mu (S)| \le n^{(\log \log n)^A}$ for every $A>0$, would suffice. Moreover, if an extension of a conjecture of Mansour (which also follows from a more general conjecture called the Influence/Entropy conjecture, see this blog post for a description of both conjectures) to functions with values {0,1,-1} is correct, it will be enough to prove that $|\hat \mu (S)| \le n^A$ for every $A>0$, to deduce the PNT for formulas.)

Let me mention that the question follows to a large extent a line of research associating $AC^0$ formulas with number theoretic questions. See the papers by Anna Bernasconi and Igor Shparlinski and the paper by Eric Allender Mike Saks Igor Shparlinski, and the paper COMPLEXITY OF SOME ARITHMETIC PROBLEMS FOR BINARY POLYNOMIALS by Eric Allender, Anna Bernasconi, Carsten Damm, Joachim von zur Gathen, Michael Saks, and Igor Shparlinski.

This question is related to this previous question where I asked about ordinary Fourier coefficients.

Start with the Mobius function $\mu (m)$. (Thus $\mu(m)=0$ unless all prime factors of $m$ appear once and $\mu (m)=(-1)^r$ if $m$ has $r$ distinct prime factors.) Now, for a n-digit positive number $m$ regard the Mobius function as a Boolean function $\mu(x_1,x_2,\dots,x_n)$ where $x_1,x_2,\dots,x_n$ are the binary digits of $m$.

For example $\mu (0,1,0,1)=\mu(2+8)=\mu(10)=1$. We write $\Omega_n$ as the set of 0-1 vectors $x=(x_1,x_2,x_m)$ of length $n$. We also write $[n]=\{1,2,\dots,n\}$, and $N=2^n$.

Next consider for some natural number $n$ the Walsh-Fourier transform

$$\hat \mu (S)= \frac{1}{2^n} \sum _{x\in \Omega_n} \mu(x_1,x_2,\dots,x_n)(-1)^{\sum\{x_i:i\in S\}}.$$

So $\sum_{S \subset [n]}|\hat \mu (S)|^2$ is roughly $6/\pi ^2$; and the Prime Number Theorem asserts that $\hat \mu(\emptyset)=o(1)$; In fact the known strong form of the Prime Number Theorem asserts that $|\hat \mu (\emptyset )|<n^{-A}$ (=($\log N)^A$) for every $A>0$. (Note that $|\hat \mu (\emptyset)=\sum_{k=0}^{N-1}\mu(k)$.)

My questions are:

1. Is it true that the individual coefficients tend to 0? Is it known even that $|\hat \mu (S)| \le n^{-A}$ for every $A>0$.

2. Is it the case that

$$(*) \sum \{ \hat \mu ^2(S)~:~|S|<(\log n)^A \} =o(1), $$ for every $A>0$.

(This does not seem to follow from bounds we can expect unconditionally on individual coefficients.)

3. The Riemann Hypothesis asserts that $$|\hat \mu (\emptyset )| < N^{-1/2+\epsilon}.$$

Does it follows from the GRH that for some $c>0$, $$| \hat \mu (S)| < N^{-c},$$ for every $S$?

An upper bound of $(\log N)^{-{\log \log N}^A}$ suffices to get the desired application.

The motivation for these questions from a certain computational complexity extension of the prime number theorem. It asserts that every function on the positive integers that can be represented by bounded depth Boolean circuit in terms of the binary expansion has diminishing correlation with the Mobius function. This conjecture that we can refer to as the $AC^0$- prime number conjecture is discussed here, on my blog and here, on Dick Lipton's blog. The conjecture follows from formula (***) by a result of Linial Mansour and Nisan on Walsh-Fourier coefficients of $AC^0$ functions.

Question 3 suggestes that perhaps we can deduce the $AC^0$ prime number conjecture from the GRH which would be of interest. Of course, it will be best to prove it unconditionally.

For polynomial size formulas, namely for functions expressible by depth-2 polynomial size circuits we may need even less. If an extension of a result of Mansour from characteristic functions of sets to functions whose domain is {-1,0,1} is true, it will show that the inequality $|\hat \mu (S)| \le n^{-(\log \log n)^A}$ for every $A>0$, would suffice. Moreover, if an extension of a conjecture of Mansour (which also follows from a more general conjecture called the Influence/Entropy conjecture, see this blog post for a description of both conjectures) to functions with values {0,1,-1} is correct, it will be enough to prove that $|\hat \mu (S)| \le n^{-A}$ for every $A>0$, to deduce the PNT for formulas.)

Let me mention that the question follows to a large extent a line of research associating $AC^0$ formulas with number theoretic questions. See the papers by Anna Bernasconi and Igor Shparlinski and the paper by Eric Allender Mike Saks Igor Shparlinski, and the paper COMPLEXITY OF SOME ARITHMETIC PROBLEMS FOR BINARY POLYNOMIALS by Eric Allender, Anna Bernasconi, Carsten Damm, Joachim von zur Gathen, Michael Saks, and Igor Shparlinski.