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: 994
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
Math journal puts Rauzy fractcal image on the cover
Heat distributions help researchers to understand curved space
Professor quantifies how 'one thing leads to another'

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