# Introduction to Fourier Transform of Boolean Function

*Brian Li*

*2020-05-20*

*MAT388 Boolean Function Fourier Transform Mathematics Card Shuffling*

## # 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 **inner product**

Once we have defined the vector space and inner product, we can define the basis with size

Let **"Fourier Basis"**, which is stated and proven in theorem 3 below.

**Theorem 1**: The formula for **Fourier transform** stated that every function **Fourier coefficient**.

## # 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**: If

**Theorem 3**:

**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

Recall that

Maj | |||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|

-1 | -1 | -1 | -1 | 1 | -1 | -1 | -1 | 1 | 1 | 1 | -1 |

-1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | -1 | -1 | 1 | 1 |

-1 | -1 | 1 | -1 | 1 | -1 | 1 | -1 | -1 | 1 | -1 | 1 |

-1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 | 1 | -1 | -1 | 1 |

1 | 1 | 1 | -1 | 1 | 1 | 1 | -1 | 1 | -1 | -1 | -1 |

1 | -1 | 1 | 1 | 1 | -1 | 1 | 1 | -1 | -1 | 1 | -1 |

1 | 1 | -1 | 1 | 1 | 1 | -1 | 1 | -1 | 1 | -1 | -1 |

1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |

**Step 2**: Compute the **Fourier Coefficient** as follows:

Similarily,

Similarily,

And

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.