257 Boolean Analysis — DNF
257.1 Overview
Bounded-width disjunctive normal forms have explicit Fourier tails and total influence bounds. These estimates yield Boolean junta approximations whose coordinate count is polynomial in reciprocal error for each fixed width.
257.2 Declarations
Let \(d\) be a DNF on \(n\) variables of width at most a positive integer \(w\). Suppose every term has no repeated literals and any two literals in a term sharing a variable are equal. For every \(t\in \mathbb N\), its sign encoding \(f(x)=(-1)^{d(x)}\) satisfies \(\sum _{|S|\gt 120w(t+1)}\widehat f(S)^2\le 8\, 2^{-t}\) under the uniform cube law.
Let \(d\) be a DNF on \(n\) variables of width at most a positive integer \(w\), and let \(t\in \mathbb N\). Its sign encoding \(f(x)=(-1)^{d(x)}\) satisfies \(\sum _{|S|\gt 120w(t+1)}\widehat f(S)^2\le 8\, 2^{-t}\) under the uniform cube law.
Let \(d\) be a DNF on \(n\) variables and let \(x\in \{ 0,1\} ^n\) satisfy \(d(x)=1\). The number of coordinates whose individual flip changes the sign encoding \((-1)^{d(x)}\) is at most the width of \(d\).
For every DNF \(d\) on \(n\) variables, the total influence under the uniform cube law of \(x\mapsto (-1)^{d(x)}\) is at most twice the width of \(d\). For a real cube function \(h\), define \(I_i(h)=\tfrac 14\mathbb E_x(h(x)-h(x^{(i)}))^2\), where \(x^{(i)}\) flips coordinate \(i\) and \(\mathbb E_x\) is uniform expectation, and \(I(h)=\sum _{i=0}^{n-1}I_i(h)\).
There exists an absolute \(C\gt 0\) such that for every positive integer \(w\) and \(0\lt \varepsilon \le 1/2\), there exists \(t\in \mathbb N\) satisfying \(8\, 2^{-t}\le \varepsilon \) and \(((2w)^3/\varepsilon ^2)9^{120w(t+1)}\le (1/\varepsilon )^{Cw}\).
There exists an absolute \(C\gt 0\) such that for every DNF \(d\) on \(n\) variables of width at most \(w\in \mathbb N\) and every \(0\lt \varepsilon \le 1\), there exist \(J\subseteq [n]\) and \(h:\{ 0,1\} ^n\to \{ -1,1\} \) depending only on \(J\), with \(|J|\le (1/\varepsilon )^{Cw}\) and \(\Pr _x((-1)^{d(x)}\ne h(x))\le \varepsilon \) under the uniform cube law.