# Some Elementary Constructions of Small-Bias Spaces, Part 2

In this short post, we examine the use of the “randomness” of quadratic characters in constructing small-bias spaces. Specifically, we’ll look at another one of AGHP’s constructions making use of Weil’s character sum estimate as well as a generalization of this argument to $\epsilon$-biased sets over $\mathbb{Z}^n_d$, due to Azar/Motwani/Naor.

Preliminaries and AGHP’s Construction

Characters of finite abelian groups $G$ are homomorphisms $\chi: G\to U(1)$. It is easy to see that the only characters $\chi_r$ of $\mathbb{Z}_d$ are given by $\chi_r(z^s) = e^{2\pi irs/d}$, where $z$ is a generator of $\mathbb{Z}_d$. We have the following useful theorem due to Weil:

Theorem 0:  (Weil) For $q$ an odd prime power, $f\in\mathbb{F}_q[t]$ with $n$ distinct zeroes in the algebraic closure of $\mathbb{F}_q$, and $\chi$ a character with order $d$ not dividing the greatest common multiplicity of $f$‘s roots, $\left|\sum_{x\in\mathbb{Z}_p}\chi_p(f(x))\right|\le(n-1)\sqrt{p}$.

For AGHP’s construction, we restrict our attention to the only nontrivial character in the case of $q = 2$ taking values only in $\pm 1$, namely the quadratic character. Concretely, we have the following definition:

Definition 1: The quadratic character $\chi_p:\mathbb{Z}^*_p\to U(1)$ sends $x$ to 1 if it is a quadratic residue and -1 otherwise. Assign $\chi_p(0)$ to be 0.

AGHP’s construction is remarkably simple: define bitstring-valued map $r: [p]\to\{0,1\}^n$ by $(r(i))_j = \frac{1 - \chi_p(i+j)}{2}$ if $i+j\neq p$, otherwise let $(r(i))_j = 1$. The motivation for this is that $(-1)^{(r(i))_j} = \chi_p(i+j)$ (for $i+j\neq p$).

Theorem 1$\text{Im}(r)$ is $\frac{(n-1)\sqrt{p} + n}{p}$-biased.

Proof: The bias by definition $\frac{1}{p}\left|\sum_{x\in\mathbb{Z}_p}(-1)^{\sum^{n-1}_{i=0}\alpha_j(r(i))_j}\right|$. For the $i$ for which there is no $j$ such that $i+j = p$ and $\alpha_i = 1$, $(-1)^{\sum^{n-1}_{i=0}\alpha_j(r(i))_j} = \chi_p\left(\prod^{n-1}_{i=0}(i+j)^{\alpha_j}\right)$. For $i$ for which there is such a $j$, this expression takes on a value of zero; we’ll just bound $\left|(-1)^{\sum^{n-1}_{i=0}\alpha_j(r(i))_j}\right|$ by 1, and because there are at most $n$ such $i$, we get the desired bound on bias once we apply Weil’s theorem.

AMN’s Generalization

We first define AMN’s generalization of bias to $\mathbb{Z}^n_d$:

Definition 2: A probability distribution $X$ is an $\epsilon$-biased space if 1) $X_i$ is uniformly distributed over $\mathbb{Z}_p$ for all $1\le i\le n$, and 2) for all test vectors $\alpha\in\mathbb{Z}^n_d$ and corresponding $g = \text{gcd}(\alpha_1,...,\alpha_n,p)$, $\frac{1}{g}\left|\Pr\left(\sum^n_{i=1}a_iX_i\equiv kg\pmod{d}\right)-\frac{g}{d}\right|\le\epsilon$.

A bit of computation tells us that the Fourier coefficient of an $\epsilon$-biased distribution with respect to $\alpha$ is bounded above by $\frac{1}{p^{n-1}}\text{bias}(\alpha)$. Another useful fact is that the $L_1$-distance between any distribution on $\mathbb{Z}^n_p$ and the uniform distribution is at most $p\sum_{\alpha}\text{bias}(\alpha)$.

We now present AMN’s generalization of AGHP’s characters construction for $\mathbb{Z}^n_d$.

Pick $q$ and a character $\chi_r$ of $\mathbb{F}^*_q$ such that the order of $\chi$ is $d$. Fix elements $b_1,...,b_n\in\mathbb{Z}_p$. Define a map $r: \mathbb{F}^*_q\to\mathbb{Z}^n_d$ as follows: for $i\in\mathbb{F}^*_q$, take $r(i)_j$ to be the $\pmod{d}$-residue of the exponent $s_j$ such that $z^{s_j} = i + b_j$ if $i + b_j \neq 0$, and to the $\pmod{d}$-residue of the exponent $s_j$ such that $z^{s_j} = b_j$.

The motivation is that for $\omega$ a primitive $d$th root of unity (taking the place of $-1$ in the original construction), and for $\chi_r(x) = \omega^{\log x}$, with $\log x$ the discrete log of $x$ with respect to generator $z$, we have that $\omega^{r(i)_j} = \chi_r(i+b_j)$.

Theorem 2$\text{Im}(r)$ is $\frac{(n-1)\sqrt{q} + n}{q}$-biased.

We make use of a corollary of Weil’s theorem:

Proposition: If $r_k$ denotes the number of solutions to $\chi(f(x)) = \omega^k$, then $|r_k - q/d|\le (n-1)\sqrt{q}$. This follows from a bit of computation following the observation that $\sum_{x\in\mathbb{F}_q}(\chi(f(x)))^k = \sum^{d-1}_{j=0}r_j\omega^{kj}$ for all $0\le k.

We now proceed with the proof that the image of $r$ is a small-bias space:

Proof: Denote the random variables given by the coordinates of the image of $r$ by $X_1,...,X_n$. It is clear that each $s_i$ is equidistributed over $[q-1]$ and thus $X_i$ is equidistributed over $\mathbb{Z}_d$ because $d|q-1$. As in the proof of our first theorem, consider the cases of $i+b_j = 0$ for all $j$ and $i+b_j\neq 0$ for some $j$ separately. The latter case incurs an extra $\frac{n}{q}$ in bias by our reasoning in the AGHP proof. In the former case, $\omega^{\sum^n_{j=1}\alpha_jX_j} = \chi_r\left(\prod^n_{j=1}(i+b_j)^{a_j}\right)$. If $\text{gcd}(\alpha_1,...,\alpha_n,d) = 1$, then the greatest common multiplicity of the polynomial $\prod^n_{j=1}(i+b_j)^{a_j}$ is relatively prime to $d$, and we can apply the corollary to Weil’s theorem to get that if there are $r_k$ values of $i$ such that $\sum^n_{j=1}a_jX_j\equiv k\pmod{d}$, $|r_k-q/d|<(n-1)\sqrt{q}$, and we get the desired bound on bias.

In the case that $g = \text{gcd}(\alpha_1,...,\alpha_n,d)>1$, we know from the above argument that if $g' = \text{gcd}(\alpha_1,...,\alpha_n)$, $\alpha' = \alpha/g'$ has the desired level of bias, and a bit of modular arithmetic gives the same bound for $\alpha$.

In our next post, we will examine the problem of fooling not just linear tests, but low-degree polynomial tests.