Let be a function on the -Biased Cube
with Degree of a Boolean Function at most .
Then
Proof
By induction on .
Let and as in Discrete Derivative.
By orthogonality:
Note also that has degree at most as
So
We can drop the second term as .
Also .
In the case we can also drop the third term and have .
In general note:
Now use Hölder inequality to find
and apply inductive step:
Apply
with and to find
and
Finally, choose such that and i.e. will do and
Corollary
Let (i.e. )
Then for every and Noise operator we have
Proof
where the last inequality is Jensen’s Inequality and the last line is Pythagoras.
We are done by Tensor Power Trick.
Corollary
Let and .
Then
Proof
Use
and note that the Noise operator is self-Adjoint so
If then so for some i.e.
as is the dual of
(or we can just say by Hölder inequality which suffices).
Corollary
Proof