AFTD Auto-Formalizing Theoretical Domains

gaussian_majority_error

def

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

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