One-even bridge criterion: odd batches around a single new even letter (root bit 1)
ProvedErdos195.one_even_bridgeA tree witness is a function on the nodes , , of the binary tree of residues. For distinct integers with , put iff . 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. The halves of a word are the subsequences of its even letters and of its odd letters, each mapped by ; the half witnesses are and .
Theorem (one-even bridge criterion, root bit ). Let . Let be a word that is -safe for some witness with . Let and be words of odd integers with no letter of in and no letter of in , and let be even. Then
if and only if
- the even half of is -safe and the odd half of is -safe;
- (closing pairs into ) for every odd : or ;
- (progressions with third term ) for every even and odd with and before : ;
- (new third terms of pairs of ) for odd and even in , before , with but : either , or and .
This is the exact root-level criterion for absorbing a single new even letter into a root-bit- word using only odd helpers placed before and after it: nothing is required of the odd batches except odd-half safety, while the letters before must be (almost) closed under reflection . It complements the lifting criteria Erdos195.lifting_criterion and Erdos195.lifting_criterion_true (odd target after an even batch). Formalization note: itself only needs to be safe for some root-bit- witness, not for .
import Mathlib import Definitions.Def_Erdos195_tree
namespace Erdos195
theorem one_even_bridge (θ : ℕ → ℤ → Bool) (h00 : θ 0 0 = true) (S P T : List ℤ) (y : ℤ)
(hS : ∃ θS : ℕ → ℤ → Bool, θS 0 0 = true ∧ 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 ++ P, a % 2 = 1 → 2 * y - a ∈ S ++ P ∨ 3 * y - 2 * a ∈ S) ∧
(∀ a ∈ S, a % 2 = 0 → ∀ b ∈ S ++ P, b % 2 = 1 → 2 * b - a = y →
(S ++ P).idxOf a < (S ++ P).idxOf b → 3 * b - 2 * a ∈ S ++ P) ∧
(∀ 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)) := by sorry
end Erdos195