# What is the polynomial representation of the Hamming weight function?

For any function $$f: \{1,-1\}^n \rightarrow \{1,-1\}$$, there is a unique multilinear polynomial $$p \in \mathbb{R}[x_1,\dots, x_n]$$ for which $$p(x)=f(x)$$ for all $$x \in \{1,-1\}^n$$ (see e.g. Lemma 4.1 here). I will call this the polynomial representation of $$f$$.

I would like to know, for each $$k=0,\dots, n$$, what the polynomial representation of the function $$f_k$$ is, where $$f_k(x)=1$$ if and only if the number of $$+1$$'s appearing in $$x$$ is equal to $$k$$.

In the absence of such a polynomial representation, I would like upper and lower bounds on the number of monomial terms appearing in the polynomial representation of each $$f_k$$.

Edit: Here is a proof that the polynomial representation of any such $$f$$ is unique (I thank Neal Young for bringing up this subtlety. This fact is obvious for $$\{0,1\}$$-valued functions, but takes slightly more work for $$\{-1,1\}$$-valued functions.)

It suffices to prove that whenever $$\sum_{I \in \{0,1\}^n} \alpha_I x_1^{I_1}\cdots x_n^{I_n}=0$$ for all $$x \in \{-1,1\}^n$$, it holds that $$\alpha_I=0$$ for all $$I \in \{0,1\}^n$$. We prove this by induction on $$n$$.

For $$n=1$$, if $$\alpha_0+\alpha_1 x_1=0$$ for $$x_1=\pm 1$$, then clearly $$\alpha_0=\alpha_1=0$$.

Now suppose $$\sum_{I \in \{0,1\}^n} \alpha_I x_1^{I_1}\cdots x_n^{I_n}=0$$ for all $$x \in \{-1,1\}^n$$. Then

$$\sum_{\substack{I \in \{0,1\}^n\\I_n=0}} \alpha_I x_1^{I_1}\cdots x_{n-1}^{I_{n-1}}=0$$ and $$-\sum_{\substack{I \in \{0,1\}^n\\I_n=1}} \alpha_I x_1^{I_1}\cdots x_{n-1}^{I_{n-1}}=0$$ for all $$x \in \{1,-1\}^{n-1}$$, so by the induction hypothesis, $$\alpha_I=0$$ for all $$I \in \{0,1\}^n$$. $$\square$$

• Yes, thank you. I should have said "unique multilinear polynomial".
– Ben
Jun 1 at 16:43
• Thanks for bringing this up. The multilinear representation is indeed unique, even for $\{-1,1\}$-valued functions (I have edited my post to include a proof).
– Ben
Jun 1 at 18:02
• I've deleted my comments above, as they no longer apply to the edited post. I'll delete this one too in a while. Jun 1 at 18:37

##### Here is the polynomial representation of any such function $$f$$:
1. For any $$y\in \{-1,1\}^n$$, define polynomial $$I_y(x) = 2^{-n}\prod_{i=1}^n 1+y_i x_i.$$

2. Then for all $$x\in\{-1,1\}^n$$ we have $$I_y(x) = 1$$ if $$y=z$$ and otherwise $$I_y(x) = 0$$.

3. So, for any function $$f:\{-1,1\}^n\rightarrow \{-1,1\}$$ and all $$x\in\{-1,1\}^n$$ we have $$f(x) = -1+2\sum_{y : f(y)=1} I_y(x),$$ so $$p_f(x) = -1+2\sum_{y:f(y)=1}I_y(x)$$ is the polynomial representation of $$f$$.

##### The number of terms in the polynomial representation of $$f_1$$ is at least $$2^{n-1}$$:
1. By the previous part, we have $$p_{f_1}(x_1,\ldots,x_n) = -1+2^{1-n}\sum_{i=1}^n (1+x_i) \prod_{j\ne i} (1-x_j)$$.
2. Note that if we constrain $$x_1 = 1$$, this simplifies to $$p_{f_1}(1, x_2, x_3, \ldots, x_n) = -1+2^{2-n}\prod_{j=2}^n (1-x_j)$$, which has $$2^{n-1}$$ terms (for $$n\ne 2$$).
3. It follows that $$f_1(x)$$ has at least $$2^{n-1}$$ terms (for $$n\ne 2$$).
##### The number of terms in the polynomial representation of $$f_k$$ is at least $$2^{n-k}$$:
1. Constraining $$x_1=x_2=\cdots=x_k=1$$, define the function $$g_k(x_{k+1}, x_{k+2}, \ldots x_n) = f_k(1,1,\ldots,1, x_{k+1}, x_{k+2}, \ldots, x_{n})$$.
2. The function $$g_k$$ takes the value 1 at $$x_{k+1}=\cdots=x_n=-1$$, and takes the value $$-1$$ for all $$(x_{k+1},\ldots, x_n)\in\{-1,1\}^{n-k}\setminus \{-1\}^{n-k}$$.
3. It follows (by the first part) that the polynomial representation of $$g_k$$ is $$-1+2^{1-n+k}\prod_{j=k+1}^n (1-x_j)$$.
4. So $$p_{g_k}$$ has $$2^{n-k}$$ terms (for $$n\ne k+1$$).
5. It follows that $$p_{f_k}$$, the polynomial representation of $$f_k$$, has at least $$2^{n-k}$$ terms (for $$n\ne k+1$$).

The above bound is surely low for large $$k$$.