Tree-safe words starting containing must meet
ProvedErdos195.zero_one_negone_mod4_oneA 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 be a -safe word (for any tree witness ) beginning with , and let with , . Then
Indeed the in-order pairs and both sit at the tree node and, if both were open (neither continuation , present), would force opposite values there. This is the fixed-node cascade behind the failure of the rule "close the newest conflicting pair by its fourth term" when extending in Ho-style constructions of -AP-free permutations of (Erdős Problem 195); the case gives the necessary condition .
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 zero_one_negone_mod4_one (θ : ℕ → ℤ → Bool) (Q : List ℤ) (hS : Safe (treeLt θ) Q)
(hpre : [0, 1, -1] <+: Q) (t : ℤ) (ht : t ∈ Q) (ht4 : t % 4 = 1) (ht1 : t ≠ 1) :
-3 ∈ Q ∨ -5 ∈ Q ∨ 2 * t + 1 ∈ Q ∨ 3 * t + 2 ∈ Q := by sorry
end Erdos195