2
$\begingroup$

Given a Boolean function $f:\{-1,1\}^n\rightarrow \{-1,1\}$, it is well know that the Fourier decomposition of $f$ can be written as $f(x)=\sum_{S\subseteq \{1,\ldots,n\}} \widehat{f}(S) \prod_{i\in S} x_i$ where $\widehat{f}(S)$ are the Fourier coefficients. So the quantity $\prod_{i\in S} x_i$ can be viewed as the parity of $x\in \{-1,1\}^n$ when restricted to $S\subseteq [n]$.

Is there a way to write the Fourier decomposition in terms of the AND of its variables, i.e., is it possible to express every Boolean function $f$ in terms of $f(x)=\sum_{S\subseteq \{1,\ldots,n\}} \widehat{f}(S) AND(x_{S})$? Can this be generalized even further? In general, can any polynomial $p:\{-1,1\}^n\rightarrow \mathbb{R}$ be written in terms of an "AND" decomposition instead of a parity decomposition (in the Fourier sense).

$\endgroup$
2
  • $\begingroup$ The nice thing about the XOR basis is that it's automatically orthogonal. You don't get that with AND. $\endgroup$
    – Aryeh
    Commented Apr 10, 2018 at 21:48
  • 3
    $\begingroup$ You can write every function as a linear combination of ANDs of its variables. If you change your variables to being in $\{0,1\}$ instead of $\{-1,1\}$ (this is just a linear transformation), and then simplify the resulting polynomial, you will have written it as a linear combination of ANDs, because each monomial will be the logical AND of all the variables involved in that monomial. $\endgroup$ Commented Apr 10, 2018 at 22:07

1 Answer 1

2
$\begingroup$

As pointed out in the comments if $u\in \{\pm 1\}$ then $x=x(u) \in \{0,1\}$ where $$x(u)=\frac{1-u}{2},$$ with $x(-1)=1,$ and $x(1)=0.$ This will then yield $$f(x)=2^{n-1}f(0)-\frac{1}{2} \sum_{S \in \{1,\ldots,n\}} \hat{f}(S) \prod_{i \in S} x_i,$$ and if we denote the $\{0,1\}$ valued version of $f$ as $\tilde{f},$ $$\frac{1-\tilde{f}(x)}{2}=2^{n-1}f(0)-\frac{1}{2} \sum_{S \in \{1,\ldots,n\}} \hat{f}(S) \prod_{i \in S} x_i,$$ leading to $$\frac{\tilde{f}(x)}{2}=\frac{1}{2}\left[1+ \sum_{S \in \{1,\ldots,n\}} \hat{f}(S) \prod_{i \in S} x_i\right]-2^{n-1}f(0),$$ or $$\tilde{f}(x)=1-2^{n}f(0)+\sum_{S \in \{1,\ldots,n\}} \hat{f}(S) \prod_{i \in S} x_i,$$ if I haven't made any errors along the way.

$\endgroup$
5
  • $\begingroup$ I am not entirely sure about your derivation, but I may be misreading what you did. You start with the "usual" Fourier representation (for $u\in\{-1,1\}^n$) of $f(u) = \sum_{S\subseteq \{1,\dots,n\}}\hat{f}(S) \prod_{i\in S} u_i$, from which you can write, for $x\in\{0,1\}^n$ and slightly abusing notation for $f$, now seen as $f\colon\{0,1\}^n\to\{-1,1\}$, $$f(x) = \sum_{S\subseteq \{1,\dots,n\}}\hat{f}(S) \prod_{i\in S} (2x_i-1)$$ How do you get your first line from expanding this? $\endgroup$
    – Clement C.
    Commented Apr 11, 2018 at 22:45
  • $\begingroup$ It's a kind of initial value property, so $\sum_{S\subseteq \{1,\ldots,n\}} \hat{f}(S)=f(0),$ but I missed the $f(0),$ thanks. $\endgroup$
    – kodlu
    Commented Apr 11, 2018 at 22:53
  • $\begingroup$ Even though (again, I may be making a mistake), expanding $\prod_{i\\in S}(2x_i-1)$ I get $$\sum_{T\subseteq S} (-1)^{|S|-|T|} 2^{|T|}\prod_{i\in T} x_i$$ so the final expansion would look like $$f(x) = \sum_{T\subseteq [n]} \left( 2^{|T|}\sum_{S\supseteq T} (-1)^{|S|-|T|} \hat{f}(S) \right) \prod_{i\in T} x_i$$ (wouldn't it?) While in your answer the "new Fourier coefficients in the AND basis" are basically the same as the "old Fourier coefficients in the parity basis." $\endgroup$
    – Clement C.
    Commented Apr 11, 2018 at 23:41
  • $\begingroup$ Yes, that's essentially correct, the two bases are related linearly after all. $\endgroup$
    – kodlu
    Commented Apr 12, 2018 at 0:02
  • $\begingroup$ But in that case, isn't the expression for the "new AND-Fourier coefficients" featured in your answer incorrect? $\endgroup$
    – Clement C.
    Commented Apr 12, 2018 at 16:03

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.