For a natural number \(n\), let \(I=\{ 0,\ldots ,n-1\} \) be the coordinate set. A multilinear polynomial on the \(n\)-dimensional Boolean cube is represented by an arbitrary coefficient family \(p:\mathcal P(I)\to \mathbb R\), assigning a real coefficient \(p(S)\) to each subset \(S\subseteq I\).

Let \(n\in \mathbb N\), \(I=\{ 0,\ldots ,n-1\} \), and let \(p:\mathcal P(I)\to \mathbb R\) be a coefficient family. For \(x\in \{ 0,1\} ^I\), its polynomial value is

where the product over the empty set is \(1\).

Let \(n,k\in \mathbb N\), \(I=\{ 0,\ldots ,n-1\} \), and \(p:\mathcal P(I)\to \mathbb R\). The coefficient family \(p\) has degree at most \(k\) precisely when \(p(S)=0\) for every \(S\subseteq I\) with \(|S|\gt k\).

For every real number \(r\), the threshold sign is the real number

In particular, zero has threshold sign \(1\).

Let \(n\in \mathbb N\), \(I=\{ 0,\ldots ,n-1\} \), and \(p:\mathcal P(I)\to \mathbb R\). The threshold function associated with \(p\) assigns to each \(x\in \{ 0,1\} ^I\) the value \(1\) when \(\sum _{S\subseteq I}p(S)\prod _{i\in S}(-1)^{x_i}\ge 0\), and \(-1\) otherwise. In particular, a zero polynomial value is assigned \(1\).

Let \(n\in \mathbb N\), \(I=\{ 0,\ldots ,n-1\} \), \(f:\{ 0,1\} ^I\to \mathbb R\), and \(p:\mathcal P(I)\to \mathbb R\). The family \(p\) is a polynomial threshold representation of \(f\) precisely when, for every \(x\in \{ 0,1\} ^I\), \(f(x)=\sigma (\sum _{S\subseteq I}p(S)\prod _{i\in S}(-1)^{x_i})\), where \(\sigma (r)=1\) for \(r\ge 0\) and \(\sigma (r)=-1\) for \(r\lt 0\).

Let \(n,k\in \mathbb N\), \(I=\{ 0,\ldots ,n-1\} \), and \(f:\{ 0,1\} ^I\to \mathbb R\). The function \(f\) is a polynomial threshold function of degree at most \(k\) precisely when there exists \(p:\mathcal P(I)\to \mathbb R\) such that \(p(S)=0\) whenever \(|S|\gt k\) and

where \(\sigma (r)=1\) for \(r\ge 0\) and \(-1\) for \(r\lt 0\).

Let \(n\in \mathbb N\), \(I=\{ 0,\ldots ,n-1\} \), and \(f:\{ 0,1\} ^I\to \mathbb R\). The function \(f\) is a linear threshold function precisely when it has a polynomial threshold representation of degree at most one: there exists \(p:\mathcal P(I)\to \mathbb R\) with \(p(S)=0\) for \(|S|\gt 1\) and \(f(x)=\sigma (\sum _{S\subseteq I}p(S)\prod _{i\in S}(-1)^{x_i})\) for every \(x\), where \(\sigma (r)=1\) for \(r\ge 0\) and \(-1\) for \(r\lt 0\).

Let \(n\in \mathbb N\), \(I=\{ 0,\ldots ,n-1\} \), \(f:\{ 0,1\} ^I\to \mathbb R\), and \(a:I\to \mathbb R\). The weights \(a\) give a homogeneous linear threshold representation of \(f\) precisely when, for every \(x\in \{ 0,1\} ^I\), the sum \(L_a(x)=\sum _{i\in I}a_i(-1)^{x_i}\) is nonzero and \(f(x)=\sigma (L_a(x))\), where \(\sigma (r)=1\) for \(r\ge 0\) and \(-1\) for \(r\lt 0\).

Let \(n,s\in \mathbb N\), \(I=\{ 0,\ldots ,n-1\} \), and \(f:\{ 0,1\} ^I\to \mathbb R\). The function \(f\) is a majority of \(s\) signed parities precisely when there are subsets \(S_0,\ldots ,S_{s-1}\subseteq I\) and signs \(\varepsilon _j\in \{ -1,1\} \) such that

where repetitions of the subsets are allowed and \(\sigma (r)=1\) for \(r\ge 0\), \(-1\) for \(r\lt 0\); thus ties, including the empty sum when \(s=0\), give the value \(1\).

Let \(n\in \mathbb N\), \(I=\{ 0,\ldots ,n-1\} \), and \(p:\mathcal P(I)\to \mathbb R\). The support of \(p\) is the finite set \(\operatorname {supp}(p)=\{ S\subseteq I:p(S)\ne 0\} \).

Let \(n\in \mathbb N\), \(I=\{ 0,\ldots ,n-1\} \), and \(p:\mathcal P(I)\to \mathbb R\). The sparsity of \(p\) is \(|\{ S\subseteq I:p(S)\ne 0\} |\), the number of its nonzero coefficients.

Let \(n,k\in \mathbb N\), \(I=\{ 0,\ldots ,n-1\} \), and \(f:\{ 0,1\} ^I\to \mathbb R\). Its Fourier weight on levels at most \(k\) is

Let \(n,k\in \mathbb N\), \(I=\{ 0,\ldots ,n-1\} \), and \(f:\{ 0,1\} ^I\to \mathbb R\). Its Fourier weight on levels strictly above \(k\) is

Let \(n\in \mathbb N\), \(I=\{ 0,\ldots ,n-1\} \), and \(f:\{ 0,1\} ^I\to \mathbb R\). Its spectral one-norm is

Let \(n\in \mathbb N\), \(I=\{ 0,\ldots ,n-1\} \), and \(f:\{ 0,1\} ^I\to \mathbb R\). The degree-one part of \(f\) is the function

The constant Fourier coefficient is excluded.

Let \(n\in \mathbb N\), \(I=\{ 0,\ldots ,n-1\} \), and \(f:\{ 0,1\} ^I\to \mathbb R\). The maximum influence is

where \(x^{\oplus i}\) is obtained by flipping coordinate \(i\), and the supremum over the empty coordinate set is assigned \(0\) when \(n=0\).

Let \(n\in \mathbb N\) and let \(f,g:\{ 0,1\} ^n\to \mathbb R\) be arbitrary real-valued functions. Their disagreement probability is \(d(f,g)=2^{-n}|\{ x\in \{ 0,1\} ^n:f(x)\ne g(x)\} |\), using the uniform distribution on the cube.

Let \(n\in \mathbb N\), \(f,g:\{ 0,1\} ^n\to \mathbb R\), and \(\varepsilon \in \mathbb R\). The functions \(f\) and \(g\) are \(\varepsilon \)-close precisely when \(2^{-n}|\{ x\in \{ 0,1\} ^n:f(x)\ne g(x)\} |\le \varepsilon \).

Let \(n\in \mathbb N\) and \(f:\{ 0,1\} ^n\to \mathbb R\). The supremum norm of \(f\) is \(\| f\| _\infty =\sup _{x\in \{ 0,1\} ^n}|f(x)|\), equivalently the maximum of \(|f|\) on this finite nonempty cube.

Let \(n\in \mathbb N\), \(I=\{ 0,\ldots ,n-1\} \), \(f:\{ 0,1\} ^I\to \mathbb R\), and \(\rho \in \mathbb R\). The noise stability at \(\rho \) is

where \(\chi _S(x)=\prod _{i\in S}(-1)^{x_i}\) and \(\widehat f(S)=2^{-n}\sum _{x\in \{ 0,1\} ^I}f(x)\chi _S(x)\); this quantity is defined for every real \(\rho \).

Let \(n\in \mathbb N\), \(I=\{ 0,\ldots ,n-1\} \), \(f:\{ 0,1\} ^I\to \mathbb R\), and \(\delta \in \mathbb R\). The noise sensitivity is the real number

where \(\chi _S(x)=\prod _{i\in S}(-1)^{x_i}\) and \(\widehat f(S)=2^{-n}\sum _{x\in \{ 0,1\} ^I}f(x)\chi _S(x)\); neither \(\delta \in [0,1]\) nor \(f(x)\in \{ -1,1\} \) is required.

For \(n\in \mathbb N\), a point of \(\{ 0,1\} ^{n+n}\) is written as two blocks \((u,v)\) with \(u,v\in \{ 0,1\} ^n\). The inner-product-mod-two function is \(\operatorname {IP}_n(u,v)=\prod _{i=0}^{n-1}(-1)^{u_i v_i}=(-1)^{\sum _{i=0}^{n-1}u_i v_i}\), so it is \(-1\) exactly when the number of coordinates where both bits are \(1\) is odd; the empty product for \(n=0\) is \(1\).

Let \(n\in \mathbb N\), \(I=\{ 0,\ldots ,n-1\} \), \(J\subseteq I\), and \(b\in \{ 0,1\} ^I\). The subcube indicator associated with \(J\) and \(b\) is the function taking value \(1\) at \(x\in \{ 0,1\} ^I\) if \(x_i=b_i\) for every \(i\in J\), and value \(0\) otherwise.

Let \(n\in \mathbb N\) and \(t\in \mathbb R\). The normalized Hamming-ball indicator takes value \(1\) at \(x\in \{ 0,1\} ^n\) precisely when \(t\le (\sum _{i=0}^{n-1}(-1)^{x_i})/\sqrt n\), and value \(0\) otherwise, including the boundary in the value-\(1\) region. When \(n=0\), the quotient is assigned \(0\), so the function takes value \(1\) exactly when \(t\le 0\).