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)$?

$\endgroup$
1
  • $\begingroup$ Have you tried checking this formula for a few functions? $\endgroup$ Oct 29, 2014 at 21:10

1 Answer 1

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.

$\endgroup$
3
  • $\begingroup$ Nice answer. Let me reflect a bit on this. $\endgroup$
    – Turbo
    Oct 30, 2014 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$
    – Turbo
    Oct 30, 2014 at 14:18
  • $\begingroup$ You don't need a reference if you can compute it yourself! $\endgroup$ Oct 30, 2014 at 14:34

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.