<h5>Here is the polynomial representation of any such function <span class="math-container">$f$</span>:</h5>
<ol>
<li><p>For any <span class="math-container">$y\in \{-1,1\}^n$</span>, define polynomial <span class="math-container">$I_y(x) = 2^{-n}\prod_{i=1}^n 1+y_i x_i.$</span></p>
</li>
<li><p>Then for all <span class="math-container">$x\in\{-1,1\}^n$</span> we have <span class="math-container">$I_y(x) = 1$</span> if <span class="math-container">$y=x$</span> and otherwise <span class="math-container">$I_y(x) = 0$</span>.</p>
</li>
<li><p>So, for any function <span class="math-container">$f:\{-1,1\}^n\rightarrow \{-1,1\}$</span>
and all <span class="math-container">$x\in\{-1,1\}^n$</span> we have <span class="math-container">$$f(x) = -1+2\sum_{y : f(y)=1} I_y(x),$$</span>
so <span class="math-container">$p_f(x) = -1+2\sum_{y:f(y)=1}I_y(x)$</span> is the polynomial representation of <span class="math-container">$f$</span>.</p>
</li>
</ol>
<h5>The number of terms in the polynomial representation of <span class="math-container">$f_1$</span> is at least <span class="math-container">$2^{n-1}$</span>:</h5>
<ol>
<li>By the previous part, we have <span class="math-container">$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)$</span>.</li>
<li>Note that if we constrain <span class="math-container">$x_1 = 1$</span>, this simplifies to
<span class="math-container">$p_{f_1}(1, x_2, x_3, \ldots, x_n) = -1+2^{2-n}\prod_{j=2}^n (1-x_j)$</span>, which has <span class="math-container">$2^{n-1}$</span> terms (for <span class="math-container">$n\ne 2$</span>).</li>
<li>It follows that <span class="math-container">$f_1(x)$</span> has at least <span class="math-container">$2^{n-1}$</span> terms (for <span class="math-container">$n\ne 2$</span>).</li>
</ol>
<h5>The number of terms in the polynomial representation of <span class="math-container">$f_k$</span> is at least <span class="math-container">$2^{n-k}$</span>:</h5>
<ol>
<li>Constraining <span class="math-container">$x_1=x_2=\cdots=x_k=1$</span>, let us define the function <span class="math-container">$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})$</span>.</li>
<li>The function <span class="math-container">$g_k$</span> takes the value 1 at <span class="math-container">$x_{k+1}=\cdots=x_n=-1$</span>, and takes the value <span class="math-container">$-1$</span> for all <span class="math-container">$(x_{k+1},\ldots, x_n)\in\{-1,1\}^{n-k}\setminus \{-1\}^{n-k}$</span>.</li>
<li>It follows (by the first part) that the polynomial representation of <span class="math-container">$g_k$</span> is <span class="math-container">$-1+2^{1-n+k}\prod_{j=k+1}^n (1-x_j)$</span>.</li>
<li>So <span class="math-container">$p_{g_k}$</span> has <span class="math-container">$2^{n-k}$</span> terms (for <span class="math-container">$n\ne k+1$</span>).</li>
<li>It follows that <span class="math-container">$p_{f_k}$</span>, the polynomial representation of <span class="math-container">$f_k$</span>, has at least <span class="math-container">$2^{n-k}$</span> terms (for <span class="math-container">$n\ne k+1$</span>).</li>
</ol>
<p>The above bound is surely too low for large <span class="math-container">$k$</span>.</p>

CC BY-SA 4.0
2021-06-01T16:43:38.747Z
Great answer, thanks!
Ben
CC BY-SA 4.0
2021-06-01T16:26:35.767Z
2022-04-02T20:12:52.287Z
2022-04-02T20:12:52.287Z
Neal Young
<p>These are given by the very widely studied Krawtchouk polynomials (a.k.a. the Fourier transform of the Hamming sphere): <a href="https://en.wikipedia.org/wiki/Kravchuk_polynomials" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Kravchuk_polynomials</a></p>

CC BY-SA 4.0
2022-04-08T00:11:22.280Z
2022-04-08T00:11:22.280Z
Mahdi Cheraghchi
<p>For any function <span class="math-container">$f: \{1,-1\}^n \rightarrow \{1,-1\}$</span>, there is a unique multilinear polynomial <span class="math-container">$p \in \mathbb{R}[x_1,\dots, x_n]$</span> for which <span class="math-container">$p(x)=f(x)$</span> for all <span class="math-container">$x \in \{1,-1\}^n$</span> (see e.g. Lemma 4.1 <a href="https://cs.uwaterloo.ca/%7Es4bendav/CS867QIC890/CS867QIC890W21week4notes.pdf" rel="nofollow noreferrer">here</a>). I will call this the <em>polynomial representation</em> of <span class="math-container">$f$</span>.</p>
<p>I would like to know, for each <span class="math-container">$k=0,\dots, n$</span>, what the polynomial representation of the function <span class="math-container">$f_k$</span> is, where <span class="math-container">$f_k(x)=1$</span> if and only if the number of <span class="math-container">$+1$</span>'s appearing in <span class="math-container">$x$</span> is equal to <span class="math-container">$k$</span>.</p>
<p>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 <span class="math-container">$f_k$</span>.</p>
<p><strong>Edit:</strong> Here is a proof that the polynomial representation of any such <span class="math-container">$f$</span> is unique (I thank Neal Young for bringing up this subtlety. This fact is obvious for <span class="math-container">$\{0,1\}$</span>-valued functions, but takes slightly more work for <span class="math-container">$\{-1,1\}$</span>-valued functions.)</p>
<p>It suffices to prove that whenever <span class="math-container">$\sum_{I \in \{0,1\}^n} \alpha_I x_1^{I_1}\cdots x_n^{I_n}=0$</span> for all <span class="math-container">$x \in \{-1,1\}^n$</span>, it holds that <span class="math-container">$\alpha_I=0$</span> for all <span class="math-container">$I \in \{0,1\}^n$</span>. We prove this by induction on <span class="math-container">$n$</span>.</p>
<p>For <span class="math-container">$n=1$</span>, if <span class="math-container">$\alpha_0+\alpha_1 x_1=0$</span> for <span class="math-container">$x_1=\pm 1$</span>, then clearly <span class="math-container">$\alpha_0=\alpha_1=0$</span>.</p>
<p>Now suppose <span class="math-container">$\sum_{I \in \{0,1\}^n} \alpha_I x_1^{I_1}\cdots x_n^{I_n}=0$</span> for all <span class="math-container">$x \in \{-1,1\}^n$</span>. Then</p>
<p><span class="math-container">$$
\sum_{\substack{I \in \{0,1\}^n\\I_n=0}} \alpha_I x_1^{I_1}\cdots x_{n-1}^{I_{n-1}}=0
$$</span>
and
<span class="math-container">$$-\sum_{\substack{I \in \{0,1\}^n\\I_n=1}} \alpha_I x_1^{I_1}\cdots x_{n-1}^{I_{n-1}}=0
$$</span>
for all <span class="math-container">$x \in \{1,-1\}^{n-1}$</span>, so by the induction hypothesis, <span class="math-container">$\alpha_I=0$</span> for all <span class="math-container">$I \in \{0,1\}^n$</span>. <span class="math-container">$\square$</span></p>

CC BY-SA 4.0
2021-06-01T16:43:08.413Z
Yes, thank you. I should have said "unique multilinear polynomial".
Ben
CC BY-SA 4.0
2021-06-01T18:02:53.047Z
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
CC BY-SA 4.0
2021-06-01T18:37:18.420Z
I've deleted my comments above, as they no longer apply to the edited post.  I'll delete this one too in a while.
Neal Young
<boolean-functions><polynomials>
What is the polynomial representation of the Hamming weight function?
Ben
# What is the polynomial representation of the Hamming weight function?

(Asked by: username_0 on 2021-06-01)

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](https://cs.uwaterloo.ca/%7Es4bendav/CS867QIC890/CS867QIC890W21week4notes.pdf)). 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 username_1 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$

**Tags:** boolean-functions, polynomials

> **Comments:**
> **username_0**: Yes, thank you. I should have said "unique multilinear polynomial".  
> **username_0**: 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).  
> **username_1**: I've deleted my comments above, as they no longer apply to the edited post.  I'll delete this one too in a while.  

---

## 2 answers

### Answer by username_1 on 2021-06-01. Score: 5 | Accepted answer

##### 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=x$ 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$, let us 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 too low for large $k$.

> **Comments:**
> **username_0**: Great answer, thanks!  

---

### Answer by username_2 on 2022-04-08. Score: 3

These are given by the very widely studied Krawtchouk polynomials (a.k.a. the Fourier transform of the Hamming sphere): <https://en.wikipedia.org/wiki/Kravchuk_polynomials>


---

