Simple Affine Extractors Using Dimension Expansion

Let F_q be the field of q elements. An (n, k)-affine extractor is a mapping D : F_qⁿ→ {0,1} such that for any k-dimensional affine subspace X ⊆ F_qⁿ, D(x) is an almost unbiased bit when x is chosen uniformly from X. Loosely speaking, the problem of explicitly constructing affine extractors gets harder as q gets smaller and easier as k gets larger. This is reflected in previous results: When q is ´large enough´, specifically q = Ω(n²), Gabizon and Raz construct affine extractors for any k ≥ 1. In the ´hardest case´, i.e. when q = 2, Bourgain constructs affine extractors for k ≥ δn for any constant (and even slightly subconstant) δ > 0. Our main result is the following: Fix any k ≥ 2 and let d = 5n/k. Then whenever q > 2 · d² and p = char(F_q) > d, we give an explicit (n, k)-affine extractor. For example, when k = δn for constant δ > 0, we get an extractor for a field of constant size Ω((1/δ)²). We also get weaker results for fields of arbitrary characteristic (but can still work with a constant field size when k = δn for constant δ > 0). Thus our result may be viewed as a ´field-size/dimension´ tradeoff for affine extractors. For a wide range of k this gives a new result, but even for large k where we do not improve (or even match) the previous result of, we believe that our construction and proof have the advantage of being very simple: Assume n is prime and d is odd, and fix any non-trivial linear map T : F_qⁿ→ F_q. Define QR : F_q → {0,1} by QR(x) = 1 if and only if x is a quadratic residue. Then, the function D : F_qⁿ → {0,1} defined by D(x) =^△ QR(T(x^d)) is an (n, k)-affine extractor. Our proof uses a result of H- - eur, Leung and Xiang giving a lower bound on the dimension of products of subspaces.