Keyboard shortcuts

Press ← or → to navigate between chapters

Press ? to show this help

Press Esc to hide this help

First Starts at Fibonacci Differences

Abstract

Locate the first longest monochromatic progression at every Fibonacci difference.

Definition 1.1 (The first start of a longest progression).

Formalization. D5/S1/Words/FibonacciMapFirstStart.goldenMAPFirstStart (✓ std3).

Citation. Gandhar Joshi and Dan Rust (2025). Monochromatic arithmetic progressions in the Fibonacci, Thue-Morse, and Rudin-Shapiro words. DOI: 10.1016/j.tcs.2025.115391. URL: https://arxiv.org/html/2501.05830v2.

Commentary.

goldenWord is the zero-indexed fixed point 010010100100101… of 0 -> 01 and 1 -> 0. True represents 0 and false represents 1. goldenMAPMaximum(d) is the supremum of all positive progression lengths over every natural start and both letters. The definition takes the natural infimum of starts attaining that length, without choosing a letter in advance. At the Fibonacci differences below the length set is bounded and its maximum is attained, so the start set is nonempty and its infimum is its least element.

Theorem 1.2 (An orbit confined to an open interval).

Proof. Machine-checked in Lean as D5/S1/Words/FibonacciMapFirstStart.open_rotation_run (✓ std3). ∎

Source. Repository-derived.

Commentary.

Let x be a finite orbit of rotation by a positive step eps, forward or backward according to the Boolean forward. If all length points lie in (lo,hi) inside [0,1], and eps is at most the complementary gap, no step wraps around. The last point is therefore the first point plus the signed total displacement, whose magnitude is strictly less than hi-lo. The subtraction length-1 is natural subtraction before coercion to the reals.

Theorem 1.3 (Both parity families).

Proof. Machine-checked in Lean as D5/S1/Words/FibonacciMapFirstStart.result (✓ std3). ∎

Resolves. Problems/joshi-rust-fibonacci-map-first-start (proved) by D5/S1/Words/FibonacciMapFirstStart.result.

Source. Repository-derived.

Acknowledgement. Gandhar Joshi and Dan Rust (2025). Monochromatic arithmetic progressions in the Fibonacci, Thue-Morse, and Rudin-Shapiro words. DOI: 10.1016/j.tcs.2025.115391. URL: https://arxiv.org/html/2501.05830v2.

Commentary.

Here fib is the natural Fibonacci sequence, with fib(0)=0 and fib(1)=1. For every n at least one both differences are positive. The two equations describe the earliest starts attaining the global maximum, not just starts of particular progression witnesses.

Write r=1/tau and m for the Fibonacci index. At word position j the phase is {(j+1)tau}, and true letters occupy (r^2,1). The step is r^m to the right for odd m and r^m to the left for even m. The natural maximum length is fib(m-2)+fib(m) for odd m and one more for even m. Open symbol endpoints prevent wraparound even when m=2 and the step equals r^2. Every false-letter progression is strictly shorter.

Cassini’s integer determinant gives one-sided orbit records: before fib(m+2), the positive displacement for odd m, or the backward displacement for even m, is at least r^m. In integral Fibonacci coordinates a smaller displacement would force a denominator at least fib(m)+fib(m+1). The odd maximal-start interval translates by one extra rotation to a positive interval shorter than r^m. The even interval has backward width r^(2m-1), smaller than the preceding even record r^(2m-2). These exclusions rule out every earlier start. The boundary n=1 gives first starts 3 at difference 2 and 2 at difference 1.

References