Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

A finite profile cycle constructs Boolean seeds at every repetition

Proved
SensitivityProfileCycle.finite_seeds

by dmilosch · Oct 21, 2026 · Mathlib 0df444a (Lean v4.33.1)

block-sensitivityfinite-certificatessensitivitytournaments

Let ccc be a finite recursive-profile cycle certificate, with tournament size KKK, positive period ppp, and return factor RRR. There exists a natural number C>1C>1C>1, independent of the repetition count, such that for every natural number mmm there is a total Boolean function fmf_mfm​ on a finite cube satisfying

s(fm)≤CRm,bs⁡(fm,0)≥(Kp)m.s(f_m)\le C R^m,\qquad \operatorname{bs}(f_m,0)\ge (K^p)^m.s(fm​)≤CRm,bs(fm​,0)≥(Kp)m.

The dimension may depend on mmm. The zero input is the all-false vector. No assumption that the certificate crosses any particular separation exponent is needed. This theorem turns finite graph and integer-profile checks into genuine Boolean functions and is reusable for other numerical targets.

Preamble
import Definitions.Def_SensitivityCampaign
import Definitions.Def_SensitivityProfileCycle
Formal statement
theorem SensitivityProfileCycle.finite_seeds
    (c : SensitivityProfileCycle.Certificate) :
    ∃ C : ℕ, 1 < C ∧ ∀ m : ℕ,
      ∃ (n : ℕ) (f : (Fin n → Bool) → Bool),
        OAI.Paper320.sensitivity f ≤ C * c.radius ^ m ∧
        (c.vertices ^ c.period) ^ m ≤
          OAI.Paper320.blockSensitivityAt f (fun _ => false) := by sorry
Source
Original variable-cycle generalization of the recursive bounds in accepted Prove2Me submission a9d25c46-43bd-4fb1-826b-0ed075b8cf0a, https://prove2.me/theorems/46659a00-722d-4dc9-b28e-ef02d6a0c9c2, namespaces SensitivityNQ and SensitivitySourceCombinedPeriodic, especially profile_step_bounds and stage_blocks. Source authors: yousofy with Codex; retains the attributed OpenAI/math, Robin Kothari with Codex, and earlier community foundations. Mission motivation: https://github.com/bigospeedrun/site/issues/2. The source does not prove that this generalization attains 2.15.

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