# Fourier expansion of boolean functions

by Dragonfall
Tags: boolean, expansion, fourier, functions
 P: 995 Any boolean function on n variables can be thought of as a function $$f : \mathbb{Z}_2^n \rightarrow \mathbb{Z}_2$$ which can be written as $$f(x) = \sum_{s \in \mathbb{Z}_2^n} \hat{f}(s) \prod_{i : x_i = 1} (-1)^{x_i}$$ where $$\hat{f}(s) = \mathbb{E}_t \left[ f(t) \prod_{i : s_i = 1} (-1)^{t_i} \right]$$ This is the Fourier expansion of a boolean function. But this uses the group $\mathbb{Z}_2^n$. Why not use $\mathbb{Z}_{2^n}$? Characters of the latter would be nice looking roots of unity on the complex circle, instead of points on an $n$-cube. EDIT: You know what, nevermind. I don't even understand my own question anymore.