Let \(n,k\in \mathbb N\), let \(f,g:\{ 0,1\} ^n\to \{ -1,1\} \), and define \(\chi _S(x)=(-1)^{\sum _{i\in S}x_i}\) and \(\widehat h(S)=\mathbb E_x[h(x)\chi _S(x)]\) using uniform expectation, for \(S\subseteq \{ 1,\ldots ,n\} \) and \(h:\{ 0,1\} ^n\to \mathbb R\). Suppose \(f(x)=\operatorname {sgn}(p(x))\) for a real multilinear polynomial \(p(x)=\sum _{|S|\le k}a_S\chi _S(x)\), where \(\operatorname {sgn}(t)=1\) for \(t\ge 0\) and \(-1\) for \(t\lt 0\). If \(\widehat g(S)=\widehat f(S)\) for every \(S\) with \(|S|\le k\), then \(g=f\).

Let \(n\in \mathbb N\) and \(f,g:\{ 0,1\} ^n\to \{ -1,1\} \), and define \(\chi _S(x)=(-1)^{\sum _{i\in S}x_i}\) and \(\widehat h(S)=\mathbb E_x[h(x)\chi _S(x)]\) for uniform \(x\), subsets \(S\subseteq \{ 1,\ldots ,n\} \), and \(h:\{ 0,1\} ^n\to \mathbb R\). Suppose \(f(x)=\operatorname {sgn}(a_\varnothing +\sum _{i=1}^na_i(-1)^{x_i})\) for real coefficients, where \(\operatorname {sgn}(t)=1\) for \(t\ge 0\) and \(-1\) for \(t\lt 0\). If \(\widehat g(S)=\widehat f(S)\) whenever \(|S|\le 1\), then \(g=f\).

Let \(n\in \mathbb N\), \(f:\{ 0,1\} ^n\to \{ -1,1\} \), and \(0\lt \delta \le \tfrac 12\); write \(\operatorname {NS}_\delta (f)=\Pr [f(x)\ne f(y)]\), where \(x\) is uniform and \(y\) is obtained by independently flipping each bit of \(x\) with probability \(\delta \). There exists \(g:\{ 0,1\} ^n\to \{ -1,1\} \) of the form \(g(x)=\operatorname {sgn}(p(x))\), where \(p\) is a real multilinear polynomial of degree at most \(\lfloor 1/\delta \rfloor \), with \(\operatorname {sgn}(t)=1\) for \(t\ge 0\) and \(-1\) for \(t\lt 0\), such that

Let \(n\in \mathbb N\) and \(f:\{ 0,1\} ^n\to \{ -1,1\} \) satisfy \(f(x)=\operatorname {sgn}(a_\varnothing +\sum _{i=1}^na_i(-1)^{x_i})\) for real coefficients, where \(\operatorname {sgn}(t)=1\) for \(t\ge 0\) and \(-1\) for \(t\lt 0\). Define \(\chi _S(x)=(-1)^{\sum _{i\in S}x_i}\) and \(\widehat f(S)=\mathbb E_x[f(x)\chi _S(x)]\) for uniform \(x\) and \(S\subseteq \{ 1,\ldots ,n\} \); then

Let \(n,k\in \mathbb N\), \(f:\{ 0,1\} ^n\to \{ -1,1\} \), and \(\chi _S(x)=(-1)^{\sum _{i\in S}x_i}\) for \(S\subseteq \{ 1,\ldots ,n\} \). Suppose \(f(x)=\operatorname {sgn}(\sum _{|S|\le k}a_S\chi _S(x))\) for real coefficients, where \(\operatorname {sgn}(t)=1\) for \(t\ge 0\) and \(-1\) for \(t\lt 0\), and define \(\widehat f(S)=\mathbb E_x[f(x)\chi _S(x)]\) using uniform expectation. Then

Let \(n\in \mathbb N\), \(\chi _S(x)=(-1)^{\sum _{i\in S}x_i}\) on \(\{ 0,1\} ^n\), and \(p(x)=\sum _Sa_S\chi _S(x)\) be a nonzero real multilinear polynomial; let \(F\) be a finite family of subsets of \(\{ 1,\ldots ,n\} \) containing every \(S\) with \(a_S\ne 0\). Suppose \(f:\{ 0,1\} ^n\to \mathbb R\) satisfies \(f(x)=\operatorname {sgn}(p(x))\), where \(\operatorname {sgn}(t)=1\) for \(t\ge 0\) and \(-1\) for \(t\lt 0\), and define \(\widehat f(S)=\mathbb E_x[f(x)\chi _S(x)]\) using uniform expectation. Then \(1\le \sum _{S\in F}|\widehat f(S)|\).

Let \(n\in \mathbb N\), \(f:\{ 0,1\} ^n\to \{ -1,1\} \), \(\chi _S(x)=(-1)^{\sum _{i\in S}x_i}\), and \(p(x)=\sum _Sa_S\chi _S(x)\) be a nonzero real multilinear polynomial on \(\{ 0,1\} ^n\). Suppose \(f(x)=\operatorname {sgn}(p(x))\), with \(\operatorname {sgn}(t)=1\) for \(t\ge 0\) and \(-1\) for \(t\lt 0\), and let \(F\) be a finite family of subsets of \(\{ 1,\ldots ,n\} \) satisfying \(a_S\ne 0\Rightarrow S\in F\). Writing \(\widehat f(S)=\mathbb E_x[f(x)\chi _S(x)]\) for uniform \(x\), one has \(1\le \sum _{S\in F}|\widehat f(S)|\).

Let \(n\in \mathbb N\) and define \(I(u,v)=(-1)^{\sum _{i=1}^nu_iv_i}\) for \(u,v\in \{ 0,1\} ^n\). Suppose the nonzero real multilinear polynomial \(p(x)=\sum _{S\subseteq \{ 1,\ldots ,2n\} }a_S\chi _S(x)\), where \(\chi _S(x)=(-1)^{\sum _{i\in S}x_i}\), satisfies \(I(x)=\operatorname {sgn}(p(x))\) for all \(x\in \{ 0,1\} ^{2n}\), with \(\operatorname {sgn}(t)=1\) for \(t\ge 0\) and \(-1\) for \(t\lt 0\). Then \(p\) has at least \(2^n\) nonzero coefficients: \(2^n\le |\{ S:a_S\ne 0\} |\).

Let \(n\in \mathbb N\) with \(n\gt 0\), let \(f:\{ 0,1\} ^n\to \mathbb R\) be nonzero, and define \(\chi _S(x)=(-1)^{\sum _{i\in S}x_i}\), \(\widehat f(S)=\mathbb E_x[f(x)\chi _S(x)]\) for uniform \(x\), and \(L=\sum _{S\subseteq \{ 1,\ldots ,n\} }|\widehat f(S)|\). For every \(\delta \gt 0\) and \(s\in \mathbb N\) with \(4nL^2/\delta ^2\le s\), there exists a real multilinear polynomial \(q(x)=\sum _Sa_S\chi _S(x)\) satisfying

Let \(n\in \mathbb N\) with \(n\gt 0\), let \(f:\{ 0,1\} ^n\to \{ -1,1\} \), define \(\chi _S(x)=(-1)^{\sum _{i\in S}x_i}\) and \(\widehat f(S)=\mathbb E_x[f(x)\chi _S(x)]\) for uniform \(x\) and \(S\subseteq \{ 1,\ldots ,n\} \), and set \(L=\sum _S|\widehat f(S)|\) and \(s=\lceil 4nL^2\rceil \). There exists a real multilinear polynomial \(p(x)=\sum _Sa_S\chi _S(x)\) with at most \(s\) nonzero coefficients such that \(f(x)=\operatorname {sgn}(p(x))\), where \(\operatorname {sgn}(t)=1\) for \(t\ge 0\) and \(-1\) for \(t\lt 0\). Moreover, there exist subsets \(S_1,\ldots ,S_s\subseteq \{ 1,\ldots ,n\} \), with repetitions allowed, and signs \(\varepsilon _1,\ldots ,\varepsilon _s\in \{ -1,1\} \) such that