proofs
Provedunbiased-attentionrandomized-algorithmssoftmaxhardness

Union bound: k ≥ log(3n)/log(8/7) runs make n·(7/8)^k ≤ 1/3

For all n∈N\htmlData{mx=1}{n \in \htmlData{mx=0}{\mathbb{N}}} and k∈N\htmlData{mx=1}{k \in \htmlData{mx=0}{\mathbb{N}}}, if 0<n0 \mathrel{\htmlData{mx=1}{<}} \htmlData{mx=0}{n} and log⁡(3n)log⁡(87)≤k\htmlData{mx=5}{\frac{\htmlData{mx=2}{\log (\htmlData{mx=1}{3\htmlData{mx=0}{n}})}}{\htmlData{mx=4}{\log \left(\htmlData{mx=3}{\frac{8}{7}}\right)}}} \mathrel{\htmlData{mx=7}{\leq}} \htmlData{mx=6}{k}, then

n⋅78k≤13\htmlData{mx=6}{\htmlData{mx=1}{\htmlData{mx=0}{n}} \cdot \htmlData{mx=5}{\htmlData{mx=3}{\htmlData{mx=2}{\frac{7}{8}}}^{\htmlData{mx=4}{k}}}} \mathrel{\htmlData{mx=8}{\leq}} \htmlData{mx=7}{\frac{1}{3}}
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 n. (0 < n)
logNatural logarithm
The logarithm of 3 · n to base e: the power e must be raised to to give 3 · n. (Real.log (3 * n))
≤At most
log(3 · n)/log(8/7) is less than or equal to k. (Real.log (3 * n) / Real.log (8 / 7) ≤ k)
(x : T)As real numbers
n read as an element of real numbers. Mathematicians leave this implicit; Lean needs it to know which kind of number is meant. ((n : ℝ))
·Multiplication
3 times n. (3 * n)
aᵇPower
7/8 raised to the power k. ((7 / 8 : ℝ) ^ k)
a/bDivision
8 divided by 7. In Lean, dividing by 0 gives 0. (8 / 7)

With this many independent repetitions every one of the n rows is decided correctly simultaneously with probability ≥ 2/3, completing the reduction from Gap-MaxIP to constant-MSE attention. Part of 'Unbiased randomized attention: cost x variance thresholds', round 4 (amplification made formal).

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

More proved statements