328 Boolean Analysis — Majority
328.1 Overview
This chapter records exact Fourier coefficients, relations between Fourier levels, and dimensional monotonicity and asymptotics for majority on an odd number of variables. Boolean inputs are expressed as signs, with false encoded by \(1\) and true by \(-1\); majority returns the sign held by more than half of the coordinates, so no tie occurs.
328.2 Declarations
For each \(k\in \mathbb N\), define the real number
Let \(m\in \mathbb N\), put \(n=2m+1\), and define \(M_m:\{ \pm 1\} ^n\to \mathbb R\) by \(M_m(x)=1\) when more than \(m\) coordinates equal \(1\), and \(M_m(x)=-1\) otherwise. Then \(M_m(x)\in \{ 1,-1\} \) for every \(x\in \{ \pm 1\} ^n\).
Let \(m\in \mathbb N\), put \(n=2m+1\), and define \(M_m:\{ \pm 1\} ^n\to \mathbb R\) by \(M_m(x)=1\) when more than \(m\) coordinates equal \(1\), and \(M_m(x)=-1\) otherwise. Then \(M_m(-x)=-M_m(x)\) for every \(x\in \{ \pm 1\} ^n\), where \(-x\) negates every coordinate.
Let \(n\in \mathbb N\) and \(f:\{ \pm 1\} ^n\to \mathbb R\); for \(S\subseteq \{ 1,\ldots ,n\} \) define \(\widehat f(S)=2^{-n}\sum _{x\in \{ \pm 1\} ^n}f(x)\prod _{i\in S}x_i\), and for every \(k\in \mathbb N\) define \(W_k(f)=\sum _{|S|=k}\widehat f(S)^2\). Then \(W_k(f)\ge 0\) for every \(k\in \mathbb N\).
Let \(n\in \mathbb N\) and \(f:\{ \pm 1\} ^n\to \mathbb R\); for \(S\subseteq \{ 1,\ldots ,n\} \) define \(\widehat f(S)=2^{-n}\sum _{x\in \{ \pm 1\} ^n}f(x)\prod _{i\in S}x_i\), and for every \(k\in \mathbb N\) define \(W_k(f)=\sum _{|S|=k}\widehat f(S)^2\). Then \(W_k(f)=0\) for every \(k\in \mathbb N\) with \(n\lt k\).
Let \(n\in \mathbb N\) and \(f:\{ \pm 1\} ^n\to \mathbb R\); for \(S\subseteq \{ 1,\ldots ,n\} \) define \(\widehat f(S)=2^{-n}\sum _{x\in \{ \pm 1\} ^n}f(x)\prod _{i\in S}x_i\), and for every \(k\in \mathbb N\) define \(W_k(f)=\sum _{|S|=k}\widehat f(S)^2\). For every \(g:\mathbb N\to \mathbb R\),
Let \(n\in \mathbb N\), \(\rho \in \mathbb R\), and \(f:\{ \pm 1\} ^n\to \mathbb R\); for \(S\subseteq \{ 1,\ldots ,n\} \) define \(\chi _S(x)=\prod _{i\in S}x_i\), \(\widehat f(S)=2^{-n}\sum _{x\in \{ \pm 1\} ^n}f(x)\chi _S(x)\), \(W_k(f)=\sum _{|S|=k}\widehat f(S)^2\) for \(k\in \mathbb N\), and \(T_\rho f(x)=\sum _{S\subseteq \{ 1,\ldots ,n\} }\rho ^{|S|}\widehat f(S)\chi _S(x)\). The noise stability \(\operatorname {Stab}_\rho (f)=2^{-n}\sum _{x\in \{ \pm 1\} ^n}f(x)T_\rho f(x)\) satisfies
Let \(n\in \mathbb N\) and \(f:\{ \pm 1\} ^n\to \mathbb R\) satisfy \(f(x)\in \{ 1,-1\} \) for every \(x\); for \(S\subseteq \{ 1,\ldots ,n\} \) define \(\widehat f(S)=2^{-n}\sum _{x\in \{ \pm 1\} ^n}f(x)\prod _{i\in S}x_i\) and \(W_k(f)=\sum _{|S|=k}\widehat f(S)^2\) for \(k\in \mathbb N\). Then \(\sum _{k=0}^n W_k(f)=1\).
Let \(N\in \mathbb N\), \(\rho \in [0,1]\), and \(a,b:\mathbb N\to \mathbb R\) satisfy \(\sum _{k=0}^{j-1}b(k)\le \sum _{k=0}^{j-1}a(k)\) for every integer \(0\le j\le N\) and \(\sum _{k=0}^{N-1}b(k)=\sum _{k=0}^{N-1}a(k)\), with sums over no indices interpreted as zero. Then
Let \(m\in \mathbb N\), put \(n=2m+1\), and define \(M_m:\{ \pm 1\} ^n\to \mathbb R\) by \(M_m(x)=1\) when more than \(m\) coordinates equal \(1\), and \(M_m(x)=-1\) otherwise. For \(S\subseteq \{ 1,\ldots ,n\} \) define \(\widehat M_m(S)=2^{-n}\sum _{x\in \{ \pm 1\} ^n}M_m(x)\prod _{i\in S}x_i\). If \(S\subseteq \{ 1,\ldots ,n\} \) has even cardinality, then \(\widehat M_m(S)=0\).
Let \(m\in \mathbb N\), put \(n=2m+1\), and define \(M_m:\{ \pm 1\} ^n\to \mathbb R\) by \(M_m(x)=1\) when more than \(m\) coordinates equal \(1\), and \(M_m(x)=-1\) otherwise. For \(S\subseteq \{ 1,\ldots ,n\} \) define \(\widehat M_m(S)=2^{-n}\sum _{x\in \{ \pm 1\} ^n}M_m(x)\prod _{i\in S}x_i\). If \(S\subseteq \{ 1,\ldots ,n\} \) has cardinality \(2r+1\) for an integer \(r\ge 0\), then
For all \(m,p,q\in \mathbb N\) with \(p+q=m\), the binomial coefficients satisfy the real identity
Let \(m\in \mathbb N\), put \(n=2m+1\), and define \(M_m:\{ \pm 1\} ^n\to \mathbb R\) by \(M_m(x)=1\) when more than \(m\) coordinates equal \(1\), and \(M_m(x)=-1\) otherwise. For \(S\subseteq \{ 1,\ldots ,n\} \) define \(\widehat M_m(S)=2^{-n}\sum _{x\in \{ \pm 1\} ^n}M_m(x)\prod _{i\in S}x_i\). If \(S,T\subseteq \{ 1,\ldots ,n\} \) satisfy \(|S|+|T|=2m+2\), then
Let \(m\in \mathbb N\), put \(n=2m+1\), and define \(M_m:\{ \pm 1\} ^n\to \mathbb R\) by \(M_m(x)=1\) when more than \(m\) coordinates equal \(1\), and \(M_m(x)=-1\) otherwise. For \(S\subseteq \{ 1,\ldots ,n\} \) define \(\widehat M_m(S)=2^{-n}\sum _{x\in \{ \pm 1\} ^n}M_m(x)\prod _{i\in S}x_i\), and for every \(k\in \mathbb N\) define \(W_k(M_m)=\sum _{|S|=k}\widehat M_m(S)^2\). If \(k\in \mathbb N\) is even, then \(W_k(M_m)=0\).
Let \(m\in \mathbb N\), put \(n=2m+1\), and define \(M_m:\{ \pm 1\} ^n\to \mathbb R\) by \(M_m(x)=1\) when more than \(m\) coordinates equal \(1\), and \(M_m(x)=-1\) otherwise. For \(S\subseteq \{ 1,\ldots ,n\} \) define \(\widehat M_m(S)=2^{-n}\sum _{x\in \{ \pm 1\} ^n}M_m(x)\prod _{i\in S}x_i\), and for every \(k\in \mathbb N\) define \(W_k(M_m)=\sum _{|S|=k}\widehat M_m(S)^2\). For every odd \(k\in \mathbb N\), put \(r=(k-1)/2\); then
where \(\binom ab=0\) for \(b\gt a\) and a real quotient with zero denominator is interpreted as zero.
Let \(m\in \mathbb N\), put \(n=2m+1\), and define \(M_m:\{ \pm 1\} ^n\to \mathbb R\) by \(M_m(x)=1\) when more than \(m\) coordinates equal \(1\), and \(M_m(x)=-1\) otherwise. For \(S\subseteq \{ 1,\ldots ,n\} \) define \(\widehat M_m(S)=2^{-n}\sum _{x\in \{ \pm 1\} ^n}M_m(x)\prod _{i\in S}x_i\), and for every \(k\in \mathbb N\) define \(W_k(M_m)=\sum _{|S|=k}\widehat M_m(S)^2\). For every \(k\in \mathbb N\) with \(k\le 2m+1\),
For all \(N,k,a\in \mathbb N\) satisfying \(N=k+a\), the binomial coefficients satisfy
For each \(q\in \mathbb N\), define \(M_q:\{ \pm 1\} ^{2q+1}\to \mathbb R\) to equal \(1\) when more than \(q\) coordinates equal \(1\), and \(-1\) otherwise; for \(S\subseteq \{ 1,\ldots ,2q+1\} \) define \(\widehat M_q(S)=2^{-(2q+1)}\sum _{x\in \{ \pm 1\} ^{2q+1}}M_q(x)\prod _{i\in S}x_i\), and for \(k\in \mathbb N\) define \(W_k(M_q)=\sum _{|S|=k}\widehat M_q(S)^2\). For every \(m,k\in \mathbb N\) with \(k\) odd and \(k\le 2m+1\), one has \(W_k(M_{m+1})\lt W_k(M_m)\).
For each \(q\in \mathbb N\), define \(M_q:\{ \pm 1\} ^{2q+1}\to \mathbb R\) to equal \(1\) when more than \(q\) coordinates equal \(1\), and \(-1\) otherwise; for \(S\subseteq \{ 1,\ldots ,2q+1\} \) define \(\widehat M_q(S)=2^{-(2q+1)}\sum _{x\in \{ \pm 1\} ^{2q+1}}M_q(x)\prod _{i\in S}x_i\), and for \(k\in \mathbb N\) define \(W_k(M_q)=\sum _{|S|=k}\widehat M_q(S)^2\). For each fixed odd integer \(k\ge 1\), set \(L_k=\frac{4}{\pi k2^k}\binom {k-1}{(k-1)/2}\); then \(\lim _{m\to \infty }W_k(M_m)=L_k\), and for every \(m\in \mathbb N\) satisfying \(k\le \lfloor (2m+1)/2\rfloor \) one has
For each \(q\in \mathbb N\), define \(M_q:\{ \pm 1\} ^{2q+1}\to \mathbb R\) to equal \(1\) when more than \(q\) coordinates equal \(1\), and \(-1\) otherwise; for \(S\subseteq \{ 1,\ldots ,2q+1\} \) define \(\widehat M_q(S)=2^{-(2q+1)}\sum _{x\in \{ \pm 1\} ^{2q+1}}M_q(x)\prod _{i\in S}x_i\), and for \(k\in \mathbb N\) define \(W_k(M_q)=\sum _{|S|=k}\widehat M_q(S)^2\). For every \(m,j\in \mathbb N\) satisfying \(j\le 2(m+1)+2\),
where both sums are zero when \(j=0\).
Let \(m\in \mathbb N\) and \(\rho \in [0,1]\), and for each \(q\in \mathbb N\) define \(M_q:\{ \pm 1\} ^{2q+1}\to \mathbb R\) to equal \(1\) when more than \(q\) coordinates equal \(1\), and \(-1\) otherwise. For any \(d\in \mathbb N\) and \(f:\{ \pm 1\} ^d\to \mathbb R\), define \(\operatorname {Stab}_\rho (f)=\mathbb E[f(X)f(Y)]\), where \(X\) is uniform on \(\{ \pm 1\} ^d\) and, independently in each coordinate, \(Y_i=-X_i\) with probability \((1-\rho )/2\) and \(Y_i=X_i\) otherwise; then
For each \(m\in \mathbb N\), define \(M_m:\{ \pm 1\} ^{2m+1}\to \mathbb R\) to equal \(1\) when more than \(m\) coordinates equal \(1\), and \(-1\) otherwise; for \(S\subseteq \{ 1,\ldots ,2m+1\} \) define \(\widehat M_m(S)=2^{-(2m+1)}\sum _{x\in \{ \pm 1\} ^{2m+1}}M_m(x)\prod _{i\in S}x_i\), \(W_k(M_m)=\sum _{|S|=k}\widehat M_m(S)^2\), and \(W_{\gt k}(M_m)=\sum _{|S|\gt k}\widehat M_m(S)^2\) for \(k\in \mathbb N\), and put \(A=(2/\pi )^{3/2}\). There exists one real constant \(C\ge 0\) such that for every \(m,k\in \mathbb N\) with \(k\) odd, \(k\gt 0\), and \(2k^2\le 2m+1\), both estimates hold: