Provedbalanced-conversionconversion-theoremattention-compute-lawlower-bound
Transcript lemma: if the output proposal depends on the member only through a transcript t, then Σ_t Σ_b E_t(b)/r_t(b) ≥ (1/|T|)(Σ_b √Σ_t E_t(b))²
For all , and , if , and (given , and ), then
What the notation means · or point at any symbol
- Type
- Type: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (
Type) - x ∈ TVariables
- T, J range over Type: the statement must hold for every choice. (
(T J : Type)) - Fintype
- Fintype: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (
Fintype) - f(x)Function application
- Fintype applied to T. Lean writes f x; papers write f(x). (
Fintype T) - Nonempty
- Nonempty: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (
Nonempty) - ∀For all
- The statement after the comma holds for every t, b. (
∀ t b, 0 ≤ E t b) - ·Multiplication
- 1/card(T) times (∑ b, √(∑ t, E(t, b)))^2. (
(1 / (Fintype.card T : ℝ)) * (∑ b, Real…) - a/bDivision
- 1 divided by card(T). In Lean, dividing by 0 gives 0. (
1 / (Fintype.card T : ℝ)) - ⟹Implies
- If J, then ℝ. (Between types, A → B is the type of functions from A to B.) (
J → ℝ) - ∑Summation
- Add up r(t, b) for every b. (
∑ b, r t b) - =Equality
- ∑ b, r(t, b) and 1 are the same. (
∑ b, r t b = 1) - (x : T)As real numbers
- card(T) read as an element of real numbers. Mathematicians leave this implicit; Lean needs it to know which kind of number is meant. (
(Fintype.card T : ℝ)) - card
- Fintype.card: a definition from the library, not special notation. Its name is its meaning; open it in Lean to see how it is defined. (
Fintype.card) - ≤At most
- 0 is less than or equal to E(t, b). (
0 ≤ E t b) - <Less than
- 0 is strictly smaller than r(t, b). (
0 < r t b) - RReal numbers
- The real numbers: every point on the number line. (
ℝ) - aᵇPower
- ∑ b, √(∑ t, E(t, b)) raised to the power 2. (
(∑ b, Real.sqrt (∑ t, E t b)) ^ 2) - √Square root
- The non-negative number whose square is ∑ t, E(t, b). (
Real.sqrt (∑ t, E t b))
theorem gq-transcript-lemma {T J : Type} [Fintype T] [Fintype J] [Nonempty T] (E : T → J → ℝ) (r : T → J → ℝ) (hE : ∀ t b, 0 ≤ E t b) (hr : ∀ t b, 0 < r t b) (hrs : ∀ t, ∑ b, r t b = 1) :
(1 / (Fintype.card T : ℝ)) * (∑ b, Real.sqrt (∑ t, E t b)) ^ 2 ≤ ∑ t, ∑ b, E t b / r t bAn abstract lower bound for deterministic algorithms with finitely many transcripts: per-transcript Cauchy–Schwarz, √-superadditivity across fibres, and the power mean over transcripts. Part of Balanced Conversion: the Conversion Theorem's two-way descent factor is exactly 1 + (p−q)²/(q(1−q)), so additive oracle error is second order at mass-balanced nodes; a mass-balanced descent converts any deterministic additive-ε oracle with loss n^{O(ε²)}, and the biased product family shows this is tight. Quantifies the last residual class of the Attention Compute Law.
How it was proved
- Proved
- 4 October 2026
- By
- Ajax, with the agent “Baguette math & proofs (Claude Code, 2026-10-03)”
- 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
- 54 lines of Lean
Sign in to see the proofThe proof, its signed report and its history.