Fourier expansion of boolean functions

In summary, boolean functions on n variables can be represented as a Fourier expansion using the group ##\mathbb {Z_2^n}##, but an alternate version using ##\mathbb {Z_{2^n}}## is not as suitable because it maps a single number to the set ##\mathbb {Z_2}## rather than a vector of length n.
  • #1
Dragonfall
1,030
4
Any boolean function on n variables can be thought of as a function

[tex]f : \mathbb{Z}_2^n \rightarrow \mathbb{Z}_2[/tex]

which can be written as

[tex]f(x) = \sum_{s \in \mathbb{Z}_2^n} \hat{f}(s) \prod_{i : x_i = 1} (-1)^{x_i}[/tex]

where

[tex]\hat{f}(s) = \mathbb{E}_t \left[ f(t) \prod_{i : s_i = 1} (-1)^{t_i} \right][/tex]

This is the Fourier expansion of a boolean function. But this uses the group [itex]\mathbb{Z}_2^n[/itex]. Why not use [itex]\mathbb{Z}_{2^n}[/itex]? Characters of the latter would be nice looking roots of unity on the complex circle, instead of points on an [itex]n[/itex]-cube.

EDIT: You know what, nevermind. I don't even understand my own question anymore.
 
Last edited:
Mathematics news on Phys.org
  • #2
Dragonfall said:
This is the Fourier expansion of a boolean function. But this uses the group [itex]\mathbb{Z}_2^n[/itex]. Why not use [itex]\mathbb{Z}_{2^n}[/itex]?
Because the function maps vectors of length n whose components are all either 0 or 1, to a set containing 0 and 1 (##\mathbb {Z_2}##). Your alternate version would map a single number in the set ##\{0, 1, \dots, 2^n - 1\}## to ##\mathbb {Z_2}##.
 

FAQ: Fourier expansion of boolean functions

What is Fourier expansion of boolean functions?

The Fourier expansion of boolean functions is a mathematical technique used to represent a boolean function as a sum of simpler functions. It is based on the idea that any boolean function can be expressed as a linear combination of certain basis functions, known as the Fourier basis functions.

How is Fourier expansion useful in computer science?

Fourier expansion is useful in computer science as it allows for efficient computation of boolean functions, especially in the field of digital signal processing. It also has applications in areas such as error-correcting codes, cryptography, and machine learning.

What are the key components of Fourier expansion?

The key components of Fourier expansion are the boolean function being expanded, the Fourier basis functions, and the coefficients used to express the function as a linear combination of the basis functions. The Fourier basis functions are typically sinusoidal functions, and the coefficients are complex numbers.

How does Fourier expansion relate to Fourier analysis?

Fourier expansion is closely related to Fourier analysis, which is a mathematical technique used to decompose a function into its constituent frequencies. Fourier expansion can be seen as a special case of Fourier analysis, where the function being analyzed is a boolean function.

Can Fourier expansion be used for functions with multiple variables?

Yes, Fourier expansion can be used for functions with multiple variables by using the concept of multi-dimensional Fourier expansion. This involves using basis functions that are products of one-dimensional Fourier basis functions and considering each variable separately.

Similar threads

Replies
6
Views
1K
Replies
10
Views
2K
Replies
4
Views
2K
Replies
3
Views
1K
Back
Top