Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

talagrand_appendix91_log_exponent_absorbs_polynomial_failure

Disproved

by Shuze Chen · Jun 29, 2026 · Mathlib c5ea003 (Lean v4.30.0)

appendix-91candes-rechtmatrix-completionpolynomial-tailscalar-arithmeticsource-faithfultalagrand

This scalar theorem isolates the last numerical step in Candès--Recht Appendix 9.1.

Let B=2μ0nr/mB=2\mu_0nr/mB=2μ0​nr/m, n=max⁡(n1,n2)n=\max(n_1,n_2)n=max(n1​,n2​), and assume the sample lower bound

m≥C′μ0nr βlog⁡n.m\ge C'\mu_0nr\,\beta\log n.m≥C′μ0​nrβlogn.

For a sufficiently large universal constant CCC, set

t=Cμ0nr βlog⁡nm.t=C\sqrt{\frac{\mu_0nr\,\beta\log n}{m}}.t=Cmμ0​nrβlogn​​.

The theorem asserts that t≥0t\ge0t≥0 and that the logarithmic Talagrand failure term from equation (9.2), with EZ≤1\mathbb E Z\le1EZ≤1, is bounded by cn−βc n^{-\beta}cn−β. This is exactly the scalar absorption used before Theorem 4.2 equation (4.10).

Source location: Candès--Recht 2008, Appendix 9.1, PDF p. 47, the paragraph beginning “Since EZ≤1\mathbb E Z\le1EZ≤1” through “Plugging t=λμ0nrlog⁡n/mt=\lambda\sqrt{\mu_0nr\log n/m}t=λμ0​nrlogn/m​ and B=2μ0nr/mB=2\mu_0nr/mB=2μ0​nr/m establishes the claim.”

Preamble
import Definitions.Def_matrix_completion_tangent
import Mathlib.Analysis.SpecialFunctions.Log.Basic

open MatrixCompletion

/-- Scalar failure-probability absorption in the Appendix 9.1 Talagrand
argument.

With `B = 2 μ₀ n r / m`, `E Z ≤ 1`, and the Candes--Recht sample lower bound,
the logarithmic exponent in Theorem 9.1 at the standard tangent-deviation scale
is large enough to dominate a polynomial failure probability `c n^{-β}`.  The
theorem also records that the chosen deviation scale is nonnegative, so it can
be substituted into the tail bound.

Source: Candes--Recht, Appendix 9.1, PDF p. 47, the paragraph beginning
"Since E Z ≤ 1" through "Plugging t = ... establishes the claim", using
Theorem 9.1 equation (9.2). -/
Formal statement
theorem talagrand_appendix91_log_exponent_absorbs_polynomial_failure
    (K : ℝ) :
    0 < K →
    ∃ C c : ℝ, 0 < C ∧ 0 < c ∧
      ∀ C' : ℝ, C ≤ C' →
      ∀ (β : ℝ), 2 < β →
      ∀ (n₁ n₂ r m : ℕ) (μ₀ meanZ : ℝ),
        0 < n₁ → 0 < n₂ → 0 < r → 0 < m → m ≤ n₁ * n₂ →
        1 ≤ μ₀ →
        (m : ℝ) ≥
          C' * μ₀ * (↑(max n₁ n₂)) * (r : ℝ) *
            (β * Real.log (↑(max n₁ n₂))) →
        meanZ ≤ 1 →
        0 ≤ tangentSamplingDeviationScale C β μ₀ (max n₁ n₂) r m ∧
          3 * Real.exp
            (-(tangentSamplingDeviationScale C β μ₀ (max n₁ n₂) r m /
                (K * (2 * μ₀ * (↑(max n₁ n₂)) * (r : ℝ) / (m : ℝ)))) *
              Real.log
                (1 +
                  ((2 * μ₀ * (↑(max n₁ n₂)) * (r : ℝ) / (m : ℝ)) *
                      tangentSamplingDeviationScale C β μ₀ (max n₁ n₂) r m) /
                    ((2 * μ₀ * (↑(max n₁ n₂)) * (r : ℝ) / (m : ℝ)) +
                      (2 * μ₀ * (↑(max n₁ n₂)) * (r : ℝ) / (m : ℝ)) *
                        meanZ))) ≤
            c * Real.rpow (↑(max n₁ n₂)) (-β) := by
  sorry
Source
Candes, Emmanuel, and Benjamin Recht. "Exact Matrix Completion via Convex Optimization" (2008).

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