A prefix of a -AP-free enumeration of is safe for some -order iff its open pairs are digit-consistent
ProvedErdos195.exists_eps_safe_prefix_iffLet be a bijection containing no monotone -term arithmetic progression, and fix a cut . Call a pair of positions open at if both values and occur in at positions . For let be the -adic order on (for with : iff the -th two's-complement digit of equals ), and call the prefix -safe if the completion "prefix, then all remaining integers in -order" has no monotone -AP. Then
This eliminates the order from Ho-style constructions with stage-dependent : a chain of prefixes, each safe for its own -order, exhausting is exactly a -AP-free enumeration of with infinitely many cuts at which the open pairs impose consistent binary-digit constraints (each open pair forces to be the -th digit of the later value ). It reduces the stage-dependent- approach to Erdős Problem 195 to a purely combinatorial condition on the permutation; it does not by itself decide whether such permutations exist.
import Mathlib import Definitions.Def_Erdos195_defs
namespace Erdos195
theorem exists_eps_safe_prefix_iff (f : ℕ ≃ ℤ) (hf : ¬ HasMonotoneAP f 4) (N : ℕ) :
(∃ ε : ℕ → Bool, Safe (epsLt ε) ((List.range N).map f)) ↔
∀ i j i' j' : ℕ, i < j → j < N → N ≤ f.symm (2 * f j - f i) →
N ≤ f.symm (3 * f j - 2 * f i) →
i' < j' → j' < N → N ≤ f.symm (2 * f j' - f i') → N ≤ f.symm (3 * f j' - 2 * f i') →
padicValInt 2 (f j - f i) = padicValInt 2 (f j' - f i') →
(bitOne (f j) (padicValInt 2 (f j - f i)) ↔
bitOne (f j') (padicValInt 2 (f j' - f i'))) := by sorry
end Erdos195