Introduction to Fourier Transform of Boolean Function
# Introduction and Definition
Hello! Today we will be introducing Fourier transform on Boolean functions including its intuition, definition, and computation. A Fourier transform of Boolean functions has a unique expansion as a multilinear polynomial (a polynomial where each variable has degree one). This is categorized as a type of discrete Fourier transform, but its underlying motivation are similar to the continuous Fourier transform.
This is a fairly new topics for most of us. Therefore, I would like to slowly build up the definition by clarifying each supplementary concept along the way and provide some intuition as well.
Let us first introduce the vector space of functions
An inner product associates a pair of vectors to a scalar quantity, a common example would be the Euclidean dot product. An inner product is usually defined as a bilinear map
Once we have defined the vector space and inner product, we can define the basis with size
Theorem 1: The formula for Fourier transform stated that every function
# Exploring Interesting Properties of Basis
The following proofs can be found in Dr. Ryan O'Donnell's book "Analysis of Boolean Functions", specifically chapter 1.3. He also teaches such course at Carnegie Mellon University and all lectures are available online.
Theorem 2: An n-dimensional Boolean function has a vector space with dimension
Proof: We know that an n-dimensional Boolean function has
Lemma 1: The number of functions in
Proof: There exist
Lemma 2: For
Proof: We proceed by solving
Lemma 3: If
Proof: We see that every function in the form of
# Compute Fourier Transform for the Majority Function
We will demonstrate the process of computing the Fourier transform of the majority function that we mentioned in the previous post. We will look at a 3-dimensional majority function.
Step 1: Calculate
Step 2: Compute the Fourier Coefficient as follows:
Therefore through Fourier transform and given all the Fourier Coefficient, we can express our Majority function in dimension three as a multilinewar function
Some Notes and Interesting Facts:
- As long as we follow the above algorithm for finding the Fourier transform, our polynomial will always be multilinear.
- Every Boolean function can be uniquely expressed as a multilinear polynomial. (Hopefully we can prove the uniqueness later on).
- It seems like by adding up the square of each coefficient, the result will always be
. For example, for the majority function above, . I currently have no way to verify this yet, but it seems to work with every Fourier transform that I have tried so far and it reminds me of the formula for computing the distance in a space. I will try to find some supporting evidence, and hopefully readers can shed some lights on such observation as well.