Theorem 6 — -local cell-probe samplers are at distance from a Hamming slice
OpenSamplingAC0.Supplement.theorem_6There are absolute constants with the following property. Let and let satisfy ; let be the uniform distribution on the strings in of Hamming weight . Let and let be -local, i.e. each output bit depends on at most of the input cells, each cell holding an element of . Then, for uniform on ,
The constants do not depend on , , , or .
Since a cell holds bits, the theorem shows that non-adaptive cell-probe samplers, and hence non-adaptive succinct membership data structures for -subsets of , need logarithmic redundancy.
Formalization Note The exponent is , as printed (the is a superscript of ). Locality counts input cells, and the number of cells is arbitrary. The typeclass assumption makes carry a uniform distribution; it follows from .
Differences from the source:
- reading: with unspecified base → ; reason: base 2 is the paper's convention (p.15 "logarithms in base two"); a different base changes by a constant factor, which the constants absorb for
- encoding: → together with the typeclass assumption ; reason: follows from and only lets Lean form the uniform distribution on
import Mathlib import Definitions.Def_SamplingAC0_tvDist import Definitions.Def_SamplingAC0_Supplement_IsLocal import Definitions.Def_SamplingAC0_Supplement_cellLaw import Definitions.Def_SamplingAC0_Supplement_slice set_option autoImplicit false
namespace SamplingAC0.Supplement
/-- **Theorem 6 (Hamming slices against non-adaptive cell probes).** Riazanov–Viola, *Sampling
Tools and the Power of AC0*, STOC 2027 submission (manuscript sha256 99c33d30…), Theorem 6, p.4
(proof §6, pp.16–20): "Let D ∼ ([n] choose k) where n ≥ c and 0.1n ≤ k ≤ 0.9n. Let
f : [n]^s → {0, 1}^n be a d-local function. Then ∆(f(U), D) ≥ 1 − log^{c^d} n / √n."
**Formalization Note.**
* c-notation (p.2): the two occurrences of `c` are absolute positive constants `c₁` (in `n ≥ c₁`)
and `c₂` (the base of the exponent `c₂^d`), chosen before `n`, `k`, `s`, `d` and `f`; neither
depends on `d`. The exponent is `c^d` (the `d` is a superscript of `c` on the page, and the proof,
p.20, bounds `t ≤ (A log n)^{C^d}`).
* The input is `s` cells with values in `[n] = Fin n` (cells of `log n` bits); `U` is uniform on
`[n]^s`; `d`-locality counts input cells (`IsLocal` over the alphabet `Fin n`). `s` and `d` are
arbitrary naturals.
* `n ≠ 0` is a typeclass argument so that `[n]^s` carries a uniform distribution; it follows from
`n ≥ c₁ > 0`.
* `log` is base 2. `0.1n ≤ k ≤ 0.9n` is compared over the reals. -/
theorem theorem_6 :
∃ c₁ c₂ : ℝ, 0 < c₁ ∧ 0 < c₂ ∧
∀ (n : ℕ) [NeZero n], c₁ ≤ (n : ℝ) →
∀ k : ℕ, (0.1 : ℝ) * n ≤ k → (k : ℝ) ≤ (0.9 : ℝ) * n →
∀ (s d : ℕ) (f : (Fin s → Fin n) → (Fin n → Bool)), IsLocal d f →
1 - Real.logb 2 n ^ (c₂ ^ d) / Real.sqrt n ≤
SamplingAC0.tvDist (cellLaw f) (slice n k) := by sorry
end SamplingAC0.Supplement