Lemma 4 —
ProvedRvsCert.lemma_4boolean-functionsp2o-gran-per-chapterp2o-plan-paperp2o-v1query-complexity
Let be the champion function. There is a constant such that for every ,
Since , this gives the certificate lower bound of Theorem 1.
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: C0(f) = Ω(n²) → ∃ c > 0, ∀ n > 0, c·n² ≤ C0(f_n); reason: asymptotic notation over the family, constant chosen before n
Preamble
import Mathlib import Definitions.Def_RvsCert_champion import Definitions.Def_RvsCert_C0
Formal statement
namespace RvsCert
/-- **Lemma 4** (p.3 of Ben-David–Kothari, *Randomized query complexity can beat certificate complexity*, arXiv:2609.15063v1): "There are no short 0-certificates:
C0(f) = Ω(n²)." There is a constant `c > 0` with `c·n² ≤ C0(champion n)` for every `n > 0`. -/
theorem lemma_4 :
∃ c : ℝ, 0 < c ∧ ∀ n : ℕ, 0 < n → c * (n : ℝ) ^ 2 ≤ (C0 (champion n) : ℝ) := by sorry
end RvsCert
Source
Ben-David–Kothari, Randomized query complexity can beat certificate complexity, arXiv:2609.15063v1, Lemma 4, p.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.