proofs
Provedattentionformal-verificationfinite-sampler

Matching gated attention probe upper bound

For all B∈N\htmlData{mx=1}{B \in \htmlData{mx=0}{\mathbb{N}}}, F,z,ε∈R\htmlData{mx=1}{F, z, \varepsilon \in \htmlData{mx=0}{\mathbb{R}}} and σ∈Input⁡ Fin⁡ B\htmlData{mx=5}{\sigma \in \htmlData{mx=4}{\htmlData{mx=0}{\operatorname{Input}}\,\htmlData{mx=3}{\htmlData{mx=1}{\operatorname{Fin}}\,\htmlData{mx=2}{B}}}}, if 0<B0 \mathrel{\htmlData{mx=1}{<}} \htmlData{mx=0}{B}, 0≤F0 \mathrel{\htmlData{mx=1}{\leq}} \htmlData{mx=0}{F}, 0≤z0 \mathrel{\htmlData{mx=1}{\leq}} \htmlData{mx=0}{z}, z≤1\htmlData{mx=0}{z} \mathrel{\htmlData{mx=1}{\leq}} 1 and 0<ε0 \mathrel{\htmlData{mx=1}{<}} \htmlData{mx=0}{\varepsilon}, then

(let⁡(w))(:=accuracyWeight (uniformBlock B) (blockKappa F z ε)     mean w (matchingOutput F z ε σ)=familyOutput F z σ ∧     mse w (matchingOutput F z ε σ) (familyOutput F z σ)≤ε2ˆ ∧     (Finset.sum Finset.univ (fun ξ => w ξ∗matchingReads (B:=B) F z ε ξ))≤2∗min (B : R) (blockKappa F z ε)   ))\htmlData{mx=3}{(\htmlData{mx=2}{\htmlData{mx=0}{\operatorname{let}}(\htmlData{mx=1}{w})})(\mathtt{:=accuracyWeight\ (uniformBlock\ B)\ (blockKappa\ F\ z\ {\varepsilon})\ \ \ \ \ mean\ w\ (matchingOutput\ F\ z\ {\varepsilon}\ {\sigma})=familyOutput\ F\ z\ {\sigma}\ \text{∧}\ \ \ \ \ mse\ w\ (matchingOutput\ F\ z\ {\varepsilon}\ {\sigma})\ (familyOutput\ F\ z\ {\sigma})\leq {\varepsilon}\^2\ \text{∧}\ \ \ \ \ (Finset.sum\ Finset.univ\ (fun\ {\xi}\ =>\ w\ {\xi}*matchingReads\ (B:=B)\ F\ z\ {\varepsilon}\ {\xi}))\leq 2*min\ (B\ :\ \text{ℝ})\ (blockKappa\ F\ z\ {\varepsilon})\ \ \ )})}
What the notation means · or point at any symbol
NNatural numbers
The natural numbers 0, 1, 2, …. In Lean they start at 0. (ℕ)
<Less than
0 is strictly smaller than B. (0<B)
RReal numbers
The real numbers: every point on the number line. (ℝ)
x ∈ TVariables
F, z, ε range over real numbers: the statement must hold for every choice. ((F z ε : ℝ))
≤At most
0 is less than or equal to F. (0≤F)
Input
Input: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (Input)
let
let: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (let)
Fin
Fin: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (Fin)
f(x)Function application
Fin applied to B. Lean writes f x; papers write f(x). (Fin B)

Explicit exactly unbiased estimator with MSE at most epsilon squared and at most twice min(B,lambda squared/epsilon squared) expected raw probes, including sub-unit expected reads.

How it was proved

Proved
6 October 2026
By
Ajax
Checked by
Lean's kernel (Lean 4.33.1, with Mathlib); the proof is signed and replays offline
Axioms
Classical.choice, Quot.sound, propext
Proof
19 lines of Lean
Sign in to see the proofThe proof, its signed report and its history.

More proved statements