One-even bridge criterion with root bit 0: odd batches around a single new even letter
ProvedErdos195.one_even_bridge_falseA tree witness defines a strict total order on (milestone framework); its root bit decides the order between integers of different parity (: every even integer precedes every odd integer at the root). 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. Write , for the halved even and odd subwords (), and , .
Theorem (one-even bridge criterion, root bit 0). Let . Let be a word that is safe for some tree witness with root bit , let and be words of odd integers with and , and let be even. Then is -safe if and only if
and the following root conditions hold:
- for every even and : , or , or ( and );
- for every even and : or ;
- for every odd with : ;
- for odd before even in with : , or ( and );
- for even before odd in with : .
This is the root-bit-0 companion of the one-even bridge criterion (root bit 1). With root bit 0 every NEW odd letter that follows an old even letter (including ) must be closed by or (conditions 1 and 2), whereas the even target itself needs no reflections, only condition 3 for odd letters reflected into the tail. After the odd shift (which flips the root bit and swaps parities), the case is the root-bit-1 exact lifting criterion for an even batch followed by an odd target; the tail is the new ingredient. Together with the root-bit-1 bridge, this gives exact criteria for both root bits.
Formalization note: words are List ℤ, membership/first-occurrence via List.idxOf, safety is Safe (treeLt θ), halves via filter/map (· / 2).
import Mathlib import Definitions.Def_Erdos195_tree
namespace Erdos195
theorem one_even_bridge_false (θ : ℕ → ℤ → Bool) (h00 : θ 0 0 = false) (S P T : List ℤ) (y : ℤ)
(hS : ∃ θS : ℕ → ℤ → Bool, θS 0 0 = false ∧ Safe (treeLt θS) S)
(hPo : ∀ p ∈ P, p % 2 = 1) (hTo : ∀ t ∈ T, t % 2 = 1) (hy : y % 2 = 0) (hyS : y ∉ S)
(hPS : ∀ p ∈ P, p ∉ S) (hTS : ∀ t ∈ T, t ∉ S ++ P) :
Safe (treeLt θ) (S ++ P ++ [y] ++ T) ↔
Safe (treeLt (fun k r => θ (k + 1) (2 * r)))
(((S ++ [y]).filter (fun x => decide (x % 2 = 0))).map (· / 2)) ∧
Safe (treeLt (fun k r => θ (k + 1) (2 * r + 1)))
(((S ++ P ++ T).filter (fun x => decide (x % 2 = 1))).map (· / 2)) ∧
(∀ a ∈ S, a % 2 = 0 → ∀ b ∈ P,
2 * b - a ∈ S ∨ 3 * b - 2 * a ∈ S ++ P ∨ (2 * b - a ≠ y ∧ 3 * b - 2 * a ∈ T)) ∧
(∀ a ∈ S ++ [y], a % 2 = 0 → ∀ b ∈ T,
2 * b - a ∈ S ++ [y] ∨ 3 * b - 2 * a ∈ S ++ P ++ T) ∧
(∀ a ∈ S ++ P, a % 2 = 1 → 2 * y - a ∈ T → 3 * y - 2 * a ∈ S) ∧
(∀ a ∈ S, ∀ b ∈ S, a % 2 = 1 → b % 2 = 0 → S.idxOf a < S.idxOf b →
2 * b - a ∉ S → 2 * b - a ∈ P ++ T →
3 * b - 2 * a ∈ S ∨ (3 * b - 2 * a = y ∧ 2 * b - a ∉ P)) ∧
(∀ a ∈ S, ∀ b ∈ S, a % 2 = 0 → b % 2 = 1 → S.idxOf a < S.idxOf b →
2 * b - a = y → 3 * b - 2 * a ∈ S ++ P) := by sorry
end Erdos195