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

Have something to add?
Draft saved Draft deleted
Similar Discussions: Fourier expansion of boolean functions
  1. Boolean Functions (Replies: 8)

  2. Boolean functions (Replies: 13)