Root conflict for : tree-safe words meet
ProvedErdos195.tree_Pn_cor3A tree witness is a function on the nodes , , of the binary tree of residues. For distinct integers with , put iff (two's-complement digits). A finite word of integers is -safe if the sequence "the letters of in order, then all remaining integers in -order" contains no monotone -term arithmetic progression. Let , and . In every -safe word (any tree witness ) containing in which occurs before and occurs before ,
because the open pairs and would force opposite values at the root node. In particular every tree-safe extension of (in any order) that contains after its prefix and contains one of these four numbers: the fourth-term repair of the family fails (Erdős Problem 195).
Formalization note: treeLt θ is from Definitions.Def_Erdos195_tree; Safe, bitOne are from Definitions.Def_Erdos195_defs. "Begins with" is the list prefix relation <+:; positions in a word are List.idxOf. The statement quantifies over every witness θ, so it holds in particular for all ε-orders.
import Mathlib import Definitions.Def_Erdos195_tree
namespace Erdos195
theorem tree_Pn_cor3 (n : ℕ) (hn : 1 ≤ n) (θ : ℕ → ℤ → Bool) (Q : List ℤ)
(hS : Safe (treeLt θ) Q)
(h0 : (0 : ℤ) ∈ Q) (h1 : (1 : ℤ) ∈ Q) (hN : (2 : ℤ) ^ n + 1 ∈ Q) (hT : 4 * (2 : ℤ) ^ n ∈ Q)
(i0 : Q.idxOf 0 < Q.idxOf ((2 : ℤ) ^ n + 1)) (i1 : Q.idxOf 1 < Q.idxOf (4 * (2 : ℤ) ^ n)) :
2 * (2 : ℤ) ^ n + 2 ∈ Q ∨ 3 * (2 : ℤ) ^ n + 3 ∈ Q ∨ 2 * (4 * (2 : ℤ) ^ n) - 1 ∈ Q ∨
3 * (4 * (2 : ℤ) ^ n) - 2 ∈ Q := by sorry
end Erdos195