Open paths close from the sink backwards: closing one pair forces the whole tail, fourth terms first
ProvedErdos195.open_path_closes_backwardsA tree witness defines a strict total order on (milestone framework). 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. For an in-order pair of a word ( before ), call its third term and its fourth term. An open path in a word is a family of in-order pairs , , of letters of with
(the fourth term of each pair is the third term of the next) and no third term in . Theorem. Let contain such an open path and let be -safe for some tree witness (any extension ). If the third term of some pair occurs in , then for every with both and occur in , and comes before .
Since , the closing order is forced: first, then . So the tail of an open path can only be closed from the sink backwards. The reason is the tree criterion: an in-order pair whose third term appears later must already have its fourth term, placed before the third term. This is the acyclic counterpart of milestone 143 (open cycles never close): for a path the closure must start at the sink's fourth term . It is a structural lemma about the tree-witness approach to Erdős #195, not a construction or an impossibility result.
Formalization note: words are List ℤ, positions via List.idxOf, pairs are a b : ℕ → ℤ on indices i < m; safety is Safe (treeLt θ) (T ++ R).
import Mathlib import Definitions.Def_Erdos195_tree
namespace Erdos195
theorem open_path_closes_backwards (θ : ℕ → ℤ → Bool) (T R : List ℤ) (m : ℕ) (a b : ℕ → ℤ)
(ha : ∀ i < m, a i ∈ T) (hb : ∀ i < m, b i ∈ T)
(hi : ∀ i < m, T.idxOf (a i) < T.idxOf (b i))
(hpath : ∀ i, i + 1 < m → 3 * b i - 2 * a i = 2 * b (i + 1) - a (i + 1))
(ht : ∀ i < m, 2 * b i - a i ∉ T) (hS : Safe (treeLt θ) (T ++ R))
(i : ℕ) (hti : 2 * b i - a i ∈ T ++ R) :
∀ j, i ≤ j → j < m →
2 * b j - a j ∈ T ++ R ∧ 3 * b j - 2 * a j ∈ T ++ R ∧
(T ++ R).idxOf (3 * b j - 2 * a j) < (T ++ R).idxOf (2 * b j - a j) := by sorry
end Erdos195