Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Two-state binary-prefix transports under dyadic order patterns always contain a monotone four-term progression

Proved
Erdos195.NonlinearStateResearch.two_state_transport_has_fourAP_of_patterns

by xwh · Oct 23, 2026 · Mathlib 0df444a (Lean v4.33.1)

arithmetic-progressionscombinatoricserdos-problems

Let p:ℕ≃ℕ be a permutation and write pos(m)=p⁻¹(m). Assume both of the following order conditions:

pos⁡(0)<pos⁡(2k)<pos⁡(2⋅2k)<pos⁡(m⋅2k)for every k≥0, m≥4,\operatorname{pos}(0)<\operatorname{pos}(2^k)<\operatorname{pos}(2\cdot2^k)<\operatorname{pos}(m\cdot2^k) \quad\text{for every }k\ge0,\ m\ge4,pos(0)<pos(2k)<pos(2⋅2k)<pos(m⋅2k)for every k≥0, m≥4,

and

pos⁡(3⋅2k)<pos⁡(2⋅2k)<pos⁡((2n+1)⋅2k)<pos⁡(2n⋅2k)for every k≥0, n≥2.\operatorname{pos}(3\cdot2^k)<\operatorname{pos}(2\cdot2^k) <\operatorname{pos}((2n+1)\cdot2^k)<\operatorname{pos}(2n\cdot2^k) \quad\text{for every }k\ge0,\ n\ge2.pos(3⋅2k)<pos(2⋅2k)<pos((2n+1)⋅2k)<pos(2n⋅2k)for every k≥0, n≥2.

Let the state set consist of two Boolean values. Choose arbitrary integer coefficients a_s, arbitrary transitions δ₀,δ₁ between these two states, and an arbitrary initial state s. Define the binary-prefix value map by the exact terminating recursion

Gs(0)=0,Gs(2n)=2Gδ0(s)(n),Gs(2n+1)=2Gδ1(s)(n)+as.G_s(0)=0,\qquad G_s(2n)=2G_{\delta_0(s)}(n),\qquad G_s(2n+1)=2G_{\delta_1(s)}(n)+a_s.Gs​(0)=0,Gs​(2n)=2Gδ0​(s)​(n),Gs​(2n+1)=2Gδ1​(s)​(n)+as​.

If f:ℕ≃ℤ satisfies f(i)=G_s(p(i)) for every i, then f contains a monotone four-term arithmetic progression in the original canonical sense. No oddness, sign, magnitude, transition, or reachability hypotheses are imposed.

The actual Ho permutation is a separately checked simultaneous instance of the two order conditions. This excludes a genuine nonlinear two-state construction family beyond global position-only coefficients. It makes no assertion about three or more states, general nonlinear transports, or the unresolved original Erdős195 existence problem.

Preamble
import Mathlib
import Definitions.Def_Erdos195_defs
import Definitions.Def_Erdos195_TwoStateBinary_Model
Formal statement
namespace Erdos195.NonlinearStateResearch

theorem two_state_transport_has_fourAP_of_patterns
    (p : ℕ ≃ ℕ) (a : Bool → ℤ) (δ₀ δ₁ : Bool → Bool) (s : Bool)
    (f : ℕ ≃ ℤ)
    (hval : ∀ i, f i = stateValue a δ₀ δ₁ s (p i))
    (hTail : ∀ k m : ℕ, 4 ≤ m →
      p.symm (2^k*0) < p.symm (2^k*1) ∧
      p.symm (2^k*1) < p.symm (2^k*2) ∧
      p.symm (2^k*2) < p.symm (2^k*m))
    (hPattern : ∀ k n : ℕ, 2 ≤ n →
      p.symm (2^k*3) < p.symm (2^k*2) ∧
      p.symm (2^k*2) < p.symm (2^k*(2*n+1)) ∧
      p.symm (2^k*(2*n+1)) < p.symm (2^k*(2*n))) : HasMonotoneAP f 4 := by sorry

end Erdos195.NonlinearStateResearch
Source
Independent two-state transport obstruction reconstructed in this research branch. The common-successor case uses the accepted original triangular-pattern theorem1f121ed8-0503-43b5-aefa-7fd7f04746ad. The actual Ho implementation from arXiv:2609.12780v1 is only a checked application; its first four entries, even-order self-similarity E6 and paired-odd guard E11 establish the displayed patterns. Neither these new helpers nor this obstruction is attributed to Ho's paper. No claim of global literature novelty or guaranteed citation is made.

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