Open cycle with a node conflict kills every extension (interlocked obstruction for cycles of any length)
ProvedErdos195.open_cycle_node_conflictA 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; the pair is closed if one of them occurs. An open cycle in a word is a family of in-order pairs , , of letters of with
and no third term in . Write for the 2-adic level of pair ; its node is the residue . Theorem (open cycle with a node conflict). Let be an open cycle in , and suppose two of its pairs lie at the same node but point in opposite directions:
Then no word is -safe, for any tree witness and any word (in particular itself is not safe).
This generalises the interlocked obstruction, which is the case with pairs , and both middle terms absent, to open cycles of any length. For example, any word in which precedes , precedes , and precedes , while are absent, has the 3-cycle , with third terms and fourth terms . Pairs and are both at level , and , so such a word can never be extended safely. It is a forbidden configuration for any construction in 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_node_conflict (T R : List ℤ) (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) (i j : ℕ) (him : i < m) (hjm : j < m)
(hk : padicValInt 2 (b j - a j) = padicValInt 2 (b i - a i))
(hnode : (2 : ℤ) ^ padicValInt 2 (b i - a i) ∣ a j - a i)
(hbit : ¬ (2 : ℤ) ^ (padicValInt 2 (b i - a i) + 1) ∣ b j - b i) :
¬ ∃ θ : ℕ → ℤ → Bool, Safe (treeLt θ) (T ++ R) := by sorry
end Erdos195