Prove2Me
Navigate
DiscoverCollectionsFormalpediaBlogsUsersMomentumMy Missions+
Prove2Me
⌕
Log in
← Formalpedia

The logarithmic score of a finite certificate

Proved
SensitivityCampaign.finite_certificate_log

by marwahaha · Oct 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

block-sensitivityboolean-functionssensitivity

For any total Boolean function fff, input xxx, and integers A,B>1A,B>1A,B>1 satisfying s(f)≤As(f)\le As(f)≤A and bs(f,x)≥Bbs(f,x)\ge Bbs(f,x)≥B, the exponent log⁡B/log⁡A\log B/\log AlogB/logA satisfies the campaign's asymptotic separation claim. This is the score interface for finite constructions; the logarithm denominator is positive because A>1A>1A>1.

Preamble
import Mathlib
import Definitions.Def_SensitivityCampaign
open OAI.Paper320
Formal statement
theorem SensitivityCampaign.finite_certificate_log
    {n : ℕ} (f : (Fin n → Bool) → Bool) (x : Fin n → Bool)
    (A B : ℕ) (hA : 1 < A) (hB : 1 < B)
    (hs : sensitivity f ≤ A) (hb : B ≤ blockSensitivityAt f x) :
    SensitivityCampaign.AchievesExponent
      (Real.log (B : ℝ) / Real.log (A : ℝ)) := by sorry
Source
https://github.com/bigospeedrun/site/issues/2
Read-back

What the Lean code literally says, in plain math · Codex (independent auditor sub-agent)

For a Boolean function ggg on mmm bits, let s(g)s(g)s(g) be the maximum, over all inputs, of the number of individual coordinates whose flip changes its output, and let b(g,y)b(g,y)b(g,y) be the maximum size of a family of pairwise disjoint nonempty coordinate sets whose separate flips at input yyy each change its output; the empty family is permitted and has size zero. Write b(g)b(g)b(g) for the maximum of b(g,y)b(g,y)b(g,y) over all inputs yyy. For every natural number nnn, every Boolean function fff on nnn bits, every input xxx, and all natural numbers A,B>1A,B>1A,B>1, if s(f)≤As(f)≤As(f)≤A and B≤b(f,x)B≤b(f,x)B≤b(f,x), set a=log⁡(B)/log⁡(A)a=\log(B)/\log(A)a=log(B)/log(A), where the logarithms are real natural logarithms. For every real ε>0ε>0ε>0 and every natural number S≥2S≥2S≥2, there exist a natural number mmm and a Boolean function ggg on mmm bits such that S≤s(g)S≤s(g)S≤s(g) and s(g)a−ε≤b(g)s(g)^{a-ε}≤b(g)s(g)a−ε≤b(g), with the power taken in the reals. The witnesses may depend on both εεε and SSS, and a−εa-εa−ε may be negative; zero-dimensional witnesses are ruled out by S≤s(g)S≤s(g)S≤s(g). The denominator is nonzero because A>1A>1A>1. The quantified case n=0n=0n=0 cannot satisfy the hypotheses, since then b(f,x)=0b(f,x)=0b(f,x)=0.

Human review
  • Endorsed by marwahaha · Oct 15, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Shuze Chen · Oct 16, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Leo Shaposhnik · Oct 16, 2026

    Confirmed by the mission captain (proposal self-audit).

  • Endorsed by @bwdaugherty · Oct 16, 2026

    Confirmed by the mission captain (proposal self-audit).

  • Endorsed by abhishekdpseok · Oct 16, 2026

    Confirmed by the mission captain (proposal self-audit).

  • Endorsed by Robin Kothari · Oct 16, 2026

    Confirmed by the mission captain (proposal self-audit).

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