Parity decomposition of -safety
ProvedErdos195.epsLt_safe_parity_decompFix and the -adic total order on given by iff and the -th two's-complement digit of equals , where . 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 , and for let be the word obtained from by keeping the letters , in order, and replacing each by . Then is -safe if and only if all of the following hold:
So safety splits into the two parity classes (a problem of the same kind one binary digit lower) plus cross-parity conditions that involve only . This reduces extension and merging questions for Ho-style constructions of -AP-free permutations of (Erdős Problem 195) to the rescaled parity classes.
Formalization note: Safe, epsLt are from Definitions.Def_Erdos195_defs; is (Q.filter (fun x => decide (x % 2 = 0))).map (fun x => x / 2), is the analogue with (x - 1) / 2; "precedes" is comparison of List.idxOf; condition (4) is stated as b % 2 = 1 ↔ ε 0 = true.
import Mathlib import Definitions.Def_Erdos195_defs
namespace Erdos195
theorem epsLt_safe_parity_decomp (ε : ℕ → Bool) (Q : List ℤ) :
Safe (epsLt ε) Q ↔
Safe (epsLt (fun k => ε (k + 1))) ((Q.filter (fun x => decide (x % 2 = 0))).map (fun x => x / 2)) ∧
Safe (epsLt (fun k => ε (k + 1)))
((Q.filter (fun x => decide (x % 2 = 1))).map (fun x => (x - 1) / 2)) ∧
(∀ a r : ℤ, r % 2 = 1 → a ∈ Q → a + r ∈ Q → a + 2 * r ∈ Q → a + 3 * r ∈ Q →
Q.idxOf a < Q.idxOf (a + r) → Q.idxOf (a + r) < Q.idxOf (a + 2 * r) →
¬ Q.idxOf (a + 2 * r) < Q.idxOf (a + 3 * r)) ∧
(∀ a r : ℤ, r % 2 = 1 → a ∈ Q → a + r ∈ Q → a + 2 * r ∈ Q →
Q.idxOf a < Q.idxOf (a + r) → Q.idxOf (a + r) < Q.idxOf (a + 2 * r) → a + 3 * r ∈ Q) ∧
(∀ a ∈ Q, ∀ b ∈ Q, Q.idxOf a < Q.idxOf b → (b - a) % 2 = 1 →
2 * b - a ∉ Q → 3 * b - 2 * a ∉ Q → (b % 2 = 1 ↔ ε 0 = true)) := by sorry
end Erdos195