Analysis of Boolean functions

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

There is an absolute $C>0$ such that any nontrivial transitive increasing event on $n\ge 2$ independent bits satisfies ${\mu }_q(A)>1-\epsilon$ if ${\mu }_p(A)>\epsilon$, $0<\epsilon <1/2$, and the displayed bound holds with $p<q<1$. A uniform weighted Kahn-Kalai-Linial theorem gives one pivotal probability at least $c{\mu }_r(A)(1-{\mu }_r(A))\log (n)/n$. Transitivity makes the total influence at least $c{\mu }_r(A)(1-{\mu }_r(A))\log n$. The Margulis–Russo formula identifies this with the derivative of ${\mu }_r(A)$. Integration of the derivative of its log odds proves the threshold bound.

For a Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ under the uniform probability measure, some coordinate has influence of a variable at least $c\mathrm{Var}(f)\log (n)/n$, where $c>0$ is an absolute constant and $I_i(f)$ is the probability that flipping coordinate $i$ changes $f$. For variance bounded below, this is order $\log (n)/n$. The tribes function shows that this order cannot be improved for general balanced Boolean functions.

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

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

The Boolean hypercube is the set $\{-1,1{\}}^n$, or equivalently $\{0,1{\}}^n$. Its hypercube graph joins two vertices exactly when they differ in one coordinate.

A face is obtained by fixing some coordinates of the Boolean hypercube and letting the remaining $d$ coordinates vary freely. It is isomorphic to $Q_d$. A two-dimensional face is a square with four vertices, and a face is contained in a set family when all its vertices belong to that family.

Order subsets first by increasing cardinality and, within each level, by lexicographic order, with the smallest differing coordinate belonging to the earlier set. This convention makes simplicial initial segments the extremizers in Harper theorem.

In the seven-dimensional Boolean hypercube, $C(63)$ contains every set of size at most three except $\{5,6,7\}$. Its external vertex boundary consists of that missing triple and all 35 four-sets. The complementary-size initial segment $C(65)$ contains every set of size at most three and $\{1,2,3,4\}$. Its external vertex boundary has the other 34 four-sets and three five-sets. Thus complementary family sizes do not impose a symmetric boundary profile.

In dimension three, the first three vertices are $\varnothing ,\{1\},\{2\}$. Their closed vertex neighbourhood has seven vertices. Adding $\{3\}$ does not change that vertex neighbourhood, so the external vertex boundary decreases from four to three even though both family sizes are at most half the cube.

For the Boolean hypercube, the initial segment of the simplicial order on the discrete cube minimizes the size of the closed vertex neighbourhood among families of a given size. Equivalently, it minimizes the external vertex boundary. This is a vertex assertion, distinct from the edge-isoperimetric inequality in the discrete cube.

For $n\ge 1$, a family of $2^{n-1}$ vertices in the Boolean hypercube has these minimum and maximum external vertex boundary sizes. The Harper theorem gives the minimum: in odd dimension take the lower half of the levels, and in even dimension add the middle-level sets containing coordinate one to all lower levels. The family of even Hamming weight attains the maximum, since every remaining vertex has an adjacent even-weight vertex.

If two nonempty set families on $m\ge 1$ coordinates have every cross-intersection greater than an integer $w\ge 0$, their density product obeys the displayed bound. Complementing the second set family separates it from the first by Hamming distance greater than $w$. Harper inequality bounds the first set family's radius-$w$ neighbourhood from below. If $S_m(a-1)<|\mathcal{F}|\le S_m(a)$, disjointness yields $|\mathcal{F}||\mathcal{G}|\le S_m(a)S_m(m-a-w)$. The binary entropy function tail estimate bounds these two factors by Gaussian tails; their deficits from the middle rank sum to at least $w$, proving the claim.

Equality in Harper theorem need not make a down-set a cube-automorphic image of a simplicial initial segment. In $Q_4$, take all sets of size at most one and the four two-element sets forming a four-cycle. This family has size nine and closed graph neighbourhood size fifteen, just like the size-nine simplicial order on the discrete cube initial segment. The induced degree of a vertex distributions differ, so they cannot be related by a graph automorphism.

Split a set family in the hypercube graph according to whether coordinate $i$ is present, and delete that coordinate from the present section. Replace both sections by initial segments of the simplicial order on the discrete cube with the same respective sizes. Induction and nesting of initial-segment closed graph neighbourhoods show that this operation cannot enlarge the original closed graph neighbourhood. Repeated nontrivial compressions terminate because the sum of simplicial positions strictly decreases.

A family fixed by every simplicial section compression is either an initial segment of the simplicial order on the discrete cube or that segment with its last vertex exchanged for the next vertex, where the exchanged vertices are complementary. Indeed, an earlier absent vertex and a later present vertex must differ in every coordinate, and cannot have another vertex between them. Complementary consecutive vertices occur only across the two central ranks in odd dimension, or at the transition from middle-rank sets containing coordinate one to those avoiding it in even dimension. Direct closed graph neighbourhood comparison resolves these exceptions in the proof of Harper theorem.

Adjoin all lower levels to a uniform set family before applying Harper theorem. Its remaining neighbourhood contribution is the upper shadow, so lexicographic initial segments minimize upper shadows. Complementation and reversal of coordinates turn this into colexicographic order minimizing the lower shadow, giving the Kruskal-Katona theorem.

Identify a vertex $(x_1,\dots ,x_n)$ with the integer ${\sum }_{i=1}^n{2}^{i-1}{x}_i$. Binary order is increasing order of these integers. Its initial segment of size $a$ has $F(a)={\sum }_{j=0}^{a-1}{s}_2(j)$ induced edges, where $s_2(j)$ is the Hamming weight of the binary expansion of $j$.

Fix a coordinate of the Boolean hypercube, delete it in each of the two sections, and replace each section by a binary initial segment of the same size. This preserves the total size. Mathematical induction on dimension proves that it does not decrease contained edge counts; the crossing contribution is the size of the section intersection, maximized by nested initial segments.

If both sections for every coordinate are binary initial segments, then the family itself is a binary initial segment, apart from the possible family $(\mathcal{P}([n-1])\setminus \{[n-1]\})\cup \{\{n\}\}$. Any missing vertex earlier than a present vertex must disagree with it in every coordinate; the two are therefore complementary and consecutive in binary order on the discrete cube, forcing this sole exceptional shape.

An initial segment of the binary order on the discrete cube contains the vertices whose integer encodings are $0,\dots ,m-1$. It is a down-set, so its internal edges and two-dimensional cube faces can be counted at their unique upper vertices by ${\sum }_{j<m}\mathrm{wt}(j)$ and ${\sum }_{j<m}\left(\genfrac{}{}{0ex}{}{\mathrm{wt}(j)}{2}\right)$.

For $F(a)={\sum }_{j=0}^{a-1}{s}_2(j)$ and nonnegative integers $a,b$, the displayed inequality follows by induction from $F(2r)=2F(r)+r$ and $F(2r+1)=F(r)+F(r+1)+r$. Splitting a vertex set of a hypercube graph into its two coordinate sections then proves the edge-isoperimetric theorem for binary initial segments.

The edge boundary of a vertex set $A$ consists of graph edges with exactly one endpoint in $A$. In a $d$-regular graph,where $e(A)$ counts edges with both endpoints in $A$.

For a finite graph with at least two vertices, the displayed minimum measures the fewest outgoing edges per vertex in a nonempty set occupying at most half the graph. It uses the edge boundary, rather than the external vertex boundary. For the hypercube graph $Q_n$, $n\ge 1$, it equals one: edge-isoperimetry gives the lower bound and a coordinate half-cube attains it.

For $A\subseteq \{0,1{\}}^n$,

Equivalently, $A$ spans at most $\frac{1}{2}|A|{\log }_2|A|$ cube edges. Induction on the dimension and concavity of binary entropy prove the inequality.

For a vertex set of size $m$ in a hypercube graph, split one coordinate into sections of sizes $a,b$. Induction bounds the internal edges within the sections by $(a{\log }_{2}a+b{\log }_{2}b)/2$; at most $\min (a,b)$ edges cross between them. Put $t=\min (a,b)/(a+b)$. The chord bound for the binary entropy function gives $H_2(t)\ge 2t$, hence $a{\log }_{2}a+b{\log }_{2}b+2\min (a,b)\le m{\log }_{2}m$. Thus at most $m{\log }_{2}m/2$ internal edges are present, and the edge boundary is at least $m(n-{\log }_{2}m)$. Coordinate subcubes attain equality when $m$ is a power of two.

For a nonempty subset of a hypercube graph, split it into sections of sizes $a,b$. The proof of the entropy edge bound uses $H_2(t)\ge 2t$, $t=\min (a,b)/(a+b)$. Strict concavity makes equality possible only at $t=0$ or $t=1/2$. In the first case one section is empty; in the second the sections coincide, since all possible crossing edges must be present. Induction forces a coordinate subcube. Conversely every coordinate subcube has the displayed edge count. At size $2^{n-1}$ these are exactly the two halves determined by fixing one coordinate.

Among subsets of the $n$-dimensional hypercube graph with $a$ vertices, initial segments of the binary order on the discrete cube minimize the edge boundary. Its exact minimum is $na-2{\sum }_{j=0}^{a-1}{s}_2(j)$. This strengthens the entropy lower bound on the same boundary.

Among families of a given size in the Boolean hypercube, a binary initial segment maximizes the number of contained two-dimensional cube faces. Under section compression in binary order, faces crossing the selected coordinate correspond to internal edges in the intersection of its two sections. The edge extremal theorem and mathematical induction control that contribution and the faces within the sections.

The binary entropy function isIt is concave on $[0,1]$ and satisfies $H_2(x)\ge 2x$ for $0\le x\le 1/2$ by comparison with the chord from $(0,0)$ to $(1/2,1)$.

A Boolean function is a function on a Boolean hypercube, often with codomain $\{-1,1\}$ or $\{0,1\}$.

Under uniform independent input bits, a zero-one Boolean function is quite fair when its mean lies between one quarter and three quarters. This convention excludes functions whose output is nearly constant; it does not require exact balance or equal coordinate influences.

The algebraic normal form is the unique multilinear polynomial representation of a Boolean function over the field with two elements, using exclusive or for addition and ordinary bit multiplication for products. The empty product is one. Existence and uniqueness follow by induction from $f(z^{\prime },z_d)=f(z^{\prime },0)\oplus z_d(f(z^{\prime },0)\oplus f(z^{\prime },1))$: the first polynomial supplies all coefficients not containing $z_d$, and the difference supplies exactly those that do. For split inputs $(x,y)$, each monomial factors into one locally computed product of Alice's bits and one of Bob's bits, yielding a separated Boolean decomposition.

Every Boolean function of distributed inputs is an exclusive or of products of locally computable bits. The displayed identity follows because exactly one indicator is one. It uses at most $2^m$ terms, each a function of $x$ times a function of $y$; exchanging the two input roles gives at most $2^n$ terms. This elementary truth-table factorization is useful for distributed computation with PR boxes and does not depend on a probabilistic approximation.

A $p$-random restriction independently leaves each coordinate live with probability $p$, otherwise fixing it to zero or one with probability $(1-p)/2$ each. Composing independent restrictions with live probabilities $p_1,\dots ,p_d$ produces the same distribution with live probability ${\prod }_j{p}_j$. Fixed values stay unbiased.

A tribes function is an OR of AND blocks: partition $mw$ coordinates into $m$ blocks of size $w$, and let $f=1$ when at least one block consists entirely of ones. For independent random variables with each bit uniform, $\mathbb{P}(f=0)=(1-2^{-w}{)}^m$. The influence of a variable is $2^{-(w-1)}(1-2^{-w}{)}^{m-1}$, because every other bit in its block must be one and every other block must fail. Taking $m$ approximately $(\log 2)2^w$ keeps both output probabilities bounded away from zero and gives influences of order $\log (mw)/(mw)$. This shows the order in the Kahn-Kalai-Linial theorem is sharp.

Choose $w\ge 1$ maximal such that $wm\le n$ for the displayed $m$, and take the OR of $m$ AND blocks of size $w$, ignoring unused coordinates. Its failure probability is $(1-2^{-w}{)}^m$, between one quarter and three quarters. Active coordinates have influence $2^{1-w}(1-2^{-w}{)}^{m-1}$ and unused ones have zero influence. Maximality gives $2^{1-w}<4(\log 2)(w+1)/n$; for $n\ge 2$, $w\le {\log }_{2}n$, so every influence is below $8\log n/n$. The construction is therefore a quite fair Boolean function with small influences for every $n\ge 2$. The logarithmic bound cannot hold at $n=1$, where every quite fair function has influence one.

For $m$ tribes of size $w$ with $m\sim (\log 2)2^w$ and $n=mw$, the success probability under the p-biased product measure is $1-(1-p^w{)}^m$. Its $x$-quantile is $p_x=[1-(1-x{)}^{1/m}{]}^{1/w}$. For fixed $0<x<1$,Thus the fixed-error window has order $1/\log n$. For small fixed error the leading coefficient grows with $\log (1/\epsilon )$, so the general Friedgut-Kalai sharp threshold theorem also has the correct error dependence up to absolute constants.

For an input $x$, count the largest family of pairwise disjoint nonempty sets of coordinates such that flipping each set individually changes the Boolean function value. Maximizing over inputs gives block sensitivity. Sensitive sets need not be contiguous and need not consist of single bits. The standard bounded-error quantum query complexity lower bound is $\Omega (\sqrt{\mathrm{bs}(f)})$. A certificate for $f(x)$ meets every sensitive set, so its size bounds their disjoint count.

A Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ is a monotone function when $x_i\le y_i$ for every $i$ implies $f(x)\le f(y)$.

For $f:\{-1,1{\}}^n\to \mathbb{R}$, the characters ${\chi }_S(x)={\prod }_{i\in S}{x}_i$ form an orthonormal basis, and the Fourier-Walsh expansion is

On the finite Boolean hypercube, these coefficients are the Hadamard transform of the vector of function values, with expectation normalization.

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 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 independent coordinate flips at rate $1/2$, a Walsh character $w_A$ is an eigenfunction with eigenvalue $-|A|$. The generator is self-adjoint and negative semidefinite. Its Dirichlet form of a Markov chain is $-\mathbb{E}[fLf]=\frac{1}{4}{\sum }_i\mathbb{E}(f({\omega }^{(i)})-f(\omega ){)}^2$.

Global sign-even functions have zero coefficients on odd-size Walsh characters. Every nonconstant remaining character has generator eigenvalue at most $-2$, yielding the displayed improvement from gap one to gap two. Combining this with the convexity of a norm proves the sharp Rademacher second-moment inequality.

For $S\subseteq [n]$, the Walsh character on the Boolean hypercube is ${\chi }_S(x)={\prod }_{i\in S}{x}_i$, equivalently $(-1{)}^{{\sum }_{i\in S}{x}_i}$ in the zero-one convention.

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 $p$-biased Fourier coefficient of $f$ at $S$ is ${\hat{f}}_p(S)={\mathbb{E}}_{{\mu }_p}[f{\varphi }_S]$.

On the unbiased cube, the discrete derivative isFor the p-biased product measure, the normalization factor is $\sigma /2$.

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

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.

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.

For the indicator $f$ of a monotone family under a p-biased product measure, the Margulis–Russo formula identifies the derivative of ${\mathbb{E}}_{{\mu }_p}f$ with the suitably normalized total influence of $f$.

A coordinate is pivotal for an increasing event in a configuration when changing only that coordinate changes whether the event occurs. Its pivotal probability is the coordinate's influence.

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

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.

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 stability is

The linear Fourier weight is $W_1(f)={\sum }_{|S|=1}\hat{f}(S{)}^2$.

A $J$-junta is a function whose value depends only on coordinates indexed by $J$. A $k$-junta depends on at most $k$ coordinates.

If $f:\{-1,1{\}}^n\to \{-1,1\}$ satisfies $\Vert f^{\le k}{\Vert }_2^2\ge 1-\epsilon$, then it has a real-valued $J$-junta approximation $g$ with $\Vert f-g{\Vert }_2^2\le 2\epsilon$ and

For every $\epsilon >0$, a Boolean function $f$ has an $\exp (O(\mathbf{I}(f)/\epsilon ))$-junta approximation with squared $L^2$ error at most $2\epsilon$.

Every Boolean function of degree at most $k$ is a $k{2}^{k-1}$-junta.

A Boolean function $f:\{0,1{\}}^n\to \{0,1\}$ is $(\epsilon ,p,r)$-quasirandom when conditioning any set of at most $r$ coordinates to any values changes its ${\mu }_p$-expectation by at most $\epsilon$.

For every $\epsilon ,p,r,\delta$, there is $T$ such that every Boolean function has a set $J$ with $|J|\le T$ for which a ${\mu }_p$-random restriction on $J$ leaves an $(\epsilon ,p,r)$-quasirandom function with probability at least $1-\delta$.

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

One form of the hypercontractive inequality is $\Vert T_{1/\sqrt{3}}f{\Vert }_4\le \Vert f{\Vert }_2$, where $T_{\rho }$ is the noise operator on the Boolean hypercube.

If a nonzero function on the Boolean hypercube has degree at most $k$, then its support has measure at least $2^{-k}$. This sharp bound follows by induction on the dimension.

Arrow's theorem says that a rank-order voting system with at least three alternatives cannot simultaneously satisfy unrestricted preferences, unanimity, independence of irrelevant alternatives, and absence of a dictator.

The Condorcet paradox is a cycle in collective pairwise preferences even though each individual voter's preference is transitive.

Let $X_i$ and $Y_i$ be independent, centered, variance-one random variables with vanishing third moments and fourth moments at most $9$. If $f$ is multilinear of degree at most $k$ and $\Vert {\psi }^{(4)}{\Vert }_{\infty }\le M$, then

The Lindeberg replacement method, inspired by the Lindeberg condition, compares functions of two independent random vectors by replacing their coordinates one at a time. Matching moments cancel the corresponding terms in a Taylor expansion.