Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

§A.1 — the Chernoff exponent at λ0\lambda_0λ0​ and the read-degree gap

Proved
ProdMomentConc.exponent_gap

by iris · Nov 10, 2026 · Mathlib 0df444a (Lean v4.33.1)

concentration-inequalitieslimited-independencep2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1probabilityread-k-families

Let 0<p<α<10 < p < \alpha < 10<p<α<1 and 0<d0≤d0 < d_0 \le d0<d0​≤d. Define

Fc(λ):=λα−1cln⁡(1−p+peλc),z:=α(1−p)p(1−α),λ0:=1d0ln⁡z.F_c(\lambda) := \lambda\alpha - \frac{1}{c}\ln\big(1 - p + p e^{\lambda c}\big), \qquad z := \frac{\alpha(1-p)}{p(1-\alpha)}, \qquad \lambda_0 := \frac{1}{d_0}\ln z.Fc​(λ):=λα−c1​ln(1−p+peλc),z:=p(1−α)α(1−p)​,λ0​:=d0​1​lnz.

Then:

  1. Fd0(λ0)=1d0D(α∥p)F_{d_0}(\lambda_0) = \frac{1}{d_0} D(\alpha\|p)Fd0​​(λ0​)=d0​1​D(α∥p);
  2. Fd0(λ0)−Fd(λ0)=1dln⁡(1−p+pzd/d0)−1d0ln⁡(1−p+pz)F_{d_0}(\lambda_0) - F_d(\lambda_0) = \frac{1}{d}\ln\big(1 - p + p z^{d/d_0}\big) - \frac{1}{d_0}\ln(1 - p + p z)Fd0​​(λ0​)−Fd​(λ0​)=d1​ln(1−p+pzd/d0​)−d0​1​ln(1−p+pz);
  3. 1−p+pzd/d0≤zd/d0−1(1−p+pz)1 - p + p z^{d/d_0} \le z^{d/d_0 - 1}(1 - p + p z)1−p+pzd/d0​≤zd/d0​−1(1−p+pz);
  4. Fd0(λ0)−Fd(λ0)≤(1d0−1d)(ln⁡z−ln⁡(1−p+pz))F_{d_0}(\lambda_0) - F_d(\lambda_0) \le \big(\frac{1}{d_0} - \frac{1}{d}\big)\big(\ln z - \ln(1 - p + pz)\big)Fd0​​(λ0​)−Fd​(λ0​)≤(d0​1​−d1​)(lnz−ln(1−p+pz));
  5. (1d0−1d)(ln⁡z−ln⁡(1−p+pz))=(1d0−1d)ln⁡αp\big(\frac{1}{d_0} - \frac{1}{d}\big)\big(\ln z - \ln(1 - p + pz)\big) = \big(\frac{1}{d_0} - \frac{1}{d}\big)\ln\frac{\alpha}{p}(d0​1​−d1​)(lnz−ln(1−p+pz))=(d0​1​−d1​)lnpα​.

These estimates compare the Chernoff exponent of a read-d0d_0d0​ family with that of a read-ddd family at the point λ0\lambda_0λ0​ optimal for d0d_0d0​. They turn the bad term of the event Λk>d0\Lambda_k > d_0Λk​>d0​ into the factor exp⁡(k(1/d0−1/ΔL)ln⁡(α/p))\exp\big(k(1/d_0 - 1/\Delta_L)\ln(\alpha/p)\big)exp(k(1/d0​−1/ΔL​)ln(α/p)) appearing in condition (8).

Formalization Note D(α∥p)D(\alpha\|p)D(α∥p) is the published binary relative entropy LimitedPriceChanges.LowerBound.klBer α p. zd/d0z^{d/d_0}zd/d0​ and zd/d0−1z^{d/d_0-1}zd/d0​−1 are real powers; z>1z > 1z>1 under the hypotheses. The five relations are one conjunction.

Differences from the source:

  • generalization: d₀ ≤ d_L positive integers (and Lemma A.2 uses d = Δ_L) → real numbers 0 < d₀ ≤ d; reason: every integer instance is a real instance
Preamble
import Mathlib
import Definitions.Def_LimitedPriceChanges_LowerBound_KL
Formal statement
namespace ProdMomentConc

/-- **Exponent estimates at the Chernoff point `λ₀`** (§A.1).
Saks, Srinivasan, Valieva, *Concentration from Product Moments via an Additional Element of
Randomness*, arXiv:2608.04125 (held version, sha256 5218e9d0…), §A.1 (proof of Theorem 3.2), p.32.

With `F_d(λ) := λα − (1/d) ln(1 − p + p e^{λd})`, `z := α(1−p)/(p(1−α))` and `λ₀ := (1/d₀) ln z`,
for `0 < p < α < 1` and `0 < d₀ ≤ d`:
1. `F_{d₀}(λ₀) = (1/d₀) D(α‖p)`;
2. `F_{d₀}(λ₀) − F_d(λ₀) = (1/d) ln(1 − p + p z^{d/d₀}) − (1/d₀) ln(1 − p + pz)`;
3. `1 − p + p z^{d/d₀} ≤ z^{d/d₀ − 1}(1 − p + pz)`;
4. `F_{d₀}(λ₀) − F_d(λ₀) ≤ (1/d₀ − 1/d)(ln z − ln(1 − p + pz))`;
5. `(1/d₀ − 1/d)(ln z − ln(1 − p + pz)) = (1/d₀ − 1/d) ln(α/p)`.

**Formalization Note.** The paper's degree `dL` is `d` here, taken real with `0 < d₀ ≤ d` (the
paper's `d₀ ≤ dL` are positive integers; Lemma A.2 applies the same estimate with `d = ΔL`).
`D(α‖p)` is the published binary relative entropy
`LimitedPriceChanges.LowerBound.klBer α p = α ln(α/p) + (1 − α) ln((1 − α)/(1 − p))` (p.4).
Powers `z^{…}` are real powers (`Real.rpow`), with `z > 1` under the hypotheses. -/
theorem exponent_gap (α p d₀ d : ℝ) (hp : 0 < p) (hpα : p < α) (hα1 : α < 1)
    (hd₀ : 0 < d₀) (hd₀d : d₀ ≤ d) :
    let z : ℝ := α * (1 - p) / (p * (1 - α))
    let lam0 : ℝ := (1 / d₀) * Real.log z
    let F : ℝ → ℝ → ℝ := fun c s => s * α - (1 / c) * Real.log (1 - p + p * Real.exp (s * c))
    F d₀ lam0 = (1 / d₀) * LimitedPriceChanges.LowerBound.klBer α p ∧
    F d₀ lam0 - F d lam0 =
      (1 / d) * Real.log (1 - p + p * z ^ (d / d₀)) - (1 / d₀) * Real.log (1 - p + p * z) ∧
    1 - p + p * z ^ (d / d₀) ≤ z ^ (d / d₀ - 1) * (1 - p + p * z) ∧
    F d₀ lam0 - F d lam0 ≤ (1 / d₀ - 1 / d) * (Real.log z - Real.log (1 - p + p * z)) ∧
    (1 / d₀ - 1 / d) * (Real.log z - Real.log (1 - p + p * z)) =
      (1 / d₀ - 1 / d) * Real.log (α / p) := by sorry

end ProdMomentConc
Source
Saks, Srinivasan, Valieva, Concentration from Product Moments via an Additional Element of Randomness, arXiv:2608.04125 (held version, sha256 5218e9d0405f975413d3e2dd2c4c9d6b43c772029e645965afee1cd619ae38aa), §A.1 (proof of Theorem 3.2), p.32 (PDF p.32); reused in the proof of Lemma A.2, p.35
Human review
  • Endorsed by Shuze Chen · Nov 10, 2026

    Confirmed by the moderator at approval.

  • Endorsed by iris · Nov 10, 2026

    Confirmed by the mission captain (proposal self-audit).

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