Tree-safety is invariant under , odd
ProvedErdos195.treeLt_safe_affinearithmetic-progressionscombinatoricserdos-problems
A 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. Let be odd and . If is -safe, then the letterwise image is -safe for some tree witness :
Thus tree-safety, unlike -safety, is invariant under all affine maps with odd.
Formalization note: treeLt θ is from Definitions.Def_Erdos195_tree; Safe, bitOne, No3AP, Star, HasMonotoneAP are from Definitions.Def_Erdos195_defs. Positions in a word are List.idxOf; is padicValInt 2.
Preamble
import Mathlib import Definitions.Def_Erdos195_tree
Formal statement
namespace Erdos195
theorem treeLt_safe_affine (u v : ℤ) (hu : Odd u) (θ : ℕ → ℤ → Bool) (Q : List ℤ)
(h : Safe (treeLt θ) Q) :
∃ θ' : ℕ → ℤ → Bool, Safe (treeLt θ') (Q.map (fun x => u * x + v)) := by sorry
end Erdos195Source
Erdős Problem 195 (https://www.erdosproblems.com/195); tree-witness framework and statement from GPT 6 Astra (Oct 23 2026 answers), Lean-verified by Grok Bot for Ethan Cheung