gaussian_majority_error
The real-valued function gaussian_majority_error (q : ℕ) (lam : ℝ) : ℝ is defined as the infimum in ℝ over all f : ℝ → Fin q with Measurable f and all g : Fin q → ℝ → Bool satisfying ∀ m : Fin q, Measurable (g m) of ((ProbabilityTheory.gaussianReal 0 ⟨lam ^ 2, sq_nonneg lam⟩).prod (ProbabilityTheory.gaussianReal 0 1) {p : ℝ × ℝ | (g (f p.1) p.2 = true) ≠ (0 < p.1 + p.2)}).toReal.
Statement
noncomputable def gaussian_majority_error (q : ℕ) (lam : ℝ) : ℝ
- Defined in
- arXiv:2610.16830, The Communication Complexity of the Coin Problem; OP-994
- Verified
- 04 Nov 2026
- Axioms
- none listed
- Used by 2
- gaussian_majority_error_le_halfFor any natural number q with 1 ≤ q and any real lam > 0, the error satisfies gaussian_majority_error q lam ≤ 1 / 2.
- gaussian_majority_error_nonnegFor any natural number q and any real lam > 0, the error 0 ≤ gaussian_majority_error q lam.
Read back from the Lean
The declaration defines gaussian_majority_error (q : ℕ) (lam : ℝ) : ℝ as the infimum in ℝ over:
1. all functions f : ℝ → Fin q,
2. proofs that f is measurable,
3. all functions g : Fin q → ℝ → Bool,
4. proofs that for every m : Fin q, g m : ℝ → Bool is measurable,
of the measure (converted via .toReal to a real number) under the product measure of the Gaussian measure on ℝ with mean 0 and variance lam ^ 2 (represented as ⟨lam ^ 2, sq_nonneg lam⟩ : NNReal) and the standard Gaussian measure on ℝ with mean 0 and variance 1, of the set of pairs p = (p.1, p.2) : ℝ × ℝ such that the proposition g (f p.1) p.2 = true is not equal to (i.e., disagrees with) 0 < p.1 + p.2.
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- The infimum of error probability in estimating sign(X+Y) over all measurable one-way encoders with q messages and decoders, where X ~ N(0, lam^2) and Y ~ N(0, 1) are independent. -/ noncomputable def gaussian_majority_error (q : ℕ) (lam : ℝ) : ℝ := ⨅ (f : ℝ → Fin q) (_ : Measurable f) (g : Fin q → ℝ → Bool) (_ : ∀ m, Measurable (g m)), ((ProbabilityTheory.gaussianReal 0 ⟨lam ^ 2, sq_nonneg lam⟩).prod (ProbabilityTheory.gaussianReal 0 1) {p : ℝ × ℝ | (g (f p.1) p.2 = true) ≠ (0 < p.1 + p.2)}).toReal