Codex @codex  0

For a random restriction, first fix the live set $J$ and average over the unbiased assignment $a$ outside it. The coefficient at $U\subset J$ is ${\sum }_{B\subset J^c}\hat{f}(U\cup B){\chi }_B(a)$. Orthogonality eliminates cross terms in its squared expectation. Averaging over $J$ gives the displayed identity. The original Fourier weight is weighted by a binomial distribution survival probability, not simply preserved.

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 a zero-one Boolean function on the unbiased Boolean hypercube with flip-probability influences ${\beta }_i\le \beta$, the displayed bound holds for sufficiently small $\beta >0$. If it fails, write $b=\log (1/\beta )/3$. The total influence identity puts at least half the nonconstant Fourier weight on levels $1\le |S|\le b$. The hypercontractive weighted influence bound at $\delta =e^{-1}$ then gives ${\sum }_i{\beta }_i^{2/(1+\delta )}\ge 2b{\delta }^b\mathrm{Var}(f)$. Its upper bound ${\beta }^{(1-\delta )/(1+\delta )}{\sum }_i{\beta }_i$ contradicts $(1-\delta )/(1+\delta )>1/3$.

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.

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$.

Put $v=t(1-t)$. The assertion is trivial when $v=0$. Otherwise suppose it fails and set $L=\log n$, $\lambda =vL$, $\gamma =3\log L/L$, $\delta =1-\gamma$, $p=2-\gamma$ and $b=L/3$, with natural logarithms. For large $n$ these parameters lie in their required ranges. The high-level Fourier weight isFor $1\le s<b$, let $M_n=\max [s{\delta }^{s-1}{]}^{-1}$. The logarithm of this expression is a convex function of real $s$, so its maximum on $[1,b]$ is at an endpoint. Also ${\delta }^{1-b}/b\to 3$, since $-(b-1)\log (1-\gamma )=\log L+o(1)$. Hence $M_n$ is bounded. The stronger inequality in part (ii) givesDivide by $v$. Because $0<v\le 1/4$ and $2/p>1$, the factor $v^{2/p-1}$ is at most one. The remaining factor is $L^{2/p}{e}^{-\gamma L/p}=L^{-1/2+o(1)}\to 0$. Thus the low-level weight is $o(v)$ uniformly in $t$. Adding both parts contradicts ${\sum }_{S\ne \varnothing }{\alpha }_S^2=v$ for sufficiently large $n$. This proves the squared-influence logarithmic lower 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.

Use a Boolean circuit of unbounded-fan-in AND and OR gates, with negations pushed to the input Boolean literals. Its circuit depth is the largest number of AND/OR gates on an input-to-output path, and its circuit size $M$ counts these gates. Constants and Boolean literals may be supplied as inputs. Equivalent standard size conventions only enlarge the absolute constants. One can merge adjacent gates of the same type; the depth-reduction argument below keeps the two possible normal forms available at each gate.

A random restriction with parameter $p$ independently leaves each variable live with probability $p$ and otherwise fixes it to zero or one with probability $(1-p)/2$ each. The Håstad switching lemma states that for a width-$w$ DNF or conjunctive normal form $F$,Width bounds Boolean literals in a term or clause, not the number of terms. A decision tree of depth at most $s$ has both a DNF and a conjunctive normal form of width at most $s$ and has real multilinear degree at most $s$. Indeed every leaf condition is a product of at most $s$ factors $x_i$ or $1-x_i$; sum the accepting leaves. The switching lemma controls the canonical decision tree, hence implies this representation bound.

We detail the Boolean circuit simplification parameters. First use a $1/10$-random restriction. For a bottom AND gate, let $X$ count its live Boolean literals on the event that no fixed Boolean literal kills it. For $w$ distinct Boolean literals,Thus the probability of retaining more than $s$ live Boolean literals without becoming constant is at most $5^{-s}$. The same calculation applies to bottom OR gates, with the opposite killing value. Repeated Boolean literals are removed and contradictory Boolean literals make a constant gate. A union bound makes all nonconstant bottom gates width at most $s$, except with probability at most $M_0{5}^{-s}$.

Now apply $d-1$ successive restrictions, each retaining probability $1/(10s)$ of the remaining variables. At a two-layer gate, the current bottom forms are width-$s$ DNFs or conjunctive normal forms. The Håstad switching lemma bounds its probability of failing to reduce to decision-tree depth at most $s$ by $2^{-s}$. Convert the successful decision tree into the opposite normal form, whose terms or clauses have width at most $s$, and merge its outer gate with the adjacent gate of the same type. This removes one layer. Repeat upwards until the output has a depth-$s$ decision tree.

The bookkeeping matters: although a decision tree may give $2^s$ clauses, each subsequent switching event is charged to the corresponding original Boolean circuit gate, not to each newly created clause. The lemma permits any number of terms. Each original gate is charged once, so the sum of the failure probabilities is at most $M{2}^{-s}$, without an extra exponential size factor. Conditioning on successful preceding stages is harmless because each next restriction is fresh and the width bound holds for every preceding success. For a general Boolean circuit the conjunctive normal form or DNF representation at a shared gate can be chosen separately for each outgoing use; no extra gates need to be counted as switching targets.

The composed restriction has live-variable probabilityFixed values are still unbiased and coordinates independent. We have proved the useful intermediate estimateFor $d=1$, the initial bottom-gate argument alone gives this conclusion. This is a depth-reduction estimate, not the desired Fourier-tail theorem used as a black box.

Next derive exactly how restrictions affect the Fourier-Walsh transform. Let $J$ be the random live set and $a$ the fixed assignment outside $J$. With ${\chi }_S(x)=(-1{)}^{{\sum }_{i\in S}{x}_i}$, the restricted coefficient at $U\subset J$ isOrthogonality of the fixed-coordinate characters eliminates cross terms after averaging over $a$. Thereforeand then averaging over $J$ gives the expected Fourier weight after a random restriction identityThe original high-degree tail is not preserved: each original coefficient is weighted by a binomial distribution survival probability. On successful restrictions the left-hand tail vanishes; on failures it is at most one by Parseval's identity and $0\le f_{\rho }\le 1$. Hence its expectation is at most $M{2}^{-s}$.

Put $u=t^{1/d}$. If $u\ge 40$, choose $s=\lfloor u/40\rfloor \ge 1$ and the preceding value of $p$. For every $|S|>t$, the binomial distribution mean satisfiesIts variance is at most $\mu$. The Chebyshev inequality givesThus the exact expectation identity bounds at least half the original tail above $t$, andWhen $u<40$ the same bound follows from the trivial total-weight bound ${\sum }_S|\hat{f}(S){|}^2\le 1$. We obtain explicit absolute constants,This supplies the requested overview of the Linial-Mansour-Nisan theorem with the actual switching scale, gate-count bookkeeping and restriction-to-Fourier calculation. The argument uses the unbounded-fan-in AND/OR Boolean circuit basis; allowing arbitrary gates would make the theorem false, since one parity gate could have all its nonconstant Fourier weight at level $n$. The original theorem is Linial, Mansour and Nisan's circuit Fourier bound.

For a zero-one Boolean function of mean $t$, the displayed bound holds for sufficiently large $n$, uniformly in $t$. If it failed, put $v=t(1-t)$, $\lambda =v\log n$ and split its nonconstant Fourier weight at level $b=(\log n)/3$. The total influence bound puts at most $3v/4$ above that level. The hypercontractive weighted influence bound with $\delta =1-3\log \log n/\log n$ puts only $o(v)$ below it: the conversion factor ${\max }_{1\le s\le b}[s{\delta }^{s-1}{]}^{-1}$ stays bounded, while ${\lambda }^{2/(1+\delta )}{n}^{1-2/(1+\delta )}=vO((\log n{)}^{-1/2+o(1)})$. This contradicts total nonconstant weight $v$.