The Rudin-Shapiro 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 . 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).

6more comments