proofs
Provedunbiased-attentionrandomized-algorithmssoftmaxfull-exponent

Gadget range: log(4n / n^{1−α}) = log 4 + α log n

For all n,α∈R\htmlData{mx=1}{n, \alpha \in \htmlData{mx=0}{\mathbb{R}}}, if 0<n0 \mathrel{\htmlData{mx=1}{<}} \htmlData{mx=0}{n}, then

log⁡(4nn1−α)=log⁡4+α⋅log⁡n\htmlData{mx=7}{\log \left(\htmlData{mx=6}{\frac{\htmlData{mx=1}{4\htmlData{mx=0}{n}}}{\htmlData{mx=5}{\htmlData{mx=2}{n}^{\htmlData{mx=4}{1 - \htmlData{mx=3}{\alpha}}}}}}\right)} \mathrel{\htmlData{mx=14}{=}} \htmlData{mx=13}{\htmlData{mx=8}{\log 4} + \htmlData{mx=12}{\htmlData{mx=9}{\alpha} \cdot \htmlData{mx=11}{\log \htmlData{mx=10}{n}}}}
What the notation means · or point at any symbol
RReal numbers
The real numbers: every point on the number line. (ℝ)
x ∈ TVariables
n, α range over real numbers: the statement must hold for every choice. ((n α : ℝ))
<Less than
0 is strictly smaller than n. (0 < n)
logNatural logarithm
The logarithm of 4 · n/n^(1 − α) to base e: the power e must be raised to to give 4 · n/n^(1 − α). (Real.log (4 * n / n ^ (1 - α)))
=Equality
log(4 · n/n^(1 − α)) and log(4) + α · log(n) are the same. (Real.log (4 * n / n ^ (1 - α)) = Real.l…)
·Multiplication
4 times n. (4 * n)
a/bDivision
4 · n divided by n^(1 − α). In Lean, dividing by 0 gives 0. (4 * n / n ^ (1 - α))
aᵇPower
n raised to the power 1 − α. (n ^ (1 - α))
-Subtraction
1 minus α. On ℕ, Lean's subtraction stops at 0: 2 − 5 = 0. (1 - α)
+Addition
log(4) plus α · log(n). (Real.log 4 + α * Real.log n)

So the multiplicity gadget's score range is (α ln n + ln 4)/(1−s), which tensor-power soundness amplification pushes to just above α ln n. Part of 'Unbiased randomized attention: cost x variance thresholds', round 12 (full exponent: multiplicity gadget for α < 1).

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
13 lines of Lean
Sign in to see the proofThe proof, its signed report and its history.

More proved statements