Minerva Lecture II: Polynomial expanders and an algebraic regularity lemma
Minerva Lecture II: Polynomial expanders and an algebraic regularity lemma
The _sum-product phenomenon_ is the observation that given a finite subset A in a ring, at least one of the sumset A+A or the product set A.A is typically significantly larger than A itself, except when A is "very close" to a field in some sense. Related to this is the fact that for "typical" polynomials P of two variables, the set P(A,A) is usually significantly larger than A itself. Polynomials with this property are known as expanding polynomials. The class of expanding polynomials has been fully classified in the context of the real or complex fields by Elekes and Szabo, but the situation is not completely resolved in the context of polynomials over finite fields (which is a case of interest in theoretical computer science). Recently, however, expansion in the setting of _large_ subsets of finite fields of large characteristic has become better understood. The main new tool is an _algebraic regularity lemma,_ which improves substantially over the famous Szemeredi regularity lemma for graphs, in the setting of graphs that come from the algebra of finite fields (or more precisely, are definable in the language of that finite field). The proof of this lemma requires some nontrivial tools from model theory (including nonstandard analysis), and modern algebraic geometry (in particular, the theory of the etale fundamental group of an algebraic variety), thus providing yet another example of algebraic geometry being applied in modern combinatorics. We discuss these connections in this talk.