Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Lemma 5.2 — PSD diagonal-estimation lower bound

Open
SketchAttr.LOO.Supplement.lemma_5_2

by mikedeng1 · Nov 15, 2026 · Mathlib 0df444a (Lean v4.33.1)

diagonal-estimationp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1query-complexity

There are universal constants b,c>0b,c>0b,c>0, with c≤1c\le1c≤1, such that the following holds for every n≥1n\ge1n≥1. Fix any randomized adaptive real matrix-vector procedure with worst-case budget qqq. If, for every real positive semidefinite n×nn\times nn×n matrix AAA with ∥A∥F≤1/16\|A\|_F\le1/16∥A∥F​≤1/16, it satisfies

Pr⁡seed ⁣(∑i=1n∣L^i−Aii∣2≤c2/n)≥23,\Pr_{\mathrm{seed}}\!\left(\sum_{i=1}^n|\widehat L_i-A_{ii}|^2\le c^2/n\right)\ge\frac23,seedPr​(i=1∑n​∣Li​−Aii​∣2≤c2/n)≥32​,

then

q>bn.q>bn.q>bn.

This is the explicit universal-constant meaning of the paper's Ω(n)\Omega(n)Ω(n) query requirement. It supports the reduction from attribution to diagonal estimation. The seed law and all query and output maps are fixed before the unknown matrix.

Differences from the source:

  • encoding: indices in [n] and probabilities over random seeds → indices in Fin n and an arbitrary measurable seed probability space; reason: zero-based labels and explicit probability laws change no instance
  • encoding: there is c greater than zero and a query lower bound Omega(n) → there are universal b and c greater than zero with c at most one and q greater than bn; reason: this exposes the stopping-after-budget form proved in Appendix C; c can be decreased to at most one
  • encoding: a randomized adaptive procedure with a worst-case query budget → a measurable fixed-length transcript padded for any earlier stopping; reason: the same oracle access and success guarantee are retained without a computation restriction
Preamble
import Mathlib
import Definitions.Def_SketchAttr_LOO_Supplement_Quadratic

open MeasureTheory
open scoped ENNReal
Formal statement
namespace SketchAttr.LOO.Supplement

theorem lemma_5_2 :
    ∃ b c : ℝ, 0 < b ∧ 0 < c ∧ c ≤ 1 ∧
      ∀ (n : ℕ), 1 ≤ n → ∀ (Seed : Type) [MeasurableSpace Seed]
        (μ : Measure Seed) [IsProbabilityMeasure μ] (q : ℕ)
        (P : MatrixProcedure Seed n q),
      (∀ A : RealMatrix n, A.PosSemidef → matrixFrobNorm A ≤ 1/16 →
        (2/3 : ℝ≥0∞) ≤ μ {seed | squaredDiagonalError (matrixEstimate P A seed) A ≤
          c^2 / n}) →
      b * n < (q : ℝ) := by sorry

end SketchAttr.LOO.Supplement
Source
Chris Liaw, Aranyak Mehta, Grigoris Velegkas, Felix Zhou, Sketching Language Models for Context Attribution, STOC 2027 submission #9 (October 2026), PDF sha256 86af2569e45c55b1009e7453d4f53047b5820d44868a7f528bdb6fed1a2ef0e2, p. 19, Lemma 5.2; repeated pp. 28–29 and proved p. 29

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