Fourier expansion of boolean functions

Click For Summary
SUMMARY

The discussion focuses on the Fourier expansion of boolean functions, specifically how any boolean function on n variables can be expressed using the formula f(x) = ∑_{s ∈ ℤ₂ⁿ} 𝑓̂(s) ∏_{i : x_i = 1} (-1)^{x_i}. The Fourier coefficients 𝑓̂(s) are defined as 𝑓̂(s) = E_t [f(t) ∏_{i : s_i = 1} (-1)^{t_i}]. A question arises regarding the potential use of the group ℤ_{2ⁿ} instead of ℤ₂ⁿ, suggesting that the latter could provide aesthetically pleasing roots of unity on the complex circle. However, the original formulation is retained due to the nature of the function mapping vectors of length n to a binary set.

PREREQUISITES
  • Understanding of boolean functions and their properties
  • Familiarity with Fourier analysis concepts
  • Knowledge of group theory, specifically ℤ₂ⁿ and ℤ_{2ⁿ}
  • Basic proficiency in mathematical notation and expectations in probability (E_t)
NEXT STEPS
  • Research the implications of using ℤ_{2ⁿ} in Fourier analysis of boolean functions
  • Explore advanced topics in group theory related to character theory
  • Study applications of Fourier expansions in computer science and cryptography
  • Learn about the relationship between boolean functions and their representations in different mathematical frameworks
USEFUL FOR

Mathematicians, computer scientists, and researchers interested in theoretical computer science, particularly those focusing on boolean functions and their applications in algorithms and cryptography.

Dragonfall
Messages
1,023
Reaction score
5
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
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}##.
 

Similar threads

  • · Replies 4 ·
Replies
4
Views
3K
  • · Replies 1 ·
Replies
1
Views
2K
  • · Replies 0 ·
Replies
0
Views
4K
  • · Replies 14 ·
Replies
14
Views
5K
  • · Replies 4 ·
Replies
4
Views
4K
  • · Replies 3 ·
Replies
3
Views
2K
  • · Replies 13 ·
Replies
13
Views
2K
  • · Replies 2 ·
Replies
2
Views
2K
  • · Replies 1 ·
Replies
1
Views
3K
  • · Replies 7 ·
Replies
7
Views
2K