AFTD Auto-Formalizing Theoretical Domains

CommunicationComplexity.Internal.cdf_mono

theoremverifiedimported Lean

Monotonicity of the cumulative distribution function. Let $p$ be a probability mass function on $\mathrm{Fin}\,m$, and for each natural number $n$ let $\mathrm{cdf}(p, n) = \sum_{j < n} p(j) \in \bbr_{\ge 0}^\infty$ be the total mass assigned to the indices below $n$. Then the map $n \mapsto \mathrm{cdf}(p, n)$ is monotone: whenever $n_1 \le n_2$, one has $\mathrm{cdf}(p, n_1) \le \mathrm{cdf}(p, n_2)$.

Statement

set_option relaxedAutoImplicit false in
set_option autoImplicit false in
open MeasureTheory in
open scoped ENNReal in
lemma CommunicationComplexity.Internal.cdf_mono {m : ℕ} (p : PMF (Fin m)) :
    Monotone (cdf p)
Source
TCSlib, `CommunicationComplexity.Internal.cdf_mono`
Lean proof
By Lucy Horowitz, Timothe Kasriel, Mihir Singhal, from github.com/Shilun-Allan-Li/tcslib at c8a02591b1e5 (Copyright (c) 2026 Lucy Horowitz, Timothe Kasriel, and Mihir Singhal. All rights reserved, Apache-2.0). Compiled here against leanprover/lean4:v4.33.1, Mathlib v4.33.1; written for leanprover/lean4:v4.25.0.
What was changed in CommunicationComplexity.Internal.cdf_mono
--- TCSlib/CommunicationComplexity/NewmanTheorem/PrivateCoinApproximation.lean:99 (CommunicationComplexity.Internal.cdf_mono)
+++ as compiled here
@@ -1,3 +1,6 @@
-/-- The cumulative distribution function is monotone. -/
-lemma cdf_mono {m : ℕ} (p : PMF (Fin m)) :
+set_option relaxedAutoImplicit false in
+set_option autoImplicit false in
+open MeasureTheory in
+open scoped ENNReal in
+lemma CommunicationComplexity.Internal.cdf_mono {m : ℕ} (p : PMF (Fin m)) :
     Monotone (cdf p) := by
@@ -10,3 +13,3 @@
   · exact absurd (lt_of_lt_of_le h1 hij) h2
-  · exact zero_le _
+  · exact zero_le
   · exact le_refl _
Verified
07 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 2
Used by 2

Lean source view module on GitHub

set_option relaxedAutoImplicit false inset_option autoImplicit false inopen MeasureTheory inopen scoped ENNReal in/-- The cumulative distribution function is monotone. -/lemma CommunicationComplexity.Internal.cdf_mono {m : ℕ} (p : PMF (Fin m)) :    Monotone (cdf p) := by  intro i j hij  unfold cdf  apply Finset.sum_le_sum  intro k _  split_ifs with h1 h2  · exact le_refl _  · exact absurd (lt_of_lt_of_le h1 hij) h2  · exact zero_le  · exact le_refl _
See it in the graphDiscuss this resultChallenge it