533. Terence Tao Expanding polynomials over finite fields of large characteristic, and
a
regularity lemma for definable sets
E-mail:

Submission date: 13 November 2012.

Abstract:

Let P: F \times F to F be a polynomial of bounded degree over a
finite
field F of large characteristic. In this paper we establish the following
dichotomy: either P is a moderate asymmetric expander in the sense
that |P(A,B)| >> |F| whenever A, B \subset F are such that |A| |B|
\geq
C |F|^{2-1/8} for a sufficiently large C, or else P takes the form
P(x,y) = Q(F(x)+G(y)) or P(x,y) = Q(F(x) G(y)) for some polynomials
Q,F,G. This is a reasonably satisfactory classification of polynomials of
two
variables that moderately expand (either symmetrically or asymmetrically).
We
obtain a similar classification for weak expansion (in which one has
|P(A,A)|
>> |A|^{1/2} |F|^{1/2} whenever |A| \geq C |F|^{2-1/16}), and a
partially
satisfactory classification for almost strong asymmetric expansion (in which
|P(A,B)| = (1-O(|F|^{-c})) |F| when |A|, |B| \geq |F|^{1-c} for some
small absolute constant c>0).
The main new tool used to establish these results is an algebraic
regularity lemma that describes the structure of dense graphs generated by
definable subsets over finite fields of large characteristic. This lemma
strengthens the Szémeredi regularity lemma in the algebraic case, in that
while the latter lemma decomposes a graph into a bounded number of
components,
most of which are ε-regular for some small but fixed ε, the
latter lemma ensures that all of the components are
O(|F|^{-1/4})-regular.
This lemma, which may be of independent interest, relies on some basic facts
about the étale fundamental group of an algebraic variety.