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 dth 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<d.

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.


Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s