The Rudin-Shapiro sequence and similar
sequences are normal along squares
Clemens Müllner

Tuesday, October 2nd, 2018

Clemens Müllner

Digital sequences along squares are normal

2. 10. 20181 / 10Sum of digits
Let q ≥ 2 be a base.
n=rX(q)εj (n)q j ,j=0(q)

where εj (n) ∈ {0, . . . , q − 1} and r = blogq (n)c.
Definition
We define the sum of digits function sq (n)rX(q)
sq (n) :=εj (n).
j=0Clemens Müllner

Digital sequences along squares are normal

2. 10. 20182 / 10Sum of digits
Let q ≥ 2 be a base.
n=rX(q)εj (n)q j ,j=0(q)

where εj (n) ∈ {0, . . . , q − 1} and r = blogq (n)c.
Definition
We define the sum of digits function sq (n)rX(q)
sq (n) :=εj (n).
j=0

Clemens Müllner

Digital sequences along squares are normal

2. 10. 20182 / 10Sum of digits
Let q ≥ 2 be a base.
n=rX(q)εj (n)q j ,j=0(q)

where εj (n) ∈ {0, . . . , q − 1} and r = blogq (n)c.
Definition
We define the sum of digits function sq (n)rX(q)
sq (n) :=εj (n).
j=0Clemens Müllner

Digital sequences along squares are normal

2. 10. 20182 / 10Gelfond
Let q ≥ 2 and m such that gcd(q − 1, m) = 1.
Theorem (Gelfond 1967)(sq (an + b) mod m)n∈N is simply normal.
2. Gelfond Problem(sq (p) mod m)p∈P is simply normal.
Solved by Mauduit and Rivat in 2010.
3. Gelfond Problem
Let P(x) be a polynomial with integer coefficients.
Then (sq (P(n)) mod m)n∈N is simply normal.
Solved by Mauduit and Rivat in 2009 for P(n) = n2 .
Drmota, Mauduit and Rivat (2018): (s2 (n2 ) mod 2)n∈N is normal!
Clemens Müllner

Digital sequences along squares are normal

2. 10. 20183 / 10Gelfond
Let q ≥ 2 and m such that gcd(q − 1, m) = 1.
Theorem (Gelfond 1967)(sq (an + b) mod m)n∈N is simply normal.
2. Gelfond Problem(sq (p) mod m)p∈P is simply normal.
Solved by Mauduit and Rivat in 2010.
3. Gelfond Problem
Let P(x) be a polynomial with integer coefficients.
Then (sq (P(n)) mod m)n∈N is simply normal.
Solved by Mauduit and Rivat in 2009 for P(n) = n2 .
Drmota, Mauduit and Rivat (2018): (s2 (n2 ) mod 2)n∈N is normal!
Clemens Müllner

Digital sequences along squares are normal

2. 10. 20183 / 10Gelfond
Let q ≥ 2 and m such that gcd(q − 1, m) = 1.
Theorem (Gelfond 1967)(sq (an + b) mod m)n∈N is simply normal.
2. Gelfond Problem(sq (p) mod m)p∈P is simply normal.
Solved by Mauduit and Rivat in 2010.
3. Gelfond Problem
Let P(x) be a polynomial with integer coefficients.
Then (sq (P(n)) mod m)n∈N is simply normal.
Solved by Mauduit and Rivat in 2009 for P(n) = n2 .
Drmota, Mauduit and Rivat (2018): (s2 (n2 ) mod 2)n∈N is normal!
Clemens Müllner

Digital sequences along squares are normal

2. 10. 20183 / 10Gelfond
Let q ≥ 2 and m such that gcd(q − 1, m) = 1.
Theorem (Gelfond 1967)(sq (an + b) mod m)n∈N is simply normal.
2. Gelfond Problem(sq (p) mod m)p∈P is simply normal.
Solved by Mauduit and Rivat in 2010.
3. Gelfond Problem
Let P(x) be a polynomial with integer coefficients.
Then (sq (P(n)) mod m)n∈N is simply normal.
Solved by Mauduit and Rivat in 2009 for P(n) = n2 .
Drmota, Mauduit and Rivat (2018): (s2 (n2 ) mod 2)n∈N is normal!
Clemens Müllner

Digital sequences along squares are normal

2. 10. 20183 / 10GelfondLet q ≥ 2 and m such that gcd(q − 1, m) = 1.
Theorem (Gelfond 1967)(sq (an + b) mod m)n∈N is simply normal.
2. Gelfond Problem(sq (p) mod m)p∈P is simply normal.
Solved by Mauduit and Rivat in 2010.
3. Gelfond Problem
Let P(x) be a polynomial with integer coefficients.
Then (sq (P(n)) mod m)n∈N is simply normal.
Solved by Mauduit and Rivat in 2009 for P(n) = n2 .
Drmota, Mauduit and Rivat (2018): (s2 (n2 ) mod 2)n∈N is normal!
Clemens Müllner

Digital sequences along squares are normal

2. 10. 20183 / 10GelfondLet q ≥ 2 and m such that gcd(q − 1, m) = 1.
Theorem (Gelfond 1967)(sq (an + b) mod m)n∈N is simply normal.
2. Gelfond Problem(sq (p) mod m)p∈P is simply normal.
Solved by Mauduit and Rivat in 2010.
3. Gelfond Problem
Let P(x) be a polynomial with integer coefficients.
Then (sq (P(n)) mod m)n∈N is simply normal.
Solved by Mauduit and Rivat in 2009 for P(n) = n2 .
Drmota, Mauduit and Rivat (2018): (s2 (n2 ) mod 2)n∈N is normal!
Clemens Müllner

Digital sequences along squares are normal

2. 10. 20183 / 10Pattern-counting function

Definition (Pattern-counting function)
Fix ` ≥ 1 and a pattern
P = (p0 , . . . , p`−1 ) ∈ {0, . . . , q − 1}` , P 6= (0, . . . , 0).
Then we define the pattern-counting functionfP (n) =rX
−`+1
j=0

1[(ε(q)(q)j+`−1 (n),...,εj (n))=P].

Rudin-Shapiro: (f11 (n) mod 2)n∈N .

Clemens Müllner

Digital sequences along squares are normal

2. 10. 20184 / 10Pattern-counting function

Definition (Pattern-counting function)
Fix ` ≥ 1 and a pattern
P = (p0 , . . . , p`−1 ) ∈ {0, . . . , q − 1}` , P 6= (0, . . . , 0).
Then we define the pattern-counting functionfP (n) =rX
−`+1
j=0

1[(ε(q)(q)j+`−1 (n),...,εj (n))=P].

Rudin-Shapiro: (f11 (n) mod 2)n∈N .

Clemens Müllner

Digital sequences along squares are normal

2. 10. 20184 / 10Pattern-counting function

Definition (Pattern-counting function)
Fix ` ≥ 1 and a pattern
P = (p0 , . . . , p`−1 ) ∈ {0, . . . , q − 1}` , P 6= (0, . . . , 0).
Then we define the pattern-counting functionfP (n) =rX
−`+1
j=0

1[(ε(q)(q)j+`−1 (n),...,εj (n))=P].

Rudin-Shapiro: (f11 (n) mod 2)n∈N .

Clemens Müllner

Digital sequences along squares are normal

2. 10. 20184 / 10Block-additive function
Definition (Block-additive function)
We say that b : N → Z is block-additive / digital if there exists` ≥ 1 and F : {0, . . . , q − 1}` → Z such that F (0, . . . , 0) = 0 andX(q)(q)b(n) =F (εj+`−1 (n), . . . , εj (n)),
j∈Zwhere εj (n) = 0 for j ∈/ {0, . . . , r }.
A block-additive function is (almost) a linear combination ofpattern-counting functions.
Proposition
Block-additive functions modm give automatic sequences.
Clemens Müllner

Digital sequences along squares are normal

2. 10. 2018

5 / 10Block-additive function
Definition (Block-additive function)
We say that b : N → Z is block-additive / digital if there exists` ≥ 1 and F : {0, . . . , q − 1}` → Z such that F (0, . . . , 0) = 0 andX(q)(q)b(n) =F (εj+`−1 (n), . . . , εj (n)),
j∈Zwhere εj (n) = 0 for j ∈/ {0, . . . , r }.
A block-additive function is (almost) a linear combination ofpattern-counting functions.
Proposition
Block-additive functions modm give automatic sequences.
Clemens Müllner

Digital sequences along squares are normal

2. 10. 2018

5 / 10Block-additive function
Definition (Block-additive function)
We say that b : N → Z is block-additive / digital if there exists` ≥ 1 and F : {0, . . . , q − 1}` → Z such that F (0, . . . , 0) = 0 andX(q)(q)b(n) =F (εj+`−1 (n), . . . , εj (n)),
j∈Zwhere εj (n) = 0 for j ∈/ {0, . . . , r }.
A block-additive function is (almost) a linear combination ofpattern-counting functions.
Proposition
Block-additive functions modm give automatic sequences.
Clemens Müllner

Digital sequences along squares are normal

2. 10. 2018

5 / 10Extensions for the 2nd Gelfond Problem

Theorem (Mauduit and Rivat, 2015)
The Rudin-Shapiro sequence is simply normal along primes.
Theorem (Hanna, 2017)
Pattern-counting functions modm along primes are simply normal.
Theorem (M., 2017)
All automatic sequences are orthogonal to the Mobius function.
The densities along primes can be described.

Clemens Müllner

Digital sequences along squares are normal

2. 10. 20186 / 10Extensions for the 2nd Gelfond Problem

Theorem (Mauduit and Rivat, 2015)
The Rudin-Shapiro sequence is simply normal along primes.
Theorem (Hanna, 2017)
Pattern-counting functions modm along primes are simply normal.
Theorem (M., 2017)
All automatic sequences are orthogonal to the Mobius function.
The densities along primes can be described.

Clemens Müllner

Digital sequences along squares are normal

2. 10. 20186 / 10Extensions for the 2nd Gelfond Problem

Theorem (Mauduit and Rivat, 2015)
The Rudin-Shapiro sequence is simply normal along primes.
Theorem (Hanna, 2017)
Pattern-counting functions modm along primes are simply normal.
Theorem (M., 2017)
All automatic sequences are orthogonal to the Mobius function.
The densities along primes can be described.

Clemens Müllner

Digital sequences along squares are normal

2. 10. 20186 / 10Main Result

Theorem (M., 2017)
Let b be a block-additive function and m ∈ N withgcd(q − 1, m) = 1 and gcd(m, {b(n), n ∈ N}) = 1. Then(b(n2 ) mod m)n∈N is normal in base m0 .
This covers all pattern-counting functions mod m, wheregcd(q − 1, m) = 1, including the Thue-Morse sequence and theRudin-Shapiro sequence.

Clemens Müllner

Digital sequences along squares are normal

2. 10. 20187 / 10Main Result

Theorem (M., 2017)
Let b be a block-additive function and m ∈ N withgcd(q − 1, m) = 1 and gcd(m, {b(n), n ∈ N}) = 1. Then(b(n2 ) mod m)n∈N is normal in base m0 .
This covers all pattern-counting functions mod m, wheregcd(q − 1, m) = 1, including the Thue-Morse sequence and theRudin-Shapiro sequence.

Clemens Müllner

Digital sequences along squares are normal

2. 10. 20187 / 10Conditions

12
34

gcd(m, {b(n), n ∈ N}) = 1: necessary for simple normality.
gcd(q − 1, m) = 1: sq (n) ≡ n(modq − 1) is periodic.
PF (0, . . . , 0) = 0 : f(0,...,0) (n) = blogq (n)c − P6=(0,...,0) fP (n).
Index-range Z instead of N: f(0,1) + f(1,0) mod 2.

The technical conditions (3) and (4) are necessary to get very
natural restrictions (1) and (2).

Clemens Müllner

Digital sequences along squares are normal

2. 10. 20188 / 10Conditions

12
3
4

gcd(m, {b(n), n ∈ N}) = 1: necessary for simple normality.
gcd(q − 1, m) = 1: sq (n) ≡ n(modq − 1) is periodic.
PF (0, . . . , 0) = 0 : f(0,...,0) (n) = blogq (n)c − P6=(0,...,0) fP (n).
Index-range Z instead of N: f(0,1) + f(1,0) mod 2.

The technical conditions (3) and (4) are necessary to get very
natural restrictions (1) and (2).

Clemens Müllner

Digital sequences along squares are normal

2. 10. 20188 / 10Conditions

12
34

gcd(m, {b(n), n ∈ N}) = 1: necessary for simple normality.
gcd(q − 1, m) = 1: sq (n) ≡ n(modq − 1) is periodic.
PF (0, . . . , 0) = 0 : f(0,...,0) (n) = blogq (n)c − P6=(0,...,0) fP (n).
Index-range Z instead of N: f(0,1) + f(1,0) mod 2.

The technical conditions (3) and (4) are necessary to get very
natural restrictions (1) and (2).

Clemens Müllner

Digital sequences along squares are normal

2. 10. 20188 / 10Conditions1234

gcd(m, {b(n), n ∈ N}) = 1: necessary for simple normality.
gcd(q − 1, m) = 1: sq (n) ≡ n(modq − 1) is periodic.
PF (0, . . . , 0) = 0 : f(0,...,0) (n) = blogq (n)c − P6=(0,...,0) fP (n).
Index-range Z instead of N: f(0,1) + f(1,0) mod 2.

The technical conditions (3) and (4) are necessary to get very
natural restrictions (1) and (2).

Clemens Müllner

Digital sequences along squares are normal

2. 10. 20188 / 10Conditions

123
4

gcd(m, {b(n), n ∈ N}) = 1: necessary for simple normality.
gcd(q − 1, m) = 1: sq (n) ≡ n(modq − 1) is periodic.
PF (0, . . . , 0) = 0 : f(0,...,0) (n) = blogq (n)c − P6=(0,...,0) fP (n).
Index-range Z instead of N: f(0,1) + f(1,0) mod 2.

The technical conditions (3) and (4) are necessary to get very
natural restrictions (1) and (2).

Clemens Müllner

Digital sequences along squares are normal

2. 10. 20188 / 10Conditions

12
34

gcd(m, {b(n), n ∈ N}) = 1: necessary for simple normality.
gcd(q − 1, m) = 1: sq (n) ≡ n(modq − 1) is periodic.
PF (0, . . . , 0) = 0 : f(0,...,0) (n) = blogq (n)c − P6=(0,...,0) fP (n).
Index-range Z instead of N: f(0,1) + f(1,0) mod 2.

The technical conditions (3) and (4) are necessary to get very
natural restrictions (1) and (2).

Clemens Müllner

Digital sequences along squares are normal

2. 10. 20188 / 10Conditions

12
34

gcd(m, {b(n), n ∈ N}) = 1: necessary for simple normality.
gcd(q − 1, m) = 1: sq (n) ≡ n(modq − 1) is periodic.
PF (0, . . . , 0) = 0 : f(0,...,0) (n) = blogq (n)c − P6=(0,...,0) fP (n).
Index-range Z instead of N: f(0,1) + f(1,0) mod 2.

The technical conditions (3) and (4) are necessary to get very
natural restrictions (1) and (2).

Clemens Müllner

Digital sequences along squares are normal

2. 10. 20188 / 10Conditions

123
4

gcd(m, {b(n), n ∈ N}) = 1: necessary for simple normality.
gcd(q − 1, m) = 1: sq (n) ≡ n(modq − 1) is periodic.
PF (0, . . . , 0) = 0 : f(0,...,0) (n) = blogq (n)c − P6=(0,...,0) fP (n).
Index-range Z instead of N: f(0,1) + f(1,0) mod 2.

The technical conditions (3) and (4) are necessary to get very
natural restrictions (1) and (2).

Clemens Müllner

Digital sequences along squares are normal

2. 10. 20188 / 10Conditions

123
4

gcd(m, {b(n), n ∈ N}) = 1: necessary for simple normality.
gcd(q − 1, m) = 1: sq (n) ≡ n(modq − 1) is periodic.
PF (0, . . . , 0) = 0 : f(0,...,0) (n) = blogq (n)c − P6=(0,...,0) fP (n).
Index-range Z instead of N: f(0,1) + f(1,0) mod 2.

The technical conditions (3) and (4) are necessary to get very
natural restrictions (1) and (2).

Clemens Müllner

Digital sequences along squares are normal

2. 10. 20188 / 10General Strategy
Rewrite the statement in terms of exponential sums.
Every block of length k appears with density m−k if!
k−1XX
αj b((n + j)2 = o(N),en≤N

j=0

for all (α0 , . . . , αk−1 ) 6= (0, . . . , 0), where e(x) = exp(2πix).
Use a variation of the Van-der-Corput inequality,2X
N + QR − Q X|r |zn ≤1−RR
0<n<N|r |<RX
zn+Qr zn .
0<n,n+Qr <N

This cuts off “high“ and “low“ digits.
Clemens Müllner

Digital sequences along squares are normal

2. 10. 2018

9 / 10General Strategy
Rewrite the statement in terms of exponential sums.
Every block of length k appears with density m−k if!
k−1XX
αj b((n + j)2 = o(N),en≤N

j=0for all (α0 , . . . , αk−1 ) 6= (0, . . . , 0), where e(x) = exp(2πix).
Use a variation of the Van-der-Corput inequality,2
X
N + QR − Q X|r |zn ≤1−RR
0<n<N|r |<RX
zn+Qr zn .
0<n,n+Qr <N

This cuts off “high“ and “low“ digits.
Clemens Müllner

Digital sequences along squares are normal

2. 10. 2018

9 / 10General Strategy
Rewrite the statement in terms of exponential sums.
Every block of length k appears with density m−k if!
k−1XX
αj b((n + j)2 = o(N),en≤N

j=0for all (α0 , . . . , αk−1 ) 6= (0, . . . , 0), where e(x) = exp(2πix).
Use a variation of the Van-der-Corput inequality,2
X
N + QR − Q X|r |zn ≤1−R
R0<n<N|r |<RX
zn+Qr zn .
0<n,n+Qr <N

This cuts off “high“ and “low“ digits.
Clemens Müllner

Digital sequences along squares are normal

2. 10. 2018

9 / 10General Strategy

Use Vaaler’s method to approximate the characteristic functionof [0, α) mod 1.
Find appropriate estimates for the new Fourier-terms,!
XXeαj b(u + jd + ij ) − huq −λ .
HλI (h, d) =u<q λClemens Müllner

jDigital sequences along squares are normal

2. 10. 201810 / 10

General Strategy

Use Vaaler’s method to approximate the characteristic functionof [0, α) mod 1.
Find appropriate estimates for the new Fourier-terms,!
XX
eαj b(u + jd + ij ) − huq −λ .
HλI (h, d) =u<q λClemens Müllnerj

Digital sequences along squares are normal

2. 10. 201810 / 10