Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Forced escape after the prefix (0,1,x)(0,1,x)(0,1,x) with x≡3(mod4)x\equiv 3\pmod{4}x≡3(mod4)

Proved
Erdos195.forced_escape_prefix

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

arithmetic-progressionscombinatoricserdos-problems

Let θ\thetaθ be a tree witness, and let QQQ be a θ\thetaθ-safe finite word which is a true root release and begins with the prefix (0,1,x)(0,1,x)(0,1,x), where x≥3x\ge 3x≥3 and x≡3(mod4)x\equiv 3\pmod{4}x≡3(mod4). Then

3x∈Q,3x\in Q,3x∈Q,

and at least one of the following holds:

3x−2∈Q,7x∈Q,or(5x∈Q and 5x occurs before 3x).3x-2\in Q,\qquad 7x\in Q,\qquad \text{or}\quad \bigl(5x\in Q\ \text{and}\ 5x\ \text{occurs before}\ 3x\bigr).3x−2∈Q,7x∈Q,or(5x∈Q and 5x occurs before 3x).

In particular, at least one of 3x−23x-23x−2, 5x5x5x, 7x7x7x occurs in QQQ. These conditions are necessary, not sufficient.

As in the official lemma odd_entry_demand, a word is a true root release if every open in-order pair (a,b)(a,b)(a,b) with odd difference has even second entry: no open pair forces the bit 111 at the root node. An in-order pair (a,b)(a,b)(a,b) is open when 2b−a∉Q2b-a\notin Q2b−a∈/Q and 3b−2a∉Q3b-2a\notin Q3b−2a∈/Q.

The first clause 3x∈Q3x\in Q3x∈Q follows from odd_entry_demand together with the prefix: if 2x2x2x occurred it would have to occur after xxx, so it cannot be the grounded partner required when 3x3x3x is absent. The remaining obligation is a genuine escape from the two official tripling chains based at 111 and at xxx: the in-order pairs (1,x)(1,x)(1,x) and (x,3x)(x,3x)(x,3x) occupy the same node (1,1)(1,1)(1,1) and force opposite values of θ\thetaθ there, so they cannot both be open.

This does not rule out unrestricted extensions of (0,1,x)(0,1,x)(0,1,x), does not claim that escape obligations always discharge finitely or propagate forever, and does not settle Erdős #195.

Formalization Note The prefix hypothesis is Q=0::1::x::TQ=0::1::x::TQ=0::1::x::T for some tail TTT. The true-root-release hypothesis is the same predicate as in Erdos195.odd_entry_demand. Safety is official Safe (treeLt θ).

Preamble
import Mathlib
import Definitions.Def_Erdos195_tree
Formal statement
namespace Erdos195

theorem forced_escape_prefix (θ : ℕ → ℤ → Bool) (Q : List ℤ) (x : ℤ)
    (hx : (3 : ℤ) ≤ x) (hxmod : x % 4 = 3)
    (hS : Safe (treeLt θ) Q)
    (hpref : ∃ T : List ℤ, Q = 0 :: 1 :: x :: T)
    (hrel : ∀ a b : ℤ, a ∈ Q → b ∈ Q → Q.idxOf a < Q.idxOf b → 2 * b - a ∉ Q →
      3 * b - 2 * a ∉ Q → (b - a) % 2 = 1 → b % 2 = 0) :
    (3 * x ∈ Q) ∧
    (3 * x - 2 ∈ Q ∨ 7 * x ∈ Q ∨ (5 * x ∈ Q ∧ Q.idxOf (5 * x) < Q.idxOf (3 * x))) ∧
    (3 * x - 2 ∈ Q ∨ 5 * x ∈ Q ∨ 7 * x ∈ Q) := by sorry

end Erdos195
Source
Erdős Problem 195 (https://www.erdosproblems.com/195); derived from analysis relayed by Ethan Cheung (Nov 17 2026), hand-checked against the official Safe / treeLt / true-root-release 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