3 deleted 42 characters in body

OK, it seems that a probabilistic swapping argument seems to work 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)$) also lies between $1$ and $x$ and 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$.

2 added 188 characters in body; deleted 32 characters in body; added 51 characters in body

OK, it seems that a probabilistic swapping argument seems to work (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)$) also lies between $1$ and $x$ and 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 $\gg 2^{-\ell} \log 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$.

1

OK, it seems that a probabilistic swapping argument seems to work (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)$) also lies between $1$ and $x$ and 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 $10 \max( \log_2 p, \log_2 q ) + 11$ (say); note from the law of large numbers that there are going to be $\gg \log 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.

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