Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Threshold separation for sums of independent geometric variables: Pr⁡(K+>τ)−Pr⁡(K−>τ)≥c δ/s\Pr(K_+>\tau)-\Pr(K_->\tau)\ge c\,\delta/sPr(K+​>τ)−Pr(K−​>τ)≥cδ/s (Lemmas 13–14)

Proved
BosonicLearn.geometric_pgf_threshold

by Senrui Chen · Nov 13, 2026 · Mathlib 0df444a (Lean v4.33.1)

bosonic-gaussian-statesquantum-informationquantum-learning

Lemmas 13 and 14 of the paper, combined and specialized to the photon-count distributions of the proof of Lemma 12.

Fix Λ>0\Lambda>0Λ>0. There is a constant c=c(Λ)>0c=c(\Lambda)>0c=c(Λ)>0 with the following property. Let 0≤λi−≤λi+≤Λ0\le\lambda^-_i\le\lambda^+_i\le\Lambda0≤λi−​≤λi+​≤Λ for i=1,…,mi=1,\dots,mi=1,…,m, and let

K+=∑i=1mMi+,K−=∑i=1mMi−K_+=\sum_{i=1}^mM^+_i,\qquad K_-=\sum_{i=1}^mM^-_iK+​=i=1∑m​Mi+​,K−​=i=1∑m​Mi−​

be sums of independent geometric random variables on {0,1,2,… }\{0,1,2,\dots\}{0,1,2,…} with means λi±\lambda^\pm_iλi±​ (so E zK±=∏i11+λi±(1−z)\mathbb E\,z^{K_\pm}=\prod_i\frac1{1+\lambda^\pm_i(1-z)}EzK±​=∏i​1+λi±​(1−z)1​). Put

δ=∑i(λi+−λi−),s2=1+Var⁡(K−)=1+∑iλi−(1+λi−).\delta=\sum_i(\lambda^+_i-\lambda^-_i),\qquad s^2=1+\operatorname{Var}(K_-)=1+\sum_i\lambda^-_i(1+\lambda^-_i).δ=i∑​(λi+​−λi−​),s2=1+Var(K−​)=1+i∑​λi−​(1+λi−​).

If 0<δ≤s0<\delta\le s0<δ≤s, then there is a threshold τ∈N\tau\in\mathbb Nτ∈N such that

Pr⁡(K+>τ)−Pr⁡(K−>τ) ≥ c δs.\Pr(K_+>\tau)-\Pr(K_->\tau)\ \ge\ c\,\frac\delta s .Pr(K+​>τ)−Pr(K−​>τ) ≥ csδ​.

Role. In the proof of Lemma 12, K±K_\pmK±​ are the photon counts in a subspace of modes for the two passive Gaussian states; the linear dependence on δ/s\delta/sδ/s (rather than the quadratic one a second-moment argument would give) is what yields the trace-distance bound ≳ξnν\gtrsim\xi\sqrt{n\nu}≳ξnν​.

Formalization Note The two laws are sequences pp pm : ℕ → ℝ with non-negative entries, specified through their probability generating functions on [0,1][0,1][0,1] (HasSum (fun k => p k * z ^ k) (∏ i, (1 + λ i * (1 - z))⁻¹)), which determine them; at z=1z=1z=1 this says they have total mass one. The hypothesis δ≤s\delta\le sδ≤s is written δ2≤s2\delta^2\le s^2δ2≤s2. The constant depends only on Λ\LambdaΛ (the proof gives c=1/(480+70Λ)c=1/(480+70\Lambda)c=1/(480+70Λ)).

Preamble
import Mathlib
Formal statement
namespace BosonicLearn

/-- **Threshold separation for sums of independent geometric variables (Lemmas 13 and 14 combined).**
Chen, Anna Mele, Anna Mele, Preskill, *When are bosonic Gaussian states classical to learn?*, arXiv:2609.26705, §5.7, Lemma 13 (coarse Lévy concentration bound), Lemma 14 (threshold separation under convolution order), and the coupling
of Eqs. (137)–(142).

Fix `Λ > 0`. There is `c > 0` such that the following holds. Let `0 ≤ λ⁻_i ≤ λ⁺_i ≤ Λ` (`i = 1, …, m`), and let
`p⁺, p⁻` be the laws on `ℕ` of `K₊ = ∑ᵢ M⁺ᵢ` and `K₋ = ∑ᵢ M⁻ᵢ`, sums of independent geometric variables with
means `λ^±_i` — given through their probability generating functions
`∑ₖ p^±_k zᵏ = ∏ᵢ 1/(1 + λ^±_i (1 − z))`, `0 ≤ z ≤ 1`. Put `δ = ∑ᵢ (λ⁺_i − λ⁻_i)` and
`s² = 1 + Var(K₋) = 1 + ∑ᵢ λ⁻_i(1 + λ⁻_i)`. If `0 < δ ≤ s`, then there is a threshold `τ` with

`Pr(K₊ > τ) − Pr(K₋ > τ) ≥ c δ / s`.

**Formalization Note.** The laws are sequences `ℕ → ℝ` with non-negative entries, determined by the generating
function identities (at `z = 1` they give total mass one). `δ ≤ s` is written `δ² ≤ s²`. -/
theorem geometric_pgf_threshold :
    ∀ Λ : ℝ, 0 < Λ → ∃ c : ℝ, 0 < c ∧
      ∀ (m : ℕ) (lp lm : Fin m → ℝ), (∀ i, 0 ≤ lm i) → (∀ i, lm i ≤ lp i) → (∀ i, lp i ≤ Λ) →
      ∀ (pp pm : ℕ → ℝ), (∀ k, 0 ≤ pp k) → (∀ k, 0 ≤ pm k) →
        (∀ z : ℝ, 0 ≤ z → z ≤ 1 →
          HasSum (fun k => pp k * z ^ k) (∏ i, (1 + lp i * (1 - z))⁻¹)) →
        (∀ z : ℝ, 0 ≤ z → z ≤ 1 →
          HasSum (fun k => pm k * z ^ k) (∏ i, (1 + lm i * (1 - z))⁻¹)) →
        0 < ∑ i, (lp i - lm i) →
        (∑ i, (lp i - lm i)) ^ 2 ≤ 1 + ∑ i, lm i * (1 + lm i) →
        ∃ τ : ℕ, c * (∑ i, (lp i - lm i)) / Real.sqrt (1 + ∑ i, lm i * (1 + lm i)) ≤
          (∑' k, if τ < k then pp k else 0) - ∑' k, if τ < k then pm k else 0 := by sorry

end BosonicLearn
Source
Chen, Anna Mele, Anna Mele, Preskill, When are bosonic Gaussian states classical to learn?, arXiv:2609.26705, §5.7, Lemma 13 (coarse Lévy concentration bound), Lemma 14 (threshold separation under convolution order), and Eqs. (137)–(142)

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me