Register to reply

Fourier expansion of boolean functions

by Dragonfall
Tags: boolean, expansion, fourier, functions
Share this thread:
Mar4-14, 09:05 PM
Dragonfall's Avatar
P: 993
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.
Phys.Org News Partner Mathematics news on
Heat distributions help researchers to understand curved space
Professor quantifies how 'one thing leads to another'
Team announces construction of a formal computer-verified proof of the Kepler conjecture

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