A band exit in the A166944 replay has gap at most half the record
ProvedA166944Research.band_exit_gap_le_half_record_v2Let be the Rowland-type recursion of OEIS A166944, its first differences and its offset from the identity. A moving-horizon state is a pair with and ; the recursion is quiet between states, and a step records the first index at which the increment is nontrivial. Write
for how much horizon is left above the index, and call the capped band the set of states with , where is the record from which the replay started.
The theorem concerns a step that leaves the band: the state is inside, , and the next state is outside, . For such a step,
In words: an exit from the band is a gain of room, and therefore a short step. The gap is at most half the record.
This is not a curiosity. It says that a replay which leaves the band can come back — as one does from the record , visiting rooms , then , then — and the reason is structural rather than accidental: leaving is the mechanism by which the room grows. Consequently the tail of a replay cannot be packaged as a single in-band suffix unless the excursion is bounded separately.
The proof has two ingredients. The first is a one-step inequality containing no gap term, so that it composes along a path:
which is equivalent to . The second is that an exit has strictly increasing, hence ; substituting into the first gives the statement.
Formalization Note The hypothesis C - s ≤ M is stated on the room rather than as s < C ∧ C - s ≤ M because IsMovingHorizonStep already carries the state conditions; hout is the strict inequality that makes the step an exit rather than a boundary case. The constant 2 in 2 * (r - s) + 1 ≤ M is optimal for the method: a stronger form 2*(r-s)+3 ≤ M holds in every measured case but is not proved.
import Definitions.Def_a166944_moving_horizon open A166944Research
namespace A166944Research
theorem band_exit_gap_le_half_record_v2 {M s C r C' : Nat}
(hstep : IsMovingHorizonStep s C r C')
(hin : C - s ≤ M) (hout : M < C' - r) :
2 * (r - s) + 1 ≤ M := by
sorry
end A166944Research