Proof of Theorem 6, p. 25 — Σ_{|S|=1} f̂(S)² = ‖ℓ‖₂² = ⟨f, ℓ⟩ ≤ ‖f‖_∞‖ℓ‖₁ ≤ ‖ℓ‖₁
ProvedOptInapprox.LevelOne.level_one_le_l1boolean-functionsfourier-analysisp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1parseval
Let and let be its linear part. Then
Here , , and , all under the uniform measure on the cube.
This chain is the first step of the proof of Theorem 6: it reduces the level-one weight of a bounded function to the norm of its linear part, a weighted sum of independent random signs.
Preamble
import Mathlib import Definitions.Def_OptInapprox_LevelOne_Cube
Formal statement
namespace OptInapprox.LevelOne
theorem level_one_le_l1 {n : ℕ} (f : (Fin n → Bool) → ℝ) (hf : ∀ x, |f x| ≤ 1) :
levelOneWeight f = l2Norm (linPart f) ^ 2 ∧
l2Norm (linPart f) ^ 2 = OptInapprox.MaxCut.cubeE (fun x => f x * linPart f x) ∧
OptInapprox.MaxCut.cubeE (fun x => f x * linPart f x) ≤ supNorm f * l1Norm (linPart f) ∧
supNorm f * l1Norm (linPart f) ≤ l1Norm (linPart f) := by sorry
end OptInapprox.LevelOne
Source
Khot, Kindler, Mossel & O'Donnell, Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs?, SIAM J. Comput. 37(1), 2007 (authors' version of February 7, 2007), p. 25, §10.2, Proof of Theorem 6 (first display)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.