Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Any finite set of odd integers extends the prefix (0,1)(0,1)(0,1) with no other even entries

Proved
Erdos195.zero_one_odd_finite_extension

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

arithmetic-progressionscombinatoricserdos-problems

A tree witness is a function θ:N×Z→{0,1}\theta:\mathbb N\times\mathbb Z\to\{0,1\}θ:N×Z→{0,1} on the nodes (k,r)(k,r)(k,r) of the binary tree of residues. For distinct integers x,yx,yx,y with k=ν2(y−x)k=\nu_2(y-x)k=ν2​(y−x), put x≺θyx\prec_\theta yx≺θ​y iff bitk(x)=1⇔θ(k, x mod 2k)=1\mathrm{bit}_k(x)=1\Leftrightarrow\theta(k,\,x\bmod 2^k)=1bitk​(x)=1⇔θ(k,xmod2k)=1. A finite word QQQ is θ\thetaθ-safe if the completion “letters of QQQ in order, then all remaining integers in ≺θ\prec_\theta≺θ​-order” contains no monotone 444-term arithmetic progression. Positions are first occurrences.

Corollary. For every finite set FFF of odd integers there is a duplicate-free word QQQ which begins with the prefix (0,1)(0,1)(0,1), contains every element of FFF, has no even entry other than 000, and is tree-safe for some witness θ\thetaθ.

The construction is the one recorded in the safe-word composition note. Let H={0}∪{(z−1)/2:z∈F}H=\{0\}\cup\{(z-1)/2:z\in F\}H={0}∪{(z−1)/2:z∈F} and apply the specified-first ordering lemma to obtain a tree-safe word AAA with underlying set HHH beginning with 000. Output

Q=(0)⋅(1+2A).Q=(0)\cdot(1+2A).Q=(0)⋅(1+2A).

The official parity decomposition of tree safety reduces the claim to safety of the even child (0)(0)(0) and of the odd child AAA, together with a root condition. Mixed-parity in-order pairs in QQQ necessarily begin with the unique even letter 000, so they force θ(0,0)=1\theta(0,0)=1θ(0,0)=1, consistently.

This handles arbitrarily many prescribed positive and negative odd integers simultaneously while preserving the prefix (0,1)(0,1)(0,1). It does not justify inserting a new even integer after the odd block has begun, is not a true-root-release statement, and does not settle Erdős #195.

Formalization Note The prefix hypothesis is Q=0::1::TQ=0::1::TQ=0::1::T for some tail TTT. Safety is official Safe (treeLt θ). The lemma specified_first_safe_order supplies AAA; the gluing step uses official safe_parity_decomp.

Preamble
import Mathlib
import Definitions.Def_Erdos195_tree
Formal statement
namespace Erdos195

theorem zero_one_odd_finite_extension (F : Finset ℤ) (hF : ∀ z ∈ F, z % 2 = 1) :
    ∃ Q : List ℤ, Q.Nodup ∧ (∃ T : List ℤ, Q = 0 :: 1 :: T) ∧ (∀ z ∈ F, z ∈ Q) ∧
      (∀ z ∈ Q, z % 2 = 0 → z = 0) ∧
      ∃ θ : ℕ → ℤ → Bool, Safe (treeLt θ) Q := by sorry

end Erdos195
Source
Erdős Problem 195 (https://www.erdosproblems.com/195); derived from analysis relayed by Ethan Cheung, hand-checked against the official Safe / treeLt / specified_first_safe_order / safe_parity_decomp definitions, Lean-verified.

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 paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me