Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Fourier expansion of boolean functions

  1. Mar 4, 2014 #1
    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]


    [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: Mar 4, 2014
  2. jcsd
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Can you help with the solution or looking for help too?
Draft saved Draft deleted

Similar Discussions: Fourier expansion of boolean functions
  1. Boolean Functions (Replies: 8)

  2. Boolean functions (Replies: 13)