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 -biased sets over , due to Azar/Motwani/Naor.
Preliminaries and AGHP’s Construction
Characters of finite abelian groups are homomorphisms . It is easy to see that the only characters of are given by , where is a generator of . We have the following useful theorem due to Weil:
Theorem 0: (Weil) For an odd prime power, with distinct zeroes in the algebraic closure of , and a character with order not dividing the greatest common multiplicity of ‘s roots, .
For AGHP’s construction, we restrict our attention to the only nontrivial character in the case of taking values only in , namely the quadratic character. Concretely, we have the following definition:
Definition 1: The quadratic character sends to 1 if it is a quadratic residue and -1 otherwise. Assign to be 0.
AGHP’s construction is remarkably simple: define bitstring-valued map by if , otherwise let . The motivation for this is that (for ).
Theorem 1: is -biased.
Proof: The bias by definition . For the for which there is no such that and , . For for which there is such a , this expression takes on a value of zero; we’ll just bound by 1, and because there are at most such , we get the desired bound on bias once we apply Weil’s theorem.
We first define AMN’s generalization of bias to :
Definition 2: A probability distribution is an -biased space if 1) is uniformly distributed over for all , and 2) for all test vectors and corresponding , .
A bit of computation tells us that the Fourier coefficient of an -biased distribution with respect to is bounded above by . Another useful fact is that the -distance between any distribution on and the uniform distribution is at most .
We now present AMN’s generalization of AGHP’s characters construction for .
Pick and a character of such that the order of is . Fix elements . Define a map as follows: for , take to be the -residue of the exponent such that if , and to the -residue of the exponent such that .
The motivation is that for a primitive th root of unity (taking the place of in the original construction), and for , with the discrete log of with respect to generator , we have that .
Theorem 2: is -biased.
We make use of a corollary of Weil’s theorem:
Proposition: If denotes the number of solutions to , then . This follows from a bit of computation following the observation that for all .
We now proceed with the proof that the image of is a small-bias space:
Proof: Denote the random variables given by the coordinates of the image of by . It is clear that each is equidistributed over and thus is equidistributed over because . As in the proof of our first theorem, consider the cases of for all and for some separately. The latter case incurs an extra in bias by our reasoning in the AGHP proof. In the former case, . If , then the greatest common multiplicity of the polynomial is relatively prime to , and we can apply the corollary to Weil’s theorem to get that if there are values of such that , , and we get the desired bound on bias.
In the case that , we know from the above argument that if , has the desired level of bias, and a bit of modular arithmetic gives the same bound for .
In our next post, we will examine the problem of fooling not just linear tests, but low-degree polynomial tests.