7
$\begingroup$

The Fibonacci word is the limit of the sequence of words starting with $0$ and satisfying rules $0 \to 01, 1 \to 0$. Equivalently, it is obtained from the recursion $S_n= S_{n-1}S_{n-2}$ under initial conditions $S_0 = 0, S_1 = 01$. Let us denote this Fibonacci word as $f_k\in\{0,1\}^{\mathbb Z_+}$.

We define the Fibonacci subshift $\Omega$ as the set of all two-sided right limits of the Fibonacci word. More precisely, we extend our Fibonacci word to $\{0,1\}^{\mathbb Z}$ by defining $\{f_j\}_{j=-\infty}^0$ arbitrarily, and define $(\mathcal Tf)_k=f_{k+1}$. The Fibonacci subshift $\Omega$ is then the set of limit points of $\{\mathcal T^n f\}_{n=0}^\infty$ under the product topology on $\{0,1\}^{\mathbb{Z}}$.

It is easy to show that the ratio of zeroes to ones in the Fibonacci word is $\varphi$, the golden ratio. Equivalently, the density of ones in the Fibonacci word (that is, the ratio of the number of ones in a subword to the length of the subword) tends to $\frac{1}{\varphi^2}$. I would like to know if this is true uniformly. That is,

Is the following true for a.e. $\omega\in\Omega$? Given any $c\in\mathbb Z$, $$\lim_{m\to\infty} \sum_{j=c-m}^{c+m}\frac{\omega_j}{2m+1}=\frac{1}{\varphi^2} $$ uniformly in $c$.

I also suspect this might be true for every $\omega\in\Omega$, not just a.e.

$\endgroup$
1
  • 7
    $\begingroup$ Another answer that the one by David Speyer below is to say that the Fibonacci word is the sequence of 0's and 1's obtained from the orbit of 0 under the dynamical system $R_\phi(t)=t+\phi\bmod 1$, where $\phi$ is the golden mean; $I_0=[0,\phi-1)$ and $I_1=[\phi-1,1)$ (so that the sequence of 0's and 1's records the order in which the order visits the intervals $I_0$ and $I_1$). The uniformity you are asking for follows from unique ergodicity of irrational circle rotations. $\endgroup$ Commented Feb 20, 2019 at 6:23

1 Answer 1

10
$\begingroup$

Yes. By Proposition 2.1.10 in Lothaire, Algebraic Combinatorics on Words, if $u$ is any substring of the Fibonacci word then $$\left| \frac{\mbox{number of $1$'s in $u$}}{\mbox{length of $u$}} - \frac{1}{\phi^2} \right| \leq \frac{1}{\mbox{length of $u$}}.$$ Any length $n$ substring of any $\omega \in \Omega$ is also a length $n$ substring of the Fibonacci word, so the same bound applies to it.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .