G.3 Part 1, p. 51 — Varshamov–Gilbert packing Σ ⊂ {−1, 1}^{d/2} with |Σ| ≥ 2^{d/16} and pairwise Hamming distance ≥ d/16
ProvedOfflineCMC.Minimax.varshamov_gilbertcoding-theorycombinatoricsminimax-lower-boundp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1
Let be even. There is a set with
This is the packing of the sign cube from which the hard subclass of the minimax lower bound is built. Two members of then differ by at least in the -norm.
Formalization Note Sign vectors are maps Fin (d / 2) → ℤˣ.
Differences from the source:
- reading: → ; reason: is an integer only when , and when it is, a larger packing contains one of exactly that size
- generalization: even (the hypothesis of Part 1) → even; reason: covers as well
Preamble
import Mathlib
Formal statement
namespace OfflineCMC.Minimax
theorem varshamov_gilbert (d : ℕ) (hd : Even d) (hd2 : 2 ≤ d) :
∃ S : Finset (Fin (d / 2) → ℤˣ), (2 : ℝ) ^ ((d : ℝ) / 16) ≤ (S.card : ℝ) ∧
∀ σ ∈ S, ∀ σ' ∈ S, σ ≠ σ' →
(d : ℝ) / 16 ≤ ((Finset.univ.filter (fun i => σ i ≠ σ' i)).card : ℝ) := by sorry
end OfflineCMC.Minimax
Source
Banerjee, Honnappa & Rao, Offline Estimation of Controlled Markov Chains: Minimaxity and Sample Complexity, arXiv:2211.07092v5, p. 51, App. G.3 Part 1 (citing Varshamov–Gilbert, [64, Theorem 5.1.7])
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.