Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Real Gaussian Gram matrices and the quadratic oracle

Definition
SketchAttr_LOO_Supplement_Quadratic

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

arithmetic-circuitsgaussian-matricesoracle-modelp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1

For a real matrix G∈Rr×nG\in\mathbb R^{r\times n}G∈Rr×n, let Gram⁡(G)=G⊤G\operatorname{Gram}(G)=G^\top GGram(G)=G⊤G, with independent standard N(0,1)N(0,1)N(0,1) entries under the matrix law. For a real square matrix AAA, its Frobenius norm is the published order-two tensor norm after embedding its entries into C\mathbb CC. Define

ϕA(w)=∑i,jAijwiwj,α(B)=B2/16.\phi_A(w)=\sum_{i,j}A_{ij}w_iw_j,\qquad \alpha(B)=B^2/16.ϕA​(w)=i,j∑​Aij​wi​wj​,α(B)=B2/16.

The real matrix-vector oracle returns AxAxAx. The quadratic oracle accepts every w,g∈Cnw,g\in\mathbb C^nw,g∈Cn and every integer N≥1N\ge1N≥1 and returns ϕA(w)\phi_A(w)ϕA​(w) together with Dgr∇ϕA(w)D_g^r\nabla\phi_A(w)Dgr​∇ϕA​(w) for 0≤r≤N0\le r\le N0≤r≤N. A sequence stores these vector responses, with zero padding beyond the requested degree. The free value and gradient at zero are the fixed pair (0,0)(0,0)(0,0), so they carry no hidden input information. Query and terminal maps receive no matrix or circuit encoding. The two oracle specializations instantiate the unrestricted adaptive interface, and squared diagonal error means ∑i∣L^i−Aii∣2\sum_i|\widehat L_i-A_{ii}|^2∑i​∣Li​−Aii​∣2.

This fixes the real Gaussian normalization and preserves the transpose convention; no complex conjugation occurs in the quadratic polynomial.

Definition code
import Mathlib
import Definitions.Def_SketchAttr_LOO_Taylor
import Definitions.Def_SketchAttr_LOO_Stability
import Definitions.Def_SketchAttr_LOO_Supplement_Adaptive

open MeasureTheory ProbabilityTheory
open scoped ENNReal

namespace SketchAttr.LOO.Supplement

instance realMatrixMeasurableSpace (r n : ℕ) :
    MeasurableSpace (Matrix (Fin r) (Fin n) ℝ) :=
  inferInstanceAs (MeasurableSpace (Fin r → Fin n → ℝ))

abbrev RealMatrix (n : ℕ) := Matrix (Fin n) (Fin n) ℝ
abbrev RealVector (n : ℕ) := Fin n → ℝ

noncomputable def matrixTensor {n : ℕ} (A : RealMatrix n) : Tensor n 2 :=
  fun j => (A (j 0) (j 1) : ℂ)

/-- The published order-two tensor norm, with the real matrix embedded in C. -/
noncomputable def matrixFrobNorm {n : ℕ} (A : RealMatrix n) : ℝ :=
  frobNorm (matrixTensor A)

noncomputable def realGaussianMatrix (r n : ℕ) :
    Measure (Matrix (Fin r) (Fin n) ℝ) :=
  Measure.pi fun _ : Fin r => Measure.pi fun _ : Fin n => gaussianReal 0 1

noncomputable def gram {r n : ℕ} (G : Matrix (Fin r) (Fin n) ℝ) : RealMatrix n :=
  fun i j => ∑ a, G a i * G a j

/-- No conjugation: the source uses transpose, not conjugate transpose. -/
noncomputable def quadratic {n : ℕ} (A : RealMatrix n) (w : Vec n) : ℂ :=
  ∑ i, ∑ j, (A i j : ℂ) * w i * w j

noncomputable def quadraticProfile : StabilityProfile :=
  fun B => ENNReal.ofReal (B.val ^ 2 / 16)

abbrev MatrixProcedure (Seed : Type*) [MeasurableSpace Seed] (n q : ℕ) :=
  AdaptiveProcedure Seed (RealVector n) (RealVector n) (RealVector n) q

noncomputable def matrixEstimate {Seed : Type*} [MeasurableSpace Seed] {n q : ℕ}
    (P : MatrixProcedure Seed n q) (A : RealMatrix n) (seed : Seed) : RealVector n :=
  adaptiveOutput P (fun x => A.mulVec x) seed

noncomputable def squaredDiagonalError {n : ℕ} (v : RealVector n) (A : RealMatrix n) : ℝ :=
  ∑ i, |v i - A i i| ^ 2

/-- All positive query degrees are permitted, with no fixed cap. -/
abbrev QuadraticQuery (n : ℕ) := Vec n × Vec n × {N : ℕ // 1 ≤ N}

/-- The sequence represents degrees 0 through the chosen N; all later
coordinates are set to zero and reveal no additional information. -/
abbrev QuadraticAnswer (n : ℕ) := ℂ × (ℕ → Vec n)

/-- Exactly the oracle of Section 5.3, evaluated on the quadratic polynomial.
Degree zero of the vector sequence is the gradient itself. -/
noncomputable def quadraticOracle {n : ℕ} (A : RealMatrix n)
    (Q : QuadraticQuery n) : QuadraticAnswer n :=
  (quadratic A Q.1, fun r => if r ≤ Q.2.2.val then
    iteratedFDeriv ℂ r (gradient (quadratic A)) Q.1 (fun _ => Q.2.1) else 0)

abbrev QuadraticProcedure (Seed : Type*) [MeasurableSpace Seed] (n q : ℕ) :=
  AdaptiveProcedure Seed (QuadraticQuery n) (QuadraticAnswer n) (Vec n) q

/-- The free value and gradient at zero are identically (0,0) on this family.
They are public constants, so omitting a redundant argument gives every
procedure exactly the same access. No circuit encoding is passed to P. -/
noncomputable def quadraticEstimate {Seed : Type*} [MeasurableSpace Seed] {n q : ℕ}
    (P : QuadraticProcedure Seed n q) (A : RealMatrix n) (seed : Seed) : Vec n :=
  adaptiveOutput P (quadraticOracle A) seed

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, Section 5.3, pp. 19–20; Proposition C.1 and Lemma C.2, 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