A Boolean function \(f : \{ 0,1\} ^n \to \{ 0,1\} \) is linear if and only if there exists a set \(S \subseteq [n]\) such that the \(\pm 1\) lift \(\texttt{BoolBLR.lift\_ pm1}\, f\) equals the Fourier character \(\chi _S\).

For any \(f : \{ 0,1\} ^n \to \{ 0,1\} \),

For any \(f : \{ 0,1\} ^n \to \mathbb {R}\),

For any \(f : \{ 0,1\} ^n \to \{ 0,1\} \), letting \(\hat{g}(S)\) denote the Fourier coefficient of \(g = \texttt{BoolBLR.lift\_ pm1}\, f\),

Let \(f, g : \{ 0,1\} ^n \to \{ 0,1\} \), let \(S \subseteq [n]\), and suppose \(\texttt{BoolBLR.lift\_ pm1}\, g = \chi _S\) and \(\operatorname{dist}(f, g) \ge \varepsilon \). Then the Fourier coefficient of \(\texttt{BoolBLR.lift\_ pm1}\, f\) at \(S\) satisfies \(\widehat{\texttt{BoolBLR.lift\_ pm1}\, f}(S) \le 1 - 2\varepsilon \).

If \(f : \{ 0,1\} ^n \to \{ 0,1\} \) is \(\varepsilon \)-far from linear, then for every \(S \subseteq [n]\),

If \(f : \{ 0,1\} ^n \to \{ 0,1\} \) is \(\varepsilon \)-far from linear, then the sum of cubed Fourier coefficients of \(\texttt{BoolBLR.lift\_ pm1}\, f\) satisfies

This follows by combining the per-coefficient bound \(\hat{f}(S) \le 1-2\varepsilon \) with the Parseval identity \(\sum _S \hat{f}(S)^2 = 1\).

If \(f : \{ 0,1\} ^n \to \{ 0,1\} \) is linear, then \(\texttt{BoolBLR.BLR\_ accept\_ prob}\, f = 1\); that is, the BLR test accepts every linear function with probability \(1\).

If \(f : \{ 0,1\} ^n \to \{ 0,1\} \) is \(\varepsilon \)-far from linear, then

That is, a function that is \(\varepsilon \)-far from every linear function causes the BLR test to reject with probability at least \(\varepsilon \).

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be linear. Then for every \(s \subseteq [n]\), writing \(\mathbf{1}_s\) for the indicator vector of \(s\) and \(e_i\) for the \(i\)-th basis vector, the value \(f(\mathbf{1}_s)\) is false when

and true otherwise; that is, \(f(\mathbf{1}_s)\) is the parity of the number of \(i \in s\) with \(f(e_i) = \texttt{true}\).

Specialization of the previous lemma to the support of an arbitrary point: if \(f : \{ 0,1\} ^n \to \{ 0,1\} \) is linear, then for every \(x \in \{ 0,1\} ^n\) the value \(f(x)\) is the parity of the number of coordinates \(i\) with \(x_i = \texttt{true}\) and \(f(e_i) = \texttt{true}\).

For every \(S \subseteq [n]\) and all \(x, y \in \{ 0,1\} ^n\),

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) satisfy \(\texttt{BoolBLR.lift\_ pm1}\, f = \chi _S\) for some \(S \subseteq [n]\), and let \(x, y \in \{ 0,1\} ^n\). Assuming the multiplicativity identity \(\chi _S(x \oplus y) = \chi _S(x)\chi _S(y)\), one has

Restatement of the support formula in the exact form used inside the proof of the character criterion: for linear \(f\) and any \(x \in \{ 0,1\} ^n\), \(f(x)\) is the parity of the number of coordinates \(i\) with \(x_i = \texttt{true}\) and \(f(e_i) = \texttt{true}\).

If \(\texttt{BoolBLR.lift\_ pm1}\, f = \chi _S\) for some \(S \subseteq [n]\), then for all \(x, y \in \{ 0,1\} ^n\),

This is the previous lemma with the multiplicativity hypothesis discharged.

Write \(g = \texttt{BoolBLR.lift\_ pm1}\, f\). For all \(x, y \in \{ 0,1\} ^n\),

Write \(g = \texttt{BoolBLR.lift\_ pm1}\, f\). For every \(x \in \{ 0,1\} ^n\),

i.e. the self-convolution of \(g\) has Fourier coefficients \(\hat{g}(S)^2\).

Write \(g = \texttt{BoolBLR.lift\_ pm1}\, f\) and assume \((g * g)(x) = \sum _S \hat{g}(S)^2 \chi _S(x)\) for all \(x\). Then

For all \(f, g : \{ 0,1\} ^n \to \{ 0,1\} \) and every \(x \in \{ 0,1\} ^n\),

For every \(f : \{ 0,1\} ^n \to \{ 0,1\} \), the \(\pm 1\) lift \(g = \texttt{BoolBLR.lift\_ pm1}\, f\) has unit Fourier mass:

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be \(\varepsilon \)-far from linear and write \(g = \texttt{BoolBLR.lift\_ pm1}\, f\). Then for every \(S \subseteq [n]\),

If \(f : \{ 0,1\} ^n \to \{ 0,1\} \) is linear, then \(f(x \oplus y) = f(x) \oplus f(y)\) for all \(x, y \in \{ 0,1\} ^n\).

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) satisfy \(f(x \oplus y) = f(x) \oplus f(y)\) for all \(x, y\), and write \(g = \texttt{BoolBLR.lift\_ pm1}\, f\). Then \(g\) is multiplicative on XOR: