Register to reply

Fourier expansion of boolean functions

by Dragonfall
Tags: boolean, expansion, fourier, functions
Share this thread:
Dragonfall
#1
Mar4-14, 09:05 PM
Dragonfall's Avatar
P: 995
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.
Phys.Org News Partner Mathematics news on Phys.org
'Moral victories' might spare you from losing again
Fair cake cutting gets its own algorithm
Effort to model Facebook yields key to famous math problem (and a prize)

Register to reply

Related Discussions
When to use fourier integral instead of fourier series expansion Classical Physics 2
Boolean functions General Math 13
Logic circuits for boolean functions Engineering, Comp Sci, & Technology Homework 7
One wayness of boolean functions General Math 4
Boolean Functions General Math 8