TCSLib

282 Boolean Analysis — Two Point

282.1 Overview

Generalized binomial coefficients yield the normalized reverse two-point estimate. Positive homogeneity and continuity extend the result to all nonnegative one-bit functions.

282.2 Declarations

Lemma 282.1 Generalized binomial series
✓

Let \(s,x\in \mathbb {R}\) with \(|x|\lt 1\), the generalized binomial series converges and \(\sum _{k=0}^{\infty }\binom {s}{k}x^k=(1+x)^s\), where \(\binom {s}{k}=s(s-1)\cdots (s-k+1)/k!\) and \(\binom {s}{0}=1\).

Lemma 282.2 Summability of the even binomial series
✓

For every \(s,x\in \mathbb {R}\) with \(|x|\lt 1\), the series \(\sum _{k=0}^{\infty }\binom {s}{2k}x^{2k}\) is summable, with generalized binomial coefficients.

Lemma 282.3 Even part of the binomial expansion
✓

Let \(s,x\in \mathbb {R}\) with \(|x|\lt 1\), \(((1+x)^s+(1-x)^s)/2=\sum _{k=0}^{\infty }\binom {s}{2k}x^{2k}\), using generalized binomial coefficients.

Let \(s,b\in \mathbb {R}\) with \(|b|\lt 1\), uniform one-bit expectation satisfies \(\mathbb {E}_{t\in \{ 0,1\} }|1+b(-1)^t|^s=((1+b)^s+(1-b)^s)/2\).

Lemma 282.5 Second generalized binomial coefficient
✓

For every \(s\in \mathbb {R}\), the generalized binomial coefficient satisfies \(\binom {s}{2}=s(s-1)/2\).

Lemma 282.6 Recurrence between even binomial coefficients
✓

Let \(s\in \mathbb {R}\) and \(k\in \mathbb N\), the generalized binomial coefficients satisfy \(\binom {s}{2k+2}=\binom {s}{2k}(s-2k)(s-2k-1)/((2k+1)(2k+2))\).

Lemma 282.7 Signs of even binomial coefficients
✓

Let \(0\lt s\lt 1\). For every integer \(k\ge 1\), the generalized binomial coefficient satisfies \(\binom {s}{2k}\le 0\).

Lemma 282.8 Borell scalar factor estimate
✓

Let \(0\lt q\lt p\lt 1\), \(\rho \ge 0\), \(\rho ^2=(1-p)/(1-q)\), and \(m\in \mathbb N\) with \(m\ge 2\). Then \(\rho (m-q)\le m-p\).

Lemma 282.9 Successor comparison of even coefficients
✓

Let \(0\lt q\lt p\lt 1\), \(\rho \ge 0\), \(\rho ^2=(1-p)/(1-q)\), and integer \(K\ge 1\). If \(\binom p{2K}\le (p/q)\binom q{2K}\rho ^{2K}\), then \(\binom p{2K+2}\le (p/q)\binom q{2K+2}\rho ^{2K+2}\), with generalized binomial coefficients.

Lemma 282.10 Comparison of even binomial coefficients
✓

Let \(0\lt q\lt p\lt 1\), \(\rho \ge 0\), and \(\rho ^2=(1-p)/(1-q)\). For every integer \(k\ge 1\), \(\binom p{2k}\le (p/q)\binom q{2k}\rho ^{2k}\), with generalized binomial coefficients.

Lemma 282.11 Normalized reverse two-point inequality
✓

Let \(0\lt q\lt p\lt 1\), \(\rho \ge 0\), \(\rho ^2=(1-p)/(1-q)\), and \(|a|\lt 1\). For \(f(t)=1+a(-1)^t\) on \(\{ 0,1\} \), \(M_q(T_\rho f)\ge M_p(f)\), where \(M_r(u)=(\mathbb {E}|u|^r)^{1/r}\) under the uniform measure. For \(d\in \mathbb N\), \(h:\{ 0,1\} ^d\to \mathbb {R}\), and \(\tau \in \mathbb {R}\), the spectral noise operator is \(T_\tau h(x)=\sum _{S\subseteq [d]}\tau ^{|S|}\widehat h(S)\chi _S(x)\), where \(\chi _S(x)=(-1)^{\sum _{i\in S}x_i}\) and \(\widehat h(S)=\mathbb {E}[h\chi _S]\) under the uniform measure.

Lemma 282.12 The two one-bit strings
✓

Every point of \(\{ 0,1\} ^1\) is either the string whose only coordinate is \(0\) or the string whose only coordinate is \(1\).

Lemma 282.13 Normalizing a nonnegative one-bit function
✓

For every nonnegative function \(f:\{ 0,1\} \to [0,\infty )\) that is not identically zero, there exist \(c\gt 0\) and \(a\in [-1,1]\) such that \(f(t)=c(1+a(-1)^t)\) for both bits \(t\).

Lemma 282.14 Continuity of affine one-bit means
✓

For every \(s\gt 0\), the map \(a\mapsto (\mathbb {E}_{t\in \{ 0,1\} }|1+a(-1)^t|^s)^{1/s}\) is continuous on \(\mathbb {R}\).

Let \(0\lt q\lt p\lt 1\), \(\rho \ge 0\), and \(\rho ^2=(1-p)/(1-q)\). Every \(f:\{ 0,1\} \to [0,\infty )\) satisfies \(M_q(T_\rho f)\ge M_p(f)\), where \(M_r(u)=(\mathbb {E}|u|^r)^{1/r}\) under the uniform measure. For \(d\in \mathbb N\), \(h:\{ 0,1\} ^d\to \mathbb {R}\), and \(\tau \in \mathbb {R}\), the spectral noise operator is \(T_\tau h(x)=\sum _{S\subseteq [d]}\tau ^{|S|}\widehat h(S)\chi _S(x)\), where \(\chi _S(x)=(-1)^{\sum _{i\in S}x_i}\) and \(\widehat h(S)=\mathbb {E}[h\chi _S]\) under the uniform measure.