Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

A prefix of a 444-AP-free enumeration of Z\mathbb{Z}Z is safe for some ε\varepsilonε-order iff its open pairs are digit-consistent

Proved
Erdos195.exists_eps_safe_prefix_iff

by Ethan Cheung Wang · Oct 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

arithmetic-progressionscombinatoricserdos-problems

Let f:N→Zf:\mathbb{N}\to\mathbb{Z}f:N→Z be a bijection containing no monotone 444-term arithmetic progression, and fix a cut N∈NN\in\mathbb{N}N∈N. Call a pair of positions i<j<Ni<j<Ni<j<N open at NNN if both values 2f(j)−f(i)2f(j)-f(i)2f(j)−f(i) and 3f(j)−2f(i)3f(j)-2f(i)3f(j)−2f(i) occur in fff at positions ≥N\ge N≥N. For ε:N→{0,1}\varepsilon:\mathbb{N}\to\{0,1\}ε:N→{0,1} let ≺ε\prec_\varepsilon≺ε​ be the 222-adic order on Z\mathbb{Z}Z (for x≠yx\neq yx=y with k=ν2(y−x)k=\nu_2(y-x)k=ν2​(y−x): x≺εyx\prec_\varepsilon yx≺ε​y iff the kkk-th two's-complement digit of xxx equals εk\varepsilon_kεk​), and call the prefix f(0),…,f(N−1)f(0),\dots,f(N-1)f(0),…,f(N−1) ε\varepsilonε-safe if the completion "prefix, then all remaining integers in ≺ε\prec_\varepsilon≺ε​-order" has no monotone 444-AP. Then

∃ ε: f(0),…,f(N−1) is ε-safe  ⟺  for all pairs (i,j),(i′,j′) open at N with ν2(f(j)−f(i))=ν2(f(j′)−f(i′))=k,the k-th binary digits of f(j) and f(j′) coincide.\exists\,\varepsilon:\ f(0),\dots,f(N-1)\ \text{is }\varepsilon\text{-safe}\iff \begin{array}{l}\text{for all pairs }(i,j),(i',j')\text{ open at }N\text{ with }\nu_2(f(j)-f(i))=\nu_2(f(j')-f(i'))=k,\\ \text{the }k\text{-th binary digits of }f(j)\text{ and }f(j')\text{ coincide.}\end{array}∃ε: f(0),…,f(N−1) is ε-safe⟺for all pairs (i,j),(i′,j′) open at N with ν2​(f(j)−f(i))=ν2​(f(j′)−f(i′))=k,the k-th binary digits of f(j) and f(j′) coincide.​

This eliminates the order from Ho-style constructions with stage-dependent ε\varepsilonε: a chain of prefixes, each safe for its own ε\varepsilonε-order, exhausting Z\mathbb{Z}Z is exactly a 444-AP-free enumeration of Z\mathbb{Z}Z with infinitely many cuts at which the open pairs impose consistent binary-digit constraints (each open pair (i,j)(i,j)(i,j) forces εk\varepsilon_kεk​ to be the kkk-th digit of the later value f(j)f(j)f(j)). It reduces the stage-dependent-ε\varepsilonε approach to Erdős Problem 195 to a purely combinatorial condition on the permutation; it does not by itself decide whether such permutations exist.

Preamble
import Mathlib
import Definitions.Def_Erdos195_defs
Formal statement
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
Source
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)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paper
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me