Gap spectra and densities of slow Fibonacci walks

Technical Summary: Gap Spectra and Densities of Slow Fibonacci Walks

Problem Statement
This paper investigates the structural properties of "slow Fibonacci walks," a concept introduced by Chung, Graham, and Spiro [4]. For any integer $n \ge 2$, there exists a unique canonical representation $n = aF_t + bF_{t-1}$ with $1 \le a \le b \le F_t$ and $t \ge 2$. The integer $n$ is classified as a "down-integer" if $t$ is even and an "up-integer" if $t$ is odd. These classifications partition the integers $\ge 2$ into two sets, $D$ (down) and $U$ (up).

The study focuses on the gap spectra of these sets. For a fixed lag $\ell \ge 1$, the $\ell$-th gap spectrum $D_\ell$ (respectively $U_\ell$) is defined as the set of differences $\{d_{k+\ell} - d_k\}$ (respectively $\{u_{k+\ell} - u_k\}$) between elements in the ordered sequences of $D$ and $U$. Chung, Graham, and Spiro established that $D_1 = U_1$ and $D_2 = U_2$, leading to the conjecture that $D_\ell = U_\ell$ for all $\ell \ge 1$. Furthermore, they posed the problem of determining the asymptotic densities of the refined occurrence sets $D_\ell(m) = \{d_k : d_{k+\ell} - d_k = m\}$ and $U_\ell(m)$, specifically asking whether these sets possess natural densities.

Methodology
The authors employ a combination of number-theoretic analysis, dynamical systems theory, and geometric measure theory.

1. Canonical Representation and Phase Analysis: The paper utilizes the unique canonical representation of integers to define a "phase" variable $\varepsilon_n$. For an integer $n$ with canonical index $t$, $\varepsilon_n$ is derived from the fractional part of $\phi n$ (where $\phi = (1+\sqrt{5})/2$). The membership of $n$ in $D$ or $U$ is determined by whether $\varepsilon_n$ falls within specific intervals defined by $\alpha = 1/(1+\phi^2)$ and $\beta = \phi/\sqrt{5}$.
2. Geometric Mapping: The authors define a mapping $L$ from the space of normalized canonical coefficients to a triangular domain $T$. They demonstrate that the distribution of canonical coefficients converges to a uniform distribution on this domain. This allows the problem of counting gaps to be translated into a problem of measuring the Lebesgue measure of specific regions within the triangle $T$ defined by rotation maps $x \mapsto \{x + \phi^{-1}\}$.
3. Rotation Dynamics: The core of the density analysis relies on the dynamics of the rotation $R(x) = \{x + \phi^{-1}\}$ on the unit circle. The authors analyze the "first return times" of this rotation to specific intervals $[0, \theta)$. By characterizing the partial sums of these return times, they determine which gap sequences are possible.
4. Asymptotic Counting Functions: To address the density questions, the authors construct a continuous, multiplicatively $\phi^4$-periodic function $P_{\ell,m}$. They prove that the normalized counting functions for $D_\ell(m)$ and $U_\ell(m)$ converge to this function (with a phase shift for $U$) as $X \to \infty$.

Key Contributions and Results

• Resolution of the Gap Spectrum Conjecture:
  The paper confirms the conjecture $D_\ell = U_\ell$ for $\ell=3$, proving that $D_3 = U_3 = \{3, 4, 5, 6, 7, 8, 10, 11, 13\}$. However, it disproves the conjecture for $\ell=4$. The authors show that $D_4 = \{5, 6, 7, 8, 10, 11, 13, 16, 18\}$, while $U_4 = D_4 \cup \{9\}$. Specifically, the gap value 9 occurs in $U$ but never in $D$ (i.e., $D_4(9) = \emptyset$ while $U_4(9) = \{8\}$).

• Characterization of Densities:
  The authors provide a complete characterization of the densities of the refined sets $D_\ell(m)$ and $U_\ell(m)$.

  • Natural Density: They prove that natural densities exist if and only if the associated periodic function $P_{\ell,m}$ is constant. For the case $\ell=1$, they show that for every $m \in D_1 = \{1, 2, 3, 5\}$, the sets $D_1(m)$ and $U_1(m)$ have positive lower density but no natural density.
  • Logarithmic Density: The paper proves that the logarithmic densities of $D_\ell(m)$ and $U_\ell(m)$ always exist and are equal for any $\ell, m$.
  • Exact Values: For $\ell=1$, the authors derive exact formulas for the logarithmic densities $d_m = \delta_{\log}(D_1(m)) = \delta_{\log}(U_1(m))$. These values are expressed in terms of $\phi$ and logarithms of $\sqrt{5}$ and $\phi$.

• Asymptotic Formula:
  Theorem 1.4 establishes that for large $X$, the count of elements in $D_\ell(m) \cap [1, X]$ is given by $X \cdot P_{\ell,m}(\lambda_X) + o(X)$, where $\lambda_X$ depends on the Fibonacci scale. This formula reveals that the distribution of gaps is not uniform but oscillates according to the periodic function $P_{\ell,m}$.

Significance
The paper resolves specific open questions posed by Chung, Graham, and Spiro regarding the symmetry of gap spectra in slow Fibonacci walks. By demonstrating that the conjecture $D_\ell = U_\ell$ fails for $\ell=4$, the work highlights subtle asymmetries in the distribution of down- and up-integers that are not apparent at lower lags. Furthermore, the rigorous determination of densities clarifies the asymptotic behavior of these sets, showing that while natural densities often fail to exist due to oscillatory behavior inherent in the Fibonacci scale, logarithmic densities provide a stable and equal measure for both sets. The methodology of linking canonical representations to rotation dynamics on the circle offers a robust framework for analyzing similar recurrence-based sequences.