AFTD Auto-Formalizing Theoretical Domains

gaussian_majority_error_le_half

theoremverified

For any natural number q with 1 ≤ q and any real lam > 0, the error satisfies gaussian_majority_error q lam ≤ 1 / 2.

Statement

theorem gaussian_majority_error_le_half (q : ℕ) (hq : 1 ≤ q) (lam : ℝ) (hlam : 0 < lam) :
    gaussian_majority_error q lam ≤ 1 / 2
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 every natural number $q$ such that $1 \le q$, and every real number $\lambda$ such that $0 < \lambda$, the Gaussian majority error gaussian_majority_error q lam is less than or equal to $1/2$.

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

To bound the Gaussian majority communication error by 1/2, we test the infimum against the trivial communication protocol where Alice always transmits message 0 and Bob always outputs false. The error event for this protocol is the open half-plane where the sum of Alice's and Bob's Gaussian inputs is strictly positive. Since the product of two centered Gaussian measures is symmetric under reflection through the origin, this half-plane and its disjoint reflection each have the same measure, which implies its measure cannot exceed 1/2.

  1. The infimum of a family of non-negative reals is non-negative.

    We split into cases on whether the indexing type is empty or nonempty. If empty, the infimum is non-negative by definition (simp). If nonempty, every element is non-negative, so its infimum is bounded below by 0 by le_ciInf.

    lines 3–5

    uses isEmpty_or_nonempty, le_ciInf

      cases isEmpty_or_nonempty ι
      · simp
      · exact le_ciInf h
  2. It suffices to bound the error of the trivial protocol where Alice always sends 0 and Bob always outputs false.

    We unfold gaussian_majority_error, which is defined as an infimum over all measurable encoding strategies f and decoding strategies g. Because the infimum is bounded below by 0 (checked at each step using gaussian_majority_error_le_half_nonneg_of_ciInf and ENNReal.toReal_nonneg), we can bound the infimum from above using ciInf_le_of_le by choosing the constant strategy f(x) = 0 (valid since 1 ≤ q) and g(m, y) = false, both of which are trivially measurable by measurable_const.

    lines 10–28

    uses gaussian_majority_error_le_half_nonneg_of_ciInf, ciInf_le_of_le, ENNReal.toReal_nonneg, measurable_const

      rw [gaussian_majority_error]
      refine ciInf_le_of_le ⟨0, ?_⟩ (fun _ : ℝ => (⟨0, hq⟩ : Fin q)) ?_
      · rintro _ ⟨f, rfl⟩
        apply gaussian_majority_error_le_half_nonneg_of_ciInf; intro hf
        apply gaussian_majority_error_le_half_nonneg_of_ciInf; intro g
        apply gaussian_majority_error_le_half_nonneg_of_ciInf; intro hg
        exact ENNReal.toReal_nonneg
      refine ciInf_le_of_le ⟨0, ?_⟩ measurable_const ?_
      · rintro _ ⟨hf, rfl⟩
        apply gaussian_majority_error_le_half_nonneg_of_ciInf; intro g
        apply gaussian_majority_error_le_half_nonneg_of_ciInf; intro hg
        exact ENNReal.toReal_nonneg
      refine ciInf_le_of_le ⟨0, ?_⟩ (fun _ _ => false) ?_
      · rintro _ ⟨g, rfl⟩
        apply gaussian_majority_error_le_half_nonneg_of_ciInf; intro hg
        exact ENNReal.toReal_nonneg
      refine ciInf_le_of_le ⟨0, ?_⟩ (fun _ => measurable_const) ?_
      · rintro _ ⟨hg, rfl⟩
        exact ENNReal.toReal_nonneg
  3. The error event of the trivial protocol is exactly the half-plane S = {p : ℝ × ℝ | 0 < p.1 + p.2}.

    With Bob always predicting false, an error occurs whenever false = true differs from 0 < p.1 + p.2. Since false = true is false, this condition simplifies to 0 < p.1 + p.2.

    lines 30–36

      have h_set : {p : ℝ × ℝ | ((fun (_ _ : ℝ) => false) ((fun _ => (⟨0, hq⟩ : Fin q)) p.1) p.2 = true) ≠ (0 < p.1 + p.2)} =
          {p : ℝ × ℝ | 0 < p.1 + p.2} := by
        ext p
        dsimp
        simp
      rw [h_set]
    
  4. The joint Gaussian distribution μ is a probability measure and is symmetric under reflection through the origin.

    The 1D Gaussians with mean 0 are Gaussian and hence probability measures by ProbabilityTheory.isGaussian_gaussianReal and ProbabilityTheory.IsGaussian.toIsProbabilityMeasure. Under negation x ↦ -x, each centered 1D Gaussian is invariant by ProbabilityTheory.gaussianReal_map_neg and neg_zero. Therefore, the product measure μ is invariant under the origin reflection p ↦ (-p.1, -p.2) by MeasureTheory.Measure.map_prod_map.

    lines 37–66

    uses ProbabilityTheory.isGaussian_gaussianReal, ProbabilityTheory.IsGaussian.toIsProbabilityMeasure, sq_nonneg, ProbabilityTheory.gaussianReal_map_neg, neg_zero, MeasureTheory.Measure.map_prod_map, measurable_neg

      have hG1 : ProbabilityTheory.IsGaussian (ProbabilityTheory.gaussianReal 0 ⟨lam ^ 2, sq_nonneg lam⟩) :=
        ProbabilityTheory.isGaussian_gaussianReal 0 ⟨lam ^ 2, sq_nonneg lam⟩
      have hP1 : MeasureTheory.IsProbabilityMeasure (ProbabilityTheory.gaussianReal 0 ⟨lam ^ 2, sq_nonneg lam⟩) :=
        ProbabilityTheory.IsGaussian.toIsProbabilityMeasure (ProbabilityTheory.gaussianReal 0 ⟨lam ^ 2, sq_nonneg lam⟩)
      have hG2 : ProbabilityTheory.IsGaussian (ProbabilityTheory.gaussianReal 0 1) :=
        ProbabilityTheory.isGaussian_gaussianReal 0 1
      have hP2 : MeasureTheory.IsProbabilityMeasure (ProbabilityTheory.gaussianReal 0 1) :=
        ProbabilityTheory.IsGaussian.toIsProbabilityMeasure (ProbabilityTheory.gaussianReal 0 1)
      have hSF1 : MeasureTheory.SFinite (ProbabilityTheory.gaussianReal 0 ⟨lam ^ 2, sq_nonneg lam⟩) := inferInstance
      have hSF2 : MeasureTheory.SFinite (ProbabilityTheory.gaussianReal 0 1) := inferInstance
    
      set μ : MeasureTheory.Measure (ℝ × ℝ) :=
        (ProbabilityTheory.gaussianReal 0 ⟨lam ^ 2, sq_nonneg lam⟩).prod (ProbabilityTheory.gaussianReal 0 1)
      have hPμ : MeasureTheory.IsProbabilityMeasure μ := inferInstance
    
      have h_symm_1 : MeasureTheory.Measure.map (fun x : ℝ => -x) (ProbabilityTheory.gaussianReal 0 ⟨lam ^ 2, sq_nonneg lam⟩) =
          ProbabilityTheory.gaussianReal 0 ⟨lam ^ 2, sq_nonneg lam⟩ := by
        have h := @ProbabilityTheory.gaussianReal_map_neg 0 ⟨lam ^ 2, sq_nonneg lam⟩
        simp only [neg_zero] at h
        exact h
      have h_symm_2 : MeasureTheory.Measure.map (fun x : ℝ => -x) (ProbabilityTheory.gaussianReal 0 1) = ProbabilityTheory.gaussianReal 0 1 := by
        have h := @ProbabilityTheory.gaussianReal_map_neg 0 1
        simp only [neg_zero] at h
        exact h
      have h_symm : MeasureTheory.Measure.map (fun p : ℝ × ℝ => (-p.1, -p.2)) μ = μ := by
        have h := (MeasureTheory.Measure.map_prod_map (ProbabilityTheory.gaussianReal 0 ⟨lam ^ 2, sq_nonneg lam⟩)
          (ProbabilityTheory.gaussianReal 0 1) measurable_neg measurable_neg).symm
        rw [h_symm_1, h_symm_2] at h
        exact h
    
  5. The measure of S under μ is at most 1/2.

    The set S = {p | 0 < p.1 + p.2} and its reflection -S = {p | 0 < -p.1 - p.2} are disjoint, since p.1 + p.2 cannot be both strictly positive and strictly negative. By symmetry, μ(-S) = μ(S). Since their union is contained in the universal set, which has total measure 1 under the probability measure μ, additivity gives 2 * μ(S) = μ(S) + μ(-S) ≤ 1, so μ(S) ≤ 1/2 in ENNReal.

    lines 67–91

    uses measurable_neg, MeasureTheory.Measure.map_apply, Set.disjoint_iff, Set.subset_univ, MeasureTheory.measure_union, MeasureTheory.measure_mono, MeasureTheory.measure_univ, two_mul, ENNReal.le_div_iff_mul_le, Or.inr, mul_comm

      set S : Set (ℝ × ℝ) := {p | 0 < p.1 + p.2}
      set neg_map : ℝ × ℝ → ℝ × ℝ := fun p => (-p.1, -p.2)
      have hS_meas : MeasurableSet S :=
        measurableSet_Ioi.preimage (measurable_fst.add measurable_snd)
      have h_neg_meas : Measurable neg_map := measurable_neg
      have h_map_S : μ (neg_map ⁻¹' S) = μ S := by
        have := (MeasureTheory.Measure.map_apply (μ := μ) h_neg_meas hS_meas).symm
        rw [h_symm] at this
        exact this
      have h_disj : Disjoint S (neg_map ⁻¹' S) := by
        rw [Set.disjoint_iff]
        rintro p ⟨hp1, hp2⟩
        dsimp [S, neg_map] at hp1 hp2
        linarith
      have h_union : S ∪ (neg_map ⁻¹' S) ⊆ Set.univ := Set.subset_univ _
      have h_meas_union : μ (S ∪ (neg_map ⁻¹' S)) = μ S + μ (neg_map ⁻¹' S) :=
        MeasureTheory.measure_union h_disj (hS_meas.preimage h_neg_meas)
      rw [h_map_S] at h_meas_union
      have h_le_univ : μ (S ∪ (neg_map ⁻¹' S)) ≤ μ Set.univ := MeasureTheory.measure_mono h_union
      rw [MeasureTheory.measure_univ (μ := μ)] at h_le_univ
      rw [h_meas_union] at h_le_univ
      have h2 : 2 * μ S = μ S + μ S := two_mul (μ S)
      rw [← h2] at h_le_univ
      have h_mu_le_half : μ S ≤ 1 / 2 :=
        ENNReal.le_div_iff_mul_le (Or.inr (by simp)) (Or.inr (by simp)) |>.2 (by simpa [mul_comm] using h_le_univ)
  6. gaussian_majority_error q lam ≤ 1 / 2 in ℝ.

    We convert 1/2 from ENNReal to ℝ and apply monotonicity of toReal (ENNReal.toReal_mono) to the inequality μ(S) ≤ 1/2.

    lines 92–94

    uses ENNReal.toReal_mono

      have h_half : ((1 : ℝ) / 2) = ENNReal.toReal (1 / 2) := by simp
      rw [h_half]
      exact ENNReal.toReal_mono (by norm_num) h_mu_le_half
gaussian_majority_error_le_half_nonneg_of_ciInf
For a family of non-negative real numbers, its infimum is also non-negative.
isEmpty_or_nonempty
A type is either empty or nonempty.
le_ciInf
If c is a lower bound of f on a nonempty index type, then c is at most the infimum of f.
ciInf_le_of_le
If a set is bounded below, its infimum is bounded above by any value in the set.
ENNReal.toReal_nonneg
The coercion of an extended non-negative real to a real is non-negative.
measurable_const
A constant function is measurable.
ProbabilityTheory.isGaussian_gaussianReal
A real Gaussian measure is indeed a Gaussian measure in the sense of ProbabilityTheory.
ProbabilityTheory.IsGaussian.toIsProbabilityMeasure
Any Gaussian probability distribution is a probability measure.
sq_nonneg
The square of any real number is non-negative.
ProbabilityTheory.gaussianReal_map_neg
The pushforward of a 1D centered Gaussian measure under negation is the Gaussian measure itself.
neg_zero
Negation of zero is zero.
MeasureTheory.Measure.map_prod_map
The product of two pushforward measures under coordinate-wise maps equals the pushforward of the product measure under the product map.
measurable_neg
The negation map on an additive group with measurable negation is measurable.
MeasureTheory.Measure.map_apply
The measure of a preimage under a measurable map equals the pushforward measure of the set.
Set.disjoint_iff
Two sets are disjoint if and only if their intersection is contained in the empty set.
Set.subset_univ
Every set is a subset of the universal set.
MeasureTheory.measure_union
The measure of the union of two disjoint measurable sets is the sum of their measures.
MeasureTheory.measure_mono
Measure is monotone with respect to set inclusion.
MeasureTheory.measure_univ
The total measure of the universal set under a probability measure is 1.
two_mul
For any element in a semiring, 2 * x = x + x.
ENNReal.le_div_iff_mul_le
For extended non-negative reals, division and multiplication by a positive finite constant are adjoint inequalities.
Or.inr
Right injection for disjunction.
mul_comm
Multiplication is commutative.
ENNReal.toReal_mono
Monotonicity of toReal for extended non-negative reals when the upper bound is finite.

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

lemma gaussian_majority_error_le_half_nonneg_of_ciInf {ι : Sort _} (F : ι → ℝ) (h : ∀ i, 0 ≤ F i) :    0 ≤ ⨅ i, F i := by  cases isEmpty_or_nonempty ι  · simp  · exact le_ciInf h/-- The Gaussian majority communication error is bounded above by 1/2. -/theorem gaussian_majority_error_le_half (q : ℕ) (hq : 1 ≤ q) (lam : ℝ) (hlam : 0 < lam) :    gaussian_majority_error q lam ≤ 1 / 2 := by  rw [gaussian_majority_error]  refine ciInf_le_of_le ⟨0, ?_⟩ (fun _ : ℝ => (⟨0, hq⟩ : Fin q)) ?_  · rintro _ ⟨f, rfl⟩    apply gaussian_majority_error_le_half_nonneg_of_ciInf; intro hf    apply gaussian_majority_error_le_half_nonneg_of_ciInf; intro g    apply gaussian_majority_error_le_half_nonneg_of_ciInf; intro hg    exact ENNReal.toReal_nonneg  refine ciInf_le_of_le ⟨0, ?_⟩ measurable_const ?_  · rintro _ ⟨hf, rfl⟩    apply gaussian_majority_error_le_half_nonneg_of_ciInf; intro g    apply gaussian_majority_error_le_half_nonneg_of_ciInf; intro hg    exact ENNReal.toReal_nonneg  refine ciInf_le_of_le ⟨0, ?_⟩ (fun _ _ => false) ?_  · rintro _ ⟨g, rfl⟩    apply gaussian_majority_error_le_half_nonneg_of_ciInf; intro hg    exact ENNReal.toReal_nonneg  refine ciInf_le_of_le ⟨0, ?_⟩ (fun _ => measurable_const) ?_  · rintro _ ⟨hg, rfl⟩    exact ENNReal.toReal_nonneg  have h_set : {p : ℝ × ℝ | ((fun (_ _ : ℝ) => false) ((fun _ => (⟨0, hq⟩ : Fin q)) p.1) p.2 = true) ≠ (0 < p.1 + p.2)} =      {p : ℝ × ℝ | 0 < p.1 + p.2} := by    ext p    dsimp    simp  rw [h_set]  have hG1 : ProbabilityTheory.IsGaussian (ProbabilityTheory.gaussianReal 0 ⟨lam ^ 2, sq_nonneg lam⟩) :=    ProbabilityTheory.isGaussian_gaussianReal 0 ⟨lam ^ 2, sq_nonneg lam⟩  have hP1 : MeasureTheory.IsProbabilityMeasure (ProbabilityTheory.gaussianReal 0 ⟨lam ^ 2, sq_nonneg lam⟩) :=    ProbabilityTheory.IsGaussian.toIsProbabilityMeasure (ProbabilityTheory.gaussianReal 0 ⟨lam ^ 2, sq_nonneg lam⟩)  have hG2 : ProbabilityTheory.IsGaussian (ProbabilityTheory.gaussianReal 0 1) :=    ProbabilityTheory.isGaussian_gaussianReal 0 1  have hP2 : MeasureTheory.IsProbabilityMeasure (ProbabilityTheory.gaussianReal 0 1) :=    ProbabilityTheory.IsGaussian.toIsProbabilityMeasure (ProbabilityTheory.gaussianReal 0 1)  have hSF1 : MeasureTheory.SFinite (ProbabilityTheory.gaussianReal 0 ⟨lam ^ 2, sq_nonneg lam⟩) := inferInstance  have hSF2 : MeasureTheory.SFinite (ProbabilityTheory.gaussianReal 0 1) := inferInstance  set μ : MeasureTheory.Measure (ℝ × ℝ) :=    (ProbabilityTheory.gaussianReal 0 ⟨lam ^ 2, sq_nonneg lam⟩).prod (ProbabilityTheory.gaussianReal 0 1)  have hPμ : MeasureTheory.IsProbabilityMeasure μ := inferInstance  have h_symm_1 : MeasureTheory.Measure.map (fun x : ℝ => -x) (ProbabilityTheory.gaussianReal 0 ⟨lam ^ 2, sq_nonneg lam⟩) =      ProbabilityTheory.gaussianReal 0 ⟨lam ^ 2, sq_nonneg lam⟩ := by    have h := @ProbabilityTheory.gaussianReal_map_neg 0 ⟨lam ^ 2, sq_nonneg lam⟩    simp only [neg_zero] at h    exact h  have h_symm_2 : MeasureTheory.Measure.map (fun x : ℝ => -x) (ProbabilityTheory.gaussianReal 0 1) = ProbabilityTheory.gaussianReal 0 1 := by    have h := @ProbabilityTheory.gaussianReal_map_neg 0 1    simp only [neg_zero] at h    exact h  have h_symm : MeasureTheory.Measure.map (fun p : ℝ × ℝ => (-p.1, -p.2)) μ = μ := by    have h := (MeasureTheory.Measure.map_prod_map (ProbabilityTheory.gaussianReal 0 ⟨lam ^ 2, sq_nonneg lam⟩)      (ProbabilityTheory.gaussianReal 0 1) measurable_neg measurable_neg).symm    rw [h_symm_1, h_symm_2] at h    exact h  set S : Set (ℝ × ℝ) := {p | 0 < p.1 + p.2}  set neg_map : ℝ × ℝ → ℝ × ℝ := fun p => (-p.1, -p.2)  have hS_meas : MeasurableSet S :=    measurableSet_Ioi.preimage (measurable_fst.add measurable_snd)  have h_neg_meas : Measurable neg_map := measurable_neg  have h_map_S : μ (neg_map ⁻¹' S) = μ S := by    have := (MeasureTheory.Measure.map_apply (μ := μ) h_neg_meas hS_meas).symm    rw [h_symm] at this    exact this  have h_disj : Disjoint S (neg_map ⁻¹' S) := by    rw [Set.disjoint_iff]    rintro p ⟨hp1, hp2⟩    dsimp [S, neg_map] at hp1 hp2    linarith  have h_union : S ∪ (neg_map ⁻¹' S) ⊆ Set.univ := Set.subset_univ _  have h_meas_union : μ (S ∪ (neg_map ⁻¹' S)) = μ S + μ (neg_map ⁻¹' S) :=    MeasureTheory.measure_union h_disj (hS_meas.preimage h_neg_meas)  rw [h_map_S] at h_meas_union  have h_le_univ : μ (S ∪ (neg_map ⁻¹' S)) ≤ μ Set.univ := MeasureTheory.measure_mono h_union  rw [MeasureTheory.measure_univ (μ := μ)] at h_le_univ  rw [h_meas_union] at h_le_univ  have h2 : 2 * μ S = μ S + μ S := two_mul (μ S)  rw [← h2] at h_le_univ  have h_mu_le_half : μ S ≤ 1 / 2 :=    ENNReal.le_div_iff_mul_le (Or.inr (by simp)) (Or.inr (by simp)) |>.2 (by simpa [mul_comm] using h_le_univ)  have h_half : ((1 : ℝ) / 2) = ENNReal.toReal (1 / 2) := by simp  rw [h_half]  exact ENNReal.toReal_mono (by norm_num) h_mu_le_half
See it in the graphDiscuss this resultChallenge it