Chapter 10 exercises

1. First obtain \[ \|a+\rho b(\boldsymbol{X}+\boldsymbol{Y})\|_{q, \boldsymbol{X},\boldsymbol{Y}} \leq \left\|\ \|a+\rho b \boldsymbol{X} + b\boldsymbol{Y}\|_{p, \boldsymbol{Y}}\ \right\|_{q,\boldsymbol{X}}. \]
2. Next, upper-bound this by \[ \left\|\ \|a+b\boldsymbol{Y} + \rho b \boldsymbol{X}\|_{q, \boldsymbol{X}}\ \right\|_{p,\boldsymbol{Y}}. \] (Hint: Exercise 1.)
3. Finally, upper-bound this by \[ \left\|\ \|a+b\boldsymbol{Y} + b \boldsymbol{X}\|_{p, \boldsymbol{X}}\ \right\|_{p,\boldsymbol{Y}} = \|a+b(\boldsymbol{X}+\boldsymbol{Y})\|_{p,\boldsymbol{X},\boldsymbol{Y}}. \]

1. Why is Exercise 2 a special case of \eqref{eqn:poly-hc-hc}?
2. Begin the inductive proof of \eqref{eqn:poly-hc-hc} by showing that the base case $n = 0$ is trivial.
3. For the case of general $n$, first establish \[ \|\mathrm{T}_\rho F(\boldsymbol{X})\|_q \leq \left\| \ \|\mathrm{T}'_\rho E(\boldsymbol{X}') + \boldsymbol{X}_n \mathrm{T}'_\rho D(\boldsymbol{X}') \|_{p, \boldsymbol{X}_n} \ \right\|_{q, \boldsymbol{X}'}, \] where we are using the notation $x’ = (x_1, \dots, x_{n-1})$, $F(x) = E(x’) + x_n D(x’)$, and $\mathrm{T}_\rho’$ for the operator acting formally on $(n-1)$-variate multilinear polynomials.
4. Complete the inductive step, using steps similar to Exercises 2(b),(c). (Hint: for $X_n$ a real constant, why is $\mathrm{T}’_\rho E(\boldsymbol{X}’) + X_n \mathrm{T}’_\rho D(\boldsymbol{X}’) = \mathrm{T}’_\rho (E + X_n D)(\boldsymbol{X}’)$?)

1. In our proof of the Two-Point Inequality we used Proposition 9.19 to deduce that a uniform bit ${\boldsymbol{x}} \sim \{-1,1\}$ is $(p,q,\rho)$-hypercontractivity if it’s $(q’,p’,\rho)$-hypercontractive. Why can’t we use Proposition 9.19 to deduce this for a general random variable $\boldsymbol{X}$?
2. For each $1 < p < 2$, exhibit a random variable $\boldsymbol{X}$ which is $(p, 2, \rho)$-hypercontractive (for some $\rho$) but not $(2,p’,\rho)$-hypercontractive.

1. Regarding Remark 2, heuristically justify (in the manner of Exercise 9.24) the following statement: If $A, B \subseteq \{-1,1\}^n$ are concentric Hamming balls with volumes $\exp(-\frac{a^2}{2})$ and $\exp(-\frac{b^2}{2})$ and $\rho a \leq b \leq a$ (where $0 < \rho < 1$) then \[ \mathop{\bf Pr}_{\substack{({\boldsymbol{x}}, \boldsymbol{y}) \\ \text{ $\rho$-correlated}}}[{\boldsymbol{x}} \in A, \boldsymbol{y} \in B] \gtrapprox \exp\left(-\tfrac12 \tfrac{a^2 – 2\rho ab + b^2}{1-\rho^2}\right); \] and further, if $b < \rho a$ then $\mathop{\bf Pr}[{\boldsymbol{x}} \in A, \boldsymbol{y} \in B] \sim \mathop{\bf Pr}[{\boldsymbol{x}} \in A]$. Here you should treat $\rho$ as fixed and $a, b \to \infty$.
2. Similarly, heuristically justify that the Reverse Small-Set Expansion Theorem is essentially sharp by considering diametrically opposed Hamming balls.

Reverse Hypercontractivity Theorem Let $f : \{-1,1\}^n \to {\mathbb R}^{\geq 0}$ be a nonnegative function and let $-\infty \leq q < p \leq 1$. Then $\|\mathrm{T}_\rho f\|_q \geq \|f\|_p$ for $0 \leq \rho \leq \sqrt{(1-p)/(1-q)}$.

Reverse Two-Function Hypercontractivity Theorem Let $f, g : \{-1,1\}^n \to {\mathbb R}^{\geq 0}$ be nonnegative, let $r, s \leq 0$, 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})] \geq \|f\|_{1+r} \|g\|_{1+s}. \]

Recall that for $-\infty < p < 0$ and for positive functions $f \in L^2(\Omega, \pi)$ the “norm” $\|f\|_p$ retains the definition $\mathop{\bf E}[f^p]^{-1/p}$. (The cases of $p = -\infty$, $p = 0$, and nonnegative functions are defined by appropriate limits; in particular $\|f\|_{-\infty}$ is the minimum of $f$’s values, $\|f\|_0$ is the geometric mean of $f$’s values, and $\|f\|_p$ is $0$ whenever $f$ is not everywhere positive. We also define $p’$ by $\frac1p + \frac1{p’} = 1$, with $0′ = 0$.)

The Reverse Two-Function Hypercontractivity Theorem can be thought of as a generalization of the lesser known “reverse Hölder inequality” in the setting of $L^2(\{-1,1\}^n, \pi_{1/2}^{\otimes n})$:

Reverse Hölder inequality Let $f \in L^2(\Omega, \pi)$ be a positive function. Then for any $p < 1$, \[ \|f\|_p = \inf\ \{ \mathop{\bf E}[fg] : g > 0, \|g\|_{p’} = 1\}. \] In particular, for $r < 0$ and $f, g > 0$ we have $\mathop{\bf E}[fg] \geq \|f\|_{1+r}\|g\|_{1+1/r}$.

1. Show that to prove these two Reverse Hypercontractivity Theorems it suffices to consider the case of $f, g : \{-1,1\}^n \to {\mathbb R}^+$; i.e., strictly positive functions.
2. Show that the Reverse Two-Function Hypercontractivity Theorem is equivalent (via the reverse Hölder inequality) to the Reverse Hypercontractivity Theorem.
3. Reduce the Reverse Two-Function Hypercontractivity Theorem to the $n = 1$ case. (Hint: virtually identical to the Two-Function Hypercontractivity Induction.) Further reduce to following:

   Reverse Two-Point Inequality Let $-\infty \leq q < p \leq 1$ and let $0 \leq \rho \leq \sqrt{(1-p)/(1-q)}$. Then $\|\mathrm{T}_\rho f\|_q \geq \|f\|_p$ for any $f : \{-1,1\} \to {\mathbb R}^+$.

1. Similar to the non-reverse case, the main effort is proving the inequality assuming that $0 < q < p \leq 1$ and that $\rho = \sqrt{(1-p)/(1-q)}$. Do this by mimicking the proof of the Two-Point Inequality. (Hint: you will need the inequality $(1+t)^\theta \geq 1 + \theta t$ for $\theta \geq 1$ and you will need to show that $\tfrac{j-r}{\sqrt{1-r}}$ is an increasing function of $r$ on $[0,1)$ for all $j \geq 2$.)
2. Extend to the case of $0 \leq \rho \leq \sqrt{(1-p)/(1-q)}$. (Hint: use the fact that for any $f : \{-1,1\}^n \to {\mathbb R}^{\geq 0}$ and $-\infty \leq p \leq q \leq \infty$ we have $\|f\|_p \leq \|f\|_q$. You can prove this generalization of Exercise 1.14 by reducing to the case of negative $p$ and $q$ to the case of positive $p$ and $q$.)
3. Establish the case $q = -\infty$ case of the Reverse Two-Point Inequality.
4. Show that the cases $-\infty < q < p < 0$ follow by ``duality''. (Hint: like Proposition 9.19 but with the reverse Hölder inequality.)
5. Show that the cases $q < 0 < p$ follow by the semigroup property of $\mathrm{T}_\rho$.
6. Finally, treat the cases of $p = 0$ or $q = 0$.

1. Show that we may take $c_2 = 1$ (and that equality holds). Henceforth assume $q > 2$.
2. By following the idea of our $q = 4$ proof, reduce to showing that there exists $0 < c_q < 1$ such that \[ |1 - c_qx|^q + c_qqx \leq |1+x|^q - qx \quad \forall x \in {\mathbb R}. \]
3. Further reduce to showing there exists $0 < c_q < 1$ such that \begin{equation} \label{eqn:unsymm-ex1} \frac{|1 – c_qx|^q + c_qqx – 1}{x^2} \leq \frac{|1+x|^q – qx – 1}{x^2} \quad \forall x \in {\mathbb R}. \end{equation} Here you should also establish that both sides are continuous functions of $x \in {\mathbb R}$ once the value at $x = 0$ is defined appropriately.
4. Show that there exists $M > 0$ such that for every $0 < c_q < \tfrac{1}{2}$, inequality \eqref{eqn:unsymm-ex1} holds once $|x| \geq M$. (Hint: consider the limit of both sides as $|x| \to \infty$.)
5. Argue that it suffices to show that \begin{equation} \label{eqn:unsymm-ex2} \frac{|1+x|^q – qx -1}{x^2} \geq \eta \end{equation} for some universal positive constant $\eta > 0$. (Hint: a uniform continuity argument for $(x,c_q) \in [-M,M] \times [0,\tfrac{1}{2}]$.)
6. Establish \eqref{eqn:unsymm-ex2}. (Hint: the best possible $\eta$ is $1$ but to just achieve some positive $\eta$, argue using Bernoulli’s inequality that $\frac{|1+x|^q – qx -1}{x^2}$ is everywhere positive and then observe that it tends to $\infty$ as $|x| \to \infty$.)
7. Possibly using a different argument, what is the best asymptotic bound you can achieve for $c_q$? Is $c_q \geq \Omega(\frac{\log q}{q})$ possible?

1. Show that $1 + 6c^2 x^2 + c^4 x^4 \leq 1 + 6x^2 + 4x^3 + x^4$ holds for all $x \in {\mathbb R}$ when $c = 1/2$. (Can you also establish it for $c \approx .5269$?)
2. Show that if $\boldsymbol{X}$ is a random variable satisfying $\mathop{\bf E}[\boldsymbol{X}] = 0$ and $\|\boldsymbol{X}\|_4 < \infty$ then $\|a + \tfrac{1}{2} \boldsymbol{r} \boldsymbol{X}\|_4 \leq \|a + \boldsymbol{X}\|_4$ for all $a \in {\mathbb R}$, where $\boldsymbol{r} \sim \{-1,1\}$ is a uniformly random bit independent of $\boldsymbol{X}$. (Cf. Lemma 14.)
3. Establish the following improvement of Theorem 42 in the case of $q = 4$: for all $f \in L^2(\Omega^n, \pi^{\otimes n})$, \[ \|\mathrm{T}_{\frac12 \boldsymbol{r}} f({\boldsymbol{x}})\|_{4,\boldsymbol{r},{\boldsymbol{x}}} \leq \|f({\boldsymbol{x}})\|_{4, {\boldsymbol{x}}} \] (where ${\boldsymbol{x}} \sim \pi^{\otimes n}$, $\boldsymbol{r} \sim \{-1,1\}^n$).

1. Show that $\rho$ is an increasing function of $\lambda$. (Hint: one route is to reduce to showing that $\rho^2$ is a decreasing function of $u \in (0,\infty)$, reduce to showing that $q\tanh(u/q)$ is an increasing function of $q \in (1, \infty)$, reduce to showing $\frac{\tanh r}{r}$ is a decreasing function of $r \in (0,\infty)$, and reduce to showing $\sinh(2r) \geq 2r$.)
2. Verify the following statements from Remark 18: \begin{align*} \text{for fixed $q$ and $\lambda \to 1/2$,} \quad &\rho \to \frac{1}{\sqrt{q-1}}; \\ \text{for fixed $q$ and $\lambda \to 0$,} \quad &\rho \sim \lambda^{1/2 – 1/q}. \end{align*} Also show: \[ \text{for fixed $\lambda$ and $q \to \infty$,} \quad \rho \sim \sqrt{\frac{u}{\sinh u}} \sqrt{\frac{1}{q}}, \] and $\sqrt{\frac{u}{\sinh u}} \sim 2\lambda\ln(1/\lambda)$ for $\lambda \to 0$.
3. Show that $\rho \geq \frac{1}{\sqrt{q-1}} \lambda^{1/2-1/q}$ holds for all $\lambda$.

1. We consider the equivalent problem of minimizing $F(f) = \|f\|_p^p$ subject to $G(f) = \|\mathrm{T}_\rho f\|_2^2 = 1$. Show that both $F(f)$ and $G(f)$ are $\mathcal{C}^1$ functionals (identifying functions $f$ with points in ${\mathbb R}^\Omega$).
2. Argue from continuity that the minimum value for $\|f\|_p^p$ subject to $\|\mathrm{T}_\rho f\|_2^2 = 1$ is attained. Henceforth write $f_0$ to denote any minimizer; the goal is to show that $f_0$ takes on at most two values.
3. Show that $f_0$ is either everywhere nonnegative or everywhere nonpositive. (Hint: by homogeneity our problem is equivalent to maximizing $\|\mathrm{T}_\rho f\|_2$ subject to $\|f\|_p = 1$; now use Exercise 2.29.) Replacing $f_0$ by $|f_0|$ if necessary, henceforth assume $f_0$ is nonnegative.
4. Show that $\nabla F(f_0) = \pi \cdot p f_0^{p-1}$ and $\nabla G(f_0) = \pi \cdot 2 \mathrm{T}_{\rho^2} f_0$. Here $\pi \cdot g$ signifies the pointwise product of functions on $\Omega$, with $\pi$ thought of as a function $\Omega \to {\mathbb R}^{\geq 0}$. (Hint: for the latter, write $G(f) = \langle \mathrm{T}_{\rho^2} f, f \rangle$.)
5. Use the method of Lagrange Multipliers to show that $c f_0^{p-1} = T_{\rho^2} f_0$ for some $c \in {\mathbb R}^+$. (Hint: you’ll need to note that $\nabla G(f_0) \neq 0$.)
6. Writing $\mu = \mathop{\bf E}[f_0]$, argue that each value $y = f(\omega)$ satisfies the equation \begin{equation} \label{eqn:wolff-equation} c y^{p-1} = \rho^2 y + (1-\rho^2) \mu. \end{equation}
7. Show that \eqref{eqn:wolff-equation} has at most two solutions for $y \in {\mathbb R}^+$, thereby completing the proof that $f_0$ takes on at most two values. (Hint: strict concavity of $y^{p-1}$.)
8. Suppose $q > 2$. By slightly modifying the above argument, show that subject to $\|g\|_2 = 1$, every $g \in L^2(\Omega,\pi)$ which maximizes $\|\mathrm{T}_{\rho} g\|_q$ takes on at most two values (and there is at least one maximizing $g$). (Hint: at some point you might want to make the substitution $g = \mathrm{T}_\rho f$; note that $g$ is two-valued if $f$ is.)

1. Let’s introduce the notation $\alpha = \lambda^{1/p}$, $\beta = (1-\lambda)^{1/p}$. Show that \[ r^* = \frac{\alpha^p\beta^{2-p} - \alpha^{2-p}\beta^p}{\alpha^2-\beta^2}. \]
2. Let $f \in L^2(\Omega, \pi)$. Write $\mu = \mathop{\bf E}[f]$ and $\delta = \mathrm{D}_1 f = \hat{f}(1)$. Our goal will be to show \begin{equation} \label{eqn:lo-goal} \mu^2 + \delta^2 r^* = \|T_{\sqrt{r^*}} f\|_2^2 \leq \|f\|_p^2. \end{equation} In the course of doing this, we’ll also exhibit a nonconstant function $f$ which makes the above inequality sharp. Why does this establish that no larger value of $\rho$ is possible?
3. Show that without loss of generality we may assume \[ f(-1) = \frac{1+y}{\alpha}, \quad f(1) = \frac{1-y}{\beta} \] for some $-1 < y < 1$. (Hint: first use Exercise 2.29 and a continuity argument to show that we may assume $f > 0$; then use homogeneity of \eqref{eqn:lo-goal}.)
4. The left-hand side of \eqref{eqn:lo-goal} is now a quadratic function of $y$. Show that our $r^*$ is precisely such that \[ \text{LHS}\eqref{eqn:lo-goal} = Ay^2 + C \] for some constants $A, C$. I.e., $r^*$ makes the linear term in $y$ drop out. (Hint: work exclusively with the $\alpha, \beta$ notation and recall from Definition 8.44 that $\delta^2 = \lambda(1-\lambda)(f(1)-f(-1))^2 = \alpha^p \beta^p(f(1)-f(-1))^2$.)
5. Compute that \begin{equation} \label{eqn:loA} A = 2\frac{\beta^{p-1}-\alpha^{p-1}}{\beta-\alpha}. \end{equation} (Hint: you’ll want to multiply the above expression by $\alpha^p + \beta^p = 1$.)
6. Show that \[ \text{RHS}\eqref{eqn:lo-goal} = ((1+y)^p + (1-y)^p)^{2/p}. \] Why does it now suffice to show \eqref{eqn:lo-goal} just for $0 \leq y < 1$?
7. Let $y^* = \frac{\beta-\alpha}{\beta+\alpha} > 0$. Show that if $y = -y^*$ then $f$ is a constant function and both sides of \eqref{eqn:lo-goal} are equal to $\frac{4}{(\alpha+\beta)^2}$.
8. Deduce that both sides of \eqref{eqn:lo-goal} are equal to $\frac{4}{(\alpha+\beta)^2}$ for $y = y^*$. Verify that after scaling, this yields the following nonconstant function for which \eqref{eqn:lo-goal} is sharp: $f(x) = \exp(-xu/p)$.
9. Write $y = \sqrt{z}$ for $0 \leq z < 1$. By now we have reduced to showing \[ Az+C \leq ((1+\sqrt{z})^p + (1-\sqrt{z})^p)^{2/p}, \] knowing that both sides are equal when $\sqrt{z} = y^*$. Calling the expression on the right $\phi(z)$, show that \[ \frac{d}{dz} \phi(z)\Bigr|_{\sqrt{z}=y^*} = A. \] (Hint: you’ll need $\alpha^p+\beta^p = 1$, as well as the fact from part (h) that $\phi(z) = \frac{4}{(\alpha+\beta)^2}$ when $\sqrt{z}=y^*$.) Deduce that we can complete the proof by showing that $\phi(z)$ is convex for $z \in [0,1)$.
10. Show that $\phi$ is indeed convex on $[0,1)$ by showing that its derivative is a nondecreasing function of $z$. (Hint: use the Generalized Binomial Theorem as well as $1 < p < 2$ to show that $(1+\sqrt{z})^p + (1-\sqrt{z})^p$ is expressible as $\sum_{j=0}^\infty b_j z^j$ where each $b_j$ is positive.)

1. Let $\Phi : [0, \infty) \to {\mathbb R}$ be defined by $\Phi(x) = x \ln x$, where we take $0\ln0 = 0$. Verify that $\Phi$ is a smooth, strictly convex function.
2. Consider the following:

   Definition 47 Let $g \in L^2(\Omega, \pi)$ be a nonnegative function. The entropy of $g$ is defined by \[ \mathbf{Ent}[g] = \mathop{\bf E}_{{\boldsymbol{x}} \sim \pi}[\Phi(g({\boldsymbol{x}}))] – \Phi\Bigl(\mathop{\bf E}_{{\boldsymbol{x}} \sim \pi}[g({\boldsymbol{x}})]\Bigr). \]

   Verify that $\mathbf{Ent}[g] \geq 0$ always, that $\mathbf{Ent}[g] = 0$ if and only if $g$ is constant, and that $\mathbf{Ent}[c g] = c\mathbf{Ent}[g]$ for any constant $c \geq 0$.

3. Suppose $\varphi$ is a probability density on $\{-1,1\}^n$ (recall Definition 1.20). Show that $\mathbf{Ent}[\varphi] = D_{\mathrm{KL}}(\varphi || \pi_{1/2}^{\otimes n})$, the Kullback–Leibler divergence of the uniform distribution from $\varphi$ (more precisely, the distribution with density $\varphi$).

The Log-Sobolev Inequality Let $f: \{-1,1\}^n \to {\mathbb R}$. Then ${\tfrac{1}{2} \mathbf{Ent}[f^2] \leq \mathbf{I}[f]}$.

1. Writing $\rho = \exp(-t)$, the $(p,2)$-Hypercontractivity Theorem tells us that \[ \|\mathrm{T}_{\exp(-t)} f\|_2^2 \leq \|f\|^2_{1+\exp(-2t)} \] for all $t \geq 0$. Denote the left- and right-hand sides as $\textrm{LHS}(t)$, $\textrm{RHS}(t)$. Verify that these are smooth functions of $t \in [0,\infty)$ and that $\textrm{LHS}(0) = \textrm{RHS}(0)$. Deduce that $\textrm{LHS}'(0) \leq \textrm{RHS}'(0)$.
2. Compute $\textrm{LHS}'(0) = -2 \mathbf{I}[f]$. (Hint: pass through the Fourier representation.)
3. Compute $\textrm{RHS}’(0) = -\mathbf{Ent}[f^2]$, thereby deducing the Log-Sobolev Inequality. (Hint: as an intermediate step, define $F(t) = \mathop{\bf E}[|f|^{1+\exp(-2t)}]$ and show that $\textrm{RHS}’(0) = F(0)\ln F(0) + F’(0)$.)

1. Let $f : \{-1,1\}^n \to {\mathbb R}$. Show that $\mathbf{Ent}[(1+\epsilon f)^2] \sim 2 \mathop{\bf Var}[f] \epsilon^2$ as $\epsilon \to 0$.
2. Deduce the Poincaré Inequality for $f$ from the Log-Sobolev Inequality.

1. Deduce from the Log-Sobolev Inequality that for $f : \{-1,1\}^n \to \{-1,1\}$ with $\alpha = \min\{\mathop{\bf Pr}[f = 1], \mathop{\bf Pr}[f=-1]\}$, \begin{equation} \label{eqn:weak-edge-iso} 2 \alpha \ln(1/\alpha) \leq \mathbf{I}[f]. \end{equation} This is off by a factor of $\ln 2$ from the optimal edge-isoperimetric inequality Theorem 2.38. (Hint: apply the inequality to either $\tfrac{1}{2} – \tfrac{1}{2} f$ or $\tfrac{1}{2} + \tfrac{1}{2} f$.)
2. Give a more streamlined direct derivation of \eqref{eqn:weak-edge-iso} by differentiating the Small-Set Expansion Theorem.

1. The first step is to establish the $n = 1$ case. Towards this, show that we may assume $f : \{-1,1\} \to {\mathbb R}$ is nonnegative and has mean $1$. (Hint: Exercise 22(b).)
2. Thus it remains to establish $\tfrac{1}{2} \mathbf{Ent}[(1+b{\boldsymbol{x}})^2] \leq b^2$ for $b \in [-1,1]$. Show that $g(b) = b^2 – \tfrac{1}{2} \mathbf{Ent}[(1+b{\boldsymbol{x}})^2]$ is smooth on $[-1,1]$ and satisfies $g(0) = 0$, $g’(0) = 0$, and $g”(b) = \frac{2b^2}{1+b^2} + \ln\frac{1+b^2}{1-b^2} \geq 0$ for $b \in (-1,1)$. Explain why this completes the proof of the $n = 1$ case of the Log-Sobolev Inequality.
3. Show that for any two functions $f_+, f_- : \{-1,1\}^n \to {\mathbb R}$, \[ \left(\tfrac{\sqrt{\mathop{\bf E}[f_+^2]} – \sqrt{\mathop{\bf E}[f_-^2]}}{2}\right)^2 \leq \mathop{\bf E}\left[\Bigl(\tfrac{f_+ - f_-}{2}\Bigr)^2\right]. \] (Hint: the triangle inequality for $\| \cdot \|_2$.)
4. Prove the Log-Sobolev Inequality via “induction by restrictions” (as described in Section 9.4). (Hint: for the right-hand side, establish $\mathbf{Inf}[f] = \mathop{\bf E}[(\tfrac{f_+ - f_-}{2})^2] + \tfrac{1}{2} \mathbf{I}[f_+] + \tfrac{1}{2} \mathbf{I}[f_-]$. For the left-hand side, apply induction, then the $n = 1$ base case, then part (c).)

1. By following the strategy of Exercise 23, establish the following:

   Log-Sobolev Inequality for general product space domains Let $f \in L^2(\Omega^n, \pi^{\otimes n})$ and write $\lambda = \min(\pi)$, $\lambda’ = 1-\lambda$, $\exp(-u) = \frac{\lambda}{\lambda’}$. Then $ \tfrac{1}{2} \varrho \mathbf{Ent}[f^2] \leq \mathbf{I}[f]$, where \[ \varrho = \varrho(\lambda) = \frac{\tanh(u/2)}{u/2} = 2 \frac{\lambda' - \lambda}{\ln \lambda' - \ln \lambda}. \]

2. Show that $\varrho(\lambda) \sim 2/\ln(1/\lambda))$ as $\lambda \to 0$.
3. Let $f : \{-1,1\}^n \to \{-1,1\}$ and treat $\{-1,1\}^n$ as having the $p$-biased distribution $\pi_p^{\otimes n}$. Write $q = 1-p$. Show that if $\alpha = \min\{\mathop{\bf Pr}_{\pi_p}[f = 1], \mathop{\bf Pr}_{\pi_p}[f = -1]\}$ then \[ 4\frac{q - p}{\ln q - \ln p} \alpha \ln(1/\alpha) \leq \mathbf{I}[f^{(p)}] \] and hence, for $p \to 0$, \begin{equation} \label{eqn:weak-p-biased-isoperim} \alpha \log_p \alpha \leq (1+o_p(1))p \cdot \mathop{\bf E}_{{\boldsymbol{x}} \sim \pi_p^{\otimes n}}[\mathrm{sens}_f({\boldsymbol{x}})]. \end{equation} We remark that \eqref{eqn:weak-p-biased-isoperim} is known to hold without the $o_p(1)$ for all $p \leq 1/2$.

1. Let $p = \frac1n$ and let $f \in L^2(\{-1,1\}^n, \pi_p^{\otimes n})$ be any boolean-valued function. Show that $\mathbf{I}[f] \leq 4$. (Hint: Proposition 8.45.)
2. Let us specialize to the case $f = \chi_{[n]}$. Show that $f$ is not $.1$-close to any width-$O(1)$ DNF (under the $\frac1n$-biased distribution, for $n$ sufficiently large). This shows that the assumption of monotonicity can’t be removed from Friedgut’s Conjecture. (Hint: show that fixing any constant number of coordinates cannot change the bias of $\chi_{[n]}$ very much.)

1. Prove that the critical property $p_c$ satisfies $p_c \leq O(1/v)$. I.e., establish that there is a universal constant $C$ such that $\mathop{\bf Pr}[\boldsymbol{G} \sim \mathcal{G}(v, C/v) \text{ is } 3\text{-colourable}] = o_n(1)$. (Hint: union-bound over all potential $3$-colourings.)
2. Towards showing (non-)$3$-colourability has a sharp threshold, suppose the property had constant total influence at the critical probability. Bourgain’s Sharp Threshold Theorem would imply that there is a $\tau$ of constant magnitude such that for $\boldsymbol{G} \sim \mathcal{G}(v,p_c)$, there is a $|\tau|$ chance that $\boldsymbol{G}$ contains a $\tau$-boosting induced subgraph $\boldsymbol{G}_T$. There are two cases, depending on the sign of $\tau$. It’s easy to rule out that the boost is in favour of $3$-colourability; the absence of a few edges shouldn’t increase the probability of $3$-colourability by much (cf. Exercise 41). On the other hand, it might seem plausible that the presence of a certain constant number of edges should boost the probability of non-$3$-colourability by a lot. For example, the presence of a $4$-clique immediately boosts the probability to $1$. However, the point is that at the critical probability it is very unlikely that $\boldsymbol{G}$ contains a $4$-clique (or indeed, any “local” witness to non-$3$-colourability). Short of showing this, prove at least that the expected number of $4$-cliques in $\boldsymbol{G} \sim \mathcal{G}(v,p)$ is $o_v(1)$ unless $p = \Omega(v^{-2/3}) \gg p_c$.