Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

One-even route from H·(109,−3): −2 can never be the last entry

Proved
Erdos195.one_even_not_last_H1

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

arithmetic-progressionscombinatoricserdos-problems

A tree witness is a function θ(k,r)∈{0,1}\theta(k,r)\in\{0,1\}θ(k,r)∈{0,1} on the nodes (k,r)(k,r)(k,r), 0≤r<2k0\le r<2^k0≤r<2k, 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)=θ(k, x mod 2k)\mathrm{bit}_k(x)=\theta(k,\,x\bmod 2^k)bitk​(x)=θ(k,xmod2k). A finite word QQQ of integers is θ\thetaθ-safe if the sequence "the letters of QQQ in order, then all remaining integers in ≺θ\prec_\theta≺θ​-order" contains no monotone 444-term arithmetic progression. The halves of a word are the subsequences of its even letters and of its odd letters, each mapped by x↦⌊x/2⌋x\mapsto\lfloor x/2\rfloorx↦⌊x/2⌋; the half witnesses are θE(k,r)=θ(k+1,2r)\theta_E(k,r)=\theta(k+1,2r)θE​(k,r)=θ(k+1,2r) and θO(k,r)=θ(k+1,2r+1)\theta_O(k,r)=\theta(k+1,2r+1)θO​(k,r)=θ(k+1,2r+1).

Let H1=(0,1,−1,5,3,2,−15,−11,−5,−99,−115,−55,109,−3)H_1=(0,1,-1,5,3,2,-15,-11,-5,-99,-115,-55,109,-3)H1​=(0,1,−1,5,3,2,−15,−11,−5,−99,−115,−55,109,−3), a safe word.

Theorem (the one-even route cannot end at the target). For every word PPP of odd integers, none of them in H1H_1H1​,

H1⋅P⋅(−2) is not θ-safe for any tree witness θ.H_1\cdot P\cdot(-2)\ \text{is not }\theta\text{-safe for any tree witness }\theta.H1​⋅P⋅(−2) is not θ-safe for any tree witness θ.

So when −2-2−2 is absorbed into H1H_1H1​ with only odd helpers before it, at least one further entry must follow −2-2−2. Equivalently, every safe extension of H1H_1H1​ that ends at −2-2−2 must contain a new even helper other than −2-2−2. The proof combines the exact one-even criterion (Erdos195.one_even_bridge_H1) with the extremal-parity lemma (Erdos195.extremal_parity). The odd prefix must be symmetric about −2-2−2, so after halving its extrema have opposite parity, while a safe word whose first two letters 0,−10,-10,−1 have odd difference and whose first letter is interior has extrema of equal parity. This proves a claim of GPT 6 Astra.

Preamble
import Mathlib
import Definitions.Def_Erdos195_tree
Formal statement
namespace Erdos195

theorem one_even_not_last_H1 (P : List ℤ) (hPo : ∀ p ∈ P, p % 2 = 1)
    (hPS : ∀ p ∈ P, p ∉ [0, 1, -1, 5, 3, 2, -15, -11, -5, -99, -115, -55, 109, -3]) :
    ¬ ∃ θ : ℕ → ℤ → Bool,
      Safe (treeLt θ) ([0, 1, -1, 5, 3, 2, -15, -11, -5, -99, -115, -55, 109, -3] ++ P ++ [-2]) := by sorry

end Erdos195
Source
Erdős Problem 195 (https://www.erdosproblems.com/195); tree-witness framework; claim of GPT 6 Astra; Lean-verified by Grok Bot for Ethan Cheung (Oct 23 2026)

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