1 BLR for general finite fields

1.1 BLR over General Finite Fields

Throughout this section, let $q=p^s$ for a prime $p$ and $s\in {\mathbb N}$ with $s\ge 1$. All vectors are in ${\mathbb F}_q^n$, and all expectations are uniform over the indicated finite sets. Let $\omega _p = e^{2\pi i/p}$.

Definition 1.1.1 Field trace

The field trace ${\rm Tr}: {\mathbb F}_q \to {\mathbb F}_p$ is

\[ {\rm Tr}(z) := \sum _{i=0}^{s-1} z^{p^i}. \]

Definition 1.1.2 Additive characters

For $\alpha \in {\mathbb F}_q^n$, define the additive character $\chi _\alpha : {\mathbb F}_q^n\to {\mathbb C}$ by

\[ \chi _\alpha (x) := \omega _p^{{\rm Tr}(\langle \alpha , x \rangle )}, \]

where $\langle \alpha , x \rangle =\sum _{i=1}^n \alpha _i x_i\in {\mathbb F}_q$.

Definition 1.1.3 Inner product and Fourier coefficient

For functions $h_1,h_2:{\mathbb F}_q^n\to {\mathbb C}$, define

\[ \langle h_1, h_2 \rangle := {\mathbb E}_{x\in {\mathbb F}_q^n}\left[h_1(x)\overline{h_2(x)}\right]. \]

For $h:{\mathbb F}_q^n\to {\mathbb C}$ and $\alpha \in {\mathbb F}_q^n$, define

\[ \widehat h(\alpha ) := \langle h, \chi _\alpha \rangle = {\mathbb E}_{x\in {\mathbb F}_q^n}\left[h(x)\overline{\chi _\alpha (x)}\right]. \]

Lemma 1.1.4 Character orthogonality

For every $\alpha ,\beta \in {\mathbb F}_q^n$,

\[ {\mathbb E}_{x\in {\mathbb F}_q^n}\left[\chi _\alpha (x)\overline{\chi _\beta (x)}\right] = \begin{cases} 1 & \text{if } \alpha =\beta ,\\ 0 & \text{if } \alpha \ne \beta . \end{cases} \]

Equivalently, ${\mathbb E}_x[\chi _\alpha (x)]=0$ for $\alpha \ne 0$ and equals $1$ for $\alpha =0$.

Proof ▶

First observe that for every $\alpha ,\beta \in {\mathbb F}_q^n$ and every $x\in {\mathbb F}_q^n$,

\[ \chi _\alpha (x)\overline{\chi _\beta (x)} = \omega _p^{{\rm Tr}(\langle \alpha , x \rangle )} \omega _p^{-{\rm Tr}(\langle \beta , x \rangle )} = \omega _p^{{\rm Tr}(\langle \alpha -\beta , x \rangle )} = \chi _{\alpha -\beta }(x), \]

where we used the ${\mathbb F}_p$-linearity of the trace map.

If $\alpha =\beta $, then $\alpha -\beta =0$, so $\chi _{\alpha -\beta }(x)=1$ for every $x\in {\mathbb F}_q^n$. Hence

\[ {\mathbb E}_{x\in {\mathbb F}_q^n}\left[\chi _\alpha (x)\overline{\chi _\beta (x)}\right] = {\mathbb E}_{x\in {\mathbb F}_q^n}[1] = 1. \]

Now suppose $\alpha \ne \beta $. Let $\gamma :=\alpha -\beta $. Then $\gamma \ne 0$, so there exists an index $j$ such that $\gamma _j\ne 0$. Fix all coordinates of $x$ except $x_j$. For the fixed remaining coordinates, the map

\[ x_j\mapsto \langle \gamma , x \rangle \]

has the form

\[ x_j\mapsto \gamma _j x_j + c \]

for some constant $c\in {\mathbb F}_q$. Since $\gamma _j\ne 0$, multiplication by $\gamma _j$ is a bijection on ${\mathbb F}_q$, and therefore the affine map $x_j\mapsto \gamma _jx_j+c$ is also a bijection on ${\mathbb F}_q$. Thus, as $x_j$ ranges uniformly over ${\mathbb F}_q$, the value $\langle \gamma , x \rangle $ also ranges uniformly over ${\mathbb F}_q$. Averaging first over $x_j$ and then over the remaining coordinates gives

\[ {\mathbb E}_{x\in {\mathbb F}_q^n}\left[\chi _\gamma (x)\right] = {\mathbb E}_{t\in {\mathbb F}_q}\left[\omega _p^{{\rm Tr}(t)}\right]. \]

It remains to show that this last average is zero. The trace map ${\rm Tr}:{\mathbb F}_q\to {\mathbb F}_p$ is a nonzero ${\mathbb F}_p$-linear map, so every fiber of ${\rm Tr}$ has the same cardinality. Since $\left\lvert {{\mathbb F}_q}\right\rvert =q$ and $\left\lvert {{\mathbb F}_p}\right\rvert =p$, each fiber has cardinality $q/p$. Therefore

\begin{align*} {\mathbb E}_{t\in {\mathbb F}_q}\left[\omega _p^{{\rm Tr}(t)}\right] & = \frac{1}{q}\sum _{t\in {\mathbb F}_q}\omega _p^{{\rm Tr}(t)} \\ & = \frac{1}{q}\sum _{r\in {\mathbb F}_p} \sum _{\substack {t\in {\mathbb F}_q\\ \begin{bgroup} {\rm Tr}(t)=r \end{bgroup}}} \omega _p^r \\ & = \frac{1}{q}\sum _{r\in {\mathbb F}_p}\frac{q}{p}\omega _p^r \\ & = \frac{1}{p}\sum _{r\in {\mathbb F}_p}\omega _p^r \\ & =0, \end{align*}

because the sum of all $p$-th roots of unity is zero. Hence, if $\alpha \ne \beta $, then

\[ {\mathbb E}_{x\in {\mathbb F}_q^n}\left[\chi _\alpha (x)\overline{\chi _\beta (x)}\right] = 0. \]

Combining the two cases proves the stated orthogonality relation. The equivalent formulation follows by taking $\beta =0$.

Lemma 1.1.5 Fourier inversion and Parseval

For every function $h:{\mathbb F}_q^n\to {\mathbb C}$,

\[ h(x)=\sum _{\alpha \in {\mathbb F}_q^n}\widehat h(\alpha )\chi _\alpha (x) \quad \text{for every }x\in {\mathbb F}_q^n, \]

and

\[ \sum _{\alpha \in {\mathbb F}_q^n}\left\lvert {\widehat h(\alpha )}\right\rvert ^2 = {\mathbb E}_{x\in {\mathbb F}_q^n}\left[\left\lvert {h(x)}\right\rvert ^2\right]. \]

In particular, if $\left\lvert {h(x)}\right\rvert =1$ for every $x$, then $\sum _{\alpha \in {\mathbb F}_q^n}\left\lvert {\widehat h(\alpha )}\right\rvert ^2=1$.

Proof ▶

By Lemma 1.1.4, the additive characters

\[ \{ \chi _\alpha : \alpha \in \mathbb F_q^n\} \]

are orthonormal with respect to the inner product

\[ \langle h_1,h_2\rangle = \mathbb E_{x\in \mathbb F_q^n} \left[h_1(x)\overline{h_2(x)}\right]. \]

Moreover, these characters span the vector space of all complex-valued functions on $\mathbb F_q^n$. Indeed, there are exactly $q^n$ characters, and the space of functions $\mathbb F_q^n\to \mathbb C$ has dimension $q^n$. Since the characters are nonzero and pairwise orthogonal, they are linearly independent. Hence they form an orthonormal basis.

Therefore every function $h:\mathbb F_q^n\to \mathbb C$ has a unique expansion in this basis:

\[ h = \sum _{\alpha \in \mathbb F_q^n} c_\alpha \chi _\alpha \]

for some coefficients $c_\alpha \in \mathbb C$. Taking the inner product of both sides with $\chi _\beta $, we obtain

\[ \langle h,\chi _\beta \rangle = \sum _{\alpha \in \mathbb F_q^n} c_\alpha \langle \chi _\alpha ,\chi _\beta \rangle . \]

By orthonormality, all terms in the sum vanish except the term $\alpha =\beta $, and $\langle \chi _\beta ,\chi _\beta \rangle =1$. Hence

\[ \langle h,\chi _\beta \rangle = c_\beta . \]

By definition of the Fourier coefficient,

\[ \widehat h(\beta )=\langle h,\chi _\beta \rangle . \]

Thus $c_\beta =\widehat h(\beta )$ for every $\beta \in \mathbb F_q^n$. Therefore

\[ h = \sum _{\alpha \in \mathbb F_q^n} \widehat h(\alpha )\chi _\alpha . \]

Evaluating this identity at $x\in \mathbb F_q^n$ gives the Fourier inversion formula

\[ h(x) = \sum _{\alpha \in \mathbb F_q^n} \widehat h(\alpha )\chi _\alpha (x). \]

It remains to prove Parseval’s identity. Using the Fourier expansion and orthonormality, we compute

\[ \begin{aligned} \mathbb E_x |h(x)|^2 & = \langle h,h\rangle \\ & = \left\langle \sum _{\alpha \in \mathbb F_q^n} \widehat h(\alpha )\chi _\alpha , \sum _{\beta \in \mathbb F_q^n} \widehat h(\beta )\chi _\beta \right\rangle \\ & = \sum _{\alpha ,\beta \in \mathbb F_q^n} \widehat h(\alpha ) \overline{\widehat h(\beta )} \langle \chi _\alpha ,\chi _\beta \rangle . \end{aligned} \]

Again, by orthonormality, $\langle \chi _\alpha ,\chi _\beta \rangle =0$ when $\alpha \neq \beta $, and $\langle \chi _\alpha ,\chi _\alpha \rangle =1$. Hence the double sum reduces to

\[ \mathbb E_x |h(x)|^2 = \sum _{\alpha \in \mathbb F_q^n} \widehat h(\alpha )\overline{\widehat h(\alpha )} = \sum _{\alpha \in \mathbb F_q^n} |\widehat h(\alpha )|^2 . \]

This proves Parseval’s identity.

Finally, if $|h(x)|=1$ for every $x\in \mathbb F_q^n$, then

\[ \mathbb E_x |h(x)|^2 = \mathbb E_x 1 = 1. \]

Therefore Parseval gives

\[ \sum _{\alpha \in \mathbb F_q^n} |\widehat h(\alpha )|^2 = 1. \]

Definition 1.1.6 Fourier expansion of a finite-field-valued function

Let $f:{\mathbb F}_q^n\to {\mathbb F}_q$. For each $c\in {\mathbb F}_q^\times $, define

\[ {\varphi }_{c}(x) := \omega _p^{{\rm Tr}(c f(x))}. \]

The Fourier expansion of $f$ is the family

\[ \left\{ {\varphi }_{c}\right\} _{c\in {\mathbb F}_q^\times }. \]

Lemma 1.1.7 Character-sum indicator

For every $z\in {\mathbb F}_q$,

\[ \mathbbm {1}[z=0] = \frac{1}{q}\sum _{c\in {\mathbb F}_q}\omega _p^{{\rm Tr}(cz)}. \]

Consequently, for every $u,v\in {\mathbb F}_q$,

\[ \mathbbm {1}[u=v] = \frac{1}{q}\sum _{c\in {\mathbb F}_q}\omega _p^{{\rm Tr}(c(u-v))}. \]

Proof ▶

Let

\[ \psi (z) := \omega _p^{{\rm Tr}(z)} \]

be the standard additive character of ${\mathbb F}_q$. We prove that, for every $t\in {\mathbb F}_q$,

\[ \mathbbm {1}[t=0] = \frac{1}{q}\sum _{c\in {\mathbb F}_q}\psi (ct). \]

The desired statement follows by taking $t=u-v$.

If $t=0$, then $ct=0$ for every $c\in {\mathbb F}_q$, so

\[ \frac{1}{q}\sum _{c\in {\mathbb F}_q}\psi (ct) = \frac{1}{q}\sum _{c\in {\mathbb F}_q}1 = 1. \]

Now suppose $t\neq 0$. Then multiplication by $t$ is a bijection ${\mathbb F}_q\to {\mathbb F}_q$, so

\[ \sum _{c\in {\mathbb F}_q}\psi (ct) = \sum _{z\in {\mathbb F}_q}\psi (z). \]

We claim that the latter sum is $0$. Let

\[ S:=\sum _{z\in {\mathbb F}_q}\psi (z). \]

Since ${\rm Tr}:{\mathbb F}_q\to {\mathbb F}_p$ is a nonzero ${\mathbb F}_p$-linear map, it is surjective. Hence there exists $a\in {\mathbb F}_q$ such that ${\rm Tr}(a)=1$. Using the bijection $z\mapsto z+a$, we get

\[ S = \sum _{z\in {\mathbb F}_q}\psi (z+a) = \sum _{z\in {\mathbb F}_q}\omega _p^{{\rm Tr}(z+a)} = \sum _{z\in {\mathbb F}_q}\omega _p^{{\rm Tr}(z)}\omega _p^{{\rm Tr}(a)} = \omega _p S. \]

Since $\omega _p\neq 1$, this implies $S=0$. Therefore, when $t\neq 0$,

\[ \frac{1}{q}\sum _{c\in {\mathbb F}_q}\psi (ct)=0. \]

Combining the two cases gives

\[ \mathbbm {1}[t=0] = \frac{1}{q}\sum _{c\in {\mathbb F}_q}\omega _p^{{\rm Tr}(ct)}. \]

Substituting $t=u-v$, we obtain

\[ \mathbbm {1}[u=v] = \frac{1}{q}\sum _{c\in {\mathbb F}_q}\omega _p^{{\rm Tr}(c(u-v))}. \]

Definition 1.1.8 Relative Hamming distance

For $f,g:{\mathbb F}_q^n\to {\mathbb F}_q$, define

\[ \delta (f,g) := \Pr _{x\in {\mathbb F}_q^n}\left[f(x)\ne g(x)\right]. \]

Definition 1.1.9 Linear functions

For $\alpha \in {\mathbb F}_q^n$, define $\ell _\alpha :{\mathbb F}_q^n\to {\mathbb F}_q$ by

\[ \ell _\alpha (x):=\langle \alpha , x \rangle . \]

The set of linear functions is

\[ {\text{$\mathcal{LIN}$}}:= \left\{ \ell _\alpha \mid \alpha \in {\mathbb F}_q^n\right\} . \]

The distance from $f:{\mathbb F}_q^n\to {\mathbb F}_q$ to linearity is

\[ \delta (f,{\text{$\mathcal{LIN}$}}):=\min _{\alpha \in {\mathbb F}_q^n}\delta (f,\ell _\alpha ). \]

Lemma 1.1.10 Distance formula

Let $f,g:{\mathbb F}_q^n\to {\mathbb F}_q$. Let $\{ {\varphi }_{c}\} _{c\in {\mathbb F}_q^\times }$ and $\{ {\gamma }_{c}\} _{c\in {\mathbb F}_q^\times }$ be their Fourier expansions. Then

\[ \delta (f,g) = 1-\frac{1}{q}\left(1+ \sum _{c\in {\mathbb F}_q^\times } \langle {\varphi }_{c}, {\gamma }_{c} \rangle \right). \]

Equivalently,

\[ \delta (f,g) = 1-\frac{1}{q}\left(1+ \sum _{c\in {\mathbb F}_q^\times } \sum _{\alpha \in {\mathbb F}_q^n} \widehat{{\varphi }_{c}}(\alpha ) \overline{\widehat{{\gamma }_{c}}(\alpha )} \right). \]

Proof ▶

By lemma 1.1.7,

\[ \Pr _x[f(x)=g(x)] = {\mathbb E}_x\left[\frac{1}{q}\sum _{c\in {\mathbb F}_q} \omega _p^{{\rm Tr}(c(f(x)-g(x)))}\right]. \]

The term $c=0$ contributes $1/q$. For $c\ne 0$,

\[ \omega _p^{{\rm Tr}(c(f(x)-g(x)))} = {\varphi }_{c}(x)\overline{{\gamma }_{c}(x)}. \]

Therefore

\[ \Pr _x[f(x)=g(x)] =\frac{1}{q}\left(1+\sum _{c\in {\mathbb F}_q^\times } \langle {\varphi }_{c}, {\gamma }_{c} \rangle \right), \]

which gives the first formula after using $\delta (f,g)=1-\Pr _x[f(x)=g(x)]$. The second formula follows from Fourier inversion and Parseval.

Lemma 1.1.11 Fourier expansion of a linear function

Fix $\alpha \in {\mathbb F}_q^n$ and $c\in {\mathbb F}_q^\times $. Let $\lambda _{c}(x):=\omega _p^{{\rm Tr}(c\ell _\alpha (x))}$. Then

\[ \lambda _{c}=\chi _{c\alpha }. \]

Equivalently, for every $\beta \in {\mathbb F}_q^n$,

\[ \widehat{\lambda _{c}}(\beta ) = \begin{cases} 1 & \text{if } \beta =c\alpha ,\\ 0 & \text{if } \beta \ne c\alpha . \end{cases} \]

Proof ▶

For every $x\in {\mathbb F}_q^n$,

\[ \lambda _{c}(x) = \omega _p^{{\rm Tr}(c\langle \alpha , x \rangle )} = \omega _p^{{\rm Tr}(\langle c\alpha , x \rangle )} = \chi _{c\alpha }(x). \]

The statement about Fourier coefficients follows from lemma 1.1.4.

Lemma 1.1.12 Distance to linearity in Fourier form

Let $f:{\mathbb F}_q^n\to {\mathbb F}_q$ have Fourier expansion $\{ {\varphi }_{c}\} _{c\in {\mathbb F}_q^\times }$. Then

\[ \delta (f,{\text{$\mathcal{LIN}$}}) = 1-\frac{1}{q}\left(1+ \max _{\alpha \in {\mathbb F}_q^n} \sum _{c\in {\mathbb F}_q^\times } \widehat{{\varphi }_{c}}(c\alpha ) \right). \]

Moreover, for every $\alpha \in {\mathbb F}_q^n$, the quantity

\[ S_\alpha := \sum _{c\in {\mathbb F}_q^\times } \widehat{{\varphi }_{c}}(c\alpha ) \]

is real and satisfies $-1\le S_\alpha \le q-1$.

Proof ▶

Apply lemma 1.1.10 with $g=\ell _\alpha $ and use lemma 1.1.11. This gives

\[ \delta (f,\ell _\alpha ) =1-\frac{1}{q}\left(1+ \sum _{c\in {\mathbb F}_q^\times } \widehat{{\varphi }_{c}}(c\alpha ) \right). \]

Taking the minimum over $\alpha $ gives the claimed formula for $\delta (f,{}$

LIN). For fixed $\alpha $, the same formula expresses $S_\alpha $ as $q(1-\delta (f,\ell _\alpha ))-1$. Hence $S_\alpha $ is real, and since $0\le \delta (f,\ell _\alpha )\le 1$, we get $-1\le S_\alpha \le q-1$.

Proof ▶

Definition 1.1.13 Finite-field BLR test

Given oracle access to $f:{\mathbb F}_q^n\to {\mathbb F}_q$, the finite-field BLR verifier ${}$

V_BLR^f samples $a,b\in {\mathbb F}_q^\times $ and $x,y\in {\mathbb F}_q^n$ uniformly and accepts iff

\[ a f(x)+b f(y)=f(ax+by). \]

That is,

\[ {\text{$\mathsf{V}_{\mathsf{BLR}}^f$ }}=1 \quad \Longleftrightarrow \quad a f(x)+b f(y)=f(ax+by). \]

Definition

Lemma 1.1.14 Completeness

If $f\in {}$

LIN, then

\[ \Pr [{\text{$\mathsf{V}_{\mathsf{BLR}}^f$ }}=1]=1. \]

Lemma

Proof ▶

If $f=\ell _\alpha $ for some $\alpha \in {\mathbb F}_q^n$, then for every $a,b\in {\mathbb F}_q^\times $ and $x,y\in {\mathbb F}_q^n$,

\[ f(ax+by) =\langle \alpha , ax+by \rangle =a\langle \alpha , x \rangle +b\langle \alpha , y \rangle =a f(x)+b f(y). \]

Thus the verifier accepts for every choice of randomness.

Lemma 1.1.15 Exact BLR acceptance formula

Let $f:{\mathbb F}_q^n\to {\mathbb F}_q$ have Fourier expansion $\{ {\varphi }_{c}\} _{c\in {\mathbb F}_q^\times }$. For each $\alpha \in {\mathbb F}_q^n$, define

\[ S_\alpha := \sum _{c\in {\mathbb F}_q^\times } \widehat{{\varphi }_{c}}(c\alpha ). \]

Then

\[ \Pr [{\text{$\mathsf{V}_{\mathsf{BLR}}^f$ }}=1] = \frac{1}{q}\left(1+\frac{1}{(q-1)^2} \sum _{\alpha \in {\mathbb F}_q^n} S_\alpha ^3 \right). \]

Proof ▶

By lemma 1.1.7, for fixed $a,b,x,y$,

\[ \mathbbm {1}[a f(x)+b f(y)=f(ax+by)] =\frac{1}{q}\sum _{c\in {\mathbb F}_q} \omega _p^{{\rm Tr}(c(a f(x)+b f(y)-f(ax+by)))}. \]

Taking expectation gives

\[ \Pr [{\text{$\mathsf{V}_{\mathsf{BLR}}^f$ }}=1] =\frac{1}{q}+\frac{1}{q}{\mathbb E}_{a,b,x,y} \left[\sum _{c\in {\mathbb F}_q^\times } {\varphi }_{ca}(x){\varphi }_{cb}(y) {\varphi }_{-c}(ax+by) \right]. \]

Expand the three complex-valued functions into their Fourier expansions:

\begin{align*} & {\mathbb E}_{a,b,x,y} \left[\sum _{c\in {\mathbb F}_q^\times } {\varphi }_{ca}(x){\varphi }_{cb}(y) {\varphi }_{-c}(ax+by) \right] \\ & ={\mathbb E}_{a,b}\left[\sum _{c\in {\mathbb F}_q^\times } \sum _{\alpha ,\beta ,\gamma \in {\mathbb F}_q^n} \widehat{{\varphi }_{ca}}(\alpha ) \widehat{{\varphi }_{cb}}(\beta ) \widehat{{\varphi }_{-c}}(\gamma ) {\mathbb E}_{x,y}\left[ \chi _\alpha (x)\chi _\beta (y)\chi _\gamma (ax+by) \right] \right]. \end{align*}

Since

\[ \chi _\gamma (ax+by)=\chi _{a\gamma }(x)\chi _{b\gamma }(y), \]

lemma 1.1.4 implies that the inner expectation is $1$ exactly when

\[ \alpha +a\gamma =0 \quad \text{and}\quad \beta +b\gamma =0, \]

and is $0$ otherwise. Therefore the last display equals

\[ {\mathbb E}_{a,b}\left[\sum _{c\in {\mathbb F}_q^\times } \sum _{\alpha \in {\mathbb F}_q^n} \widehat{{\varphi }_{ca}}(\alpha ) \widehat{{\varphi }_{cb}}(a^{-1}b\alpha ) \widehat{{\varphi }_{-c}}(-a^{-1}\alpha ) \right]. \]

Substitute $\alpha =ca\eta $. Then this becomes

\[ {\mathbb E}_{a,b}\left[\sum _{c\in {\mathbb F}_q^\times } \sum _{\eta \in {\mathbb F}_q^n} \widehat{{\varphi }_{ca}}(ca\eta ) \widehat{{\varphi }_{cb}}(cb\eta ) \widehat{{\varphi }_{-c}}(-c\eta ) \right]. \]

As $a,b,c$ range over ${\mathbb F}_q^\times $, so do $ca$, $cb$, and $-c$. Hence this equals

\[ \frac{1}{(q-1)^2} \sum _{\eta \in {\mathbb F}_q^n} \left(\sum _{d\in {\mathbb F}_q^\times } \widehat{{\varphi }_{d}}(d\eta ) \right)^3 =\frac{1}{(q-1)^2}\sum _{\eta \in {\mathbb F}_q^n}S_\eta ^3. \]

Substituting into the expression for $\Pr [{}$

V_BLR^f=1] proves the claim.

Proof ▶

Lemma 1.1.16 Second moment bound

With $S_\alpha $ as in lemma 1.1.15,

\[ \sum _{\alpha \in {\mathbb F}_q^n} S_\alpha ^2 \le (q-1)^2. \]

Proof ▶

Expanding the square gives

\[ \sum _{\alpha \in {\mathbb F}_q^n} S_\alpha ^2 =\sum _{a,b\in {\mathbb F}_q^\times } \sum _{\alpha \in {\mathbb F}_q^n} \widehat{{\varphi }_{a}}(a\alpha ) \widehat{{\varphi }_{b}}(b\alpha ). \]

For fixed $a,b\in {\mathbb F}_q^\times $, Cauchy–Schwarz and lemma 1.1.5 give

\begin{align*} \left\lvert {\sum _{\alpha \in {\mathbb F}_q^n} \widehat{{\varphi }_{a}}(a\alpha ) \widehat{{\varphi }_{b}}(b\alpha )}\right\rvert & \le \left(\sum _{\alpha \in {\mathbb F}_q^n}\left\lvert {\widehat{{\varphi }_{a}}(a\alpha )}\right\rvert ^2\right)^{1/2} \left(\sum _{\alpha \in {\mathbb F}_q^n}\left\lvert {\widehat{{\varphi }_{b}}(b\alpha )}\right\rvert ^2\right)^{1/2} \\ & =1. \end{align*}

The equality uses that multiplication by $a$ and by $b$ permutes ${\mathbb F}_q^n$, and that $\left\lvert {{\varphi }_{a}(x)}\right\rvert =\left\lvert {{\varphi }_{b}(x)}\right\rvert =1$ for every $x$. Summing over the $(q-1)^2$ choices of $(a,b)$ gives the result.

Theorem 1.1.17 Soundness of the finite-field BLR test

For every function $f:{\mathbb F}_q^n\to {\mathbb F}_q$,

\[ \Pr [{\text{$\mathsf{V}_{\mathsf{BLR}}^f$ }}=0] \ge \delta (f,{\text{$\mathcal{LIN}$}}). \]

Equivalently,

\[ \Pr [{\text{$\mathsf{V}_{\mathsf{BLR}}^f$ }}=1] \le 1-\delta (f,{\text{$\mathcal{LIN}$}}). \]

Proof ▶

Let $S_\alpha $ be as in lemma 1.1.15, and let

\[ M:=\max _{\alpha \in {\mathbb F}_q^n}S_\alpha . \]

By lemma 1.1.12,

\[ 1-\delta (f,{\text{$\mathcal{LIN}$}})=\frac{1}{q}(1+M). \]

By lemma 1.1.12, each $S_\alpha $ is real and $S_\alpha \le M$. Therefore $S_\alpha ^3\le M S_\alpha ^2$ for every $\alpha $, because $S_\alpha ^2\ge 0$. Using lemma 1.1.15 and lemma 1.1.16,

\begin{align*} \Pr [{\text{$\mathsf{V}_{\mathsf{BLR}}^f$ }}=1] & =\frac{1}{q}\left(1+\frac{1}{(q-1)^2} \sum _{\alpha \in {\mathbb F}_q^n}S_\alpha ^3\right) \\ & \le \frac{1}{q}\left(1+\frac{M}{(q-1)^2} \sum _{\alpha \in {\mathbb F}_q^n}S_\alpha ^2\right) \\ & \le \frac{1}{q}(1+M) \\ & =1-\delta (f,{\text{$\mathcal{LIN}$}}). \end{align*}

Taking complements gives $\Pr [{}$

V_BLR^f=0]≥δ(f,LIN).

Proof ▶