An expression for the multilinear joint XOR polynomial over $\{1,-1\}^n$

Question

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.

Answer 1

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.

Answer 2

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).