Möbius orthogonality for automatic sequences
and beyond
Clemens Müllner

May 24, 2018

Joint work with Michael Drmota and Lukas Spiegelhofer
Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 20181 / 19Möbius function
The Möbius function is defined by (−1)kµ(n) = 0if n is squarefree andk is the number of prime factors
otherwise

A sequence u is orthogonal to the Möbius function µ(n) if
Xµ(n)un = o(n≤NX|un |)(N → ∞).

n≤N

Old Heuristic - Mobius Randomness Law
Any ”reasonably defined (easy)”bounded sequence independent of µ
is orthogonal to µ.
Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 20182 / 19Möbius function
The Möbius function is defined by (−1)kµ(n) = 0if n is squarefree andk is the number of prime factors
otherwise

A sequence u is orthogonal to the Möbius function µ(n) if
Xµ(n)un = o(n≤NX|un |)(N → ∞).

n≤N

Old Heuristic - Mobius Randomness Law
Any ”reasonably defined (easy)”bounded sequence independent of µ
is orthogonal to µ.
Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 20182 / 19Möbius function
The Möbius function is defined by (−1)kµ(n) = 0if n is squarefree andk is the number of prime factors
otherwise

A sequence u is orthogonal to the Möbius function µ(n) if
Xµ(n)un = o(n≤NX|un |)(N → ∞).

n≤N

Old Heuristic - Mobius Randomness Law
Any ”reasonably defined (easy)”bounded sequence independent of µ
is orthogonal to µ.
Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 20182 / 19Orthogonality to µ

Results
Constant sequences ⇔ PNT
Periodic sequences ⇔ PNT in arithmetic Progressions
Quasiperiodic sequences f (n) = F (αn mod 1) - Davenport
Nilsequences - Green and Tao
Horocycle Flows - Bourgain, Sarnak and Ziegler
Dynamical systems with discrete spectrum

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 20183 / 19Orthogonality to µ

Results
Constant sequences ⇔ PNT
Periodic sequences ⇔ PNT in arithmetic Progressions
Quasiperiodic sequences f (n) = F (αn mod 1) - Davenport
Nilsequences - Green and Tao
Horocycle Flows - Bourgain, Sarnak and Ziegler
Dynamical systems with discrete spectrum

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 20183 / 19Orthogonality to µ

Results
Constant sequences ⇔ PNT
Periodic sequences ⇔ PNT in arithmetic Progressions
Quasiperiodic sequences f (n) = F (αn mod 1) - Davenport
Nilsequences - Green and Tao
Horocycle Flows - Bourgain, Sarnak and Ziegler
Dynamical systems with discrete spectrum

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 20183 / 19Orthogonality to µ

Results
Constant sequences ⇔ PNT
Periodic sequences ⇔ PNT in arithmetic Progressions
Quasiperiodic sequences f (n) = F (αn mod 1) - Davenport
Nilsequences - Green and Tao
Horocycle Flows - Bourgain, Sarnak and Ziegler
Dynamical systems with discrete spectrum

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 20183 / 19Orthogonality to µ

Results
Constant sequences ⇔ PNT
Periodic sequences ⇔ PNT in arithmetic Progressions
Quasiperiodic sequences f (n) = F (αn mod 1) - Davenport
Nilsequences - Green and Tao
Horocycle Flows - Bourgain, Sarnak and Ziegler
Dynamical systems with discrete spectrum

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 20183 / 19Orthogonality to µ

Results
Constant sequences ⇔ PNT
Periodic sequences ⇔ PNT in arithmetic Progressions
Quasiperiodic sequences f (n) = F (αn mod 1) - Davenport
Nilsequences - Green and Tao
Horocycle Flows - Bourgain, Sarnak and Ziegler
Dynamical systems with discrete spectrum

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 20183 / 19Orthogonality to µ

Results
Constant sequences ⇔ PNT
Periodic sequences ⇔ PNT in arithmetic Progressions
Quasiperiodic sequences f (n) = F (αn mod 1) - Davenport
Nilsequences - Green and Tao
Horocycle Flows - Bourgain, Sarnak and Ziegler
Dynamical systems with discrete spectrum

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 20183 / 19Orthogonality to µ

Results
Constant sequences ⇔ PNT
Periodic sequences ⇔ PNT in arithmetic Progressions
Quasiperiodic sequences f (n) = F (αn mod 1) - Davenport
Nilsequences - Green and Tao
Horocycle Flows - Bourgain, Sarnak and Ziegler
Dynamical systems with discrete spectrum

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 20183 / 19Sarnak Conjecture

Definition
A dynamical system is said to be deterministic, if its topologicalentropy is 0.
Conjecture (Sarnak conjecture, 2010)
Every bounded complex sequence u = (un )n>0 that is obtained by adeterministic dynamical system is orthogonal to the Möbius functionµ(n).

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 20184 / 19Sarnak Conjecture

Definition
A dynamical system is said to be deterministic, if its topologicalentropy is 0.
Conjecture (Sarnak conjecture, 2010)
Every bounded complex sequence u = (un )n>0 that is obtained by adeterministic dynamical system is orthogonal to the Möbius functionµ(n).

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 20184 / 19Automatic Sequences

Automatic Sequences
Definition
Let E be a finite set and σ a k-uniform morphism such that
σ(E ) ⊆ E k . Then if w is a fixed point of σ, i.e. σ(w) = w, then w
is a k-automatic sequence.
Example (Thue-Morse)
E = {0, 1}
σ(0) = 01
σ(1) = 1001101001100101101001011001101001 . . .

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 2018

5 / 19Automatic Sequences

Automatic Sequences
Definition
Let E be a finite set and σ a k-uniform morphism such that
σ(E ) ⊆ E k . Then if w is a fixed point of σ, i.e. σ(w) = w, then w
is a k-automatic sequence.
Example (Thue-Morse)
E = {0, 1}
σ(0) = 01
σ(1) = 1001101001100101101001011001101001 . . .

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 2018

5 / 19Automatic Sequences

Automatic Sequences
Definition
Let E be a finite set and σ a k-uniform morphism such that
σ(E ) ⊆ E k . Then if w is a fixed point of σ, i.e. σ(w) = w, then w
is a k-automatic sequence.
Example (Thue-Morse)
E = {0, 1}
σ(0) = 01
σ(1) = 1001101001100101101001011001101001 . . .

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 2018

5 / 19Automatic Sequences

Automatic Sequences
Definition
Let E be a finite set and σ a k-uniform morphism such that
σ(E ) ⊆ E k . Then if w is a fixed point of σ, i.e. σ(w) = w, then w
is a k-automatic sequence.
Example (Thue-Morse)
E = {0, 1}
σ(0) = 01
σ(1) = 1001101001100101101001011001101001 . . .

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 2018

5 / 19Automatic Sequences

Automatic Sequences
Definition
Let E be a finite set and σ a k-uniform morphism such that
σ(E ) ⊆ E k . Then if w is a fixed point of σ, i.e. σ(w) = w, then w
is a k-automatic sequence.
Example (Thue-Morse)
E = {0, 1}
σ(0) = 01
σ(1) = 1001101001100101101001011001101001 . . .

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 2018

5 / 19Automatic Sequences

Automatic Sequences
Definition
Let E be a finite set and σ a k-uniform morphism such that
σ(E ) ⊆ E k . Then if w is a fixed point of σ, i.e. σ(w) = w, then w
is a k-automatic sequence.
Example (Thue-Morse)
E = {0, 1}
σ(0) = 01
σ(1) = 1001101001100101101001011001101001 . . .

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 2018

5 / 19Automatic Sequences

Automatic Sequences
Definition
Let E be a finite set and σ a k-uniform morphism such that
σ(E ) ⊆ E k . Then if w is a fixed point of σ, i.e. σ(w) = w, then w
is a k-automatic sequence.
Example (Thue-Morse)
E = {0, 1}
σ(0) = 01
σ(1) = 1001101001100101101001011001101001 . . .

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 2018

5 / 19Automatic Sequences

Automatic Sequences
Definition
Let E be a finite set and σ a k-uniform morphism such that
σ(E ) ⊆ E k . Then if w is a fixed point of σ, i.e. σ(w) = w, then w
is a k-automatic sequence.
Example (Thue-Morse)
E = {0, 1}
σ(0) = 01
σ(1) = 1001101001100101101001011001101001 . . .

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 2018

5 / 19Automatic Sequences

Automatic Sequences
Definition
Let E be a finite set and σ a k-uniform morphism such that
σ(E ) ⊆ E k . Then if w is a fixed point of σ, i.e. σ(w) = w, then w
is a k-automatic sequence.
Example (Thue-Morse)
E = {0, 1}
σ(0) = 01
σ(1) = 1001101001100101101001011001101001 . . .

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 2018

5 / 19Automatic Sequences

Automatic Sequences
Definition
Let E be a finite set and σ a k-uniform morphism such that
σ(E ) ⊆ E k . Then if w is a fixed point of σ, i.e. σ(w) = w, then w
is a k-automatic sequence.
Example (Thue-Morse)
E = {0, 1}
σ(0) = 01
σ(1) = 1001101001100101101001011001101001 . . .

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 2018

5 / 19Automatic Sequences

Deterministic Finite Automata
Definition (Automaton - DFA)A = (Q, Σ = {0, . . . , k − 1}, δ, q0 , τ )Example (Thue-Morse sequence)
0

0
1

start

a/0

b/1
1

n = 22 = (10110)2 ,u22 = 1u = (un )n≥0 = 01101001100101101001011001101001 . . .
Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 20186 / 19Automatic Sequences

Deterministic Finite Automata
Definition (Automaton - DFA)A = (Q, Σ = {0, . . . , k − 1}, δ, q0 , τ )Example (Thue-Morse sequence)
0

0
1

start

a/0

b/1
1

n = 22 = (10110)2 ,u22 = 1u = (un )n≥0 = 01101001100101101001011001101001 . . .
Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 20186 / 19Automatic Sequences

Deterministic Finite Automata
Definition (Automaton - DFA)A = (Q, Σ = {0, . . . , k − 1}, δ, q0 , τ )Example (Thue-Morse sequence)
0

0
1

start

a/0

b/1
1

n = 22 = (10110)2 ,u22 = 1u = (un )n≥0 = 01101001100101101001011001101001 . . .
Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 20186 / 19Automatic Sequences

Deterministic Finite Automata
Definition (Automaton - DFA)A = (Q, Σ = {0, . . . , k − 1}, δ, q0 , τ )Example (Thue-Morse sequence)
0

0
1

start

a/0

b/1
1

n = 22 = (10110)2 ,u22 = 1u = (un )n≥0 = 01101001100101101001011001101001 . . .
Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 20186 / 19Automatic Sequences

Results I

Theorem (M., 2016)
Every automatic sequence (an )n≥0 fulfills the Sarnak Conjecture
Theorem 2 (M., 2016)
Under suitable (weak) conditions one also gets a Prime Number
Theorem for automatic sequence.

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 20187 / 19Automatic Sequences

Results I

Theorem (M., 2016)
Every automatic sequence (an )n≥0 fulfills the Sarnak Conjecture
Theorem 2 (M., 2016)
Under suitable (weak) conditions one also gets a Prime Number
Theorem for automatic sequence.

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 20187 / 19Automatic Sequences

Representation of automatic sequences
Example (Rudin-Shapiro)

start

0

0

a

b

0

0 | id01

0 | id1 | id

1

1

c

a, b

start

d

c, d

1
1 | (12)Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 20188 / 19Automatic Sequences

Representation of automatic sequences
Example (Rudin-Shapiro)

start

0

0

a

b

0

0 | id01

0 | id1 | id

1

1

c

a, b

start

d

c, d

1
1 | (12)Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 20188 / 19Automatic Sequences

Representation of automatic sequences
Example (Rudin-Shapiro)

start

0

0

a

b

0

0 | id01

0 | id1 | id

1

1

c

a, b

start

d

c, d

1
1 | (12)Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 20188 / 19Automatic Sequences

Theorem (M., 2016)
For every strongly connected automaton A, there exists a naturally
induced transducer TA . All other naturally induced transducers canbe obtained by changing the order on the elements of Q.
Example:0|(12)

0

q10

1 0

start

0

q00

q20
0,1

1
1

1

q00 , q10 , q20

start

0|(12)
1| id

1|(23)

0q30
Clemens Müllner

q40
Möbius orthogonality for automatic sequences and beyond

q00 , q30 , q40
24. 05. 2018

9 / 19Automatic Sequences

Theorem (M., 2016)
For every strongly connected automaton A, there exists a naturally
induced transducer TA . All other naturally induced transducers canbe obtained by changing the order on the elements of Q.
Example:0|(12)

0

q10

1 0

start

0

q00

q20
0,1

1
1

1

q00 , q10 , q20

start

0|(12)
1| id

1|(23)

0q30
Clemens Müllner

q40
Möbius orthogonality for automatic sequences and beyond

q00 , q30 , q40
24. 05. 2018

9 / 19Automatic Sequences

Theorem (M., 2016)
For every strongly connected automaton A, there exists a naturally
induced transducer TA . All other naturally induced transducers canbe obtained by changing the order on the elements of Q.
Example:0|(12)

0

q10

1 0

start

0

q00

q20
0,1

1
1

1

q00 , q10 , q20

start

0|(12)
1| id

1|(23)

0q30
Clemens Müllner

q40
Möbius orthogonality for automatic sequences and beyond

q00 , q30 , q40
24. 05. 2018

9 / 19Automatic Sequences

Theorem (M., 2016)
For every strongly connected automaton A, there exists a naturally
induced transducer TA . All other naturally induced transducers canbe obtained by changing the order on the elements of Q.
Example:0|(12)

0

q10

1 0

start

0

q00

q20
0,1

1
1

1

q00 , q10 , q20

start

0|(12)
1| id

1|(23)

0q30
Clemens Müllner

q40
Möbius orthogonality for automatic sequences and beyond

q00 , q30 , q40
24. 05. 2018

9 / 19Automatic Sequences

Theorem (M., 2016)
For every strongly connected automaton A, there exists a naturally
induced transducer TA . All other naturally induced transducers canbe obtained by changing the order on the elements of Q.
Example:0|(12)

0

q10

1 0

start

0

q00

q20
0,1

1
1

1

q00 , q10 , q20

start

0|(12)
1| id

1|(23)

0q30
Clemens Müllner

q40
Möbius orthogonality for automatic sequences and beyond

q00 , q30 , q40
24. 05. 2018

9 / 19Automatic Sequences

Theorem (M., 2016)
For every strongly connected automaton A, there exists a naturally
induced transducer TA . All other naturally induced transducers canbe obtained by changing the order on the elements of Q.
Example:0|(12)

0

q10

1 0

start

0

q00

q20
0,1

1
1

1

q00 , q10 , q20

start

0|(12)
1| id

1|(23)

0q30
Clemens Müllner

q40
Möbius orthogonality for automatic sequences and beyond

q00 , q30 , q40
24. 05. 2018

9 / 19Automatic Sequences

Theorem (M., 2016)
For every strongly connected automaton A, there exists a naturally
induced transducer TA . All other naturally induced transducers canbe obtained by changing the order on the elements of Q.
Example:0|(12)

0

q10

1 0

start

0

q00

q20
0,1

1
1

1

q00 , q10 , q20

start

0|(12)
1| id

1|(23)

0q30
Clemens Müllner

q40
Möbius orthogonality for automatic sequences and beyond

q00 , q30 , q40
24. 05. 2018

9 / 19Automatic Sequences

Theorem (M., 2016)
For every strongly connected automaton A, there exists a naturally
induced transducer TA . All other naturally induced transducers canbe obtained by changing the order on the elements of Q.
Example:0|(12)

0

q10

1 0

start

0

q00

q20
0,1

1
1

1

q00 , q10 , q20

start

0|(12)
1| id

1|(23)

0q30
Clemens Müllner

q40
Möbius orthogonality for automatic sequences and beyond

q00 , q30 , q40
24. 05. 2018

9 / 19Automatic Sequences

Techniques
Use and adopt a framework of Mauduit and Rivat developed for the
Rudin-Shapiro sequence.
Carry Property: The contribution of high and low digits is
independent“.
”
Fourier Property:
We say that U has the Fourier property if there exists η > 0
and c such that for all λ, α and t
1 X
U(mk α )e(mt) ≤ ck −ηλ .
k λ m<k λClemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201810 / 19

Automatic Sequences

Techniques
Use and adopt a framework of Mauduit and Rivat developed for the
Rudin-Shapiro sequence.
Carry Property: The contribution of high and low digits is
independent“.
”
Fourier Property:
We say that U has the Fourier property if there exists η > 0
and c such that for all λ, α and t
1 X
U(mk α )e(mt) ≤ ck −ηλ .
k λ m<k λClemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201810 / 19

Automatic Sequences

Techniques
Use and adopt a framework of Mauduit and Rivat developed for the
Rudin-Shapiro sequence.
Carry Property: The contribution of high and low digits is
independent“.
”
Fourier Property:
We say that U has the Fourier property if there exists η > 0
and c such that for all λ, α and t
1 X
U(mk α )e(mt) ≤ ck −ηλ .
k λ m<k λClemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201810 / 19

Zeckendorf Sum of Digits

Zeckendorf Representation
Fibonacci numbers
F0 = 0, F1 = 1 and Fk+2 = Fk+1 + Fk for k ≥ 0.
Fn =ϕn − (−ϕ)−n√,5where, ϕ is the golden ratio.
Zeckendorf Representation
Every positive integer n admits a unique representationn=X

εi (n)Fi ,i≥2

where, εi (n) ∈ {0, 1} and εi = 1 ⇒ εi+1 = 0.
Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201811 / 19

Zeckendorf Sum of Digits

Zeckendorf Representation
Fibonacci numbers
F0 = 0, F1 = 1 and Fk+2 = Fk+1 + Fk for k ≥ 0.
Fn =ϕn − (−ϕ)−n√,5where, ϕ is the golden ratio.
Zeckendorf Representation
Every positive integer n admits a unique representationn=X

εi (n)Fi ,i≥2

where, εi (n) ∈ {0, 1} and εi = 1 ⇒ εi+1 = 0.
Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201811 / 19

Zeckendorf Sum of Digits

Zeckendorf Representation
Fibonacci numbers
F0 = 0, F1 = 1 and Fk+2 = Fk+1 + Fk for k ≥ 0.
Fn =ϕn − (−ϕ)−n√,5where, ϕ is the golden ratio.
Zeckendorf Representation
Every positive integer n admits a unique representationn=X

εi (n)Fi ,i≥2

where, εi (n) ∈ {0, 1} and εi = 1 ⇒ εi+1 = 0.
Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201811 / 19

Zeckendorf Sum of Digits

Zeckendorf sum-of-digits Function

Definition
We denote bysϕ (n) =Xεi (n)i≥2

the Zeckendorf sum-of-digits function.
We note that sϕ (n) is the least k such that n is the sum of k
Fibonacci numbers.

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201812 / 19

Zeckendorf Sum of Digits

Zeckendorf sum-of-digits Function

Definition
We denote bysϕ (n) =Xεi (n)i≥2

the Zeckendorf sum-of-digits function.
We note that sϕ (n) is the least k such that n is the sum of k
Fibonacci numbers.

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201812 / 19

Zeckendorf Sum of Digits

Results II

Theorem (Drmota, M., Spiegelhofer, 2017)
Let sϕ (n) be the Zeckendorf sum-of-digits function and m(n) abounded multiplicative function. Then we haveX(−1)sϕ (n) m(n) = o(N)(N → ∞).

n<N

This implies that the Zeckendorf sum-of-digits function isorthogonal to the Möbius function.

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201813 / 19

Zeckendorf Sum of Digits

Results II

Theorem (Drmota, M., Spiegelhofer, 2017)
Let sϕ (n) be the Zeckendorf sum-of-digits function and m(n) abounded multiplicative function. Then we haveX(−1)sϕ (n) m(n) = o(N)(N → ∞).

n<N

This implies that the Zeckendorf sum-of-digits function isorthogonal to the Möbius function.

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201813 / 19

Zeckendorf Sum of Digits

Fixpoint of a Substitution
A Morphisma 7→ abb 7→ cc 7→ cd
d 7→ a.
This gives the sequence (−1)sϕ (n) under the codingτ (a) = τ (d) = 1, τ (b) = τ (c) = −1.
This is one of the first examples of a substitution with non-constantlength to be orthogonal to the Möbius function.
Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201814 / 19

Zeckendorf Sum of Digits

Fixpoint of a Substitution
A Morphisma 7→ abb 7→ cc 7→ cd
d 7→ a.
This gives the sequence (−1)sϕ (n) under the codingτ (a) = τ (d) = 1, τ (b) = τ (c) = −1.
This is one of the first examples of a substitution with non-constantlength to be orthogonal to the Möbius function.
Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201814 / 19

Zeckendorf Sum of Digits

Fixpoint of a Substitution
A Morphisma 7→ abb 7→ cc 7→ cd
d 7→ a.
This gives the sequence (−1)sϕ (n) under the codingτ (a) = τ (d) = 1, τ (b) = τ (c) = −1.
This is one of the first examples of a substitution with non-constantlength to be orthogonal to the Möbius function.
Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201814 / 19

Zeckendorf Sum of Digits

Sketch of the Proof
Starting point: (Kátai Criterion) it is sufficient to show
X(−1)sϕ (pn)+sϕ (qn) = o(N),n≤Nfor all different primes p, q.
Use a generating function approach and “quasi-additivity”(Carry Property)
This reduces to find any cancellation in the sum
X(−1)sϕ (pn)+sϕ (qn)

(1)

n<N

for some N > 0.
Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201815 / 19

Zeckendorf Sum of Digits

Sketch of the Proof
Starting point: (Kátai Criterion) it is sufficient to show
X(−1)sϕ (pn)+sϕ (qn) = o(N),n≤Nfor all different primes p, q.
Use a generating function approach and “quasi-additivity”(Carry Property)
This reduces to find any cancellation in the sum
X(−1)sϕ (pn)+sϕ (qn)

(1)

n<N

for some N > 0.
Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201815 / 19

Zeckendorf Sum of Digits

Sketch of the Proof
Starting point: (Kátai Criterion) it is sufficient to show
X(−1)sϕ (pn)+sϕ (qn) = o(N),n≤Nfor all different primes p, q.
Use a generating function approach and “quasi-additivity”(Carry Property)
This reduces to find any cancellation in the sum
X(−1)sϕ (pn)+sϕ (qn)

(1)

n<N

for some N > 0.
Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201815 / 19

Zeckendorf Sum of DigitsKátai Criterion
Suppose that (xn ) is a bounded complex valued sequence withvalues in a finite set and that for every pair (p, q) of different prime
numbers we haveX

xpn xqn = o(N).

n≤NThen for all bounded multiplicative functions m(n) it follows thatX

xn m(n) = o(N).

n≤N

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201816 / 19

Zeckendorf Sum of DigitsKátai Criterion
Suppose that (xn ) is a bounded complex valued sequence withvalues in a finite set and that for every pair (p, q) of different prime
numbers we haveX

xpn xqn = o(N).

n≤NThen for all bounded multiplicative functions m(n) it follows thatX

xn m(n) = o(N).

n≤N

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201816 / 19

Zeckendorf Sum of Digits

Quasi Additivity

Definition
We say that n1 and n2 are r -separated at position k if εi (n1 ) = 0 fori ≥ k − r and εi (n2 ) = 0 for i ≤ k + r .
Example:n1 = 4 ⇒ 0000101
n2 = 29 ⇒ 1010000

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201817 / 19

Zeckendorf Sum of Digits

Quasi Additivity

Definition
We say that n1 and n2 are r -separated at position k if εi (n1 ) = 0 fori ≥ k − r and εi (n2 ) = 0 for i ≤ k + r .
Example:n1 = 4 ⇒ 0000101
n2 = 29 ⇒ 1010000

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201817 / 19

Zeckendorf Sum of Digits

Quasi Additivity

Definition (for integer base by Kropf, Wagner)
We call a function f (n) quasi-additive (with respect to the
Zeckendorf expansion) if there exists r ≥ 0 such thatf (n1 + n2 ) = f (n1 ) + f (n2 )for all integers n1 , n2 that are r separated.
f (n1 ) = f (n2 ) if the Zeckendorf expansion of n1 and n2
coincide up to shifts“.
”

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201818 / 19

Zeckendorf Sum of Digits

Quasi Additivity

Definition (for integer base by Kropf, Wagner)
We call a function f (n) quasi-additive (with respect to the
Zeckendorf expansion) if there exists r ≥ 0 such thatf (n1 + n2 ) = f (n1 ) + f (n2 )for all integers n1 , n2 that are r separated.
f (n1 ) = f (n2 ) if the Zeckendorf expansion of n1 and n2
coincide up to shifts“.
”

Clemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201818 / 19

Conclusion

Common useful properties
Some kind of Carry Property- Carry Property- Quasi Additivity

Recursive Structure- Recursion for Fourier Transforms- Generating function approach

Find some saving- Fourier Property- Cancellation in the sum
X(−1)sϕ (pn)+sϕ (qn)n<NClemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201819 / 19

Conclusion

Common useful properties
Some kind of Carry Property- Carry Property- Quasi Additivity

Recursive Structure- Recursion for Fourier Transforms- Generating function approach

Find some saving- Fourier Property- Cancellation in the sum
X(−1)sϕ (pn)+sϕ (qn)n<NClemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201819 / 19

Conclusion

Common useful properties
Some kind of Carry Property- Carry Property- Quasi Additivity

Recursive Structure- Recursion for Fourier Transforms- Generating function approach

Find some saving- Fourier Property- Cancellation in the sum
X(−1)sϕ (pn)+sϕ (qn)n<NClemens Müllner

Möbius orthogonality for automatic sequences and beyond

24. 05. 201819 / 19