Thue-Morse-Hedlund Sequence

2010-08-13T08:04:21Z

Jennie:

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 [http://gowers.wordpress.com/2010/01/06/erdss-discrepancy-problem-as-a-forthcoming-polymath-project/#comment-4775 this comment] and the next one for an easy proof of <math>\gg N^{1/2}</math>

We have the generating function identity

[http://www.casino-virtuelle.com/ casino en ligne]

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

Polymath Wiki - User contributions [en]

Thue-Morse-Hedlund Sequence