Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Two dyadic order patterns obstruct signed-binary transport to a 4AP-free integer permutation

Proved
Erdos195.SignedDigitResearch.signed_binary_pattern_obstruction

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

arithmetic-progressionscombinatoricserdos-problems

Let p be a permutation of the natural numbers. Suppose that for every k≥0 the values 3·2^k,2·2^k,5·2^k,4·2^k occur in that order under p, and the values 1·2^k,2·2^k,15·2^k,8·2^k also occur in that order. For any fixed choice of signs on binary place values, every bijection f from the natural numbers onto the integers satisfying f(i)=signedValue(ε,p(i)) contains a monotone four-term arithmetic progression. The signed value is the finite binary digit sum with coefficients +2^j or −2^j according to ε(j), defined by the exact terminating binary recursion. This is a construction-family obstruction; the original Erdős195 existence question remains open.

Preamble
import Mathlib
import Definitions.Def_Erdos195_defs
import Definitions.Def_Erdos195_SignedBinary_Model
Formal statement
namespace Erdos195.SignedDigitResearch

theorem signed_binary_pattern_obstruction (p : ℕ ≃ ℕ) (ε : ℕ → Bool) (f : ℕ ≃ ℤ)
    (hval : ∀ i, f i = signedValue ε (p i))
    (hA : ∀ k, p.symm (2^k*3) < p.symm (2^k*2) ∧
      p.symm (2^k*2) < p.symm (2^k*5) ∧ p.symm (2^k*5) < p.symm (2^k*4))
    (hB : ∀ k, p.symm (2^k*1) < p.symm (2^k*2) ∧
      p.symm (2^k*2) < p.symm (2^k*15) ∧ p.symm (2^k*15) < p.symm (2^k*8)) :
    HasMonotoneAP f 4 := by sorry

end Erdos195.SignedDigitResearch
Source
Independent signed-binary transport obstruction developed in this research branch. The actual Ho permutation from arXiv:2609.12780v1 is a separately kernel-checked application: it satisfies both patterns, and even-order self-similarity propagates them to every dyadic scale. Neither this obstruction nor self-similarity is attributed to the paper. Exact actual Ho closure provenance: accepted submission ba0ba110-74af-4501-8488-3247e332dec2, MIT-licensed upstream boonsuan/4ap.

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