§10.4: More on randomization/symmetrization

In Section 3 we collected a number of consequences of the General Hypercontractivity Theorem for functions $f \in L^2(\Omega^n, \pi^{\otimes n})$. All of these had a dependence on “$\lambda$”, the least probability of an outcome under $\pi$. This can sometimes be quite expensive; for example, the KKL Theorem and its consequence Theorem 28 are trivialized when $\lambda = 1/n^{\Theta(1)}$.

However as mentioned in Section 2, when working with symmetric random variables $\boldsymbol{X}$, the “randomization” trick sometimes lets you reduce to the analysis of uniformly random $\pm 1$ bits (which have $\lambda = 1/2$). Further, Lemma 14 suggests a way of “symmetrizing” general mean-zero random variables (at least if we don’t mind applying $\mathrm{T}_{\frac12}$). In this section we will develop the randomization/symmetrization technique more thoroughly and see an application: bounding the $L^p \to L^p$ norm of the “low-degree projection” operator.

Informally, applying the randomization/symmetrization technique to $f \in L^2(\Omega^n,\pi^{\otimes n})$ means introducing $n$ independent uniformly random bits $\boldsymbol{r} = (\boldsymbol{r}_1, \dots, \boldsymbol{r}_n) \sim \{-1,1\}^n$ and then “multiplying the $i$th input to $f$ by $\boldsymbol{r}_i$”. Of course $\Omega$ is just an abstract set so this doesn’t quite make sense. What we really mean is “multiplying $\mathrm{L}_i f$, the $i$th part of $f$’s Fourier expansion (orthogonal decomposition), by $\boldsymbol{r}_i$”. Let’s see some examples:

Example 29 Let $f : \{-1,1\}^n \to {\mathbb R}$ be a usual boolean function with Fourier expansion $f(x) = \sum_{S \subseteq [n]} \widehat{f}(S)\prod_{i\in S} x_i.$ Its randomization/symmetrization will be the function $\widetilde{f}(r,x) = \sum_{S \subseteq [n]} \widehat{f}(S) \prod_{i \in S}r_ix_i = \sum_{S \subseteq [n]} \widehat{f}(S)\,x^Sr^S.$ The key observation is that for random inputs ${\boldsymbol{x}}, \boldsymbol{r} \sim \{-1,1\}^n$, the random variables $f({\boldsymbol{x}})$ and $\widetilde{f}(\boldsymbol{r},{\boldsymbol{x}})$ are identically distributed. This is simply because ${\boldsymbol{x}}_i$ is a symmetric random variable, so it has the same distribution as $\boldsymbol{r}_i {\boldsymbol{x}}_i$.

Example 30 Let’s return to Examples 8.10, 8.15 from Chapter 8.1. Here we had $\Omega = \{a,b,c\}$ with $\pi$ the uniform distribution, and we defined a certain Fourier basis $\{\phi_0 \equiv 1, \phi_1, \phi_2\}$. A typical $f : \Omega^3 \to {\mathbb R}$ here might look like \begin{align*} f({\boldsymbol{x}}_1,{\boldsymbol{x}}_2,{\boldsymbol{x}}_3) = \tfrac13 &- \tfrac14 \cdot\phi_1({\boldsymbol{x}}_1) + \tfrac32 \cdot\phi_{2}({\boldsymbol{x}}_1) + \cdot\phi_1({\boldsymbol{x}}_2) + \tfrac12 \cdot\phi_{2}({\boldsymbol{x}}_2) – \tfrac23 \cdot\phi_2({\boldsymbol{x}}_3) \\ &{}+\tfrac{1}{6}\cdot\phi_1({\boldsymbol{x}}_1)\cdot\phi_2({\boldsymbol{x}}_3) + \tfrac18 \cdot\phi_1({\boldsymbol{x}}_2)\cdot\phi_1({\boldsymbol{x}}_3) \\ &{}-\tfrac{1}{10} \cdot\phi_1({\boldsymbol{x}}_1)\cdot\phi_2({\boldsymbol{x}}_2)\cdot\phi_3({\boldsymbol{x}}_3) + \tfrac{1}{5} \cdot\phi_2({\boldsymbol{x}}_1)\cdot\phi_2({\boldsymbol{x}}_2)\cdot\phi_2({\boldsymbol{x}}_3). \end{align*} The randomization/symmetrization of this function would be the following function $\widetilde{f} \in L^2(\{-1,1\}^3 \times \Omega^3, \pi_{1/2}^{\otimes 3} \otimes \pi^{\otimes 3})$: \begin{align*} \widetilde{f}(\boldsymbol{r},{\boldsymbol{x}}) = \tfrac13 &- \tfrac14 \phi_1({\boldsymbol{x}}_1)\cdot\boldsymbol{r}_1 + \tfrac32 \phi_{2}({\boldsymbol{x}}_1)\cdot\boldsymbol{r}_1 + \phi_1({\boldsymbol{x}}_2)\cdot\boldsymbol{r}_2 + \tfrac12 \phi_{2}({\boldsymbol{x}}_2)\cdot\boldsymbol{r}_2 – \tfrac23 \phi_2({\boldsymbol{x}}_3)\cdot\boldsymbol{r}_3 \\ &{}+\tfrac{1}{6}\phi_1({\boldsymbol{x}}_1)\cdot\phi_2({\boldsymbol{x}}_3)\cdot\boldsymbol{r}_1\boldsymbol{r}_3 + \tfrac18 \phi_1({\boldsymbol{x}}_2)\cdot\phi_1({\boldsymbol{x}}_3)\cdot\boldsymbol{r}_2\boldsymbol{r}_3 \\ &{}-\tfrac{1}{10} \phi_1({\boldsymbol{x}}_1)\cdot\phi_2({\boldsymbol{x}}_2)\cdot\phi_3({\boldsymbol{x}}_3)\cdot\boldsymbol{r}_1\boldsymbol{r}_2\boldsymbol{r}_3 + \tfrac{1}{5} \phi_2({\boldsymbol{x}}_1)\cdot\phi_2({\boldsymbol{x}}_2)\cdot\phi_2({\boldsymbol{x}}_3)\cdot\boldsymbol{r}_1\boldsymbol{r}_2\boldsymbol{r}_3. \end{align*} There’s no obvious way to compare the distributions of $f({\boldsymbol{x}})$ and $\widetilde{f}(\boldsymbol{r},{\boldsymbol{x}})$. However looking carefully at Example 8.10 we see that the basis function $\phi_2$ has the property that $\phi_2({\boldsymbol{x}}_i)$ is a symmetric real random variable when ${\boldsymbol{x}}_i \sim \pi$. In particular, $\boldsymbol{r}_i\cdot\phi_2({\boldsymbol{x}}_i)$ has the same distribution as $\phi_2({\boldsymbol{x}}_i)$. Therefore if $g \in L^2(\Omega^n,\pi^{\otimes n})$ has the lucky property that its Fourier expansion happens to only use $\phi_2$ and never uses $\phi_1$, then we do have that $g({\boldsymbol{x}})$ and $\widetilde{g}(\boldsymbol{r},{\boldsymbol{x}})$ are identically distributed.

Let’s give a formal definition of randomization/symmetrization.

Definition 31 Let $f \in L^2(\Omega^n, \pi^{\otimes n})$. The randomization/symmetrization of $f$ is the function $\widetilde{f} \in L^2(\{-1,1\}^n \times \Omega^n, \pi_{1/2}^{\otimes n} \otimes \pi^{\otimes n})$ defined by \begin{equation} \label{eqn:randsymm-def} \widetilde{f}(\boldsymbol{r}, {\boldsymbol{x}}) = \sum_{S \subseteq [n]} \boldsymbol{r}^{S} f^{=S}({\boldsymbol{x}}), \end{equation} where we recall the notation $r^S = \prod_{i \in S} r_i$.

Remark 32 Another way of defining $\widetilde{f}$ is to stipulate that for each $x \in \Omega^n$, the function $\widetilde{f}_{ \mid x} : \{-1,1\}^n \to {\mathbb R}$ is defined to be the boolean function whose Fourier coefficient on $S$ is $f^{=S}(x)$. (This is more evident from \eqref{eqn:randsymm-def} if you swap the positions of $\boldsymbol{r}^{S}$ and $f^{=S}({\boldsymbol{x}})$.)

In light of this remark, the basic Parseval formula for boolean functions implies that for all $x \in \Omega^n$, $\|\widetilde{f}_{ \mid x}\|_{2,\boldsymbol{r}}^2 = \sum_{S \subseteq [n]} f^{=S}(x)^2.$ (The notation $\|\cdot\|_{2,\boldsymbol{r}}$ emphasizes that the norm is computed with respect to the random inputs $\boldsymbol{r}$.) If we take the expectation of the above over ${\boldsymbol{x}} \sim \pi^{\otimes n}$, the left-hand side becomes $\|\widetilde{f}\|_{2,\boldsymbol{r},{\boldsymbol{x}}}^2$ and the right-hand side becomes $\|f\|_{2,{\boldsymbol{x}}}^2$, by Parseval’s formula for $L^2(\Omega^n,\pi^{\otimes n})$. Thus:

Proposition 33 Let $f \in L^2(\Omega^n,\pi^{\otimes n})$. Then $\|\widetilde{f}\|_2 = \|f\|_2$.

Thus randomization/symmetrization doesn’t change $2$-norms. What about $q$-norms for $q \neq 2$? As discussed in Examples 29, 30, if $f$ has the lucky property that its Fourier expansion only contains symmetric basis functions then $\widetilde{f}(\boldsymbol{r},{\boldsymbol{x}})$ and $f({\boldsymbol{x}})$ have identical distributions, so their $q$-norms are identical. The essential feature of the randomization/symmetrization technique is that even for general $f$ the $q$-norms don’t change much — if you are willing to apply $\mathrm{T}_\rho$ for some constant $\rho$:

Theorem 34 For $f \in L^2(\Omega^n,\pi^{\otimes n})$ and $q > 1$, \begin{equation} \label{eqn:rand-symm-thm1} \|\mathrm{T}_{\frac12} f\|_q \leq \|\widetilde{f}\|_q \leq \|\mathrm{T}_{c_q^{-1}} f\|_q. \end{equation} Equivalently, $\|\widetilde{\mathrm{T}_{c_q} f}\|_q \leq \|f\|_q \leq \|\widetilde{\mathrm{T}_2 f}\|_q.$ Here $0 < c_q \leq 1$ is a constant depending only on $q$; in particular, we may take $c_4 = c_{4/3} = \frac25$.

The two inequalities in \eqref{eqn:rand-symm-thm1} are not too difficult to prove; for example, you might already correctly guess that the left-hand inequality follows from our first randomization/symmetrization Lemma 14 and an induction. We’ll give the proofs at the end of this section. But first, let’s illustrate how you might use them by solving the following basic problem concerning low-degree projections:

Question Let $k \in {\mathbb N}$, let $1 < q < \infty$, and let $f \in L^2(\Omega^n, \pi^{\otimes n})$. Can $\|f^{\leq k}\|_q$ be much larger than $\|f\|_q$? To put the question in reverse, suppose $g \in L^2(\Omega^n, \pi^{\otimes n})$ has degree at most $k$; is it possible to make the $q$-norm of $g$ much smaller by adding terms of degree exceeding $k$ to its Fourier expansion?

The question has a simple answer if $q = 2$: in this case we have $\|f^{\leq k}\|_2 \leq \|f\|_2$ always. This follows from Paresval: \begin{equation} \label{eqn:norm-proj2} \|f^{\leq k}\|_2^2 = \sum_{j = 0}^k \mathbf{W}^{j}[f] \leq \sum_{j = 0}^n \mathbf{W}^{j}[f] = \|f\|_2^2. \end{equation} When $q \neq 2$ things are not so simple, so let’s first consider the most familiar setting of $\Omega = \{-1,1\}$, $\pi = \pi_{1/2}$. In this case we can relate the $q$-norm and the $2$-norm via the Hypercontractivity Theorem:

Proposition 35 Let $k \in {\mathbb N}$ and let $g : \{-1,1\}^n \to {\mathbb R}$. Then for $q \geq 2$ we have $\|g^{\leq k}\|_q \leq \sqrt{q-1}^k \|g\|_q$ and for $1 < q \leq 2$ we have $\|g^{\leq k}\|_q \leq (1/\sqrt{q-1})^k \|g\|_q$.

This proposition is an easy consequence of the Hypercontractivity Theorem and already appeared as Exercise 9.8. The simplest case, $q = 4$, follows from the Bonami Lemma alone: \begin{equation} \label{eqn:low-deg-proj-4-bounded} \|g^{\leq k}\|_4 \leq \sqrt{3}^k \|g^{\leq k}\|_2 \leq \sqrt{3}^k \|g\|_2 \leq \sqrt{3}^k \|g\|_4. \end{equation}

Now let’s consider functions $f \in L^2(\Omega^n, \pi^{\otimes n})$ on general product spaces; for simplicity, we’ll continue to focus on the case $q = 4$. One possibility is to repeat the above proof using the General Hypercontractivity Theorem (more specifically, Theorem 20). This would give us $\|f^{\leq k}\|_4 \leq \sqrt{3/\lambda}^k \|f\|_4$. However we will see that it’s possible to get a bound completely independent of $\lambda$ — i.e., independent of $(\Omega, \pi)$ — using randomization/symmetrization.

First, suppose we are in the lucky case described in Example 30 in which $f$’s Fourier spectrum only uses symmetric basis functions. In this case $f^{\leq k}({\boldsymbol{x}})$ and $\widetilde{f^{\leq k}}(\boldsymbol{r},{\boldsymbol{x}})$ have the same distribution for any $k$, and we can leverage the $L^2(\{-1,1\})$ bound \eqref{eqn:low-deg-proj-4-bounded} to get the same result for $f$: First, $\|f^{\leq k}\|_4 = \|\widetilde{f^{\leq k}}\|_4 = \left\|\ \|\widetilde{f^{\leq k}}_{ \mid {\boldsymbol{x}}}(\boldsymbol{r})\|_{4, \boldsymbol{r}}\ \right\|_{4, {\boldsymbol{x}}}.$ For each outcome ${\boldsymbol{x}} = x$, the inner function $g(r) = \widetilde{f^{\leq k}}_{ \mid x}(r)$ is a degree-$k$ function of $r \in \{-1,1\}^n$. Therefore we can apply \eqref{eqn:low-deg-proj-4-bounded} with this $g$ to deduce $\left\|\ \|\widetilde{f^{\leq k}}_{ \mid {\boldsymbol{x}}}(\boldsymbol{r})\|_{4, \boldsymbol{r}}\ \right\|_{4, {\boldsymbol{x}}} \leq \left\|\ \sqrt{3}^k \|\widetilde{f}_{ \mid {\boldsymbol{x}}}(\boldsymbol{r})\|_{4, \boldsymbol{r}}\ \right\|_{4, {\boldsymbol{x}}} = \sqrt{3}^k \|\widetilde{f}\|_4 = \sqrt{3}^k \|f\|_4.$ Thus we see that we can deduce \eqref{eqn:low-deg-proj-4-bounded} “automatically” for these luckily symmetric $f$, with no dependence on “$\lambda$”. We’ll now show that we can get something similar for a completely general $f$ using the randomization/symmetrization Theorem 34. This will cause us to lose a factor of $(2\cdot\tfrac52)^k$, due to application of $\mathrm{T}_2$ and $\mathrm{T}_{\frac52}$; to prepare for this, we first extend the calculation in \eqref{eqn:low-deg-proj-4-bounded} slightly.

Lemma 36 Let $k \in {\mathbb N}$ and let $g : \{-1,1\}^n \to {\mathbb R}$. Then for any $0 < \rho \leq 1$, $\|g^{\leq k}\|_4 \leq (\sqrt{3}/\rho)^k \|\mathrm{T}_\rho g\|_4.$

Proof: We have $\|g^{\leq k}\|_4 \leq \sqrt{3}^k \|g^{\leq k}\|_2 \leq \sqrt{3/\rho}^k \|\mathrm{T}_\rho g\|_2 \leq \sqrt{3/rho}^k \|\mathrm{T}_\rho g\|_4.$ Here the first inequality is Bonami’s Lemma and the second is because $\|g^{\leq k}\|_2^2 = \sum_{j = 0}^k \mathbf{W}^{j}[f] \leq (1/\rho^2)^{k} \sum_{j = 0}^k \rho^{2j} \mathbf{W}^{j}[f] \leq (1/\rho^2)^{k} \sum_{j = 0}^n \rho^{2j} \mathbf{W}^{j}[f] = (1/\rho^2)^{k} \|\mathrm{T}_\rho g\|_2^2. \qquad \Box$

We can now give a good answer to the Question above, showing that low-degree projection doesn’t substantially increase any $q$-norm:

Theorem 37 Let $k \in {\mathbb N}$ and let $f \in L^2(\Omega^n, \pi^{\otimes n})$. Then for $q > 1$ we have $\|f^{\leq k}\|_q \leq C_q^k \|f\|_q$. Here $C_q$ is a constant depending only on $q$; in particular we may take $C_4, C_{4/3} = 5\sqrt{3} \leq 9$.

Proof: We will give the proof for $q = 4$; the other cases are left as an exercise. Using the randomization/symmetrization Theorem 34, $\|f^{\leq k}\|_4 \leq \|\widetilde{\mathrm{T}_2 f^{\leq k}}\|_4 = \left\|\ \|\widetilde{\mathrm{T}_2 f^{\leq k}}_{ \mid {\boldsymbol{x}}}(\boldsymbol{r})\|_{4, \boldsymbol{r}}\ \right\|_{4,{\boldsymbol{x}}}.$ For a given outcome ${\boldsymbol{x}} = x$, let’s write $g = \widetilde{\mathrm{T}_2 f}_{ \mid x} : \{-1,1\}^n \to {\mathbb R}$, so that we have $\|g^{\leq k}(\boldsymbol{r})\|_4$ on the inside above. For clarity, we remark that $g$ is the boolean function whose Fourier coefficient on $S$ is $2^{|S|} f^{=S}(x)$. We apply Lemma 36 to this $g$, with $\rho = \frac15$; note that $\mathrm{T}_\rho g$ is then the boolean function whose Fourier coefficient on $S$ is $(\tfrac25)^{|S|} f^{=S}(x)$. I.e., it is $\widetilde{\mathrm{T}_{\frac25} f}_{ \mid x}$. Thus we deduce $\left\|\ \|\widetilde{\mathrm{T}_2 f^{\leq k}}_{ \mid {\boldsymbol{x}}}(\boldsymbol{r})\|_{4, \boldsymbol{r}}\ \right\|_{4,{\boldsymbol{x}}} \leq \left\|\ (5\sqrt{3})^k\|\widetilde{\mathrm{T}_{\frac25} f}_{ \mid {\boldsymbol{x}}}(\boldsymbol{r})\|_{4, \boldsymbol{r}}\ \right\|_{4,{\boldsymbol{x}}} = (5\sqrt{3})^k\|\widetilde{\mathrm{T}_{\frac25} f}\|_4 \leq (5\sqrt{3})^k\|f\|_4,$ where the last step is the “un-randomization/symmetrization” inequality from Theorem 34. $\Box$

The remainder of this section is devoted to the proof of Theorem 34, which lets us compare norms of a function and its randomization/symmetrization. It will help to view randomization/symmetrization from an operator perspective. To do this, we need to slightly extend our $\mathrm{T}_\rho$ notation, allowing for “different noise rates on different coordinates”.

Definition 38 For $i \in [n]$ and $\rho \in {\mathbb R}$, let $\mathrm{T}^i_\rho$ be the operator on $L^2(\Omega^n, \pi^{\otimes n})$ defined by \begin{equation} \label{eqn:single-T} \mathrm{T}^i_\rho f = \rho f + (1-\rho) \mathrm{E}_i f = \mathrm{E}_i f + \rho \mathrm{L}_i f = \sum_{S \not \ni i} f^{=S} + \rho \sum_{S \ni i} f^{=S}. \end{equation} Furthermore, for $r = (r_1, \dots, r_n) \in {\mathbb R}^n$, let $\mathrm{T}_r$ be the operator on $L^2(\Omega^n, \pi^{\otimes n})$ defined by $\mathrm{T}_r = \mathrm{T}^1_{r_1} \mathrm{T}^2_{r_2} \cdots \mathrm{T}^n_{r_n}$. From the third formula in \eqref{eqn:single-T} we have \begin{equation} \label{eqn:single-T2} \mathrm{T}_r f = \sum_{S \subseteq [n]} r^S\,f^{=S}, \end{equation} where we use the notation $r^S = \prod_{i \in S} r_i$. In particular, $\mathrm{T}_{(\rho, \dots, \rho)}$ is the usual $\mathrm{T}_\rho$ operator. We remark that when $r \in [0,1]^n$ we have $\mathrm{T}_r f(x) = \mathop{\bf E}_{\boldsymbol{y}_1 \sim N_{r_1}(x_1), \dots, \boldsymbol{y}_n \sim N_{r_n}(x_n)}[f(\boldsymbol{y}_1, \dots, \boldsymbol{y}_n)].$

These generalizations of the noise operator behave the way you would expect; you are referred to the exercises for some basic properties. Now comparing \eqref{eqn:single-T2} and \eqref{eqn:randsymm-def} reveals the connection to randomization/symmetrization:

Fact 39 For $f \in L^2(\Omega^n, \pi^{\otimes n})$, $x \in \Omega^n$, and $r \in \{-1,1\}^n$, $\widetilde{f}(r,x) = \mathrm{T}_r f(x).$

In other words, randomization/symmetrization of $f$ means applying $\mathrm{T}_{(\pm 1, \pm 1, \dots, \pm 1)}$ to $f$ for a random choice of signs. We use this viewpoint to prove Theorem 34, which we do in two steps:

Theorem 40 Let $f \in L^2(\Omega^n, \pi^{\otimes n})$. Then for any $q \geq 1$, \begin{equation} \label{eqn:rand-symm} \|\mathrm{T}_{\frac12} f({\boldsymbol{x}})\|_{q,{\boldsymbol{x}}} \leq \|\mathrm{T}_{\boldsymbol{r}} f({\boldsymbol{x}})\|_{q, \boldsymbol{r}, {\boldsymbol{x}}} \end{equation} for ${\boldsymbol{x}} \sim \pi^{\otimes n}$, $\boldsymbol{r} \sim \{-1,1\}^n$. In other words, $\|\mathrm{T}_{\frac12} f\|_q \leq \|\widetilde{f}\|_q$.

Proof: In brief, the result follows from our first randomization/symmetrization result, Lemma 14, and an induction. To fill in the details, we begin by showing that if $h \in L^2(\Omega, \pi)$ is any one-input function and $\boldsymbol{\omega} \sim \pi$, $\boldsymbol{b} \sim \{-1,1\}$, then \begin{equation} \label{eqn:symm-h} \|\mathrm{T}_{\frac12} h(\boldsymbol{\omega})\|_{q, \boldsymbol{\omega}} \leq \|\mathrm{T}_{\boldsymbol{b}} h(\boldsymbol{\omega})\|_{q, \boldsymbol{b}, \boldsymbol{\omega}}. \end{equation} This follows immediately from Lemma 14 because $h^{=\{1\}}({\boldsymbol{x}})$ is a mean-zero random variable (cf. the proof of Corollary 19). Next, we show that for any $g \in L^2(\Omega^n, \pi^{\otimes n})$ and any $i \in [n]$, \begin{equation} \label{eqn:symm-g} \|\mathrm{T}^i_{\frac12} g({\boldsymbol{x}})\|_{q,{\boldsymbol{x}}} \leq \|\mathrm{T}^i_{\boldsymbol{r}_i} g({\boldsymbol{x}})\|_{q, \boldsymbol{r}_i, {\boldsymbol{x}}}. \end{equation} Assuming $i = 1$ for notational simplicity, and writing $x = (x_1, x’)$ where $x’ = (x_2, \dots, x_n)$, we have $\|\mathrm{T}^i_{\frac12} g({\boldsymbol{x}})\|_{q,{\boldsymbol{x}}} = \left\|\ \|\mathrm{T}^i_{\frac12} g({\boldsymbol{x}}_1, {\boldsymbol{x}}')\|_{q,{\boldsymbol{x}}_1}\ \right\|_{q,{\boldsymbol{x}}'} = \left\|\ \|(\mathrm{T}_{\frac12} g_{ \mid {\boldsymbol{x}}'})({\boldsymbol{x}}_1)\|_{q,{\boldsymbol{x}}_1}\ \right\|_{q,{\boldsymbol{x}}'}.$ (You are asked to carefully justify the second equality here in the exercises.) Now for each outcome of ${\boldsymbol{x}}’$ we can apply \eqref{eqn:symm-h} with $h = g_{ \mid {\boldsymbol{x}}’}$ to deduce $\left\|\ \|(\mathrm{T}_{\frac12} g_{ \mid {\boldsymbol{x}}'})({\boldsymbol{x}}_1)\|_{q,{\boldsymbol{x}}_1}\ \right\|_{q,{\boldsymbol{x}}'} \leq \left\|\ \|(\mathrm{T}_{\boldsymbol{r}_1} g_{ \mid {\boldsymbol{x}}'})({\boldsymbol{x}}_1)\|_{q,{\boldsymbol{x}}_1, \boldsymbol{r}_1}\ \right\|_{q,{\boldsymbol{x}}'} = \|\mathrm{T}^i_{\boldsymbol{r}_i} g({\boldsymbol{x}})\|_{q, \boldsymbol{r}_i, {\boldsymbol{x}}}.$ Finally, we illustrate the first step of the induction. For distinct indices $i,j$, $\|\mathrm{T}^i_{\frac12} \mathrm{T}^j_{\frac12} f({\boldsymbol{x}})\|_{q,{\boldsymbol{x}}} \leq \|\mathrm{T}^i_{\boldsymbol{r}_i} \mathrm{T}^j_{\frac12} f({\boldsymbol{x}})\|_{q, \boldsymbol{r}_i, {\boldsymbol{x}}}$ by applying \eqref{eqn:symm-g} with $g = \mathrm{T}^j_{\frac12} f$. Then $\|\mathrm{T}^i_{\boldsymbol{r}_i} \mathrm{T}^j_{\frac12} f({\boldsymbol{x}})\|_{q, \boldsymbol{r}_i, {\boldsymbol{x}}} = \left\|\ \|\mathrm{T}^i_{\boldsymbol{r}_i} \mathrm{T}^j_{\frac12} f({\boldsymbol{x}})\|_{q, {\boldsymbol{x}}}\ \right\|_{q, \boldsymbol{r}_i} = \left\|\ \|\mathrm{T}^j_{\frac12} \mathrm{T}^i_{\boldsymbol{r}_i} f({\boldsymbol{x}})\|_{q, {\boldsymbol{x}}}\ \right\|_{q, \boldsymbol{r}_i},$ where we used that $\mathrm{T}^i_{\rho_i}$ and $\mathrm{T}^j_{\rho_j}$ commute. Now for each outcome of $\boldsymbol{r}_i$ we can apply \eqref{eqn:symm-g} with $g = \mathrm{T}^i_{\boldsymbol{r}_i} f$ to get $\left\|\ \|\mathrm{T}^j_{\frac12} \mathrm{T}^i_{\boldsymbol{r}_i} f({\boldsymbol{x}})\|_{q, {\boldsymbol{x}}}\ \right\|_{q, \boldsymbol{r}_i} \leq \left\|\ \|\mathrm{T}^j_{\boldsymbol{r}_j} \mathrm{T}^i_{\boldsymbol{r}_i} f({\boldsymbol{x}})\|_{q, \boldsymbol{r}_j, {\boldsymbol{x}}}\ \right\|_{q, \boldsymbol{r}_i} = \|\mathrm{T}^i_{\boldsymbol{r}_i} \mathrm{T}^j_{\boldsymbol{r}_j} f({\boldsymbol{x}})\|_{q,\boldsymbol{r}_i,\boldsymbol{r}_j,{\boldsymbol{x}}}.$ Thus we have shown $\|\mathrm{T}^i_{\frac12} \mathrm{T}^j_{\frac12} f({\boldsymbol{x}})\|_{q,{\boldsymbol{x}}} \leq \|\mathrm{T}^i_{\boldsymbol{r}_i} \mathrm{T}^j_{\boldsymbol{r}_j} f({\boldsymbol{x}})\|_{q,\boldsymbol{r}_i,\boldsymbol{r}_j,{\boldsymbol{x}}}.$ Continuing the induction in the same way completes the proof. $\Box$

To prove the “un-randomization/symmetrization” inequality in Theorem 34, we first establish an elementary lemma about mean-zero random variables:

Lemma 41 Let $q \geq 2$. Then there is a small enough $0 < c_q \leq 1$ such that $\|a - c_q \boldsymbol{X}\|_q \leq \|a + \boldsymbol{X}\|_q$ for any $a \in {\mathbb R}$ and any random variable $\boldsymbol{X}$ satisfying $\mathop{\bf E}[\boldsymbol{X}] = 0$ and $\|\boldsymbol{X}\|_q < \infty$. In particular we may take $c_4 = \frac25$.

Proof: We will only prove the statement for $q = 4$; you are asked to establish the general case in the exercises. By homogeneity we may assume $a = 1$; then raising the inequality to the $4$th power we need to show $\mathop{\bf E}[(1 - c \boldsymbol{X})^4] \leq \mathop{\bf E}[(1 + \boldsymbol{X})^4]$ for small enough $c$. Expanding both sides and using $\mathop{\bf E}[\boldsymbol{X}] = 0$, this is equivalent to \begin{equation} \label{eqn:unsymm} \mathop{\bf E}[(1 - c^4) \boldsymbol{X}^4 + (4+4c^3)\boldsymbol{X}^3 + (6 - 6c^2)\boldsymbol{X}^2] \geq 0. \end{equation} It suffices to find $c$ such that \begin{equation} \label{eqn:unsymm-ex} (1 – c^4) x^2 + (4+4c^3)x + (6 – 6c^2) \geq 0 \quad \forall x \in {\mathbb R}; \end{equation} then we can multiply this inequality by $x^2$ and take expectations to obtain \eqref{eqn:unsymm}. This last problem is elementary, and in the exercises you’re asked to find the largest $c$ which works (the answer is $c \approx .435$). To see that $c = \frac25$ suffices, we use the fact that $x \geq -\frac29 x^2 – \frac98$ for all $x$ (because the difference of the left- and right-hand sides is $\frac{1}{72}(4x+9)^2$). Putting this into \eqref{eqn:unsymm-ex}, it remains to ensure $(\tfrac19-\tfrac89c^3-c^4)x^2 + (\tfrac32 -6c^2-\tfrac92c^3) \geq 0 \quad \forall x \in {\mathbb R},$ and when $c = \frac25$ this is the trivially true statement $\frac{161}{5625}x^2+\frac{63}{250} \geq 0$. $\Box$

Theorem 42 Let $f \in L^2(\Omega^n,\pi^{\otimes n})$. Then for any $q > 1$, $\|\mathrm{T}_{c_q \boldsymbol{r}} f({\boldsymbol{x}})\|_{q,\boldsymbol{r},{\boldsymbol{x}}} \leq \| f({\boldsymbol{x}})\|_{q, {\boldsymbol{x}}}$ for ${\boldsymbol{x}} \sim \pi^{\otimes n}$, $\boldsymbol{r} \sim \{-1,1\}^n$. In other words, $\|\widetilde{\mathrm{T}_{c_q} f}\|_q \leq \|f\|_q$. Here $0 < c_q \leq 1$ is a constant depending only on $q$; in particular we may take $c_4, c_{4/3} = \frac25$.

Proof: In fact, we can show that for every outcome $\boldsymbol{r} = r \in \{-1,1\}^n$ we have $\|\mathrm{T}_{c_q r} f({\boldsymbol{x}})\|_{q,{\boldsymbol{x}}} \leq \| f({\boldsymbol{x}})\|_{q, {\boldsymbol{x}}}$ for sufficiently small $c_q > 0$. Note that on the left-hand side we have $\|\mathrm{T}^1_{\pm c_q} \mathrm{T}^2_{\pm c_q} \cdots \mathrm{T}^n_{\pm c_q} f({\boldsymbol{x}})\|_{q, {\boldsymbol{x}}}.$ We know that $\mathrm{T}^i_\rho$ is a contraction in $L^q$ for any $\rho \geq 0$ (exercise). Hence it suffices to show that $\mathrm{T}^i_{-c_q}$ is a contraction in $L^q$; i.e., that \begin{equation} \label{eqn:unsymm1} \|\mathrm{T}^i_{-c_q} g({\boldsymbol{x}})\|_{q,{\boldsymbol{x}}} \leq \|g({\boldsymbol{x}})\|_{q,{\boldsymbol{x}}} \end{equation} for all $g \in L^2(\Omega^n, \pi^{\otimes n})$. Similar to the proof of Theorem 40, it suffices to show \begin{equation} \label{eqn:negative-contract} \|\mathrm{T}_{-c_q} h\|_q \leq \|h\|_q \end{equation} for all one-input functions $h \in L^2(\Omega, \pi)$, because then \eqref{eqn:unsymm1} holds pointwise for all outcomes of ${\boldsymbol{x}}_1, \dots, {\boldsymbol{x}}_{i-1}, {\boldsymbol{x}}_{i+1}, \dots, {\boldsymbol{x}}_n$. By Proposition 9.19, if we prove \eqref{eqn:negative-contract} for some $q$ then the same constant $c_q$ works for the conjugate Hölder index $q’$; thus we may restrict attention to $q \geq 2$. Now the result follows from Lemma 41 by taking $a = h^{=\emptyset}$ and $\boldsymbol{X} = h^{=\{1\}}({\boldsymbol{x}})$. $\Box$

14 comments to §10.4: More on randomization/symmetrization

• Ravi Boppana

In the statement of Theorem 37, should $C_4, C_{4/3}$ be just $C_4$?

• Ryan O'Donnell

I think it’s what I intended; although I only give the proof for $C_4$, one may also take that value for $C_{4/3}$, as one exercise requests you show. I think, at least; perhaps I’ve made a mistake?

Glad someone is reading these latter chapters carefully, thanks!

• Ravi Boppana

Okay, makes sense. I got confused because the given proof only deals with $C_4$, but the result seems okay for $C_{4/3}$ too.

• Noam Lifshitz

I think in Lemma 36 it should be
$\|g^{\leq k}\|_4 \leq \sqrt{3}^k \|g^{\leq k}\|_2 \leq \sqrt{3/\rho}^k \|\mathrm{T}_\rho g\|_2 \leq \sqrt{3/\rho}^k \|\mathrm{T}_\rho g\|_4.$

• Ryan O'Donnell

Thanks! Fixed!

• Noam Lifshitz

Actually I think it should be $\|g^{\leq k}\|_4 \leq \sqrt{3}^k \|g^{\leq k}\|_2 \leq \sqrt{3/\rho^2}^k \|\mathrm{T}_\rho g\|_2 \leq \sqrt{3/\rho^2}^k \|\mathrm{T}_\rho g\|_4.$

• Ryan O'Donnell

Right again. Thanks for this!

• Noam Lifshitz

In theorem 37 it should probably be
$\left\|\ \|\widetilde{\mathrm{T}_2 f^{\leq k}}_{ \mid {\boldsymbol{x}}}(\boldsymbol{r})\|_{4, \boldsymbol{r}}\ \right\|_{4,{\boldsymbol{x}}} \leq \left\|\ (5\sqrt{3})^k\|\widetilde{\mathrm{T}_{\frac25} f}_{ \mid {\boldsymbol{x}}}(\boldsymbol{r})\|_{4, \boldsymbol{r}}\ \right\|_{4,{\boldsymbol{x}}} = (5\sqrt{3})^k\|\widetilde{\mathrm{T}_{\frac25} f}\|_4 \leq (5\sqrt{3})^k\|f\|_4,$

• Ryan O'Donnell

Absolutely, thanks!

• Noam Lifshitz

In def 38 I think it should be
$\mathrm{T}_r = \mathrm{T^1}_{r_1} \mathrm{T^2}_{r_2} \cdots \mathrm{T^n}_{r_n}$

• Ryan O'Donnell

Yes, thank you!

• Matt Franklin

There may be two small typos in the first line of the proof of Lemma 10.38 (p. 297 in book):
should they be ($\sqrt{3} / \rho)^k$ instead of $\sqrt{3 / \rho}^k$ ?

• Ryan O'Donnell

They should, though someone else reported this bug already Thanks!

• Ohad Klein

ctrl+f: Paresval.