1
$\begingroup$

Preliminary: If $g:\{0,1\}^n\rightarrow \{0,1\}$ then there is a unique multilinear polynomial $f:\{1,-1\}^n\rightarrow \{1,-1\}$ such that $f((-1)^{a_1},\ldots,(-1)^{a_n})=(-1)^{g(a)}$ of all $a\in \{0,1\}^n$. Indeed, one only needs to consider the indicator polynomial $$f(x_1,\ldots,x_n)=\sum_{a\in \{0,1\}^n}(-1)^{g(a)}\prod_{i=1}^n\left(\frac{1+(-1)^{a_i}x_i}{2}\right)$$ and recall that the monomials $x^S:=\prod_{j\in S}x_j$ for $S\subseteq [n]$ form a basis for the vector space of such functions. Hence, we can express $$f(x_1,\ldots,x_n)=\sum_{S\subset [n]} \hat{f_S} x^S,$$ where $\hat{f_S}$ are the Fourier coefficients (basis coefficients for $f$).

Question: Let $g$ be the XOR function i.e. $g_n(a)=1$ if $a\in \{0,1\}^n$ contains a single $1$ otherwise $g_n(a)=0$. Can we find a nice expression for the corresponding $f(x_1,\ldots,x_n)$ of the joint XOR function $g_n$?

eg. If $n=2$ we have $g_2(a_1,a_2)=a_1\oplus a_2$ and we can see that $f_2(x_1,x_2)=x_1x_2$.

So far I have tried to obtain a simplified formula by starting directly with the indicator polynomial for the XOR function but I haven't had any luck... even a formula for $n=3$ would be appreciated.

$\endgroup$

2 Answers 2

1
$\begingroup$

Let $g_n$ be the $n$-th XOR function and $f_n$ a corresponding polynomial. Take $x = (x_1, ..., x_n)$ and $y$. I provide a recursive formula.

\begin{align*} f_{n+1}(x, y) =& \sum_{a\in \{0,1\}^n}(-1)^{g_{n+1}(a, 0)}\prod_{i=1}^n\left(\frac{1+(-1)^{a_i}x_i}{2}\right)\left(\frac{1+y}{2}\right)\\& + \sum_{a\in \{0,1\}^n}(-1)^{g_{n+1}(a, 1)}\prod_{i=1}^n\left(\frac{1+(-1)^{a_i}x_i}{2}\right)\left(\frac{1-y}{2}\right)\\ =&f_n(x)\left(\frac{1+y}{2}\right)-2\prod_{i=1}^n\left(\frac{1+x_i}{2} \right)\left(\frac{1-y}{2}\right)+\\& \sum_{a\in \{0,1\}^n}\prod_{i=1}^n\left(\frac{1+(-1)^{a_i}x_i}{2}\right)\left(\frac{1-y}{2}\right)\\ =& f_n(x)\left(\frac{y+1}{2}\right)+\left(\frac{1}{2^{n-1}}\prod_{i=1}^n\left(1+x_i \right)-1\right)\left(\frac{y-1}{2}\right)\end{align*}

For $n = 1$, $g_1 \equiv \text{Id}$ and $f_1(x_1) = x_1$.

For $n = 2$, $f_2(x_1, x_2) = x_1\left(\frac{x_2+1}{2}\right)+x_1\left(\frac{x_2-1}{2}\right) = x_1x_2$.

For $n = 3$, $$f_3(x_1, x_2) = x_1x_2\left(\frac{x_3+1}{2}\right)+\left(\frac{1}{2}x_1x_2+\frac{1}{2}x_1+\frac{1}{2}x_2-\frac{1}{2}\right)\left(\frac{x_3-1}{2}\right) = \frac{1}{4}[3x_1x_2x_3+x_1x_2+x_1x_3+x_2x_3-x_3-x_1-x_2+1] = \frac{1}{4}[3p_1+p_2-p_3+1]$$ where $(x+x_1)(x+x_2)(x+x_3) = x^3+p_3x^2+p_2x+p_1$ (elementary symmetric polynomials).

$\endgroup$
0
$\begingroup$

Observe the function $$f_n(x_1,\ldots,x_n)=1-2\sum_{k=1}^n \frac{(1-x_k)}{2}\prod_{\ell\neq k}^n\frac{(1+x_\ell)}{2}$$ attains the value $-1$ whenever the input string of $x_i$'s contains only one $x_k=-1$ (resp. $x_\ell=1$ for all $\ell\neq k$) and attains the value $1$ whenever there is a pair $x_k=x_j=-1$ ($j\neq k$) in the input.

$\endgroup$

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.