# BLR Linearity Test for Boolean Functions

### Linear Functions

A function $$f\colon F_2^n \to F_2$$ is linear if $$f(x+y) = f(x) +f(y)$$ for all $$x,y\in F_2^n$$. Equivalently, $$f$$ is linear if and only if there exists $$a\in F_2^n$$ such that $$f(x) = ax$$, or there exists $$S\subseteq [n]$$ such that $$f(x) = \sum_{i\in S} x_i$$.

Note that $$x$$ can be expressed as $$x = \sum_{i=1}^n x_i e_i$$, where each $$e_i$$ is a unit vector. A linear function $$f$$ decomposes as $$f(x) = f (\sum_{i=1}^n x_i e_i) = \sum_{i=1}^n x_i f(e_i)$$.

We say a function $$f\colon F_2^n \to \pm 1$$ is linear if there is $$\alpha\in F_2^n$$ such that $$f(x) = (-1)^{\alpha x}$$. Equivalently, $$f$$ is linear if and only if $$f(x+y) = f(x)f(y)$$ for all $$x,y\in F_2^n$$.

We say two functions $$f, g\colon F_2^n \to \pm 1$$ are $$\epsilon$$-close if they disagree on at most $$\epsilon$$ fraction of inputs. It holds that $$f, g$$ are $$\epsilon$$-close if and only if $$\langle f,g \rangle \geq 1-2\epsilon$$. A function $$f$$ is $$\epsilon$$-close to linear if there is a linear function $$g$$ such that $$f$$ and $$g$$ are $$\epsilon$$-close.

### Linearity Testing

The linearity testing problem is to check whether a function is (close to) linear by asking oracle queries to the function. The BLR (Blum-Luby-Rubinfeld) test is defined as follows: Pick up $$x,y\in F_2^n$$ randomly, and accept if and only if $$f(x+y) = f(x) f(y)$$. Note that there are three queries asked here. The probability that $$f$$ passes the test is
$\Pr_{x,y\in F_2^n}[f(x+y) = f(x) f(y)].$
It turns out this probability characterizes how close $$f$$ is to linear.

Theorem. If $$\Pr_{x,y\in F_2^n}[f(x+y) = f(x) f(y)] \geq 1 – \epsilon$$ for $$\epsilon\in[0,1]$$, then $$f$$ is $$\epsilon$$-close to linear.

Lemma.
$\Pr_{x,y\in F_2^n}[f(x+y) = f(x) f(y)] = \frac{1}{2} + \frac{1}{2} \sum_{\alpha\in F_2^n} \widehat{f}(\alpha)^3$

Proof.
First, we have
$\Pr_{x,y}[f(x+y) = f(x) f(y)] = \Pr_{x,y}[ f(x)f(y)f(x+y) =1] = \frac{1}{2} + \frac{1}{2} E[f(x)f(y)f(x+y)].$

We have the following facts on the Fourier expansion
$f(x) = \sum_{\alpha\in F_2^n} \widehat{f}(\alpha) \chi_\alpha(x),$
$\chi_\alpha(x+y) = (-1)^{\alpha(x+y)} = \chi_\alpha(x)\chi_\alpha(y),$
$\chi_\alpha(x) \chi_\gamma(x) = (-1)^{\alpha x + \gamma x} = \chi_{\alpha+\gamma}(x).$

Therefore, we get
\begin{eqnarray*}
E[f(x)f(y)f(x+y)]
&=& E[ \sum_{\alpha,\beta,\gamma} \widehat{f}(\alpha) \widehat{f}(\beta) \widehat{f}(\gamma) \chi_\alpha(x)\chi_\beta(y)\chi_\gamma(x+y) ] \\
&=& \sum_{\alpha,\beta,\gamma} \widehat{f}(\alpha) \widehat{f}(\beta) \widehat{f}(\gamma) E[ \chi_\alpha(x)\chi_\beta(y)\chi_\gamma(x+y) ] \\
&=& \sum_{\alpha,\beta,\gamma} \widehat{f}(\alpha) \widehat{f}(\beta) \widehat{f}(\gamma) E[ \chi_{\alpha+\gamma}(x)\chi_{\beta+\gamma}(y) ] \\
&=& \sum_{\alpha,\beta,\gamma} \widehat{f}(\alpha) \widehat{f}(\beta) \widehat{f}(\gamma) E[ \chi_{\alpha+\gamma}(x)] E[\chi_{\beta+\gamma}(y) ] \\
\end{eqnarray*}

Since $$E_x[\chi_\alpha(x)]$$ is 0 if $$\alpha \neq 0$$ and 1 otherwise, each item in the summation above is non-zero if and only if $$\alpha = \beta=\gamma$$. Therefore,
$E[f(x)f(y)f(x+y)] = \sum_{\alpha } \widehat{f}(\alpha)^3$

An alternative way to show this is using convolution.
\begin{eqnarray*}
E[f(x)f(y)f(x+y)]
&=& E_x[f(x) E_y[ f(y)f(x+y) ] ] \\
&=& E_x[f(x) (f*f)(x) ] ] \\
&=& \langle f, f*f \rangle \\
&=& 2^n \cdot \langle \widehat{f}, \widehat{f*f} \rangle \\
&=& 2^n \cdot \langle \widehat{f}, \widehat{f}^2 \rangle \\
&=& \sum_{\alpha } \widehat{f}(\alpha)^3.
\end{eqnarray*}

$$\square$$

Then we are ready to prove the Theorem. Since $$\sum_{\alpha} \widehat{f}(\alpha)^2 = 1$$,
$\sum_{\alpha} \widehat{f}(\alpha)^3 \leq \max_{\alpha} \widehat{f}(\alpha) \cdot \sum_{\alpha} \widehat{f}(\alpha)^2 = \max_{\alpha} \widehat{\alpha}(S)$

The condition that $$\Pr_{x,y}[f(x+y) = f(x) f(y)] \geq 1- \epsilon$$ implies $$\max_{\alpha} \widehat{f}(\alpha) \geq 1-2\epsilon$$. Since $$\widehat{f}(\alpha) = \langle f, \chi_\alpha\rangle$$, we get that there exists some $$\alpha$$ such that $$\langle f, \chi_\alpha\rangle \geq 1-2\epsilon$$, and then $$f$$ is $$\epsilon$$-close to linear.

### Property Testing

A property of boolean functions is a collection of boolean functions. A property $$\mathcal{P}$$ is locally testable if there is a randomized algorithm such that

• if $$f\in \mathcal{P}$$, then accept;
• if $$f$$ is $$\epsilon$$-far from $$\mathcal{P}$$, then reject with probability $$1-\Omega(\epsilon)$$.

A property $$\mathcal{P}$$ is testable with $$q(\epsilon)$$ queries if there is a randomized algorithm such that

• if $$f\in \mathcal{P}$$, then accept with probability at least $$2/3$$;
• if $$f$$ is $$\epsilon$$-far from $$\mathcal{P}$$, then reject with probability at least $$2/3$$.

Linearity is locally testable, and testable with $$O(1/\epsilon)$$ queries.