I was recently reading about Fourier dimension of Boolean functions. What I understand is that if we take the Fourier expansion of $f: \{\pm1\}^n \to \{\pm1\}$ and consider the monomials with non zero Fourier coefficients as vectors in $\mathbb{F}_2^n$, then the Fourier dimension is the dimension of the span of these vectors.

This might help to understand when a Boolean function is "reduceable" or "equivalent" to another one. For example, if we replace a variable with a product of say $m$ variables, then in the vectors of the corresponding monomials, those $m$ places will be $1$ or $0$ together. This gives us that the Fourier dimension remains unchanged in such a transformation.

My question is for what kind of variable transformations does the Fourier dimension remain unchanged?

  • $\begingroup$ It's probably linear-invariant or even affine-invariant. $\endgroup$ May 12, 2022 at 5:20
  • $\begingroup$ @YuvalFilmus would it be invariant under product or composition of $f$ with itself? $\endgroup$ May 14, 2022 at 7:26
  • 1
    $\begingroup$ Why not check it using some examples? $\endgroup$ May 14, 2022 at 10:20


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.