Reflection absorption for a one-grandchild block: is tree-safe
ProvedErdos195.block_reflection_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 .
Theorem (reflection absorption for a one-grandchild block). Let , , and let be a finite word such that is SAFE. Suppose that
- for every (so and lie in the same class mod but in opposite classes mod ),
- all entries of are congruent modulo (one grandchild), and
- and .
Then the word
is SAFE. Thus the target is absorbed last, using exactly auxiliary letters (the reflection of about , in the original order).
Formalization note: treeLt θ is from Definitions.Def_Erdos195_tree, and Safe is from Definitions.Def_Erdos195_defs. The hypotheses are stated with divisibility: and ; ; . a :: B ++ L parses as (a :: B) ++ L.
import Mathlib import Definitions.Def_Erdos195_tree
namespace Erdos195
theorem block_reflection_absorption (a y : ℤ) (k : ℕ) (B : List ℤ)
(hB : ∀ b ∈ B, (2 : ℤ) ^ k ∣ b - a ∧ ¬ (2 : ℤ) ^ (k + 1) ∣ b - a)
(hG : ∀ b ∈ B, ∀ b' ∈ B, (2 : ℤ) ^ (k + 2) ∣ b' - b)
(hy : (2 : ℤ) ^ (k + 1) ∣ y - a) (hya : y ≠ a)
(hQ : ∃ θ : ℕ → ℤ → Bool, Safe (treeLt θ) (a :: B)) :
∃ θ' : ℕ → ℤ → Bool, Safe (treeLt θ') (a :: B ++ B.map (fun b => 2 * y - b) ++ [y]) := by sorry
end Erdos195