fourier_entropy_block_bound
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.
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.
uses
Finset.nonempty_iff_ne_empty,Finset.sum_poshave 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
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.
uses
Real.log_le_sub_one_of_pos,Real.log_inv,one_div,mul_le_mul_of_nonneg_left,sq_nonneghave 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]
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.
uses
Finset.sum_le_sum,Finset.sum_sub_distrib,Finset.sum_div,div_self,ne_of_gthave 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]
∑_{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).
uses
Real.log_mul,ne_of_gt,Finset.sum_congr,Finset.sum_add_distrib,Finset.sum_mulhave 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
∑_{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.
uses
Finset.sum_neg_distrib,Finset.sum_congr,one_div,Real.log_invhave 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]
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.
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_righthave 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
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.
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_lefthave 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
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.
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_logbhave 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
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.
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_logbhave 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
∑_{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.
uses
ne_of_gt,Real.logb_mul,Real.logb_pow,Finset.sum_congr,Finset.mul_sum,Finset.sum_add_distrib,Finset.sum_mulhave 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
∑_{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.
uses
mul_le_mul_of_nonneg_left,le_of_ltrw [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
∑_{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.
uses
Finset.sum_le_univ_sum_of_nonneg,norm_nonneg,le_max_righthave 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
∑_{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.
uses
fourier_entropy_block_bound_aux,norm_nonneg,le_max_leftexact 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
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.
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