2013/09/12 by Polyanskiy, Yury
#Combinatorics (math.CO) #FOS: Computer and information sciences #FOS: Mathematics #Functional Analysis (math.FA) #Information Theory (cs.IT) #Probability (math.PR)
paper · doi:10.48550/arxiv.1309.3014
Consider the linear space of functions on the binary hypercube and the linear operator Sδ acting by averaging a function over a Hamming sphere of radius δn around every point. It is shown that this operator has a dimension-independent bound on the norm Lp → L2 with p = 1+(1-2δ)2. This result evidently parallels a classical estimate of Bonami and Gross for Lp → Lq norms for the operator of convolution with a Bernoulli noise. The estimate for Sδ is harder to obtain since the latter is neither a part of a semigroup, nor a tensor power. The result is shown by a detailed study of the eigenvalues of Sδ and Lp→ L2 norms of the Fourier multiplier operators Πa with symbol equal to a characteristic function of the Hamming sphere of radius a (in the notation common in boolean analysis Πa f=f=a, where f=a is a degree-a component of function f). A sample application of the result is given: Any set A⊂ \FF2n with the property that A+A contains a large portion of some Hamming sphere (counted with multiplicity) must have cardinality a constant multiple of 2n.