Proof. Induction on $n$. $n=1$ is easy. Let $f:{\{-1,1\}}^n\to ℝ$. Then $f=g+x_{n}h$ where $g(x)=E_{n}f=\frac{1}{2}(f(x_{n\to 1})+f(x_{n\to -1}))$ and $h(x)=D_{n}x=\frac{1}{2}(f(x_{n\to 1})-f(x_{n\to -1}))$. Note also that $g$ and $x_{n}h$ are orthogonal.

Recall that

$$x_A=\{\begin{array}{cc}0\hfill & n\notin A\hfill \\ x_{A\setminus \{n\}}\hfill & n\in A\hfill \end{array}$$

Therefore, $D_{n}f$ has degree at most $k-1$. First,

$$\parallel f{\parallel }_2^2=\parallel g{\parallel }_2^2+\parallel x_{n}h{\parallel }_2^2=\parallel g{\parallel }_2^2+\parallel h{\parallel }_2^2.$$

Also,

$$\begin{array}{llll}\hfill \parallel f{\parallel }_4^4& ={𝔼}_x{(g(x)+x_{n}h(x))}^4& \hfill & \\ \hfill & ={𝔼}_x(g{(x)}^4+4x_{n}g{(x)}^{3}h(x)+6x_n^{2}g{(x)}^{2}h{(x)}^2+4x_n^{3}g(x)h{(x)}^3+x_n^{4}h{(x)}^4)& \hfill & \\ \hfill & =\parallel g{\parallel }_4^4+6{𝔼}_{x}g{(x)}^{2}h{(x)}^2+\parallel h{\parallel }_4^4& \hfill & \end{array}$$

The last line uses the fact that $g$, $h$ don’t depend on $x_n$ and that $x_n=\pm 1$ with probability $\frac{1}{2}$. Then

$$\begin{array}{llllll}\hfill \parallel f{\parallel }_4^4& =\parallel g{\parallel }_4^4+6{𝔼}_{x}g{(x)}^{2}h{(x)}^2+\parallel h{\parallel }_4^4& \hfill & & \hfill & \\ \hfill & \le \parallel g{\parallel }_4^4+6\parallel g{\parallel }_4^2\parallel h{\parallel }_4^2+\parallel h{\parallel }_4^4& \hfill & \text{(by Cauchy-Schwarz)}& \hfill & & \hfill & \\ \hfill & \le 3^{2k}\parallel g{\parallel }_2^4+6\cdot 3^k\parallel g{\parallel }_2^2{3}^{k-1}\parallel h{\parallel }_2^2+3^{2(k-1)}\parallel h{\parallel }_2^4& \hfill & \text{(by inductive hypothesis)}& \hfill & & \hfill & \\ \hfill & \le 3^{2k}\left(\parallel g{\parallel }_2^4+2\parallel g{\parallel }_2^2\parallel h{\parallel }_2^2+\frac{1}{9}\parallel h{\parallel }_2^4\right)& \hfill & & \hfill & \\ \hfill & \le 3^{2k}{(\parallel g{\parallel }_2^2+\parallel h{\parallel }_2^2)}^2& \hfill & & \hfill & \\ \hfill & \le 3^{2k}\parallel f{\parallel }_2^4& \hfill & \square & \hfill & & \hfill & \end{array}$$

Proof. Let $g=f-\mu$. Then $𝔼g=0$ and $\parallel g{\parallel }_2^2={\sigma }^2$. Let $p=\mathbb{P}\left[|g(x)|>\frac{\sigma }{2}\right]$. Let $A=\left\{x:|g(x)|\le \frac{\sigma }{2}\right\}$, $B=A^c$. Then

$${\sigma }^2=\parallel g{\parallel }_2^2\le (1-p)\frac{{\sigma }^2}{4}+p{𝔼}_{x\in B}g{(x)}^2.$$

Therefore,

$$p{𝔼}_{x\in B}g{(x)}^2\ge \frac{3}{4}{\sigma }^2,$$

so

$${𝔼}_{x\in B}g{(x)}^2\ge \frac{3{\sigma }^2}{4p}.$$

By Cauchy-Schwarz (or $\mathrm{Var}(g{(x)}^2)\ge 0$) we have

$${𝔼}_{x\in B}g{(x)}^4\ge \frac{9{\sigma }^4}{16p^2},$$

so $\parallel g{\parallel }_4^4\ge \frac{9{\sigma }^4}{16p}$. But Bonami’s Lemma implies that $\parallel g{\parallel }_4^4\le 3^{2k}\parallel g{\parallel }_2^4=3^{2k}{\sigma }^4$. Therefore, $p\ge \frac{9}{16}\cdot 3^{-2k}$, as stated. □

Proof. $𝔼g^2={\sum }_i{a}_i^2$ by Parseval, so

$$\begin{array}{llll}\hfill {(𝔼g^2)}^2& =\sum _i{a}_i^4+\sum _{i\ne j}{a}_i^2{a}_j^2& \hfill & \\ \hfill 𝔼g^4& =\sum _{i,j,k,l}{a}_i{a}_j{a}_k{a}_l{𝔼}_x{x}_i{x}_j{x}_k{x}_l& \hfill & \\ \hfill & =\sum _i{a}_i^4+3\sum _{i\ne j}{a}_i^2{a}_j^2& \hfill & \end{array}$$

Note that ${𝔼}_x{x}_i{x}_j{x}_k{x}_l$ vanishes if any index appears an odd number of times, which is how we deduce the last equality above.

Subtracting the two above equations gives the result. □

Proof. Let $g(x)={\sum }_i{a}_i{x}_i$. Then $1-\delta \le {\sum }_i{a}_i^2\le 1$, $2{\sum }_{i\ne j}{a}_i^2{a}_j^2\le C\delta$. Therefore,

$$\sum _i{a}_i^4={\left(\sum _i{a}_i^2\right)}^2-\sum _{i\ne j}{a}_i^2{a}_j^2\ge 1-2\delta -\frac{C}{2}\delta =1-\left(2+\frac{C}{2}\right)\delta .$$

Also,

$$\sum _i{a}_i^4\le \underset{i}{\max }{a}_i^2\left(\sum _i{a}_i^2\right)\le \max \underset{i}{\overset{2}{a}}=\max \widehat{g}{(i)}^2.\square$$

Proof. Let $G$ be the degree-$1$ part of $f$, i.e. $g={\sum }_i\widehat{f}(i)x_i$. Then by hypothesis, $1-\delta \le \parallel g{\parallel }_2^2$, and by Parseval $\parallel g{\parallel }_2^2\le \parallel g{\parallel }_2^2=1$. Let $\sigma =\mathrm{Var}{g}^2$. Note that $g^2$ has degree at most $2$. By the Anticoncentration of low-degree functions,

$$\mathbb{P}\left[|g^2-\parallel g{\parallel }_2^2|>\frac{\sigma }{2}\right]\ge \frac{9}{16}\cdot \frac{1}{81}=\frac{1}{9\times 16}.$$

Since $\parallel g{\parallel }_2^2\in [1-\delta ,1]$, it follows that

$$\mathbb{P}\left[|g^2-1|>\frac{\sigma }{2}-\delta \right]\ge \frac{1}{9\times 16}.$$

Also, $1=f^2$. Therefore,

$${𝔼}_x|g{(x)}^2-f{(x)}^2|\ge \frac{1}{9\times 16}\cdot \left(\frac{\sigma }{2}-\delta \right).$$

But

$${𝔼}_x|g{(x)}^2-f{(x)}^2|={𝔼}_x|g(x)+f(x)||g(x)-f(x)|\le \parallel f+g{\parallel }_2\parallel f-g{\parallel }_2\le 2\sqrt{\delta }$$

by Cauchy-Schwarz. Therefore, $\frac{\sigma }{2}-\delta \le 32\times 9\sqrt{\delta }$, so $\sigma \le 64\times 9\sqrt{\delta }+2\delta \le 600\sqrt{\delta }$, so ${\sigma }^2\le 360000\delta$. By Lemma 4.4, there exists $i$ such that $\widehat{g}{(i)}^2\ge 1-180002\delta =1-O(\delta )$. But $\widehat{g}{(i)}^2=\widehat{f}{(i)}^2$, so we are done. □

Proof.

$$\begin{array}{llllll}\hfill \parallel T_{\rho }f{\parallel }_4& =\parallel \sum _{k=0}^n{T}_{r}ho{f}^{(=k)}{\parallel }_4& \hfill & & \hfill & \\ \hfill & =\parallel \sum _{k=0}^n{\rho }^k{f}^{(=k)}{\parallel }_4& \hfill & & \hfill & \\ \hfill & \le \sum _{k=0}^n{\rho }^k\parallel f^{(=k)}{\parallel }_4& \hfill & & \hfill & \\ \hfill & \le \sum _{k=0}^n{\rho }^k\cdot 3^{k∕2}\parallel f^{(=k)}{\parallel }_2& \hfill & \text{(by }\text{Bonami’s Lemma}\text{)}& \hfill & & \hfill & \\ \hfill & =\sum _{k=0}^n\parallel f^{(=k)}{\parallel }_2& \hfill & & \hfill & \\ \hfill & \le \sqrt{n}{\left(\sum _{k=0}^n\parallel f^{(=k)}{\parallel }_2^2\right)}^{\frac{1}{2}}& \hfill & & \hfill & \\ \hfill & =\sqrt{n}\parallel f{\parallel }_2& \hfill & \text{(since the }{f}^{(=k)}\text{ are orthogonal)}& \hfill & & \hfill & \end{array}$$

To get rid of the $\sqrt{n}$ we use the tensor-power trick.

Write $f^{\otimes m}:{({\{-1,1\}}^n)}^m\to ℝ$ for the function

$$f^{\otimes m}(x^1,\dots ,x^m)=f(x^1)\cdots f(x^m).$$

It is easy to check that $\parallel T_{\rho }{f}^{\otimes m}{\parallel }_4=\parallel T_{\rho }f{\parallel }_4^m$ and $\parallel f^{\otimes m}{\parallel }_2=\parallel f{\parallel }_2^m$. Therefore,

$$\parallel T_{\rho }f{\parallel }_4^m=\parallel T_{\rho }{f}^{\otimes m}{\parallel }_4\le \sqrt{mn}\parallel f^{\otimes m}{\parallel }_2=\sqrt{mn}\parallel f{\parallel }_2^m,$$

where the inequality is what we proved earlier.

So $\parallel T_{\rho }f{\parallel }_4\le {(mn)}^{\frac{1}{2m}}\parallel f{\parallel }_2$ for every $m$. Letting $m\to \infty$, we deduce that $\parallel T_{\rho }f{\parallel }_4\le \parallel f{\parallel }_2$. □

Proof. Note that $T_{\rho }$ is self adjoint (see the example sheet, or note that it easily follows from $\widehat{T_{\rho }f}(A)={\rho }^{|A|}\widehat{f}(A)$). So

$$\begin{array}{llllll}\hfill \parallel T_{\rho }f{\parallel }_2& =\underset{\parallel g{\parallel }_2=1}{\max }⟨T_{\rho }f,g⟩& \hfill & & \hfill & \\ \hfill & =\underset{\parallel g{\parallel }_2=1}{\max }⟨f,T_{\rho }g⟩& \hfill & \text{(self-adjoint)}& \hfill & & \hfill & \\ \hfill & \le \underset{\parallel h{\parallel }_4=1}{\max }⟨f,h⟩& \hfill & \text{(by Theorem }\text{4.6}\text{)}& \hfill & & \hfill & \\ \hfill & =\parallel f{\parallel }_{4∕3}& \hfill & \text{(since }{L}_{4∕3}\text{ is the dual of }{L}_4\text{)}\square & \hfill & & \hfill & \end{array}$$