What are all the functions $f:\{0,1\}^n\rightarrow\{0,1\}$ that can be expressed as a product of affine Boolean functions? For example, if $x_1,x_2,x_3\in\{0,1\}$ then $x_1x_2x_3\oplus x_2x_3 \oplus x_2=(x_1\oplus x_2)(x_1\oplus 1)(x_3\oplus 1)$. Here $\oplus$ denotes the XOR operation.

I would guess that not any function can be written this way. Has this been worked out? Is there any normal form other than algebraic normal form that uses the XOR (not counting the Fourier transform)?

  • 1
    $\begingroup$ Well, more-or-less by definition, $f$ is expressible in this form iff $f^{-1}(1)$ (or $f^{-1}(0)$, doesn’t matter) is an affine subspace of $\mathbb F_2^n$. $\endgroup$ Sep 17, 2021 at 4:20
  • 1
    $\begingroup$ No, sorry, it does matter: $f^{-1}(1)$, not $f^{-1}(0)$. $\endgroup$ Sep 17, 2021 at 4:29


Your Answer

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

Browse other questions tagged or ask your own question.