§9.4: Two-function hypercontractivity and induction

At this point we have established that if $f : \{-1,1\} \to {\mathbb R}$ then for any $p \leq 2 \leq q$, \[ \|\mathrm{T}_{\sqrt{p-1}} f\|_2 \leq \|f\|_p, \qquad \|\mathrm{T}_{1/\sqrt{q-1}} f\|_q \leq \|f\|_2. \] We would like to extend these facts to the case of general $f : \{-1,1\}^n \to {\mathbb R}$; i.e., establish the $(p,2)$- and $(2,q)$-Hypercontractivity Theorems stated at the beginning of the chapter. A natural approach is induction.

In analysis of boolean functions, there are two methods for proving statements about $f : \{-1,1\}^n \to {\mathbb R}$ by induction on $n$. One method, which might be called “induction by derivatives”, uses the decomposition $f(x) = x_n \mathrm{D}_nf(x) + \mathrm{E}_n f(x)$. We saw this approach in our inductive proof of the Bonami Lemma. The other method, which might be called “induction by restrictions”, goes via the subfunctions $f_{\pm 1}$ obtained by restricting the $n$th coordinate of $f$ to $\pm 1$. We saw this approach in our proof of the OSSS Inequality in Chapter 8.6. In both methods we reduce inductively from one function $f$ to two functions — either $\mathrm{D}_n f$ and $\mathrm{E}_n f$, or $f_{-1}$ and $f_{+1}$. Because of this, when trying to prove a fact by induction on $n$ it’s often helpful to try proving a generalized fact about two functions. Our proof of the OSSS Inequality gives a good example this technique.

So to facilitate induction, let’s find a two-function version of the hypercontractivity statements we’ve proven so far. Perhaps the most natural statement we’ve seen is the noise-stability rephrasing of the $(4/3,2)$-Hypercontractivity Theorem, namely $\mathbf{Stab}_{1/3}[f] \leq \|f\|_{4/3}^2$. At least in the case $n = 1$, our work in the previous section (Theorem 18) generalizes this to $\mathbf{Stab}_{p-1}[f] \leq \|f\|_{p}^2$ for $1 \leq p \leq 2$. I.e., \[ \mathbf{Stab}_\rho[f] = \mathop{\bf E}_{{\substack{({\boldsymbol{x}}, \boldsymbol{y}) \\ \text{ $\rho$-correlated}}}}[f({\boldsymbol{x}}) f(\boldsymbol{y})] \leq \|f\|_{1+\rho}^2 \] for $0 \leq \rho \leq 1$. Looking at this, you might naturally guess a (correct) generalization for two functions $f, g : \{-1,1\}^n \to {\mathbb R}$, namely \begin{equation} \label{eqn:two-fn-warmup} \mathop{\bf E}_{{\substack{({\boldsymbol{x}}, \boldsymbol{y}) \\ \text{ $\rho$-correlated}}}}[f({\boldsymbol{x}}) g(\boldsymbol{y})] \leq \|f\|_{1+\rho} \|g\|_{1+\rho}. \end{equation} We have a nice interpretation of this inequality when $f, g : \{-1,1\}^n \to \{0,1\}$ are indicators of subsets $A, B \subseteq \{-1,1\}^n$ as in Corollary 8; it gives an upper bound on the probability of going from $A$ to $B$ in one step on the $\rho$-stable hypercube graph. This bound is sharp when $A$ and $B$ have the same volume, but for $A$ and $B$ of different sizes you might imagine it’s helpful to measure $f$ and $g$ by different norms in \eqref{eqn:two-fn-warmup}. To see what we can expect, let’s break up the $\rho$-correlation in \eqref{eqn:two-fn-warmup} into two parts; say, write \[ \rho = \sqrt{rs}, \qquad 0 \leq r, s \leq 1, \] and use \[ \mathop{\bf E}_{{\substack{({\boldsymbol{x}}, \boldsymbol{y}) \\ \text{ $\sqrt{rs}$-correlated}}}}[f({\boldsymbol{x}}) g(\boldsymbol{y})] = \mathop{\bf E}[\mathrm{T}_{\sqrt{r}} f \cdot \mathrm{T}_{\sqrt{s}} g]. \] Then Cauchy–Schwarz implies \begin{equation} \label{eqn:two-function-n1} \mathop{\bf E}_{{\substack{({\boldsymbol{x}}, \boldsymbol{y}) \\ \text{ $\rho$-correlated}}}}[f({\boldsymbol{x}}) g(\boldsymbol{y})] = \mathop{\bf E}[\mathrm{T}_{\sqrt{r}} f \cdot \mathrm{T}_{\sqrt{s}} g] \leq \|\mathrm{T}_{\sqrt{r}} f\|_2 \|\mathrm{T}_{\sqrt{s}} g\|_2 \leq \|f\|_{1+r} \|g\|_{1+s}, \end{equation} where the last step used $(p,2)$-hypercontractivity — which we have so far only proven in the case $n = 1$ (Theorem 18). The inequality \eqref{eqn:two-function-n1}, restated below, is precisely the desired two-function version of the $(2,q)$- and $(p,2)$-Hypercontractive Theorems.

(Weak) Two-Function Hypercontractivity Theorem Let $f, g : \{-1,1\}^n \to {\mathbb R}$, let $0 \leq r, s \leq 1$, and assume $0 \leq \rho \leq \sqrt{rs} \leq 1$. Then \[ \mathop{\bf E}_{{\substack{({\boldsymbol{x}}, \boldsymbol{y}) \\ \text{ $\rho$-correlated}}}}[f({\boldsymbol{x}}) g(\boldsymbol{y})] \leq \|f\|_{1+r} \|g\|_{1+s}. \]

We call this the “Weak” Two-Function Hypercontractivity Theorem because the hypothesis $r, s \leq 1$ is not actually necessary (as we will show in Chapter 10). As mentioned, we have so far established this theorem in the case $n = 1$. However the beauty of hypercontractivity in this form is that it extends to general $n$ by an almost trivial induction. The form of the induction is “induction by restrictions”. (It’s also possible — but a little trickier — to extend the $(2,q)$-Hypercontractivity Theorem from $n = 1$ to general $n$ via “induction by derivatives”; see the exercises.) For future use, we will write the induction in more general notation.

Two-Function Hypercontractivity Induction Theorem Let $0 \leq \rho \leq 1$ and assume that \[ \mathop{\bf E}_{{\substack{({\boldsymbol{x}}, \boldsymbol{y}) \\ \text{ $\rho$-correlated}}}}[f({\boldsymbol{x}}) g(\boldsymbol{y})] \leq \|f\|_p \|g\|_q \] holds for every $f, g \in L^2(\Omega, \pi)$. Then the inequality also holds for every $f, g \in L^2(\Omega^n, \pi^{\otimes n})$.

Proof: The proof is by induction on $n$, with the $n = 1$ case holding by assumption. For $n > 1$, let $f, g \in L^2(\Omega^n, \pi^{\otimes n})$ and let $({\boldsymbol{x}}, \boldsymbol{y})$ denote a $\rho$-correlated pair under $\pi^{\otimes n}$. We’ll use the notation ${\boldsymbol{x}} = ({\boldsymbol{x}}’, {\boldsymbol{x}}_n)$ where ${\boldsymbol{x}}’ = ({\boldsymbol{x}}_1, \dots, {\boldsymbol{x}}_{n-1})$, and similar notation for $\boldsymbol{y}$. Note that $({\boldsymbol{x}}’, \boldsymbol{y}’)$ and $({\boldsymbol{x}}_n, \boldsymbol{y}_n)$ are both $\rho$-correlated pairs (of length $n-1$ and $1$, respectively). We’ll also write $f_{x_n} = f_{[n-1] \mid x_n}$ for the restriction of $f$ in which the last coordinate is fixed to value $x_n$, and similarly for $g$. Now \[ \mathop{\bf E}_{({\boldsymbol{x}}, \boldsymbol{y})}[f({\boldsymbol{x}}) g(\boldsymbol{y})] = \mathop{\bf E}_{({\boldsymbol{x}}_n, \boldsymbol{y}_n)} \mathop{\bf E}_{({\boldsymbol{x}}’, \boldsymbol{y}’)}[f_{{\boldsymbol{x}}_n}({\boldsymbol{x}}') g_{\boldsymbol{y}_n}(\boldsymbol{y}')] \leq \mathop{\bf E}_{({\boldsymbol{x}}_n, \boldsymbol{y}_n)}[\|f_{{\boldsymbol{x}}_n}\|_p \|g_{\boldsymbol{y}_n}\|_q] \] by induction. If we write $F \in L^2(\Omega, \pi)$ for the function $x_n \mapsto \|f_{x_n}\|_p$ and similarly write $G(y_n) = \|g_{y_n}\|_q$ then we may continue the above as \[ \mathop{\bf E}_{({\boldsymbol{x}}_n, \boldsymbol{y}_n)}[\|f_{{\boldsymbol{x}}_n}\|_p \|g_{\boldsymbol{y}_n}\|_q] = \mathop{\bf E}_{({\boldsymbol{x}}_n, \boldsymbol{y}_n)}[F({\boldsymbol{x}}_n) G(\boldsymbol{y}_n)] \leq \|F\|_{p, {\boldsymbol{x}}_n} \|G\|_{q, {\boldsymbol{x}}_n}, \] where we used the base case of the induction. Finally, \[ \|F\|_{p, {\boldsymbol{x}}_n} = \mathop{\bf E}_{{\boldsymbol{x}}_n}[|F({\boldsymbol{x}}_n)|^p]^{1/p} = \mathop{\bf E}_{{\boldsymbol{x}}_n}[\|f_{{\boldsymbol{x}}_n}\|_p^p]^{1/p} = \bigl(\mathop{\bf E}_{{\boldsymbol{x}}_n} \mathop{\bf E}_{{\boldsymbol{x}}’} |f_{{\boldsymbol{x}}_n}({\boldsymbol{x}}’)|^p]\bigr)^{1/p} = \|f\|_p \] by definition, and similarly for $\|G\|_{q,{\boldsymbol{x}}_n}$. Thus we have established $\mathop{\bf E}[f({\boldsymbol{x}})g(\boldsymbol{y})] \leq \|f\|_p\|g\|_q$, completing the induction. $\Box$

Remark 20 More generally, if we assume the inequality holds over each of $(\Omega_1, \pi_1), \dots, (\Omega_n, \pi_n)$ then it also holds over $(\Omega_1 \times \cdots \times \Omega_n, \pi_1 \otimes \cdots \otimes \pi_n)$; the only change needed to the proof is notational.

At this point, we have fully established the Weak Two-Function Hypercontractivity Theorem. By taking $g = f$ and $r = s = \rho$ in the theorem we obtain the full $(p,2)$-Hypercontractivity Theorem stated at the beginning of the chapter. Finally, by applying Proposition 19 we also obtain the $(2,q)$-Hypercontractivity Theorem for all $f : \{-1,1\}^n \to {\mathbb R}$.

1 comment to §9.4: Two-function hypercontractivity and induction

  • Raphaël Bouyrie

    Hello,

    Just a small remark about the following:

    “Looking at this, you might naturally guess a (correct) generalization for two functions:
    \E_{ (x,y)-\rho correlated }[f(x) g(y)] \leq \| f \|_{1+\rho} \| g \|_{1+\rho}”

    It is actually not a guess, but simply follows from the dual form of the hypercontracivity of Bonami/Becker…
    I don’t know if it is relevant to point it out, but it is not explicit here.

Leave a Reply

  

  

  

You can use most standard LaTeX, as well as these HTML tags

<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>