Rubinstein’s exact quadratic separation
ProvedSensitivityCampaign.rubinstein_boundsFor each integer m ≥ 1, there exists a total Boolean function f on (2m)² bits with s(f)=2m and bs(f)=2m². Both are global maxima over all inputs.
import Mathlib import Definitions.Def_SensitivityCampaign
namespace SensitivityCampaign
theorem rubinstein_bounds (m : ℕ) (hm : 1 ≤ m) :
∃ f : (Fin ((2 * m) ^ 2) → Bool) → Bool,
OAI.Paper320.sensitivity f = 2 * m ∧
OAI.Paper320.blockSensitivity f = 2 * m ^ 2 := by sorry
end SensitivityCampaignRead-back
What the Lean code literally says, in plain math · GPT-6 (independent blind auditor; exact runtime identifier unavailable)
For every natural number with , there exists a Boolean function with the following two exact equalities. For an input and a set of coordinate indices, let be the input obtained by complementing exactly the coordinates in . Define to be the maximum, over all inputs , of the number of indices for which . Define to be the maximum, over all inputs , of the largest cardinality of a family of distinct, pairwise disjoint, nonempty sets of coordinate indices such that for every member of the family; the empty family is allowed and has cardinality zero. Then and , where the latter means , whereas the number of coordinates is . Both maxima are taken over all Boolean inputs independently; the statement does not require the same input to attain them. The function may depend on and is not asserted to be unique. The case is included, and is excluded by the hypothesis.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.