Two-entry target-last absorption: every two-letter word absorbs any new target with at most one helper
ProvedErdos195.two_entry_absorptionA 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. is SAFE if it is -safe for some tree witness . Let be integers and let . Put and , and define
Then has distinct entries and is SAFE. So any two-letter word can absorb an arbitrary new target placed last, with at most one auxiliary letter . Note that the hypotheses do not require itself to have any property, since every two-letter word is SAFE. This is the base case of the local absorption recipes (Astra) in the tree-witness approach to Erdős Problem 195.
Formalization note: treeLt θ is from Definitions.Def_Erdos195_tree, and Safe is from Definitions.Def_Erdos195_defs. Positions are List.idxOf, and is padicValInt 2.
import Mathlib import Definitions.Def_Erdos195_tree
namespace Erdos195
theorem two_entry_absorption (a b y : ℤ) (hab : a ≠ b) (hya : y ≠ a) (hyb : y ≠ b) :
let W : List ℤ := if padicValInt 2 (y - a) ≤ padicValInt 2 (b - a) then [a, b, y]
else [a, b, 2 * y - b, y]
W.Nodup ∧ ∃ θ : ℕ → ℤ → Bool, Safe (treeLt θ) W := by sorry
end Erdos195