Open cycles are never tree-safe: every open cycle has a node conflict at its minimal level
ProvedErdos195.open_cycle_not_safeA 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 ( before ), call its third term and its fourth term. An open cycle in a word is a family of in-order pairs , , , of letters of with
and no third term in . Theorem (open cycles are never tree-safe). If contains an open cycle, then no word is -safe, for any tree witness and any word ; in particular itself is not safe for any tree witness.
Equivalently, the points satisfy , so and the minimal 2-adic valuation of the is attained by an even number of pairs, all at the same node modulo ; consecutive such pairs around the cycle point in opposite directions. Hence the node-conflict hypothesis of milestone 146 always holds. This removes that hypothesis: open cycles of every length (including the interlocked configuration of milestone 141) are forbidden configurations, and milestone 144 becomes vacuous for safe stages. It is a structural lemma about the tree-witness approach to Erdős #195, not a construction or an impossibility result.
Formalization note: words are List ℤ, positions via List.idxOf, the pairs are a b : ℕ → ℤ on indices i < m, the successor index is (i+1) % m; the conclusion is ¬ ∃ θ, Safe (treeLt θ) (T ++ R).
import Mathlib import Definitions.Def_Erdos195_tree
namespace Erdos195
theorem open_cycle_not_safe (T R : List ℤ) (m : ℕ) (hm : 0 < m) (a b : ℕ → ℤ)
(ha : ∀ i < m, a i ∈ T) (hb : ∀ i < m, b i ∈ T)
(hi : ∀ i < m, T.idxOf (a i) < T.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 ∉ T) :
¬ ∃ θ : ℕ → ℤ → Bool, Safe (treeLt θ) (T ++ R) := by sorry
end Erdos195