Finite entropy tail estimate for the punctured-ball Fourier transform
OpenSaglamGV.muHat_tail_kscoding-theoryentropyfourier-analysisgilbert-varshamov-bound
Let , , be integers, , and . Suppose
For the uniform kernel on the punctured Hamming ball of radius , of size , the unnormalized Fourier transform satisfies
Probabilities are uniform on and include . This is a finite-parameter tail bound that can be applied at any admissible integral cutoff.
Formalization Note. Appendix A's KS threshold is bounded above by using the binomial volume estimate and the displayed bound on . The strict event above is therefore contained in the source's non-strict threshold event; this is a weakening of that bound.
Preamble
import Mathlib import Definitions.Def_SaglamGV_Fourier import Definitions.Def_SaglamGV_Analytic import Definitions.Def_SelectiveDPT_H2
Formal statement
theorem SaglamGV.muHat_tail_ks (n w k : ℕ) (hn : 2 ≤ n) (hw : 1 ≤ w)
(hwn : 2 * w ≤ n)
(hk : (k : ℝ) / n ≤ 1 / 2 -
Real.sqrt (((w : ℝ) / n) * (1 - (w : ℝ) / n))) :
SaglamGV.probY (fun y ↦ Real.sqrt ((n : ℝ) + 1) *
Real.exp (-2 * w * ((k : ℝ) / n)) < |SaglamGV.muHat n (w + 1) y|) ≤
(2 : ℝ) ^ ((n : ℝ) * (SelectiveDPT.H2 ((k : ℝ) / n) - 1)) := 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.