Let \(n\in \mathbb N\), let \(J\subseteq \{ 0,\ldots ,n-1\} \) be nonempty, let \(b\in \{ 0,1\} ^n\), and put \(k=|J|\) and \(q(x)=\mathbf1_{\{ x_i=b_i\ \text{for every }i\in J\} }\) for \(x\in \{ 0,1\} ^n\). Using uniform expectation \(\mathbb E[h]=2^{-n}\sum _xh(x)\), singleton Fourier coefficients \(\widehat q(\{ i\} )=\mathbb E[q(x)(-1)^{x_i}]\), and degree-one Fourier weight \(W^1[q]=\sum _{i\lt n}\widehat q(\{ i\} )^2\), one has

For \(t\in \mathbb R\) and \(n\in \mathbb N\), define the \(\{ 0,1\} \)-valued function

where the quotient at \(n=0\) is taken to be \(0\). Write \(\mathbb E_n[h]=2^{-n}\sum _{x\in \{ 0,1\} ^n}h(x)\), \(\widehat h(\{ i\} )=\mathbb E_n[h(x)(-1)^{x_i}]\), and \(W^1[h]=\sum _{i\lt n}\widehat h(\{ i\} )^2\) for the degree-one Fourier weight; let \(\varphi (u)=(2\pi )^{-1/2}e^{-u^2/2}\) and \(\overline\Phi (t)=\int _t^\infty \varphi (u)\, du\) be the standard Gaussian density and upper tail. For every real \(t\), both limits hold as \(n\to \infty \) through the natural numbers:

Let \(n\in \mathbb N\), let \((a_i)_{i\lt n}\) be real coefficients with \(\sum _{i\lt n}a_i^2=1\), and let \(s\in \mathbb R\) satisfy \(s\ge 1\). For \(L(x)=\sum _{i\lt n}a_i(-1)^{x_i}\) on \(\{ 0,1\} ^n\) and uniform expectation \(\mathbb E[h]=2^{-n}\sum _{x\in \{ 0,1\} ^n}h(x)\), one has

For \(n\in \mathbb N\) and a real-valued function \(h\) on \(\{ 0,1\} ^n\), write \(\mathbb E[h]=2^{-n}\sum _{x\in \{ 0,1\} ^n}h(x)\), \(\widehat h(\{ i\} )=\mathbb E[h(x)(-1)^{x_i}]\), and \(W^1[h]=\sum _{i\lt n}\widehat h(\{ i\} )^2\) for its degree-one Fourier weight. There exists a real constant \(C\ge 0\) such that, for every \(n\in \mathbb N\), every \(f:\{ 0,1\} ^n\to \mathbb R\) satisfying \(f(x)\in \{ 0,1\} \) for every \(x\), and every real \(\alpha \) with \(\mathbb E[f]=\alpha \) and \(0\lt \alpha \le \tfrac 12\), one has

where \(\log \) is the natural logarithm.

For \(n\in \mathbb N\) and a real-valued function \(f\) on \(\{ 0,1\} ^n\), use uniform expectation \(\mathbb E[h]=2^{-n}\sum _xh(x)\), singleton Fourier coefficients \(\widehat f(\{ i\} )=\mathbb E[f(x)(-1)^{x_i}]\), degree-one Fourier weight \(W^1[f]=\sum _{i\lt n}\widehat f(\{ i\} )^2\), and degree-one part \(L_f(x)=\sum _{i\lt n}\widehat f(\{ i\} )(-1)^{x_i}\); define \(\tau (r)=1\) for \(r\ge 0\) and \(\tau (r)=-1\) for \(r\lt 0\). There exists a real constant \(C\ge 0\) such that, for every \(n\in \mathbb N\), every sign-valued function \(f:\{ 0,1\} ^n\to \{ -1,1\} \), and every real \(\varepsilon \ge 0\) with \(|\widehat f(\{ i\} )|\le \varepsilon \) for every \(i\lt n\), one has

where the probability is uniform on the cube.

Let \(n\in \mathbb N\) and let \(f:\{ 0,1\} ^n\to \{ -1,1\} \) be sign-valued, with uniform expectation \(\mathbb E[h]=2^{-n}\sum _{x\in \{ 0,1\} ^n}h(x)\), singleton Fourier coefficients \(\widehat f(\{ i\} )=\mathbb E[f(x)(-1)^{x_i}]\), and degree-one Fourier weight \(W^1[f]=\sum _{i\lt n}\widehat f(\{ i\} )^2\). For every real \(\delta \) satisfying \(0\le 1-\delta \) and \(1-\delta \le |\mathbb E[f]|\), one has

The logarithm is natural, and at \(\delta =0\) both \(2/\delta \) and \(\log (2/\delta )\) are interpreted as \(0\).

For any dimension \(d\in \mathbb N\) and real-valued function \(h\) on \(\{ 0,1\} ^d\), set \(\widehat h(\{ j\} )=2^{-d}\sum _{x\in \{ 0,1\} ^d}h(x)(-1)^{x_j}\) and \(W^1[h]=\sum _{j\lt d}\widehat h(\{ j\} )^2\) for its singleton Fourier coefficients and degree-one Fourier weight, and let every probability on a cube be uniform. Let \(C\in \mathbb R\) satisfy \(C\ge 1\), and assume that for every \(m\in \mathbb N\) with \(m\gt 0\), every \(g:\{ 0,1\} ^m\to \{ -1,1\} \), and every real \(\eta \) with \(0\le \eta \le 1\) and \(1-\eta \le W^1[g]\), there exist \(j\lt m\) and \(u\in \{ 1,-1\} \) with \(\Pr [g(x)\ne u(-1)^{x_j}]\le C\eta \). Then for every \(n\in \mathbb N\) with \(n\gt 0\), every sign-valued \(f:\{ 0,1\} ^n\to \{ -1,1\} \), and every real \(\delta \) with \(0\le \delta \le 1\) and \(1-\delta \le W^1[f]\), there exist \(i\lt n\) and \(s\in \{ 1,-1\} \) such that

where \(\log \) is natural and, at \(\delta =0\), \(1/(C\delta )\) and its logarithm are interpreted as \(0\).