Numerical cutoff estimates for the Hamming-ball entropy tail
ProvedSaglamGV.ks_tail_cutoffcoding-theoryentropyfourier-analysisgilbert-varshamov-bound
Fix . There are and an integer such that, whenever and , the integers and real numbers
satisfy all three estimates
Logarithms denoted by are base two, and is binary entropy in bits. This purely numerical lemma separates the rounding and entropy estimates from the spectral theorem in Appendix A.
Formalization Note. The cutoff is exactly the rounded cutoff used on p.7. The asymptotic regime is expressed uniformly by , matching the parent milestone. The natural-number ceiling agrees with the ordinary ceiling on this positive range.
Preamble
import Mathlib import Definitions.Def_SaglamGV_Fourier import Definitions.Def_SaglamGV_Analytic import Definitions.Def_SelectiveDPT_H2
Formal statement
theorem SaglamGV.ks_tail_cutoff (ε : ℝ) (hε : 0 < ε) :
∃ L : ℝ, 0 < L ∧ ∃ N₀ : ℕ, 2 ≤ N₀ ∧
∀ n w : ℕ, N₀ ≤ n → L * Real.logb 2 n ≤ w →
(w : ℝ) ≤ (1 / 2 - ε) * n →
let k : ℕ := ⌈(n : ℝ) * Real.logb 2 n / w⌉₊
(k : ℝ) / n ≤ 1 / 2 -
Real.sqrt (((w : ℝ) / n) * (1 - (w : ℝ) / n)) ∧
Real.sqrt ((n : ℝ) + 1) * Real.exp (-2 * w * ((k : ℝ) / n)) ≤
1 / (n : ℝ) ∧
(n : ℝ) * (SelectiveDPT.H2 ((k : ℝ) / n) - 1) ≤
-(n : ℝ) + 2 * n * Real.logb 2 n / w *
Real.logb 2 (Real.exp 1 * w / Real.logb 2 n) := by sorrySource
M. Saglam, Linear codes exceeding the Gilbert–Varshamov bound, STOC 2027 submission manuscript (held version sha256 ac6f2bba913aa15cfec8dda07a8e9e37b7186e145fef4719cb623dd04d15baa3), Appendix A, pp.6–7; https://mnsaglam.com/papers/linear-codes.pdf. Uses Kirshner–Samorodnitsky, IEEE Trans. Inf. Theory 67.6 (2021), Corollary 1.4 and Theorem 1.5, doi:10.1109/TIT.2021.3071597.