9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – antkam May 2 at 21:15
  • 2
    $\begingroup$ 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$. $\endgroup$ – Coolwater May 2 at 21:23
  • $\begingroup$ 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. $\endgroup$ – Vladimir Reshetnikov May 3 at 0:31
4
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.