Lemma 3 —
ProvedRvsCert.lemma_3boolean-functionsp2o-gran-per-chapterp2o-plan-paperp2o-v1query-complexity
Let be the champion function. There is a constant such that for every there is a natural number with
where is the bounded-error randomized query complexity (error at most on every input, worst-case number of bit queries).
Differences from the source:
- encoding: the function f on (X, Y) with numbers in log n bits → the bit layout
Idx nwith fixed widths wX n = ⌈log₂(2n²+1)⌉, wY n = ⌊log₂ n⌋+1, ⊥ = 0, athlete (c,b) = 1+cn+b, 0-based positions, card entry j for the j-th opponent in increasing order; reason: the paper fixes only O(log n)-bit numbers; this is one such injective encoding - reading: R(f) = O(n log n) → ∃ T : ℕ, randQC f_n ≤ T ∧ T ≤ A·n·(log₂ n + 1), for all n > 0; reason: asymptotic notation over the family in n, constants chosen before n; the +1 keeps the log factor positive at n = 1
- encoding: R(f), bounded-error randomized query complexity → randQC, an infimum in ℕ∞ with success probability ≥ 2/3 on every input and worst-case query count; reason: the standard [BdW02] notion; ℕ∞ keeps the bound non-vacuous
Preamble
import Mathlib import Definitions.Def_RvsCert_champion import Definitions.Def_RvsCert_randQC
Formal statement
namespace RvsCert
/-- **Lemma 3** (p.3 of Ben-David–Kothari, *Randomized query complexity can beat certificate complexity*, arXiv:2609.15063v1): "There is a fast randomized algorithm:
R(f) = O(n log n)." There is a constant `A` such that for every `n > 0` the bounded-error
(error `1/3` on every input) randomized query complexity of `champion n`, counted in bit
queries, is at most `A·n·(log₂ n + 1)`.
**Formalization Note.** The upper bound is stated as `∃ T : ℕ, randQC f ≤ T ∧ T ≤ …`, so an
infeasible (`⊤`) value is excluded; `A` is chosen before `n`. -/
theorem lemma_3 :
∃ A : ℝ, ∀ n : ℕ, 0 < n → ∃ T : ℕ, randQC (champion n) ≤ T ∧
(T : ℝ) ≤ A * (n : ℝ) * (Real.logb 2 n + 1) := by sorry
end RvsCert
Source
Ben-David–Kothari, Randomized query complexity can beat certificate complexity, arXiv:2609.15063v1, Lemma 3, p.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.