1
$\begingroup$

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$

$\endgroup$
3
  • $\begingroup$ Yes, thank you. I should have said "unique multilinear polynomial". $\endgroup$
    – Ben
    Jun 1 at 16:43
  • $\begingroup$ 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). $\endgroup$
    – Ben
    Jun 1 at 18:02
  • $\begingroup$ I've deleted my comments above, as they no longer apply to the edited post. I'll delete this one too in a while. $\endgroup$
    – Neal Young
    Jun 1 at 18:37
3
$\begingroup$
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$.

$\endgroup$
1
  • $\begingroup$ Great answer, thanks! $\endgroup$
    – Ben
    Jun 1 at 16:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.