Past exam of the mathematics course of the University of Cambridge / 2003 / iii / Paper 7 / 5

A Boolean function takes each vector of bits to either zero or one. Use independent uniform input bits; the influence of a variable is the probability that flipping that bit changes the value. A quite fair Boolean function has $1/4\le \mathbb{E}f\le 3/4$. All logarithms in the estimates below are natural, except where a base is explicitly written.

Here is a balanced tribes construction with unused coordinates valid for every $n\ge 2$. For each $w\ge 1$ put $m_w=\lfloor (\log 2)2^w\rfloor$, and choose the largest $w$ with $w{m}_w\le n$. Partition $w{m}_w$ of the bits into $m=m_w$ blocks of size $w$. Let $f$ be one when at least one block is all ones, and ignore the other bits. This is a tribes function. With $s=2^{-w}$, its zero probability is $(1-s{)}^m$.

For $w=1$ the function is a single bit and has mean $1/2$. For $w\ge 2$, $ms\le \log 2$ and $ms\ge \log 2-s$. The elementary inequalities $-s/(1-s)\le \log (1-s)\le -s$ giveThus both output probabilities are between one quarter and three quarters.

A used bit is pivotal exactly when the other $w-1$ bits of its block are one and every other block fails. Hence its influence is $2^{1-w}(1-2^{-w}{)}^{m-1}\le 2^{1-w}$; unused bits have zero influence. Maximality of $w$ gives $n<(w+1)m_{w+1}\le (w+1)(\log 2)2^{w+1}$. Also $w\le {\log }_{2}n$ for $n\ge 2$: this is immediate for $w=1$, while for $w\ge 2$ one has $w{m}_w\ge 2^w$. ThereforeThis proves the requested existence with room in the constant. The dimension-one boundary case cannot satisfy the printed logarithmic bound: a quite fair function of one bit is nonconstant and has influence one, whereas $10\log 1=0$. Thus the statement requires the usual nontrivial range $n\ge 2$ (or its intended large-$n$ interpretation).

Use normalized Fourier-Walsh transform coefficients $\hat{g}(\xi )=2^{-n}{\sum }_{x}g(x)(-1{)}^{x\cdot \xi }$. The Hamming weight $|\xi |$ counts the nonzero coordinates. Norms on the input cube use uniform probability, and a frequency integral here is counting over $\xi \in {\mathbb{F}}_2^n$. A common alternative normalization multiplies both sides of the requested comparison by the same factor and does not change it.

Beckner's inequality states that for $1<p\le q<\infty$ and $0\le \rho \le \sqrt{(p-1)/(q-1)}$, the noise operator on the Boolean hypercube, with coefficients $\widehat{T_{\rho }g}(\xi )={\rho }^{|\xi |}\hat{g}(\xi )$, satisfies $\Vert T_{\rho }g{\Vert }_q\le \Vert g{\Vert }_p$. In particular choose $q=2$, $p=4/3$, $\rho =1/\sqrt{3}$.

Let $g=1_A$ and $\alpha =|A|/2^n$. Then $\Vert g{\Vert }_{4/3}^2={\alpha }^{3/2}$. On frequencies of weight at most two, ${\rho }^{2|\xi |}\ge 1/9$, so Beckner's inequality and Parseval's identity give the low-degree Fourier mass of a sparse Boolean set estimateThe indicator function is real and the cube characters are real, so the displayed squares equal the squared absolute values. Total Fourier weight is $\sum \hat{g}(\xi {)}^2=\Vert g{\Vert }_2^2=\alpha$. If $2^n>2003$, then $0<\alpha \le 1/2003$ and $9\sqrt{\alpha }\le 9/\sqrt{2003}<1/2$, since $2003>18^2$. ThereforeThis establishes the strict comparison for every power $N=2^n>2003$, not merely for an unspecified very large threshold. The original PDF supplies the density condition and Beckner request, both missing from the converted TeX.