1
$\begingroup$

Let a real polynomial representing a boolean function be $P(x_1,\dots,x_n) = \sum_{a\in\{0,1\}^n}c_ax^a = \sum_{a\in\{0,1\}^n}p(a)\prod_{i\in 1_a}x_i\prod_{j\in \bar{1}_a}(1-x_j)$ where $1_a$ is the set of $i$ such that $a_i=1$ and $\bar{1}_a$ is the complement of $1_a$. How do you represent $c_a$ in terms of $p(a)$?

Is for all $b\in\{0,1\}^n$, $c_{b} = \sum_{a\in\{0,1\}^n}(-1)^{<b,a>}p(a)$?

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Have you tried checking this formula for a few functions? $\endgroup$ – Yuval Filmus Oct 29 '14 at 21:10
1
$\begingroup$

Consider the function $P(x_1) = x_1$. Then $P(0) = 0$, $P(1) = 1$, and the polynomial representation is $x_1$, but your formula gives $c_0 = 1$ and $c_1 = -1$. However, if we define $\hat{P}(b) = 2^{-n} \sum_{a \in \{0,1\}^n} (-1)^{\langle a,b \rangle} P(a)$ then $$ P(x) = \sum_{b \in \{0,1\}^n} \hat{P}(b) (-1)^{\langle x,b \rangle}. $$ This is known as the Fourier expansion of $P$. To relate this to your expansion, notice that $$ (-1)^{\langle x,b \rangle} = \prod_{i\colon b_i=1} (-1)^{x_i} = \prod_{i\colon b_i=1} (1-2x_i). $$ It is now an exercise to relate the coefficients $\hat{P}(b)$ to the coefficients $c_b$ you are interested in.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Nice answer. Let me reflect a bit on this. $\endgroup$ – T.... Oct 30 '14 at 2:12
  • $\begingroup$ Looks like the exact relation $c_b$ is linear but complicated weight by $2^c$ sum of $\hat{P}(b)$. Is there a reference for exact relation? $\endgroup$ – T.... Oct 30 '14 at 14:18
  • $\begingroup$ You don't need a reference if you can compute it yourself! $\endgroup$ – Yuval Filmus Oct 30 '14 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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