The [Rudin-Shapiro sequence](http://en.wikipedia.org/wiki/Rudin%E2%80%93Shapiro_sequence) (also known as the Golay-Rudin-Shapiro sequence) is defined as follows.


Let $a\_n = \sum \epsilon\_i\epsilon\_{i+1}$ where $\epsilon\_1,\epsilon\_2,\dots$ are the digits in the binary expansion of $n$.
$WS(n)$, the $n$th term of the Rudin Shapiro sequence is defined by $$WS(n)=(-1)^{a\_n}.$$


Question:
---------


Prove that $$\sum\_{i=0}^n WS(i) \mu (i) = o(n).$$


Here, $\mu(n)$ is the Möbius function.


Motivation
----------


This question continues a one-year old question [walsh-fourier-transform-of-the-mobius-function](https://mathoverflow.net/questions/57543/walsh-fourier-transform-of-the-mobius-function). The two parts of the old question on "Mobius randomness" was settled by Green and by Bourgain, respectively. This question represent the simplest case, which is quite important in its own right, where some new idea/method may be needed.


Motivation (2)
--------------


Under the translation 0 --> 1, 1 --> -1, the "Walsh-Fourier" functions can be considered as (all) linear functions over Z/2Z. It tuned out that proving Mobius randomness for a few of them suffices to deduce Mobious randomness for $AC^0$ functions. This was the second part of our old question that was proved by Green. Bourgain showed Mobius randomness for all Walsh functions (namely all linear functions over Z/2Z.) What about low degree polynomials instead of linear polynomials? The Rudin-Shapiro sequence represent a very simple example of quadratic polynomial.


If we can extend the results to polynomials over Z/2Z of degree at most polylog (n) this will imply by a result of Razborov Mobius randomness for $AC^0(2)$ circuits. (This is interesting also under GRH).



Möbius Randomness of the Rudin-Shapiro Sequence
OK, it seems that a probabilistic swapping argument works (and is simpler than the two other suggestions I made above).


Firstly, by the Bourgain-Sarnak-Ziegler criterion (Proposition 1 in <http://terrytao.wordpress.com/2011/11/21/the-bourgain-sarnak-ziegler-orthogonality-criterion/> ), it suffices to show that


$$ \sum\_{n \leq x} WS(pn) WS(qn) = o(x)$$


for all fixed distinct primes $p$, $q$, and in the limit $x \to \infty$. 


Fix $p,q,x$. We phrase things probabilistically. Let $n$ be a random integer between $1$ and $x$; the objective is to show that


$$ {\bf E} WS(pn) WS(qn) = o(1) \quad\quad (1).$$


The way we will do this is to construct a new random variable $n'$, coupled with $n$, which asymptotically almost surely (i.e. with probability $1-o(1)$) is such that
$$ WS(pn) WS(qn) = - WS(pn') WS(qn') \quad\quad (2) $$
aas. Also, the total variation distance between the distribution of $n$ and the distribution of $n'$ will be established to be $o(1)$, so that
$$ {\bf E} WS(pn) WS(qn) = {\bf E} WS(pn') WS(qn') + o(1).$$
Putting these facts together will give the claim (1).


It remains to construct $n'$ with the desired properties. For simplicity let us begin with the case when $WS(p) = -WS(q)$. Then to obtain $n'$ from $n$, what one does is scan the binary expansion of $n$ for a block of zeroes of length at least $\ell := 10 \max( \log\_2 p, \log\_2 q ) + 11$ (say); note from the law of large numbers that there are going to be about $2^{-\ell} \log\_2 x$ such blocks aas. We randomly select one of these blocks, and flip the middle zero in this block to a one to create $n'$. A bit of thought (using the long multiplication algorithm) shows that $WS(pn') = WS(pn) WS(p)$ and $WS(qn') = WS(qn) WS(q)$, giving (2) since $WS(p) = -WS(q)$. A rather tedious double counting involving the Chernoff inequality (which I will omit here) also shows that the distribution of n' is within o(1) in total variation to that of n, giving the claim. (The point is that the indegrees and outdegrees of the edit graph connecting potential $n$s to potential $n'$s both concentrate around the same quantity, namely $2^{-\ell} \log\_2 x$.)


Of course, it could happen that $WS(p)=WS(q)$ instead. But a variant of the above argument will work as long as one can find at least one natural number $a$ for which $WS(ap) = -WS(aq)$, basically one has to insert in the binary expansion of $a$ in the middle of a sufficiently large block of zeroes of $n$ to make $n$, rather than flipping a single bit. So the only way things can go wrong is if the primes $p,q$ are such that $WS(ap)=WS(aq)$ for all natural numbers $a$ (i.e. if there is absolutely no cancellation at all in $\sum\_{n \leq x} WS(pn) WS(qn)$. This can be eliminated as follows. Without loss of generality we have $p > q$ and $p$ odd. Then we can find $n,k$ such that $qn < 2^k < pn < 2^{k+1}$. We observe that


$$ WS(p (n+2^{k+1}) ) = - WS(pn) WS(p)$$


and


$$ WS(q (n+2^{k+1}) ) = WS(qn) WS(q)$$


and so we cannot have $WS(ap)=WS(aq)$ for all $a$.


