Scaling transports tree safety to the shifted subtree witness, both directions
ProvedErdos195.safe_affine_scale_iffA tree witness is a function on the nodes of the binary tree of residues. For distinct integers with , put iff ( is the -th two's-complement binary digit). A finite word of integers is -safe if the completion "the letters of in order, then all remaining integers in -order" contains no monotone -term arithmetic progression (positions of increasing, ). Positions in are first occurrences. Let and let be a finite word. Then the word is -safe if and only if is -safe, where :
The forward direction transports a safe word on one parity class down to a safe word for the shifted subtree witness (e.g. on odd words), and the backward direction is the lifting: any safe word for any witness lifts to a safe word on the class for every whose subtree at is .
import Mathlib import Definitions.Def_Erdos195_tree
namespace Erdos195
theorem safe_affine_scale_iff (θ : ℕ → ℤ → Bool) (c : ℤ) (hc : c = 0 ∨ c = 1) (P : List ℤ) :
Safe (treeLt θ) (P.map (fun y => 2 * y + c)) ↔
Safe (treeLt (fun k r => θ (k + 1) (2 * r + c))) P := by sorry
end Erdos195