Open cycles of pairs block exhaustive chains of tree-safe words
ProvedErdos195.open_cycle_blocks_exhaustive_chainA 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 (a before b), call its third term and its fourth term. Theorem (open cycles block exhaustive chains). Let be finite words with each a prefix of , each -safe for some tree witness (which may depend on ), and such that every integer occurs in some . Then no stage contains a cycle of in-order pairs , , , with
and all third terms absent from .
So an exhaustive chain of tree-safe words (the kind of chain that would give a permutation of with no monotone 4-term AP) must never create such a cycle, of any length, at any stage. This is a forbidden-configuration result for the tree-witness method for Erdős #195, not a resolution of the problem.
Formalization note: the chain is P : ℕ → List ℤ with P n <+: P (n+1), safety is ∃ θ, Safe (treeLt θ) (P n), coverage is ∀ x, ∃ n, x ∈ P n; positions via List.idxOf, successor index (i+1) % m.
import Mathlib import Definitions.Def_Erdos195_tree
namespace Erdos195
theorem open_cycle_blocks_exhaustive_chain (P : ℕ → List ℤ) (hpre : ∀ n, P n <+: P (n + 1))
(hsafe : ∀ n, ∃ θ : ℕ → ℤ → Bool, Safe (treeLt θ) (P n)) (hcov : ∀ x : ℤ, ∃ n, x ∈ P n)
(N m : ℕ) (hm : 0 < m) (a b : ℕ → ℤ)
(ha : ∀ i < m, a i ∈ P N) (hb : ∀ i < m, b i ∈ P N)
(hi : ∀ i < m, (P N).idxOf (a i) < (P N).idxOf (b i))
(hcyc : ∀ i < m, 3 * b i - 2 * a i = 2 * b ((i + 1) % m) - a ((i + 1) % m))
(ht : ∀ i < m, 2 * b i - a i ∉ P N) : False := by sorry
end Erdos195