A regularity lemma for definable sets over finite fields, and expanding polynomials
Introductory Workshop: Model Theory, Arithmetic Geometry and Number Theory February 03, 2014  February 07, 2014
Location: SLMath: Eisenbud Auditorium
v1258
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 modeltheoretic 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 LangWeil 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.
Tao notes

Download 
v1258
H.264 Video 
v1258.mp4

Download 
Please report video problems to itsupport@slmath.org.
See more of our Streaming videos on our main VMath Videos page.