Thue-Morse-Hedlund Sequence

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

We have the generating function identity

[math]\displaystyle{ \sum_{n=0}^{2^k-1} t_n x^n = \prod_{v=0}^{k-1} (1-x^{2^v}). }[/math]

Set [math]\displaystyle{ N=2^{2m}-1 }[/math], which is a multiple of 3. We have

[math]\displaystyle{ (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} }[/math]

We have

[math]\displaystyle{ \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}} }[/math]

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

[math]\displaystyle{ 0=Res[f,0]+Res[f,\omega]+Res[f,\omega^2] }[/math]

with [math]\displaystyle{ f=\frac{\prod_{v=1}^{2m-1}(1-x^{2^v})}{(x-\omega)(x-\omega^2)x^{N+1}} }[/math]. We get

[math]\displaystyle{ 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} }[/math]

[math]\displaystyle{ Res[f,\omega^2] = - 3^{m-1} }[/math]

whence

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

and [math]\displaystyle{ \delta(N,t) = 2 \cdot 3^{m-1} = \frac23 \cdot (N+1)^{\log_4(3)}. }[/math]