Proof of Lemma 4 — the all- input has no certificate of bits
ProvedRvsCert.lemma_4_hard_inputboolean-functionsp2o-gran-per-chapterp2o-plan-paperp2o-v1query-complexity
Let and let be the input whose race lists are filled with and whose proposal cards are filled with (in the binary encoding, the all-zero bit string). Then , and every certificate for reveals more than bits:
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: any certificate that exhibits n²/2 bits of this input cannot certify that f(X,Y) = 0 → every certificate S of x₀ has |S| > n²/2; reason: a certificate of at most n²/2 bits is excluded; a subset of a non-certificate is a non-certificate, so 'exactly' and 'at most' n²/2 bits say the same
Preamble
import Mathlib import Definitions.Def_RvsCert_champion import Definitions.Def_RvsCert_IsCertificate
Formal statement
namespace RvsCert
/-- **Proof of Lemma 4, the hard 0-input** (p.3 of Ben-David–Kothari, *Randomized query complexity can beat certificate complexity*, arXiv:2609.15063v1): "Consider the input
(X, Y) where the X lists for each race are filled with ⊥ and the Y lists for each athlete are
filled with 0. This is clearly an input with f(X, Y) = 0. … Any certificate that exhibits n²/2
bits of this input cannot certify that f(X, Y) = 0." In the binary encoding this is the all-false
input; `champion n` is `false` on it, and every certificate for it has more than `n²/2` bits. -/
theorem lemma_4_hard_input (n : ℕ) (hn : 0 < n) :
champion n (fun _ => false) = false ∧
∀ S : Finset (Idx n), IsCertificate (champion n) (fun _ => false) S →
(n : ℝ) ^ 2 / 2 < S.card := by sorry
end RvsCert
Source
Ben-David–Kothari, Randomized query complexity can beat certificate complexity, arXiv:2609.15063v1, proof of Lemma 4, p.3
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.