gaussian_majority_error_nonneg
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.
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.
unfold gaussian_majority_errorIt 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.
uses
Real.le_iInf,le_rflrefine 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
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.
uses
ENNReal.toReal_nonnegexact 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
- In Lean's definition of the infimum on ℝ, the infimum of an empty family defaults to 0. Consequently, Real.le_iInf requires an extra hypothesis a ≤ 0 when bounding an infimum from below by a; since the lower bound sought here is a = 0, this side condition is discharged immediately by reflexivity (le_rfl).
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.
/-- 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