The logarithmic score of a finite certificate
ProvedSensitivityCampaign.finite_certificate_logFor any total Boolean function , input , and integers satisfying and , the exponent satisfies the campaign's asymptotic separation claim. This is the score interface for finite constructions; the logarithm denominator is positive because .
import Mathlib import Definitions.Def_SensitivityCampaign open OAI.Paper320
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 sorryRead-back
What the Lean code literally says, in plain math · Codex (independent auditor sub-agent)
For a Boolean function on bits, let be the maximum, over all inputs, of the number of individual coordinates whose flip changes its output, and let be the maximum size of a family of pairwise disjoint nonempty coordinate sets whose separate flips at input each change its output; the empty family is permitted and has size zero. Write for the maximum of over all inputs . For every natural number , every Boolean function on bits, every input , and all natural numbers , if and , set , where the logarithms are real natural logarithms. For every real and every natural number , there exist a natural number and a Boolean function on bits such that and , with the power taken in the reals. The witnesses may depend on both and , and may be negative; zero-dimensional witnesses are ruled out by . The denominator is nonzero because . The quantified case cannot satisfy the hypotheses, since then .
Confirmed by the moderator at approval.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.