What is the polynomial representation of the Hamming weight function?

Question

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$

Answer 1

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