Lemma 2 (second part) —
ProvedRvsCert.lemma_2_uc1boolean-functionsp2o-gran-per-chapterp2o-plan-paperp2o-v1query-complexity
Let be the champion function with parameter . There is a constant such that for every ,
Certificate sizes count input bits.
The bound on is the verification step of Lemmas 3 and 5, and together with Lemma 4 it separates from .
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: UC1(f) = O(n log n) → UC1(f_n) ≤ 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
Preamble
import Mathlib import Definitions.Def_RvsCert_champion import Definitions.Def_RvsCert_C1 import Definitions.Def_RvsCert_UC1
Formal statement
namespace RvsCert
/-- **Lemma 2, second sentence** (p.2 of Ben-David–Kothari, *Randomized query complexity can beat certificate complexity*, arXiv:2609.15063v1): "C1(f) ≤ UC1(f) = O(n log n)."
There is a constant `A` such that for every `n > 0`, `C1(f_n) ≤ UC1(f_n)` and
`UC1(f_n) ≤ A·n·(log₂ n + 1)`, where `f_n = champion n`.
**Formalization Note.** `O(n log n)` is read with `log₂ n + 1` (positive at `n = 1`), uniform
in `n`. Sizes count bits. -/
theorem lemma_2_uc1 :
∃ A : ℝ, ∀ n : ℕ, 0 < n →
C1 (champion n) ≤ UC1 (champion n) ∧
(UC1 (champion n) : ℝ) ≤ 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 2, p.2
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.