Shield lemma: is tree-safe and releases the node
ProvedErdos195.shield_safeA tree witness is a function on the nodes , , of the binary tree of residues. For distinct integers with , put iff (two's-complement digits). 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; it is tree-safe if it is -safe for some . An in-order pair of ( occurs before ) is open if and ; an open pair lies at the node , , and -safety requires there. For all integers , the four-letter word
is tree-safe, it closes the pair (its fourth term is present), and every open in-order pair of lying at the node forces the bit opposite to , . (Concretely, the open pairs are , , , at levels , , ; for this is the word .) Thus a 'shield' releases the value forced at by the pair : unlike the bare fourth-term completion, it flips the requirement at that node. This is a release lemma for two-letter prefixes in the tree-witness approach to Erdős Problem 195.
Formalization note: treeLt θ is from Definitions.Def_Erdos195_tree; Safe, bitOne are from Definitions.Def_Erdos195_defs. Positions in a word are List.idxOf; P ++ [c] appends c.
import Mathlib import Definitions.Def_Erdos195_tree
namespace Erdos195
theorem shield_safe (u w : ℤ) (huw : u ≠ w) :
(∃ θ : ℕ → ℤ → Bool, Safe (treeLt θ) [u, w, 6 * w - 5 * u, 3 * w - 2 * u]) ∧
3 * w - 2 * u ∈ [u, w, 6 * w - 5 * u, 3 * w - 2 * u] ∧
(∀ a b : ℤ, a ∈ [u, w, 6 * w - 5 * u, 3 * w - 2 * u] → b ∈ [u, w, 6 * w - 5 * u, 3 * w - 2 * u] →
[u, w, 6 * w - 5 * u, 3 * w - 2 * u].idxOf a < [u, w, 6 * w - 5 * u, 3 * w - 2 * u].idxOf b →
2 * b - a ∉ [u, w, 6 * w - 5 * u, 3 * w - 2 * u] →
3 * b - 2 * a ∉ [u, w, 6 * w - 5 * u, 3 * w - 2 * u] →
padicValInt 2 (b - a) = padicValInt 2 (w - u) →
a % 2 ^ padicValInt 2 (w - u) = u % 2 ^ padicValInt 2 (w - u) →
(bitOne b (padicValInt 2 (w - u)) ↔ ¬ bitOne w (padicValInt 2 (w - u)))) := by sorry
end Erdos195