AFTD Auto-Formalizing Theoretical Domains

gaussian_majority_error_nonneg

theoremverified

For any natural number q and any real lam > 0, the error 0 ≤ gaussian_majority_error q lam.

Statement

theorem gaussian_majority_error_nonneg (q : ℕ) (lam : ℝ) (hlam : 0 < lam) :
    0 ≤ gaussian_majority_error q lam
Source
arXiv:2610.16830, target: gaussian_coin_majority_worst_variance_zeta_crossover
Verified
04 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 1
  • gaussian_majority_errorThe real-valued function gaussian_majority_error (q : ℕ) (lam : ℝ) : ℝ is defined as the infimum in ℝ over all f : ℝ → Fin q with…

Read back from the Lean

For any natural number q and any real number lam such that 0 < lam, the Gaussian majority error gaussian_majority_error q lam is greater than or equal to 0.

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 Gaussian majority error is defined as the infimum of the error probabilities over all measurable encoding and decoding strategies. To show that this error is at least 0, the proof repeatedly applies Real.le_iInf to pass the lower bound 0 under the infima, reducing the goal to showing that each individual error probability is nonnegative. This holds immediately because probability measures take values in the extended nonnegative reals, whose conversion to real numbers is always nonnegative.

  1. The goal is expressed as a lower bound of 0 on a fourfold infimum of protocol error probabilities

    Unfolding the definition of gaussian_majority_error expresses it explicitly as an infimum over encoding strategies f : ℝ → Fin q, proofs of measurability of f, decoding strategies g : Fin q → ℝ → Bool, and proofs of measurability of g, of the probability of error under the product Gaussian measure converted to a real number.

    line 4

      unfold gaussian_majority_error
  2. It suffices to show that the error probability for any fixed pair of measurable encoding and decoding strategies is at least 0

    A lower bound a ≤ ⨅ i, f i follows if a ≤ f i holds for every index i and a ≤ 0 holds (Real.le_iInf). Here a = 0, so the side condition 0 ≤ 0 is trivial (le_rfl). Applying this four times peels off the infima over f, the measurability of f, g, and the measurability of each slice of g, leaving only the evaluation of the error probability itself.

    lines 5–8

    uses Real.le_iInf, le_rfl

      refine Real.le_iInf (fun _ => ?_) le_rfl
      refine Real.le_iInf (fun _ => ?_) le_rfl
      refine Real.le_iInf (fun _ => ?_) le_rfl
      refine Real.le_iInf (fun _ => ?_) le_rfl
  3. The error probability is nonnegative

    The error probability is obtained by taking the real part (.toReal) of a measure value in ENNReal (the extended nonnegative reals). The lemma ENNReal.toReal_nonneg establishes that every such value is at least 0, finishing the proof.

    line 9

    uses ENNReal.toReal_nonneg

      exact ENNReal.toReal_nonneg
Real.le_iInf
a real number a is a lower bound for an infimum ⨅ i, f i if it bounds every term f i from below and satisfies a ≤ 0
le_rfl
every element in a preorder is less than or equal to itself
ENNReal.toReal_nonneg
the real value of an extended nonnegative real number is always nonnegative

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

/-- The Gaussian majority communication error is always nonnegative. -/theorem gaussian_majority_error_nonneg (q : ℕ) (lam : ℝ) (hlam : 0 < lam) :    0 ≤ gaussian_majority_error q lam := by  unfold gaussian_majority_error  refine Real.le_iInf (fun _ => ?_) le_rfl  refine Real.le_iInf (fun _ => ?_) le_rfl  refine Real.le_iInf (fun _ => ?_) le_rfl  refine Real.le_iInf (fun _ => ?_) le_rfl  exact ENNReal.toReal_nonneg
See it in the graphDiscuss this resultChallenge it