Escape chains terminate at every node, for every tree witness
ProvedErdos195.escape_chain_terminates_treeA 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 for some tree witness , and let be letters of with before and (a "wrong" in-order pair at the node of ). Put , so and . Then there is such that all occur in , occur after , and either
- (reflection) occurs after , and occurs in before ; or
- (reversal) and occurs before .
Since and , all pairs lie at the same node and are wrong for ; the chain cannot go on forever because the are distinct and is finite. This generalizes milestone #142 (the root-node case , odd, even) to arbitrary levels, nodes and witnesses.
import Mathlib import Definitions.Def_Erdos195_tree
namespace Erdos195
theorem escape_chain_terminates_tree (θ : ℕ → ℤ → Bool) (Q : List ℤ)
(hS : Safe (treeLt θ) Q) (o w : ℤ) (ho : o ∈ Q) (hw : w ∈ Q)
(hi : Q.idxOf o < Q.idxOf w) (hlt : treeLt θ o w) :
∃ n : ℕ, (∀ m ≤ n, o + 3 ^ m * (w - o) ∈ Q) ∧
(∀ m < n, Q.idxOf o < Q.idxOf (o + 3 ^ m * (w - o))) ∧
((Q.idxOf o < Q.idxOf (o + 3 ^ n * (w - o)) ∧
2 * (o + 3 ^ n * (w - o)) - o ∈ Q ∧
Q.idxOf (2 * (o + 3 ^ n * (w - o)) - o) < Q.idxOf (o + 3 ^ n * (w - o))) ∨
(0 < n ∧ Q.idxOf (o + 3 ^ n * (w - o)) < Q.idxOf o)) := by sorry
end Erdos195