327 Boolean Analysis — Threshold Functions — Low Degree Norm

327.1 Overview

Hypercontractive moment bounds and interpolation compare the first and second moments of low-degree Walsh polynomials with the sharp exponential degree factor.

327.2 Declarations

Lemma 327.1 Low-degree energy retained by noise

✓

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\). Let \(P(x)=\sum _{S\subseteq [n]}a_S\chi _S(x)\) with real coefficients; degree at most \(k\) means \(a_S=0\) for \(|S|\gt k\). If \(P\) has degree at most the integer \(k\ge 0\) and \(0\le \rho \le 1\), define \(T_\rho P=\sum _S\rho ^{|S|}a_S\chi _S\). Then \(\rho ^{2k}\sum _Sa_S^2\le \mathbb E[(T_\rho P)^2]\), with natural powers including \(0^0=1\).

Lemma 327.2 Hypercontractive bound for a low-degree moment

✓

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\). Let \(P(x)=\sum _{S\subseteq [n]}a_S\chi _S(x)\) with real coefficients; degree at most \(k\) means \(a_S=0\) for \(|S|\gt k\). If \(P\) has degree at most the integer \(k\ge 0\) and \(1\lt t\lt 2\), then \((t-1)^k\sum _Sa_S^2\le (\mathbb E|P|^t)^{2/t}\).

Lemma 327.3 Interpolation between first and second moments

✓

Let \(n\ge 0\) and give \(\{ 0,1\} ^n\) uniform probability; write \(\mathbb E\) for expectation. For every real cube function \(f\) and real \(1\lt t\lt 2\), \(\mathbb E|f|^t\le (\mathbb E|f|)^{2-t}(\mathbb E[f^2])^{t-1}\).

Lemma 327.4 Natural-power form of the interpolation bound

✓

Let \(m\ge 0\) be an integer and let \(A,B,M\ge 0\). If \(M\le A^{1/(m+1)}B^{m/(m+1)}\), then \(M^{2(m+1)}\le A^2B^{2m}\), with every zero base to the zero power interpreted as one.

Lemma 327.5 Natural-power form of a moment comparison

✓

Let \(m,k\ge 0\) be integers and let \(B,M,D\ge 0\). If \(D^kB\le M^{2(m+1)/(2m+1)}\), then \((D^kB)^{2m+1}\le M^{2(m+1)}\), using natural powers and \(0^0=1\).

Lemma 327.6 An algebraic second-moment comparison

✓

Let \(m,k\ge 0\) be integers and \(A,B,M,C,D\) be real numbers with \(B\gt 0\), \(C\ge 1\), and \(CD=1\). If \((D^kB)^{2m+1}\le M^{2(m+1)}\) and \(M^{2(m+1)}\le A^2B^{2m}\), then \(B\le (C^{m+1})^{2k}A^2\).

Lemma 327.7 Finite exponential degree factor

✓

Let \(m\ge 1\) and \(k\ge 0\) be integers, let \(A,M\ge 0\) and \(B\gt 0\), and put \(t=(2m+1)/(m+1)\). If \((t-1)^kB\le M^{2/t}\) and \(M\le A^{2-t}B^{t-1}\), then \(B\le ((1+1/m)^{m+1})^{2k}A^2\).

Theorem 327.8 Limit of the finite degree factors

✓

For every integer \(k\ge 0\), the sequence \(((1+1/m)^{m+1})^{2k}\) converges to \(e^{2k}\) as the positive integer \(m\to \infty \).

Theorem 327.9 Endpoint of a family of norm comparisons

✓

Let \(k\ge 0\) be an integer and \(A,B\in \mathbb R\). If \(B\le ((1+1/m)^{m+1})^{2k}A^2\) for every integer \(m\ge 2\), then \(B\le e^{2k}A^2\).

Theorem 327.10 Sharp exponential first-to-second moment bound

✓

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\). Let \(P(x)=\sum _{S\subseteq [n]}a_S\chi _S(x)\) with real coefficients; degree at most \(k\) means \(a_S=0\) for \(|S|\gt k\). If \(P\) has degree at most the integer \(k\ge 0\), then \(e^{-2k}\sum _{S\subseteq [n]}a_S^2\le (\mathbb E|P|)^2\).