After a sink step, the sink passes back along the path: the previous third term becomes a true sink
ProvedErdos195.sink_step_inheritsA 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 tree-safe and let , , be an open path in whose sink fourth term is not in . Put . Assume uniqueness: every in-order pair of with and has . Then in the word :
- every path pair , , is still an in-order pair, and no third term lies in (in particular ), so is an open path of whose sink fourth term is (for );
- satisfies C1 in : every in-order pair of with has .
So is a true-sink fourth term of . Together with milestone #149 (an open path can only be closed from the sink backwards) this shows that the backward closure of a path is a sequence of true-sink steps. The fact uses the ruler law (#148) and the exact valuation of the telescoping sum.
import Mathlib import Definitions.Def_Erdos195_tree
namespace Erdos195
theorem sink_step_inherits (T : List ℤ) (hS : ∃ θ : ℕ → ℤ → Bool, Safe (treeLt θ) T)
(m : ℕ) (a b : ℕ → ℤ) (hm : 0 < m)
(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)
(hU : ∀ x y : ℤ, x ∈ T → y ∈ T → T.idxOf x < T.idxOf y →
2 * y - x = 2 * b (m - 1) - a (m - 1) → 3 * y - 2 * x ∉ T →
3 * y - 2 * x = 3 * b (m - 1) - 2 * a (m - 1)) :
(∀ i < m, a i ∈ T ++ [3 * b (m - 1) - 2 * a (m - 1)]) ∧
(∀ i < m, b i ∈ T ++ [3 * b (m - 1) - 2 * a (m - 1)]) ∧
(∀ i < m, (T ++ [3 * b (m - 1) - 2 * a (m - 1)]).idxOf (a i) <
(T ++ [3 * b (m - 1) - 2 * a (m - 1)]).idxOf (b i)) ∧
(∀ i < m, 2 * b i - a i ∉ T ++ [3 * b (m - 1) - 2 * a (m - 1)]) ∧
(∀ x y : ℤ, x ∈ T ++ [3 * b (m - 1) - 2 * a (m - 1)] → y ∈ T ++ [3 * b (m - 1) - 2 * a (m - 1)] →
(T ++ [3 * b (m - 1) - 2 * a (m - 1)]).idxOf x < (T ++ [3 * b (m - 1) - 2 * a (m - 1)]).idxOf y →
2 * y - x = 2 * b (m - 1) - a (m - 1) →
3 * y - 2 * x ∈ T ++ [3 * b (m - 1) - 2 * a (m - 1)]) := by sorry
end Erdos195