Sink steps are blocked only by other sinks' trees
ProvedErdos195.sink_append_blocked_by_other_sinkA 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; the pair is fully open in if neither lies in . An open path in is a family of in-order pairs , , of letters of with for and no third term in .
Theorem. Let be -safe, let , and assume the C1 condition for : whenever for an in-order pair of , we have (true for the fourth term of a true sink). If is not -safe for any tree witness , then there are with and a fully open in-order pair of with , , and opposite orientation (the -th binary digits of and differ). This is a node conflict. Moreover:
- no open path starting at has last fourth term equal to ;
- lies on an open path ending at a true sink (in the sense of the previous milestone) whose fourth term is different from .
So appending the sink fourth term , the forced first step of closing a path (milestone #149), can only be blocked by a fully open pair belonging to the in-tree of a different sink. In particular, if every fully open pair of not released by reaches , then is tree-safe. The proof combines milestones #59, #153 and the previous milestone.
import Mathlib import Definitions.Def_Erdos195_tree
namespace Erdos195
theorem sink_append_blocked_by_other_sink (θ : ℕ → ℤ → 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)
(hbad : ¬ ∃ θ' : ℕ → ℤ → Bool, Safe (treeLt θ') (T ++ [w])) :
∃ x x' y' : ℤ, x ∈ T ∧ 2 * w - x ∉ T ∧ 3 * w - 2 * x ∉ T ∧
x' ∈ T ∧ y' ∈ T ∧ T.idxOf x' < T.idxOf y' ∧ 2 * y' - x' ∉ T ∧ 3 * y' - 2 * x' ∉ T ∧
3 * y' - 2 * x' ≠ w ∧
padicValInt 2 (y' - x') = padicValInt 2 (w - x) ∧
x' % 2 ^ padicValInt 2 (y' - x') = x % 2 ^ padicValInt 2 (y' - x') ∧
¬ (bitOne y' (padicValInt 2 (y' - x')) ↔ bitOne w (padicValInt 2 (y' - x'))) ∧
(∀ (m : ℕ) (a b : ℕ → ℤ), a 0 = x' → b 0 = y' →
(∀ 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) ≠ w) ∧
(∃ (m : ℕ) (a b : ℕ → ℤ), 0 < m ∧ a 0 = x' ∧ b 0 = y' ∧
(∀ 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) := by sorry
end Erdos195