Fix an integer \(k \ge 1\) and a dimension \(n\), and let \(f : (\mathbb {Z}/k\mathbb {Z})^n \to \mathbb {Z}/k\mathbb {Z}\) be any function. Then \(f\) is linear — that is, \(f(x+y) = f(x) + f(y)\) for all \(x, y \in (\mathbb {Z}/k\mathbb {Z})^n\) — if and only if there is a vector \(s \in (\mathbb {Z}/k\mathbb {Z})^n\) with \(f(x) = s \cdot x = \sum _{i=0}^{n-1} s_i x_i\) for every \(x\), all sums taken modulo \(k\).

Let \(f : (\mathbb {Z}/k\mathbb {Z})^n \to \mathbb {Z}/k\mathbb {Z}\) be any function on the \(n\)-dimensional space over \(\mathbb {Z}/k\mathbb {Z}\), and let its normalization be \((\mathrm{normalize}\, f)(x) = f(x) - f(0)\). Then this normalization vanishes at the origin: \((\mathrm{normalize}\, f)(0) = 0\).

Let \(k \ge 1\) and \(n\) be natural numbers, and let \(f : (\mathbb {Z}/k\mathbb {Z})^n \to \mathbb {Z}/k\mathbb {Z}\) be a linear function, meaning \(f(x+y) = f(x) + f(y)\) for all \(x, y \in (\mathbb {Z}/k\mathbb {Z})^n\). Then \(f\) is normalized: \(f(0) = 0\).

Let \(k \ge 2\) and write \(\omega _k = e^{2\pi i / k}\) for the primitive \(k\)-th root of unity. For every nonzero \(a \in \mathbb {Z}/k\mathbb {Z}\),

where \(\omega _k^{\, a}\) denotes \(\omega _k\) raised to the canonical representative of \(a\) in \(\{ 0, 1, \ldots , k-1\} \).

Let \(k \ge 2\) and let \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\), with lift \(\widetilde{f}(x) = \omega _k^{f(x)}\) where \(\omega _k = e^{2\pi i/k}\). Then for every frequency \(s \in \mathbb {Z}_k^n\), the real part of the Fourier coefficient of \(\widetilde{f}\) at \(s\) is bounded above by

where \(\chi _s(x) = s\cdot x\) is the linear character and \(\mathrm{dist}(f,\chi _s)\) is the fraction of inputs \(x\) on which \(f(x) \ne s\cdot x\).

Fix an integer \(k \ge 2\) and let \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\) be \(\varepsilon \)-far from linear in the normalized sense: that is, \(f(0) = 0\), the parameter satisfies \(0 \le \varepsilon \le 1\), and \(\operatorname{dist}(f, g) \ge \varepsilon \) for every linear \(g : \mathbb {Z}_k^n \to \mathbb {Z}_k\). Write \(\widetilde{f}(x) = \omega _k^{f(x)}\) for the lift of \(f\) to the unit circle, where \(\omega _k = e^{2\pi i/k}\), and let \(\widehat{\widetilde{f}}(s)\) denote its Fourier coefficient at frequency \(s\). Then for every \(s \in \mathbb {Z}_k^n\),

Let \(k \ge 1\) and \(n \ge 0\), and let \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\) be a linear function, meaning \(f(x+y) = f(x) + f(y)\) for all \(x, y \in \mathbb {Z}_k^n\). Then the BLR acceptance probability of \(f\) equals \(1\); that is,

where \(x\) and \(y\) range independently and uniformly over \(\mathbb {Z}_k^n\).

Let \(k \ge 1\) and write \(\omega _k = e^{2\pi i/k}\) for the primitive \(k\)-th root of unity. For each \(a \in \mathbb {Z}/k\mathbb {Z}\),

where each exponent \(ja \in \mathbb {Z}/k\mathbb {Z}\) is taken via its canonical representative in \(\{ 0, 1, \ldots , k-1\} \).

Let \(k \ge 1\) and write \(\omega _k = e^{2\pi i/k}\) for the primitive \(k\)-th root of unity. For every \(a \in \mathbb {Z}/k\mathbb {Z}\),

where the exponent \(ja\) is computed in \(\mathbb {Z}/k\mathbb {Z}\) and then lifted to its canonical representative in \(\{ 0,\ldots ,k-1\} \), and the left-hand side equals \(1\) when \(a = 0\) and \(0\) otherwise.

Let \(k \ge 1\) and \(n \ge 0\) be integers, and write \(\omega _k = e^{2\pi i/k}\). Fix \(j \in \mathbb {Z}/k\mathbb {Z}\) and an arbitrary function \(f : \mathbb {Z}_k^n \to \mathbb {Z}/k\mathbb {Z}\), and let \(\widetilde{f}_j : \mathbb {Z}_k^n \to \mathbb {C}\) be the \(j\)-twisted lift given by \(\widetilde{f}_j(x) = \omega _k^{\, j\cdot f(x)}\), with Fourier coefficients \(\widehat{\widetilde{f}_j}(s)\) indexed by the frequencies \(s \in \mathbb {Z}_k^n\). Then

Fix \(k \ge 1\) and \(n \ge 0\), and work over the group \(\mathbb {Z}_k^n = (\mathbb {Z}/k\mathbb {Z})^n\) with primitive \(k\)-th root of unity \(\omega _k = e^{2\pi i/k}\). Given \(j \in \mathbb {Z}/k\mathbb {Z}\) and a map \(f \colon \mathbb {Z}_k^n \to \mathbb {Z}/k\mathbb {Z}\), let \(F(x) = \omega _k^{\, j\cdot f(x)}\) be its \(j\)-twisted lift, and for \(s \in \mathbb {Z}_k^n\) let \(\widehat{F}(s) = \mathbb {E}_x\! \big[F(x)\, \overline{\omega _k^{\, s\cdot x}}\big]\) be its Fourier coefficient, where \(s\cdot x = \sum _{i} s_i x_i \in \mathbb {Z}/k\mathbb {Z}\) and \(\mathbb {E}\) denotes the uniform average over \(\mathbb {Z}_k^n\). Then the triple-product expectation over independent uniform \(x,y\) equals a cubic sum of the Fourier coefficients:

Let \(k \ge 1\), and let \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\). For each \(j \in \mathbb {Z}_k\) let \(\widetilde{f}_j(x) = \omega _k^{\, j\, f(x)}\) denote the \(j\)-twisted lift of \(f\), and write \(\widehat{\widetilde{f}_j}(s)\) for its Fourier coefficient at frequency \(s \in \mathbb {Z}_k^n\). Then the BLR acceptance probability of \(f\) admits the representation

where \(|\cdot |\) is the complex modulus and \(\operatorname {Re}\) the real part.

Fix an integer \(k \ge 1\), and let \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\) be arbitrary. Write \(\widetilde{f}_0(x) = \omega _k^{\, 0 \cdot f(x)}\) for the \(0\)-twisted lift of \(f\) (equivalently, the constant function \(1\)), and let \(\widehat{\widetilde{f}_0}(s)\) denote its Fourier coefficient at frequency \(s \in \mathbb {Z}_k^n\). Then

where \(|\cdot |\) is the complex modulus.

Let \(k \ge 1\) and \(n\) be integers, fix \(j \in \mathbb {Z}/k\mathbb {Z}\) and a function \(f : \mathbb {Z}_k^n \to \mathbb {Z}/k\mathbb {Z}\), and let \(\widetilde{f}_j(x) = \omega _k^{\, j\, f(x)}\) be its \(j\)-twisted lift, with Fourier coefficients \(\widehat{\widetilde{f}_j}(s)\) indexed by frequencies \(s \in \mathbb {Z}_k^n\). Then

where \(\lvert \cdot \rvert \) denotes the complex modulus and \(\operatorname {Re}\) the real part.

Let \(p\) be a prime, let \(n \ge 0\), and let \(f : \mathbb {Z}_p^n \to \mathbb {Z}_p\) be a function, whose lift to roots of unity is \(\widetilde{f}(x) = \omega _p^{f(x)}\) with \(\omega _p = e^{2\pi i/p}\). Write \(\widehat{\widetilde{f}}(s)\) for the Fourier coefficient of \(\widetilde{f}\) at frequency \(s \in \mathbb {Z}_p^n\). If \(A \in \mathbb {R}\) is such that \(\bigl\| \widehat{\widetilde{f}}(s)\bigr\| \le A\) for every \(s \in \mathbb {Z}_p^n\), then

Let \(p\) be a prime and \(n \ge 0\), and write \(\omega _p = e^{2\pi i/p}\). For a function \(f : \mathbb {Z}_p^n \to \mathbb {Z}/p\mathbb {Z}\), let \(\widetilde{f} : \mathbb {Z}_p^n \to \mathbb {C}\) be its lift \(\widetilde{f}(x) = \omega _p^{f(x)}\), and let \(\widehat{\widetilde{f}}(s)\) denote its Fourier coefficient at frequency \(s \in \mathbb {Z}_p^n\). Then

Let \(p\) be prime, and let \(f : \mathbb {Z}_p^n \to \mathbb {Z}_p\) be normalized and \(\varepsilon \)-far from linear: that is, \(f(0) = 0\), the parameter satisfies \(0 \le \varepsilon \le 1\), and \(\mathrm{dist}(f,g) \ge \varepsilon \) for every linear \(g : \mathbb {Z}_p^n \to \mathbb {Z}_p\). Write \(\widetilde{f}(x) = \omega _p^{f(x)}\) for the lift of \(f\) to the \(p\)-th roots of unity, and \(\hat{\widetilde{f}}(s)\) for its Fourier coefficient at frequency \(s \in \mathbb {Z}_p^n\). Then

Let \(p\) be a prime, let \(n \ge 0\), and write \(\omega _p = e^{2\pi i/p}\) for the primitive \(p\)-th root of unity. Let \(f : \mathbb {Z}_p^{\, n} \to \mathbb {Z}_p\) be normalized (\(f(0)=0\)) and \(\varepsilon \)-far from linear, meaning \(0 \le \varepsilon \le 1\) and \(\Pr _x[f(x)\ne g(x)] \ge \varepsilon \) for every additive homomorphism \(g : \mathbb {Z}_p^{\, n} \to \mathbb {Z}_p\). Fix \(j \in \mathbb {Z}_p\) with \(j \ne 0\), and for \(s \in \mathbb {Z}_p^{\, n}\) let \(\widehat{h}(s) = \mathbb {E}_x\bigl[h(x)\, \omega _p^{-\, s\cdot x}\bigr]\) denote the Fourier coefficient of a function \(h : \mathbb {Z}_p^{\, n} \to \mathbb {C}\) at frequency \(s\), where \(s\cdot x = \sum _{i} s_i x_i \in \mathbb {Z}_p\). Then the \(j\)-twisted lift \(\widetilde{f}_j(x) = \omega _p^{\, j\, f(x)}\) satisfies

for every \(s \in \mathbb {Z}_p^{\, n}\).

Let \(p\) be prime and let \(f : \mathbb {Z}_p^n \to \mathbb {Z}_p\) be normalized, meaning \(f(0) = 0\), and \(\varepsilon \)-far from linear: \(0 \le \varepsilon \le 1\) and \(\mathrm{dist}(f,g) \ge \varepsilon \) for every linear function \(g : \mathbb {Z}_p^n \to \mathbb {Z}_p\), where \(\mathrm{dist}\) denotes the fraction of inputs on which the two functions disagree. Fix a nonzero \(j \in \mathbb {Z}_p\) and let \(\widetilde{f}_j(x) = \omega _p^{\, j\, f(x)}\) be the associated \(j\)-twisted lift, with \(\omega _p = e^{2\pi i / p}\), and write \(\widehat{\widetilde{f}_j}(s)\) for its Fourier coefficient at frequency \(s\). Then

Let \(p\) be prime and fix \(n \ge 0\). Let \(f : \mathbb {Z}_p^n \to \mathbb {Z}_p\) be a normalized function (so \(f(0)=0\)), and let \(0 \le \varepsilon \le 1\) be such that \(f\) is \(\varepsilon \)-far from every linear map, meaning \(\mathrm{dist}(f,g) \ge \varepsilon \) for every linear \(g : \mathbb {Z}_p^n \to \mathbb {Z}_p\), where \(\mathrm{dist}(f,g) = \Pr _x[f(x) \ne g(x)]\). Then the BLR acceptance probability of \(f\) satisfies

where \(x,y\) range uniformly and independently over \(\mathbb {Z}_p^n\).

Let \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\) be a normalized function that is \(\varepsilon \)-far from linear, meaning \(f(0) = 0\), \(0 \le \varepsilon \le 1\), and \(\operatorname{dist}(f, g) \ge \varepsilon \) for every linear \(g : \mathbb {Z}_k^n \to \mathbb {Z}_k\). Then for any unit \(j \in (\mathbb {Z}_k)^\times \), the scaled function \(x \mapsto j \cdot f(x)\) is again normalized and \(\varepsilon \)-far from linear.

Let \(k \ge 2\) and let \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\) be normalized and \(\varepsilon \)-far from linear, meaning that \(f(0) = 0\), that \(0 \le \varepsilon \le 1\), and that \(\operatorname{dist}(f,g) \ge \varepsilon \) for every linear \(g : \mathbb {Z}_k^n \to \mathbb {Z}_k\) (where \(\operatorname{dist}\) is the fraction of inputs on which two functions disagree). Fix a unit \(j \in (\mathbb {Z}/k\mathbb {Z})^\times \) and a frequency \(s \in \mathbb {Z}_k^n\), and let \(\widetilde{f}_j(x) = \omega _k^{\, j\, f(x)}\) be the corresponding \(j\)-twisted lift, with \(\omega _k = e^{2\pi i/k}\). Then the Fourier coefficient of \(\widetilde{f}_j\) at \(s\) has real part bounded by

Let \(k \ge 2\), and let \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\) be normalized (that is, \(f(0) = 0\)) and \(\varepsilon \)-far from linear for some \(0 \le \varepsilon \le 1\), meaning that \(\mathrm{dist}(f,g) \ge \varepsilon \) for every linear function \(g : \mathbb {Z}_k^n \to \mathbb {Z}_k\). Then for every unit \(j \in (\mathbb {Z}/k\mathbb {Z})^\times \), the \(j\)-twisted lift \(\widetilde{f}_j(x) = \omega _k^{\, j\, f(x)}\) satisfies

where \(\widehat{\widetilde{f}_j}(s)\) denotes the Fourier coefficient of \(\widetilde{f}_j\) at frequency \(s\).

Let \(k \ge 2\), and let \(f : \mathbb {Z}_k^n \to \mathbb {Z}_k\) be normalized, so that \(f(0) = 0\). Fix a real number \(\varepsilon \) with \(0 \le \varepsilon \le 1\), and suppose \(f\) is \(\varepsilon \)-far from linear: for every linear function \(g : \mathbb {Z}_k^n \to \mathbb {Z}_k\) (one satisfying \(g(x+y) = g(x)+g(y)\) for all \(x,y\)), the fraction of inputs on which \(f\) and \(g\) disagree is at least \(\varepsilon \). Then the acceptance probability of the BLR linearity test, taken over independent uniform \(x, y \in \mathbb {Z}_k^n\), obeys

where \(\varphi \) denotes Euler’s totient function.

Let \(p\) be prime and let \(f : \mathbb {Z}_p^n \to \mathbb {Z}_p\) be normalized, meaning \(f(0) = 0\). Fix \(\varepsilon \) with \(0 \le \varepsilon \le 1\), and suppose \(f\) is \(\varepsilon \)-far from linear: every linear function \(g : \mathbb {Z}_p^n \to \mathbb {Z}_p\) (one satisfying \(g(x+y) = g(x)+g(y)\) for all \(x,y\)) has \(\operatorname{dist}(f,g) \ge \varepsilon \), where \(\operatorname{dist}(f,g) = \Pr _x[f(x) \ne g(x)]\). Then the BLR acceptance probability of \(f\) obeys

the probability being taken over \(x,y\) drawn independently and uniformly from \(\mathbb {Z}_p^n\).