AFTD Auto-Formalizing Theoretical Domains

fourier_cross_level_one_le_sqrt_variance_mul

theoremverified

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

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.

  1. 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).

    lines 5–10

    uses Finset.sum_mul_sq_le_sq_mul_sq

      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 _ _ _
  2. 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).

    lines 11–24

    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_nonneg

      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 _
  3. 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.

    lines 25–33

    uses Finset.sum_nonneg, sq_nonneg, mul_le_mul

      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
  4. 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)).

    lines 34–38

    uses Real.le_sqrt_of_sq_le, le_refl, Real.sqrt_le_sqrt

      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
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

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

/-- 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
See it in the graphDiscuss this resultChallenge it