The ≺_θ-least sink fourth term can always be appended (no sink deadlock)
ProvedErdos195.least_sink_append_safeA tree witness defines a strict total order on : for with , iff the -th binary digit of is exactly when . 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); is tree-safe if it is -safe for some . For an in-order pair of ( before ) call its third term and its fourth term. An open path in is a family of in-order pairs , , , with for and no third term in . Its sink fourth term is a true-sink fourth term of if and every in-order pair of with has (condition C1 for appending ).
Theorem. Let be -safe and let satisfy C1: every in-order pair of with has . Suppose that
Then (the word followed by ) is tree-safe.
This answers the deadlock question left by milestone #155: a failed sink step is caused by a fully open pair from the in-tree of another true sink , and here we show that such a blocking always forces . So the "blocks" relation between sinks is contained in and is acyclic, and the -least sink is never blocked.
import Mathlib import Definitions.Def_Erdos195_tree
namespace Erdos195
theorem least_sink_append_safe (θ : ℕ → ℤ → Bool) (T : List ℤ) (hS : Safe (treeLt θ) T)
(w : ℤ) (hwT : w ∉ T)
(hC1 : ∀ x y : ℤ, x ∈ T → y ∈ T → T.idxOf x < T.idxOf y → 2 * y - x = w → 3 * y - 2 * x ∈ T)
(hmin : ∀ (m : ℕ) (a b : ℕ → ℤ), 0 < m →
(∀ i < m, a i ∈ T) → (∀ i < m, b i ∈ T) →
(∀ i < m, T.idxOf (a i) < T.idxOf (b i)) →
(∀ i, i + 1 < m → 3 * b i - 2 * a i = 2 * b (i + 1) - a (i + 1)) →
(∀ i < m, 2 * b i - a i ∉ T) →
3 * b (m - 1) - 2 * a (m - 1) ∉ T →
(∀ x y : ℤ, x ∈ T → y ∈ T → T.idxOf x < T.idxOf y →
2 * y - x = 3 * b (m - 1) - 2 * a (m - 1) → 3 * y - 2 * x ∈ T) →
3 * b (m - 1) - 2 * a (m - 1) ≠ w →
treeLt θ w (3 * b (m - 1) - 2 * a (m - 1))) :
∃ θ' : ℕ → ℤ → Bool, Safe (treeLt θ') (T ++ [w]) := by sorry
end Erdos195