Escape chains terminate: o + 3^n(w−o) ends in a reflection or precedes o (root bit 1)
ProvedErdos195.escape_chain_terminatesA tree witness defines a strict total order on (milestone framework); it satisfies Ho's identity : . A finite word of integers is -safe if the sequence "letters of in order, then all remaining integers in -order" has no monotone 4-term arithmetic progression; positions are first occurrences. With root bit , every odd before an even is either reflected ( occurs before ) or escapes ( occurs). The escape is again even.
Theorem (escape chains terminate). Let , let be -safe, and let odd come before even in . Put , so and is the escape of at . Then there is such that , comes before each of , and either (i) comes before and comes before (a genuine reflection), or (ii) and comes before .
So escapes cannot be used indefinitely. Each inverted (odd, even) pair starts a geometric chain of escapes with ratio 3 about , and the chain must end in a reflection or in a letter placed before . In particular, if no even letter precedes , some is genuinely reflected. This is a structural lemma for Erdős #195, not a construction or an impossibility result.
Formalization note: words are List ℤ, positions via List.idxOf, safety is Safe (treeLt θ).
import Mathlib import Definitions.Def_Erdos195_tree
namespace Erdos195
theorem escape_chain_terminates (θ : ℕ → ℤ → Bool) (h00 : θ 0 0 = true) (Q : List ℤ)
(hS : Safe (treeLt θ) Q) (o w : ℤ) (ho : o ∈ Q) (hw : w ∈ Q) (hoo : o % 2 = 1)
(hwe : w % 2 = 0) (hi : Q.idxOf o < Q.idxOf w) :
∃ n : ℕ, (∀ m ≤ n, o + 3 ^ m * (w - o) ∈ Q) ∧
(∀ m < n, Q.idxOf o < Q.idxOf (o + 3 ^ m * (w - o))) ∧
((Q.idxOf o < Q.idxOf (o + 3 ^ n * (w - o)) ∧
2 * (o + 3 ^ n * (w - o)) - o ∈ Q ∧
Q.idxOf (2 * (o + 3 ^ n * (w - o)) - o) < Q.idxOf (o + 3 ^ n * (w - o))) ∨
(0 < n ∧ Q.idxOf (o + 3 ^ n * (w - o)) < Q.idxOf o)) := by sorry
end Erdos195