KKL.friedgut_junta
theoremverifiedformalizationimported Lean
Friedgut's junta theorem. Let $f : \{0,1\}^n \to \{-1,1\}$ be a $\pm 1$-valued Boolean function with total influence $I[f]$, and let $\varepsilon > 0$. Then there exist a coordinate set $J \subseteq [n]$ and a Boolean function $g : \{0,1\}^n \to \bbr$ such that \[ \abs{J} \;\le\; \frac{4n\,I[f]}{\varepsilon}, \] $g$ is a $J$-junta, and $\E\big[(f(x) - g(x))^2\big] \le \varepsilon$ under the uniform measure on the cube.
Statement
set_option autoImplicit true in set_option relaxedAutoImplicit true in set_option maxHeartbeats 800000 in open scoped BigOperators in open BooleanAnalysis in variable {n : ℕ} in open Classical in theorem KKL.friedgut_junta (f : BooleanFunc n) (hf : isPmOne f) (ε : ℝ) (hε : 0 < ε) : ∃ (J : Finset (Fin n)) (g : BooleanFunc n), (J.card : ℝ) ≤ 4 * n * totalInfluence f / ε ∧ IsJunta g J ∧ l2DistSq f g ≤ ε
- Formalizes
- Friedgut's junta theorem, as formalized in TCSlib (`KKL.friedgut_junta`)
- Lean proof
- By Mina, Owen McGinty, Hydroxyi (from the file's git history), from github.com/Shilun-Allan-Li/tcslib at
c8a02591b1e5(Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.KKL.friedgut_junta← KKL.friedgut_junta (TCSlib/BooleanAnalysis/KKL.lean:659): verbatim
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 18
- BooleanAnalysis.totalInfluence_eq_sum_sq_degTotal influence via Fourier coefficients. For every Boolean function $f\colon\{0,1\}^n\to\bbr$, the total influence of $f$ is recovered…
- BooleanAnalysis.uniformWeightThe uniform probability measure on $\{0,1\}^n$ assigns weight $2^{-n}$ to each point.
- BooleanAnalysis.expectThe expectation of $f$ under the uniform measure: \[ \E[f] \;=\; 2^{-n}\sum_{x\in\{0,1\}^n} f(x). \]
- KKL.lowDegreePartThe low-degree part of $f$ at level $k$ keeps only the Fourier coefficients of degree at most $k$:…
- BooleanAnalysis.chiS_singletonValue of a singleton Walsh character. Fix a dimension $n$, a coordinate $i \in [n]$, and a point $x$ of the Boolean hypercube $\{0,1\}^n$.…
- BooleanAnalysis.BoolCubeThe Boolean hypercube of dimension $n$ is $\{0,1\}^n$, represented as the function type $\mathrm{Fin}\,n \to \mathrm{Bool}$.
- KKL.influentialCoordsThe set of $\tau$-influential coordinates of $f$ is the finite set…
- KKL.influential_coords_cardFew influential coordinates. Let $f : \{0,1\}^n \to \bbr$ be a Boolean function and let $\tau > 0$. The number of $\tau$-influential…
- BooleanAnalysis.isPmOne$f$ is $\pm 1$-valued if $f(x)\in\{-1,1\}$ for all $x$.
- BooleanAnalysis.totalInfluence$I[f] = \sum_{i=1}^n \mathrm{Inf}_i[f]$.
- KKL.lowDegreePart_depends_on_influentialLow-degree part is close to a junta on the influential coordinates. Let $f:\{0,1\}^n\to\bbr$ be a Boolean function, let $k$ be a natural…
- KKL.IsJuntaA function $g$ is a $J$-junta if it depends only on the coordinates in $J$: whenever $x$ and $y$ agree on every $i \in J$, we have…
- KKL.l2DistSqThe squared $L^2$ distance between two Boolean functions is $\E\big[(f(x) - g(x))^2\big]$ under the uniform measure on the cube.
- BooleanAnalysis.BooleanFuncA Boolean function of arity $n$ is a function $f : \{0,1\}^n \to \bbr$.
- KKL.lowDegree_approxLow-degree approximation error bound. Let $f\colon\{0,1\}^n\to\bbr$ be a Boolean function and let $k\ge 1$ be an integer. Writing…
- BooleanAnalysis.flipBit_flipBitBit-flip is an involution. For a point $x$ in the Boolean hypercube $\{0,1\}^n$ and a coordinate $i$, flipping the $i$-th coordinate of…
- BooleanAnalysis.fourierCoeffThe Fourier--Walsh coefficient of $f$ at frequency $S$ is…
- BooleanAnalysis.influenceThe influence of coordinate $i$ on $f$ measures how often flipping bit $i$ changes the output:…
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
set_option autoImplicit true inset_option relaxedAutoImplicit true inset_option maxHeartbeats 800000 inopen scoped BigOperators inopen BooleanAnalysis invariable {n : ℕ} inopen Classical in/-- **Friedgut's Junta Theorem** (1998): Any Boolean function `f : {-1,1}^n -> {-1,1}` is `epsilon`-close (in L2) to a function that depends on at most `ceil(4 * n * I[f] / epsilon)` coordinates. Proof strategy: 1. Set `k = ceil(4 * I[f] / epsilon)` and `tau = epsilon / (4 * n)`. 2. The low-degree part `f_{<=k}` satisfies `E[(f - f_{<=k})^2] <= I[f]/k <= epsilon/4`. 3. There are at most `I[f] / tau = 4 * n * I[f] / epsilon` coordinates with `Inf_i >= tau`. 4. Restricting to those coordinates loses at most `n * tau = epsilon/4` in L2 from `f_{<=k}`. 5. By the triangle inequality: `l2DistSq f g <= 2 * (epsilon/4 + epsilon/4) = epsilon`. **Source:** [OD14, Ch. 10]. **Deviation:** The stated junta-size bound is a deliberately weaker finite-dimensional form than the standard asymptotic theorem. -/theorem KKL.friedgut_junta (f : BooleanFunc n) (hf : isPmOne f) (ε : ℝ) (hε : 0 < ε) : ∃ (J : Finset (Fin n)) (g : BooleanFunc n), (J.card : ℝ) ≤ 4 * n * totalInfluence f / ε ∧ IsJunta g J ∧ l2DistSq f g ≤ ε := by -- Step A: Choose the degree truncation level have hk : 0 < ⌈totalInfluence f / (ε / 2)⌉₊ ∨ totalInfluence f ≤ 0 := by by_cases hI : totalInfluence f ≤ 0 · right; exact hI · left push_neg at hI apply Nat.ceil_pos.mpr apply div_pos hI linarith -- Step B: Low-degree approximation have hlow : ∀ (k : ℕ), 0 < k → l2DistSq f (lowDegreePart f k) ≤ totalInfluence f / k := by intro k hk exact lowDegree_approx f k hk -- Step C: Junta approximation of lowDegreePart -- The lowDegreePart depends on coordinates appearing in its Fourier support. -- We approximate it by a junta on influential coordinates. have hjunta : ∀ (k : ℕ) (τ : ℝ), 0 < τ → ∃ (J : Finset (Fin n)) (g : BooleanFunc n), (J.card : ℝ) ≤ totalInfluence f / τ ∧ IsJunta g J ∧ l2DistSq (lowDegreePart f k) g ≤ (n : ℝ) * τ := by intro k τ hτ obtain ⟨g, hg_junta, hg_err⟩ := lowDegreePart_depends_on_influential f k τ hτ exact ⟨influentialCoords f τ, g, influential_coords_card f τ hτ, hg_junta, hg_err⟩ -- Step D: Triangle inequality for L2 and parameter optimization -- Triangle inequality: l2DistSq f g ≤ 2*(l2DistSq f h + l2DistSq h g) -- (follows from (a-c)^2 ≤ 2*(a-b)^2 + 2*(b-c)^2 pointwise) have htri : ∀ (p q r : BooleanFunc n), l2DistSq p r ≤ 2 * l2DistSq p q + 2 * l2DistSq q r := by intro p q r simp only [l2DistSq, expect, uniformWeight] have hw : (0 : ℝ) ≤ 2⁻¹ ^ n := by positivity calc 2⁻¹ ^ n * ∑ x : BoolCube n, (p x - r x) ^ 2 ≤ 2⁻¹ ^ n * (2 * ∑ x : BoolCube n, (p x - q x) ^ 2 + 2 * ∑ x : BoolCube n, (q x - r x) ^ 2) := by apply mul_le_mul_of_nonneg_left _ hw have hrw : 2 * ∑ x : BoolCube n, (p x - q x) ^ 2 + 2 * ∑ x : BoolCube n, (q x - r x) ^ 2 = ∑ x : BoolCube n, (2 * (p x - q x) ^ 2 + 2 * (q x - r x) ^ 2) := by simp [Finset.sum_add_distrib, Finset.mul_sum] rw [hrw] apply Finset.sum_le_sum; intro x _ nlinarith [sq_nonneg (p x - q x - (q x - r x))] _ = 2 * (2⁻¹ ^ n * ∑ x, (p x - q x) ^ 2) + 2 * (2⁻¹ ^ n * ∑ x, (q x - r x) ^ 2) := by ring -- Handle the I[f] = 0 case first by_cases hI : totalInfluence f ≤ 0 · -- I[f] = 0 (since totalInfluence is a sum of nonneg terms) have hI0 : totalInfluence f = 0 := le_antisymm hI (by rw [totalInfluence_eq_sum_sq_deg] apply Finset.sum_nonneg; intro S _; positivity) -- Sub-case: n = 0 by_cases hn : n = 0 · -- BoolCube 0 is a singleton; f is trivially constant refine ⟨∅, f, ?_, ?_, ?_⟩ · simp [hn] · intro x y _ -- Fin 0 → Bool has a unique element (empty domain) subst hn exact congrArg f (Subsingleton.elim x y) · simp only [l2DistSq] have hzero : (fun x : BoolCube n => (f x - f x) ^ 2) = fun _ => (0 : ℝ) := by ext x; ring rw [hzero] simp [expect, uniformWeight, Finset.sum_const_zero] linarith · -- n > 0, I = 0: use k = 1 and τ = ε/(2*n) have hn' : 0 < n := Nat.pos_of_ne_zero hn set τ₀ := ε / (2 * (↑n : ℝ)) with hτ₀_def have hτ₀ : 0 < τ₀ := by positivity have hτ₀n : (↑n : ℝ) * τ₀ = ε / 2 := by have hn_pos : (0 : ℝ) < ↑n := Nat.cast_pos.mpr hn' simp only [hτ₀_def] field_simp [hn_pos.ne', hε.ne'] obtain ⟨J, g, hJcard, hJjunta, hJerr⟩ := hjunta 1 τ₀ hτ₀ refine ⟨J, g, ?_, hJjunta, ?_⟩ · -- |J| ≤ I/τ₀ = 0 ≤ 4*n*0/ε calc (J.card : ℝ) ≤ totalInfluence f / τ₀ := hJcard _ = 0 := by rw [hI0]; simp _ ≤ 4 * ↑n * totalInfluence f / ε := by rw [hI0]; simp · -- l2DistSq f g ≤ ε -- hlow 1: l2DistSq f (lowDeg 1) ≤ I/1 = 0 -- hJerr: l2DistSq (lowDeg 1) g ≤ n * τ₀ = ε/2 -- triangle: l2DistSq f g ≤ 2*(0 + ε/2) = ε have hlow1 := hlow 1 (by norm_num) have hlow_zero : l2DistSq f (lowDegreePart f 1) ≤ 0 := by calc l2DistSq f (lowDegreePart f 1) ≤ totalInfluence f / ↑(1 : ℕ) := hlow1 _ = 0 := by simp [hI0] have hjerr_half : l2DistSq (lowDegreePart f 1) g ≤ ε / 2 := by calc l2DistSq (lowDegreePart f 1) g ≤ ↑n * τ₀ := hJerr _ = ε / 2 := hτ₀n have hd_nn : 0 ≤ l2DistSq f (lowDegreePart f 1) := by simp only [l2DistSq, expect, uniformWeight] apply mul_nonneg (by positivity) apply Finset.sum_nonneg; intro x _; positivity calc l2DistSq f g ≤ 2 * l2DistSq f (lowDegreePart f 1) + 2 * l2DistSq (lowDegreePart f 1) g := htri f (lowDegreePart f 1) g _ ≤ 2 * 0 + 2 * (ε / 2) := by linarith _ = ε := by ring · -- I[f] > 0 push_neg at hI -- Derive n > 0 from I[f] > 0 have hn : 0 < n := by by_contra h0; push_neg at h0 have h_n0 : n = 0 := Nat.le_zero.mp h0 subst h_n0 simp [totalInfluence] at hI -- Choose parameters: τ = ε/(4*n), k = ⌈4*I/ε⌉₊ set τ := ε / (4 * ↑n) with hτ_def have hτ : 0 < τ := by positivity have hτn : (↑n : ℝ) * τ = ε / 4 := by have hn_pos : (0 : ℝ) < ↑n := Nat.cast_pos.mpr hn simp only [hτ_def] field_simp [hn_pos.ne', hε.ne'] set k := ⌈4 * totalInfluence f / ε⌉₊ with hk_def have hk_pos : 0 < k := Nat.ceil_pos.mpr (by positivity) -- Get junta from hjunta have hlow_k := hlow k hk_pos obtain ⟨J, g, hJcard, hJjunta, hJerr⟩ := hjunta k τ hτ refine ⟨J, g, ?_, hJjunta, ?_⟩ -- Junta size bound: |J| ≤ I/τ = 4*n*I/ε · calc (J.card : ℝ) ≤ totalInfluence f / τ := hJcard _ = 4 * ↑n * totalInfluence f / ε := by have hn_pos : (0 : ℝ) < ↑n := Nat.cast_pos.mpr hn simp only [hτ_def] field_simp [hn_pos.ne', hε.ne'] -- L2 error bound: l2DistSq f g ≤ ε · -- Low-degree error: I/k ≤ ε/4 have hlow_bound : l2DistSq f (lowDegreePart f k) ≤ ε / 4 := by apply le_trans hlow_k rw [div_le_div_iff₀ (Nat.cast_pos.mpr hk_pos) (by norm_num : (0:ℝ) < 4)] -- Goal: totalInfluence f * 4 ≤ ε * ↑k have hle : 4 * totalInfluence f / ε ≤ (k : ℝ) := Nat.le_ceil _ have h := (div_le_iff₀ hε).mp hle linarith -- Junta error: n*τ = ε/4 have hjunta_bound : l2DistSq (lowDegreePart f k) g ≤ ε / 4 := by calc l2DistSq (lowDegreePart f k) g ≤ (↑n) * τ := hJerr _ = ε / 4 := hτn -- Triangle inequality gives total error ≤ 2*(ε/4 + ε/4) = ε calc l2DistSq f g ≤ 2 * l2DistSq f (lowDegreePart f k) + 2 * l2DistSq (lowDegreePart f k) g := htri f (lowDegreePart f k) g _ ≤ 2 * (ε / 4) + 2 * (ε / 4) := by linarith _ = ε := by ring