Theorem 1 — a total on bits with , ,
ProvedRvsCert.theorem_1boolean-functionsp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-algorithmsquery-complexity
There are constants , and such that for every there is a total Boolean function with
- ,
- ,
- , and
- ,
where is the certificate complexity and , are the bounded-error (error on every input) randomized and quantum query complexities. In particular and , answering the question whether a total function can have .
Formalization Note and take values in ; each upper bound is stated as the existence of a natural number with (resp. ) satisfying the bound.
Differences from the source:
- reading: N = Õ(n³), C(f) = Ω(n²), R(f) = Õ(n), Q(f) = Õ(√n) for all n > 0 → ∃ A, c > 0, k before n with N ≤ A·n³·(log₂ n+1)^k, c·n² ≤ C f, R, Q ≤ A·n·(log₂ n+1)^k, A·√n·(log₂ n+1)^k; reason: asymptotic notation over the family in n is uniform; the +1 keeps the polylog factor positive at n = 1; a common A and k for the three Õ bounds is equivalent (take the maximum)
- encoding: f : {0,1}^N → {0,1}; R(f), Q(f) → f : (Fin N → Bool) → Bool; randQC, quantQC in ℕ∞ stated as ∃ T : ℕ, … ≤ T ∧ T ≤ …; reason: Lean convention; same instances
Preamble
import Mathlib import Definitions.Def_RvsCert_C import Definitions.Def_RvsCert_randQC import Definitions.Def_RvsCert_quantQC
Formal statement
namespace RvsCert
/-- **Theorem 1** (p.1 of Ben-David–Kothari, *Randomized query complexity can beat certificate complexity*, arXiv:2609.15063v1): "For all n > 0, there is a total Boolean
function f : {0, 1}^N → {0, 1} with N = Õ(n³), such that C(f) = Ω(n²), R(f) = Õ(n), and
Q(f) = Õ(√n)." There are constants `A`, `c > 0` and `k` such that for every `n > 0` there are
`N` and a total `f : (Fin N → Bool) → Bool` with `N ≤ A·n³·(log₂ n + 1)^k`, `C(f) ≥ c·n²`,
`R(f) ≤ A·n·(log₂ n + 1)^k` and `Q(f) ≤ A·√n·(log₂ n + 1)^k`.
**Formalization Note.** `R` and `Q` are bounded-error (`1/3` on every input) worst-case query
complexities in `ℕ∞`, stated as `∃ T : ℕ, … ≤ T ∧ T ≤ …`; `Õ(g)` is read as
`≤ A·g·(log₂ n + 1)^k` with constants chosen before `n`. -/
theorem theorem_1 :
∃ (A c : ℝ) (k : ℕ), 0 < c ∧ ∀ n : ℕ, 0 < n →
∃ (N : ℕ) (f : (Fin N → Bool) → Bool),
(N : ℝ) ≤ A * (n : ℝ) ^ 3 * (Real.logb 2 n + 1) ^ k ∧
c * (n : ℝ) ^ 2 ≤ (C f : ℝ) ∧
(∃ T : ℕ, randQC f ≤ T ∧ (T : ℝ) ≤ A * (n : ℝ) * (Real.logb 2 n + 1) ^ k) ∧
(∃ T : ℕ, quantQC f ≤ T ∧ (T : ℝ) ≤ A * Real.sqrt n * (Real.logb 2 n + 1) ^ k) := by sorry
end RvsCert
Source
Ben-David–Kothari, Randomized query complexity can beat certificate complexity, arXiv:2609.15063v1, Theorem 1, p.1
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.