2019/09/26 by Naomi Kirshner, Kirshner, Naomi, Alex Samorodnitsky +1 · 2 citations
Computer Science · Mathematics · #Coding theory and cryptography #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Information Theory (cs.IT) #Mathematical Approximation and Integration
paper · pdf · doi:10.48550/arxiv.1909.11929
openalex publication_date 2019/09/26 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let p \≥ 2. We improve the bound \(\‖f\‖p)/(\‖f\‖2) \≤ (p-1)s/2\nfor a polynomial f of degree s on the boolean cube 0,1 n, which comes\nfrom hypercontractivity, replacing the right hand side of this inequality by an\nexplicit bivariate function of p and s, which is smaller than (p-1)s/2\nfor any p > 2 and s > 0. We show the new bound to be tight, within a\nsmaller order factor, for the Krawchouk polynomial of degree s.\n This implies several nearly-extremal properties of Krawchouk polynomials and\nHamming spheres (equivalently, Hamming balls). In particular, Krawchouk\npolynomials have (almost) the heaviest tails among all polynomials of the same\ndegree and \ℓ2 norm (this has to be interpreted with some care). The\nHamming spheres have the following approximate edge-isoperimetric property: For\nall 1 \≤ s \≤ \(n)/(2), and for all even distances 0 \≤ i \≤\n\(2s(n-s))/(n), the Hamming sphere of radius s contains, up to a\nmultiplicative factor of O(i), as many pairs of points at distance i as\npossible, among sets of the same size (there is a similar, but slightly weaker\nand somewhat more complicated claim for general distances). This also implies\nthat Hamming spheres are (almost) stablest with respect to noise among sets of\nthe same size. In coding theory terms this means that a Hamming sphere\n(equivalently a Hamming ball) has the maximal probability of undetected error,\namong all binary codes of the same rate.\n We also describe a family of hypercontractive inequalities for functions on\n 0,1 n, which improve on the `usual' "q \→ 2" inequality by\ntaking into account the concentration of a function (expressed as the ratio\nbetween its \ℓr norms), and which are nearly tight for characteristic\nfunctions of Hamming spheres.\n