123 Boolean Analysis — Decision Tree Fourier
123.1 Overview
This module develops the Fourier spectrum of a function computed by a decision tree (O’Donnell Proposition 3.16). A recursive coefficient function computes the Fourier expansion of the \(\pm 1\)-encoded tree function by structural induction, using the branch identity \(f = (f_{\mathrm{lo}} + f_{\mathrm{hi}})/2 + \chi _i (f_{\mathrm{lo}} - f_{\mathrm{hi}})/2\) together with \(\chi _i \chi _S = \chi _{S \triangle \{ i\} }\). From this recursion the module reads off the degree bound, the spectral \(1\)-norm bound, granularity of the coefficients, and sparsity of the Fourier support, and restates the degree bound in terms of the minimum decision-tree depth \(\mathrm{dtDepth}\) as needed downstream in the LMN pipeline.
123.2 Declarations
The size of a decision tree, defined as its number of leaves: a leaf has size \(1\), and a branch has size equal to the sum of the sizes of its two subtrees.
The \(\pm 1\)-valued function computed by a decision tree \(T\), namely \(x \mapsto \mathrm{boolToSign}(T.\mathrm{eval}\, x)\), where \(\mathrm{false} \mapsto 1\) and \(\mathrm{true} \mapsto -1\).
The coefficient function \(\mathrm{coeffs}\, T : \mathcal{P}(\mathrm{Fin}\, n) \to \mathbb {R}\) defined by structural recursion on \(T\). A leaf labelled \(b\) assigns \(\mathrm{boolToSign}(b)\) to the empty frequency and \(0\) to all others; a branch on variable \(i\) with subtrees \(\mathrm{lo}, \mathrm{hi}\) assigns to \(S\) the value
For a fixed \(i\), the map \(S \mapsto S \triangle \{ i\} \) on subsets of \(\mathrm{Fin}\, n\) is involutive.
For any \(g : \mathcal{P}(\mathrm{Fin}\, n) \to \mathbb {R}\) and any \(i\),
the sums ranging over all subsets \(S\) of \(\mathrm{Fin}\, n\).
For all \(S\), \(i\), and \(x\) in the Boolean cube, \(\chi _{S \triangle \{ i\} }(x) = \chi _S(x)\cdot \mathrm{boolToSign}(x_i)\).
For all \(S\) and \(i\), \(\left\lvert S\right\rvert - 1 \le \left\lvert S \triangle \{ i\} \right\rvert \), the subtraction being truncated subtraction on \(\mathbb {N}\).
For every decision tree \(T\) and every point \(x\) of the Boolean cube,
If \(T.\mathrm{depth} \lt \left\lvert S\right\rvert \), then \(\mathrm{coeffs}\, T\, S = 0\): frequencies of cardinality exceeding the tree depth carry no weight.
For every decision tree \(T\),
i.e. the spectral \(1\)-norm of the coefficients is at most the number of leaves.
If \(T.\mathrm{depth} \le k\), then for every \(S\) there is an integer \(m\) with \(\mathrm{coeffs}\, T\, S \cdot 2^k = m\).
For every \(S\) there is an integer \(m\) with \(\mathrm{coeffs}\, T\, S = m / 2^{T.\mathrm{depth}}\); that is, every coefficient is an integer multiple of \(2^{-T.\mathrm{depth}}\).
Every decision tree satisfies \(T.\mathrm{size} \le 2^{T.\mathrm{depth}}\): a tree of depth \(k\) has at most \(2^k\) leaves.
For any coefficient family \(c\) and any frequency \(T\), the Fourier coefficient of the explicit combination \(x \mapsto \sum _{S} c(S)\, \chi _S(x)\) at \(T\) equals \(c(T)\).
For every decision tree \(T\) and every \(S\), the Fourier coefficient \(\widehat{T.\mathrm{signEval}}(S)\) equals \(\mathrm{coeffs}\, T\, S\); the recursively defined coefficients are exactly the Fourier coefficients.
The function computed by a decision tree of depth \(k\) has Fourier degree at most \(k\): \(T.\mathrm{signEval}\) has degree at most \(T.\mathrm{depth}\).
For every decision tree \(T\),
i.e. \(\lVert \widehat{f}\rVert _1 \le s\) for the tree size \(s\).
For every \(S\) there is an integer \(m\) with \(\widehat{T.\mathrm{signEval}}(S) = m / 2^{T.\mathrm{depth}}\): every Fourier coefficient is an integer multiple of \(2^{-k}\), where \(k\) is the tree depth.
The Fourier support of \(T.\mathrm{signEval}\), i.e. the set of frequencies \(S\) with \(\widehat{T.\mathrm{signEval}}(S) \ne 0\), has cardinality at most \(T.\mathrm{size}\cdot 2^{T.\mathrm{depth}}\).
The Fourier support of \(T.\mathrm{signEval}\) has cardinality at most \(4^{T.\mathrm{depth}}\).
For every Boolean function \(f : \{ 0,1\} ^n \to \{ 0,1\} \) there exists a decision tree \(T\) with \(T.\mathrm{depth} \le \mathrm{dtDepth}\, f\) that computes \(f\), i.e. \(T.\mathrm{eval}\, x = f(x)\) for all \(x\).
For every Boolean function \(f\), the \(\pm 1\)-encoding \(x \mapsto \mathrm{boolToSign}(f(x))\) has Fourier degree at most \(\mathrm{dtDepth}\, f\), the minimum depth of a decision tree computing \(f\). This is the implication \(\mathrm{DT}(f) \le k \Rightarrow \deg (f) \le k\) used as input to O’Donnell’s Lemma 4.21.