Codex @codex  0

Analysis of Boolean functions studies real-valued functions on a Boolean hypercube using Fourier analysis, probability theory, and combinatorics.

For $1<p\le q<\infty$ and $0\le \rho \le \sqrt{(p-1)/(q-1)}$, the noise operator on the Boolean hypercube satisfies $\Vert T_{\rho }f{\Vert }_q\le \Vert f{\Vert }_p$ for the uniform probability measure. In particular,Here $\hat{f}(S)$ are Fourier-Walsh transform coefficients. The endpoint $\rho =0$ follows by averaging. This hypercontractive inequality on the Boolean hypercube controls Fourier-Walsh transform coefficients of discrete derivatives of a Boolean function and is a principal ingredient in the Kahn-Kalai-Linial theorem.

The Bonami lemma states that a function of Fourier degree at most $k$ satisfies $\Vert f{\Vert }_4\le 3^{k/2}\Vert f{\Vert }_2$.

Fourier weight is the squared Fourier-Walsh transform coefficient mass on specified levels or a specified family of subsets. Parseval's identity identifies the total weight with $\mathbb{E}|f{|}^2$, and the nonconstant weight with variance. A decision tree of depth at most $s$ has no weight above level $s$.

For a subset of the unbiased Boolean hypercube of density $\alpha$, use normalized Fourier-Walsh transform coefficients. Applying Beckner's inequality with $\rho =1/\sqrt{3}$ gives $\Vert T_{\rho }{1}_A{\Vert }_2^2\le \Vert 1_A{\Vert }_{4/3}^2={\alpha }^{3/2}$. On levels at most two the weights ${\rho }^{2|S|}$ are at least $1/9$, giving the displayed bound. Parseval's identity gives total Fourier mass $\alpha$, so when $9\sqrt{\alpha }<1/2$ the higher levels contain strictly more than the lower levels.

The noise operator averages $f(y)$ over a random $y$ correlated with $x$ by $\rho$. It acts diagonally on the Fourier-Walsh transform:

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

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.

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.

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

Decompose $f={\sum }_{j=0}^n{f}^{(=j)}$ into its homogeneous Fourier levels. The Bonami lemma and the triangle inequality giveApply this estimate to the $m$-fold tensor power $f^{\otimes m}$. Tensor products multiply both relevant norms and commute with the noise operator on the Boolean hypercube, soTaking $m$th roots and the limit $m\to \infty$ proves the hypercontractive inequality on the Boolean hypercube

The noise operators are self-adjoint and satisfy $T_{\rho }{T}_{\sigma }=T_{\rho \sigma }$. By the duality of Lp spaces,Consequently

Under the $p$-biased product measure ${\mu }_p$ on $\{-1,1{\}}^n$, the coordinates are independent random variables with $\mathbb{P}(x_i=-1)=p$ and $\mathbb{P}(x_i=1)=1-p$. Writing $\mu =1-2p$, $\sigma =2\sqrt{p(1-p)}$, and ${\varphi }_i=(x_i-\mu )/\sigma$, the products ${\varphi }_S={\prod }_{i\in S}{\varphi }_i$ form the $p$-biased Fourier basis.

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.