discrete_level_one_to_three_sharp_constant_of_lt_three
The 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 Cauchy-Schwarz.
Statement
theorem discrete_level_one_to_three_sharp_constant_of_lt_three (n : ℕ) (hn : 1 ≤ n) (hn3 : n < 3)
(f g : BooleanAnalysis.BooleanFunc n) (hf : Monotone f) (hg : Monotone g)
(hw : 0 < fourier_cross_level 1 f g) :
- (fourier_cross_level 1 f g / (3 * Real.log (4 / 3))) *
Real.log (Real.sqrt (fourier_variance f * fourier_variance g) / fourier_cross_level 1 f g) ≤
fourier_cross_level 3 f g- Source
- step towards discrete_level_one_to_three_sharp_constant
- Verified
- 12 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 8
- 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…
- fourier_cross_level_eq_zero_of_card_ltFor any two functions $f, g : \{0,1\}^n \to \mathbb{R}$ and any integer $k > n$, the $k$-th cross Fourier level $W_k[f,g]$ equals zero.
- fourier_cross_level_one_le_sqrt_variance_mulCauchy-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)).
- LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder. - BooleanAnalysis.BoolCubeThe Boolean hypercube of dimension $n$ is $\{0,1\}^n$, represented as the function type $\mathrm{Fin}\,n \to \mathrm{Bool}$.
- BooleanAnalysis.BooleanFuncA Boolean function of arity $n$ is a function $f : \{0,1\}^n \to \bbr$.
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
The proof, explained
The inequality is proved by showing that its right-hand side equals zero while its left-hand side is non-positive. For n < 3, the Boolean cube has no subsets of size 3, so the degree-3 Fourier cross level W₃[f, g] vanishes identically. On the left-hand side, the Cauchy-Schwarz inequality implies that W₁[f, g] ≤ √(Var(f) * Var(g)), making the ratio inside the logarithm at least 1 and the logarithm non-negative. Multiplied by a strictly positive coefficient and then negated, the left-hand side is at most 0 ≤ W₃[f, g].
The right-hand side fourier_cross_level 3 f g is zero, reducing the goal to showing that the left-hand side is non-positive.
Because the dimension n < 3, the hypercube contains no subsets of size 3, which means the level-3 Fourier cross level vanishes by fourier_cross_level_eq_zero_of_card_lt. Substituting 0 for the right-hand side reduces the required inequality to proving that the left-hand side is at most 0.
uses
fourier_cross_level_eq_zero_of_card_lthave hW3 : fourier_cross_level 3 f g = 0 := fourier_cross_level_eq_zero_of_card_lt hn3 f g rw [hW3]
The logarithmic factor ln(√(Var(f) * Var(g)) / W₁[f, g]) is non-negative.
By the Cauchy-Schwarz inequality for level-1 Fourier coefficients (fourier_cross_level_one_le_sqrt_variance_mul), W₁[f, g] ≤ √(Var(f) * Var(g)). Since W₁[f, g] > 0 by assumption, dividing through via le_div_iff₀ shows that the ratio inside the logarithm is at least 1. Since ln(x) ≥ 0 for x ≥ 1 (Real.log_nonneg), the logarithmic factor is non-negative.
uses
fourier_cross_level_one_le_sqrt_variance_mul,le_div_iff₀,Real.log_nonneghave hA : 0 < fourier_cross_level 1 f g := hw have hCS := fourier_cross_level_one_le_sqrt_variance_mul f g have hratio : 1 ≤ Real.sqrt (fourier_variance f * fourier_variance g) / fourier_cross_level 1 f g := by rw [le_div_iff₀ hA] simpa using hCS have hlog : 0 ≤ Real.log (Real.sqrt (fourier_variance f * fourier_variance g) / fourier_cross_level 1 f g) := Real.log_nonneg hratio
The prefactor W₁[f, g] / (3 ln(4/3)) is strictly positive.
Since 4/3 > 1, its natural logarithm is strictly positive (Real.log_pos), so the denominator 3 ln(4/3) is strictly positive. Because the numerator W₁[f, g] is also strictly positive by hypothesis, their quotient is strictly positive by div_pos.
uses
Real.log_pos,div_poshave hden : 0 < 3 * Real.log (4 / 3 : ℝ) := by have h : (1 : ℝ) < 4 / 3 := by norm_num have := Real.log_pos h positivity have hcoef : 0 < fourier_cross_level 1 f g / (3 * Real.log (4 / 3 : ℝ)) := div_pos hA hden
The left-hand side is non-positive, completing the proof.
The product of the positive coefficient and the non-negative logarithm is non-negative by mul_nonneg (using le_of_lt). Negating this product yields a non-positive real number via neg_nonpos.mpr. Rewriting with neg_mul establishes that the left-hand side is at most 0, which matches the right-hand side.
uses
mul_nonneg,le_of_lt,neg_mul,neg_nonpos.mprhave hprod : 0 ≤ fourier_cross_level 1 f g / (3 * Real.log (4 / 3 : ℝ)) * Real.log (Real.sqrt (fourier_variance f * fourier_variance g) / fourier_cross_level 1 f g) := mul_nonneg (le_of_lt hcoef) hlog simpa [neg_mul] using neg_nonpos.mpr hprod
fourier_cross_level_eq_zero_of_card_lt- If n < k, the level-k Fourier cross level of any two functions on n variables is zero.
fourier_cross_level_one_le_sqrt_variance_mul- The level-1 Fourier cross level of f and g is bounded above by the geometric mean of their Fourier variances (Cauchy-Schwarz).
le_div_iff₀- For a strictly positive denominator c > 0, a ≤ b / c holds if and only if a * c ≤ b.
Real.log_nonneg- For any real number x ≥ 1, the natural logarithm ln(x) is non-negative.
Real.log_pos- For any real number x > 1, the natural logarithm ln(x) is strictly positive.
div_pos- The quotient of two strictly positive numbers is strictly positive.
mul_nonneg- The product of two non-negative numbers is non-negative.
le_of_lt- A strict inequality a < b implies the weak inequality a ≤ b.
neg_mul- Multiplication distributes over negation: -a * b = -(a * b).
neg_nonpos.mpr- If a real number x satisfies 0 ≤ x, then -x ≤ 0.
- The theorem assumes that f and g are monotone, but this assumption is never used in the proof; only n < 3 and 0 < fourier_cross_level 1 f g are needed.
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.
/-- Sharp level 1 to 3 inequality for dimensions n < 3 (arXiv:2611.08289 Question 6.1). -/theorem discrete_level_one_to_three_sharp_constant_of_lt_three (n : ℕ) (hn : 1 ≤ n) (hn3 : n < 3) (f g : BooleanAnalysis.BooleanFunc n) (hf : Monotone f) (hg : Monotone g) (hw : 0 < fourier_cross_level 1 f g) : - (fourier_cross_level 1 f g / (3 * Real.log (4 / 3))) * Real.log (Real.sqrt (fourier_variance f * fourier_variance g) / fourier_cross_level 1 f g) ≤ fourier_cross_level 3 f g := by have hW3 : fourier_cross_level 3 f g = 0 := fourier_cross_level_eq_zero_of_card_lt hn3 f g rw [hW3] have hA : 0 < fourier_cross_level 1 f g := hw have hCS := fourier_cross_level_one_le_sqrt_variance_mul f g have hratio : 1 ≤ Real.sqrt (fourier_variance f * fourier_variance g) / fourier_cross_level 1 f g := by rw [le_div_iff₀ hA] simpa using hCS have hlog : 0 ≤ Real.log (Real.sqrt (fourier_variance f * fourier_variance g) / fourier_cross_level 1 f g) := Real.log_nonneg hratio have hden : 0 < 3 * Real.log (4 / 3 : ℝ) := by have h : (1 : ℝ) < 4 / 3 := by norm_num have := Real.log_pos h positivity have hcoef : 0 < fourier_cross_level 1 f g / (3 * Real.log (4 / 3 : ℝ)) := div_pos hA hden have hprod : 0 ≤ fourier_cross_level 1 f g / (3 * Real.log (4 / 3 : ℝ)) * Real.log (Real.sqrt (fourier_variance f * fourier_variance g) / fourier_cross_level 1 f g) := mul_nonneg (le_of_lt hcoef) hlog simpa [neg_mul] using neg_nonpos.mpr hprod