Fix \(n \in \mathbb {N}\) and an index \(i \in \{ 0, 1, \dots , n-1\} \). The map on subsets of \(\{ 0, 1, \dots , n-1\} \) that sends each set \(S\) to its symmetric difference \(S \triangle \{ i\} \) with the singleton \(\{ i\} \) is an involution: applying it twice returns every set to itself, so \(\bigl(S \triangle \{ i\} \bigr) \triangle \{ i\} = S\) for all \(S\).

Fix \(n \in \mathbb {N}\), let \(i\) be an element of \(\{ 0, 1, \dots , n-1\} \), and let \(g\) assign a real number to each subset of \(\{ 0, 1, \dots , n-1\} \). Then summing \(g\) over all subsets is unaffected by first toggling the membership of \(i\); that is,

where both sums range over all subsets \(S \subseteq \{ 0, 1, \dots , n-1\} \) and \(S \mathbin {\triangle } \{ i\} \) denotes the symmetric difference of \(S\) with the singleton \(\{ i\} \).

Let \(S\subseteq [n]\), let \(i\in [n]\), and let \(x\in \{ 0,1\} ^n\). Then the Walsh–Fourier character indexed by the symmetric difference \(S\mathbin {\triangle }\{ i\} \) satisfies

where \(\sigma \) is the sign encoding \(\sigma (x_i)=(-1)^{x_i}\).

Let \(S\) be a finite subset of \(\{ 0,1,\dots ,n-1\} \) and let \(i\) be one of these indices. Then the symmetric difference \(S \triangle \{ i\} \) satisfies

where \(\left\lvert S\right\rvert - 1\) denotes truncated subtraction on the natural numbers (so it is \(0\) when \(S\) is empty).

Let \(T\) be a decision tree on \(n\) Boolean variables, computing the \(\pm 1\)-valued sign-encoded function \(x \mapsto \sigma (T(x))\), where \(\sigma \) is the sign encoding sending \(\mathrm{false}\) to \(1\) and \(\mathrm{true}\) to \(-1\). For every point \(x \in \{ 0,1\} ^n\),

where the sum ranges over all subsets \(S\) of \([n]\), \(c_T(S)\) denotes the recursively defined coefficient of \(T\) at the frequency \(S\), and \(\chi _S\) is the Walsh character of \(S\).

Let \(T\) be a decision tree on \(n\) Boolean variables, and let \(S \subseteq \{ 0,1,\dots ,n-1\} \) be a set of variables whose cardinality \(\left\lvert S\right\rvert \) exceeds the depth of \(T\). Then the coefficient assigned to the frequency \(S\) vanishes, \(\mathrm{coeffs}\, T\, S = 0\).

Let \(T\) be a decision tree on \(n\) Boolean variables, and for each subset \(S \subseteq \{ 0,\dots ,n-1\} \) let \(\mathrm{coeffs}\, T\, (S)\) denote its recursively defined Fourier coefficient at frequency \(S\). Then the total absolute mass of these coefficients is bounded by the number of leaves of \(T\):

Let \(T\) be a decision tree on \(n\) Boolean variables, and write \(\mathrm{coeffs}(T) : \mathcal{P}(\{ 0,\dots ,n-1\} ) \to \mathbb {R}\) for its recursively defined coefficient function. If \(k\) is a natural number with \(\mathrm{depth}(T) \le k\), then for every set \(S\) of variables the scaled coefficient \(\mathrm{coeffs}(T)(S)\cdot 2^{k}\) is an integer; that is, there exists \(m \in \mathbb {Z}\) with \(\mathrm{coeffs}(T)(S)\cdot 2^{k} = m\).

Let \(T\) be a decision tree on \(n\) Boolean variables, and let \(S \subseteq \{ 0,\dots ,n-1\} \) be a frequency set. Then the coefficient \(\mathrm{coeffs}\, T\, S\) is a dyadic rational with denominator \(2^{\mathrm{depth}(T)}\): there exists an integer \(m \in \mathbb {Z}\) such that

Equivalently, every such coefficient is an integer multiple of \(2^{-\mathrm{depth}(T)}\).

Let \(T\) be a decision tree on \(n\) Boolean variables, with size (number of leaves) \(\mathrm{size}(T)\) and depth \(\mathrm{depth}(T)\). Then \(\mathrm{size}(T) \le 2^{\mathrm{depth}(T)}\); that is, a decision tree of depth \(k\) has at most \(2^{k}\) leaves.

Fix \(n\), let \(c\) assign a real number \(c(S)\) to each subset \(S \subseteq [n]\), and consider the Boolean function \(f(x) = \sum _{S \subseteq [n]} c(S)\, \chi _S(x)\), where \(\chi _S\) is the Walsh–Fourier character of \(S\). Then for every \(T \subseteq [n]\) the Fourier–Walsh coefficient of \(f\) at frequency \(T\) recovers the corresponding coefficient, namely \(\hat f(T) = c(T)\).

For every Boolean function \(f : (\mathrm{Fin}\, n \to \mathrm{Bool}) \to \mathrm{Bool}\), there is a decision tree \(T\) on the \(n\) Boolean variables whose depth is at most the decision-tree depth of \(f\) and which computes \(f\), meaning \(T\) evaluates to \(f(x)\) on every input \(x\).