AFTD Auto-Formalizing Theoretical Domains

discrete_level_one_to_three_sharp_constant_of_lt_three

theoremverified

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 LinearOrder is a TotalPreorder.
  • 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 than LinearOrder — 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].

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

    lines 8–10

    uses fourier_cross_level_eq_zero_of_card_lt

      have hW3 : fourier_cross_level 3 f g = 0 :=
        fourier_cross_level_eq_zero_of_card_lt hn3 f g
      rw [hW3]
  2. 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.

    lines 11–20

    uses fourier_cross_level_one_le_sqrt_variance_mul, le_div_iff₀, Real.log_nonneg

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

    lines 21–26

    uses Real.log_pos, div_pos

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

    lines 27–32

    uses mul_nonneg, le_of_lt, neg_mul, neg_nonpos.mpr

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

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

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