# 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.