# Thue-Morse-Hedlund Sequence

Set $t_n=1$ or $t_n=-1$ according to whether the binary expansion of $n$ has an even or an odd number of `1's. The sequence $(t_n)$ is known as the Thue-Morse-Hedlund sequence. The purpose of this website is to show that $\delta(N,t)\gg N^{\log_4(3)}$. The proof is lifted from Newman (1969). See the discussion following this comment and the next one for an easy proof of $\gg N^{1/2}$

We have the generating function identity

$\sum_{n=0}^{2^k-1} t_n x^n = \prod_{v=0}^{k-1} (1-x^{2^v}).$

Set $N=2^{2m}-1$, which is a multiple of 3. We have

$(1-x^3)^{-1} \prod_{v=0}^{2m-1} (1-x^{2^v}) = \left(\sum_{j=0}^{N/3} t_{3j}\right) x^N + \text{other terms}$

We have

$\sum_{j=0}^{N/3} t_{3j} = \frac{1}{2\pi i} \int_{|x|=1/2} \frac{\prod_v (1-x^{2^v})}{1-x^3} \frac{dx}{x^{N+1}}$

The integrand has poles at 0, $\omega=\exp(2\pi i/3), \omega^2$ (the factor $1-x$ cancels). We can push the contour to a circle of radius $R$, and let $R\to\infty$. As the integrand is $O(R^{-4})$, the limit is 0. In other words,

$0=Res[f,0]+Res[f,\omega]+Res[f,\omega^2]$

with $f=\frac{\prod_{v=1}^{2m-1}(1-x^{2^v})}{(x-\omega)(x-\omega^2)x^{N+1}}$. We get

$Res[f,\omega]=\lim_{x\to\omega} \frac{\prod_{v=1}^{2m-1}(1-x^{2^v})}{(x-\omega^2)x^{N+1}} = \frac{(1-\omega)^{m-1}(1-\omega^2)^m}{(\omega-\omega^2)\omega^{N+1}}=-3^{m-1}$
$Res[f,\omega^2] = - 3^{m-1}$

whence

$\sum_{j=0}^{N/3} t_{3j} = Res[f,0] = 2 \cdot 3^{m-1}$

and $\delta(N,t) = 2 \cdot 3^{m-1} = \frac23 \cdot (N+1)^{\log_4(3)}.$