77 Boolean Analysis — Zk BLR
77.1 Overview
This module formalizes the Blum–Luby–Rubinfeld (BLR) linearity test over \(\mathbb {Z}_k^n\). A function \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\) is linear if \(f(x+y)=f(x)+f(y)\) for all \(x,y\), or equivalently if it is a dot-product character \(x \mapsto s \cdot x\) for some coefficient vector \(s\). The module proves completeness (linear functions are always accepted) and soundness bounds: if \(f\) is \(\varepsilon \)-far from every linear function, the acceptance probability is at most \(1 - \tfrac {\varphi (k)}{k}(1-\cos (2\pi /k))\varepsilon \), specialising for prime \(p\) to \(1 - \tfrac {p-1}{p}(1-\cos (2\pi /p))\varepsilon \).
77.2 Declarations
A function \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\) is linear if \(f(x+y) = f(x)+f(y)\) for all \(x, y \in \mathbb {Z}_k^n\).
Given \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\), the lifted function \(\widetilde{f} : \mathbb {Z}_k^n \to \mathbb {C}\) is defined by \(\widetilde{f}(x) = \omega _k^{f(x)}\), where \(\omega _k = e^{2\pi i/k}\).
The distance between \(f, g : \mathbb {Z}_k^n \to \mathbb {Z}_k\) is the fraction of inputs on which they disagree:
A function \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\) is \(\varepsilon \)-far from linear if \(0 \le \varepsilon \le 1\) and \(\mathrm{dist}(f,g) \ge \varepsilon \) for every linear function \(g : \mathbb {Z}_k^n \to \mathbb {Z}_k\).
A function \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\) is linear if and only if there exists \(s \in \mathbb {Z}_k^n\) such that \(f(x) = s \cdot x\) for all \(x\), where \(s \cdot x = \sum _i s_i x_i\) denotes the dot product in \(\mathbb {Z}_k\).
For \(s \in \mathbb {Z}_k^n\), the linear character \(\chi _s : \mathbb {Z}_k^n \to \mathbb {Z}_k\) is the dot-product function \(\chi _s(x) = s \cdot x\).
A function \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\) is normalized if \(f(0) = 0\). Every linear function is automatically normalized.
The normalization of \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\) is the function \((\mathrm{normalize}\, f)(x) = f(x) - f(0)\), which satisfies \((\mathrm{normalize}\, f)(0) = 0\).
For any \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\), \((\mathrm{normalize}\, f)(0) = 0\).
If \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\) is linear, then \(f(0) = 0\), i.e. \(f\) is normalized.
A function \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\) satisfies ZkBLR.epsilon_far_from_linear_normalized with parameter \(\varepsilon \) if \(f\) is normalized (\(f(0)=0\)), \(0\le \varepsilon \le 1\), and \(\mathrm{dist}(f,g)\ge \varepsilon \) for every linear \(g\).
For \(k \ge 2\) and any nonzero \(a \in \mathbb {Z}_k\), \(\operatorname {Re}(\omega _k^a) \le \cos (2\pi /k)\).
For \(k \ge 2\) and \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\), the real part of the \(s\)-th Fourier coefficient of the lifted function \(\widetilde{f}\) satisfies
If \(k \ge 2\) and \(f\) is \(\varepsilon \)-far from linear (in the normalized sense), then for every \(s \in \mathbb {Z}_k^n\),
For \(j \in \mathbb {Z}_k\), the \(j\)-twisted lift of \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\) is \(\widetilde{f}_j(x) = \omega _k^{j \cdot f(x)}\). The case \(j=1\) recovers ZkBLR.lift_omega; the case \(j=0\) gives the constant function \(1\).
The BLR acceptance probability of \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\) is
If \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\) is linear, then \(\Pr [{\rm BLR\ accepts}\ f] = 1\).
For any \(a \in \mathbb {Z}_k\),
For any \(a \in \mathbb {Z}_k\),
For any \(j \in \mathbb {Z}_k\) and \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\),
For \(j \in \mathbb {Z}_k\) and \(F = \widetilde{f}_j\), the triple-product expectation satisfies
The BLR acceptance probability admits the Fourier representation
For any \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\), the \(j=0\) term of the Fourier sum evaluates to \(1\):
For any \(j \in \mathbb {Z}_k\) and \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\),
If \(\| \widehat{\widetilde{f}}(s)\| \le A\) for all \(s \in \mathbb {Z}_p^n\), then
For \(f : \mathbb {Z}_p^n \to \mathbb {Z}_p\),
If \(f : \mathbb {Z}_p^n \to \mathbb {Z}_p\) is \(\varepsilon \)-far from linear (normalized), then
If \(f : \mathbb {Z}_p^n \to \mathbb {Z}_p\) is \(\varepsilon \)-far from linear (normalized), \(j \ne 0\), and \(s \in \mathbb {Z}_p^n\), then
If \(f : \mathbb {Z}_p^n \to \mathbb {Z}_p\) is \(\varepsilon \)-far from linear (normalized) and \(j \ne 0\), then
If \(f : \mathbb {Z}_p^n \to \mathbb {Z}_p\) is \(\varepsilon \)-far from linear (normalized), then
If \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\) is \(\varepsilon \)-far from linear (normalized) and \(j \in \mathbb {Z}_k^\times \) is a unit, then the scaled function \(x \mapsto j \cdot f(x)\) is also \(\varepsilon \)-far from linear (normalized).
If \(k \ge 2\), \(f\) is \(\varepsilon \)-far from linear (normalized), \(j \in \mathbb {Z}_k^\times \), and \(s \in \mathbb {Z}_k^n\), then
If \(k \ge 2\), \(f\) is \(\varepsilon \)-far from linear (normalized), and \(j \in \mathbb {Z}_k^\times \), then
For \(k \ge 2\), if \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\) is \(\varepsilon \)-far from linear (normalized), then
where \(\varphi (k)\) denotes Euler’s totient function.
If \(p\) is prime and \(f : \mathbb {Z}_p^n \to \mathbb {Z}_p\) is \(\varepsilon \)-far from linear (normalized), then
recovering the prime-field soundness bound as a corollary of the general result (using \(\varphi (p)=p-1\)).