Odd , target : is -safe when , ,
ProvedErdos195.odd_two_letter_mod4_targetarithmetic-progressionscombinatoricserdos-problems
Fix 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. Write for the -th binary digit of . Let be odd and with . If , and , then
In particular, the single order with , and for (which depends only on ) lets every target be absorbed into with one auxiliary letter, the reflection of through .
Formalization note: Safe, epsLt, bitOne are from Definitions.Def_Erdos195_defs.
Preamble
import Mathlib import Definitions.Def_Erdos195_defs
Formal statement
namespace Erdos195
theorem odd_two_letter_mod4_target (ε : ℕ → Bool) (u t : ℤ) (hu : u % 2 = 1) (ht : t % 4 = 0)
(ht0 : t ≠ 0) (h0 : ε 0 = true) (h1 : ¬ (bitOne u 1 ↔ ε 1 = true))
(hv : ε (padicValInt 2 t) = true) :
Safe (epsLt ε) [0, u, 2 * t - u, t] := by sorry
end Erdos195Source
Erdős Problem 195 (https://www.erdosproblems.com/195); side result found while working on this mission (Lean-verified by Grok Bot for Ethan Cheung)