fourier_cross_level_one_le_sqrt_variance_mul
Cauchy-Schwarz inequality for the first cross Fourier level: for any two functions f, g : {0,1}^n → ℝ, W_1[f, g] ≤ sqrt(Var(f) * Var(g)).
Statement
theorem fourier_cross_level_one_le_sqrt_variance_mul {n : ℕ}
(f g : BooleanAnalysis.BooleanFunc n) :
fourier_cross_level 1 f g ≤ Real.sqrt (fourier_variance f * fourier_variance g)- Source
- step towards discrete_level_one_to_three_sharp_constant
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 4
- fourier_cross_levelThe $k$-th cross Fourier level $W_k[f,g]$ of two real-valued functions $f, g : \{0,1\}^n \to \mathbb{R}$ is the sum…
- fourier_varianceThe Fourier variance $\mathrm{Var}(f)$ of a function $f : \{0,1\}^n \to \mathbb{R}$ is the sum of the squares of its non-empty…
- BooleanAnalysis.BooleanFuncA Boolean function of arity $n$ is a function $f : \{0,1\}^n \to \bbr$.
- BooleanAnalysis.fourierCoeffThe Fourier--Walsh coefficient of $f$ at frequency $S$ is…
- Used by 1
- discrete_level_one_to_three_sharp_constant_of_lt_threeThe sharp level 1 to 3 inequality holds for all n < 3 (i.e. n = 1, 2) because W_3[f,g] = 0 and the left-hand side is nonpositive by…
The proof, explained
The theorem bounds the level-1 cross Fourier weight W_1[f, g] = ∑_{|S|=1} f̂(S) ĝ(S) by sqrt(Var(f) * Var(g)). The argument applies the Cauchy-Schwarz inequality for sums to bound (W_1[f, g])^2 by the product of the individual level-1 weights, (∑_{|S|=1} f̂(S)^2) * (∑_{|S|=1} ĝ(S)^2). Since singletons are nonempty and squared Fourier coefficients are nonnegative, each level-1 weight is bounded above by the total variance Var(h) = ∑_{S ≠ ∅} ĥ(S)^2. Multiplying these bounds and taking square roots yields the desired inequality.
The square of the level-1 cross Fourier weight is bounded by the product of the level-1 Fourier weights: W_1[f, g]^2 ≤ (∑_{|S|=1} f̂(S)^2) * (∑_{|S|=1} ĝ(S)^2)
Let L be the collection of all subsets of {0, ..., n-1} of cardinality 1. Expanding the definition of the level-1 cross Fourier weight W_1[f, g] = ∑_{S ∈ L} f̂(S) ĝ(S), the Cauchy-Schwarz inequality for finite sums (Finset.sum_mul_sq_le_sq_mul_sq) gives W_1[f, g]^2 ≤ (∑_{S ∈ L} f̂(S)^2) * (∑_{S ∈ L} ĝ(S)^2).
uses
Finset.sum_mul_sq_le_sq_mul_sqset L := Finset.powersetCard 1 (Finset.univ : Finset (Fin n)) with hL have hCS : (fourier_cross_level 1 f g)^2 ≤ (∑ S ∈ L, BooleanAnalysis.fourierCoeff f S ^ 2) * (∑ S ∈ L, BooleanAnalysis.fourierCoeff g S ^ 2) := by rw [hL] rw [fourier_cross_level] exact Finset.sum_mul_sq_le_sq_mul_sq _ _ _
For any Boolean function h, its level-1 Fourier weight is bounded above by its variance: ∑_{|S|=1} ĥ(S)^2 ≤ Var(h)
By definition, the variance Var(h) sums ĥ(S)^2 over all nonempty subsets S. Every set S ∈ L has cardinality 1 (Finset.mem_powersetCard), so S cannot be empty (Finset.nonempty_iff_ne_empty, Finset.mem_filter, Finset.mem_univ, true_and), proving L is a subset of all nonempty sets. Since squared Fourier coefficients are always nonnegative (sq_nonneg), the sum over L is bounded by the sum over all nonempty sets (Finset.sum_le_sum_of_subset_of_nonneg).
uses
Finset.sum_le_sum_of_subset_of_nonneg,Finset.mem_powersetCard,Finset.mem_filter,Finset.mem_univ,true_and,Finset.nonempty_iff_ne_empty,sq_nonneghave hkey : ∀ (h : BooleanAnalysis.BooleanFunc n), (∑ S ∈ L, BooleanAnalysis.fourierCoeff h S ^ 2) ≤ fourier_variance h := by intro h rw [fourier_variance] refine Finset.sum_le_sum_of_subset_of_nonneg ?_ ?_ · intro S hS rw [hL, Finset.mem_powersetCard] at hS simp only [Finset.mem_filter, Finset.mem_univ, true_and] rw [Finset.nonempty_iff_ne_empty] intro hh rw [hh] at hS simp at hS · intro S _ _ exact sq_nonneg _
The product of the level-1 weights of f and g is at most the product of their variances: (∑_{|S|=1} f̂(S)^2) * (∑_{|S|=1} ĝ(S)^2) ≤ Var(f) * Var(g)
Applying the previous bound to f and g gives ∑_{S ∈ L} f̂(S)^2 ≤ Var(f) and ∑_{S ∈ L} ĝ(S)^2 ≤ Var(g). Since sums of squares are nonnegative (Finset.sum_nonneg, sq_nonneg), both the level-1 weight of g and the variance of f are nonnegative. Multiplying these inequalities preserves the relation by mul_le_mul.
uses
Finset.sum_nonneg,sq_nonneg,mul_le_mulhave hA := hkey f have hB := hkey g have hBn : (0:ℝ) ≤ ∑ S ∈ L, BooleanAnalysis.fourierCoeff g S ^ 2 := Finset.sum_nonneg (fun S _ => sq_nonneg _) have hvf : (0:ℝ) ≤ fourier_variance f := by rw [fourier_variance]; exact Finset.sum_nonneg (fun S _ => sq_nonneg _) have hAB : (∑ S ∈ L, BooleanAnalysis.fourierCoeff f S ^ 2) * (∑ S ∈ L, BooleanAnalysis.fourierCoeff g S ^ 2) ≤ fourier_variance f * fourier_variance g := mul_le_mul hA hB hBn hvf
Taking square roots yields W_1[f, g] ≤ sqrt(Var(f) * Var(g))
For any real number x, reflexivity x^2 ≤ x^2 (le_refl) implies x ≤ sqrt(x^2) by Real.le_sqrt_of_sq_le. Applying the monotonicity of the real square root (Real.sqrt_le_sqrt) to the Cauchy-Schwarz bound and the variance product bound completes the chain: W_1[f, g] ≤ sqrt(W_1[f, g]^2) ≤ sqrt((∑_{S ∈ L} f̂(S)^2) * (∑_{S ∈ L} ĝ(S)^2)) ≤ sqrt(Var(f) * Var(g)).
uses
Real.le_sqrt_of_sq_le,le_refl,Real.sqrt_le_sqrtcalc fourier_cross_level 1 f g ≤ Real.sqrt ((fourier_cross_level 1 f g)^2) := Real.le_sqrt_of_sq_le (le_refl _) _ ≤ Real.sqrt ((∑ S ∈ L, BooleanAnalysis.fourierCoeff f S ^ 2) * (∑ S ∈ L, BooleanAnalysis.fourierCoeff g S ^ 2)) := Real.sqrt_le_sqrt hCS _ ≤ Real.sqrt (fourier_variance f * fourier_variance g) := Real.sqrt_le_sqrt hAB
Finset.sum_mul_sq_le_sq_mul_sq- Cauchy-Schwarz inequality for finite sums: (∑ i ∈ s, f i * g i)^2 ≤ (∑ i ∈ s, f i^2) * (∑ i ∈ s, g i^2)
Finset.sum_le_sum_of_subset_of_nonneg- If s ⊆ t and f i ≥ 0 for all i ∈ t \ s, then ∑ i ∈ s, f i ≤ ∑ i ∈ t, f i
Finset.mem_powersetCard- A subset s belongs to the size-n powerset of t if and only if s ⊆ t and |s| = n
Finset.mem_filter- An element belongs to the filtered set {x ∈ s | p x} if and only if x ∈ s and p x holds
Finset.mem_univ- Every element of a finite type belongs to Finset.univ
true_and- The proposition (True ∧ p) is equivalent to p
Finset.nonempty_iff_ne_empty- A finite set is nonempty if and only if it is not equal to the empty set
sq_nonneg- The square of any real number is nonnegative: 0 ≤ a^2
Finset.sum_nonneg- A finite sum of nonnegative elements is nonnegative
mul_le_mul- If a ≤ b, c ≤ d, with c ≥ 0 and b ≥ 0, then a * c ≤ b * d
Real.le_sqrt_of_sq_le- For real numbers, if x^2 ≤ y, then x ≤ √y
le_refl- Reflexivity of inequality: a ≤ a
Real.sqrt_le_sqrt- The real square root function is monotone: if x ≤ y, then √x ≤ √y
- In Step 2, the containment that every size-1 subset is nonempty is proved formally by showing that assuming S = ∅ contradicts |S| = 1, a detail that informal presentations treat as immediate.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
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.
/-- Cauchy-Schwarz inequality bounding cross level 1 Fourier weight by square root of variance product. -/theorem fourier_cross_level_one_le_sqrt_variance_mul {n : ℕ} (f g : BooleanAnalysis.BooleanFunc n) : fourier_cross_level 1 f g ≤ Real.sqrt (fourier_variance f * fourier_variance g) := by set L := Finset.powersetCard 1 (Finset.univ : Finset (Fin n)) with hL have hCS : (fourier_cross_level 1 f g)^2 ≤ (∑ S ∈ L, BooleanAnalysis.fourierCoeff f S ^ 2) * (∑ S ∈ L, BooleanAnalysis.fourierCoeff g S ^ 2) := by rw [hL] rw [fourier_cross_level] exact Finset.sum_mul_sq_le_sq_mul_sq _ _ _ have hkey : ∀ (h : BooleanAnalysis.BooleanFunc n), (∑ S ∈ L, BooleanAnalysis.fourierCoeff h S ^ 2) ≤ fourier_variance h := by intro h rw [fourier_variance] refine Finset.sum_le_sum_of_subset_of_nonneg ?_ ?_ · intro S hS rw [hL, Finset.mem_powersetCard] at hS simp only [Finset.mem_filter, Finset.mem_univ, true_and] rw [Finset.nonempty_iff_ne_empty] intro hh rw [hh] at hS simp at hS · intro S _ _ exact sq_nonneg _ have hA := hkey f have hB := hkey g have hBn : (0:ℝ) ≤ ∑ S ∈ L, BooleanAnalysis.fourierCoeff g S ^ 2 := Finset.sum_nonneg (fun S _ => sq_nonneg _) have hvf : (0:ℝ) ≤ fourier_variance f := by rw [fourier_variance]; exact Finset.sum_nonneg (fun S _ => sq_nonneg _) have hAB : (∑ S ∈ L, BooleanAnalysis.fourierCoeff f S ^ 2) * (∑ S ∈ L, BooleanAnalysis.fourierCoeff g S ^ 2) ≤ fourier_variance f * fourier_variance g := mul_le_mul hA hB hBn hvf calc fourier_cross_level 1 f g ≤ Real.sqrt ((fourier_cross_level 1 f g)^2) := Real.le_sqrt_of_sq_le (le_refl _) _ ≤ Real.sqrt ((∑ S ∈ L, BooleanAnalysis.fourierCoeff f S ^ 2) * (∑ S ∈ L, BooleanAnalysis.fourierCoeff g S ^ 2)) := Real.sqrt_le_sqrt hCS _ ≤ Real.sqrt (fourier_variance f * fourier_variance g) := Real.sqrt_le_sqrt hAB