
\documentclass[11pt]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{hyperref}
\newtheorem{define}{Definition}

\newtheorem{example}{Example}



%\newcommand{\Z}{{\bf Z}}
%\usepackage{psfig}

\oddsidemargin=0.15in
\evensidemargin=0.15in
\topmargin=-.5in
\textheight=9in
\textwidth=6.25in

\input{defs.tex}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Definitions: If you want to add definitions commands and macros to the
%% scribe, please do it in this space

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% Heading: In the parentheses below, write the sequential number of the
%% talk, the talk date, the name of the speaker, and the name or names of
%% whoever wrote the scribe (seperated by commas).

\lecture{12}{May 26, 2008}{Guy Kindler}{Ori Gurel-Gurevich}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%  Body: from here on it's your territory - write your scribe here.

So far, we used elementary techniques. Today we will do something
less elementary, for the first time.

\section*{Reminders and Preliminaries}

\begin{definition}
The \emph{$L_p$-norm} of a function $f:\{\pm 1\}^n\rightarrow \R$ is
$$\|f\|_p=(\E[|f(x)|^p])^{1/p}$$
for $1\le p < \infty$ and
$$\|f\|_\infty=\max_{x\in \{\pm 1\}^n} |f(x)|$$
\end{definition}

\noindent We already proved \emph{monotonicity}: if $p<q$ then
$\|f\|_p \le \|f\|_q$.

\noindent We also have \emph{continuity in $p$}: $\lim_{p
\rightarrow q} \|f\|_p  = \|f\|_q$. This includes the case
$q=\infty$.

\begin{definition}
$R:\R^{\{\pm 1\}^n} \rightarrow \R^{\{\pm 1\}^n}$ is a \emph{linear
transformation} if for any $f,g \in \{\pm 1\}^n$ and $\lambda \in
\R$ we have
$$R(f+g)=R(f)+R(g)$$
and
$$R(\lambda f)= \lambda R(f)$$
\end{definition}


\begin{definition}
$R$ is \emph{$p$-contractive} if for all $f \in \R^{\{\pm 1\}^n}$ we
have

$$\|R(f)\|_p \le \|f\|_p$$
\end{definition}

\begin{definition}
$R$ is \emph{$p\rightarrow q$-hypercontractive} if for all $f \in
\R^{\{\pm 1\}^n}$ we have

$$\|R(f)\|_q \le \|f\|_p$$
\end{definition}

$p \rightarrow p$-hypercontractivity is just $p$-contractivity. If
$R$ is $p\rightarrow q$-hypercontractive then for any $p\le p' \le
q' \le q$ we have that $R$ is $p' \rightarrow q'$-hypercontractive,
since, by monotonicity $\|R(f)\|_{q'} \le \|R(f)\|_q \le \|f\|_p \le
\|f\|_{p'}$.

\begin{definition}
Given an indexed set of real numbers $A = \{a_S\}_{S\subset [n]}$
define the transform
$$T_A(f)=\sum_S a_S \hat{f}(S) \chi_S$$
\end{definition}

If for all $S$ we have $|a_S| \le 1$ then $T_A$ is $2$-contractive,
but not necessarily $p$-contractive for $p\ne 2$, as we have seen in
the exercise. An interesting question is for which $A$ and which
$p,q$ is $T_A$ (hyper)contractive.

\begin{example}
If we take $a_S = 1$ if $|S|\le k$ and 0 otherwise, we get that
$T_A(f)=f^{\le k}$.
\end{example}

We already used this transformation.

\begin{example}
The \emph{Rademacher projection} is the transform
$$Rad(f)=f^{=1}=\sum_i \hat{f}(i) \chi_i$$
\end{example}


\begin{theorem}
For all $2\le p$ we have
$$\|Rad(f)\|_p \le \sqrt{p-1} \|f\|_2$$
\end{theorem}

If we replace $\sqrt{p-1}$ by $\sqrt{p}$, and require $p$ to be
even, then what we get follows from part 3 of exercise 3.

\section*{The Bonami-Beckner Transform}


\begin{definition}
For $0\le \delta \le 1$ the \emph{Bonami-Beckner Transform} is
defined by
$$T_\delta(f) = \sum_S \delta^{|S|} \hat{f}(S) \chi_S \ .$$
\end{definition}

For which $\delta$ is $T_\delta$ (hyper)contractive?

\begin{claim}
$T_\delta$ is $p$-contractive for all $0\le \delta \le 1$ and all $p
\ge 1$.
\end{claim}

\begin{proof}
Consider the transform

$$T'_\delta(f) = \E_{z\sim \mu^{(n)}_{(1-\delta)/2}} [f(z x)]$$

A straightforward computation reveals that

$$T'_\delta(f)(x)= \sum_S \hat{f}(S) \chi_S(x) \E_{z\sim \mu^{(n)}_{(1-\delta)/2}}
[\chi_S(z)]= \sum_S \hat{f}(S) \chi_S(x) \delta^{|S|} =
T_\delta(f)(x)$$ so these two transforms are one. $T'_\delta$ can
also be written as
$$T'_\delta(f)=\E_{z\sim \mu^{(n)}_{(1-\delta)/2}} [\sigma_z(f)] \ ,$$
where $\sigma_z$ is the shift by $z$ on the hypercube.

Since $\|\sigma_z(f)\|_p=\|f\|_p$ for any $z$ and $\|\cdot\|_p$ is
convex we have
$$\|T'_\delta(f)\|_p=\|\E_{z\sim \mu^{(n)}_{(1-\delta)/2}} [\sigma_z(f)]\|_p \le \E_{z\sim \mu^{(n)}_{(1-\delta)/2}} \|\sigma_z(f)\|_p =
\|f\|_p$$
\end{proof}

\begin{theorem}[Bonami 72', Beckner 73']
For $1\le p \le q $ and $\delta \le \sqrt{\frac{p-1}{q-1}}$ we have

$$\|T_\delta(f)\|_q \le \|f\|_p$$

\end{theorem}

We will not prove this theorem, but it can be done by induction on
$n$. However, even the base case ($n=1$) is far from trivial.
Instead, we will see what can be done with it.

\begin{corollary} \label{cor1}
If $1\le 2 \le q <\infty$ then
$$\|f^{\le k}\|_q \le (q-1)^{k/2} \|f\|_2$$
$$\|f^{\le k}\|_2 \le (p-1)^{-k/2} \|f\|_p$$
\end{corollary}


\begin{proof}
We prove the second inequality, the first is similar.

Take $\delta=\sqrt{p-1}$. Then,
$$\|f\|_p \ge \|T_\delta (f)\|_2 = \sqrt{\sum_S \delta^{2|S|}
\hat{f}^2(S)} \ge \sqrt{\sum_{|S|\le k} \delta^{2|S|} \hat{f}^2(S)}
\ge \sqrt{\sum_{|S|\le k} \delta^{2 k} \hat{f}^2(S)} = \delta^k
\|f^{\le k}\|_2$$
\end{proof}

Next, we use the corollary to prove some cool stuff about the
influence of low degree functions.

\begin{corollary}
Let $f:\{\pm 1\}^n \rightarrow \{\pm 1\}$ be a Boolean function of
degree at most $k$. Then for each $i$ either
$$I_i(f)=0 \qquad \text{or} \qquad I_i(f)\ge 8^{-k}$$
\end{corollary}

\begin{proof}
Define
$$f_i(x)=\frac{f(x)-f(\sigma_i x)}{2} \ .$$

Since $f$ is Boolean, we have $|f_i(x)|=1$ if $f(x)\ne f(\sigma_i
x)$ and 0 otherwise. Therefore, for every $1\le p$
$$\|f_i\|_p^p = I_i(f) \ .$$

By corollary \ref{cor1}, taking $p=3/2$, we have
$$\|f_i\|_2 \le 2^{k/2}\|f_i\|_{3/2} \ .$$

Putting these together yields
$$I_i(f) \le 2^k \|f_i\|_{3/2}^2 = 2^k (I_i(f))^{4/3} \ ,$$
so either $I_i(f)=0$ or we can divide by it getting
$$I_i(f)\ge 8^{-k} \ .$$
\end{proof}


Since $\sum_i I_i(f) = \sum_S |S| \hat{f}^2(S) \le k$ we get one
final corollary.

\begin{corollary}
Let $f:\{\pm 1\}^n \rightarrow \{\pm 1\}$ be a Boolean function of
degree at most $k$. Then the number of influencing variables is at
most $k 8^k$.
\end{corollary}

{\bf note:} one can actually get a better exponent basis in this
bound, but some exponent is necessary (exercise).



%\section{A proof of some theorem}
%
%In this talk we prove the following theorem.
%\begin{theorem}
%    This is a wonderful scribe indeed!
%\end{theorem}
%\begin{proof}
%    Suppose for the sake of contradiction that this scribe is not
%    wonderful. To put it formally, we write
%    \begin{equation}
%        \label{eq:not wonderful}
%        This\ scribe\neq\ wonderful.
%    \end{equation}
%    However, all scribes for this course are wonderful, in conradiction with~\eqref{eq:not wonderful}.
%\end{proof}

\end{document}
