Gap spectra and densities of slow Fibonacci walks

Abstract

Let $F_1=F_2=1$ and $F_{t+2}=F_{t+1}+F_t$ for $t\ge 1$. For every $n\ge 2$, there are unique integers $a,b,t$ such that $n=a{F}_t+b{F}_{t-1}$ with $t\ge 2$ and $1\le a\le b\le F_t$. The Fibonacci walk with initial pair $(b,a)$ reaches $n$ as late as possible, and the term following $n$ in this walk is $\lfloor \varphi n\rfloor$ when $t$ is even and $\lceil \varphi n\rceil$ when $t$ is odd, where $\varphi =(1+\sqrt{5})/2$. Let $D=\{d_1<d_2<\cdots \}$ and $U=\{u_1<u_2<\cdots \}$ be the sets corresponding to even and odd $t$, respectively. For $\ell ,m\ge 1$, define $D_{\ell }=\{d_{k+\ell }-d_k:k\ge 1\}$, $U_{\ell }=\{u_{k+\ell }-u_k:k\ge 1\}$, $D_{\ell }(m)=\{d_k:d_{k+\ell }-d_k=m\}$ and $U_{\ell }(m)=\{u_k:u_{k+\ell }-u_k=m\}$. Chung, Graham and Spiro conjectured that $D_{\ell }=U_{\ell }$ for all $\ell$, and asked for the densities of $D_{\ell }(m)$ and $U_{\ell }(m)$, especially when $\ell =1$. In this paper, we determine the third and fourth order gap spectra, and show that the conjecture holds for $\ell =3$ but fails for $\ell =4$. We also answer their density question by characterizing when $D_{\ell }(m)$ and $U_{\ell }(m)$ have natural densities and proving that their logarithmic densities always exist and are equal. For $\ell =1$, we give the exact logarithmic densities.

12 pages