Skip to main content
replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link

The Thue-Morse sequence is a triple-free element $(a_i)\in\{0,1\}^\mathbb{N}$ which can be constructed by iterating the transformations $0\to 01$ and $1\to 10$ starting from $0$.

The beginning of the sequence reads $0110100110010110\dots$

I would like a lower bound on the cardinality of the set of consecutive length $n$ subsequences, $\{a_ia_{i+1}\dots a_{i+n-1}|i\in\mathbb{N}\}$.

For instance, does it grow exponentially in $n$?

By Cube-free infinite binary wordsCube-free infinite binary words the number of length $n$ cube-free words in $\{0,1\}^\mathbb{N}$ grows exponentially in $n$, but is this already true for subsequences of the Thue-Morse sequence?

The Thue-Morse sequence is a triple-free element $(a_i)\in\{0,1\}^\mathbb{N}$ which can be constructed by iterating the transformations $0\to 01$ and $1\to 10$ starting from $0$.

The beginning of the sequence reads $0110100110010110\dots$

I would like a lower bound on the cardinality of the set of consecutive length $n$ subsequences, $\{a_ia_{i+1}\dots a_{i+n-1}|i\in\mathbb{N}\}$.

For instance, does it grow exponentially in $n$?

By Cube-free infinite binary words the number of length $n$ cube-free words in $\{0,1\}^\mathbb{N}$ grows exponentially in $n$, but is this already true for subsequences of the Thue-Morse sequence?

The Thue-Morse sequence is a triple-free element $(a_i)\in\{0,1\}^\mathbb{N}$ which can be constructed by iterating the transformations $0\to 01$ and $1\to 10$ starting from $0$.

The beginning of the sequence reads $0110100110010110\dots$

I would like a lower bound on the cardinality of the set of consecutive length $n$ subsequences, $\{a_ia_{i+1}\dots a_{i+n-1}|i\in\mathbb{N}\}$.

For instance, does it grow exponentially in $n$?

By Cube-free infinite binary words the number of length $n$ cube-free words in $\{0,1\}^\mathbb{N}$ grows exponentially in $n$, but is this already true for subsequences of the Thue-Morse sequence?

Source Link
DavidHume
  • 743
  • 3
  • 12

Counting triple-free sequences

The Thue-Morse sequence is a triple-free element $(a_i)\in\{0,1\}^\mathbb{N}$ which can be constructed by iterating the transformations $0\to 01$ and $1\to 10$ starting from $0$.

The beginning of the sequence reads $0110100110010110\dots$

I would like a lower bound on the cardinality of the set of consecutive length $n$ subsequences, $\{a_ia_{i+1}\dots a_{i+n-1}|i\in\mathbb{N}\}$.

For instance, does it grow exponentially in $n$?

By Cube-free infinite binary words the number of length $n$ cube-free words in $\{0,1\}^\mathbb{N}$ grows exponentially in $n$, but is this already true for subsequences of the Thue-Morse sequence?