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

October 2
UDT 2018, CIRM

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 20181 / 23

Section 1
The Thue–Morse sequence

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 20182 / 23

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) = 01
t(2) = 0110
t(3) = 01101001
t(4) = 0110100110010110
t(5) = 01101001100101101001011001101001
The Thue–Morse sequence t is the pointwise limit of this sequence.

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 20183 / 23

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) = 01
t(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

October 2, 20183 / 23

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 tn = 0 if and only if s(n) ≡ 0 mod 2.

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 2018

4 / 23

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 tn = 0 if and only if s(n) ≡ 0 mod 2.
(4) The Thue–Morse sequence is one of the simplest automaticsequences:
0

0
1

0

1
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

October 2, 2018

4 / 23

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 line segment in the unscaled snowflake curve (wheree(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

October 2, 2018

5 / 23

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, in
fact lim supL→∞ p(L)/L = 10/3.
Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 2018

6 / 23

Thue–Morse along arithmetic progressions
↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

011010011001011010010110011010011001011001101001011010

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 20187 / 23

Thue–Morse along arithmetic progressions
↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

011010011001011010010110011010011001011001101001011010

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 20187 / 23

Thue–Morse along arithmetic progressions
↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

↓

011010011001011010010110011010011001011001101001011010

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 20187 / 23

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 : tn = 0, n ≡ a mod d} =Lukas Spiegelhofer (TU Vienna)

x+ O xλ .
2dLevel of distribution of the Thue–Morse sequence

October 2, 20187 / 23

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

October 2, 20187 / 23

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 : tn = 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.
Open problem: For k given, determine the subword complexity of tnk .
Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 20187 / 23

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.

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 20188 / 23

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.

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 20188 / 23

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

October 2, 20188 / 23

Section 2
The level of distribution

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 2018

9 / 23

The averaged error term
Theorem (Fouvry–Mauduit 1996)
X

max
max
y ,z

1≤d≤D z−y ≤x

0≤a<d

X

(−1)s(n) ≤ Cx 1−ηy ≤n<zn≡a mod dfor some η > 0 and D = x 0.5924 .

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 201810 / 23

The averaged error term
Theorem (Fouvry–Mauduit 1996)
X

max
max
y ,z

1≤d≤D z−y ≤x

0≤a<d

X

(−1)s(n) ≤ Cx 1−ηy ≤n<zn≡a mod dfor some η > 0 and D = x 0.5924 .
observed − expected

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 201810 / 23

The averaged error term
Theorem (Fouvry–Mauduit 1996)
X

max
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.

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 201810 / 23

The averaged error term
Theorem (Fouvry–Mauduit 1996)
X

max
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

October 2, 201810 / 23

The averaged error term
Theorem (Fouvry–Mauduit 1996)
X

max
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.

Theorem (Müllner, S. 2017)
The Thue–Morse sequence has level of distribution 2/3.
Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 201810 / 23

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 that
X

max
max
y ,z

1≤d≤D z−y ≤x

0≤a<d

X

(−1)s(n) ≤ Cx 1−ηy ≤n<zn≡a mod dfor D = x 1−ε .

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 201811 / 23

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 that
X

max
max
y ,z

1≤d≤D z−y ≤x

0≤a<d

X

(−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 , where R > 0
is arbitrary (R ≤ 1.46 for Fouvry–Mauduit, R < 2 for Müllner–S.).

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 201811 / 23

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 that
X

max
max
y ,z

1≤d≤D z−y ≤x

0≤a<d

X

(−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 , where R > 0
is arbitrary (R ≤ 1.46 for Fouvry–Mauduit, R < 2 for Müllner–S.).
Open problem. What about D = x(log x)−A ? This corresponds to N-termεAPs with common difference ∼ e N for some ε > 0. Where is the limit?
Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 201811 / 23

Sparse arithmetic subsequences of tt along short arithmetic subsequences even seems to behave randomly.
Such sequences even seem to pass most standard tests for PRNGs. Also,
such a PRNG is reasonably fast on CPUs with POPCNT instruction.

Figure: N = 64 × 64 terms, common difference N R = 321
Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 201812 / 23

Does every pattern occur?
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

October 2, 201813 / 23

Does every pattern occur?
We know that arbitrarily long sequences of 0s appear as arithmetic
subsequences of t. What about other sequences?

Theorem (Special case of Avgustinovich, Fon-Der-Flaass, and Frid,2000)
Every finite sequence over {0, 1} appears as an arithmetic subsequence of
the Thue–Morse sequence.
That is, the Thue–Morse sequence has full arithmetic complexity.

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 201813 / 23

Does every pattern occur?
We know that arbitrarily long sequences of 0s appear as arithmetic
subsequences of t. What about other sequences?

Theorem (Special case of Avgustinovich, Fon-Der-Flaass, and Frid,2000)
Every finite sequence over {0, 1} appears as an arithmetic subsequence of
the Thue–Morse sequence.
That is, the Thue–Morse sequence has full arithmetic complexity.
I This also follows from results by Konieczny (2017).

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 201813 / 23

Does every pattern occur?
We know that arbitrarily long sequences of 0s appear as arithmetic
subsequences of t. What about other sequences?

Theorem (Special case of Avgustinovich, Fon-Der-Flaass, and Frid,2000)
Every finite sequence over {0, 1} appears as an arithmetic subsequence of
the Thue–Morse sequence.
That is, the Thue–Morse sequence has full arithmetic complexity.
I This also follows from results by Konieczny (2017).
I Müllner and S. (2017) re-proved this (the third time), showing thestronger statement that each block ω ∈ {0, 1}L occurs with almost

the right frequency in (tnd+a )n<N for most d ∼ N 2−ε .

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 201813 / 23

Does every pattern occur?
We know that arbitrarily long sequences of 0s appear as arithmetic
subsequences of t. What about other sequences?

Theorem (Special case of Avgustinovich, Fon-Der-Flaass, and Frid,2000)
Every finite sequence over {0, 1} appears as an arithmetic subsequence of
the Thue–Morse sequence.
That is, the Thue–Morse sequence has full arithmetic complexity.
I This also follows from results by Konieczny (2017).
I Müllner and S. (2017) re-proved this (the third time), showing thestronger statement that each block ω ∈ {0, 1}L occurs with almost

the right frequency in (tnd+a )n<N for most d ∼ N 2−ε .
I However: for given d and a, there are always blocks that do not occur

in tnd+a , since the subword complexity is at most linear! These
sequences are therefore not normal sequences.
; consider sparse infinite subsequences of t.
Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 201813 / 23

Section 3
Sparse infinite subsequences of Thue–Morse

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 201814 / 23

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

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 201815 / 23

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

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 201815 / 23

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

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

Theorem (Special case 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

October 2, 201815 / 23

Subsequences of t

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

Theorem (Special case 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→ tbnc c is simply normal.

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 201816 / 23

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”.

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 201817 / 23

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.

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 201817 / 23

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

October 2, 201817 / 23

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
100
80
60
40



20

b1.6860n − 38.1826c

0.06n1.7



n

0
20

n0 = 55

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence80

October 2, 201818 / 23

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

100
80
60
40



20

b1.6860n − 38.1826c

0.06n1.7



n

0
20

n0 = 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

October 2, 201818 / 23

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 have1NXs(bnc c)

(−1)


≤ C

N<n≤2N

where(log N)2 J(f 0 (N), K )f (N)K ++K
f 0 (N)KZ 2D
J(D, K ) =max
DLukas Spiegelhofer (TU Vienna)

β≥0

00

2

X


,

(−1)s(bnα+βc) dα.

0≤n<K

Level of distribution of the Thue–Morse sequence

October 2, 201819 / 23

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 have1NXs(bnc c)

(−1)


≤ C

N<n≤2N(log N)2 J(f 0 (N), K )f (N)K ++K
f 0 (N)K
00

2


,

f 0 (N) a large power of K for c close to 2

where

Z 2D
J(D, K ) =max
DLukas Spiegelhofer (TU Vienna)

β≥0X(−1)s(bnα+βc) dα.

0≤n<K

Level of distribution of the Thue–Morse sequence

October 2, 201819 / 23

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 have1NXs(bnc c)

(−1)


≤ C

N<n≤2N(log N)2 J(f 0 (N), K )f (N)K ++K
f 0 (N)K
00

2


,

f 0 (N) a large power of K for c close to 2

where

Z 2D
J(D, K ) =

max
D

β≥0

X

(−1)s(bnα+βc) dα.

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

version of our main theorem!

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 201819 / 23

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 have1NXs(bnc c)

(−1)


≤ C

N<n≤2N(log N)2 J(f 0 (N), K )f (N)K ++K
f 0 (N)K
00

2


,

f 0 (N) a large power of K for c close to 2

where

Z 2D
J(D, K ) =

max
D

β≥0

X

(−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

October 2, 201819 / 23

Section 4“Proof” of the main theorem

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 201820 / 23van der Corput’s inequality
In the proof of the main theorem we make use of van der Corput’s
inequality:

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 have
2

X
n∈I

an

N + K (R − 1) X≤
R

Lukas Spiegelhofer (TU Vienna)|r |<R

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

Level of distribution of the Thue–Morse sequence

October 2, 201821 / 23van der Corput’s inequality
In the proof of the main theorem we make use of van der Corput’s
inequality:

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 have
2

X
n∈I

an

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

October 2, 201821 / 23

Reducing the number of significant digits

I Iterating van der Corput’s inequality, we introduce “multiple

correlations”, while reducing step by step the number of digits thathave to be considered.

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 201822 / 23

Reducing the number of significant digits

I Iterating van der Corput’s inequality, we introduce “multiple

correlations”, while reducing step by step the number of digits thathave to be considered.
I We have to estimate


X

X

1
e
2
ρ

r1 ,...,rm <2ρ 0≤n<2

Lukas Spiegelhofer (TU Vienna)

X




X
sρ n +
εi ri ε1 ,...,εm ∈{0,1}1≤i≤mLevel of distribution of the Thue–Morse sequence

October 2, 201822 / 23

Reducing the number of significant digits

I Iterating van der Corput’s inequality, we introduce “multiple

correlations”, while reducing step by step the number of digits thathave to be considered.
I We have to estimate


X

X

1
e
2
ρ

r1 ,...,rm <2ρ 0≤n<2

X




X
sρ n +
εi ri ε1 ,...,εm ∈{0,1}1≤i≤m

I 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

October 2, 201822 / 23

Thank you!

1

1

Supported by the FWF–ANR joint project MuDeRa

Lukas Spiegelhofer (TU Vienna)

Level of distribution of the Thue–Morse sequence

October 2, 201823 / 23