Thue-Morse-Hedlund Sequence

From Polymath1Wiki
Jump to: navigation, search

Set [math]t_n=1[/math] or [math]t_n=-1[/math] according to whether the binary expansion of [math]n[/math] has an even or an odd number of `1's. The sequence [math](t_n)[/math] is known as the Thue-Morse-Hedlund sequence. The purpose of this website is to show that [math]\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]\gg N^{1/2}[/math]

We have the generating function identity

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

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

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

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

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

[math]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]Res[f,\omega^2] = - 3^{m-1}[/math]

whence

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

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