MORE ON THE SUM-PRODUCT PHENOMENON IN PRIME FIELDS AND ITS APPLICATIONS 论文

摘要

In this paper we establish new estimates on sum-product sets and certain exponential sums in finite fields of prime order. Our first result is an extension of the sum-product theorem from [8] when sets of different sizes are involed. It is shown that if [Formula: see text] and p ε < |B|, |C| < |A| < p 1-ε , then |A + B| + |A · C| > p δ (ε) |A|. Next we exploit the Szemerédi–Trotter theorem in finite fields (also obtained in [8]) to derive several new facts on expanders and extractors. It is shown for instance that the function f(x,y) = x(x+y) from [Formula: see text] to [Formula: see text] satisfies |F(A,B)| > p β for some β = β (α) > α whenever [Formula: see text] and |A| ~ |B|~ p α , 0 < α < 1. The exponential sum ∑ x∈ A,y∈B ε p (axy+bx 2 y 2 ), ab ≠ 0 ( mod p), may be estimated nontrivially for arbitrary sets [Formula: see text] satisfying |A|, |B| > p ρ where ρ < 1/2 is some constant. From this, one obtains an explicit 2-source extractor (with exponential uniform distribution) if both sources have entropy ratio at last ρ. No such examples when ρ < 1/2 seemed known. These questions were largely motivated by recent works on pseudo-randomness such as [2] and [3]. Finally it is shown that if p ε < |A| < p 1-ε , then always |A + A|+|A -1 + A -1 | > p δ(ε) |A|. This is the finite fields version of a problem considered in [11]. If A is an interval, there is a relation to estimates on incomplete Kloosterman sums. In the Appendix, we obtain an apparently new bound on bilinear Kloosterman sums over relatively short intervals (without the restrictions of Karatsuba's result [14]) which is of relevance to problems involving the divisor function (see [1]) and the distribution ( mod p) of certain rational functions on the primes (cf. [12]).