Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean function. Then \(f\) is linear — that is, \(f(x \oplus y) = f(x) \oplus f(y)\) for all \(x, y \in \{ 0,1\} ^n\), where \(\oplus \) denotes bitwise XOR — if and only if there exists a set \(S \subseteq [n]\) for which the \(\pm 1\) lift \(x \mapsto (-1)^{f(x)}\) coincides with the Walsh character \(\chi _S(x) = \prod _{i \in S}(-1)^{x_i}\).

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean-valued function, and write \(F(x) = (-1)^{f(x)} \in \{ \pm 1\} \) for its sign lift. Then the BLR acceptance probability of \(f\), the probability that \(F(x \oplus y) = F(x)\, F(y)\) when \(x\) and \(y\) are drawn independently and uniformly from \(\{ 0,1\} ^n\), satisfies

where \(x \oplus y\) denotes the componentwise XOR.

Let \(f : \{ 0,1\} ^n \to \mathbb {R}\) be a Boolean function on the hypercube, write \(x \oplus y\) for the componentwise XOR of \(x, y \in \{ 0,1\} ^n\), and let \(\mathbb {E}\) denote expectation over a uniformly random point of \(\{ 0,1\} ^n\). Then

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean-valued function on the hypercube, and let \(g = (-1)^{f}\) denote its \(\pm 1\) lift. Then the double uniform expectation of the triple product of \(g\) over independent inputs and their componentwise XOR equals the sum of the cubes of the Fourier coefficients of \(g\):

where \(x, y\) range uniformly over \(\{ 0,1\} ^n\), \((x \oplus y)_i = x_i \oplus y_i\), and \(\hat{g}(S) = \langle g, \chi _S \rangle \) is the Fourier coefficient at \(S \subseteq [n]\).

Let \(f,g:\{ 0,1\} ^n\to \{ 0,1\} \) be Boolean-valued functions, let \(S\subseteq [n]\), and let \(\varepsilon \in \mathbb {R}\). Write \(f^{\pm },g^{\pm }:\{ 0,1\} ^n\to \mathbb {R}\) for their \(\pm 1\) lifts, given by \(x\mapsto (-1)^{f(x)}\) and \(x\mapsto (-1)^{g(x)}\). Suppose that \(g^{\pm }\) coincides with the Walsh character \(\chi _S\), and that \(\operatorname{dist}(f,g)=\Pr _{x}[f(x)\ne g(x)]\ge \varepsilon \). Then the Fourier coefficient of \(f^{\pm }\) at \(S\) satisfies

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be \(\varepsilon \)-far from linear, meaning that \(0 \le \varepsilon \le 1\) and every linear function \(g : \{ 0,1\} ^n \to \{ 0,1\} \) (one satisfying \(g(x \oplus y) = g(x) \oplus g(y)\) for all \(x,y\)) has \(\Pr _{x}[f(x) \ne g(x)] \ge \varepsilon \) under the uniform distribution. Let \(F(x) = (-1)^{f(x)}\) be the \(\pm 1\) lift of \(f\). Then for every subset \(S \subseteq [n]\), the Fourier coefficient of \(F\) at \(S\) satisfies

where \(\chi _S(x) = \prod _{i \in S}(-1)^{x_i}\) is the Walsh character indexed by \(S\).

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean function and let \(\varepsilon \in \mathbb {R}\) with \(0 \le \varepsilon \le 1\), and suppose \(f\) is \(\varepsilon \)-far from linear: for every linear function \(g : \{ 0,1\} ^n \to \{ 0,1\} \) one has \(\operatorname{dist}(f,g) \ge \varepsilon \). Writing \(F = (-1)^{f}\) for the \(\pm 1\) lift of \(f\) and \(\hat F(S) = \langle F, \chi _S\rangle \) for its Fourier coefficient at \(S \subseteq [n]\), the sum of the cubed coefficients over all subsets satisfies

Let \(n\) be a natural number and let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be linear, meaning that \(f(x \oplus y) = f(x) \oplus f(y)\) for all \(x, y \in \{ 0,1\} ^n\). Then the BLR acceptance probability of \(f\) equals \(1\); that is, when \(x\) and \(y\) are drawn uniformly and independently from \(\{ 0,1\} ^n\), the test always accepts.

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) and let \(\varepsilon \in \mathbb {R}\) satisfy \(0 \le \varepsilon \le 1\). Suppose \(f\) is \(\varepsilon \)-far from linear, meaning that every linear function \(g : \{ 0,1\} ^n \to \{ 0,1\} \) (one satisfying \(g(x \oplus y) = g(x) \oplus g(y)\) for all \(x, y\)) has distance \(\Pr _{x}[f(x) \ne g(x)] \ge \varepsilon \) from \(f\). Then the BLR acceptance probability of \(f\) satisfies

where \(x\) and \(y\) range uniformly over \(\{ 0,1\} ^n\); equivalently, the test rejects \(f\) with probability at least \(\varepsilon \).

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a linear Boolean function, meaning \(f(x \oplus y) = f(x) \oplus f(y)\) for all \(x, y \in \{ 0,1\} ^n\), where \(\oplus \) is componentwise XOR. For a subset \(s \subseteq \{ 0, \dots , n-1\} \), let \(\mathbf{1}_s \in \{ 0,1\} ^n\) be its indicator vector, whose \(i\)-th coordinate is \(1\) when \(i \in s\) and \(0\) otherwise, and for each index \(i\) let \(e_i \in \{ 0,1\} ^n\) be the standard basis vector, whose \(i\)-th coordinate is \(1\) and all others \(0\). Then for every \(s\) the value \(f(\mathbf{1}_s)\) is \(0\) when

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

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a linear Boolean function, meaning \(f(x \oplus y) = f(x) \oplus f(y)\) for all \(x, y \in \{ 0,1\} ^n\), and for each coordinate \(i\) let \(e_i \in \{ 0,1\} ^n\) denote the standard basis vector that is \(1\) in position \(i\) and \(0\) elsewhere. Then for every \(x \in \{ 0,1\} ^n\), the value \(f(x)\) equals the parity of the number of coordinates \(i\) with \(x_i = 1\) and \(f(e_i) = 1\); that is, \(f(x) = 1\) if that count is odd and \(f(x) = 0\) if it is even.

Fix \(n\) and a subset \(S \subseteq [n]\), and let \(\chi _S(x) = \prod _{i \in S}(-1)^{x_i}\) be the associated Walsh character on the hypercube \(\{ 0,1\} ^n\). Then for all \(x, y \in \{ 0,1\} ^n\),

where \(x \oplus y\) denotes the componentwise XOR.

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean-valued function whose \(\pm 1\) lift coincides with a Walsh character, say \(x \mapsto (-1)^{f(x)}\) equals \(\chi _S\) for some \(S \subseteq [n]\), and fix points \(x, y \in \{ 0,1\} ^n\). If the character is multiplicative at this pair, meaning \(\chi _S(x \oplus y) = \chi _S(x)\, \chi _S(y)\) where \(x \oplus y\) denotes the componentwise XOR, then

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a linear Boolean function, meaning \(f(x \oplus y) = f(x) \oplus f(y)\) for all \(x, y \in \{ 0,1\} ^n\), where \(\oplus \) is componentwise XOR. For each coordinate \(i\), let \(e_i \in \{ 0,1\} ^n\) denote the standard basis vector that is \(1\) in coordinate \(i\) and \(0\) elsewhere. Then for every \(x \in \{ 0,1\} ^n\), the value \(f(x)\) is \(1\) if the number of coordinates \(i\) with \(x_i = 1\) and \(f(e_i) = 1\) is odd, and \(0\) if that number is even; equivalently, \(f(x)\) is the parity of \(\lvert \{ \, i : x_i = 1 \text{ and } f(e_i) = 1 \, \} \rvert \).

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean-valued function whose \(\pm 1\) lift \(x \mapsto (-1)^{f(x)}\) coincides with the Walsh character \(\chi _S\) for some subset \(S \subseteq [n]\). Then for all \(x, y \in \{ 0,1\} ^n\),

where \(x \oplus y\) denotes the componentwise XOR of \(x\) and \(y\) and \(f(x) \oplus f(y)\) the XOR of the two Boolean outputs.

Fix \(n \in \mathbb {N}\) and a Boolean-valued function \(f : \{ 0,1\} ^n \to \{ 0,1\} \), and let \(g : \{ 0,1\} ^n \to \mathbb {R}\) be its \(\pm 1\) lift, \(g(x) = (-1)^{f(x)}\). Then for all \(x, y \in \{ 0,1\} ^n\),

where \(x \oplus y\) denotes the componentwise XOR and the left-hand side is \(1\) when the equality holds and \(0\) otherwise.

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean-valued function, and let \(g : \{ 0,1\} ^n \to \mathbb {R}\) be its \(\pm 1\) lift, \(g(x) = (-1)^{f(x)}\). Writing \(g * g\) for the self-convolution \((g * g)(x) = \mathbb {E}_{y}\bigl[g(y)\, g(x \oplus y)\bigr]\) with respect to the uniform measure, and \(\hat g(S) = \mathbb {E}[g\, \chi _S]\) for the Fourier coefficient of \(g\) at \(S\), one has for every \(x \in \{ 0,1\} ^n\)

where \(\chi _S(x) = \prod _{i \in S} (-1)^{x_i}\) is the Walsh character of \(S\). That is, the self-convolution of \(g\) has Fourier coefficients \(\hat g(S)^2\).

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean function, and let \(g\) denote its \(\pm 1\) lift, so that \(g(x) = (-1)^{f(x)}\). Suppose that the convolution of \(g\) with itself admits the Fourier expansion

where \(\chi _S\) is the Walsh character of \(S\) and \(\hat{g}(S) = \langle g, \chi _S\rangle \). Then

the expectation being taken uniformly over \(x \in \{ 0,1\} ^n\).

Let \(f, g : \{ 0,1\} ^n \to \{ 0,1\} \) be Boolean-valued functions on the hypercube, and write \(F, G : \{ 0,1\} ^n \to \mathbb {R}\) for their \(\pm 1\) lifts, given by \(F(x) = (-1)^{f(x)}\) and \(G(x) = (-1)^{g(x)}\). Then for every point \(x \in \{ 0,1\} ^n\),

so the product equals \(+1\) where \(f\) and \(g\) agree at \(x\) and \(-1\) where they disagree.

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a Boolean-valued function, and let \(g : \{ 0,1\} ^n \to \mathbb {R}\) be its \(\pm 1\) lift, given by \(g(x) = (-1)^{f(x)}\). Then the Fourier coefficients \(\hat g(S) = \langle g, \chi _S\rangle \), taken over all subsets \(S \subseteq [n]\), satisfy

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be \(\varepsilon \)-far from linear, meaning that \(0 \le \varepsilon \le 1\) and every linear function \(g : \{ 0,1\} ^n \to \{ 0,1\} \) (one satisfying \(g(x \oplus y) = g(x) \oplus g(y)\) for all \(x,y\)) has distance \(\Pr _{x}[f(x) \ne g(x)] \ge \varepsilon \) from \(f\). Write \(\hat F(S) = \mathbb {E}[F \cdot \chi _S]\) for the Fourier coefficient of \(F = (-1)^{f}\), the \(\pm 1\) lift of \(f\), at a subset \(S \subseteq [n]\). Then for every such \(S\),

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a linear function, meaning that \(f(x \oplus y) = f(x) \oplus f(y)\) for all \(x, y \in \{ 0,1\} ^n\), where \(\oplus \) denotes componentwise XOR. Then for all \(x, y \in \{ 0,1\} ^n\) we have \(f(x \oplus y) = f(x) \oplus f(y)\).

Let \(f : \{ 0,1\} ^n \to \{ 0,1\} \) be a function that respects componentwise XOR, meaning \(f(x \oplus y) = f(x) \oplus f(y)\) for all \(x, y \in \{ 0,1\} ^n\), and let \(g : \{ 0,1\} ^n \to \mathbb {R}\) be its \(\pm 1\) lift, \(g(x) = (-1)^{f(x)}\). Then \(g\) turns XOR into multiplication: