Hypercontractive inequalities are a useful tool in dealing with extremal questions in the geometry of high-dimensional discrete and continuous spaces. In this survey we trace a few connections between different manifestations of hypercontractivity, and also present some relatively recent applications of these techniques in computer science.
1. Preliminaries and notation
Fourier analysis on the hypercube. We define the inner product on functions , where the expectation is taken over the uniform (counting) measure on . The multilinear polynomials (where ranges over subsets of ) form an orthogonal basis under this inner product; they are called the Fourier basis. Thus, for any function , we have , where the Fourier coefficients obey Plancherel’s relation . It is easy to verify that and .
Norms. For , define the norm . These norms are monotone in : for every function , implies . For a linear operator carrying functions to functions , we define the -to- operator norm . is said to be a contraction from to when . Because of the monotonicity of norms, a contraction from to is automatically a contraction from to for any . When and , then is said to be hypercontractive.
Convolution operators. Letting represent the coordinatewise product of , we define the convolution of two functions , and note that it is a linear operator for every fixed . Convolution is commutative and associative, and the Fourier coefficients of a convolution satisfy the useful property . We shall be particularly interested in the convolution properties of the following functions
- The Dirac delta , given by and otherwise. It is the identity for convolution and has for all .
- The edge functions given by
is or according as contains or does not contain , respectively. For any function , , where is obtained from by flipping just the th bit. Convolution with acts as an orthogonal projection (as we can easily see in the Fourier domain), so for any functions , we have
- The Bonami-Gross-Beckner noise functions for , where and we define . These operators form a semigroup, because and . Note that . We define the noise operator acting on functions on the discrete cube by . In combinatorial terms, is the expected value of , where is obtained from by independently flipping each bit of with probability .