Let P: F x F -> F be a polynomial of bounded degree on a large finite field F. Informally, we say that P is an expanding polynomial if P(A,A) is larger than A for all sets A of a certain size. It is still a challenging combinatorial problem to classify expanding polynomials for medium sized sets A. However, for large sets A (in particular, larger than |F|^{15/16}), we have a fairly satisfactory classification, thanks to an "algebraic regularity lemma"
that gives a good structural description of large graphs definable over finite fields, analogous to the Szemeredi regularity lemma but stronger in certain key respects. The proof of this lemma initially relied heavily on algebraic geometry tools (in particular, the theory of the etale fundamental group), although subsequent proofs have largely eliminated this dependence. In this talk we give an overview of these developments.
Copyright. All Rights Reserved.