255 Boolean Analysis — Basic

255.1 Overview

Fourier truncations, stable influences, and coordinate juntas support quantitative approximation on the uniform Boolean cube. The module includes low degree error bounds and counting estimates for bounded-size subsets.

255.2 Declarations

Definition 255.1 Noisy coordinate influence

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube, \(i\in [n]\), and \(\rho \in \mathbb R\). Define \(I_i^{(\rho )}(f)=\sum _{S\ni i}\rho ^{|S|-1}\widehat f(S)^2\), with natural exponents, including \(\rho =0\).

Definition 255.2 Low degree Fourier truncation

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube and \(k\in \mathbb N\). Define \(f^{\le k}(x)=\sum _{|S|\le k}\widehat f(S)\chi _S(x)\), where \(\chi _S(x)=\prod _{i\in S}(-1)^{x_i}\).

Definition 255.3 High degree Fourier part

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube and \(k\in \mathbb N\). Define \(f^{\gt k}(x)=\sum _{|S|\gt k}\widehat f(S)\chi _S(x)\), where \(\chi _S(x)=\prod _{i\in S}(-1)^{x_i}\).

Definition 255.4 Influential coordinate set

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube and \(\tau \in \mathbb R\). Define \(J_\tau (f)=\{ i\in [n]:I_i(f)\ge \tau \} \). 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.

Definition 255.5 Real-valued coordinate juntas

✓

For every \(g:\{ 0,1\} ^n\to \mathbb R\) and \(J\subseteq [n]\), say that \(g\) is a \(J\)-junta if \(g(x)=g(y)\) whenever \(x_i=y_i\) for every \(i\in J\).

Definition 255.6 Squared second-norm distance

✓

For every \(f,g:\{ 0,1\} ^n\to \mathbb R\), define \(d_2(f,g)^2=\mathbb E_x(f(x)-g(x))^2\) under the uniform distribution on the Boolean cube.

Lemma 255.7 Noisy influence at one

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube and \(i\in [n]\). Then \(I_i^{(1)}(f)=I_i(f)\). 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.

Lemma 255.8 Sum of noisy influences

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube and \(\rho \in \mathbb R\). Then \(\sum _iI_i^{(\rho )}(f)=\sum _{S\subseteq [n]}|S|\rho ^{|S|-1}\widehat f(S)^2\), using natural powers.

Lemma 255.9 Total influence sum

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube. Then \(I(f)=\sum _{i=0}^{n-1}I_i(f)\). 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)\).

Lemma 255.10 Boolean second moment

✓

Let \(f:\{ 0,1\} ^n\to \{ -1,1\} \) be a function on the uniform Boolean cube. Then \(\mathbb Ef^2=1\).

Lemma 255.11 Squared Fourier weight identity

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube. Then \(\sum _{S\subseteq [n]}\widehat f(S)^2=\mathbb Ef^2\).

Lemma 255.12 Fourier truncation reconstruction

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube, \(k\in \mathbb N\), and \(x\in \{ 0,1\} ^n\). Then \(f^{\le k}(x)+f^{\gt k}(x)=f(x)\), where the two parts retain Fourier coefficients with \(|S|\le k\) and \(|S|\gt k\), respectively.

Lemma 255.13 Coefficients of low degree truncation

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube, \(k\in \mathbb N\), and \(S\subseteq [n]\). Then \(\widehat{f^{\le k}}(S)=\widehat f(S)\) if \(|S|\le k\), and zero otherwise.

Lemma 255.14 Squared truncation error

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube and \(k\in \mathbb N\). Then \(\mathbb E(f-f^{\le k})^2=\sum _{|S|\gt k}\widehat f(S)^2\).

Lemma 255.15 Fourier tail influence bound

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube and a positive integer \(k\). Then \(\sum _{|S|\gt k}\widehat f(S)^2\le I(f)/k\). 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)\).

Lemma 255.16 Low degree approximation

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube and a positive integer \(k\). Then \(\mathbb E(f-f^{\le k})^2\le I(f)/k\). 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)\).

Lemma 255.17 Number of influential coordinates

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube and \(\tau \gt 0\). Then \(|\{ i:I_i(f)\ge \tau \} |\le I(f)/\tau \). 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)\).

Lemma 255.18 Influential-coordinate approximation

✓

Let \(f:\{ 0,1\} ^n\to \mathbb R\) be a function on the uniform Boolean cube, \(k\in \mathbb N\), and \(\tau \gt 0\). There exists \(g:\{ 0,1\} ^n\to \mathbb R\) depending only on \(J_\tau (f)=\{ i:I_i(f)\ge \tau \} \) such that \(\mathbb E(f^{\le k}-g)^2\le n\tau \). 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.

Lemma 255.19 Counting bounded-size subsets

✓

For any finite set \(s\) and \(k\in \mathbb N\), the number of subsets \(t\subseteq s\) with \(|t|\le k\) is at most \((|s|+1)^k\).