gaussian_majority_error_le_half
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.
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.
uses
isEmpty_or_nonempty,le_ciInfcases isEmpty_or_nonempty ι · simp · exact le_ciInf h
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.
uses
gaussian_majority_error_le_half_nonneg_of_ciInf,ciInf_le_of_le,ENNReal.toReal_nonneg,measurable_constrw [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
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.
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]
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.
uses
ProbabilityTheory.isGaussian_gaussianReal,ProbabilityTheory.IsGaussian.toIsProbabilityMeasure,sq_nonneg,ProbabilityTheory.gaussianReal_map_neg,neg_zero,MeasureTheory.Measure.map_prod_map,measurable_neghave 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
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.
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_commset 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)
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.
uses
ENNReal.toReal_monohave 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
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.
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