Let \(n\ge 0\), \(x\in \{ 0,1\} ^n\), \(i\in [n]\), and \(b\in \{ 0,1\} \). Replacing \(x_i\) by \(b\) leaves \(x\) unchanged if \(x_i=b\) and otherwise gives the vector obtained by flipping bit \(i\).

Let \(n\ge 0\) and give \(\{ 0,1\} ^n\) uniform probability; write \(\mathbb E\) for expectation. For a real cube function \(h\), write \(D_i h(x)=\tfrac 12(h(x_{i\leftarrow 0})-h(x_{i\leftarrow 1}))\), where \(x_{i\leftarrow b}\) replaces bit \(i\) by \(b\). For every coordinate \(i\) and point \(x\), \(D_i h(x)=\tfrac 12(h(x)-h(x^{\{ i\} }))(-1)^{x_i}\), where \(x^{\{ i\} }\) flips bit \(i\).

Let \(n\ge 0\) and give \(\{ 0,1\} ^n\) uniform probability; write \(\mathbb E\) for expectation. For a real cube function \(h\), write \(D_i h(x)=\tfrac 12(h(x_{i\leftarrow 0})-h(x_{i\leftarrow 1}))\), where \(x_{i\leftarrow b}\) replaces bit \(i\) by \(b\). Set \(I_i(h)=\tfrac 14\mathbb E[(h(x)-h(x^{\{ i\} }))^2]\) and \(I(h)=\sum _i I_i(h)\), where \(x^{\{ i\} }\) flips bit \(i\). For every real cube function \(h\) and \(i\in [n]\), \(I_i(h)=\mathbb E[(D_i h)^2]\).

Let \(n\ge 0\) and give \(\{ 0,1\} ^n\) uniform probability; write \(\mathbb E\) for expectation. Let \(g\) be a real cube function and \(i\in [n]\), and define \(E_i g(x)=\tfrac 12(g(x_{i\leftarrow 0})+g(x_{i\leftarrow 1}))\), where the indicated update replaces bit \(i\). Then \(\mathbb E[E_i g]=\mathbb E g\).

Let \(n\ge 0\) and give \(\{ 0,1\} ^n\) uniform probability; write \(\mathbb E\) for expectation. Put \(\chi _S(x)=\prod _{i\in S}(-1)^{x_i}\) and \(\widehat h(S)=\mathbb E[h\chi _S]\) for \(S\subseteq [n]\) and real cube functions \(h\). For a real cube function \(h\), write \(D_i h(x)=\tfrac 12(h(x_{i\leftarrow 0})-h(x_{i\leftarrow 1}))\), where \(x_{i\leftarrow b}\) replaces bit \(i\) by \(b\). For every real cube function \(h\) and coordinate \(i\), \(\widehat h(\{ i\} )=\mathbb E[D_i h]\).

Let \(n\ge 0\) and give \(\{ 0,1\} ^n\) uniform probability; write \(\mathbb E\) for expectation. For a real cube function \(h\), write \(D_i h(x)=\tfrac 12(h(x_{i\leftarrow 0})-h(x_{i\leftarrow 1}))\), where \(x_{i\leftarrow b}\) replaces bit \(i\) by \(b\). For any \(h\colon \{ 0,1\} ^n\to \{ -1,1\} \), coordinate \(i\), and cube point \(x\), \((D_i h(x))^2=|D_i h(x)|\).

Let \(n\ge 0\) and give \(\{ 0,1\} ^n\) uniform probability; write \(\mathbb E\) for expectation. Put \(\chi _S(x)=\prod _{i\in S}(-1)^{x_i}\) and \(\widehat h(S)=\mathbb E[h\chi _S]\) for \(S\subseteq [n]\) and real cube functions \(h\). For a real cube function \(h\), write \(D_i h(x)=\tfrac 12(h(x_{i\leftarrow 0})-h(x_{i\leftarrow 1}))\), where \(x_{i\leftarrow b}\) replaces bit \(i\) by \(b\). Set \(I_i(h)=\tfrac 14\mathbb E[(h(x)-h(x^{\{ i\} }))^2]\) and \(I(h)=\sum _i I_i(h)\), where \(x^{\{ i\} }\) flips bit \(i\). If \(h\) is sign-valued and either \(D_i h(x)\ge 0\) for all \(x\) or \(D_i h(x)\le 0\) for all \(x\), then \(I_i(h)=|\widehat h(\{ i\} )|\).

Let \(n\ge 0\). Let \(c\in \mathbb R\), \(a\in \mathbb R^n\), and let \(A_{c,a}(S)\) equal \(c\) for \(S=\varnothing \), \(a_i\) for \(S=\{ i\} \), and zero for all larger \(S\). Then \(A_{c,a}(\varnothing )=c\).

Let \(n\ge 0\). Let \(c\in \mathbb R\), \(a\in \mathbb R^n\), and let \(A_{c,a}(S)\) equal \(c\) for \(S=\varnothing \), \(a_i\) for \(S=\{ i\} \), and zero for all larger \(S\). For every \(i\in [n]\), \(A_{c,a}(\{ i\} )=a_i\).

Let \(n\ge 0\). Let \(c\in \mathbb R\), \(a\in \mathbb R^n\), and let \(A_{c,a}(S)\) equal \(c\) for \(S=\varnothing \), \(a_i\) for \(S=\{ i\} \), and zero for all larger \(S\). This coefficient family has degree at most one: \(A_{c,a}(S)=0\) whenever \(|S|\gt 1\).

Let \(n\ge 0\) and give \(\{ 0,1\} ^n\) uniform probability; write \(\mathbb E\) for expectation. Put \(\chi _S(x)=\prod _{i\in S}(-1)^{x_i}\) and \(\widehat h(S)=\mathbb E[h\chi _S]\) for \(S\subseteq [n]\) and real cube functions \(h\). Write \(\operatorname {sgn}_+(t)=1\) for \(t\ge 0\) and \(-1\) for \(t\lt 0\). If \(f\) is the sign \(\operatorname {sgn}_+(P)\) of a Walsh polynomial \(P\) whose coefficients vanish on sets larger than one, then there exist real \(c\) and \(a_1,\ldots ,a_n\) such that \(f(x)=\operatorname {sgn}_+(c+\sum _i a_i(-1)^{x_i})\) for every \(x\).

Let \(n\ge 0\) and give \(\{ 0,1\} ^n\) uniform probability; write \(\mathbb E\) for expectation. Write \(\operatorname {sgn}_+(t)=1\) for \(t\ge 0\) and \(-1\) for \(t\lt 0\). For every real \(c\) and \(a\in \mathbb R^n\), the function \(x\mapsto \operatorname {sgn}_+(c+\sum _i a_i(-1)^{x_i})\) is a linear threshold function, meaning the sign of a Walsh polynomial with no coefficient above degree one.

Let \(n\ge 0\), \(c\in \mathbb R\), \(a\in \mathbb R^n\), \(i\in [n]\), \(x\in \{ 0,1\} ^n\), and \(b\in \{ 0,1\} \). If \(x_{i\leftarrow b}\) replaces bit \(i\) by \(b\), then \(c+\sum _j a_j(-1)^{(x_{i\leftarrow b})_j}=(c+\sum _{j\ne i}a_j(-1)^{x_j})+a_i(-1)^b\).

Let \(n\ge 0\) and give \(\{ 0,1\} ^n\) uniform probability; write \(\mathbb E\) for expectation. Write \(\operatorname {sgn}_+(t)=1\) for \(t\ge 0\) and \(-1\) for \(t\lt 0\). For a real cube function \(h\), write \(D_i h(x)=\tfrac 12(h(x_{i\leftarrow 0})-h(x_{i\leftarrow 1}))\), where \(x_{i\leftarrow b}\) replaces bit \(i\) by \(b\). For any real \(c\), \(a\in \mathbb R^n\), and \(i\in [n]\), put \(f(x)=\operatorname {sgn}_+(c+\sum _j a_j(-1)^{x_j})\). Either \(D_i f(x)\ge 0\) for every \(x\), or \(D_i f(x)\le 0\) for every \(x\).

Let \(n\ge 0\) and give \(\{ 0,1\} ^n\) uniform probability; write \(\mathbb E\) for expectation. Put \(\chi _S(x)=\prod _{i\in S}(-1)^{x_i}\) and \(\widehat h(S)=\mathbb E[h\chi _S]\) for \(S\subseteq [n]\) and real cube functions \(h\). Every \(f\colon \{ 0,1\} ^n\to \{ -1,1\} \) satisfies \(\sum _{i=1}^n\widehat f(\{ i\} )^2\le 1\).