Abstract

Introduction
1
High-quality randomness is needed for a variety of applications. However, most physical sources are only weakly random. Moreover, such weak sources arise in cryptography when an adversary learns information about a uniformly random string. It is therefore natural and important to try to extract the usable randomness from a weak source. It is impossible to extract even one bit of randomness from a natural yet large enough class of sources using a single function [SV86]. There are two ways to counter this. One is to extract with the help of a small amount of randomness; this is called a seeded extractor [NZ96].  Our focus is on the second way: to extract only from more structured sources (and not allow any auxiliary randomness). Such a function is called a deterministic (or seedless) extractor. We now give a formal definition of extractors. In the following definition the term source simply refers to a random variable. Definition 1.1. A function Ext : {0,1} n → {0,1} n  is an ϵ -extractor for a family of sources X  if for every X ∈ X , the distribution Ext(X) is ε-close in statistical (variation) distance to Um. Here Um denotes the uniform distribution on m bits. We measure the randomness in a source X using min-entropy. Definition 1.2. The min-entropy of a random variable X is
If X ⊆ {0,1} n , we say that X has entropy rate H ∞ (X)/n. The probabilistic method shows that if | X | ≤ 2 -9 k , where k is the min-entropy of each source, then there exists a deterministic extractor for X . Constructing such an extractor explicitly is a much harder challenge.  One type of source for which deterministic extractors have been constructed is an affine source - a uniform distribution over an affine subspace of a vector space [GR05, Bou07a, DG10, Yeh11, Li11, BDL14]. In this paper, we explore generalizations of affine sources with more minimal structure. We show that an explicit deterministic extractor can be constructed for a broad generalization of affine sources that we call additive sources. Remark 1.3. Throughout the paper we often abuse notation and refer to a set X as a source. The source is actually the random variable uniformly distributed on the set X. Before presenting our general notion of an additive source, it will be instructive to look at two simpler natural generalizations of affine sources that are special cases of our notion. The first generalizes an affine source when viewed as the image of a linear map. The second generalizes a linear source when viewed as the kernel of a linear map. Generalized arithmetic progressions   An affine subspace in Z r may be viewed as the set of elements V = {α 1 · t 1 + . . . α r · t r + b | t 1 , . . . , t r ∈ Z p } for some fixed α 1 , . . . ,α r , b ∈ Z p such that α 1 , . . . , α r are linearly independent. One relaxation of this definition would be to not insist that α 1 , . . . , α r be linearly independent, and allow the t i ’s to only range through a subset of Z p of the form {0,.., s − 1}, rather than all of Z p . The result is exactly what is known as a generalized arithmetic progression (GAP). That is, a (r,s)-GAP is a set of the form
for some fixed α₁, . . . , α r , b ∈ Z n and s ≤ p . Bohr sets   A linear subspace in Z n may also be viewed as the set of elements v ∈ Z n such that for all i = 1, . . . , d, L i ( v ) = 0, for some fixed linear functions L 1, . . . , L d : Z p → Z p . A relaxation of this definition could be to look at the set of elements v ∈ V such that L i ( v ) is 'close to zero' for every i ∈ [d]. We could define the distance from zero of an element α ∈ Z p by looking at α as an integer in {0, . . . ,p – 1}, and taking the minimum of the distances between | p – a | and | a – 0| = | a | Equivalently, we could define it as ‖ a/p‖ where ‖ · ‖ denotes the distance to the nearest integer. The resulting definition is what is known as a Bohr set in Z p . That is, a ( d, ρ )-Bohr set is a set B of the form
for some fixed 0 < ρ < 1 and linear functions L 1 , . . . , L d : L p → L p In fact, as opposed to subspaces GAPs and Bohr sets can be defined not just in Z n but in any abelian group. See Definitions 2.3 and 2.6 for the definitions in a general abelian group. We proceed to describe our general notion of an additive source.
1.1
Defining additive sources
Before defining an additive source, we give some intuition on the definition we chose and the pitfalls of other natural definitions. We work in an abelian group G , which is usually Z p or Z p under addition. A first attempt at a minimal structure that generalizes subspaces is to require X  to have small doubling:  | X + X | ≤ C | X | for small C > 1. (Here A+B denotes the set {a+b|a ∈ A,b ∈ B}.) The Cauchy-Davenport Theorem implies that for A ⊂ Z p , | A + A | ≥ min { 2 | A | − 1, p } . Kneser's theorem, which extends the Cauchy- Davenport theorem, implies the same is true for any A ⊆ Z n that is not contained in a strict subgroup of Z n .  So, for obtaining a large class of sources it makes sense to look at C ≥ 2. However, even for C = 2 we get a class of sources for which deterministic extraction is impossible: For let f : G → {0,1} be any such purported extractor. Then the uniform distribution on the larger of f−1(0) and f−1(1) gives a counterexample. If this seems artificial and one asks about smaller sets, we could start with any B such that | B + B | ≤ 2 | B | , such as an arithmetic progression, and then the larger of f-1 (0) ∩ B or f-1 (1) ∩ B gives a counterexample for C = 4. A similar attempt at a definition would be to lower bound the additive energy - a quantity that measures how many sums in X + X lead to the same value. However, this is also insufficient, as sets with small doubling have large energy. In light of the above, we seek to impose an additional condition, besides small doubling. This extra condition involves the notion of symmetry sets from additive combinatorics. A symmetry set for a set X ⊆ G with parameter γ > 0 is defined as
In other words, an element is in Sym չ ( X ) if it can be expressed as x − x ′ , for x, x ′ ∈ X , in at least γ | X | ways. We shall be interested in the setting where γ is close to 1. The simplest examples of sets with large symmetry sets are subgroups and cosets of subgroups. Specifically, if X is a subgroup or a coset of a subgroup, then Sym 1 (X) = X. We note that large symmetry sets don't imply small doubling. For example, if we start with a set Y with Sym 1_α (Y) large, then we could choose a set T of size 2α | Y | with large doubling, such as a Sidon set or random set, and set X = YUT . Then Sym1_3g(X) is large but X has large doubling. Yet this counterexample isn't completely satisfactory, because for extraction it would suffice that whenever X has Sym 1 − α (X) large, there exists a large X ′ ⊆ X , |X ′ | ≥ (1 − ε) |X | , where X ′ has small doubling.  We also give a counterexample to this weakened question.  To give a counterexample with p 1 / d large symmetry sets, it's easiest to work in Z d . Pick a large-doubling set T in Z d− 1 , and let X = T × Z p . Then Sym 1 (X) contains Z p , but X + X has size Θ(|T| 2 p) = Θ(|X| 2 /p). The same is true for large subsets of X . If we worked in Z p instead, we could take a union of intervals, which would give slightly weaker parameters. Thus, we define an additive source to be (the uniform distribution on) a set that has small doubling and has a large symmetry set. Definition 1.4 (Additive source). A set X in a finite abelian group (G,+) is called an (α,β,τ)- additive source if |X + X| ≤ |X|¹+™ and
In Sections 3 and 4 we show that GAPs and Bohr sets in Z p and Z p are indeed captured by our definition of additive sources. As far as we know, these have not been studied in the extractor literature. One can easily see that there are doubly exponentially many (α,β,τ)-additive sources for rea- sonably small α,τ and any constant β < 1. Due to this, there is no succinct representation of a general additive source, unlike affine sources. The only other natural family with doubly exponen- tially many sources is the family of independent sources.
Related work
1.2
We review relevant previous work. The first class of additive sources considered were bit fixing sources by Chor et al [CFG+85], and then by Kamp and Zuckerman [KZ06] and Gabizon, Raz and Shaltiel in [GRS06]. Next, in the more general case of affine sources, Bourgain obtained extractors for constant entropy rate [Bou07a] over F2, with improvements to slightly subconstant rate by Yehudayoff [Yeh11] and Li [Li11]. In the case of large fields, extractors for affine sources were given by Gabizon and Raz [GR05] and more recently by Bourgain, Dvir and Leeman [BDL14]. DeVos and Gabizon [DG10] gave constructions interpolating between these extreme cases. Generalizations of affine sources have also been studied in the work of Dvir, Gabizon and Wigderson [DGW07] and Ben-Sasson and Gabizon [BG11] where the authors look at polynomial sources and by Dvir [Dvi09] where varieties are considered. Special cases of affine sources have also been studied by Rao [Rao08].  Gabizon and Shaltiel [GS08] constructed a weaker object called a disperser over large fields for affine sources.  Ben-Sasson and Kopparty [BSK12] constructed dispersers for affine sources with min-entropy 6 n 4/5 over F 2 . Shaltiel [Sha11] improved on this and constructed a disperser for min-entropy nº(¹) over F2.
Our results
1.3
In our main theorem for Z p for p a large prime, we construct an extractor for additive sources for any constant entropy rate. More specifically, our construction works whenever p is large enough, and for (α,β,τ)-additive sources whenever α and τ are small enough. Specifically, for p an n -bit prime, we need α < 1/n, and we extract about log(1/( αn )) bits. Thus, α = 1/poly( n ) leads to Ω(log n ) random bits whereas α = 1/p 7 leads to Ω( n ) random bits.  We now state our main theorem over  Zp Theorem 1. For every δ,β > 0, there exists τ > 0 and po such that for all primes p > po and α > 0, the following holds.  There is an explicit efficient ε-extractor Ext : Z p → {0,1} m , for (α,β,τ)-additive sources of entropy rate δ in Z p where ε = (3α + p−Ωρ,σ(1)) 2m/2 logp. As a corollary, we obtain extractors for GAPs 1 for any constant entropy rate. Corollary 2 (GAP Sources). For all δ > 0, there exists c,p0 such that for all primes p ≥ p0 the following holds.  For all integers r ≥ c, and all primes p ≥ c r /δ  the following holds.  There exists an explicit efficient ε-extractor Ext : Z p → {0,1} m , for (r,pδ/r)-GAP sources (of entropy rate δ) in Lp where ε = po 357, + p-1/2 | 2m/2 log p. Observe that the only restriction we put is that r ≥ c and p ≥ c r / δ  which simply means that the side lengths of the GAP (that is, p δ / r ) have to be larger than some fixed constant c and the dimension has to be larger than a fixed constant c. Thus, if we let r be a constant, then we can extract a constant fraction of the min entropy, that is Ω(δ log p ) bits. As another corollary, we obtain extractors for Bohr sources. We state it for constant ρ for simplicity. It can be easily generalized to any arbitrary ρ . Corollary 3 (Bohr Sources). Let ρ,α > 0 and S ⊂ Z p with |S| = d be arbitrary.  Then for prime p = Ω ( ( ξ ) α ), there exists an explicit efficient ε-extractor Ext : Z p → {0,1} m , for (d,ρ)-Bohr sources of entropy rate δ in Z p where ε = (3α + p−Ω(1)) 2m/2 log p . Next, we construct an extractor for additive sources in Z n for large enough p (polynomial in n ) and any constant entropy rate, provided the source is sufficiently structured additively and satisfies a certain list decodability property. As a corollary, we give an extractor for GAPs in Z p and Bohr sets with constant entropy rate, provided they satisfy the list decodability property. We note that our extractor works for affine sources even though they may not satisfy the list decodability property. See Section 4.4. Our extractors for GAPs and Bohr sets over Z p , and for Bohr sets over Z p , extract a linear number of bits with exponentially small error. We also show that all large sets (min-entropy rate close to 1), most sets ( δ min-entropy rate for any δ > 0) and most affine sources ( δ min-entropy rate for any δ > 0) satisfy the list decodability condition. See Remark 4.5, 4.6 and 4.7. In the final two sections, we study special cases of additive sources. First, we give an extractor for one dimensional affine sources (lines) in F q which requires only that q > n . This improves the results of Gabizon and Raz [GR05], which required q = Ω( n 2 ). Surprisingly, it even improves the non-explicit bound obtained via the probabilistic method of q = Ω(n log n). Theorem 4 (Extractors for lines). There is an explicit efficient ε-extractor Ext : F n → {0,1} for all line sources in Fq where ε ≤ 4(n/q)¹/². We then show the same extractor in fact works for 'partial lines' - i.e., arithmetic progressions in Zn Theorem 5 (Extractors for APs). There is an explicit efficient ε-extractor Ext : F n → {0,1} m for all k-AP sources in F p where ε ≤ 16 log² p√πp2m/² /k. Therefore, if we have k = p 1 /2+δ  and n < p δ , then we can extract δ /2 log p bits. Moreover, we show that the general framework of [GR05] for constructing extractors for affine sources can be generalized to work for GAPs. See Theorem 5.10. As a corollary, we extend a result of DeVos and Gabizon [DG10] to obtain extractors for GAPs in Z n
1.4
Techniques and Proof Overview
1.4.1
Extractors for additive sources in Zp.
For our proofs it will be convenient to define the notion of a multiplicative source. The definition simply corresponds to that of an additive source with multiplicative notation. Formally, Definition 1.5 (Multiplicative source). Fix positive constants 0 < α,β,τ < 1. Let Y  be a subset of a finite abelian group (G, ). We define the set Sym1-α(Y) ⊆ G by Sym1_α(Y) = {g ∈ G : |Y ∩ (Y · g)| ≥ (1 − α) · |Y|}. We say that Y  is an (α,β,τ)-multiplicative source if |Y ·Y| ≤ |Y|¹+τ  and |Sym¹_α(Y)| ≥ |Y|³. Suppose X is an (α,β,τ)-additive source in Z p . Our extractor construction is as follows. We describe the construction in detail only for this class of sources. Let q be a large prime, q = 1 (mod p ) and g be a generator of Z å of order p . Define Ext( x )     σ( g * ), where σ : Z q → Z m is the function from Lemma 2.8. Then, it is enough by Lemma 2.8, to show that | E x e p (a.g x ) | for all a̸= 0 is small. The analysis break down into two main steps: Step 1: ‘Encoding’ X into a multiplicative source.  As noted before, we fix a prime q > p such that q = 1 (mod p ). For such q there exists an element g ∈ Z z of order p . Fix such an element g and look at the map from Z p to Z q taking x to g x . Let Y ⊆ Z q be the image of X under this map. That is, Y show that Y is an (α, β′, τ)-multiplicative source in Z q , where β′ ～ β . Step 2: Applying a character sum bound of Bourgain together with an 'average to worst-case reduction'.  The advantage of the transition to a multiplicative source comes from a theorem of Bourgain that roughly says the following. Suppose Y is a subset of Z x such that |Y · Y | ≤ |Y |¹+ τ for appropriate 0 < τ < 1. Then, for most α ∈ Z q the sum
is small in absolute value. See Theorem 3.2 for a precise statement (The theorem does not directly correspond to the description here, and actually talks about the 't'th moment of additive characters over Y'.) If we knew that | F ( a ) | is small for all a ∈ Z x rather than most a ∈ Z x , we could extract randomness from Y using the XOR lemma (Lemma 2.8).  Our main insight is that when Sym 1 – α (Y) is large, we can indeed deduce that | Y ( a ) | is small for all a ∈ Z t . We sketch why this is the case. Assume for contradiction that there is some a E Z*g such that
is large. Fix any α ′ ∈ Sym 1_α ( Y ). As |Y ∩ α ′ · Y | ≥ (1 − α) · |Y | and each summand is one in absolute value, the above sum will not change much if we sum over a ′ · Y rather than Y . That is, the sum
must also be large in absolute value. But this sum is equal to
Thus, | Y ( a ′ · a ) | is large for all a ′ ∈ Sym 1 − α ( Y ) - a contradiction as we know that | Y ( b ) | is small for most b ∈ Z* Thus, for all α̸= 0, | E χ e p (a.g × ) | is small. In summary, the extractor construction is Ext( x ) = σ( g × ), where σ : Z q → Z m is the function from Lemma 2.8. See Section 3 for full details.
1.4.2
Extractors for additive sources in T n
Our construction over Z n follows similar lines but is more involved. We give a sketch describing the same basic two steps. Let X be an (α,β,τ)-additive source in Z n Step 1: ‘Encoding’ X into a multiplicative source. We choose n distinct primes q1, . . . , qn such that for all i ∈ [ n ], q i = 1 (mod p ). Let g i be an element of order p in Z q i . Let q = q 1 · · ·q n , and let CRT : Π i Zqi → Zq be the 'Chinese remaindering map'. We look at the map from Z n to Z q taking ( x 1 , . . . , x n ) to CRT( g x 1 , . . , g x n ). Let Y be the image of X under this map. That is, Y = {CRT(g ī x , . . ,g ī x n ) | (x 1 , . . ,x n ) ∈ X } . We can show that Y is an (α,β′,τ)-multiplicative source in Z q , 2 where β′ ～ β assuming q = pO(1). We show that we can indeed get q = pO(1) by observing that the proof of Linnik's Theorem implies that for large enough p , we can always find appropriate q1, . . . , qn that are all at most pO(1) Step 2: Applying a character sum bound of Bourgain together with an 'average to worst-case reduction'.  As in the case of Z p , we would now like to apply a theorem saying that for Y ⊂ Z q such that |Y · Y | ≤ | Y |¹+ץ, | Ỹ ( α )| is small for most 0̸≠ α ∈ Z q . The difference from the case of Z p is that now we are dealing with a composite q . Bourgain indeed has such a theorem for the case of composite q . However, it requires an additional condition on Y apart from |Y · Y | ≤ |Y |¹+ 7 . Roughly speaking, the condition is that if we look at elements of Y modulo a factor q i of q , they are not too concentrated on any particular element of Z q i . See Theorem 4.14 for a precise statement. We show that if X satisfies a certain 'list-decodability' condition, Y satisfies the condition required by Bourgain's theorem. For arbitrary γ > 0, we also show that a random source of min-entropy γη and a random affine source of min-entropy γη satisfy the list decodability condition with very high probability. Thus, our extractor does not work for all additive sources in Z p . The reduction from the statement about most 0̸= α ∈ Z q to all is similar to the description in the case of Zp. We show that for the case of affine sources, we do not need a list decodability condition on X . A potentially useful tool we develop for this is an XOR lemma that guarantees closeness to uniform under a weaker condition than usual. The usual setting, described for example by Rao [Rao07], is when N > M and for all nontrivial characters ψ on Z N , we have E χ [ψ(X)] ≤ ε . Then there's a simple map σ : Z N → Z M such that σ ( X ) is close to uniform. We show that a similar result holds under the weaker assumption that E x [ψ( X )] ≤ ε only for characters ψ of the form ψ( x ) = e n ( a · x ) for a ∈ Z n , i.e., (a, N ) = 1. See Section 4 for full details.
1.4.3
Extractors for APs and GAPs.
For the case when the additive source is an AP or GAP in Z n , we give alternate constructions for a wider range of parameters. For this, we generalize an approach introduced by Gabizon and Raz [GR05] and used by DeVos and Gabizon [DG10] for constructing extractors for affine sources. Their approach was to construct a polynomial f : Z p → Z p guaranteed to be non-constant on any k -dimensional affine subspace. Given such an f of degree d , the Weil bound (Theorem 2.12) can be used to construct an extractor for affine sources of dimension k when p = Ω( d 2 ). We show that the same approach works for GAPs: Suppose we can construct an explicit polynomial f : Z p → Z p of degree d that is non-constant and of degree larger than one when restricted to any affine subspace of dimension k . Then we can construct an extractor for GAPs in Z n of dimension r ～ k , assuming p is roughly Ω( d 2 · log 4 d ). See Theorem 5.8 for a precise statement. Theorem 5.8 follows from a generalization of the Weil bound. Let us first recall the Weil bound of Theorem 2.12 says. Suppose we have a univariate polynomial f over Z p of degree d < √ . Suppose ψ is a non trivial additive character of Z p . Then the character sum, is small; more specifically, it is at most d ⋅ √ q . One may ask what happens when the same sum is taken only on the first s elements of Z p . Perhaps it is significantly larger than d · √ q and becomes smaller only when running over the whole field? We show this is not the case. More precisely, for any 0 ≤ s < p we have
The proof uses a combination of Theorem 2.12 and Fourier analysis. (see Lemma 5.11). For example, a central step is to bound the Fourier coefficients of the function ψ o f using the Weil bound. See Section 5.2 for full details. Extractors for lines over smaller fields.   [GR05] used the approach mentioned above to con- struct extractors for line sources in Z p over fields Z p of size p = Ω( n 2 ). The main component in their construction was an explicit polynomial f : Z p → Z p of degree n that is non-constant when restricted to any affine line. We improve on this and construct a polynomial f of degree O( √ π ) that is non-constant on any affine line. As a result we get extractors for line sources in p = Ω(n). We sketch the construction of f . ● The first step is to construct a polynomial g : Z p → Z p of degree n that is non-constant on any line, and moreover, has the following stronger property: The restriction of g to any affine line will have degree exactly n (rather than just at most n ). We show that taking g to be a 'norm polynomial' insures this property. ● The second step is to partition the n coordinates into blocks of ascending size 1, 2, . . . , l where l = O( √ π). Now, let g i : Z i , → Z p denote the ‘version’ of the polynomial g when applied to a domain of i coordinates. We apply g i to the i'th block. Note that the degree of the g i's is at most deg( ge ) = ℓ = Ο( √ n ). ● Now we define f to be the sum of the g i 's when applied to the corresponding blocks. Note that deg( f ) = O( √ n ). We claim that f is non-constant on any affine line: Fix any affine line L , and fix the maximal i ∈ [ ℓ ] such that L is non-constant when restricted to the coordinates of the i ' th block. The above-mentioned property of g guarantees that the ' g i -summand of f ' restricted to L will have degree i. All other summands will either be constant or of lower degree. Thus, f restricted to L is non-constant. See Section 5 for full details.
1.5
Organization
In Section 2, we present basic definitions. In Section 3, we present our deterministic extractor for additive sources in Z p , and instantiate it in the case of GAPs and Bohr sets. In Section 4, we give our deterministic extractor for sources in Z n and again instantiate it in the case of GAPs and Bohr sets. In Section 5, we construct deterministic extractors for lines (1 dimensional affine spaces), partial lines in
2
Definitions
In the following, p will denote a prime number. For x ∈ R , ∥ x ∥ denote the distance to the nearest integer. e(x) denotes the complex number e 2 π ix and e m (x) denotes e 2 π ix /m for any positive integer m. To avoid clutter, ey is written is exp(y).
2.1
Probability Distributions and Extractors
As mentioned earlier, a set X and a source X shall be used interchangeably where a source X denotes the uniform distribution on the set X.
Additive Combinatorics
2.2
We now state some standard terminology from additive combinatorics.  We refer the reader to [TV06] for more details. In this section, let us fix a finite abelian group ( G , +). Definition 2.1 (Representation function). Let A be a subset of G. For g ∈ G, we define repa-a(g) = |A ∩ (A + g)| which is the number of ways to represent g as a difference of two elements in A. Definition 2.2 (Affine source and line source). A δ-affine source in Z n is an affine source of dimension δn. A dimension 1 affine source is called a line source. Definition 2.3 (Generalized arithmetic progression). An ( r, s )-Generalized arithmetic progression (or GAP for short) in G defined is a set of the form for fixed elements b0, b1, . . . , br ∈ G (note that the a i ’s are integers rather than elements of G). We say that the GAP is proper if all the s" sums are distinct. The dimension of the GAP is r. All GAPs are assumed to be proper in this paper unless mentioned otherwise. In fact, we will see in Section 5.2 how to handle general GAPs in F n . Definition 2.4 (k-AP and k-line). An arithmetic progression of length k (or k-AP for short) is a (1, k)-GAP. A k-AP in Fq is also called a k-line. Definition 2.5 (k-HAP). A homogenous arithmetic progression of length k (or k-HAP for short) is a k-AP with bo = 0. Definition 2.6 (Bohr set). Let S be a set of characters of G and let ρ > 0. Then we define the Bohr set Bohr(S,ρ) = { x ∈ G : max |ξ( x )| < ρ} We call the ρ the radius and | S | the rank of the Bohr set.  We refer to a Bohr set of rank d and radius ρ as a (d,ρ)-Bohr set. Bohr sets and GAPs are closely related. In particular, any Bohr set contains a large GAP with small dimension [Ruz09, Theorem 7.1]. We say that a Bohr set is regular if additionally,
whenever κ < 1/100|S|. Regular Bohr sets have the property that increasing the radius of the Bohr set by a little does not make the Bohr set very large. In fact, regular Bohr sets are ubiquitous [TV06], that is every Bohr set is "close" to a regular Bohr set. More precisely, for every S and ε, there is ρ ∈ [ ε, 2ε ] such that Bohr( S, ρ ) is regular. In this work, all Bohr sets will be regular Bohr sets. When G = Zp, we know that the dual of G is isomorphic to G. Thus, in this case, we can consider S ⊂ Z p and the Bohr set
Here ‖ · ‖ denotes the distance to the nearest integer. Note that if G is a vector space over F g , then every subspace of G is a Bohr set with radius 1/q and rank equal to the codimension of the subspace.  Thus, Bohr sets are generalizations of subspaces and are substitutes for the latter when G has no proper subgroups (e.g., when G= Zp ). Bohr sets can also be thought of as the inverse image of a cube in C S (where C is the unit circle in C) if one considers the map x → (ep(ξ · x))ξ∈ς. This is justified by the inequality 4‖θ‖ ≤ |ε(θ) − 1‖ ≤ 2π‖θ‖.
2.3
Characters
Let f : Z m → C be any function. Recall that, for 0 ≤ j ≤ m − 1, the Fourier coefficients of f are given by
It is well known that the set of functions {exp(2πijx/m)}0<j<m-1 is an orthonormal basis for all complex functions defined on Z m , and that f can be expressed as
Let us consider f : Zm → [0, 1]. Thus, Parseval's identity states that Exponential/Character sums to extractors. Throughout the paper, ψ and χ denote additive and multiplicative characters respectively and ψ o and χ o denote the trivial additive and multi- plicative characters respectively. We let en(x) denote e2πiz/n. We now state two lemmas that gives a black box construction of deterministic extractors from exponential/character sums. Note that we use the term exponential sum for additive characters and character sums for multiplicative characters. The following lemma is for exponential sums. [X] ∑ x ∈ x ψ (x)  < ε ∀ψ̸= ψ o, then there exists an efficient σ : F p → Lemma 2.7. Let X ⊆ F n . If Fp  such that |σ(X) − ∪| < ε√pm We state a similar lemma that works for cyclic groups. A proof of this can be found in [Rao06]. Lemma 2.8. Let X ⊆ Z N . If | X | Σ π x Ψ ( x ) | < ε ∀ ψ ≠ ψ 0, then there exists an efficient σ : Z N → Z M  such that |σ(X) − U| < ε√M log N + O(M/N) The next lemma is for character sums. Lemma 2.9. Let X ⊆ F p n . If | [x] ∑ x ε x x(x)| < ε ∀ x ≠ xo, then there exists an efficient σ : F p n → F p m  such that Proof. Without loss of generality let us assume that m divides n . If not, we can always append 0's to increase the dimension by a factor of at most 2. We have the following standard claim. Claim 2.10. Let X be a distribution on G such that |E[χ(X)]| ≤ ε ∀χ ≠ χο. Then, X is ε√|G[ close to U . With the above claim, we define σ : F x n → F x m as σ(x) = x x x − 1 . Claim 2.11. Given a nontrivial multiplicative character Ψ of F x m , Ψ o σ is a nontrivial multiplica- tive character of F*n
The Riemann Hypothesis for curves over finite fields. In 1948 Weil [Wei48] proved the celebrated Riemann Hypothesis for curves over finite fields. A consequence of Weil's result is a bound for exponential and character sums over low degree polynomials over a finite field. We state it below. The theorems can also be found in [Sch76]. Theorem 2.12 (Weil's bound). Let ψ be a nontrivial additive character of Fq. Let f(t) ∈ Fq[t] be a polynomial of degree m. Let gcd(m,q) = 1. Then
Theorem 2.13 (Weil's bound). Let χ be a nontrivial multiplicative character of F q of order d. Let f(t) ∈ F q [t] be a polynomial of degree m. Suppose that f (t) is not of the form cg (t) d  for any c ∈ F q and g(t) ∈ F q [t].  Then

3
Extractors for additive sources in Z p
We now state our extractors for additive sources in Zp.
3.1
An extractor for additive sources
Our main theorem for Z p (Theorem 1) follows from the following theorem. Theorem 3.1. Fix any δ > 0 and positive constant C.  There exists po ∈ N such that for all primes p ≥ p 0 the following holds. There is an explicit efficient ε-extractor Ext : Z p → {0,1} m , for (α, β, τ)-additive sources of entropy rate δ in Z p where δβ ≥ 2t log p (1/α) + δ/C, ε = 3α2m/2 log p + O(2m /p) and τ,t are constants depending only on δ and C. Proof of Theorem 1. Let C = 2/β and γ = αξ. Then the hypothesis of the above theorem is satisfied if α > p − γ . The 2 m /p term can now be dropped by assuming without loss of generality γ < 1/2. Now, since, any (α,β,τ)-additive source is an (α ′ ,β,τ)-additive source for α < α ′ , this finishes the proof. ● The above theorem follows from Lemma 3.3 and Lemma  2.8. Before we state Lemma 3.3 and prove it, we state the following theorem. Theorem 3.2 ([Bou05a, Theorem 1']). For all Q ∈ Z +, there is τ > 0 and t ∈ Z + such that if H ⊂ F ∞ satisfies |H · H | < |H |¹+ r , then
Lemma 3.3. There exists p 0 ∈ N such that for all primes p ≥ p 0 the following holds. There exists an efficient f : Zp → Zq (for q = o(p 6 )) such that if δ > 0 is arbitrary and C is an arbitrary large constant, then there exist τ(δ,C) > 0 and t(δ,C) such that if ● X is an (α,β,τ)-additive set of entropy rate δ in ( Zp,+) , ● βδ ≥ 2t log (1/α) + δ/C, then, for all ξ ∈ Lq \ {0},
Proof. Let q be the smallest prime such that q = 1 (mod p ). By Linnik's theorem, such a q exists and q = O( p 5.2 ). Let g be an element of Z q ⊂ Z q such that ord( g ) = p. Now define f : Z p → Z q as follows. Let f(x) = gx. Let Y = f(X). Let S = Sym1-a(X). Claim 3.4. Y is a (α,β,τ)-multiplicative set of entropy rate δ/6 in ( Z *, × ). Proof. We first note that f : X → Y is injective. To see that, suppose for x,y ∈ Zp we have g x = g v . This implies g x-v = 1. Since ord(g) = p, we have x ≡ y (mod p). Now, since f is injective, |Y| ≥ p δ ≥ q δ /6. Also, we claim that for each a ∈ S , repy.y-1(f(α)) ≥ (1 − α)|Y|: This is because if α ≡ x − x ′ (mod p) for x,x ′ ∈ X , then g α = g x− x ′ = f(x)/f(x ′ ) ∈ Y · Y− 1 , where the first equality again uses the fact that ord(g) = p. So | Y ∩ ( Y · f (α)) | = | X ∩ ( X + α) | ≥ (1 −α) | Y | . Now, observe that | f ( S ) | ≥ | X | β = | Y | β . Finally, we show that | Y · Y | ≥ | Y | 1+ 7 . This follows from ● the fact that for a, b ∈ X, f(a) · f(b) = f(a + b) and therefore |Y · Y| = |X + X|. We now continue with the proof. Let Q = 6C/δ. Let M = maxξ≠ο ∑ y ∈ y ∈ q (ξy) | and let ξ attain M. Claim 3.5. M < 3|Y|α. Proof. Suppose M ≥ 3 ( Y ) α . Consider any ξ ′ ∈ f ( S ). Then,
Since this lower bound holds for any ξ ′ ∈ f ( S ), we have
Therefore, since | f ( S ) | ≥ p δβ , and Y satisfies the hypothesis of Theorem 3.2, we have
for large enough p. But this implies δβ − 2t log n (1/α) < δ / C which is a contradiction. Thus, we ● have max ≠ 0 < 3 Y α. This implies
We proceed to formally show that GAPs and Bohr sets are indeed additive sources in Z p . We then use Theorem 3.1 to derive corollaries on these types of sources.
3.2
Application to GAPs and Bohr sets
We first show that a GAP source is an additive source with the appropriate parameters.  We assume that the GAP is proper in this subsection. Lemma 3.6. For all ε > 0, there exists c,no ∈ N such that for all prime p ≥ no the following holds.  If δ ≥ c/logp, then an (r,p δ )-GAP source is a (r/p 0.9 δ ,0.1,ε)-additive source of entropy rate δr in (Zp, +). Proof. Let X be the ( p δ , r )-GAP source defined by X = { b 0 + ∑ i = 1 α i b i : 0 ≤ α i ≤ s − 1} where s = p δ and let it be (αφ,βρ,τφ)-additive. It is easy to see that the entropy rate is δr. The lemma now follows from a series of claims. Claim 3.7. τ 0 ≤ ε for all ε > 0. Proof. Note that
Therefore, |X + X| ≤ 2rsr = 2r|X| since X is a proper GAP. Now, 2r < |X| 70 iff s70 > 2 which is true for constant τ 0 = ε since s = p δ ≥ 2 c . ● Claim 3.8. α = r/p0.9δ  and β = 0.1. Proof. Consider the set S = { b 0 + ∑ i =1 α i b i : 0 ≤ α i < s 0 .1 } . Now fix an arbitrary x ∈ S . Then,
Therefore, | X ∩ ( X + x ) | ≥ ( s − s 0.1 ) ″ = | X | (1 − 1/s 0.9 ) ″ > | X | (1 − r /s 0.9 ). Also, we have | S | ≥ |X|0.1. This proves the claim.
Note that the requirement of δ ≥ c/ log p merely means that the sides of the GAP are p δ = Ω(1) in length. Next, we show that a Bohr set is an additive source with the appropriate parameters. We will use the following lemma from [TV06] for the group G . As before let S be a set of frequencies of G . Lemma 3.9 (Lemma 4.20 [TV06]). |Bohr(S, ρ)| ≥ ρ l S ||G| and |Bohr(S, 2ρ)| ≤ 4 l S ||Bohr(S, ρ)|. We are now ready to prove our lemma about Bohr sets. Lemma 3.10. Let β,ε,δ,ρ > 0 be arbitrary and S ⊂ G be a set of frequencies. Let B = Bohr( S,ρ) in G where d = |S|. Let 0 ≤ κ ≤ 100α. A Bohr source is a (100κd,β,ε)-additive source of entropy rate δ in G whenever | G | ≥ max Proof. |B| ≥ ρ d |G| by Lemma 3.9 and by the hypothesis, we have |B| ≥ |G| δ . To see that B has small doubling, observe that B + B ⊆ Bohr( S, 2 ρ ) and therefore, using the fact |Bohr( S, 2 ρ )| ≤ 4 Bohr( S, ρ ) (Lemma 3.9) we have |B + B | ≤ 4 α |B | < |B |¹+ε . The last inequality is true because | B | ≥ ρ d | G | (Lemma 3.9) and ρ d | G | > 4 d / c by hypothesis. We now argue the presence of large symsets in B . Let Y = Bohr( S, κρ). Fix y ∈ Y . For any x ∈ Bohr( S, (1 − κ)ρ), x + y ∈ B. Therefore, | B ∩ ( y + B ) | ≥ | Bohr( S, (1 − κ)ρ ) | ≥ (1 − 100 κd ) | B | This is because we consider regular Bohr sets.  Also, |Y| ≥ ( κρ ) d |G| > |G| β ≥ |B| β by the hypothesis ■ and Lemma 3.9. This finishes the proof. GAP sources. We first restate our corollary for GAP sources. Corollary 2.  For all δρ > 0, there exists c,p 0 ∈ N,δρ > 0 such that for all primes p ≥ p 0 the following holds. There exists an explicit efficient ε -extractor Ext : Zp → {0,1} n , for ( r,p δ )- GAP sources (of entropy rate δ 0 = δr) in Z p where p δ ≥ c, r ≥ Cδ 0 (where Cδ 0 is a constant
depending on δ 0 only) and ε = 3 (r/p 0.9δ + p −1/2) 2m/2 logp. Proof. By Lemma 3.6, an ( r, p δ )-GAP source is a ( r/p 0.9 δ , 0.1, τ )-additive source of entropy rate δr in Z p for all τ > 0. We will apply Theorem 3.1 with C = 20 and δ ′ = δr which is a constant. Therefore, t and τ from the theorem conclusion are also constants. Note that we already have s > 2c by Lemma 3.6.  Now, the second condition in Theorem 3.1 is equivalent to 0.1δr > 2t log p ( p 0.9δ /r ) + δr/20 is satisfied if r ≥ 36t. We also drop the 2 n /p by putting a p-1/2 term similar to Theorem 1. ● This finishes the proof. Note that the above extractor works for GAPs with sides as small as superconstant. It works as long as the total volume of the GAP exceeds p (1) which clearly improves upon a standard convex combination argument by extracting of each individual AP as that would need at least p Ω (1) entropy along each side. We now restate our corollary for Bohr sources. Bohr sources. Corollary 3. Let ρ,α > 0 and S ⊆ Z p with | S | = d be arbitrary. Then for prime p = Ω ( ( ₫ ) α there exists an explicit efficient ε -extractor Ext : Z p → {0,1} m , for ( d,ρ ) -Bohr sources of entropy rate δ in Z p where ε = (3α + p−Ω(1) 2m/2 log p . Proof. By Lemma 3.10, any Bohr( S, ρ ) is a (100 κd, β, ε )-additive source of entropy rate δ in Z p d/1-δ (ニ) d/1-β . The statement follows from the lower bound whenever p ≥ max ● on p and Theorem 1. Note that the upper bound on δ is reasonable because as δ increases the Bohr structure keeps fading away. Hence we cannot extract from arbitrarily large Bohr sets. We can extract more randomness from GAPs under the Paley Graph Conjecture which we show in Appendix A.
Extractors for additive sources in Z n
4
We now state our extractors for additive sources in π n
4.1
GAPs and Bohr sets
We first show that a GAP source is an additive source with the appropriate parameters. Lemma 4.1. For all ε > 0, there exists c,no ∈ N such that for all prime p ≥ no the following holds.  If δ ≥ (C/logp), then an (r = μπ,pβ)-GAP source is a (μπ/pβ.9δ,0.1,ε)-additive source of entropy rate δμ in (Zp, +). Proof. Let X be the (r = µn,p δ )-GAP source defined by X = { b 0 + ∑ i = 1 α i b i : 0 ≤ α i ≤ s − 1} where s = p δ and let it be (α 0 , β 0 , τ 0 )-additive. It is easy to see that the entropy rate is μδ . The lemma now follows from a series of claims. Claim 4.2. τ 0 ≤ ε for all ε > 0. Proof. Note that
Therefore, |X + X| ≤ 2rsr = 2r|X| since X is a proper GAP. Now, 2r < |X|70 iff s70 > 2 which is true for constant τ 0 = ε since s = p δ ≥ 2c. ● Claim 4.3. α = r/p 0.9δ  and β = 0.1. Proof. Consider the set S = { b 0 + ∑ i =1 α i b i : 0 ≤ α i < s 0 .1 } . Now fix an arbitrary x ∈ S . Then,
Therefore, | X ∩ ( X + x ) | ≥ ( s − s 0.1 ) ″ = | X | (1 − 1/s 0.9 ) ″ > | X | (1 − r /s 0.9 ) . Also, we have | S | ≥ |X|0.1. This proves the claim. Note that the requirement of δ ≥ (C/logp) merely means that the sides of the GAP are p δ = Ω(1) in length. We have already shown in Lemma 3.10 that Bohr sets are additive sources. We now proceed with the main theorem of this section.
4.2
Extractor for additive sources
We say that a set X is ( r, B )-list decodable if for any arbitrary r indices i 1 , ···ir, c j ∈ Z p for j ∈ [ r ], X x i 1 =c 1 ,...x i r =c r | ≤ B . We now state the main theorem of this section. Theorem 4.4. There exists p 0 , L 0 ∈ N such that for all L ≥ L 0 and primes p ≥ p 0 the following holds.  Let γ,κ > 0 be arbitrary.  There exists an efficient ε-extractor Ext : Z p → {0,1} m for (α, κL/δ, τ)-additive sources of entropy rate δ in ( Zp, +) where n ≤ p l−2, X is (r,p−r γ l . | X |)-list decodable for every τn/L ≤ r ≤ n and ε < (3α + |X|-τ) 2m/2 log pn + O(2m/pn) where τ is a constant depending on γ and κ. The following remarks show that the list decodability condition is not too restrictive. Remark 4.5 (Min-entropy (1 – ε ′ )n is list decodable). In fact, for high enough min-entropy, we can now eliminate the list decodability assumption altogether. Given L, choose γ = 1/(4L), (and fix some κ > 0 as in Theorem 4.4). Now this fixing of γ and κ also fixes some τ > 0. Denote α = τn/L.  We claim the theorem can now be applied to any source of entropy k = n − α/2.  Fix such a source X . For r > a, and any fixing of any r coordinates, the corresponding list will be of size at most p n-r.  We need to show that this is smaller than p-L^r|X| = p-r/4+n-a/2  It can be checked that this is indeed the case
Remark 4.6 (Random set of min-entropy ε ′ n is list decodable). A random set X  of size | X | > φ 2 L γπ satisfies the list decodability condition with high probability.  To see this, fix r > τn/L, a set of indices S of size r, field values c1,...,cr for those indices and a subset W of the set of size B = p-γ Lr|X|+1.  The probability that all of W  has the property that the coordinates in S get values c i 's is (1/pr) β . A union bound over all W gives ( | β | )(1/pr) β < (|X|e/B) β (1/pr) β << 1/po.9rB as γ is arbitrarily small. An outer round of union bound over each of the p r settings of c i 's and S is too mild to boost up the error probability for large p. Remark 4.7 (Random affine source of min-entropy ε ′ n is list decodable). Let γ < 1/L be an arbitrary small constant. A subspace X of dimension k > 27Ln defined by a random k × n matrix satisfies the list decodability condition. Indeed, let G be the random k × n matrix. We know that for any submatrix C of r columns in G, C has rank at least γr L with high probability. To see this, fix a subset of r column indices. Let a = γrL. Note that a < k/2. Let C be the submatrix of G defined by the r columns. Then, Pr[rank(C) < a] < ( ω )pα−k . Here we are saying that some choice of the a columns of C will be linearly independent and then using the bound that a random s × t matrix has full rank with probability roughly at least 1 – p 8–t (for s < t/2).  Continuing with the analysis, ( r )pα−k < 2rp−k/2 < 2np−k/2.  Taking a union bound over the choice of r columns, we incur another factor of 2 n , and taking p ≥ 5 2 n/k  gives error at most (4/5) n , finishing the proof.  Let us continue with the proof. Fix r coordinates i1,...,ir. Let c1,...,cr be r values in the field. Since the corresponding submatrix C has rank at least γ L, the number of strings in X which are c 1 in coordinate ij, j = 1, . . . , r, is at most p-rlr|X|. This satisfies the list decodability condition for all r. The theorem follows from Lemma 4.18 and the following lemma. Lemma 4.8. There exists po, Lo ∈ N such that for all L ≥ Lo and primes p ≥ po the following holds. There exists an efficient f : Z p → Z q (for p n < q < p L n ) such that if γ, κ > 0 are arbitrary, then there exists τ > 0 such that if ● X is an (α, κξ,τ)-additive source of entropy rate δ in ( Z n, +) ● for every integer τn/L ≤ r ≤ n, X is (r,p-r-γ-L · |X|)-list decodable, Then, for all ξ ∈ Zq \ {0},
Proof. Let q1, q2, . . qn be n distinct primes such that for all i, qi ≡ 1 (mod p ). This is guaranteed by the following consequence of (the proof of) Linnik's theorem. Claim 4.9. There exist constants L 0 > 0 and n 0 ∈ N such that for all p ≥ n 0, L ≥ L 0, the size of the set
is at least pL-2 Proof.  Define
By [IK04, Corollary 18.8], there is a constant L 0 (known as Linnik's constant ) such that for all p sufficiently large and x ≥ p L 0 , we have
for some constant C , where φ ( n ) is Euler's totient φ function. Let
If x = p L for L ≥ L 0 , then this is Then π(x,p) log x ≥ θ(x,p) ≥  C ≠ ≥ . Thus, π(x,p) ≥ p3/2 log x ● clearly ≥ p L − 2 . Thus, by the above, we have for all i, qi < p L . Also, let gi generate the order p subgroup in Z *, Define two maps φ 1 , φ 2 as follows. Let φ 1 : Z n → Π i ∈ [n] Z q i be defined by
and for q = Π i ∈ [n] qi, let φ 2 : Π i ∈ [n] Zqi → Zq be defined by
where [ x − 1] p is the inverse of x in Z t . Note that φ 2 is the Chinese remaindering map. Define function f as follows.
Let Y = f ( X ). | Y | ≥ q δ / L . In the following, define for q ′ , q, π q : Zq → Zq ′ by πq ′ ( x ) = x  (mod q ′ ). Then, for ξ ∈ Z q , we define π − 1 (ξ) = { x ∈ Z q : π q ′ ( x ) = ξ} . We now have the following claim. Claim 4.10. If q'|q, and q' > q' , ξ ∈ Zq' , then |Y ∩ πζ 1 (ξ)| < (q')- γ |Y|. Proof. Without loss of generality, let q' = Π i =1 q i for r ≤ n. As q > q T , we have p l r > q T > p n , since each q i ≥ p . Therefore, r > π ζ . Next, we need the following claim. Claim 4.11. Let q' be as above. Given any ξ ∈ Z q , let ξ i = ξ (mod q i ) for 1 ≤ i ≤ r. Then for Y ⊆ Lq, we have
Proof. Note that Y ∩ π q 1 (ξ) = { y ∈ Y : y (mod q ′ ) = ξ}. The condition y (mod q ′ ) = ξ can be re-written as yi = ξ i  (mod q i ) as q i |q ′ |q . Therefore, we have
● Now, by the hypothesis, for r ≥ nτ/L , we have for any c 1 , . . . , c r ,
as pr L > q ′ . This finishes the proof. ● Next, we have the following. Claim 4.12. |Y.Y| < |Y|¹+ｧProof. This follows because f is an one-one function from ( Z p , +) into ( Z q , *). ● Next, we have the following claim. Claim 4.13. |Sym1_α(Y)| ≥ q*. Proof. The proof follows because f is an one-one function from ( Z e , +) into ( Z e , *). It is similar ● to the proof of Claim 3.4. This would show that |Sym1_α(Y)| ≥ |Y|β=κL/δ = ρπκL > qk. We now need the following theorem due to Bourgain bounding the number of large Fourier coefficients. Theorem 4.14 (|Bou07b, Corollary 3|). Given γ,κ > 0, there is τ > 0 such that the following holds. Let q be an arbitrary modulus and H ⊂ Z a satisfy
● |H.H| < |H|¹+™. Then |{ξ ∈ Zq : |Σx∈H eq(ξx)| > |H|1−7}| < q*. Let M = maxξ≠ο ∑ y ∈ γ ∈ q (ξy) and let ξ attain M . Let S = {x ∈ Z p : {repx-x(x)| > (1 − α)|X|}. Claim 4.15. M < 3|Y|α Proof. Suppose M ≥ 3|Y|α. Consider any ξ′ ∈ ƒ( S ). Note that |Y ∩ ξ′ Y| ≥ (1 − α)|Y|. Then,
Since the above lower bound holds for any ξ ′ ∈ f ( S ), we have a contradiction to Theorem 4.14 → above as |ƒ(S)| = |X|β = pδn(κL/δ) > q κ . Thus, we have maxξ≠δ ∑ y ∈ γ ∈ q(Ey)  < 3|Y|α This implies | ∑ x ∈ x ∈ q ( ξ f ( x )) | < 3α | X | , as desired.

Application to GAPs and Bohr sets
4.3
We first state our corollary for GAP sources. Corollary 4.16. Let C > 0 be arbitrary. There exists p0, L0 E N such that for all L ≥ L0 and primes p ≥ p 0 the following holds. Let δ,μ > 0 be arbitrary. There exists an efficient ε-extractor Ext : Z p → {0,1} m for (μn,p δ ) − GAP sources (of entropy rate μδ) in Z p where n ≤ p t− 2 , X is ( τn / L, | X | 1−1/C ) -list decodable and ε < | 2m/² log p n + O(2m/p n ) where τ < 1 is a constant ( 3 poss depending on δ × μ, L, C. Proof.  Choose κ = μ /10L.  By Lemma 4.1, a ( μπ,p δ ) − GAP is ( μπ/p 0.9 δ , 0.1,ε)-additive of entropy rate δμ. To use Theorem 4.4, we need κL = 0.1δμ which is true by the choice of κ. Now choose γ = δμ/CL for a large enough C . Then, for X that is τ(δμ,C,L)n/L,|X|1−1/C)-list decodable and n ≤ p L − 2, the hypothesis of Theorem 4.4 is satisfied and hence the statement follows. ● We now state our corollary for Bohr sets. As in the previous section, we state it for constant ρ and for d = μn for simplicity. Corollary 4.17. Let C,ρ,α,μ > 0 be arbitrary. There exists p 0 , L 0 ∈ N such that for all L ≥ L 0 and primes p ≥ po the following holds. There exists an efficient ε-extractor Ext : Z p → {0,1}m for (d = μn,ρ)-Bohr sources in Z n where p ≥ max{ n 1/(L−2),Ω (( ≥ ) π )}, X is ( τn/L, | X | 1−1/C )-list decodable and ε < (3α + | X | − τ ) 2m/2 log p n + O (2m /p n ) where τ < 1 is an arbitrarily small constant depending on d, ρ and C. Proof. By Lemma 3.10, any Bohr( S, ρ ) is a (100 κd, β, ε )-additive source of entropy rate δ in Z p for κ < 1/100d whenever pn ≥ max ( 4 / ε ) d , ( ± ) d/1−δ , ( ± ) d/1−β .  Now apply Theorem 4.4 and ● using the lower bound on p the conclusion follows.
Application to affine sources and a new XOR lemma
4.4
We note that extractor for additive sources in Z n presented above indeed works for arbitrary affine spaces of constant min-entropy without any condition on list decodability as shown in Appendix C. Firstly we need a way of converting exponential sum bounds to extractors. This has been folklore and known as the Vazirani XOR lemma. However, the conditions required for that are too stringent for our character sum bounds and we need a different generalization of the XOR lemma which we state below. Lemma 4.18. Let M < N be integers with M , N coprime and N be the product of n distinct primes all greater than p.  Let σ : ZN → ZM be the function σ(x) = x  mod M.  Let X  be a distribution on Z N with |E xψ(X)| ≤ ε for every ψ ∈ Z * N . Then, |σ(X) − U| = O ((ε + n/p) log N/M]) The proof will perform a rather careful analysis of the traditional proof of the XOR lemma. See Appendix B. We believe this might be of independent interest.
5
Extractor for APs and GAPs in F n
We first focus our attention to the special case of line sources. We construct an extractor for line sources and later generalize to partial lines (or k -lines).
5.1
Extractor for lines in F n
As mentioned in the introduction, it becomes increasingly harder to construct an extractor for lines for small q (large n ), since when n is large enough compared to q , we get a proof of non- existence by the density Hales-Jewett theorem. In this section, we shall focus on 1-bit extractors. Generalizations to more number of bits follows from the XOR lemma (Lemma 2.8). In the following, let q be power of p . For the sake of completeness, we first show by a simple well known probabilistic argument, the existence of a 1-bit 0.1-extractor for lines sources in F n as long as q = Ω( n log n ). Lemma 5.1. There exists a non-explicit 0.1-extractor f : Fq → {0,1} for all line sources in Fq for n large enough as long as q > 200n log n. Proof. Choose a random f such that for each x , Pr[f(x) = 0] = 1/2. Fix an arbitrary source X = {a + tb : t ∈ Fq} ⊆ Fq. Recall that we view a set as a source which is uniform on the set. Let U denote the uniform distribution on {0, 1}. For i = 0, . . q − 1, let Y i 's be 0 − 1 indicator random variables such that Y i = 1 iff f (a + ib) = 1. We want to bound the event that | f (X) − U | > 0.1. This is equivalent to the event | f ∑ i Y i − 1/2| > 0.1. Call the above event E x . By a Chernoff bound, Pr[E X ] < 2exp(−0.02q). By a union bound over all sources X , and noting that there are q²n lines, Pr[f is not a 0.1 extractor] < 2exp(−0.02q)q²n ≤ 1 by using the lower bound on q. ● Gabizon and Raz [GR05] achieved an extractor for q = Ω(n²). Theorem 5.2 ([GR05]). There is an explicit efficient ε-extractor Ext : F n → {0,1} for all line sources in Fq where ε ≤ n/√√. In this section, we construct our extractor which beats even the randomness argument and works for q = Ω(n). The Main Theorem We state our main theorem of this subsection. As in the previous sections, the theorem follows from a lemma on exponential sums and the XOR lemma. Theorem 4. There is an explicit efficient ε -extractor Ext : F q → {0,1} for all line sources in Fn where ε ≤ 4(n/q) 1 ⁄ 2 . In order to construct our extractor, we shall be using Norm Polynomials p.272 of [LN83]. Definition 5.3 (Norm Polynomial). A norm polynomial P ∈ F q [r1, . . . rk] is a homogeneous poly- nomial of degree k which satisfies for all (c 1 ,c 2 ,...,c k ) ∈ F k , P(c 1 ,...c k ) = 0 iff c 1 = ...c k = 0. Construction of Norm Polynomials We follow the construction given in [LN83]. Let α 1 , . . . α k be a basis of E = Fqk over Fq. Set
Since, the α i , j = 0, 1, . . . k − 1, are conjugates of α i with respect to F q , the coefficients of N are in F q . Clearly, degree of N is d . Now let (c 1 , . . . c k ) ∈ F q . Then,
which is zero if and only if α 1 c 1 + . . . + α k c k = 0, which is true iff c i = 0 for all 1 ≤ i ≤ k . We now begin with the two main lemmas of this section. The first lemma is for additive characters and works for all q . The second lemma is for the quadratic multiplicative character for odd q. Lemma 5.4. There is an explicit efficient f : F q → F q such that the following holds. Let X be a line in Fn. Then for any non trivial additive character ψ,
Lemma 5.5. Let q be odd. There is an explicit efficient f : Fq → Fq such that the following holds. Let X be a line in Fq. Then for the multiplicative quadratic character χ2 we have
To extract more bits, we use the XOR lemma along with the theorem on additive characters. The general form is presented in the next subsection. Let us now focus on the problem of extracting 1 bit. When q is even, we use the trace function for the additive character which gives 1 bit. For odd q , we see that the quadratic character outputs 1 bit. Some care needs to be taken in this case. For a proof, see [GR05]. We start with the proof of Lemma 5.4. Proof of Lemma 5.4. The construction is in two steps. First we define for an arbitrary subset of coordinates S , a polynomial Q S and then partition the n coordinates carefully and apply a linear combination of the corresponding Qs's. Construction of Q S  Let X = {a + td : t ∈ Fq}.  For any subset of coordinates, say S = {x 1 , . . . , x k}, we define Q s(t) = P(a 1 + td 1 , . . . a k + td k ). Now, observe that ● Coefficient of t k in Q S (t) is P (d 1 , . . .d k ) which is zero iff d 1 = . . .d k = 0. ● On the other hand, we also have that if d 1 = . . d k = 0, then deg(Q s ) = 0. Combining the Qs's  Now, the construction is as follows. We partition the n coordinates into blocks of length 1,2,3,...,d(d ≤ 2√π(1 + 1/p)) excluding multiples of p . Without loss of gener- ality, we can assume that n is exactly partitioned in the increasing order as mentioned above. If not, we can always append all-zero coordinates and work in a dimension < 2n. (We adjust for this extra factor in the end. For now we assume n can be exactly partitioned) Let us call this family of subsets of coordinates S. We let f(t) = ∑ S ∈ S Q S (t). (We abuse notation and sometimes use f(t) and f ( x ) interchangeably with the obvious correspondence.) We now argue that this polynomial is nonzero whenever some d i is nonzero. Now starting from the rightmost coordinate, we stop when we hit a nonzero d i .  All the blocks to its right will have degree 0 and all the ones to the left will have degree less than the degree of this block. So there is no cancellation. Thus, we always have a non zero polynomial of degree d ≤ 2 √ 2 n (1 + 1 /p) < 4 √ n (taking the extra doubling of dimension into account) and we can apply Theorem 2.12 noting by the choice of the partition that gcd(q,d) = 1 (as d is never a multiple of p) to get
Next, we prove Lemma 5.5. Proof of Lemma 5.5. The construction is again in two steps. The first part is like in the previous proof but we state it for completeness. First we define for an arbitrary subset of coordinates S , a polynomial Q S and then partition the n coordinates carefully and apply a linear combination of the corresponding Qs's. Construction of Q S  Let X = {a + td : t ∈ Fq}.  For any subset of coordinates, say S = {x1,...,xk}, we define Qs(t) = P(a1 + td1,...ak + tdk). Now, observe that ● Coefficient of t k in Q S (t) is P (d 1 , . . .d k ) which is zero iff d 1 = . . .d k = 0. ● On the other hand, we also have that if d 1 = . . . d k = 0, then deg(Q s ) = 0. Combining the Q s’s Now, the construction is as follows. We partition the n coordinates into blocks of length 1,3, . . . ,d(d ≤ 2√ n ), that is, excluding multiples of 2. Without loss of generality, we can assume that n is exactly partitioned in the increasing order as mentioned above. If not, we can always append all-zero coordinates and work in a dimension < 2n. (We adjust for this extra factor in the end. For now we assume n can be exactly partitioned) Let us call this family of subsets of coordinates S. We let f(t) = ∑ S ∈ S Q S (t). (We abuse notation and sometimes use f(t) and f ( x ) interchangeably with the obvious correspondence.) We now argue that this polynomial is nonzero whenever some d i is nonzero. Now starting from the rightmost coordinate, we stop when we hit a nonzero d i . All the blocks to its right will have degree 0 and all the ones to the left will have degree less than the degree of this block. So there is no cancellation. Thus, we always have a non zero polynomial of odd degree d ≤ 4 √ ñ (taking the extra doubling of dimension into account) and we can apply Theorem 2.13 noting by the choice of the partition that the polynomial can never be a perfect square since it is of odd degree to get

5.2
Extractors for APs and GAPs in Z n
We will build on the polynomial obtained in the previous subsection to get an extractor for APs and GAPs. As we will use field operations, it will be convenient to use the notation F n rather than Z n .  Fix integers r,s with 1 ≤ s ≤ p − 1.  For α 1 , . . ,α r,b ∈ F n we denote by G α 1 , . . ,α r,b the (r, s)-GAP G α 1 ,…,ar,b = {∑ i =1 α i · t i + b : 0 ≤ t i ≤ s − 1}. It will be convenient to look at GAPs where the a i 's are linearly independent. Definition 5.6.  For α 1 , . . . ,α r , b ∈ Z r , we say the (r, s)-GAP G α 1 , . . ,α r,b is independent if α 1 , . . ,α r are linearly independent in Zn Claim 5.7. An (r, s)-GAP in F n can be written as a union of (k, s)-GAPs in F n which are inde- pendent, for k ≥ r · log s/ log p. Proof. Fix an ( r, s )-GAP Ga 1 ,...,ar,b . Let k be the dimension of the F p -linear span of { a 1 ,...,ar}. We have pk ≥ s " → k ≥ r · log s / log p . Assume, w.l.o.g., that α 1 . . . ,α k are linearly independent. We can write G α 1 , . . ,α r,b as a union of GAPs G α 1 ….α k ,b ′ where b ′ will range over the values { α k +1 · t k +1 + . . + α r · t r + b : 0 ≤ t i ≤ s − 1 } .   □ [GR05] and [DG10] used polynomials that are non-constant over subspaces of a certain dimen- sion together with Weil bounds to construct affine extractors.  We show that such polynomials are sufficient for the more general goal of constructing extractors for GAPs. For a polynomial f : F p → F p , and α 1 , . . . ,α k , b ∈ F p , we denote by f | α 1 , . . ,α k , b the polynomial f | α 1 , . . ,α k , b ( t 1 , . . , t k ) f(a1 · t1 + . . . + ak · tk + b). We first prove the following theorem. Theorem 5.8. Fix integers r, s, d with d, s < p. Fix integer k ≤ min{1, r · log s/ log p}. Suppose we are given an efficiently computable polynomial f : F n → F p such that for all a 1 , . . , a k , b ∈ F n where a 1 , . . . , a k are linearly independent, f | a 1 , . . . , a k , b is non-constant of degree 1 < d ′ ≤ d . Then we can construct an explicit efficient ε-extractor Ext : F n → {0,1} m for (r,s)-GAP sources where ε ≤ (4 log p · √p + 1) · d/s · 2m/2 + 2m /p. Remark 5.9. In the case r = 1 a d/s factor can be taken off from the ε. This will be evident in the proof. Once we have this, the two main theorems follow immediately. Theorem 5. There is an explicit efficient ε -extractor Ext : F n → {0,1} m for all k -AP sources in F n  where ε ≤ 16 log² p √πρ2m/²/k. Proof. Plugging the polynomial from Lemma 5.4 that has degree 4 ⁄ ⁄ π and is non-constant on affine subspaces of dimension 1 completes the proof. The 2 n /p factor can be dropped as it will be dominated by the first term. ● Theorem 5.10 (Extractors for GAPs). Fix integers r, s with s < p. Then we can construct an explicit efficient ε-extractor Ext : F n → {0,1} m for (r,s)-GAP sources where ε ≤ (34 log³ p · √ p) · n/(r · log s · s) · 2 m/2 + 2 m/p. In particular, when p = Ω((r · s/n)²) we can output one bit with constant error. Proof. DeVos and Gabizon ([DG10], Theorem 7) construct an explicit function f : F n → F p that is non-constant of degree 1 < d < 2n/k when restricted to any affine subspace of dimension k. Plugging this function into Theorem 5.8 finishes the proof. ● Let us now prove Theorem 5.8. The main ingredient in the theorem's proof is the following lemma that generalizes the Weil bound for exponential sums (Theorem 2.12) to the case where the sum ranges only over an AP, rather than the whole field. Lemma 5.11. Let f ∈ F p [t] be a polynomial of degree 1 < d < p. Let X be an s-AP. Let ψ be a non trivial additive character of F p . Then, for any integer 0 < s < p,
Using the XOR lemma, Lemma 5.11 implies the following. Corollary 5.12. Let f ∈ F n [t] be a polynomial of degree 1 < d < p. For any integer 0 < s ≤ p, let X be an s-AP source. Let σ : F n → F n be the function from Lemma 2.7. Then, |σ(X) − U| < ε for ε = 4 log p · √ p · d · pm/2 We prove Theorem 5.8 given the corollary. Proof. Let σ : F n → F n be the function from Lemma 2.7. Fix an (s,k)-independent GAP X = Ga1,...,ak,b Claim 5.7 implies it is enough to construct an extractor for such GAPs. We know that g = f | α 1 ,...,α k ,b is non-constant of degree d ′ where 1 < d ′ ≤ d < p . Assume w.l.o.g. that t 1 appears in g with degree greater than 1. Denote by a the maximal degree that t 1 has in g. Write g as a polynomial in t 1 whose coefficients are polynomials in t 2 , . . . , t k . Look at the coefficient gα(t 2, . . . ,t k ) of t 1 in g. From the Schwartz-Zippel Lemma gα(t 2, . . . ,t k ) = 0 with probability at most d /s ≤ d/s when choosing t 2 , . . . , t k uniformly in { 0 , . . , s − 1 } k − 1 . Note that X can be viewed as a convex combination of the s-APs X t2 ,...,t k For t 2 , . . . , t k such that g a ( t 2 , . . . , t k ) ≠ 0, it follows that the polynomial g t 2 , . . , t k ( t ) ≠ g ( t , t 2 , . . , t k ) is non-constant of degree larger than 1 and at most d. Therefore, from Corollary 5.12 we have ● |σ( X t 2 ,…,t k ) − U | ≤ 4 log p · √ p · d · p m /2 . We proceed with the proof of Lemma 5.11. Proof.  (of Lemma 5.11) The proof combines the Weil bound with Fourier analysis. It is based on two claims. The first uses the Weil bound to bound the Fourier coefficients of f composed with an additive character. Claim 5.13. Let ψ be the non trivial additive character from the lemma statement.  Then for all < < d / p . ξ ∈ Fp, we have ψ ◦ f (ξ) Proof.  Suppose ψ(x) = e p (a · x) for some a ∈ F p .  We have
The last line follows from Weil bound and by observing two things: The first is that the sum in the line before is an exponential sum with the character φ ′ ( x ) = e ρ ( α− 1 · x ) on the polynomial f'(t) = f(t) - ξψ-1t. The second is that f'(t) is also a non-constant polynomial of degree d < p so the Weil bound can be used. ● Next, we need the following claim upper bounding the L 1 Fourier norm of a set related to s-APs. Let A = {0, 1, . . . s − 1}. Denote by A(x) the indicator set of A.
| A( j )| ≤ 4 log p Proof. Note that
Now noting that |e(θ) − 1| ≥ 4{θ} we have | Ä(j) We now turn to computing the L 1 Fourier norm of A.
● With the above two claims in place, we now turn to proving the lemma.
This finishes the proof.
□
6
Acknowledgements
We thank the anonymous referees for their valuable comments to improve the quality of the writeup. We also thank the reviewer who pointed out a problem with the condition of list decodability in Section 4. This led us to making the condition much less restrictive. [BDL14] Jean Bourgain, Zeev Dvir, and Ethan Leeman. Affine extractors over large fields with exponential error.  CoRR , abs/1401.6189, 2014. [BG11] E. Ben-Sasson and A. Gabizon. Extractors for polynomial sources over constant-size Technical Report TR11-129, Electronic Colloquium on fields of small characteristic. Computational Complexity, 2011. [Bou05a] J. Bourgain. Estimates on exponential sums related to the diffiehellman distributions. Geometric and Functional Analysis GAFA , 15(1):1–34, 2005. [Bou05b] J. Bourgain. Exponential sum estimates over subgroups of zq*, q arbitrary.  Journal dAnalyse Mathmatique, 97(1):317–355, 2005. [Bou07a] J. Bourgain. On the construction of affine extractors. Geometric and Functional Anal- ysis, 17:33–57, 2007. [Bou07b] Jean Bourgain. Sumproduct theorems and exponential sum bounds in residue classes for general modulus. Comptes Rendus Mathematique , 344(6):349 – 352, 2007. [BSK12] Eli Ben-Sasson and Swastik Kopparty. Affine dispersers from subspace polynomials. SIAM J. Comput. , 41(4):880–914, 2012. [CFG+85] B. Chor, J. Friedman, O. Goldreich, J. Hastad, S. Rudich, and R. Smolensky. The bit extraction problem or t –resilient functions. In Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science , pages 396–407, 1985. [Dav00] Harold Davenport. Multiplicative number theory , volume 74 of Graduate Texts in Math- ematics. Springer-Verlag, New York, third edition, 2000. Revised and with a preface by Hugh L. Montgomery. [DG10] M. DeVos and A. Gabizon.  Simple affine extractors using dimension expansion.  In Proceedings of the 25th Annual IEEE Conference on Computational Complexity, 2010. [DGW07] Z. Dvir, A. Gabizon, and A. Wigderson. Extractors and rank extractors for polyno- mial sources. In Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, pages 52–62, 2007. Z. Dvir. Extractors for varieties. In Proceedings of the 24th Annual IEEE Conference on Computational Complexity , pages 102–113, 2009. [Dvi09] A. Gabizon and R. Raz. Deterministic extractors for affine sources over large fields. In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, pages 407–418, 2005. [GR05] Ariel Gabizon, Ran Raz, and Ronen Shaltiel.  Deterministic extractors for bit-fixing sources by obtaining an independent seed. SIAM J. Comput. , 36(4):1072–1094, 2006. [GRS06] Andrew Granville and K. Soundararajan. Large character sums. J. Amer. Math. Soc., 14(2):365–397, 2001. [GS01] A. Gabizon and R. Shaltiel. Increasing the output length of zero-error dispersers. In Ashish Goel, Klaus Jansen, JosD.P. Rolim, and Ronitt Rubinfeld, editors, Approxi- mation, Randomization and Combinatorial Optimization. Algorithms and Techniques, volume 5171 of Lecture Notes in Computer Science , pages 430–443. Springer Berlin Heidelberg, 2008. [GS08] [IK04] Henryk Iwaniec and Emmanuel Kowalski. Analytic number theory , volume 53 of Amer- ican Mathematical Society Colloquium Publications.  American Mathematical Society, Providence, RI, 2004. J. Kamp and D. Zuckerman. Deterministic extractors for bit-fixing sources and exposure- resilient cryptography. SIAM Journal on Computing , 36:1231–1247, 2006. [KZ06] X. Li. A new approach to affine extractors and dispersers. In Proceedings of the 26th Annual IEEE Conference on Computational Complexity , 2011. [Li11] [LN83] R. Lidl and H. Niederreiter. Finite Fields. Addison-Wesley, 1983. [MV77] H. L. Montgomery and R. C. Vaughan. Exponential sums with multiplicative coefficients. Invent. Math. , 43(1):69–82, 1977. [NZ96] N. Nisan and D. Zuckerman. Randomness is linear in space. Journal of Computer and System Sciences, 52(1):43–52, 1996. [Rao06] A. Rao. Extractors for a constant number of polynomially small min-entropy inde- pendent sources. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, pages 497–506, 2006. [Rao07] A. Rao. An exposition of Bourgain's 2-source extractor. Technical Report TR07-034, Electronic Colloquium on Computational Complexity, 2007. [Rao08] Anup Rao. Extractors for low-weight affine sources. Electronic Colloquium on Compu- tational Complexity (ECCC) , 15(015), 2008. [Ros02] Michael Rosen. Number theory in function fields , volume 210 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2002. [Ruz09] Imre Z. Ruzsa.  Sumsets and structure.  In Combinatorial number theory and additive group theory, Adv. Courses Math. CRM Barcelona, pages 87–210. Birkhäuser Verlag, Basel, 2009. [Sch76] W.M. Schmidt. Equations over Finite Fields. An Elementary Approach , volume 536 of Lecture Notes in Mathematics. Springer-Verlag, 1976. Ronen Shaltiel. Dispersers for affine sources with sub-polynomial entropy. In FOCS, pages 247–256, 2011. [Sha11] K. Soundararajan. Smooth polynomials: analogies and asymptotics. unpublished manuscript. [Sou] M. Santha and U. V. Vazirani. Generating quasi-random sequences from semi-random sources.  Journal of Computer and System Sciences, 33:75–87, 1986. [SV86] T. Tao and V. Vu. Additive Combinatorics. Cambridge University Press, 2006. [TV06] [Wei48] A. Weil. On some exponential sums. Proceedings of the National Academy of Sciences, 34:204–207, 1948. Amir Yehudayoff. Affine extractors over prime fields. Combinatorica , 31(2):245–256, 2011. [Yeh11] We first state the conjecture below and then the main theorem of this section. Conjecture 1 (PG(δ)). Let χ be a multiplicative character of Z p .  Let S,T ⊆ Z p such that |S|, |T| > p δ .  Then there exists ε > 0  such that
We begin with the main theorem of this section. Theorem A.1. Let p be such that p−1 have no large prime factors.  There exists an explicit efficient 2p-c2m/2-extractor Ext : Zp → {0,1} m , for (r,p tδ /r)-GAP sources (entropy rate 4δ) under PG(δ) where ε = ε(δ). We first prove a statement about APs ( r = 1) and later a statement for r > 1 and later use Lemma 2.9 to prove the main theorem . Lemma A.2.  Given an AP X = { b 0 + ab 1 : 0 ≤ a < l }, for any k such that l > p 28 , there is ε > 0 such that we have |E x ∈ x x ( x ) | < 1/p ε + 1/p o Proof. Let k be an arbitrary integer and l = kd such that d > p δ . Remove this assumption later. For −1 ≤ i ≤ k, let Also, let T = {bo + ab1 : 0 ≤ a < d} Now, | S i | , | T | = d > p δ Thus, applying Conjecture PG(δ), to each S i and T pair, we get Consider A = ∑ i ∑ s ∈ S i ,t ∈ T X ( s + t ). By the above, | A | < ( k + 2)d 2 /p ε . Rewriting A in another way,
where m ( z ) is the number of times ξ ( z ) occurs in A .  Consider any z = b 0 + ( xd + yb ) where 0 ≤ x ≤ k − 1. Then m ( z ) includes contribution from the following 2 sets: S i , i ∈ { x − 1, x } . Therefore,
Now, if some x i = 0 or x i = k , we won't have the above cancellation. We have 2(k − (k − 1))d = 2d such z ′ s each with m ( z ) ≤ d. Therefore, |d ∑ z ∈ x X( x ) | ≤ kd 2 /p ε + 2d 2 . Setting k = p δ proves the theorem.
Proof. Since the GAP is proper, let m = | r/2 | . Let
and Then, since | S | , | T | > p δ , by Conjecture PG ( δ ) , we have
This proves the theorem. Thus, combining the two lemmas above, we have the following.
Lemma A.4.  Given an (r,l)-GAP X = {bo + ∑ i=1 a,b, : 0 ≤ a, < l}, for r ≥ 1,l > p ≠ , we have
The proof of the main theorem now follows using the above lemma and the XOR lemma (Lemma 2.8) and the efficiency of the extractor follows from the fact that the discrete logarithm in Zp is efficiently computable if p – 1 is smooth. We generalize the XOR lemma on Z N under a relaxed requirement on the character sums as made precise below. We note that not all the statements are specific to Z N . However, we stick to it for simplicity. Throughout, let N = Π i =1 q i where each distinct q i ≥ p for some prime p. Let Z * N denote the units of ( Z N , *). We restate our main lemma below. The proof will be similar to that in [Rao06] but will require a more careful analysis. Lemma 4.18 Let M < N be integers with M,N coprime and N be the product of n distinct primes all greater than p.  Let σ : ZN → ZM be the function σ(x) = x  mod M.  Let X be a distribution on Z N with | E χψ ( X ) | ≤ ε for every ψ ∈ Z * N . Then,
Before we prove our lemma, we need the following. Claim B.1 (Prop 2.9 in [Rao06]). ∑ x ∈ Z N | f (x) | ≤ N 3/2 max ξ ∈ Z N | f (ξ) Lemma B.2 (Lemma 4.4 in [Rao06]). Let M < N be integers. Let σ : Z N → Z M be the function σ(x) = x  mod M. Then, for every character φ ∈ Z m, we have
The following claim is implicit in Lemma 4.4 in [Rao06]. Claim B.3. [Rao06]Let M < N be integers and w ∈ Z M . Then
We will also need the following lemmas. Lemma B.4. Let X  be a distribution on Z N  with | E X ψ ( X ) | ≤ ε  for every ψ ∈ Z N .  Let U  be the uniform distribution on Z N . Let σ : Z N → Z M be a function such that for every non trivial character φ ∈ L M , we have
and
Then, |σ(X) − σ(U)| < (ετ2 + τ1) √ M. Proof. Let φ ∈ Z M be a nontrivial character. Note that the hypothesis | E χψ(X) | ≤ ε is equivalent to |X − ∪(ψ)| ≤ ε/N for ψ ≠ 0. Then,
Now, for the trivial character we have σ(X) − σ(U)(φ) = 0 since X and U are distributions. ● Thus, the lemma follows by Claim B.1. Next, we prove the following lemma. Lemma B.5. Let M < N be integers with M , N coprime and N be the product of n distinct primes all greater than p.  Let σ : Z N → Z M  be the function σ(x) = x  mod M .  Then, for every non trivial character φ ∈ L M , we have
Proof. Recall that e(x) = e 2πix . Let φ be any non trivial character of Z M . Then φ(y) = e(wy/M) for some w ∈ Z M − {0}. Then, φ(σ(X)) = e( wx/M ). Now,
□ We now finish the proof of Lemma 4.18. Proof of Lemma 4.18. Using Lemma B.5 and Lemma B.4, we have
On uniform input, the distribution σ(U) is close to uniform. More precisely, let N = sM + t with t < M . Therefore, σ(U) is 2t((s + 1)/N − 1/M) = 2 M /N close to uniform. This finishes the proof. ● We note that extractor for structured sources in Z n presented in Section 4 indeed works for arbitrary vector spaces of constant min-entropy without any condition on list decodability. Theorem C.1.  There exists p 0 , L 0 ∈ N such that for all L ≥ L 0 and primes p ≥ p 0 the following is true. Let δ > 0 be arbitrary. There exists an efficient ε-extractor Ext : Zp → {0,1}m for (δ)-affine τ is a constant depending on δ / L. The proof will again follow from the following lemma on exponential sums and Lemma 4.18. Lemma C.2.  There exists po, Lo ∈ N such that for all L ≥ Lo and primes p ≥ po the following is there exists τ(δ/L) > 0 such that if ● X is a δ-affine source in Zn ● n ≤ p L − 2 Then, for all ξ ∈ Z*, The proof is along the lines of the general theorem above. We restate it here for completeness. Proof. Let q1,q2, · · qn be n distinct primes such that for all i,qi = 1 ( mod p ). This is guaranteed by the following claim which uses Linnik's theorem. Claim C.3. There exist L 0 > 0 and n 0 ∈ N such that for all p ≥ n 0 , L ≥ L 0 , the size of the set
is at least pL-2. Proof.  Define
By Linnik's theorem, for all p ≥ n 0 , if x > p L , we have θ(x,p) ≥ p1/2φ(p) Euler φ function which counts the number of positive integers up to n . Using φ( p ) ≤ p we have θ(x,p) ≥  ∞ .  Let
Then,
Cx Thus, π(x,p) ≥ p≠rz logx which we want to be at least n. Choose x = p L ′ for L ′ ≥ L . Then n < p L ′−² which finishes the proof. ● Thus, by the above, we have for all i, q i < p L . Also, let g i generate the order p subgroup in Z x i Define two maps φ 1 , φ 2 as follows. Let φ 1 : Z n → Π i ∈ [n] Z q i be defined by
and for q = Π i ∈ [n] qi, let φ 2 : Π i ∈ [n] Zqi → Zq be defined by
where [ x − 1] p is the inverse of x in Z p . Note that φ 2 is the Chinese remaindering map. Define function f as follows.
Let Y = f(X). |Y| ≥ qδ/L. Since f is an one-one function from ( Z p , +) into ( Z q , *) we have that Y is a multiplicative subgroup in Z*. We now appeal to the following exponential sum. Theorem C.4. [Bou05b]Given δ > 0, there is τ > 0 such that the following holds. Let q be an arbi- trary modulus and H ⊆ Z ą be a multiplicative subgroup. Then, for all ξ ∈ Z ą , | ∑ z ∈ H ∈ q (ξ f (x)) | < q- T | H | . Using Theorem C.4, we have for ξ ∈ Z*