Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Matrix Chernoff scalar transform coefficient and tail functions

Definition
TroppMatrixConcentration_ch5_chernoff_functions

by tc · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

matrix-concentrationrandom-matrices

Define c(L,θ)=(eθL−1)/Lc(L,\theta)=(e^{\theta L}-1)/Lc(L,θ)=(eθL−1)/L for L≠0L\ne0L=0, and c(0,θ)=θc(0,\theta)=\thetac(0,θ)=θ by continuous extension. Define the lower-tail expression

d[e−ε/(1−ε)1−ε]a/Ld\left[e^{-\varepsilon}/(1-\varepsilon)^{1-\varepsilon}\right]^{a/L}d[e−ε/(1−ε)1−ε]a/L

and the upper-tail expression

d[eε/(1+ε)1+ε]a/Ld\left[e^\varepsilon/(1+\varepsilon)^{1+\varepsilon}\right]^{a/L}d[eε/(1+ε)1+ε]a/L

when L≠0L\ne0L=0, using real powers. When L=0L=0L=0, define both tail expressions to be ddd. The theorem statements restrict the lower-tail deviation to 0≤ε<10\le\varepsilon<10≤ε<1 and the upper-tail deviation to ε≥0\varepsilon\ge0ε≥0, so their bases are positive. They impose L≥0L\ge0L≥0 and positive dimension. At L=0L=0L=0 all permitted summands vanish, so the relevant non-strict relative tail events occur at zero. These scalar definitions introduce no probabilistic assumptions or conclusions.

Definition code
import Definitions.Def_TroppMatrixConcentration_probability
import Mathlib.Analysis.SpecialFunctions.Pow.Real

noncomputable section
namespace TroppMatrixConcentration

def chernoffCgfCoefficient (L θ : ℝ) : ℝ :=
  if L = 0 then θ else (Real.exp (θ * L) - 1) / L

def chernoffLowerTail (dimension : ℕ) (a L ε : ℝ) : ℝ :=
  if L = 0 then (dimension : ℝ)
  else (dimension : ℝ) * Real.rpow
    (Real.exp (-ε) / Real.rpow (1 - ε) (1 - ε)) (a / L)

def chernoffUpperTail (dimension : ℕ) (a L ε : ℝ) : ℝ :=
  if L = 0 then (dimension : ℝ)
  else (dimension : ℝ) * Real.rpow
    (Real.exp ε / Real.rpow (1 + ε) (1 + ε)) (a / L)

end TroppMatrixConcentration
Source
Joel A. Tropp, An Introduction to Matrix Concentration Inequalities, arXiv:1501.01571v1 (7 January 2015); https://arxiv.org/abs/1501.01571v1; Theorem 5.1.1, equations (5.1.5–6), printed p. 60; Lemma 5.4.1, printed p. 70.
Read-back

What the Lean code literally says, in plain math · gpt-6

chernoffCgfCoefficient. For arbitrary real numbers LLL and θ\thetaθ, this defines a real number equal to θ\thetaθ if L=0L=0L=0, and equal to (exp⁡(θL)−1)/L(\exp(\theta L)-1)/L(exp(θL)−1)/L if L≠0L\ne0L=0. There are no sign restrictions on either argument. In particular, the value is zero whenever θ=0\theta=0θ=0, including when L=0L=0L=0.

chernoffLowerTail. For any natural number ddd (including zero) and any real numbers a,L,εa,L,\varepsilona,L,ε, this defines the real number ddd if L=0L=0L=0, and otherwise defines d R(exp⁡(−ε)/R(1−ε,1−ε),a/L)d\,R\bigl(\exp(-\varepsilon)/R(1-\varepsilon,1-\varepsilon),a/L\bigr)dR(exp(−ε)/R(1−ε,1−ε),a/L), with ddd viewed as a real number. Here the total real power function RRR is given by R(x,y)=exp⁡(ylog⁡x)R(x,y)=\exp(y\log x)R(x,y)=exp(ylogx) for x>0x>0x>0, R(0,0)=1R(0,0)=1R(0,0)=1, R(0,y)=0R(0,y)=0R(0,y)=0 for every nonzero real yyy (including negative yyy), and R(x,y)=exp⁡(ylog⁡∣x∣)cos⁡(πy)R(x,y)=\exp(y\log|x|)\cos(\pi y)R(x,y)=exp(ylog∣x∣)cos(πy) for x<0x<0x<0; division by zero has value zero. No positivity assumptions on aaa or LLL, or interval restrictions on ε\varepsilonε, are imposed. Thus the expression also covers ε>1\varepsilon>1ε>1, when the inner real power has a negative base and may have zero or negative value. If its value is zero and L≠0L\ne0L=0, the quotient supplied to the outer power is zero, so the result is ddd when a=0a=0a=0 and zero when a≠0a\ne0a=0. At ε=1\varepsilon=1ε=1 the inner power is R(0,0)=1R(0,0)=1R(0,0)=1, and, when L≠0L\ne0L=0, the result is dexp⁡(−a/L)d\exp(-a/L)dexp(−a/L). The value is zero for d=0d=0d=0, and is ddd whenever a=0a=0a=0 or ε=0\varepsilon=0ε=0, including in the L=0L=0L=0 branch.

chernoffUpperTail. For any natural number ddd (including zero) and any real numbers a,L,εa,L,\varepsilona,L,ε, this defines the real number ddd if L=0L=0L=0, and otherwise defines d R(exp⁡(ε)/R(1+ε,1+ε),a/L)d\,R\bigl(\exp(\varepsilon)/R(1+\varepsilon,1+\varepsilon),a/L\bigr)dR(exp(ε)/R(1+ε,1+ε),a/L), with ddd viewed as a real number. Here the total real power function RRR is given by R(x,y)=exp⁡(ylog⁡x)R(x,y)=\exp(y\log x)R(x,y)=exp(ylogx) for x>0x>0x>0, R(0,0)=1R(0,0)=1R(0,0)=1, R(0,y)=0R(0,y)=0R(0,y)=0 for every nonzero real yyy (including negative yyy), and R(x,y)=exp⁡(ylog⁡∣x∣)cos⁡(πy)R(x,y)=\exp(y\log|x|)\cos(\pi y)R(x,y)=exp(ylog∣x∣)cos(πy) for x<0x<0x<0; division by zero has value zero. No positivity assumptions on aaa or LLL, or interval restrictions on ε\varepsilonε, are imposed. Thus the expression also covers ε<−1\varepsilon<-1ε<−1, when the inner real power has a negative base and may have zero or negative value. If its value is zero and L≠0L\ne0L=0, the quotient supplied to the outer power is zero, so the result is ddd when a=0a=0a=0 and zero when a≠0a\ne0a=0. At ε=−1\varepsilon=-1ε=−1 the inner power is R(0,0)=1R(0,0)=1R(0,0)=1, and, when L≠0L\ne0L=0, the result is dexp⁡(−a/L)d\exp(-a/L)dexp(−a/L). The value is zero for d=0d=0d=0, and is ddd whenever a=0a=0a=0 or ε=0\varepsilon=0ε=0, including in the L=0L=0L=0 branch.

Human review
  • Endorsed by Shuze Chen · Oct 7, 2026

    Confirmed by the moderator at approval.

  • Endorsed by tc · Oct 7, 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