# Asymptotic frequency of $[0,\,1,\,1]$ in the Thue–Morse sequence

Let $$t_n$$ be the Thue–Morse sequence: $$[\color{blue}{0,\,1,\,1,\,0,}\,\color{red}{1,\,0,\,0,\,1,}\,\color{blue}{1,\,0,\,0,\,1,}\,\color{red}{0,\,1,\,1,\,0,}\,...].\tag1$$ See this question for a definition and formula for $$t_n$$.

Let's split the sequence into non-overlapping runs of length $$3$$: $$[\underline{[\color{blue}{0,\,1,\,1}]},\,[\color{blue}{0,}\,\color{red}{1,\,0}],\,[\color{red}{0,\,1,}\,\color{blue}1],\,[\color{blue}{0,\,0,\,1}],\,\underline{[\color{red}{0,\,1,\,1}]},\,...].\tag2$$ There are $$6$$ different sorts or runs in this sequence: all possible combinations of $$0$$ and $$1$$ except $$[0,\,0,\,0]$$ and $$[1,\,1,\,1]$$ — the Thue–Morse sequence is cube-free.

What is the asymptotic frequency of the $$\underline{[0,\,1,\,1]}$$ run?

Empirically, it seems to be around $$\style{color:#bbbbbb;text-decoration:line-through}{1/5}\,1/6$$, but the convergence is quite slow and erratic.

• For overlapping runs, I think the asymptotic frequency should be $1/6$. How sure are you that for non-overlapping runs it would be $1/5$? How high $n$ did you try? – antkam May 2 at 21:15
• I did a numerical test using the first $67108864$ values of the thue-morse sequence. Computing the fraction of triplets being $[0,1,1]$ among the first $2^n$ triplets. The result was $$\frac{1}{3} 2^{-n-1} \left(2^n+3^{\frac{n+1}{2}}+1\right)$$ for all odd $n$ possible having only the first $67108864$ values of the thue-morse sequence (that is $n\leq 24$). The limit is $1/6$. – Coolwater May 2 at 21:23
• Yes, after checking $3\times10^{11}$ elements I get $0.166668$ as the fraction of $[0,\,1,\,1]$ runs. So, $1/6$ looks more likely. – Vladimir Reshetnikov May 3 at 0:31

## 1 Answer

UPDATE: Some more thoughts at the end on the OP's non-overlapping case, and now I'm not so sure the fraction remains $$1/6$$ any more.

A proof that in the overlapping case the fraction is $$1/6$$.

Let $$a(n) =$$ the number of $$1$$s in the binary expansion of $$n$$. According to wikipedia, the $$n$$th bit of the Thue-Morse sequence $$t_n = 0$$ if $$a(n)$$ is even, and $$t_n = 1$$ if $$a(n)$$ is odd.

Claim: $$[t_n, t_{n+1}, t_{n+2}] = [0,1,1]$$ iff the binary expression of $$n$$ has the form:

$$B0\overbrace{1...1}^{k \ \text{times}}0, \text{also written as: } B01^k0$$

where $$k$$ is even (incl. $$k=0$$) and $$B$$ is any binary sequence (incl. empty sequence) with an even number of $$1$$s.

Proof: First of all, the least significant bit (LSB) of $$n$$ cannot be $$1$$. Assume for future contradiction that $$LSB(n) = 1$$, then $$LSB(n+1) = 0$$ and $$LSB(n+2) = 1$$ and while going from $$n+1$$ to $$n+2$$ all other bits didn't change. So $$t_{n+1} \neq t_{n+2}$$, which contradicts the $$[0,1,1]$$ requirement.

Now that $$LSB(n) = 0$$, we have $$a(n+1) = a(n)+1$$, so $$t_{n+1} \neq t_n$$ as required. Next, consider the longest sequence of $$1$$s preceding the LSB of $$n$$, and say its length is $$k$$. The last $$k+2$$ bits of $$n+1$$ are therefore $$01...1$$ with $$k+1$$ ending $$1$$s. This means the last $$k+2$$ bits of $$n+2$$ are $$10...0$$ with $$k+1$$ ending $$0$$s. The rest of the bits didn't change, so the requirement $$t_{n+2} = t_{n+1} \implies k+1$$ is odd, i.e. $$k$$ is even.

Finally, we can pre-fix with any $$B$$, and we need $$t_n = 0$$, so $$B$$ must have an even number of $$1$$s, which together with an even $$k$$ number of $$1$$s result in an even total no. of $$1$$s. QED

Corollary: In the limit, the fraction of numbers of the form $$B01^k10$$ for a specific $$k$$ is $$2^{-(k+3)}$$. A factor of $$2^{-(k+2)}$$ comes from the requirement that the ending $$k+2$$ bits are specified, and another factor of $$2^{-1}$$ comes from the requirement that $$B$$ must have an even number of $$1$$s. So the total fraction, summed over all even $$k$$, is:

$$\sum_{j=0}^\infty 2^{-(2j+3)} = {1\over 8} \sum_{j=0}^\infty {1\over 4}^j = {1\over 8} {4 \over 3} = {1 \over 6}$$

So this answers the overlapping case.

The non-overlapping case is equivalent to restricting the starting $$n$$ to multiples of $$3$$. Let:

• $$S =$$ the set of values of $$n$$ s.t. the binary expression of $$n$$ is of the form $$B01^k0$$, where $$B$$ has an even number of $$1$$s and $$k$$ is even.

• $$T =$$ the set of non-negative multiples of $$3$$.

Then any $$n \in S \cap T$$ would start a $$[0,1,1]$$ triplet in the OP's non-overlapping sequence.

The OP is asking for the "fraction" $${|S \cap T| \over |T|}$$. If this "fraction" were to remain $${1\over 6}$$, then the "fraction" $${|S\cap T| \over |\mathbb{N}|} = {1 \over 18}$$. Combined with the previous (overlapping) result that $${|S| \over |\mathbb{N}|} = {1 \over 6}$$, this implies $${|S\cap T| \over |S|} = {1 \over 3}$$.

Informally, all this is saying membership in $$S$$ and membership in $$T$$ must be "orthogonal" or "independent". However, IMHO early numerical results are... less independent than I had hoped.

Consider the binary expression $$B01^k0$$ for some $$n \in S$$. Notice that any adjacent pair of digits which are both $$1$$s have a value of $$2q + q$$ for some $$q$$ (a power of $$2$$), and therefore contribute $$0$$ when evaluated mod $$3$$. Obviously, trailing $$0$$s also don't matter. Therefore:

$$k \text{ is even } \implies B01^k0 = B0^{k+2} = B \pmod 3$$

So any $$n = B01^k0 \in S$$ is a multiple of $$3$$ iff $$B$$ (interpreted as a binary number) is a multiple of $$3$$. The only restriction on $$B$$ is that it belongs in the set of "evil" numbers $$E$$:

• $$E =$$ the set of binary strings (or equiv., numbers with binary expressions) with an even number of $$1$$s.

So the question becomes whether $$T$$ and $$E$$ are "orthogonal", i.e. $${|T \cap E| \over |E|} = {1 \over 3}$$? Since $${|E| \over |\mathbb{N}|} = {1 \over 2}$$ this further becomes whether $${|T \cap E| \over |T|} = {1 \over 2}$$?

And this is where the numerical evidence is surprising. According to this OEIS list of "evil" numbers, most of the early multiples-of-$$3$$ are evil! I.e. at least among the early numbers, they are not orthogonal at all.

I tried up to all $$24$$ bit numbers, and found $${|T \cap E| \over |T|} \approx 0.53$$, which is more distant from the "nominal" $$0.5$$ than I expected...