Finite seed certificate implies an asymptotic separation
ProvedSensitivityCampaign.finite_certificateLet be a total Boolean function and let be any input. Suppose integers satisfy and . For every real with , prove the campaign's asymptotic claim at exponent : for every and every integer , some total Boolean function satisfies and . The conclusion must include arbitrarily large sensitivity. No normalization hypothesis is imposed on or ; establishing the necessary normalization is part of the proof.
import Mathlib import Definitions.Def_SensitivityCampaign open OAI.Paper320
theorem SensitivityCampaign.finite_certificate
{n : ℕ} (f : (Fin n → Bool) → Bool) (x : Fin n → Bool)
(A B : ℕ) (a : ℝ)
(hA : 1 < A) (hB : 1 < B) (ha : 0 ≤ a)
(hs : sensitivity f ≤ A) (hb : B ≤ blockSensitivityAt f x)
(hpow : (A : ℝ) ^ a ≤ (B : ℝ)) :
SensitivityCampaign.AchievesExponent 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 , all natural numbers with and , and every real , if , , and after interpreting as real numbers, then the following holds: 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 . Although is allowed by its quantifier, its hypotheses cannot hold because 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.