The -biased cube is the set with measure
where for each we have ,
and are all independent.
We can also have the biased cube on where now instead.
In the case of we define:
To normalize we introduce where
We will also write and for
(which are the Characters for this group)
For any write
Also define for :
Convention
Sometimes we will write to signify that all expectations should be considered in the -biased case.
Lemma
For any we have
Proof
Lemma
Let be a multilinear function.
Then
Proof 1
Write
where is the Discrete Fourier Transform on Boolean Functions of .
Then
Proof 2
Write
where is the Discrete Fourier Transform on the Biased Cube of .
Then
because .
Proof 3
By induction on .
where we used multilinearity in the last coordinate and the induction hypothesis.