Dragonfall
- 1,023
- 5
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.
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.
Last edited: