# Möbius Randomness of the Rudin-Shapiro Sequence

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).

-
It seems natural to start by using the Bourgain-Sarnak-Ziegler criterion to eliminate the Mobius function: terrytao.wordpress.com/2011/11/21/… One then has to understand how multiplication by a fixed prime p affects the binary digits of n, but this seems to be manageable in principle... –  Terry Tao Sep 24 '12 at 22:14
Terry is right. To get more than $o(n)$ cancellation one would need to show that more general bilinear sums involving the Rudin-Shapiro sequence are small, not a tempting task, but probably fairly necessary. I note that it would also be enough to show that a weird variant of the Gowers $U^3$-norm of $\mu$ is small -- not the usual Gowers norm $U^3[N]$, but the norm $U^3[F_2^n]$ in which M\"obius is considered as a function on the binary cube via its binary digits. Not a very natural thing to try and compute. –  Ben Green Sep 24 '12 at 22:22
It also looks natural to try to decouple the low and high bits of n. Indeed, if we write $n = 2^m a + b$ for some natural numbers $a,b$ with $0 \leq b < 2^m$ and some well chosen cutoff parameter $m$, then we have $WS(n) = WS(a) WS(b) (-1)^{a_0 b_{m-1}}$, thus almost entirely decoupling the $a$ and $b$ components. It's then tempting to estimate a sum such as $\sum_{n \leq x} WS(pn) WS(qn)$ for fixed distinct primes $p,q$ by performing such a splitting (with $2^m$ a little bit less than $x$), and using a Cauchy-Schwarz to kill off the low bit component. –  Terry Tao Sep 24 '12 at 23:34
An alternative approach would be to understand the joint distribution of $WS(pn)$ and $WS(qn)$ of some binary string $n = \epsilon_0 + \ldots + 2^k \epsilon_k$ by looking at the dynamics of the evolution of $WS(pn_j), WS(qn_j)$ for $0 \leq j \leq k$, where $n_j := \epsilon_0 + \ldots + 2^j \epsilon_j$. It looks like this dynamics is basically some sort of finite Markov chain (as can be seen by deconstructing the long multiplication algorithm in binary, noting that it can be performed in a streaming fashion with only O(1) memory), if we view the digits $\epsilon_j$ as iid Bernoulli variables. –  Terry Tao Sep 24 '12 at 23:38
(Actually, it's more of a random walk on a finite graph than a finite Markov chain.) One should be able to establish asymptotic convergence in k to an equilibrium measure (at least in the model case when $x$ is a power of 2 - otherwise one has to work a little harder), and then one just has to take the expectation of $WS(pn) WS(qn)$ wrt this equilibrium measure, I think, to get the desired cancellation. –  Terry Tao Sep 24 '12 at 23:44

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$.

-
Incidentally, extension to more general polynomials than Rudin-Shapiro looks possible, though complicated. Instead of comparing a pair $n,n'$ of random variables caused by flipping one set of bits that is "insulated" from the rest of the bitstring by lots of zeroes, one should consider a sufficiently high-dimensional cube of such random variables, such that the top-order contributions to $WS(pn) WS(qn)$ are suitably non-trivial. It should then be possible to use Ramsey theory to kill off all lower order terms (an argument of Alon and Beigel) and get some cancellation. –  Terry Tao Sep 25 '12 at 2:29
Impressive! Thanks a lot. –  Gil Kalai Sep 27 '12 at 1:13