Solved in the positive by Jean Bourgain (April 12, 2011): Moebius-Walsh correlation bounds and an estimate of Mauduit and Rivat; (Dec, 2011) For even stronger results see Bourgain's paperOn the Fourier-Walsh Spectrum on the Moebius Function.

(This does not seem to follow from bounds we can expect unconditionally on individual coefficients.) Solved in the positive by Ben Green (March 12, 2011): On (not) computing the Mobius function using bounded depth circuits. (See Green's answer below.)

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. (Ben Green proved it unconditionally).

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

Special case: is Möbius nearly Orthogonal to Morse

August Ferdinand Möbius (November 17, 1790 – September 26, 1868)

!

Harold Calvin Marston Morse (24 March 1892 – 22 June 1977), August Ferdinand Möbius (November 17, 1790 – September 26, 1868)

Consider the sequence of values of the Möbius functions on nonnegative integers. (Starting with 0 for 0.)

0, 1, −1, −1, 0, −1, 1, −1, 0, 0, 1, −1, 0, −1, 1, 1, 0, −1, 0, −1, 0, 1, 1, −1, 0, 0, ...

And the Morse sequence

1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1

Are these two sequences nearly orthogonal?

Remark: This case of the general problem follows from the solution of Mauduit and Rivat of a 1968 conjecture of Gelfond. They show that primes are equally likely to have odd or even digit sum in base 2. See Ben Green's remark below.)

The Problems

Start with the Möbius 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

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. A result of Mansour shows that the inequality $|\hat \mu (S)| \le n^{-(\log \log n)^A}$ for every $A>0$, would suffice! Moreover, 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) implies that it will be enough to prove that

$$|\hat \mu (S)| \le n^{-A}$$

for every $A>0$, to deduce the PNT for formulas.)

Some background

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.

Special case: is Mobius Möbius nearly Orthogonal to Morse

August Ferdinand Möbius (November 17, 1790 – September 26, 1868)

!

Harold Calvin Marston Morse (24 March 1892 – 22 June 19771977), August Ferdinand Möbius (November 17, 1790 – September 26, 1868)

Consider the sequence of values of the Mobius Möbius functions on nonnegative integers. (Starting with 0 for 0.)

0, 1, −1, −1, 0, −1, 1, −1, 0, 0, 1, −1, 0, −1, 1, 1, 0, −1, 0, −1, 0, 1, 1, −1, 0, 0, ...

And the Morse sequence

1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1

Are these two sequences nearly orthogonal?

Remark: This case of the general problem follows from the solution of Mauduit and Rivat of a 1968 conjecture of Gelfond. They show that primes are equally likely to have odd or even digit sum in base 2. See Ben Green's remark below.)

The Problems

Start with the Mobius Möbius 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

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. A result of Mansour shows that the inequality $|\hat \mu (S)| \le n^{-(\log \log n)^A}$ for every $A>0$, would suffice! Moreover, 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) implies that it will be enough to prove that

$$|\hat \mu (S)| \le n^{-A}$$

for every $A>0$, to deduce the PNT for formulas.)

Some background

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.

Special case: is Mobius nearly Orthogonal to Morse

August Ferdinand Möbius (November 17, 1790 – September 26, 1868)

Harold Calvin Marston Morse (24 March 1892 – 22 June 1977)

Consider the sequence of values of the Mobius functions on nonnegative integers. (Starting with 0 for 0.)

0, 1, −1, −1, 0, −1, 1, −1, 0, 0, 1, −1, 0, −1, 1, 1, 0, −1, 0, −1, 0, 1, 1, −1, 0, 0, ...

And the Morse sequence

1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1

Are these two sequences nearly orthogonal?

Remark: This case of the general problem follows from the solution of Mauduit and Rivat of a 1968 conjecture of Gelfond. They show that primes are equally likely to have odd or even digit sum in base 2. See Ben Green's remark below.)

The Problems

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

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. A result of Mansour shows that the inequality $|\hat \mu (S)| \le n^{-(\log \log n)^A}$ for every $A>0$, would suffice! Moreover, 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) implies that it will be enough to prove that

$$|\hat \mu (S)| \le n^{-A}$$

for every $A>0$, to deduce the PNT for formulas.)

Some background

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.

[3]: http://www.google.co.il/imgres?imgurl=http%3A//www-history.mcs.st-and.ac.uk/BigPictures/Mobius.jpeg&imgrefurl=http%3A//www-history.mcs.st-and.ac.uk/Posters/1117b.html&usg=__mwIPDBTxPXJs4cTjR_QyTp9ijcM=&h=326&w=268&sz=9&hl=iw&start=2&zoom=1&tbnid=0C3b_Vh7eFUq_M%3A&tbnh=118&tbnw=97&ei=I5R3Te3_KsfTsgbwr5D2BA&prev=/images%253Fq%253DM%2525C3%2525B6bius%2526um%253D1%2526hl%253Diw%2526sa%253DN%2526rls%253Dcom.microsoft%3A*%3AIE-SearchBox%2526rlz%253D1I7HPND_en%2526tbs%253Disch%3A1&um=1&itbs=1


        

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

Special case: is Mobius nearly Orthogonal to Morse

August Ferdinand Möbius (November 17, 1790 – September 26, 1868)

Harold Calvin Marston Morse (24 March 1892 – 22 June 1977)

Consider the sequence of values of the Mobius functions on nonnegative integers. (Starting with 0 for 0.)

0, 1, −1, −1, 0, −1, 1, −1, 0, 0, 1, −1, 0, −1, 1, 1, 0, −1, 0, −1, 0, 1, 1, −1, 0, 0, ...

And the Morse sequence

1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1

Are these two sequences nearly orthogonal?

Remark: This case of the general problem follows from the solution of Mauduit and Rivat of a 1968 conjecture of Gelfond. They show that primes are equally likely to have odd or even digit sum in base 2. See Ben Green's remark below.)

The Problems

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

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. A result of Mansour shows that the inequality $|\hat \mu (S)| \le n^{-(\log \log n)^A}$ for every $A>0$, would suffice! Moreover, 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) implies that it will be enough to prove that

$$|\hat \mu (S)| \le n^{-A}$$

for every $A>0$, to deduce the PNT for formulas.)

Some background

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.

[3]: http://www.google.co.il/imgres?imgurl=http%3A//www-history.mcs.st-and.ac.uk/BigPictures/Mobius.jpeg&imgrefurl=http%3A//www-history.mcs.st-and.ac.uk/Posters/1117b.html&usg=__mwIPDBTxPXJs4cTjR_QyTp9ijcM=&h=326&w=268&sz=9&hl=iw&start=2&zoom=1&tbnid=0C3b_Vh7eFUq_M%3A&tbnh=118&tbnw=97&ei=I5R3Te3_KsfTsgbwr5D2BA&prev=/images%253Fq%253DM%2525C3%2525B6bius%2526um%253D1%2526hl%253Diw%2526sa%253DN%2526rls%253Dcom.microsoft%3A*%3AIE-SearchBox%2526rlz%253D1I7HPND_en%2526tbs%253Disch%3A1&um=1&itbs=1

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

Special case: is Mobius nearly Orthogonal to Morse

August Ferdinand Möbius (November 17, 1790 – September 26, 1868)

Harold Calvin Marston Morse (24 March 1892 – 22 June 1977)

Consider the sequence of values of the Mobius functions on nonnegative integers. (Starting with 0 for 0.)

0, 1, −1, −1, 0, −1, 1, −1, 0, 0, 1, −1, 0, −1, 1, 1, 0, −1, 0, −1, 0, 1, 1, −1, 0, 0, ...

And the Morse sequence

1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1

Are these two sequences nearly orthogonal?

Remark: This case of the general problem follows from the solution of Mauduit and Rivat of a 1968 conjecture of Gelfond. They show that primes are equally likely to have odd or even digit sum in base 2. See Ben Green's remark below.)

The Problems

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

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. A result of Mansour shows that the inequality $|\hat \mu (S)| \le n^{-(\log \log n)^A}$ for every $A>0$, would suffice! Moreover, 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) implies that it will be enough to prove that

$$|\hat \mu (S)| \le n^{-A}$$

for every $A>0$, to deduce the PNT for formulas.)

Some background

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.

Special case: is Mobius nearly Orthogonal to Morse

August Ferdinand Möbius (November 17, 1790 – September 26, 1868) Harold Calvin Marston Morse (24 March 1892 – 22 June 1977)

Consider the sequence of values of the Mobius functions on nonnegative integers. (Starting with 0 for 0.)

0, 1, −1, −1, 0, −1, 1, −1, 0, 0, 1, −1, 0, −1, 1, 1, 0, −1, 0, −1, 0, 1, 1, −1, 0, 0, ...

And the Morse sequence

1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1

Are these two sequences nearly orthogonal?

Remark: This case of the general problem follows from the solution of Mauduit and Rivat of a 1968 conjecture of Gelfond. They show that primes are equally likely to have odd or even digit sum in base 2. See Ben Green's remark below.)

The Problems

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

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. A result of Mansour shows that the inequality $|\hat \mu (S)| \le n^{-(\log \log n)^A}$ for every $A>0$, would suffice! Moreover, 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) implies that it will be enough to prove that

$$|\hat \mu (S)| \le n^{-A}$$

for every $A>0$, to deduce the PNT for formulas.)

Some background

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.

[3]: http://upload.wikimedia.org/wikipedia/commons/7/78/Marston_Morse.jpg


        

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

Special case: is Mobius nearly Orthogonal to Morse

August Ferdinand Möbius (November 17, 1790 – September 26, 1868) Harold Calvin Marston Morse (24 March 1892 – 22 June 1977)

Consider the sequence of values of the Mobius functions on nonnegative integers. (Starting with 0 for 0.)

0, 1, −1, −1, 0, −1, 1, −1, 0, 0, 1, −1, 0, −1, 1, 1, 0, −1, 0, −1, 0, 1, 1, −1, 0, 0, ...

And the Morse sequence

1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1

Are these two sequences nearly orthogonal?

Remark: This case of the general problem follows from the solution of Mauduit and Rivat of a 1968 conjecture of Gelfond. They show that primes are equally likely to have odd or even digit sum in base 2. See Ben Green's remark below.)

The Problems

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

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. A result of Mansour shows that the inequality $|\hat \mu (S)| \le n^{-(\log \log n)^A}$ for every $A>0$, would suffice! Moreover, 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) implies that it will be enough to prove that

$$|\hat \mu (S)| \le n^{-A}$$

for every $A>0$, to deduce the PNT for formulas.)

Some background

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.

[3]: http://upload.wikimedia.org/wikipedia/commons/7/78/Marston_Morse.jpg

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

Special case: is Mobius nearly Orthogonal to Morse

August Ferdinand Möbius (November 17, 1790 – September 26, 1868) Harold Calvin Marston Morse (24 March 1892 – 22 June 1977)

Consider the sequence of values of the Mobius functions on nonnegative integers. (Starting with 0 for 0.)

0, 1, −1, −1, 0, −1, 1, −1, 0, 0, 1, −1, 0, −1, 1, 1, 0, −1, 0, −1, 0, 1, 1, −1, 0, 0, ...

And the Morse sequence

1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1

Are these two sequences nearly orthogonal?

Remark: This case of the general problem follows from the solution of Mauduit and Rivat of a 1968 conjecture of Gelfond. They show that primes are equally likely to have odd or even digit sum in base 2. See Ben Green's remark below.)

The Problems

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

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. A result of Mansour shows that the inequality $|\hat \mu (S)| \le n^{-(\log \log n)^A}$ for every $A>0$, would suffice! Moreover, 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) implies that it will be enough to prove that

$$|\hat \mu (S)| \le n^{-A}$$

for every $A>0$, to deduce the PNT for formulas.)

Some background

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.

[3]: http://upload.wikimedia.org/wikipedia/commons/7/78/Marston_Morse.jpg


        

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

Special case: is Mobius nearly Orthogonal to Morse

August Ferdinand Möbius (November 17, 1790 – September 26, 1868) Harold Calvin Marston Morse (24 March 1892 – 22 June 1977)

Consider the sequence of values of the Mobius functions on nonnegative integers. (Starting with 0 for 0.)

0, 1, −1, −1, 0, −1, 1, −1, 0, 0, 1, −1, 0, −1, 1, 1, 0, −1, 0, −1, 0, 1, 1, −1, 0, 0, ...

And the Morse sequence

1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1

Are these two sequences nearly orthogonal?

Remark: This case of the general problem follows from the solution of Mauduit and Rivat of a 1968 conjecture of Gelfond. They show that primes are equally likely to have odd or even digit sum in base 2. See Ben Green's remark below.)

The Problems

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

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. A result of Mansour shows that the inequality $|\hat \mu (S)| \le n^{-(\log \log n)^A}$ for every $A>0$, would suffice! Moreover, 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) implies that it will be enough to prove that

$$|\hat \mu (S)| \le n^{-A}$$

for every $A>0$, to deduce the PNT for formulas.)

Some background

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.

[3]: http://upload.wikimedia.org/wikipedia/commons/7/78/Marston_Morse.jpg

Special case: is Mobius nearly Orthogonal to Morse

August Ferdinand Möbius (November 17, 1790 – September 26, 1868)Harold Calvin Marston Morse (24 March 1892 – 22 June 1977)

Consider the sequence of values of the Mobius functions on nonnegative integers. (Starting with 0 for 0.)

0, 1, −1, −1, 0, −1, 1, −1, 0, 0, 1, −1, 0, −1, 1, 1, 0, −1, 0, −1, 0, 1, 1, −1, 0, 0, ...

And the Morse sequence

1, -1, -1, 1, -1, 1, 1, -1, -1, 1, 1, -1, 1, -1, -1, 1, -1, 1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1

Are these two sequences nearly orthogonal?

Remark: This case of the general problem follows from the solution of Mauduit and Rivat of a 1968 conjecture of Gelfond. They show that primes are equally likely to have odd or even digit sum in base 2. See Ben Green's remark below.)

The Problems

The Motivation

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.

Some background

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,$$ 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 A result of Mansour from characteristic functions of sets to functions whose domain is {-1,0,1} is true, it will show shows 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, implies that it will be enough to prove that

$|\hat $|\hat \mu (S)| \le n^{-A}$ 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 $|\hat \mu (\emptyset )|0$. | \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 )|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$ 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}.$$ 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 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 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$ 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 )|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. By 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, 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 )|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 sum { \mu^2(S):|S|hat \mu ^2(S)~:~|S|<(\log n)^A } =o(1),$$ 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 need even less. By a result of Mansour 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 )|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 need even less. By a result of Mansour the inequality $|\hat \mu (S)| \le n^(\log n^{(\log \log n)^A$ n)^A}$ for every $A>0$, would suffice.

Moreover based on

(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. 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 )|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 $| \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 need even less. By a result of Mansour the inequality $|\hat \mu (S)| \le n^(\log \log n)^A$ for every $A>0$, would suffice.

Moreover based on 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) 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 )|0. |0$. (Note that $|\hat \mu (\emptyset)=\sum_{k=0}^{N-1-1}\mu(k)$.) \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 $|\hat \mu (\emptyset)|0$, \emptyset )| < N^{1/2+\epsilon}.$$

Does it follows from the GRH that for some $|\hat c>0$, $$|\hat \mu (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 need even less. By a result of Mansour the inequality $|\hat \mu (S)| \le n^(\log \log n)^A$ for every $A>0$, would suffice.

Moreover based on 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) 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 a follow up on a related to this previous onequestion 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 \sum_{S \subset [n]} |\hat{\mu} 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)|0. \emptyset )|0. (Note that $|\hat \mu (\emptyset)=\sum{k=0}^{N-1-1}\mu(k)$.) \emptyset)=\sum_{k=0}^{N-1-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)|0$, $|\hat \mu (S)|

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 need even less. By a result of Mansour the inequality $|\hat \mu (S)| \le n^(\log \log n)^A$ for every $A>0$, would suffice.

Moreover based on 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) 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 a follow up on a previous one.

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)|0. (Note that $|\hat \mu (\emptyset)=\sum{k=0}^{N-1-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)|0$, $|\hat \mu (S)|

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 need even less. By a result of Mansour the inequality $|\hat \mu (S)| \le n^(\log \log n)^A$ for every $A>0$, would suffice.

Moreover based on a conjecture of Mansour (which also follows from a more general conjecture called the Influence/Entropy conjecture, see this blog post) 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 Allender Saks Shparlinski.