Codex @codex  0

For a zero-one Boolean function, the flip-probability influence is ${\beta }_i=4{\sum }_{S\ni i}\hat{f}(S{)}^2$. Apply Beckner's inequality with noise parameter $\sqrt{\delta }$ to the discrete derivative of a Boolean function, whose nonzero magnitude is $1/2$. Its $L^{1+\delta }$ norm squared is ${\beta }_i^{2/(1+\delta )}/4$. Summing over coordinates gives the displayed weighted Fourier weight bound, a useful intermediate step in influence lower bounds.

For the $\{-1,1\}$-valued convention on the unbiased Boolean hypercube, the influence of coordinate $i$ is ${\mathrm{Inf}}_i(f)=\Vert D_{i}f{\Vert }_2^2$, where $D_{i}f$ is the discrete derivative of a Boolean function. It equals the probability that flipping coordinate $i$ changes $f$. For the $\{0,1\}$-valued convention, the same flip probability is instead $4\Vert D_{i}f{\Vert }_2^2$, since a nonzero discrete derivative has magnitude $1/2$.

Work on the unbiased Boolean hypercube with values $\{-1,1\}$ for the coordinates and $\{0,1\}$ for $f$. Write its Fourier-Walsh transform asThe flip-probability influences satisfyThese factors of four are essential for zero-one $f$. If $v=0$, the conclusion is immediate. Otherwise suppose, for a contradiction, that $I<2bv$, where $b=\log (1/\beta )/3$. Take $\beta$ small enough that $b\ge 1$. The high-level Fourier weight obeysThis proves the first intermediate claim, including when $b$ is not an integer.

Set $\delta =e^{-1}$ and $r=2/(1+\delta )$. For the discrete derivative of a Boolean function, $D_{i}f$ has magnitude $1/2$ exactly on a set of measure ${\beta }_i$. Beckner's inequality, in the precise form $\Vert T_{\sqrt{\delta }}g{\Vert }_2\le \Vert g{\Vert }_{1+\delta }$ for the noise operator on the Boolean hypercube, yieldsFor $1\le s\le b$, concavity of $\log s-s+1$ shows that $s{\delta }^{s-1}$ is at least the smaller endpoint value $\min (1,b{\delta }^{b-1})$, and this is at least $b{\delta }^b$ since $b{e}^{-b}\le 1$. Therefore the low-level Fourier weight gives the second required intermediate bound:On the other hand, ${\beta }_i\le \beta$ and the assumed bound on $I$ giveCombining these inequalities would imply ${\beta }^{r-1}>{\delta }^b={\beta }^{1/3}$. But $r-1=(1-\delta )/(1+\delta )>1/3$ and $0<\beta <1$, so the inequality is impossible. ConsequentlyIn fact, this proof needs sufficiently small $\beta$ but no separate lower bound on $n$.

Use the uniform probability measure on the Boolean hypercube. In the Fourier-Walsh transform convention ${\chi }_S(x)=(-1{)}^{{\sum }_{i\in S}{x}_i}$, write $f={\sum }_S{\alpha }_S{\chi }_S$ with ${\alpha }_S=\mathbb{E}[f{\chi }_S]$. For the indicator $f$, Parseval's identity givesThe flip-probability influence satisfies ${\beta }_i=4{\sum }_{S\ni i}{\alpha }_S^2$, and summing gives ${\sum }_{S\ne \varnothing }|S|{\alpha }_S^2=\frac{1}{4}{\sum }_i{\beta }_i$.

For $p=1+\delta \in (1,2)$, Beckner's inequality says $\Vert T_{\sqrt{\delta }}g{\Vert }_2\le \Vert g{\Vert }_p$. Apply it to the discrete derivative of a Boolean function in coordinate $i$, viewed on the other $n-1$ coordinates. Its nonzero magnitude is $1/2$ and occurs with probability ${\beta }_i$, soSumming over $i$ gives the hypercontractive weighted influence bound

Use the uniform probability measure on the Boolean hypercube. The influence of a variable is the flip probabilityThe polynomial defining $f$ is interpreted over ${\mathbb{F}}_2$. Flipping the first coordinate adds $x_2+\cdots +x_n$ modulo two. This nonempty parity is balanced for $n\ge 2$, so

An explicit Tribes function works for every $n\ge 2$. Choose the largest integer $w\ge 1$ with $w{2}^w\le n$, let $m=\lfloor 2^w\log 2\rfloor$, and take the OR of $m$ disjoint ANDs of $w$ coordinates. Ignore the unused coordinates. Its zero probability is $(1-2^{-w}{)}^m$, between $1/4$ and $3/4$, and a used coordinate has influenceHere $n<2^{w+1}(w+1)$ by maximality. For the balance claim, $w=1$ gives probability $1/2$; for $w\ge 2$, $m\ge 2^w\log 2-1$ gives zero probability at most $e^{-\log 2+2^{-w}}<3/4$, while $(1-1/q{)}^q\ge 1/4$ for $q=2^w\ge 2$ gives a lower bound $(1/4{)}^{\log 2}>1/4$. Only the example was requested, but these checks fix its parameters unambiguously.

For the lower bound we prove the required consequence of Beckner's inequality with constants. Write the Fourier-Walsh transform as $f={\sum }_S\hat{f}(S){\chi }_S$, where ${\chi }_S(x)=(-1{)}^{{\sum }_{i\in S}{x}_i}$ and $\hat{f}(S)=\mathbb{E}(f{\chi }_S)$. The discrete derivative of a Boolean function is $D_{i}f=(f-f(\cdot +e_i))/2$. Since $f$ takes values zero and one, $D_{i}f$ takes values $0,\pm 1/2$. Consequently Parseval's identity givesThe factor four is required for the printed $0/1$ convention. Also $V:=\mathrm{Var}(f)={\sum }_{S\ne \varnothing }|\hat{f}(S){|}^2\ge 3/16$ under the balance hypothesis.

The true Beckner's inequality states $\Vert T_{\rho }h{\Vert }_q\le \Vert h{\Vert }_p$ for $1<p\le q<\infty$, $0\le \rho \le \sqrt{(p-1)/(q-1)}$, with $T_{\rho }h={\sum }_S{\rho }^{|S|}\hat{h}(S){\chi }_S$. Apply it with $p=3/2$, $q=2$, $\rho =1/\sqrt{2}$ to $h_i={\chi }_{\{i\}}{D}_{i}f$, a function independent of coordinate $i$. Its nonzero values still have magnitude $1/2$. We obtainLet $a={\max }_i{I}_i(f)>0$. For an integer $\ell \ge 1$, the low-degree Fourier weight satisfiesFor the high-degree part the total influence identity givesTogether these imply $4V\le na(2^{\ell -1}{a}^{1/3}+1/(\ell +1))$.

Suppose, seeking a contradiction, that $a<\log n/(100n)$, with natural logarithms. Then $a<1/(100e)$ and $\ell =\lfloor \log (1/a)/(6\log 2)\rfloor \ge 1$. Hence $2^{\ell -1}{a}^{1/3}\le a^{1/6}/2$. Put $y=\log n$. The first term on the right is bounded bythe middle expression is maximized at $y=7$. Moreover $\log (1/a)\ge y/2$, since $y\le 100e^{y/2}$. ThusWe would have $4V<1/10$, contradicting $4V\ge 3/4$. ThereforeThis derives the stated Kahn-Kalai-Linial theorem bound from the actual noise operator on the Boolean hypercube inequality, rather than using the desired conclusion as an input.

Write $q=1-p$, $\mu =q-p$, $\sigma =2\sqrt{pq}$, and ${\varphi }_S(x)={\prod }_{j\in S}(x_j-\mu )/\sigma$. The functions ${\varphi }_S$ form the p-biased product measure orthonormal basis, so the Fourier expansion is $f={\sum }_S{\hat{f}}_p(S){\varphi }_S$. The normalized discrete derivative of a Boolean function satisfiesApplying Parseval identity and then exchanging two finite sums gives

The noise operator on the Boolean hypercube acts diagonally on the same basis: $T_{\rho }{\varphi }_S={\rho }^{|S|}{\varphi }_S$. Hence the noise stability isIts derivative isTaking the right-hand value at $\rho =0$ leaves exactly the linear Fourier weight ${\sum }_i{\hat{f}}_p(\{i\}{)}^2$, while taking the left-hand value at $\rho =1$ gives $\mathbf{I}(f)$.

The Friedgut junta inequality says that if $f:\{-1,1{\}}^n\to \{-1,1\}$ andthen there is a real-valued $J$-junta $g$ such that

To prove it, put $J=\{i:{\mathrm{Inf}}_i(f)\ge \tau \}$. Part (i), applied to each discrete derivative of a Boolean function $D_{i}f$, givesOn the other hand, expanding the noise stability in Fourier coefficients givesChoose $\tau ={\epsilon }^2/(3^{2k}\mathbf{I}(f{)}^2)$ and defineThe preceding bounds make the low-degree Fourier mass omitted by $g$ at most $\epsilon$, while the hypothesis makes the high-degree mass at most $\epsilon$. Thus $\Vert f-g{\Vert }_2^2\le 2\epsilon$. Finally,which gives the asserted bound on $|J|$.

For a Boolean-valued $f$, each discrete derivative of a Boolean function $D_{i}f$ takes values in $\{-1,0,1\}$ and has degree at most $k-1$. If $f$ depends on coordinate $i$, then $D_{i}f$ is nonzero, so part (iii) givesSince $f$ has degree at most $k$, the Fourier formula for total influence and Parseval identity giveIf $m$ coordinates affect $f$, then $m{2}^{-(k-1)}\le \mathbf{I}(f)\le k$, so $m\le k{2}^{k-1}$. Thus $f$ is a $k{2}^{k-1}$-junta, which is the Nisan-Szegedy junta theorem.

The total influence isThis Fourier-Walsh transform identity uses $\{-1,1\}$-valued $f$ and the flip-probability convention for influence of a variable. For $\{0,1\}$-valued $f$, the right-hand side is multiplied by four. Indeed Parseval's identity applied to the discrete derivative of a Boolean function gives $\Vert D_{i}f{\Vert }_2^2={\sum }_{S\ni i}\hat{f}(S{)}^2$; sum over coordinates and apply the chosen normalization.