A regularity lemma for definable sets over finite fields, and expanding polynomials

Szemeredi's regularity lemma provides a structural description of arbitrary large dense graphs; roughly speaking, it decomposes any such graphs into a bounded number of pieces, most of which behave "pseudorandomly". While this lemma applies to arbitrary graphs, the dependence on constants can be terrible, and there can also exist "bad" components which are not pseudorandom. However, these defects can sometimes be removed if further assumptions are placed on the original graph. We present an "algebraic regularity lemma" which covers the case when the graph is definable (with bounded complexity) over a finite field of large characteristic. By combining the model-theoretic classification of definable sets in this setting with an ultraproduct argument (to transfer to the characteristic zero setting) combined with algebraic geometry tools (such as the etale fundamental group) and the Lang-Weil inequality, we are able to get much better control on the pseudorandomness and definability properties of the components, and also can exclude the existence of bad components. As an application of this lemma, we classify the polynomials over finite fields of large characteristic which are "expanding" in a combinatorial sense.

Please report video problems to itsupport@slmath.org.

See more of our Streaming videos on our main VMath Videos page.