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

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.

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