The sink's fourth term never conflicts with its own fully open path
ProvedErdos195.open_path_sink_compatibleA 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, its fourth term, and its level. An open path in is a family of in-order pairs , , of letters of with for and no third term in . Write , , and for the fourth term of the last (sink) pair.
Theorem. Suppose is -safe and contains an open path of length whose sink fourth term is absent from . Let , put , and let satisfy and (the pair has the level of pair and sits at its node). Then
In the tree characterization of safety, this is exactly the orientation condition of the new pair created when is appended. By milestone #149 every closure of the path must place first, and this result shows that the path's own fully open pairs never cause a node conflict for that step: any obstruction to appending comes from pairs off the path. (Proof idea: forces by the ruler law, so .)
import Mathlib import Definitions.Def_Erdos195_tree
namespace Erdos195
theorem open_path_sink_compatible (θ : ℕ → ℤ → Bool) (T : List ℤ) (hS : Safe (treeLt θ) T)
(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)
(hw : 3 * b (m - 1) - 2 * a (m - 1) ∉ T)
(x : ℤ) (j : ℕ) (hj : j < m)
(hk : padicValInt 2 ((3 * b (m - 1) - 2 * a (m - 1)) - x) = padicValInt 2 (b j - a j))
(hnode : x % 2 ^ padicValInt 2 (b j - a j) = a j % 2 ^ padicValInt 2 (b j - a j)) :
(θ (padicValInt 2 ((3 * b (m - 1) - 2 * a (m - 1)) - x))
(x % 2 ^ padicValInt 2 ((3 * b (m - 1) - 2 * a (m - 1)) - x)) = true ↔
bitOne (3 * b (m - 1) - 2 * a (m - 1)) (padicValInt 2 ((3 * b (m - 1) - 2 * a (m - 1)) - x))) := by sorry
end Erdos195