The level of distribution of the Thue–Morse sequence
Lukas Spiegelhofer
Vienna University of Technology

May 24, 2018
Numeration 2018, Paris

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

May 24, 20181 / 24

Section 1
The Thue–Morse sequence

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

May 24, 20182 / 24

The Thue–Morse sequence(1) Start with t(0) = 0 and let t(k+1) be the concatenation of t(k) and its
Boolean complement t(k) .
t(0) = 0t(1) = 01t(2) = 0110
t(3) = 01101001
t(4) = 0110100110010110
t(5) = 01101001100101101001011001101001
The Thue–Morse sequence t is the pointwise limit of this sequence.
(2) By induction, it follows that t is the fixed point of the substitution
0 7→ 01, 1 7→ 10that starts with 0.
Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

May 24, 20183 / 24

The Thue–Morse sequence, continued(3) A third description uses the binary sum of digits function s:s(ε0 20 + · · · + εν 2µ ) = ε0 + · · · + εν for εi ∈ {0, 1}.
We have t(n) = 0 if and only if s(n) ≡ 0 mod 2. In the proofs, wework with (−1)s(n) .
(4) The Thue–Morse sequence is one of the simplest automaticsequences:
00
1

01
1

We feed in the binary expansion of n and obtain a letter ∈ {0, 1}.

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

May 24, 2018

4 / 24

The Thue–Morse sequence, continued

A less well-known characterization uses the Koch snowflake curve.
(5) The sequence n 7→ (−1)s(n) e(−n/3) describes the orientation of thenth segment in the unscaled snowflake curve (where e(x) = e 2πix ):The snowflake curve is the Thue–Morse sequence in disguise.

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

May 24, 2018

5 / 24

Thue–Morse, 16 × 16.

The Thue–Morse sequence has low subword complexity: if p(L) denotes
the number of (contiguous) subwords of length L, then p(L) ≤ CL forsome constant C . This is true for any automatic sequence. Here C ≤ 8.
Lukas Spiegelhofer (TU Vienna)Level of distribution of the Thue–Morse sequence

May 24, 2018

6 / 24

Thue–Morse along arithmetic progressions↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓↓

011010011001011010010110011010011001011001101001011010 . . .

Theorem (Gelfond 1968)
Let d ≥ 1 and a be integers. There is an absolute λ < 1 such that
{1 ≤ n ≤ x : t(n) = 0, n ≡ a mod d} =x+ O xλ .
2dThat is, for all d ≥ 1 and a < d we haveX(−1)s(md+a) ≤ CM λ .
1≤m≤MThe Thue–Morse sequence shows cancellation along arithmetic
progressions.

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

May 24, 20187 / 24

The error term for sums over APs

I However, we cannot not get a uniform constant C for all d and a.

This is the case because there are arbitrarily long arithmetic
progressions on which t is constant.
I Two ways to see this:

1. Let d = 2λ + 1. Then 2 | s(md) for all m < 2λ .
2. van der Waerden’s theorem.
I Therefore we look at a certain average over d.

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

May 24, 20188 / 24

Section 2
The level of distribution

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

May 24, 2018

9 / 24

The averaged error term
Theorem (Fouvry–Mauduit 1996)
Xmax
max
y ,z

1≤d≤D z−y ≤x0≤a<dselects the “worst” APX(−1)s(n) ≤ Cx 1−ηy ≤n<zn≡a mod dfor some η > 0 and D = x 0.5924 .
observed − expected
I The number 0.5924 is a level of distribution of the Thue–Morsesequence.
I Note that we have “trivial” summands (of size  x/d) ford = 2λ + 1, where x ≤ 22λ . These don’t matter in the sum.

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

May 24, 201810 / 24

The level of distribution of the Thue–Morse sequence
Theorem (S. 2018+)
The Thue–Morse sequence has level of distribution 1. More precisely, let
0 < ε < 1. There exist η > 0 and C such thatXmax
max
y ,z1≤d≤D z−y ≤x0≤a<dX(−1)s(n) ≤ Cx 1−ηy ≤n<zn≡a mod dfor D = x 1−ε .
I This is a statement on sparse arithmetic progressions: theThue–Morse sequence usually shows cancellation along N-termarithmetic progressions having common difference ∼ N R , whereR > 0 is arbitrary (R ≤ 1.46 for Fouvry–Mauduit).
Open problem. What about D = x(log x)−A ?
Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

May 24, 201811 / 24

CorollaryFor d ≥ 1, a ≥ 0 define md,a = min{n : t(nd + a) = 1}.
For each ε > 0 we have{d < D : max md,a ≥ d ε } = o(D).
a≥0That is, the first 1 in an arithmetic progression is not far away for most d.
Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

May 24, 201812 / 24

Sparse arithmetic subsequences of tt along short arithmetic subsequences even seems to behave randomly.

does every pattern occur?

N = 128 × 128 terms, common difference N R = 321
We know that arbitrarily long sequences of 0s appear as arithmetic
subsequences of t. What about other sequences?
Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

May 24, 201813 / 24

Does every pattern occur?

Theorem (Müllner, S. 2017)
Every finite sequence over {0, 1} appears as an arithmetic subsequence ofthe Thue–Morse sequence.
Added after the talk: Avgustinovich, Fon-Der-Flaass, and Frid proved thisin 2000! ; search for “arithmetical complexity”.
However: for given d and a, there are always blocks that do not occur int(nd + a), since the subword complexity is at most linear!
; consider sparse infinite subsequences of t.

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

May 24, 201814 / 24Section 3
Sparse infinite subsequences of Thue–MorseLukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

May 24, 201815 / 24

Subsequences of t
We wish to study t along subsequences of asymptotic density 0 and show(simple) normality of such subsequences (Knuth’s R1 and R2).
Candidates:
I Polynomials with values in N
Gelfond problems
I Prime numbers
I 3nI bf (n)c for fsatisfying some growth conditions. For example,
Piatetski-Shapiro sequences bnc c.

Theorem (Corollary of Mauduit–Rivat 2009, Acta Math.)
The Thue–Morse sequence along the sequence of squares is simply normal.
Notorious open problem: t(n3 ).

Theorem (Corollary of Mauduit–Rivat 2010, Ann. of Math.)
The Thue–Morse sequence along the primes is simply normal.
Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

May 24, 201816 / 24

Subsequences of t
I Related to t(3n ) is the following (hard) problem: is the sequence of
fractional parts of (3/2)n dense in [0, 1]?

In both cases: study the binary expansion of 3n =n k0≤k≤n k 2 .

P

I The sum of digits of bnc c is an approximation to the problem “thesum of digits of n2 ”, which could not be handled at first.

Theorem (Corollary of Mauduit–Rivat 2005)
Let 1 < c < 1.4. There exists an η > 0 such thatXc(−1)s(bn c)  x 1−η .
1≤n≤x

In particular, for 1 < c < 1.4, the sequence n 7→ t(bnc c) is simply
normal.

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

May 24, 201817 / 24

The Thue–Morse sequence along sparse subsequences
Theorem (S. 2014)
The Thue–Morse sequence along bnc c is simply normal for 1 < c ≤ 1.42.
Note that 1.42 is larger than 1.4 by “two cents”.

Theorem (Drmota–Mauduit–Rivat 2018)
The Thue–Morse sequence along the sequence of squares is normal: every
block B ∈ {0, 1}k appears as a subword with asymptotic frequency 1/2k .

Theorem (S. 2015)
The Thue–Morse sequence along bnc c is normal for 1 < c < 4/3.

Theorem (Müllner–S. 2017)
The Thue–Morse sequence along bnc c is normal for 1 < c < 1.5.

Theorem (S. 2018+)
The Thue–Morse sequence along bnc c is simply normal for 1 < c < 2.
Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

May 24, 201818 / 24

Piatetski-Shapiro via Beatty sequences
The question on bnc c can be reduced to the linear case by Taylor
approximation. This simplification comes at the cost of shorter sums.
120
Exact approximation for
most integers in an interval

100806040

20

b1.6860n − 38.1826c0.06n1.7

n020n0 = 55

80

For c → 2, the slope f 0 (n) is a large power of the length of theapproximation interval.
Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

May 24, 201819 / 24

Piatetski-Shapiro via Beatty sequences
Proposition (S. 2014)
We write f (x) = x c , where 1 < c < 2 is a real number. There exists a
constant C such that for all N ≥ 2 and K > 0 we have
1NXs(bnc c)(−1)

≤ CN<n≤2N(log N)2 J(f 0 (N), K )f (N)K ++K
f 0 (N)K002

,

f 0 (N) a large power of K for c close to 2whereZ 2D
J(D, K ) =max
Dβ≥0X(−1)s(bnα+βc) dα.

0≤n<KI The problem “simple normality” is reduced to a Beatty sequence

version of our main theorem!
I The proof of this new statement is analogous to the main theorem.
Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

May 24, 201820 / 24Section 4“Proof” of the main theorem

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

May 24, 201821 / 24

van der Corput’s inequality
In the proof of the main theorem we make use of van der Corput’sinequality:

Lemma
Let I be a finite interval containing N integers and let an be a complex
number for n ∈ I . For all integers K ≥ 1 and R ≥ 1 we have2Xn∈Ian

N + K (R − 1) X
≤R

|r |<R X|r |1−an+Kr an .
Rn∈In+Kr ∈I

Instead of the original sum, we now have to estimate certain correlations(where KR will be small compared to N).

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

May 24, 201822 / 24

Reducing the number of significant digits

I Iterating van der Corput’s inequality, we introduce “multiplecorrelations”, while reducing step by step the number of digits thathave to be considered.
I We have to estimate

XX

1e
2
ρ

r1 ,...,rm <2ρ 0≤n<2X
Xsρ n +εi ri 

ε1 ,...,εm ∈{0,1}1≤i≤mI This is a Gowers norm for the Thue–Morse sequence. An estimate ofa very similar expression was given by Konieczny (2017). This finishes
our “proof”.

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

May 24, 201823 / 24

Thank you!

1

1

Supported by the FWF–ANR joint project MuDeRa

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

May 24, 201824 / 24