Extending , , by with one helper works iff
ProvedErdos195.zero_u_single_helper_classificationFix 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 be integers. The following are equivalent:
Thus, outside the single exceptional relation , absorbing a new target into the safe word with requires at least two auxiliary letters, wherever they are placed. This is a sharp case of the one-step extension problem for Ho-style constructions of -AP-free permutations of (Erdős Problem 195); e.g. for every needs at least two helpers.
Formalization note: "begins with " is [0, u] <+: Q; the letter bound is ∀ x ∈ Q, x = 0 ∨ x = u ∨ x = t ∨ x = h; Safe, epsLt come from Definitions.Def_Erdos195_defs.
import Mathlib import Definitions.Def_Erdos195_defs
namespace Erdos195
theorem zero_u_single_helper_classification (u t : ℤ) (hu : u % 4 = 3) (ht : t % 4 = 2) :
((∃ (ε : ℕ → Bool) (Q : List ℤ) (h : ℤ), [0, u] <+: Q ∧ t ∈ Q ∧
(∀ x ∈ Q, x = 0 ∨ x = u ∨ x = t ∨ x = h) ∧ Safe (epsLt ε) Q) ↔ 3 * t = 2 * u) ∧
((∃ ε : ℕ → Bool, Safe (epsLt ε) [0, u, t]) ↔ 3 * t = 2 * u) := by sorry
end Erdos195