AFTD Auto-Formalizing Theoretical Domains

fourier_entropy_block_bound

theoremverified

Let f, P : (Fin n → Bool) → ℂ and let T be a set of frequencies with non-zero Fourier coefficients |f_hat(S)| > 0 such that |f_hat(S)| ≤ 2 * |P_hat(S)| for all S in T. If mu = ∑_{S ∈ T} |f_hat(S)|^2 > 0, then ∑_{S ∈ T} |f_hat(S)|^2 * log_2(1 / |f_hat(S)|^2) ≤ 2 * mu * (1 + log_2(max 1 ||P_hat||_1) + log_2(1 / mu)).

Statement

theorem fourier_entropy_block_bound {n : ℕ} (f : (Fin n → Bool) → ℂ)
    (T : Finset (Finset (Fin n)))
    (P : (Fin n → Bool) → ℂ)
    (hT : ∀ S ∈ T,
      ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖
      ≤ 2 * ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, P x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖)
    (h_pos : ∀ S ∈ T, ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ≠ 0)
    (mu : ℝ)
    (hmu : mu = ∑ S ∈ T, ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2)
    (hmu_pos : 0 < mu) :
    ∑ S ∈ T, ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2 *
      Real.logb 2 (1 / ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2)
    ≤ 2 * mu * (1 + Real.logb 2 (max 1 (spectral_norm_c P)) + Real.logb 2 (1 / mu))
Source
arXiv:2611.06451 Theorem 3.1 proof (eq. 18)
Verified
06 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • spectral_norm_cThe spectral norm ||f_hat||_1 of a function f : (Fin n -> Bool) -> ℂ is defined as the sum over all subsets S of Fin n of the absolute…

Read back from the Lean

For any natural number $n$, any function $f : (\mathrm{Fin}\ n \to \mathrm{Bool}) \to \mathbb{C}$, any collection $T$ of subsets of $\mathrm{Fin}\ n$ (as a Finset (Finset (Fin n))), any function $P : (\mathrm{Fin}\ n \to \mathrm{Bool}) \to \mathbb{C}$, and any real number $\mu$, assume: 1. For every $S \in T$, the Fourier coefficient magnitude $|\widehat{f}(S)| = \left\| \frac{1}{2^n} \sum_{x : \mathrm{Fin}\ n \to \mathrm{Bool}} f(x) \prod_{i \in S} (\text{if } x(i) \text{ then } -1 \text{ else } 1) \right\|$ is at most $2$ times the corresponding Fourier coefficient magnitude of $P$, $|\widehat{P}(S)| = \left\| \frac{1}{2^n} \sum_{x : \mathrm{Fin}\ n \to \mathrm{Bool}} P(x) \prod_{i \in S} (\text{if } x(i) \text{ then } -1 \text{ else } 1) \right\|$; 2. For every $S \in T$, $|\widehat{f}(S)| \neq 0$; 3. $\mu = \sum_{S \in T} |\widehat{f}(S)|^2$; 4. $0 < \mu$. Then the partial Fourier entropy over $T$ satisfies the upper bound: $$\sum_{S \in T} |\widehat{f}(S)|^2 \log_2\left(\frac{1}{|\widehat{f}(S)|^2}\right) \le 2\mu \left(1 + \log_2(\max(1, \mathrm{spectral\_norm\_c}(P))) + \log_2\left(\frac{1}{\mu}\right)\right)$$ where $\log_2$ is Real.logb 2.

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

The proof bounds the Fourier entropy contribution of a block T of frequencies by reducing it to a fundamental inequality on normalized weights: for any u_i > 0 with ∑ u_i^2 = 1, we have ∑ u_i^2 log_2(1 / u_i) ≤ log_2(∑ u_i), proved via the elementary inequality ln(x) ≤ x - 1 applied to (u_i ∑ u_j)⁻¹. Normalizing the Fourier coefficients |f_hat(S)| by √mu produces such a unit vector whose sum is bounded by 2 * ||P_hat||_1 / √mu. Expanding the block entropy in terms of these normalized weights and evaluating log_2(2 * A / √mu) yields the desired upper bound.

  1. The index set T is non-empty and the sum U = ∑_{i ∈ T} u_i is strictly positive.

    If T were empty, the sum of squares ∑_{i ∈ T} u_i^2 would be 0, contradicting the hypothesis that it equals 1. Because T is non-empty and every weight u_i is strictly positive, their sum U is also strictly positive.

    lines 4–7

    uses Finset.nonempty_iff_ne_empty, Finset.sum_pos

      have hne : T.Nonempty := by
        rw [Finset.nonempty_iff_ne_empty]
        intro h; rw [h] at hsum; simp at hsum
      have hU : 0 < ∑ i ∈ T, u i := Finset.sum_pos (fun i hi => hu i hi) hne
  2. For every i ∈ T, u_i^2 - u_i / (∑_{j ∈ T} u_j) ≤ u_i^2 * ln(u_i * ∑_{j ∈ T} u_j).

    Applying the standard inequality ln(x) ≤ x - 1 to x = (u_i * U)⁻¹ yields -ln(u_i * U) ≤ (u_i * U)⁻¹ - 1, which rearranges to 1 - 1 / (u_i * U) ≤ ln(u_i * U). Multiplying both sides by the non-negative quantity u_i^2 and simplifying the left-hand side gives the claimed pointwise bound.

    lines 8–22

    uses Real.log_le_sub_one_of_pos, Real.log_inv, one_div, mul_le_mul_of_nonneg_left, sq_nonneg

      have hterm : ∀ i ∈ T, u i ^ 2 - u i / (∑ j ∈ T, u j) ≤ u i ^ 2 * Real.log (u i * ∑ j ∈ T, u j) := by
        intro i hi
        have hui : 0 < u i := hu i hi
        have hpos : (0:ℝ) < (u i * ∑ j ∈ T, u j)⁻¹ := by positivity
        have h0 : Real.log ((u i * ∑ j ∈ T, u j)⁻¹) ≤ (u i * ∑ j ∈ T, u j)⁻¹ - 1 :=
          Real.log_le_sub_one_of_pos hpos
        rw [Real.log_inv] at h0
        have hlog : 1 - 1 / (u i * ∑ j ∈ T, u j) ≤ Real.log (u i * ∑ j ∈ T, u j) := by
          have h2 : (1:ℝ) / (u i * ∑ j ∈ T, u j) = (u i * ∑ j ∈ T, u j)⁻¹ := one_div _
          linarith [h0, h2]
        have hmul : u i ^ 2 * (1 - 1 / (u i * ∑ j ∈ T, u j)) ≤ u i ^ 2 * Real.log (u i * ∑ j ∈ T, u j) :=
          mul_le_mul_of_nonneg_left hlog (sq_nonneg _)
        have heq : u i ^ 2 * (1 - 1 / (u i * ∑ j ∈ T, u j)) = u i ^ 2 - u i / (∑ j ∈ T, u j) := by
          have h1 := hui; have h2 := hU; field_simp
        linarith [hmul, heq]
  3. The sum ∑_{i ∈ T} u_i^2 * ln(u_i * ∑_{j ∈ T} u_j) is non-negative.

    Summing the pointwise inequality over all i ∈ T gives a lower bound of ∑_{i ∈ T} (u_i^2 - u_i / U). Since ∑ u_i^2 = 1 and (∑ u_i) / U = U / U = 1, this lower bound evaluates to 1 - 1 = 0.

    lines 23–31

    uses Finset.sum_le_sum, Finset.sum_sub_distrib, Finset.sum_div, div_self, ne_of_gt

      have hge : 0 ≤ ∑ i ∈ T, u i ^ 2 * Real.log (u i * ∑ j ∈ T, u j) := by
        have h1 : ∑ i ∈ T, (u i ^ 2 - u i / (∑ j ∈ T, u j)) ≤ ∑ i ∈ T, u i ^ 2 * Real.log (u i * ∑ j ∈ T, u j) :=
          Finset.sum_le_sum hterm
        have h2 : ∑ i ∈ T, (u i ^ 2 - u i / (∑ j ∈ T, u j)) = 0 := by
          rw [Finset.sum_sub_distrib]
          rw [← Finset.sum_div]
          rw [hsum, div_self (ne_of_gt hU)]
          ring
        linarith [h1, h2]
  4. ∑_{i ∈ T} u_i^2 * ln(u_i * ∑_{j ∈ T} u_j) = ∑_{i ∈ T} u_i^2 * ln(u_i) + ln(∑_{j ∈ T} u_j).

    Decomposing ln(u_i * U) as ln(u_i) + ln(U) for each term, the sum splits into ∑ u_i^2 * ln(u_i) + (∑ u_i^2) * ln(U). Since ∑ u_i^2 = 1, the second term simplifies to ln(U).

    lines 32–40

    uses Real.log_mul, ne_of_gt, Finset.sum_congr, Finset.sum_add_distrib, Finset.sum_mul

      have hsplit : ∑ i ∈ T, u i ^ 2 * Real.log (u i * ∑ j ∈ T, u j)
          = ∑ i ∈ T, u i ^ 2 * Real.log (u i) + Real.log (∑ j ∈ T, u j) := by
        have hcongr : ∀ i ∈ T, u i ^ 2 * Real.log (u i * ∑ j ∈ T, u j)
            = u i ^ 2 * Real.log (u i) + u i ^ 2 * Real.log (∑ j ∈ T, u j) := by
          intro i hi
          rw [Real.log_mul (ne_of_gt (hu i hi)) (ne_of_gt hU)]
          ring
        rw [Finset.sum_congr rfl hcongr, Finset.sum_add_distrib, ← Finset.sum_mul, hsum]
        ring
  5. ∑_{i ∈ T} u_i^2 * ln(1 / u_i) ≤ ln(∑_{i ∈ T} u_i).

    Combining non-negativity from Step 3 with the split formula from Step 4 gives ∑ u_i^2 * ln(u_i) ≥ -ln(U). Since ln(1 / u_i) = -ln(u_i), rewriting the left-hand side as -∑ u_i^2 * ln(u_i) immediately proves the inequality.

    lines 41–50

    uses Finset.sum_neg_distrib, Finset.sum_congr, one_div, Real.log_inv

      have hgoal : ∑ i ∈ T, u i ^ 2 * Real.log (u i) ≥ - Real.log (∑ j ∈ T, u j) := by
        linarith [hge, hsplit]
      have hconv : ∑ i ∈ T, u i ^ 2 * Real.log (1 / u i) = - ∑ i ∈ T, u i ^ 2 * Real.log (u i) := by
        rw [← Finset.sum_neg_distrib]
        apply Finset.sum_congr rfl
        intro i hi
        rw [one_div, Real.log_inv]
        ring
      rw [hconv]
      linarith [hgoal]
  6. For normalized positive weights u_i, ∑_{i ∈ T} u_i^2 * log_2(1 / u_i) ≤ log_2(∑_{i ∈ T} u_i).

    The base-2 logarithm is defined by log_2(x) = ln(x) / ln(2). Dividing both sides of the natural log inequality fourier_entropy_block_bound_logsum by ln(2) > 0 and factoring out the constant divisor converts the result directly to base 2.

    lines 55–64

    uses fourier_entropy_block_bound_logsum, Real.log_pos, Real.logb, mul_div_assoc, Finset.sum_congr, Finset.sum_div, div_le_div_iff_of_pos_right

      have h := fourier_entropy_block_bound_logsum T u hu hsum
      have hD : 0 < Real.log 2 := Real.log_pos (by norm_num)
      have hterm : ∀ i ∈ T, u i ^ 2 * Real.logb 2 (1/u i) = (u i^2 * Real.log (1/u i)) / Real.log 2 := by
        intro i hi; rw [Real.logb, mul_div_assoc]
      have hsum_eq : ∑ i ∈ T, u i ^ 2 * Real.logb 2 (1 / u i)
          = (∑ i ∈ T, u i ^ 2 * Real.log (1 / u i)) / Real.log 2 := by
        rw [Finset.sum_congr rfl hterm]
        exact (Finset.sum_div T (fun i => u i ^ 2 * Real.log (1 / u i)) (Real.log 2)).symm
      rw [hsum_eq, Real.logb]
      exact (div_le_div_iff_of_pos_right hD).mpr h
  7. Each a_S > 0, T is non-empty, ∑_{S ∈ T} a_S > 0, and ∑_{S ∈ T} a_S ≤ 2 * A.

    Because a_S ≥ 0 and a_S ≠ 0 on T, each a_S > 0. Since mu = ∑ a_S^2 > 0, T cannot be empty, hence ∑_{S ∈ T} a_S > 0. Summing the hypothesis a_S ≤ 2 * b_S over T gives ∑ a_S ≤ 2 * ∑ b_S ≤ 2 * A.

    lines 74–83

    uses lt_of_le_of_ne, Ne.symm, Finset.nonempty_iff_ne_empty, Finset.sum_pos, Finset.sum_le_sum, Finset.mul_sum, mul_le_mul_of_nonneg_left

      have ha_pos : ∀ S ∈ T, 0 < a S := fun S hS => lt_of_le_of_ne (ha S hS) (Ne.symm (ha0 S hS))
      have hne : T.Nonempty := by
        rw [Finset.nonempty_iff_ne_empty]
        intro h; rw [h] at hmu; simp at hmu; linarith [hmu_pos, hmu]
      have hUpos : 0 < ∑ S ∈ T, a S := Finset.sum_pos (fun S hS => ha_pos S hS) hne
      have hUle : ∑ S ∈ T, a S ≤ 2 * A := by
        have h1 : ∑ S ∈ T, a S ≤ ∑ S ∈ T, 2 * b S := Finset.sum_le_sum hT
        have h2 : ∑ S ∈ T, 2 * b S = 2 * ∑ S ∈ T, b S := by rw [Finset.mul_sum]
        have h3 : 2 * ∑ S ∈ T, b S ≤ 2 * A := by linarith [mul_le_mul_of_nonneg_left hAb (by norm_num : (0:ℝ) ≤ 2)]
        linarith
  8. With u_S = a_S / √mu, we have u_S > 0, ∑_{S ∈ T} u_S^2 = 1, and ∑_{S ∈ T} u_S^2 * log_2(1 / u_S) ≤ log_2(∑_{S ∈ T} u_S).

    Normalizing each a_S by √mu yields positive weights u_S whose squared sum is (∑ a_S^2) / mu = mu / mu = 1. Applying fourier_entropy_block_bound_logsum_logb gives the entropy bound on the normalized weights.

    lines 84–94

    uses Real.sqrt_pos.mpr, Real.sq_sqrt, le_of_lt, div_pos, div_pow, Finset.sum_congr, Finset.sum_div, div_self, ne_of_gt, fourier_entropy_block_bound_logsum_logb

      have hsqrtpos : 0 < Real.sqrt mu := Real.sqrt_pos.mpr hmu_pos
      have hsq_sqrt : Real.sqrt mu ^ 2 = mu := Real.sq_sqrt (le_of_lt hmu_pos)
      set u : ι → ℝ := fun S => a S / Real.sqrt mu with hu_def
      have hu : ∀ S ∈ T, 0 < u S := by
        intro S hS; rw [hu_def]; exact div_pos (ha_pos S hS) hsqrtpos
      have hsumu : ∑ S ∈ T, u S ^ 2 = 1 := by
        have hterm : ∀ S ∈ T, u S ^ 2 = a S ^ 2 / mu := by
          intro S hS; rw [hu_def]; rw [div_pow, hsq_sqrt]
        rw [Finset.sum_congr rfl hterm, ← Finset.sum_div, ← hmu, div_self (ne_of_gt hmu_pos)]
      have hentropy : ∑ S ∈ T, u S ^ 2 * Real.logb 2 (1 / u S) ≤ Real.logb 2 (∑ S ∈ T, u S) :=
        fourier_entropy_block_bound_logsum_logb T u hu hsumu
  9. log_2(∑_{S ∈ T} u_S) ≤ 1 + log_2(A) + (1 / 2) * log_2(1 / mu).

    Since ∑ u_S = (∑ a_S) / √mu ≤ 2 * A / √mu, monotonicity of log_2 gives log_2(∑ u_S) ≤ log_2(2 * A / √mu). Expanding the logarithm into log_2(2) + log_2(A) - log_2(√mu), using log_2(2) = 1 and log_2(√mu) = (1/2) * log_2(mu) = -(1/2) * log_2(1/mu), establishes the bound.

    lines 95–117

    uses Finset.sum_div, Real.logb_pow, Real.logb, div_self, ne_of_gt, Real.log_pos, Real.logb_div, Real.logb_mul, one_div, Real.logb_inv, div_le_div_iff_of_pos_right, Real.logb_le_logb

      have hsumu_val : ∑ S ∈ T, u S = (∑ S ∈ T, a S) / Real.sqrt mu := by
        rw [hu_def]; exact (Finset.sum_div T a (Real.sqrt mu)).symm
      have hsumu_pos : 0 < ∑ S ∈ T, u S := by rw [hsumu_val]; positivity
      have hlogsqrt : Real.logb 2 (Real.sqrt mu) = (1 / 2) * Real.logb 2 mu := by
        have h := Real.logb_pow 2 (Real.sqrt mu) 2
        rw [hsq_sqrt] at h
        push_cast at h
        linarith
      have hone : Real.logb 2 (2:ℝ) = 1 := by
        rw [Real.logb]; rw [div_self (ne_of_gt (Real.log_pos (by norm_num)))]
      have hval : Real.logb 2 (2*A/Real.sqrt mu) = 1 + Real.logb 2 A + (1/2)*Real.logb 2 (1/mu) := by
        have hAne : A ≠ 0 := by linarith [hA1]
        have hdiv := Real.logb_div (b:=2) (x:=2*A) (y:=Real.sqrt mu) (by positivity) (ne_of_gt hsqrtpos)
        have hmul := Real.logb_mul (b:=2) (x:=(2:ℝ)) (y:=A) (by norm_num) hAne
        have h1mu : Real.logb 2 (1/mu) = - Real.logb 2 mu := by rw [one_div, Real.logb_inv]
        rw [hdiv, hmul, hone, h1mu]
        linarith [hlogsqrt]
      have hbound_log : Real.logb 2 (∑ S ∈ T, u S) ≤ 1 + Real.logb 2 A + (1/2)*Real.logb 2 (1/mu) := by
        have hle : ∑ S ∈ T, u S ≤ 2*A/Real.sqrt mu := by
          rw [hsumu_val]; exact (div_le_div_iff_of_pos_right hsqrtpos).mpr hUle
        have hpos2A : 0 < 2*A/Real.sqrt mu := by positivity
        have h := (Real.logb_le_logb (by norm_num : (1:ℝ) < 2) hsumu_pos hpos2A).mpr hle
        rwa [hval] at h
  10. ∑_{S ∈ T} a_S^2 * log_2(1 / a_S^2) = mu * (2 * ∑_{S ∈ T} u_S^2 * log_2(1 / u_S) + log_2(1 / mu)).

    Using a_S^2 = mu * u_S^2, we expand log_2(1 / a_S^2) as log_2(1 / mu) + 2 * log_2(1 / u_S). Multiplying by a_S^2, summing over T, factoring out mu, and using ∑ u_S^2 = 1 gives the algebraic identity.

    lines 118–136

    uses ne_of_gt, Real.logb_mul, Real.logb_pow, Finset.sum_congr, Finset.mul_sum, Finset.sum_add_distrib, Finset.sum_mul

      have hLHS_eq : ∑ S ∈ T, a S ^ 2 * Real.logb 2 (1 / a S ^ 2)
          = mu * (2 * (∑ S ∈ T, u S ^ 2 * Real.logb 2 (1 / u S)) + Real.logb 2 (1 / mu)) := by
        have hterm : ∀ S ∈ T, a S ^ 2 * Real.logb 2 (1 / a S ^ 2)
            = mu * (2 * (u S ^ 2 * Real.logb 2 (1 / u S)) + u S ^ 2 * Real.logb 2 (1 / mu)) := by
          intro S hS
          have huS : u S = a S / Real.sqrt mu := by rw [hu_def]
          have hune : u S ≠ 0 := ne_of_gt (hu S hS)
          have hsq : a S ^ 2 = mu * u S ^ 2 := by rw [huS]; field_simp; rw [hsq_sqrt]
          have hlog : Real.logb 2 (1 / a S ^ 2) = Real.logb 2 (1 / mu) + 2 * Real.logb 2 (1 / u S) := by
            rw [hsq]
            have hm : (1:ℝ) / (mu * u S ^ 2) = (1/mu) * (1/u S ^ 2) := by field_simp
            rw [hm, Real.logb_mul (by positivity) (by positivity)]
            rw [show (1:ℝ)/u S^2 = (1/u S)^2 by ring, Real.logb_pow]
            ring
          rw [hlog, hsq]; ring
        rw [Finset.sum_congr rfl hterm, ← Finset.mul_sum]
        congr 1
        rw [Finset.sum_add_distrib, ← Finset.mul_sum, ← Finset.sum_mul, hsumu]
        ring
  11. ∑_{S ∈ T} a_S^2 * log_2(1 / a_S^2) ≤ 2 * mu * (1 + log_2(A) + log_2(1 / mu)).

    Plugging the bound on the normalized entropy sum into the identity from Step 10 gives an inner expression bounded by 2 * (1 + log_2(A) + (1/2) * log_2(1/mu)) + log_2(1/mu) = 2 * (1 + log_2(A) + log_2(1/mu)). Multiplying by mu > 0 completes the auxiliary lemma.

    lines 137–143

    uses mul_le_mul_of_nonneg_left, le_of_lt

      rw [hLHS_eq]
      have hinner : 2 * (∑ S ∈ T, u S ^ 2 * Real.logb 2 (1 / u S)) + Real.logb 2 (1 / mu)
          ≤ 2 * (1 + Real.logb 2 A + Real.logb 2 (1 / mu)) := by
        linarith [hentropy, hbound_log]
      calc mu * (2 * (∑ S ∈ T, u S ^ 2 * Real.logb 2 (1 / u S)) + Real.logb 2 (1 / mu))
          ≤ mu * (2 * (1 + Real.logb 2 A + Real.logb 2 (1 / mu))) := mul_le_mul_of_nonneg_left hinner (le_of_lt hmu_pos)
        _ = 2 * mu * (1 + Real.logb 2 A + Real.logb 2 (1 / mu)) := by ring
  12. ∑_{S ∈ T} |P_hat(S)| ≤ max 1 ||P_hat||_1.

    Since norms are non-negative, the sum of |P_hat(S)| over the subset T is bounded by the sum over all frequencies Finset (Fin n), which is by definition spectral_norm_c(P) = ||P_hat||_1. This norm is in turn bounded by max 1 ||P_hat||_1.

    lines 159–166

    uses Finset.sum_le_univ_sum_of_nonneg, norm_nonneg, le_max_right

      have hAb : (∑ S ∈ T, ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, P x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖)
          ≤ max 1 (spectral_norm_c P) := by
        have h1 : (∑ S ∈ T, ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, P x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖)
            ≤ ∑ S : Finset (Fin n), ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, P x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ :=
          Finset.sum_le_univ_sum_of_nonneg (fun S => norm_nonneg _)
        have h2 : (∑ S : Finset (Fin n), ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, P x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖) = spectral_norm_c P := rfl
        have h3 : spectral_norm_c P ≤ max 1 (spectral_norm_c P) := le_max_right _ _
        linarith
  13. ∑_{S ∈ T} |f_hat(S)|^2 * log_2(1 / |f_hat(S)|^2) ≤ 2 * mu * (1 + log_2(max 1 ||P_hat||_1) + log_2(1 / mu)).

    Instantiate fourier_entropy_block_bound_aux with a_S = |f_hat(S)|, b_S = |P_hat(S)|, and A = max 1 (spectral_norm_c P). All required conditions hold: coefficients are non-negative, a_S ≤ 2 * b_S, a_S ≠ 0, mu > 0, A ≥ 1, and ∑_{S ∈ T} b_S ≤ A.

    lines 167–171

    uses fourier_entropy_block_bound_aux, norm_nonneg, le_max_left

      exact fourier_entropy_block_bound_aux T
        (fun S => ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖)
        (fun S => ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, P x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖)
        (max 1 (spectral_norm_c P)) mu
        (fun S _ => norm_nonneg _) (fun S _ => norm_nonneg _) hT h_pos hmu hmu_pos (le_max_left _ _) hAb
Finset.nonempty_iff_ne_empty
A finite set is nonempty if and only if it is not the empty set.
Finset.sum_pos
A finite sum of strictly positive elements over a nonempty set is strictly positive.
Real.log_le_sub_one_of_pos
For any x > 0, ln(x) ≤ x - 1.
Real.log_inv
The natural logarithm of the reciprocal is the negative of the logarithm: ln(x⁻¹) = -ln(x).
one_div
Division of 1 by a equals the multiplicative inverse a⁻¹.
mul_le_mul_of_nonneg_left
Multiplication by a non-negative element preserves an inequality.
sq_nonneg
The square of any element in an ordered semiring is non-negative.
Finset.sum_le_sum
A sum of pointwise smaller terms is less than or equal to the sum of the larger terms.
Finset.sum_sub_distrib
The sum of a difference is the difference of the sums.
Finset.sum_div
A common divisor factors out of a finite sum.
div_self
Any non-zero element divided by itself equals 1.
ne_of_gt
If b < a, then a ≠ b.
Real.log_mul
The logarithm of a product of non-zero real numbers is the sum of their logarithms.
Finset.sum_congr
Sums of pointwise equal functions over the same finite set are equal.
Finset.sum_add_distrib
The sum of a pointwise addition distributes into two separate sums.
Finset.sum_mul
A common right-factor can be factored out of a finite sum.
Finset.sum_neg_distrib
Negation distributes across a finite sum.
fourier_entropy_block_bound_logsum
For positive weights u_i summing in square to 1, the natural entropy sum is bounded by ln(∑ u_i).
Real.log_pos
For x > 1, the natural logarithm ln(x) is strictly positive.
Real.logb
Definition of the base-b logarithm: log_b(x) = ln(x) / ln(b).
mul_div_assoc
Associativity of multiplication and division: a * b / c = a * (b / c).
div_le_div_iff_of_pos_right
Division by a strictly positive number preserves an inequality.
lt_of_le_of_ne
If a ≤ b and a ≠ b, then a < b.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
Finset.mul_sum
A common left-factor distributes over a finite sum.
Real.sqrt_pos.mpr
The square root of a strictly positive real number is strictly positive.
Real.sq_sqrt
The square of the square root of a non-negative real number equals the number.
le_of_lt
A strict inequality implies a non-strict inequality: if a < b then a ≤ b.
div_pos
The quotient of two strictly positive numbers is strictly positive.
div_pow
A quotient raised to a power equals the quotient of the powers: (a / b)^n = a^n / b^n.
fourier_entropy_block_bound_logsum_logb
For positive weights u_i summing in square to 1, the base-2 entropy sum is bounded by log_2(∑ u_i).
Real.logb_pow
Power rule for base-b logarithms: log_b(x^k) = k * log_b(x).
Real.logb_div
Logarithm of a quotient: log_b(x / y) = log_b(x) - log_b(y).
Real.logb_mul
Logarithm of a product: log_b(x * y) = log_b(x) + log_b(y).
Real.logb_inv
Base-b logarithm of an inverse: log_b(x⁻¹) = -log_b(x).
Real.logb_le_logb
Strict monotonicity of base-b logarithm for b > 1: log_b(x) ≤ log_b(y) ↔ x ≤ y.
Finset.sum_le_univ_sum_of_nonneg
A sum of non-negative elements over a subset is bounded by the sum over the entire universe.
norm_nonneg
The seminorm of any vector is non-negative.
le_max_right
Any element is less than or equal to the maximum of another element and itself: b ≤ max a b.
fourier_entropy_block_bound_aux
Auxiliary entropy bound for non-negative weights a_S ≤ 2 * b_S with ∑ b_S ≤ A.
le_max_left
Any element is less than or equal to the maximum of itself and another element: a ≤ max a b.

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

theorem fourier_entropy_block_bound_logsum {ι : Type*} (T : Finset ι) (u : ι → ℝ)    (hu : ∀ i ∈ T, 0 < u i) (hsum : ∑ i ∈ T, u i ^ 2 = 1) :    ∑ i ∈ T, u i ^ 2 * Real.log (1 / u i) ≤ Real.log (∑ i ∈ T, u i) := by  have hne : T.Nonempty := by    rw [Finset.nonempty_iff_ne_empty]    intro h; rw [h] at hsum; simp at hsum  have hU : 0 < ∑ i ∈ T, u i := Finset.sum_pos (fun i hi => hu i hi) hne  have hterm : ∀ i ∈ T, u i ^ 2 - u i / (∑ j ∈ T, u j) ≤ u i ^ 2 * Real.log (u i * ∑ j ∈ T, u j) := by    intro i hi    have hui : 0 < u i := hu i hi    have hpos : (0:ℝ) < (u i * ∑ j ∈ T, u j)⁻¹ := by positivity    have h0 : Real.log ((u i * ∑ j ∈ T, u j)⁻¹) ≤ (u i * ∑ j ∈ T, u j)⁻¹ - 1 :=      Real.log_le_sub_one_of_pos hpos    rw [Real.log_inv] at h0    have hlog : 1 - 1 / (u i * ∑ j ∈ T, u j) ≤ Real.log (u i * ∑ j ∈ T, u j) := by      have h2 : (1:ℝ) / (u i * ∑ j ∈ T, u j) = (u i * ∑ j ∈ T, u j)⁻¹ := one_div _      linarith [h0, h2]    have hmul : u i ^ 2 * (1 - 1 / (u i * ∑ j ∈ T, u j)) ≤ u i ^ 2 * Real.log (u i * ∑ j ∈ T, u j) :=      mul_le_mul_of_nonneg_left hlog (sq_nonneg _)    have heq : u i ^ 2 * (1 - 1 / (u i * ∑ j ∈ T, u j)) = u i ^ 2 - u i / (∑ j ∈ T, u j) := by      have h1 := hui; have h2 := hU; field_simp    linarith [hmul, heq]  have hge : 0 ≤ ∑ i ∈ T, u i ^ 2 * Real.log (u i * ∑ j ∈ T, u j) := by    have h1 : ∑ i ∈ T, (u i ^ 2 - u i / (∑ j ∈ T, u j)) ≤ ∑ i ∈ T, u i ^ 2 * Real.log (u i * ∑ j ∈ T, u j) :=      Finset.sum_le_sum hterm    have h2 : ∑ i ∈ T, (u i ^ 2 - u i / (∑ j ∈ T, u j)) = 0 := by      rw [Finset.sum_sub_distrib]      rw [← Finset.sum_div]      rw [hsum, div_self (ne_of_gt hU)]      ring    linarith [h1, h2]  have hsplit : ∑ i ∈ T, u i ^ 2 * Real.log (u i * ∑ j ∈ T, u j)      = ∑ i ∈ T, u i ^ 2 * Real.log (u i) + Real.log (∑ j ∈ T, u j) := by    have hcongr : ∀ i ∈ T, u i ^ 2 * Real.log (u i * ∑ j ∈ T, u j)        = u i ^ 2 * Real.log (u i) + u i ^ 2 * Real.log (∑ j ∈ T, u j) := by      intro i hi      rw [Real.log_mul (ne_of_gt (hu i hi)) (ne_of_gt hU)]      ring    rw [Finset.sum_congr rfl hcongr, Finset.sum_add_distrib, ← Finset.sum_mul, hsum]    ring  have hgoal : ∑ i ∈ T, u i ^ 2 * Real.log (u i) ≥ - Real.log (∑ j ∈ T, u j) := by    linarith [hge, hsplit]  have hconv : ∑ i ∈ T, u i ^ 2 * Real.log (1 / u i) = - ∑ i ∈ T, u i ^ 2 * Real.log (u i) := by    rw [← Finset.sum_neg_distrib]    apply Finset.sum_congr rfl    intro i hi    rw [one_div, Real.log_inv]    ring  rw [hconv]  linarith [hgoal]theorem fourier_entropy_block_bound_logsum_logb {ι : Type*} (T : Finset ι) (u : ι → ℝ)    (hu : ∀ i ∈ T, 0 < u i) (hsum : ∑ i ∈ T, u i ^ 2 = 1) :    ∑ i ∈ T, u i ^ 2 * Real.logb 2 (1 / u i) ≤ Real.logb 2 (∑ i ∈ T, u i) := by  have h := fourier_entropy_block_bound_logsum T u hu hsum  have hD : 0 < Real.log 2 := Real.log_pos (by norm_num)  have hterm : ∀ i ∈ T, u i ^ 2 * Real.logb 2 (1/u i) = (u i^2 * Real.log (1/u i)) / Real.log 2 := by    intro i hi; rw [Real.logb, mul_div_assoc]  have hsum_eq : ∑ i ∈ T, u i ^ 2 * Real.logb 2 (1 / u i)      = (∑ i ∈ T, u i ^ 2 * Real.log (1 / u i)) / Real.log 2 := by    rw [Finset.sum_congr rfl hterm]    exact (Finset.sum_div T (fun i => u i ^ 2 * Real.log (1 / u i)) (Real.log 2)).symm  rw [hsum_eq, Real.logb]  exact (div_le_div_iff_of_pos_right hD).mpr htheorem fourier_entropy_block_bound_aux {ι : Type*} (T : Finset ι) (a b : ι → ℝ) (A mu : ℝ)    (ha : ∀ S ∈ T, 0 ≤ a S) (hb : ∀ S ∈ T, 0 ≤ b S)    (hT : ∀ S ∈ T, a S ≤ 2 * b S)    (ha0 : ∀ S ∈ T, a S ≠ 0)    (hmu : mu = ∑ S ∈ T, a S ^ 2) (hmu_pos : 0 < mu)    (hA1 : 1 ≤ A) (hAb : ∑ S ∈ T, b S ≤ A) :    ∑ S ∈ T, a S ^ 2 * Real.logb 2 (1 / a S ^ 2)      ≤ 2 * mu * (1 + Real.logb 2 A + Real.logb 2 (1 / mu)) := by  have ha_pos : ∀ S ∈ T, 0 < a S := fun S hS => lt_of_le_of_ne (ha S hS) (Ne.symm (ha0 S hS))  have hne : T.Nonempty := by    rw [Finset.nonempty_iff_ne_empty]    intro h; rw [h] at hmu; simp at hmu; linarith [hmu_pos, hmu]  have hUpos : 0 < ∑ S ∈ T, a S := Finset.sum_pos (fun S hS => ha_pos S hS) hne  have hUle : ∑ S ∈ T, a S ≤ 2 * A := by    have h1 : ∑ S ∈ T, a S ≤ ∑ S ∈ T, 2 * b S := Finset.sum_le_sum hT    have h2 : ∑ S ∈ T, 2 * b S = 2 * ∑ S ∈ T, b S := by rw [Finset.mul_sum]    have h3 : 2 * ∑ S ∈ T, b S ≤ 2 * A := by linarith [mul_le_mul_of_nonneg_left hAb (by norm_num : (0:ℝ) ≤ 2)]    linarith  have hsqrtpos : 0 < Real.sqrt mu := Real.sqrt_pos.mpr hmu_pos  have hsq_sqrt : Real.sqrt mu ^ 2 = mu := Real.sq_sqrt (le_of_lt hmu_pos)  set u : ι → ℝ := fun S => a S / Real.sqrt mu with hu_def  have hu : ∀ S ∈ T, 0 < u S := by    intro S hS; rw [hu_def]; exact div_pos (ha_pos S hS) hsqrtpos  have hsumu : ∑ S ∈ T, u S ^ 2 = 1 := by    have hterm : ∀ S ∈ T, u S ^ 2 = a S ^ 2 / mu := by      intro S hS; rw [hu_def]; rw [div_pow, hsq_sqrt]    rw [Finset.sum_congr rfl hterm, ← Finset.sum_div, ← hmu, div_self (ne_of_gt hmu_pos)]  have hentropy : ∑ S ∈ T, u S ^ 2 * Real.logb 2 (1 / u S) ≤ Real.logb 2 (∑ S ∈ T, u S) :=    fourier_entropy_block_bound_logsum_logb T u hu hsumu  have hsumu_val : ∑ S ∈ T, u S = (∑ S ∈ T, a S) / Real.sqrt mu := by    rw [hu_def]; exact (Finset.sum_div T a (Real.sqrt mu)).symm  have hsumu_pos : 0 < ∑ S ∈ T, u S := by rw [hsumu_val]; positivity  have hlogsqrt : Real.logb 2 (Real.sqrt mu) = (1 / 2) * Real.logb 2 mu := by    have h := Real.logb_pow 2 (Real.sqrt mu) 2    rw [hsq_sqrt] at h    push_cast at h    linarith  have hone : Real.logb 2 (2:ℝ) = 1 := by    rw [Real.logb]; rw [div_self (ne_of_gt (Real.log_pos (by norm_num)))]  have hval : Real.logb 2 (2*A/Real.sqrt mu) = 1 + Real.logb 2 A + (1/2)*Real.logb 2 (1/mu) := by    have hAne : A ≠ 0 := by linarith [hA1]    have hdiv := Real.logb_div (b:=2) (x:=2*A) (y:=Real.sqrt mu) (by positivity) (ne_of_gt hsqrtpos)    have hmul := Real.logb_mul (b:=2) (x:=(2:ℝ)) (y:=A) (by norm_num) hAne    have h1mu : Real.logb 2 (1/mu) = - Real.logb 2 mu := by rw [one_div, Real.logb_inv]    rw [hdiv, hmul, hone, h1mu]    linarith [hlogsqrt]  have hbound_log : Real.logb 2 (∑ S ∈ T, u S) ≤ 1 + Real.logb 2 A + (1/2)*Real.logb 2 (1/mu) := by    have hle : ∑ S ∈ T, u S ≤ 2*A/Real.sqrt mu := by      rw [hsumu_val]; exact (div_le_div_iff_of_pos_right hsqrtpos).mpr hUle    have hpos2A : 0 < 2*A/Real.sqrt mu := by positivity    have h := (Real.logb_le_logb (by norm_num : (1:ℝ) < 2) hsumu_pos hpos2A).mpr hle    rwa [hval] at h  have hLHS_eq : ∑ S ∈ T, a S ^ 2 * Real.logb 2 (1 / a S ^ 2)      = mu * (2 * (∑ S ∈ T, u S ^ 2 * Real.logb 2 (1 / u S)) + Real.logb 2 (1 / mu)) := by    have hterm : ∀ S ∈ T, a S ^ 2 * Real.logb 2 (1 / a S ^ 2)        = mu * (2 * (u S ^ 2 * Real.logb 2 (1 / u S)) + u S ^ 2 * Real.logb 2 (1 / mu)) := by      intro S hS      have huS : u S = a S / Real.sqrt mu := by rw [hu_def]      have hune : u S ≠ 0 := ne_of_gt (hu S hS)      have hsq : a S ^ 2 = mu * u S ^ 2 := by rw [huS]; field_simp; rw [hsq_sqrt]      have hlog : Real.logb 2 (1 / a S ^ 2) = Real.logb 2 (1 / mu) + 2 * Real.logb 2 (1 / u S) := by        rw [hsq]        have hm : (1:ℝ) / (mu * u S ^ 2) = (1/mu) * (1/u S ^ 2) := by field_simp        rw [hm, Real.logb_mul (by positivity) (by positivity)]        rw [show (1:ℝ)/u S^2 = (1/u S)^2 by ring, Real.logb_pow]        ring      rw [hlog, hsq]; ring    rw [Finset.sum_congr rfl hterm, ← Finset.mul_sum]    congr 1    rw [Finset.sum_add_distrib, ← Finset.mul_sum, ← Finset.sum_mul, hsumu]    ring  rw [hLHS_eq]  have hinner : 2 * (∑ S ∈ T, u S ^ 2 * Real.logb 2 (1 / u S)) + Real.logb 2 (1 / mu)      ≤ 2 * (1 + Real.logb 2 A + Real.logb 2 (1 / mu)) := by    linarith [hentropy, hbound_log]  calc mu * (2 * (∑ S ∈ T, u S ^ 2 * Real.logb 2 (1 / u S)) + Real.logb 2 (1 / mu))      ≤ mu * (2 * (1 + Real.logb 2 A + Real.logb 2 (1 / mu))) := mul_le_mul_of_nonneg_left hinner (le_of_lt hmu_pos)    _ = 2 * mu * (1 + Real.logb 2 A + Real.logb 2 (1 / mu)) := by ring/-- Entropy contribution of a block of frequencies bounded via concavity of log. -/theorem fourier_entropy_block_bound {n : ℕ} (f : (Fin n → Bool) → ℂ)    (T : Finset (Finset (Fin n)))    (P : (Fin n → Bool) → ℂ)    (hT : ∀ S ∈ T,      ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖      ≤ 2 * ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, P x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖)    (h_pos : ∀ S ∈ T, ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ≠ 0)    (mu : ℝ)    (hmu : mu = ∑ S ∈ T, ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2)    (hmu_pos : 0 < mu) :    ∑ S ∈ T, ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2 *      Real.logb 2 (1 / ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ ^ 2)    ≤ 2 * mu * (1 + Real.logb 2 (max 1 (spectral_norm_c P)) + Real.logb 2 (1 / mu)) := by  have hAb : (∑ S ∈ T, ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, P x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖)      ≤ max 1 (spectral_norm_c P) := by    have h1 : (∑ S ∈ T, ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, P x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖)        ≤ ∑ S : Finset (Fin n), ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, P x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖ :=      Finset.sum_le_univ_sum_of_nonneg (fun S => norm_nonneg _)    have h2 : (∑ S : Finset (Fin n), ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, P x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖) = spectral_norm_c P := rfl    have h3 : spectral_norm_c P ≤ max 1 (spectral_norm_c P) := le_max_right _ _    linarith  exact fourier_entropy_block_bound_aux T    (fun S => ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, f x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖)    (fun S => ‖(1 / (2 : ℂ) ^ n) * ∑ x : Fin n → Bool, P x * (∏ i ∈ S, if x i then (-1 : ℂ) else 1)‖)    (max 1 (spectral_norm_c P)) mu    (fun S _ => norm_nonneg _) (fun S _ => norm_nonneg _) hT h_pos hmu hmu_pos (le_max_left _ _) hAb
See it in the graphDiscuss this resultChallenge it